Obstacle Avoidance and Local Path Planning for Mobile Robots using the Fast Elastic Band

FEB를 이용한 이동로봇의 장애물 회피와 국지경로계획 Obstacle Avoidance and Local Path Planning for Mobile Robots using

the Fast Elastic Band

김 일 환^*

(Ilhwan Kim

)

1

Kangwon National University

Abstract: This paper presents a new obstacle-avoidance method for mobile robots. This approach, called the FEB (Fast Elastic Band) method, has been developed and successfully tested on the experimental mobile robot PHOPE-1S. The FEB method eliminates the shortcomings of the elastic band method previously introduced, yet retains all the advantages of its predecessor. The FEB algorithm is computationally efficient, and it allows continuous and fast motion of the mobile robot without stopping for obstacles. The FEB-controlled mobile robot traverses very densely cluttered obstacle courses and is able to pass through narrow openings or narrow corridors without oscillations. The results of the simulation and experiment have verified the validity of the proposed method.

Keywords: local path planning, obstacle avoidance, elastic band, mobile robot

I. 서론

서비스 이동로봇을 목적지까지 자동적으로 움직이게 하는 일은 쉽지 않다. 경로 계획은 로봇이 목적지에 도달하기 위 한 경로를 계산하기 위해서 실제 환경과 로봇의 모델을 이용 한다. 경로 계획에서 가장 일반적인 문제는 경로 계획기가 만드는 많은 과정들로 인한 계산의 부담이 매우 크다는 것이 다. 경로 계획기의 출력은 로봇이 장애물에 충돌하지 않고 목적지에 도달할 수 있는 연속적인 경로이다. 그러나 실제 모델은 불확실성과 움직이는 장애물들로 인하여 완벽하지 않고 부정확하다. 따라서 무조건 계획된 경로를 따라간다면 충돌이 발생할 수 있다. 이러한 이동로봇의 경로계획은 전역 경로계획(GPP: Global Path Planning)과 국지경로계획(LPP: Local Path Planning) 으로 나눌 수 있다. GPP는 환경에 대한 정보가 주어진 경우에 시작점에서 목표지점까지의 최단거리 및 최 단시간으로 이동할 수 있는 경로를 계산한다. LPP는 환경 센 서를 통해 환경을 인식하고 정적 및 동적 장애물을 회피해 목적지로 이동하는 경로를 실시간으로 계획한다. GPP는 미리 정해진 지도를 통하여 경로를 계산하고 LPP는 국지적으로 환경을 인식하여 이를 실시간으로 수정하여 보완하는 일종 의 제어기라 할 수 있다. LPP는 한 경로지점에서 다음 경로 지점으로 이동할 때 최단거리와 최단시간으로 이동할 수 있 는 국지경로를 만들고, 이동시 정적 및 동적 장애물에 대한 충돌 예측과 충돌 회피, 그리고 로봇의 기구학적 및 동력학 적인 모션제어를 포함한다[1,2]. 국지경로를 만드는 방법은 NF1, A*, D* [4,5] 등이 연구되어 왔다. 국지 경로는 최소회전 반경, 이동속도 등을 고려하여 유연한 경로로 만들 필요가 있다. NF1, A* 등으로 만들어진 국지경로는 유연한 경로로 만들어지는 것이 아니기 때문에 Quinlan[3] 등은 이동로봇의

국지경로에 EB (Elastic Band)라는 개념을 도입하여 국지경로 를 유연한 경로로 만드는 방법을 연구하였다. EB는 NF1에서 만든 국지경로를 버블을 이용하여 변형하며, 버블들을 업데 이트 하면서 주행 중 실시간으로 환경변화에 대한 영향을 경 로에 반영해 유연한 충돌 자유 경로를 만들어주는 방법이다.

국지 경로 계획은 환경 변화를 인식하여 실시간으로 동작해 야 하기 때문에 각각의 처리 루틴의 수행시간이 빠르면 빠를 수록 좋다.

