Autonomous Navigation of Nonholonomic Mobile Robots Using Generalized Voronoi Diagrams

ISSN 2283-4846(Online) / ISSN 2233-6036(Print)

일반화된 보로노이 다이어그램을 이용한 논홀로노믹 모바일 로봇의 자율 주행

^a,c

^c

^b*

Autonomous Navigation of Nonholonomic Mobile Robots Using Generalized Voronoi Diagrams

Minglei Shao

^a,c

^c

^b*

a

Department of Mechanical Engineering, Hanyang University, 55 Hanyangdaehak-ro, Ansan, Gyeonggi-do, 426-791, Korea

b

Department of Robot Engineering, Hanyang University, 55 Hanyangdaehak-ro, Ansan, Gyeonggi-do, 426-791, Korea

c

Guangzhou Institute of Advanced Technology, 1121 Haibin Road, Nansha, Guangzhou, 511458, China

ARTICLE INFO ABSTRACT

Article history: This paper proposes an autonomous navigation method for a nonholonomic mobile robot, based on the generalized Voronoi diagram (GVD). We define the look-ahead point for a given motion constraint to determine the direction of motion, which solves the problem of a minimum turning radius for the real nonholonomic mobile robot. This method can be used to direct the robot to explore an unknown environment and construct smooth feedback curves for the nonholonomic robot. As the trajectories can be smoothed, the position of the robot can be stabilized in the plane. The simulation results are presented to verify the performance of the proposed methods for the nonholonomic mobile robot.

Furthermore, this approach is worth drawing on the experience of any other mobile robots.

Received 28 November 2014 Revised 23 January 2015 Accepted 27 January 2015

Keywords:

Generalized Voronoi diagram Nonholonomic mobile robot Autonomous navigation Sensor-based

* Corresponding author. Tel.: +82-31-400-5245 Fax: +82-31-460-5090

E-mail address: [email protected] (Kyoosik Shin).

1. 서 론

최근 자율 주행 로봇의 경로 계획과 경로 추종에 관한 많은 연 구가 이루어지고 있다. 그 중 일반화된 보로노이 다이어그램 (GVD; generalized Voronoi diagram) 을 이용한 로드맵은 작업 공간에서 장애물과의 거리를 최대화하며, 지역적 거리 정보만을 이 용해서 지도를 구성하기 때문에 미지의 환경에서 시작하여 센서 기반 점진적 지도 구성을 수행한다. GVD를 경로 계획에 맨 처음 언급한 것은 Sowat이며

, 이후 Ó’Dúnlaing과 Yap은 GVD를 평 면상의 점 로봇에 적용하였다

. Choset 과 Burdic은 일반화된 보 노로이 그래프(GVG)를 정의함으로써 GVD를, 고차원으로 확장 시켰다

.

Nagatani 와 그의 동료들은 자동차 형태의 로봇(car-like robot) 에 적합하도록 GVD를 확장하였다

. 로봇이 취할 수 있는 회전 반경을 기준으로 베지어 곡선을 이용해서 매끄럽지 않은 GVD를 부드럽게 변형하였는데, 여러 후보 경로를 주행함으로써 평가하고, 그 중 최적의 경로를 취하는 방법이다. 그러나 많은 경우, 모바일 로봇은 자동차 형태보다 더 단순한 형태, 즉 두 개의 능동 바퀴와 수동 캐스터를 갖는 형태로서, 이러한 로봇은 논홀로노믹 구속조건 을 갖지만, 제자리 회전이 가능하다. 이 경우 Nagatani의 방법은 너무 복잡한 방법이라 하겠다.

이 논문은 모바일 로봇의 자율 주행에 관한 것으로, GVD를 가

급적 추정하되, 일정 거리의 앞보기 점(look-ahead)을 단순 추적

(pure pursuit) 하여 매끄럽지 않는 GVD를 실시간으로 매끄럽게

Fig. 1 Example of GVD, solid lines segments correspond to the set of points equidistant to two closest obstacles 낸다. 시스템은 초음파 센서와 적외선 센서를 이용하여 장애물을

탐지 많이 사용 하였다

.

이 논문의 구성은 다음과 같다. 2절에서는 GVD의 정의 및 추종 에 대한 기존 연구를 요약하며, 3절에서는 해당 논홀로믹 로봇을 정의하고 모델링하고, 이 로봇이 GVD를 추종하는 알고리즘에 대 해서 설명한다. 4절에서 다양한 매개변수를 적용해서 시뮬레이션 하고 토론할 것이다. 5절에서는 결과를 요약한다.

