한국지능시스템학회논문지 2011, Vol. 21, No. 1, pp. 36-41 DOI : 10.5391/JKIIS.2011.21.1.36 Performance Evaluation for Multi-Level Configuration Space for the Development of an Efficient Mobile Robot Path Planner 박정수 소병철 정진우 + Jung-Soo Park, Byung-Chul So and Jin-Woo Jung 동국대학교컴퓨터공학과 요 모바일로봇의경로계획을위해형태공간 (Configuration space) 과형태장애물 (Configuration obstacle) 이라는개념이많이활용되고있다. 이개념은이동로봇을공간상에서하나의점으로간주할수있도록주변장애물을확장시킨다는것으로, 이를통해장애물과의충돌로부터자유로운 (Collision free) 이동경로를쉽게찾아낼수있게된다. 또한, 이러한형태공간및형태장애물을쉽게생성하는가장보편적인방법중하나는이동로봇의형태를원형으로근사화하는것이다. 이는그방법이간단하기때문에이동로봇의구체적인형태및이동메커니즘을고려하여형태공간을생성하는방법보다형태장애물생성시간을크게단축시킬수있게해준다. 하지만이동로봇을원형으로근사화하여형태장애물을생성할경우비교적가까이에있는실제장애물들이하나의형태장애물로병합될수있다는문제점이있다. 이로인하여형태공간내에서이동경로를생성할경우최적의이동경로를찾는다는보장을할수가없게된다. 따라서형태공간내에서최적에가까운이동경로를효율적으로찾도록하기위해부분적으로보다정확한형태공간을생성하면서도전체생성시간을단축시킬수있는다단계형태공간생성방법을제안하였다. 제안된방법은로봇을원형으로근사화시킨뒤시작지점과목표지점을잇는이상적인경로를생성하고이경로상에존재하는형태장애물이로봇의원형근사화로인해주변의다른형태장애물과병합되었다면해당형태장애물에대해서만보다정확한형태장애물을재생성한다는방법이다. 또한, 본논문에서는기존의정확한형태공간생성방법과새롭게제안한다단계근사화형태공간생성방법을비교하기위해다양한이동로봇의형태와회전각도에대해형태공간을생성하는데소요되는생성시간을비교 분석해보았다. 키워드 : 형태공간, 형태장애물, 모바일로봇, 성능검증 약 Abs tract Configuration s pace( C-s pace) including configuration obs tacle( C-obs tacle) is one of the most important concepts in mobile robot path planning. Us ing C-s pace and C-obs tacles, the robot with different shapes and moving mechanisms can be considered as a point in the C-space. And, as a result, the collision-free path for the robot can be eas ily achieved. To make C-space including C-obstacle, many res earchers used circular approximation method for the efficient caluculation time. This method can help us to save our time by approx imating the s hape of a robot as the minimum sized circle which can cover all the area of robot. But, by using the circle larger than the robot, more space are cons idered as the part of robot and, as a result, s ome obs tacles which are very near each other may be cons idered as a combined one obs tacle. To solve this problem, multi-level configuration s pace is propos ed by this paper. This multi-level method also use the circular approximation method as the initial step. But, after finding the initial path, it will check how many obs tacles are combined. And then, for each combined obstacle, more accurate C-space generation will be continued. To check the efficiency of the propos ed algorithm, time for c-s pace generation are compared with the w ell-know n accurate C-space generation method using various types of robot shape. Key Words : configuration space, configuration obstalce, mobile robot, performance evaluation 접수일자 : 2010 년 10 월 21 일완료일자 : 2010 년 12 월 24 일 * 본논문은본학회 2010 년도추계학술대회에서선정된우수논문입니다. * 본연구는동국대학교와산학협력중심대학육성사업기술개발과제 ( 세부과제명 : RoboticsLab 시뮬레이터의기능개선을위한이동로봇의효율적경로계획알고리즘개발 ) 의지원으로수행되었음. + 교신저자 1. 서론 최근로봇관련기술들의연구성과가확산되면서로봇기술에대한활용영역이산업분야뿐만아니라의료용, 교육용, 가정용, 심해용, 우주용등의다양한분야로확대되고있다.[1]. 이렇게로봇기술의활용범위가넓어짐에따라이동로봇의안전한주행 (Navigation) 이날로강조되고있다 [5]. 특히, 최근에는동적으로움직이는장애물이존재하거나목표지점이변화하는동적인환경에서의이동로봇의 36
성공적인주행을보장하는제어알고리즘에관한연구들이활발히진행되고있다 [5][6][7][8][9]. 이러한이동로봇의안전한주행을목적으로하는기본적인연구중의하나는장애물과의충돌로부터자유로우면서 (Collision free) 시작지점과목표지점까지의연결된경로를생성해주는경로계획 (Path planning) 이다 [5 ]. 또한, 이동로봇의경로계획을수행하기위한중요한개념들중하나가형태공간 (Configuration space, C-space) 과형태장애물 (Configuration obstacle, C-obstacle) 이다. 참고로형태공간상에서가상으로그크기가확장된장애물들을형태장애물 (Configuration obstacle, C-obstacle) 이라고부른다. 실제로이동로봇들은각각다른형태를가질수있으므로결과적으로시작지점에서목표지점으로향하는이동로봇의경로가그이동로봇의형태및이동메커니즘에따라서달라질수있다는문제를야기한다. 이때, 로봇의원형근사화를고려한형태장애물과형태공간은이러한문제점에대한하나의해결책이될수있다. 구체적으로형태장애물을포함한형태공간은이동로봇의형태및이동메커니즘에기반하여공간상에존재하는장애물들을확장해생성되었으므로, 이동로봇을그형태에상관없이하나의점으로인지할수있게해준다. 이때형태공간의차원의수는이동로봇이가지는자유도 (Degree of freedom) 의개수와같다. 이러한형태공간과형태장애물이라는개념은이동로봇의경로계획에있어서장애물과의충돌에서자유로운 (Collision free) 이동경로를효율적으로찾아낼수있는기반이된다. 하지만정확한형태장애물을포함한형태공간의생성에는공간상에존재하는모든장애물에대하여로봇의형태및이동메커니즘을고려할필요가있으므로그계산시간이오래걸리게되는부담이있다. 이를해결할수있는한방법으로는이동로봇의형태를이동로봇전체를포함할수있는최소크기의원으로근사화시키는방법이있다. 이는형태공간생성시이동로봇의형태및이동메커니즘을고려할필요가없어지게되므로보다쉽고빠르게형태공간을생성할수있게된다. 하지만이동로봇을원형으로근사화한형태는기존의이동로봇형태보다더많은공간을차지하게된다. 즉, 이동로봇의원형근사화를통해생성된형태공간내부에있는형태장애물은이동로봇의형태및이동메커니즘을고려하여생성한형태공간내의형태장애물보다그크기가증가하게된다는것이다. 이러한형태장애물크기의증가는근접해있는장애물들이하나의형태장애물로병합되는문제를발생시킬수있으며, 이는이동로봇의경로계획에있어서시작지점과목표지점을연결하는최적의이동경로를찾는데방해가될수있다. 따라서본논문에서는이러한문제점을해결하기위하여이동로봇의경로계획을위한형태공간생성시다단계로형태공간을생성하는방법을제안하였다 [4]. 2. 다단계형태공간생성방법 형태공간을다단계로생성하는방법은크게두가지단계로나눌수있다. 첫번째단계에서는공간상에존재하는이동로봇의형태를원형으로근사화하는방법을사용하여이동로봇이이동경로를계획할수있도록해준다. 이는 기존의형태공간생성시이동로봇의형태및모든자유도를고려하는방법보다형태공간을생성하는데필요로하는계산량을줄이기위함이다. 두번째단계에서는이동로봇의실제형태및모든자유도를고려한형태장애물의생성을형태공간상에서부분적으로적용시킴으로써첫번째단계에서생성한형태공간에서보다최적에가까운이동경로를찾을수있도록한다. 구체적인알고리즘은다음과같다. [ 다단계형태공간생성방법알고리즘 ] 1 현재 환경 상에 존재하는 장애물의 개수 (N1) 를 파악한 다. 2 이동로봇의형태를원형으로가정하고 1 단계형태장애 물 (CO1) 및 1 단계형태공간 (CS1) 을생성한다. 3 2 에서 생성된 1 단계 형태 장애물 (CO1) 의 개수 (N2) 를 파악한다. 또한, 2 개이상의장애물들이서로병합된경 우이를별도로표시해둔다. 4 N1=N2 인경우 A. CO1 및 CS1 을이용하여경로계획을수행한다. 5 N1 N2인경우 A. 시작점 (SP) 과목표점 (GP) 을잇는이상적경로인직 선 (I P) 을긋는다. B. 두개이상의장애물이병합된형태장애물 (co1 CO1) 에대하여 ⅰ. 만약 co1 과 IP 가서로교차한다면 1) co1 을 구성하는 장애물들에 한정하여 2 단계 형태공간 (CS2) 을생성한다. 이는이동로봇 의 실제 형태와 이동 메커니즘을 고려한 형 태장애물 (CO2) 을가지게된다. 2) CS1 을 1) 에서 생성된 CO2 를 이용하여 새로 운 CS1' 을 생성한다. 이를 수학식으로 표현 하면 CS1'=(CS1-{ co1} ) CO2) 이 되며, 이 는 2 에서 생성된 1 단계 형태 공간에서 co1 의집합을제외한다음 1) 에서생성된 CO2 를 합하여 새로운 CS1' 형태 공간을 생성하는 것을의미한다. 3) 새롭게 생성된 CS1' 형태 공간에 대해서 이 동경로계획을수행한다. ⅱ. co1 과 IP 가서로교차하지않는다면 1) CO1 및 CS1 을이용하여경로계획을수행한 다. 그림 1 은이동로봇의원형근사화를통하여형태공간을생성한뒤이동경로계획을수행한모습이다. 이동로봇의원형근사화를통하여형태장애물을생성하면서실제장애물 1 번과 2 번, 실제장애물 4 번과 5 번이하나의형태장애물로생성된것을확인할수있을것이다. 이형태공간을이용하여이동경로계획을수행하였을경우그림 1 과같이형태장애물을우회하게되는이동경로가생성되게될것이다. 하지만이이동경로를최적에가까운이동경로라고볼수는없다. 만약시작지점과목표지점을잇는이상적인경로상에놓인장애물들사이에이동로봇이통과할수있는공간이존재하면서도불구하고가상으로그크기가확장되어하나의형태장애물만이존재한다면해당형태장애물을보다정확하게찾아줌으로써이동로봇이통과할수있는공간을만들어줄수있게된다. 또한, 이를통해보다최적에가까 37
한국지능시스템학회논문지 2011, Vol. 21, No. 1 운이동경로를찾아낼수있게된다. 이러한내용이그림 2 와그림 3 에나와있다. 그림 1. 원형근사화를통한이동경로계획 Fig 1. Path planning for virtual circular approximation of mobile robot's shape 이동로봇의원형근사화를통하여형태공간을생성하고생성된형태장애물중에서두개이상의구분된장애물로구성된형태장애물이있다면형태공간을부분적으로재구성해야될필요성이있는지판단하여본다. 그림 2 에서는이를판단하는방법이나와있다. 시작지점과목표지점을잇는이상적인최단경로인직선을긋고이직선상에두개이상의실제장애물로구성된형태장애물이있는지판단하여본다. 만약직선상에조건을만족하는형태장애물이존재할경우해당형태장애물에대해서이동로봇의형태및이동메커니즘을고려하여새롭게형태장애물및형태공간을재생성하게된다. 이내용이그림 3 에나와있다. 그림 3 은특정부분에한정해서형태공간을보다상세하게재생성한모습이다. 실제장애물 4 번과 5 번으로생성된형태장애물이시작지점과목표지점을잇는이상적경로인직선내에위치하고있다. 따라서해당형태장애물에대해서이동로봇의실제형태및이동메커니즘을고려하여형태장애물을재생성하게되면하나의형태장애물이두개의형태장애물로나뉘게되고이공간을이용하여최적에가까운이동경로를찾을수있게되는것이다. 그림 4 에서는형태공간을부분적으로재생성하여새롭게구성된형태공간을이용하여이동경로계획을한모습이다. 그림 2 에서볼수있듯이이동로봇을원형으로근사화하여생성한형태공간에서이동경로계획을하였을때보다최적에가까운이동경로를찾을수있는것을확인할수있다. 그림 2. 시작지점과목표지점을잇는직선 Fig 2. Straight line connecting between the starting point and goal point 그림 4. 형태공간에따른이동경로계획의차이 Fig 4. Different types of path planning of C-space 본논문에서는새롭게제안한다단계형태공간생성방법이모든장애물을대상으로형태공간을정확히생성해내는기존의방법보다얼마나효율적인지를시뮬레이션을통해검증하고자한다. 구체적으로이동로봇의다양한형태별로형태공간을생성되는데소요되는시간들을비교, 분석하는방법으로성능검증을수행하였다. 그림 3. 이동로봇의형태및이동메커니즘을고려한형태장애물재생성 Fig 3. Recreate the detailed parital C-space with real shape and movement mechanism of the mobile robot 3. 성능검증을위한실험환경 새롭게제안한다단계형태공간생성방법에대한성능을검증하기위하여 Intel i5 750 CPU[2.66GHz], DDR3 4G 38
메모리, 그리고 MS-Windows 7 이탑재된 PC 상에서 Microsoft Visual 2008 C++ 와 MFC, OpenGL 을이용하여시뮬레이션을구현하고시행하였다. 시뮬레이션을위한이동로봇의형태로는그림 4 와같이총 5 개의형태를사용하였다. 테스트진행환경은그림 5 와같이 160(cm) 120(cm) 크기의평면을구성하였다. 이평면에실제장애물을 20(cm) 20(cm) 1 개, 40(cm) 20(cm) 1 개, 20(cm) 10(cm) 2 개위치시킨다. 그리고그림 6 에나와있는 5 개의이동로봇형태를이용하여일정한각도 (10, 1, 0.5, 0.1 ) 별로이동로봇을회전시키면서이동로봇의형태및회전각도 (heading angle) 을고려하여모든장애물들을대상으로형태공간을생성하였을경우의소요시간과원형근사화이후부분적으로형태공간을생성하였을경우의소요시간을중앙처리장치 (CPU) 의틱카운트 (Tick count) 를이용하여측정하였다. 단, 중앙처리장치의틱카운트를사용할경우 PC 의리소스등여러가지환경적인요인에따라서같은결과가나오지않기때문에보다정확한실험결과를얻기위하여모든실험은각각 5 회씩수행한뒤이들의평균값을이용하였다. 4. 실험결과 아래의표 1, 표 2, 표 3, 표 4 는 5 가지의이동로봇의형태를이용하여원형근사화이후부분적으로정확한형태공간을생성 ( 제안한방법 ) 하는데걸린시간과모든장애물을대상으로형태공간을생성 ( 기존의방법 ) 하는데걸린시간을이동로봇을회전시키는단위각도별로정리한것이다. 각표의아래부분에삽인된시간단축은제안된방법이기존의방법에비해얼마만큼의효율을보이는지를나타내고있다. 표 1. 단위회전각도 10 Table 1. Rotation Degree 1 0 ( 단위 : 초 ) 제안 1.445 2.246 2.683 1.248 0.92 기존 2.018 3.198 3.915 1.248 1.482 시간단축 28.4% 29.8% 31.5% 5.9% 37.9% 표 2. 단위회전각도 1 Table 2. Rotation Degree 1 ( 단위 : 초 ) 제안 14.758 22.293 26.894 12.324 9.219 기존 20.187 32.74 39.265 12.324 14.726 시간단축 26.9% 31.9% 31.5% 7.6% 37.4% 그림 5. 테스트환경 Fig 5. Environment of Testing 표 3. 단위회전각도 0. 5 Table 3. Rotation Degree 0.5 ( 단위 : 초 ) 제안 29.656 44.819 54.23 24.773 18.611 기존 40.327 64.85 78.39 24.773 29.468 시간단축 26.5% 30.9% 30.8% 7.2% 36.8% 표 4. 단위회전각도 0. 1 Table 4. Rotation Degree 0.1 ( 단위 : 초 ) 제안 148.185 223.628 269.538 123.724 92.243 기존 202.53 320.473-123.724 147.405 시간단축 26.8% 30.2% - 7.2% 37.4% 그림 6. 이동로봇의형태 Fig 6. Shape of mobile robots 5 개의이동로봇의형태를크게두가지로원형과비원형 ( 사각형, 별, 다각형, 타원 ) 으로나눌수있다. 이같은분류로각각의실험결과를살펴보면이동로봇의형태가원형일경우보다비원형일경우형태공간을생성하는데소요되는시간이많이나타나는것을확인할수있다. 이는이동로봇의형태가원일경우에는이동로봇의형태를원형으로근사화하는방법과마찬가지로이동로봇의회전자유도를고려하지않아도되기때문에형태공간을생성하는데걸리는소요시간이적게나타나는것으로분석된다. 이동로봇의형태가비원형으로이루어져있을경우도선분으로이루어진이동로봇의형태 ( 사각형, 별, 다각형 ) 와 39
한국지능시스템학회논문지 2011, Vol. 21, No. 1 곡선으로이루어진이동로봇의형태 ( 타원 ) 로나눌수있다. 선분으로이루어진이동로봇들은평균 29% 정도의시간단축률을보이는반면선분이아닌형태로이루어진경우 37% 정도의시간단축률을보여주고있다. 이는선분으로이루어진이동로봇의경우해당형태장애물을생성할때계산의간략화를위해이동로봇을구성하는각각의선분들에대하여각각이동로봇이회전하는각도에맞추어각도변환을해줄수있지만, 선분이아닌형태 ( 타원 ) 로이루어진이동로봇의경우이동로봇의형태를가장비슷하게표현할수있는곡선식을이용하거나또는격자지도의경우각픽셀별로각도변환을해주어야하기때문이다. 그결과, 다양한선분을가진다각형의경우타원과같은곡선형태보다도계산시간이많이걸린것을확인할수있었다. 표 4 를살펴보면이동로봇의형태가다각형일때모든장애물을대상으로형태공간을생성할때에대한실험결과가없는것을볼수있다. 이는해당케이스로실험을진행하였을경우메모리풀 (Memory full) 이발생하여실험결과를얻지못하였다. 하지만그결과를전체적인실험결과를토대로예측하여보면 390 초 400 초정도소요될것으로예상된다. 결론적으로실험을통해새롭게제안한다단계형태공간생성방법이기존의방법보다뛰어난수행시간단축효과가있는것을확인하였다. 특히그림 7 은회전각도 10 에서부분적으로형태공간을생성하였을때의시뮬레이션화면이다. 그림을살펴보면위 아래에한줄씩표현되는선이각각도에대한시작지점과목표지점이다. 그림 7 의왼쪽에있는두개의장애물은이동로봇의모양을원형근사화하여형태장애물을생성할경우한개의형태장애물로합쳐지게되고또한시작지점과목표지점을잇는직선상에위치하게된다. 결과적으로이경우보다효과적인이동경로를찾을수있는가능성이존재하기때문에두개의실제장애물로나누어지는것이바람직하며그림 7 은제안된방법에따라 2 개의실제장애물로나뉘어졌음을보이고있다. 즉, 해당형태장애물의경우이동로봇의형태와이동메커니즘에맞게생성된것을확인할수있으며나머지두개의장애물은이동로봇의형태를원형근사화하여생성한형태장애물의모양을띄고있다. 그림 7. 회전각도 10 에서부분적형태공간생성 Fig 7. Applying 10 degree of rotation for partial obstacles in C-space generation 반면그림 8 은회전각도 10 에서모든장애물을대상으로형태공간을생성하였을때의시뮬레이션화면이다. 그림 7 과같이시작지점과목표지점을잇는직선상에는두개의실제장애물들만존재하지만모든장애물에대해이동로봇의형태및이동메커니즘을적용하여정확한형태공간을구성하였다. 그림 8. 회전각도 10 에서모든장애물에대한형태공간생성 Fig 8. Applying 10 degree of rotation for all obstacles in C-space generation 5. 결론 본논문에서는이동로봇의경로계획을위한중요한개념들중의하나인형태공간을효율적으로구성하는방법으로다단계형태공간생성방법을제안하고이에대한성능검증을실시하였다. 성능검증을실시하는방법으로는모든장애물들에대해이동로봇의형태및이동메커니즘을적용하여형태공간을생성하였을경우의생성시간과새롭게제안한이동로봇의원형근사화이후일부장애물에만이동로봇의형태및이동메커니즘을적용하여정확한형태공간을재생성하였을경우의생성시간을비교하였다. 이번실험에서사용한실험공간은 160(cm) 120(cm) 크기의평면에배치시킨실제장애물 4 개중이동로봇의원형근사화를통해두개의실제장애물이하나의형태장애물로병합되도록구성하였다. 이러한환경하에서실험을진행한결과이동로봇의형태가원형이아닐경우약 27% 37% 의생성시간단축효과를확인할수있었다. 하지만이동로봇의형태가원형일경우약 5% 7% 의미미한생성시간단축효율을보였다. 이동로봇의형태가원형일경우가원형이아닐경우보다생성시간단축효율이낮은이유는이동로봇의형태가원형일경우이동로봇의이동메커니즘을고려하지않아도되기때문에그차이가적은것으로확인되었다. 만약이번실험에서사용한환경보다공간의크기및복잡도가높아지고시작지점과목표지점을연결하는이상적인이동경로인직선상에두개이상의실제장애물로구성되어진형태장애물의개수가많아지게된다면이번실험을통해얻은약 27% 37% 의시간단축효율보다보다높은생성시간단축률을보일것이다. 40
참고문헌 [1] 정만태, 신 성장 동인으로 주목 받는 로봇산업의 현황과발전전략, KEIT 산업경제, 2009년 3월. [2 ] T. Lozano-Perez, A Spatial Planning : A Configuration Space Approach, IEEE Transactions on Computers, Vol. C-32, pp.108-120, 1983 [3] T. Loz ano-perez, A Simple Motion Planning Algorithm for General Robot Manipulators, IEEE Transactions on Robotics and Automation, Vol. RA-3, no.3, pp.224-238, 1987 [4 ] Jin-Woo Jung, Byung-Chul So, Multi-level configuration space for the development of an efficient mobile robot path planner in the embedded system, Proc. Of ISET 2010, Daegu, Korea, May 2010 [5] 정광민, 이희재, 심귀보, Potential Feild 를 이용한 자율이동로봇의 경로 계획에 관한 연구, 한국지능 시스템학회논문지, vol. 19, no. 5, pp. 737-742, 2009 [6 ] L. Pimenta and A. R. F onseca, " Robot N avigation Based on Electros tatic Field Computation," IEEE Transaction on Magnetics, vol. 42, no. 4, April 2006. [7] R. Daily and D. M. Bevly, "Harmonic Potential Field Path Planning for High Speed Vehicles," American Control Conference 2008, Seattle, Washington, USA, 2008 [8] Thomas Braunl, Embedded Robotics, Springer -V erlag, Berlin, Heidelberg, 2 0 0 3 [9] T. Hesse and T. Sattel, "Path-Planning with Virtual Beams," Proc. of the 2007 American Controls Conference, pp 3904-3905, July 2007 관심분야 : 모바일로봇 E-mail : hostkit@naver. com 저자소개 박정수 (Jung-Soo Park) 2011 년 : 동국대학교컴퓨터공학과 ( 공학사 ) 2011 년 현재 : 동국대학교컴퓨터공학과석사과정 소병철 (Byung-Chul So) 2010 년 : 동국대학교컴퓨터공학과 ( 공학사 ) 2010 년 현재 : 동국대학교컴퓨터공학과석사과정 관심분야 : 모바일로봇, 인간 - 로봇상호작용 E-mail : sbc10620@naver.com 정진우 (Jin-Woo Jung) 1997 년 : 한국과학기술원 전기 및 전자공 학과 ( 공학사 ) 1999 년 : 한국과학기술원 전기 및 전자 공 학과 ( 공학석사 ) 2001년~2002년 : 일본동경대학교기계정 보공학과대학원방문연 구원 2004 년 : 한국과학기술원 인간친화 복지 로봇시스템 연구센 터박사후연구원 2006 년 ~ 현재 : 동국대학교컴퓨터공학과조교수 관심분야 : 인간 - 로봇상호작용, 다개체협력로봇, 소프트컴퓨팅, 생체측정, 지능로봇 E-mail : jwjung@dongguk.edu 41