따라서 본 연구에서는 유연한 경로를 만들고 유연한 경로 를 만들기 위한 수행시간을 빠르게 하도록 하기 위하여 기존 의 EB를 확장하고 수정한 FEB (Fast Elastic Band)를 제안한다.

서비스 로봇에 적용하여 실험하였으며 결과를 통하여 그 유 효성을 검증하였다.

II. FAST ELASTIC BAND

Quinlan[3] 등이 제안한 버블은 충돌 자유 공간의 국부 부 분집합으로 식 (1)과 같이 나타낸다. 버블간의 내부와 외부 인공력(artificial force)을 이용하여 버블을 실시간으로 업데이 트 할 수 있도록 하여 환경변화에 대한 충돌 자유공간을 유 지할 수 있도록 하였다.

{ },

{ , , },

0... 1

B = B B = c r m i = n − (1) 여기서 r

는 버블의 반지름, c

= ( , x

y

) 는 버블의 중심,

m

는 마스킹 거리, n 는 버블의 수이다. 한편, 내부 인공력 은 이웃한 버블 사이에 수축시키는 힘으로서 버블간의 느슨 함을 제거하여 유연한 경로를 생성하는 역할을 하지만, 원하 는 경로가 직선이 아니고 꺾어지는 경우에는 내부 인공력이 영이 될 때까지 버블에 영향을 미치므로 버블의 중심이 원하 는 경로에서 벗어나게 되고 버블의 업데이트가 계속되면 결 국에는 경로가 직선이 된다. 고로, 이러한 문제점을 해결하기 위하여 본 논문에서는 식 (2)와 같이 새로운 버블을 정의한다.

* 책임저자(Corresponding Author)

논문접수: 2010. 4. 16., 수정: 2010. 6. 4., 채택확정: 2010. 6. 10.

김일환: 강원대학교 전자통신공학과([email protected])

※ 본 논문은 2010년도 ICROS 학술대회에서 초안이 발표되었습니다.

Copyright© ICROS 2010

, , , ,

{ , , , , , }, 0... 1

i i i r i l i r i l i

B = c r d d ip ip i = n − (2) 여기서 d 와

d 는 각각 오른쪽과 왼쪽 방향으로 장애물

과 가장 가까운 거리, ip

= ( ipx ipy

,

) 와 ip

= ( ipx

,

,

)

ipy

는 버블의 교차점이다. 식 (1)에서 EB는 버블의 중심 과 반지름 등으로 정의되나, FEB에서의 버블은 식 (2)에서 보 듯이 좌우 양방향의 장애물과의 거리와 버블의 교차점을 포 함하여 정의한다. 버블의 중심에서 장애물과 가장 가까운 거 리에 있는 장애물의 위치를 오른쪽 방향으로는 P 로, 왼쪽

방향 으로는 P 로 나타낸다. 버블과 관계된 장애물 중 최대

거리의 장애물과의 거리를 R

라 하고 버블의 중심과 P

또는 P 중 가장 가까운 거리를 버블의 반지름으로 하며

식 (3)에 의해 구한다.

,

,

, , max

*, { }

, ,*

, max

*, { }

, ,*

, ,

{ } { : }

{ } arg{ min } { }

{ } { : }

{ } arg{ min } { }

{ } min{ , }

r ij

l ij

r ij r j i j

r i P P i j

r i i r i

l ij lj i j

l i P P i j

l i i l i

i r i l i

p P c P R

P c P

d c P

P P c P R

P c P

d c P

r d d

∈

∈

= − <

= −

= −

= − <

= −

= −

=

(3)