2. 일반화된 보로노이 다이어그램

2.1 GVD 정의

GVD 는 1차원 로봇의 작업공간(workspace)을 2차원 평면으로 가정하자. 작업 공간 안에는 로봇이 침범할 수 없는, 장애물이라 불리는 볼록한 영역(convex area)이 여러 개 존재한다. 볼록하지 않은 장애물은 여러 개의 볼록한 장애물로 나눌 수 있으므로 볼록 하다는 조건은 제약조건이라기 보다는 기술의 편의상 붙인 것이라 하겠다. 장애물이 차지하지 않은 공간을 자유 공간(free space)이 라 하며, 모바일 로봇은 이 자유 공간 상에서 움직이게 된다.

일반화된 보로노이 다이어그램(GVD; generalized Voronoi diagram) 은 자유 공간의 1차원 부분 집합으로서, 서로 다른 두 장 애물과의 거리가 같은 점들의 집합이다. 보로노이 다이어그램을 일 반화하기 위해서, 점과 장애물과의 거리를 정의해야 한다. 한 점 x∈R

에서 영역 C

∈R

로 표현되는 장애물 i까지의 거리 d

(x)는 그 장애물 상의 가장 가까운 점과의 거리로 정의한다:

( ) min

i c C

d x x c

= ∈ − (1)

이를 바탕으로 장애물 i까지의 거리와 장애물 j까지의 거리가 같 은 점들의 집합 SS

를 정의할 수 있다.

{ 2 : ( ) ( ) and }

ij i j i j

SS = x ∈ R d x = d x ∇ ≠ ∇ d d (2) 이를 등거리 전사 곡면(two-equidistance surjective surface)이 라고 명명하자. 이 곡면은 스칼라 장(field)의 높이가 0인 등위면 (level surface) 에 해당한다. 식 (2)의 정의에서 기울기가 같지 않 아야 한다는 조건은 d

− d

의 접 사상(tangent map)이 전사함수가 되도록 하고, 이는 곧 원상 정리(pre-image theorem)에 따라서 SS

의 여차원(co-dimension)이 항상 1이 되도록 보장한다. 집합

SS

를 선이 아닌 면이라 칭한 것은 차원보다는 여차원을 강조한 것이라 하겠다.

( d _i − d _j )( ) x  d x _i ( ) − d x _j ( ) (3) 우리가 관심을 갖는 것은 SS

전체가 아니라, SS

에 내재하는 등거리가 다른 어떤 장애물과의 거리보다 가까운 영역으로 한정시 켜야 한다. 즉 등거리 면(two-equidistance face) F

를 다음과 같 이 정의하자.

{ : ( ) ( ) }

ij ij i h

F = x ∈ SS d x ≤ d x ∀ h (4)

F

는 1차원 집합인 GVD의 최종 빌딩 블록이 되는데, 이를 강조 해서 GVD 모서리(GVD edge)라고 일컫기도 한다. GVD 모서리는 유계이며, 그 양단은 교차점(meet point)이거나 경계점(boundary point) 이다. 교차점은 삼중 등거리 점(three-equidistance point)으 로서 세 개의 GVD 모서리가 만나는 점이고, 반면에 경계점은 장 애물과의 거리가 0이 되는 점이다.

GVD 는 모든 GVD 모서리의 합집합이다. 즉,

1

1 1

n n

i j i ij

GVD ⁻ F

= = +

= ∪ ∪ (5)

여기서, n은 장애물의 개수이다. Fig. 1은 GVD의 예를 보여주고 있다. 그림에서 환경은 네 개의 장애물로 둘러쌓인 공간에 세 개의 직사각형 장애물이 놓인 경우이다.

2.2 점 로봇의 GVD 추종

GVD 는 장애물과의 거리를 최대화하는 측면에서 점 로봇(point

robot) 이 취할 수 있는 최적 경로이다. 게다가 GVD는 오직 로봇에

부착된 선세의 거리 정보만으로 정의되기 때문에 센서 기반 맵 생성

뿐만 아니라 추종 알고리즘을 구현할 수 있다. 여기에, 일반적으로

시작점과 목표점이 GVD 상에 있지 않으므로, 시작점에서 GVD로

Fig. 2 Example of GVD Fig. 3 Mobile robot model

접근하는(accessing) 알고리즘과 GVD를 벗어나(departing) 목표 점으로 도달하는 알고리즘이 더해져서 점 로봇의 자율주행을 가능 케 한다(Fig. 2).

자유공간 상의 점 x에 대해 d

(x)를 가장 가까운 장애물까지의 거리, d