그림 1(a)에서 장애물 중 버블의 중심과 가장 가까운 장애 물을 구하고, 식 (4)로부터 인공력을 계산하고, 식 (6)로 업데 이트하면 그림 1(b)와 같이 새로운 버블이 생기고 양방향으 로 장애물과의 거리가 같아짐을 알 수 있다. 이렇게 양방향 의 거리가 일정해지기 때문에 업데이트의 종료 시점을 정확 히 예측할 수 있다. 즉, 버블의 반지름과 좌우 측 장애물과의 거리가 비슷해지면 그 버블은 더 이상 업데이트를 필요로 하 지 않게 된다. 첫 번째 버블은 버블의 시작점으로 로봇의 현 재 위치가 되고, 마지막 버블은 목적지가 된다. 첫 번째와 마 지막의 버블의 중심은 고정되고, 버블의 반지름은 장애물과 의 유클리디언 거리에 따라 변경된다. 버블의 오른쪽 방향 장애물 중 가장 가까운 장애물의 인공력을 fr 이라 할 때, fr 은 장애물과의 거리가 R

보다 크면 0이고, R

보다 작거나 같으면 식 (4)와 같이 계산된다.

, ,

, , , , ,

, , , , ,

( , )

( )cos(arctan 2( , )) ( )sin(arctan 2( , ))

i r i l i

x i r i c i r i c i r i

y i r i c i r i c i r i

Max d d

fr d y py x px

fr d y py x px

γ γ γ

=

= − − −

= − − −

(4)

마찬가지로 왼쪽 방향 장애물 중 가장 가까운 장애물의 인 공력을 fl 이라 할 때, fl 은 식 (5)와 같이 계산된다.

. , , , ,

. , , , ,

( )cos(arctan 2( , )) ( )sin(arctan 2( , ))

x i r i c i l i c i l i

y i r i c i l i c i l i

fl d y py x px

fl d y py x px

γ γ

= − − −

= − − − (5)

식 (6)을 이용하여 장애물에 대한 인공력이 반영된 새로운 버블의 중심이 구해진다

, , 1

i i i

i t i t i

c fr fl c c

c

∆ = +

= + ∆ (6)

III. 시뮬레이션 및 실험 결과 1. EB와 FEB의 비교

기존의 EB는 내부 및 외부의 인공력(artificial force)으로 버 블의 상태를 유지하게 되는데, 외부 인공력은 장애물로부터 로봇의 여유 간격을 증가시키는 힘이고, 내부 인공력은 이웃 한 버블의 중심과의 관계에 의해 영향을 미치는 힘이다. 이 (a) Before updating the bubble.

(b) After updating the bubble.

그림 1. Fast elastic band.

Fig. 1. The fast elastic band.

(a) m = 1 (b) m = 10 (c) m = 20

(d) m = 1 (e) m = 2 (f) m ≥ 3 그림 2. 시뮬레이션 결과.

Fig. 2. Simulation results.

러한 내부 인공력은 버블의 유연한 경로를 만드는 데는 도움 이 되지만 이웃한 버블의 중심이 꺾인 경우에는 버블의 업데 이트가 반복될수록 그림 2(b)와 (c)에서 보는 것처럼 버블의 중심을 밖으로 밀어내는 역할을 한다. 그림 2(a), (b), (c)는 Philippsen[4] 의 EB를 사용해 만든 버블로 반복회수(m)를 1에 서 20까지 하여 반복계산을 실행해보면 업데이트가 진행될 수록 버블의 위치가 변해가는 것을 알 수 있다. 반면에 그림 2(d), (e), (f) 는 본 연구에서 제안한 FEB를 사용해 버블을 만들 고 업데이트를 수행한 경우로 내부 인공력의 영향이 없으므 로 버블의 위치가 만들어지면 m이 3 이상에서도 버블의 크 기가 변하지 않는다. 따라서, 본 논문에서는 내부 인공력을 사용하지 않고, 외부 인공력 만을 사용하여 EB를 만든다. 내 부 인공력을 사용하지 않으므로 그만큼 계산 시간이 단축될 뿐만 아니라 반복계산을 하더라도 외부 인공력의 변화가 없 는 경우에는 주행 경로가 변경되지 않는 장점이 있다.

2. 이동로봇 시스템과 FEB의 구현

실험에 사용한 이동로봇은 그림 3에 보인 것과 같이 서비 스로봇을 만들기 전에 알고리즘 실험용으로 개발한 이동로 봇인 PHOPE-1S를 사용했다. PHOPE-1S의 크기는 38(W)x 50(D)x120(H)cm 로 ActivMedia의 P3-DX를 플랫폼의 베이스로 사용한다. 센서로서는 I2C 방식의 12개의 초음파센서(SRF08),

바닥감지센서 및 인체감지센서 등이 있다. FEB는 그림 4에 나타낸 내비게이션 시스템의 일부분으로 실행된다. 내비게이 션 시스템은 executor, GPP, LPP, FEB, localizer, 맵 DB, 로봇 플 랫폼의 각종 센서를 처리하는 컴포넌트들로 구성되어 있다.

Executor 는 사용자의 입력을 받아 실행해주는 역할을 담당하 고, GPP는 executor의 명령으로 시작점과 종료 점을 입력 받 아 전역 맵 DB에서 전역 맵을 읽어와 시작점과 종료 점을 연결해주는 경로지점(way point)을 만들어 준다. GPP는 격자 맵 기반 A*를 이용해 1m에서 2m 간격으로 경로지점을 만든 다. LPP는 GPP에서 만들어진 경로지점들을 이동할 수 있는 그림 3. 이동 로봇(PHOPE-1S).

Fig. 3. The mobile robot (PHOPE-1S).

그림 4. 내비게이션 시스템.

Fig. 4. The navigation system.

그림 5. FEB의 구조.

Fig. 5. The structure of FEB.

(a) Local map (8x8m) (b) C-space map (4x4m)

(c) FEB map (4x4m) 그림 6. 내비게이션 맵.

Fig. 6. The navigation map.

국지경로지점(local way point)을 만들어주는데, 레이저 센서로 부터 읽어온 데이터를 국지맵(local map)으로 만들고, 국지맵 을 이용해 로봇이 주행 가능한 국지경로지점을 만든다. LPP 는 5*의 시간 간격으로 주기적으로 실행된다. GPP와 LPP는 모두 A*로 경로를 만든다. LPP에서 사용하는 맵은 그림 6에 나타낸 것처럼 두 가지가 있다. 첫 번째는 레이저 센서로부 터 인식된 환경 정보로 만드는 국지맵이다. 레이저센서의 최 대측정거리가 4m이므로 8m*8m의 크기로 161개(5cm/cell)의 셀을 사용한다. 두 번째는 경로지점을 만드는 A*에서 국지맵 의 일부분인 4m*4m의 크기로 41*41개(10cm/cell)의 맵을 사

용해 먼저 로봇의 C-space를 맵으로 만들고, 이로부터 GPP에 서 만든 경로지점을 시작점과 끝점으로 하여 국지경로를 만 든다. FEB에서는 그림 6(c)에서와 같이 국지맵(local map)으로 부터 4m*4m의 크기로 81*81개(5cm/cell)의 맵을 사용하는데 LPP 에서 만든 국지경로지점으로부터 초기 버블을 만든 후 앞에서 설명한 방법으로 업데이트하면 그림 6(c)에서 보는 것처럼 국지경로지점보다 유연한 경로가 만들어진다.

3. 주행실험

실험에서는 GPP에 의해 만들어진 경로지점을 LPP와 FEB 에 의해 주행한다. LPP는 5* t ∆ 의 주기로 실행되고, FEB는