(x)는 두번째로 가까운 장애물까지의 거리라고 하자. 거리 함수의 기울기 ∇d

(x)는 x에서 장애물 i 상의 가장 가까운 점을 가리키는 단위 벡터이다. 시작점에서 로봇이 기울기 ∇d

방향으로 이동하다보면 GVD 상의 한 점, 즉, d

− d

= 0 인 점에 도달하게 된다. 한편 GVD 모서리는 D(x) = d

(x) − d

(x) 의 높이 0인 등위 면이므로, GVD 모서리의 점 x 에서의 접선 공간(tangent space) 은 ∇D = ∇d

− ∇d

의 영공간(null space)에 해당하고, 이는 ∇D 에 수직이다. 로봇은 접선을 따라 이동하되, 선형화에 따른 오차를 보정해 줌으로써, GVD 모서리를 추종할 수 있다. GVD를 떠라 목표점을 향할 때는 접근할 때와 반대 방법으로 하면 된다.

3. 논홀로노믹 로봇과 GVD 추종

앞 절에서 GVD가 무엇이고, 이것이 어떻게 점 로봇의 자율주행 에 이용될 수 있는지 설명했다. 그러나 대부분의 모바일 로봇은 점 로봇이 아니라, 바퀴를 갖는, 그래서 논홀로노믹 구속조건을 갖는 로봇이다. 이 절은 논홀로노믹 모바일 로봇이 GVD를 효과적으로 추종할 수 알고리즘을 제시한다.

3.1 모바일 로봇 모델

이 연구에서 가정한 모바일 로봇의 모델은 두 Fig. 3과 같다. 로 봇의 짜임새(configuration)를 표현하기 위해 고정된 좌표계 S와 로봇에 부착된 로봇 좌표계 B를 정의하였다. 로봇의 짜임새 q는 로봇 프레임 B의 고정 프레임 S에 대한 상대 위치로 표현할 수 있 으며, 이는 2차원 유클리드 군 SE(2) 상의 한 점에 해당한다. 즉,

( , , ) 1 2 (2)

q = x x θ ∈ SE (6)

여기서, (x

, x

) 는 로봇 프레임 B의 원점의 위치이며, θ는 로봇 프 레임 B의 회전 각도이다.

모바일 로봇은 옆으로 속도를 낼 수 없는 논홀로노믹 구속조건을 갖는다. 즉, 특정 짜임새에서 로봇이 낼 수 있는 속도는 전후 주행 과 회전이라는 두 성분의 조합만 가능하다. 따라서, 비록 짜임새 공간이 3차원이더라도, 두 개의 능동 바퀴로서 충분히 그 자세를 제어할 수 있다. 각 바퀴의 속도를 

과 

이라고 하고, 이 바퀴의 속도 제어는 로봇의 제어에 비해 충분히 빠르다고 가정하자. 표현 을 간단히 하기 위해, 각 바퀴의 속도 대신 로봇의 선 속도는 

= ( _

+ _

)/2 와 회전 속도  = ( _

− 

)/w(w는 로봇의 폭)를 이 용하자. 로봇의 상태 방정식은 다음과 같은 비선형 미분방정식으로 표현된다.

0 0

co sin

s v

q v

θ θ ω

⎡ ⎤

⎢ ⎥

⎢ ⎥

= ⎢ ⎢ ⎥ ⎥

⎢ ⎥

⎣ ⎦

 (7)

≠  인 경우, 이 식을 적분하면,

0 0

0 0

(sin(

(

) sin ) )

cos( co s ) i f 0

v v

t

q t

t

ω ω

θ θ

ω θ

ω θ ω

ω

⎡ + Δ − ⎤

⎢ ⎥

⎢ ⎥

Δ = ⎢ ⎢ ⎢ ⎣ + Δ − Δ ⎥ ⎥ ⎥ ⎦

− ≠ (8a)

을 얻을 수 있다. 만약에    이면,

(8b)

식 (8b)는 식 (8a)에 로피탈 정리(L'Hopital rule)를 적용해서 얻

을 수도 있다. 식 (8)은 샘플링 타임 Δt 동안 입력 ( 

,  ) 가 가해졌

을 때, 짜임새의 변위이다.

Fig. 4 Circling by a look-ahead point Fig. 5 GVD tracing by circling

3.2 앞보기 점을 통한 선회

Fig. 1 에서 보는 것처럼 GVD는 연속이지만, 부드럽지는 않다.

특히 교차점에서 GVD는 갑자기 그 방향이 바뀌는 경우가 많다.

만약 논홀로노믹 모바일 로봇이 이 경로를 정확히 추종하고자 한다 면, 진행 속도를 0으로 늦추고 제자리 회전을 해야 한다. 이는 아주 협소한 공간이 아닌 이상 분명히 낭비이다. 더욱이 자동차 형태의 로봇의 경우 제자리 회전 자체가 불가능하다.

이런 비효율성을 없애기 위해, 앞보기 점(look-ahead point) 설 정을 통해 선회를 하자. 구체적으로, 현재 위치와 방향에서 앞보기 점에 도달하기 위한 (이 때 방향은 중요하지 않다) 선회 반경을 결 정하여 그것을 로봇이 따르게 하는 것이다 (Fig. 4). 로봇 프레임에 대해 앞보기 점 

 



 이 정해지면 선회 반경 ^ρ 는, 간단한 기하학에 의해, 다음과 같이 계산된다.

2

2

( ) 2

a a

ρ l

= ξ (9)

여기서 l

을 앞보기 거리라고 한다. 그리고, 주행 선 속도 

가 주어 진 상황에서 선회 반경 ρ가 결정되면, 회전 속도를   

 로 결 정할 수 있다.

3.3 GVD 기반 앞보기 점 설정

본 논문의 목표는 선회를 통한 GVD 추종이다. 이는 앞보기 점 을 GVD 상에 놓이게 함으로써 달성할 수 있다. 현재 위치에서 로 봇은 지역적 센서 정보만 가질 뿐 GVD의 전역적 형태는 알 수 없다고 가정하자. 비록 이전의 탐사에 의해 맵을 구성하였다 하더 라도, 맵은 경로 계획에 필요한 노드(교차점과 경계점) 정보와 각 노드를 잇는 모서리의 비용(거리) 정도만 기억할 뿐, 전체 경로를 기억하는 것은 아닐 것이므로, 합당한 가정이라 하겠다.

만약에 로봇이 GVD 상에 있다면, 목표점은 GVD 상의 전방에 놓일 것이다. 우리는 GVD의 로컬 정보만 알 뿐 전체 형태를 알 수 없으므로, 전방이란 말은 GVD에 접하는 접선 벡터로써 그 위

치가 결정된다. 반면에 GVD에서 충분히 멀리 떨어져 있다면, 우 선 GVD에 접근하는 것에만 신경을 쏟아야 할 것이다. 대부분의 경우, 접선을 따른 추종과 기울기를 통한 접근이 동시에 일어날 것 이다(Fig. 5).

a v D

ξ = α − β ∇ D

∇ (10)

이고,

( )

2 2

min , ( ) / 2 sgn(( ) )

a

a a

v D D

l D x v v l β

α ξ β

⊥

⊥

= ∇

=

= − ⋅ − (11)

현재 위치가 GVD에서 충분히 멀 경우 (D(x) ≥ 2l

), GVD 로 접근하는 데에만 집중하며 (α = 0, β = l

), 반면에 GVD 상에 있 다면 (D(x) = 0), 오직 GVD를 따라 가는 데 집중한다 (α = l

, β

= 0).

한편, 로봇이 교차점에 충분히 가까워 졌을 때는, 새로이 나타날 다른 모서리를 따라 가기 위한 선회를 미리 시작해야 한다. 교차점 에 다다랐을 때 비로소 시작하면, 경로 상 불필요한 초과량 (overshoot) 이 발생할 것이다. 현재 로봇이 F

상에 있다고 하자.

그러면 d

(x) = d

(x)가 가장 가까운 두 거리일 것이다. F

를 추종하 던 중, 교차점 부근에 다다랐다는 말은, 세번째 가까운 거리 d

(x) 가 이 둘의 값과 그리 큰 차이를 보이지 않는다는 말이다. 즉,

( ) ( ) ( )

i j k a

d x = d x < d x − l (12)

이 경우, 곧 F

와 F

가 나타날 것이며, 로봇은 이 둘 중 적절한

경로를 따라 이동해야 한다. 맵이 이미 완성되 있고 적절한 경로계

획 알고리즘이 있다면, 어느 길로 가야할지 결정해 줄 것이다. 그렇

지 않다면, 최종 목표점을 고려해서 결정해야 할 것이다. 어느 방법

이든 간에, F

를 따라가야 한다고 결정했다고 하자. 이 경우 장애

(a) (b) Fig. 7 Simulation: effect of look-ahead distance

(a) (b)

Fig. 6 Simulation

물 j를 무시해서 얻게 되는 경로에 접근하는 문제로 풀 수가 있다.

4. 시뮬레이션

시뮬레이션에 사용된 작업 환경은 Fig. 1과 같다. 네 개의 장애물 로 둘러 쌓인, 가로 12 m, 세로 10 m의 직사각형 환경 안에 세 개의 직사각형 장애물이 더 놓여 있는 상황이다. 로봇의 폭은 w

= 0.4 m 이고, 로봇의 선속도는 

= 5 m/s 를 유지한다. 앞보기 거 리는 l

= 1 m, 샘플링 타임은 Δt = 0.1 sec 이다. Fig. 6에서 보는 바와 같이 따라가야 할 GVD가 (a) 비교적 완만할 때와 (b) 급할 때 모두 잘 추적함을 볼 수 있다.

Fig. 7(a) 는 Fig. 6(b)와 동일한 상황이다. 시작 방향이 서로 반 대인 경우이다. 비록 이 경우에도 목표점에 도달하긴 했으나, 엉뚱 한 경로를 따라 빙빙 돌아 도달했다. 이 시뮬레이션에서는, 기존에 맵이 없다고 가정하고, 목표점의 위치에 따라 실시간 경로계획을 수행했기 때문에 충분히 발생할 수 있는 상황이다. 이러한 현상은 C 지점에서 GVD에서 벗어난 오프셋 양이 잘못된 판단을 하게끔 이끌었기 때문이다. Fig. 7(b)는 앞보기 거리 l

= 0.5 m 로 설정해 서 다시 시뮬레이션 한 결과이다. 앞보기 거리를 줄임으로써 더 세 밀하게 GVD를 추종하는 것을 볼 수 있다. 그렇다고 이를 무한정 줄일 수는 없다. 선속도 

를 유지한채 앞보기 거리 l

를 줄이는 것은 선회 시 더 큰 원심력을 받게 되는 것을 감안해야 한다. 그러 나, 이 두 매개변수 

와 l

를 실제 상황에 맞게 조절함으로써, 진행 속도와 추종 성능 간의 타협을 시도할 수 있다.

5. 결 론

본 연구에서는 논홀로노믹 구속조건을 갖는 모바일 로봇이 일반 화된 보로노이 다이어그램을 추종하는 알고리즘을 제시하였다. 기 존의 GVD에 대한 연구는 로봇의 구동이 어떻게 이루어지는지에 별 관심을 두지 않고, 임의의 방향으로 자유자재로 움직일 수 있는

이상적인 로봇을 가정하였으나, 본 연구에서는 실제 로봇에 적용할 때 나타날 수 있는 여러 문제 중에 하나인 논홀로노믹 성질을 어떻 게 다룰지를 제안하였다. 센서 데이터로부터 GVD의 위치를 예측 하고, 이에 기반해서 앞보기 점을 지정함으로써 GVD를 효율적이 고 효과적으로 추종할 수 있음을 보였다.

References

[1] Sowat, P. F., 1979, Representing Spatial Experience and Solving Spatial Problems in a Simulated Robot Environment, A Thesis for a Doctorate, University of British Columbia, England.

[2] Ó’Dúnlaing, C., Yap, C. K., 1985, A “Retraction” Method for Planning the Motion of a Disc, J. Algorithms, 6:1 104-111.

[3] Choset, H., Burdic, k. J., 1995, Sensor Based Planning. I. The Generalized Voronoi Graph, Int. Robotics and Automation, 2 1649-1655.

[4] Choset, H., Burdic, k. J., 1995, Sensor-based Planning, Part II:

Incremental Construction of the Generalized Voronoi Graph, Int.

Robotics and Automation, 2 1643-1643.

[5] Choset, H., Burdick, J., 2000, Sensor-based Exploration: the Hierarchical Generalized Voronoi Graph, Int. J. Robotics Res., 19:2 96- 125.

[6] Nagatani, K., Choset, H., 1999, Toward Robust Sensor-based Exploration by Constructing Reduced Generalized Voronoi Graph, Int.

Intelligent robots and systems, 3 1687-1692.

[7] Nagatani, K., Iwai, Y., Tanaka, Y., 2003, Sensor Based Navigation for Car-like Mobile Robots using Generalized Voronoi Graph, Advanced Robotics, 17:5 385-401.

[8] Kim, D., Yu, B., Lee, J., Han, C., 2009, Analysis of a Geometric Path Tracking Method For a Nonholonomic Mobile Robots Based On, Int.

ICCAS-SICE, 2926-2931.

[9] Kim, S., Seon, J., Kee, C., 2011, Development of Map Building

Algorithm for Mobile Robot by Using RFID, Korean Society of

Manufacturing Technology Engineers, 20:2133-138.