∆ 의 주기로 실행된다. 실험에서 t t ∆ 는 0.1sec로 실행되므로 LPP 에 의해 만들어지는 국지경로는 0.5sec마다 업데이트 된 다. LPP의 국지경로는 0.5sec의 시간간격 동안 장애물 정보가 반영되지 않지만 t ∆ 마다 주기적으로 실행되는 FEB에서는 환경의 변화가 즉각적으로 반영되므로 주행 중에 발생하는 정보에 의해서 LPP의 국지경로계획과 FEB에서 주행 가능여 부의 판단은 달라질 수 있다. 주행 실험은 그림 7(a)에서 보 는 것처럼 좁은 복도를 주행시키는 실험이다. 실험에서는 두 개의 연속되는 좁은 복도를 진입하도록 실험했다. 복도의 폭 은 90cm정도로 일반적인 화장실 입구이다. 첫 번째 a 위치에 서 첫 번째 좁은 복도로 진입하기 위해 FEB에서 만들어진 경로에 따라 이동해서 좁은 복도로 진입에 성공한 실험이고, b 위치에서 첫 번째 좁은 복도를 나와 두 번째 좁은 복도로 진입하기 전 FEB에 의해 진입 경로가 만들어지는 과정이다.

c 위치에서는 두 번째 복도로 진입에 성공하고 마지막 경로 지점으로 이동하기 전 FEB에서 만든 경로를 보여준다.

IV. 결론

본 연구에서는 실시간으로 경로 수정이 가능하며 충돌 자 유 공간을 보장하기 위한 장애물과의 충돌회피 및 국지경로 계획 방법인 EB를 보다 짧은 시간 내에 예측 가능한 반복계 산시간으로 수행되도록 수정하여 실시간으로 환경의 변화를 즉각적으로 반영할 수 있도록 하였고, 버블이 충돌자유공간 을 보장한다는 특성을 이용하여 정적 및 동적인 충돌예측과 회피가 가능하도록 하였다. 즉, 버블의 업데이트에 내부 인공 력을 사용하지 않아 반복계산에 의한 문제점인 이웃한 버블 의 영향에 의한 버블의 중심점 이동이 없도록 개선하였다.

외부 인공력에 좌우 양방향의 장애물 거리를 사용하도록 수 정함으로써 반복계산시간을 줄였다. Quinlan[3] 등이 제안한 EB 에서는 100ms이내로 수행하는 것이 어려웠으나, 본 논문 에서는 FEB의 실행시간을 100ms이내로 가능함을 보였다. 실 험을 위하여 내비게이션 시스템에 FEB를 구현하여 좁은 공 간의 주행실험에 의해 그 효용성을 보였다.

참고문헌

[1] J. Borenstein and Y. Koren, “Obstacle avoidance with ultrasonic sensors,” IEEE J. Robotics and Automation, vol. 4, no. 2, pp.

213-218, 1988.

[2] J. Borenstein and Y. Koren, “Real-time obstacle avoidance for fast mobile robots,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 19, no. 5, pp. 1179-1187, 1989.

[3] S. Quinlan and O. Khatib, “Elastics bands: Connecting path

a

b

c

(a) Trajectory through narrow corridors

(b) Trajectory through position ‘a’

(c) Trajectory through position ‘b’

(d) Trajectory through position ‘c’

그림 7. 좁은 복도에서의 주행.

Fig. 7. Travelling through the narrow corridors.

planning and control,” Proc. of IEEE International Conference on Robotics and Automation. pp. 802-807, 1993.

[4] R. Philippsen and R. Siegwart, “Smooth and efficient obstacle avoidance for a tour guide robot,” Proc. of IEEE International Conference on Robotics and Automation, Lausanne, Switzerland, pp. 446-451, 2003.

[5] O. Brock and O. Khatib, “High-speed navigation using the global dynamic window approach,” Proc. of IEEE International Conference on Robotics and Automation, pp. 341-346, 1999.

[6] I. H. Kim, “Obstacle avoidance for mobile robots using a new elastic band,” Proc. of ICROS Annual Conference 2010, Chuncheon, Korea, pp. 194-195, May 2010.

김 일 환

1993 년 일본 토호쿠대학 기계공학과 박

사 졸업. 1995년~현재 강원대학교 전자

통신공학과 교수. 관심분야는 제어시스

템, 휴먼 인터페이스.