Microsoft Word - 08_이영삼

Journal of Institute of Control, Robotics and Systems (2016) 22(3):217-225 http://dx.doi.org/10.5302/j.icros.2016.15.0201 ISSN:1976-5622 eissn:2233-4335 RRT 와 SPP 경로평활화를이용한자동주행로봇의경로계획및장애물회피알고리즘 Path Planning and Obstacle Avoidance Algorithm of an Autonomous Traveling Robot Using the RRT and the SPP Path Smoothing 박영상, 이영삼 * (Yeong-Sang Park 1 and Young-Sam Lee 1,* ) 1 Department of Electrical Engineering, Inha University Abstract: In this paper, we propose an improved path planning method and obstacle avoidance algorithm for two-wheel mobile robots, which can be effectively applied in an environment where obstacles can be represented by circles. Firstly, we briefly introduce the rapidly exploring random tree (RRT) and single polar polynomial (SPP) algorithm. Secondly, we present additional two methods for applying our proposed method. Thirdly, we propose a global path planning, smoothing and obstacle avoidance method that combines the RRT and SPP algorithms. Finally, we present a simulation using our proposed method and check the feasibility. This shows that proposed method is better than existing methods in terms of the optimality of the trajectory and the satisfaction of the kinematic constraints. Keywords: path planning, autonomous traveling robot, RRT, SPP curve, path smoothing I. 서론최근드론및무인자동차와같은자동로봇 (autonomous robot) 이중요한이슈로떠오르고있다. 자동로봇이란높은자율성을가진로봇을뜻하는말로써, 예측할수없는상황즉동적환경에서도자가적인결정을내리고행동하는로봇을말한다. 이러한자동로봇에서는경로계획 (path planning) 이매우중요한부분을차지하는데, 이는경로혹은움직임에따라로봇의자율성이얼마나높은지나타낼수있는일종의척도가되기때문이다. 경로계획알고리즘에서가장중점을두는부분은최단거리를가지는경로를생성하는것이다. 기존의경로계획알고리즘에는그래프 (graph) 또는트리 (tree) 자료구조를이용하여최단거리문제를해결하는 Dijkstra [1], A* [2,3], 그리고 D* [4,5] 알고리즘등이있다. 이알고리즘들은전체지도를모두정점 (node) 으로세분화한후, 해당알고리즘에따라최단거리를찾아나간다. 그래프또는트리를이용한경로계획알고리즘들은실제최적의결과를구하게되어있다는장점이있으나, 복잡한환경에서는전체정점을모두탐색할수도있게되어계산량이많아진다는비효율성을가지고있다. 이와같은문제점을해결하기위해몇가지의무작위알고리즘 (randomized algorithm) 이연구되었다. 무작위알고리즘은무작위샘플링 (random sampling) 을기반으로하는알고리즘으 * Corresponding Author Manuscript received December 1, 2015 / revised January 11, 2016 / accepted January 19, 2016 박영상, 이영삼 : 인하대학교전기공학과 (pys0728k@hotmail.co.kr/lys@inha.ac.kr) 본연구는미래창조과학부및정보통신기술진흥센터의 ICT 융합고급인력과정지원사업의연구결과로수행되었으며 (IITP-2015- H8601-15-1003) 또한한국전력공사의재원으로기초전력연구원의 2015 년선정기초연구개발과제의지원을받아수행된것임 ( 과제번호 : R15XA03-12). 로, 전체지도에서무작위로정점을추출하여각각의알고리즘을적용하는방법이다. 이방법은그래프또는트리자료구조를이용한방법에비해최적의경로를찾아낼수는없으나, 계산량이적고, 빠른시간안에도착점까지의경로를생성해낼수있다는장점이있다. 이방법을이용하는알고리즘은대표적으로 randomized potential field, probabilistic roadmap [6], RRT [7,8] 알고리즘등이있다. 그중에서도 RRT는 Voronoi region에서착안한빠른공간탐색방법을이용하여최근각광받고있는이론이다. 자동로봇에서는경로의평활화 (smoothing) 도경로계획못지않은중요성을가지고있다. RRT를이용한경로계획을실행하면흔들림 (jittering) 을가진경로가생성되는데, 이를최적화시키기위한가장단순한평활화기법으로는경로에서장애물이없는두지점을직선으로연결하는방법이있다. 하지만이렇게평활화된경로는추종하는로봇의실제동역학을만족시키지못한다. 이를해결하는몇가지의평활화기법으로는 SPP 곡선 [9], clothoid 곡선 [10], B-spline 곡선 [11] 등을이용하는방법들이있다. 상기한경로생성과경로평활화는기존연구에서는주로분리하여연구가진행되었지만, 실제주행로봇에적용할때는분리해서생각할수없는관계이다. 이를개선하기위해최단거리경로와로봇의동역학을모두만족시키기위한몇가지기존연구결과도있었으나, 즉각적인후처리를필요로하여예측불가능한계산부하가발생하거나 [12], 최단거리경로를충분히만족시키지않는결과를도출하였다 [13]. 이논문에서는 RRT를통하여전역적경로계획을선행하고, SPP를통하여계획된경로의평활화 (smoothing) 및이륜로봇의기구학적제약조건이고려된경로생성방법을제안한다. Section 2에서는 RRT 및 SPP에대한이론을소개하고, Section 3에서는제안된방법을사용하기위해서추가적으로 Copyright ICROS 2016

218 Yeong-Sang 박영 Park 상 and, 이 Young-Sam 영삼 Lee 사용해야하는두가지방법을제안한다. Section 4에서는 RRT와 SPP를통합한경로생성및장애물회피알고리즘을제안한다. Section 5에서는시뮬레이션결과를살펴보고마지막으로 Section 6에서는결론을내린다. II. 관련이론 1. Rapidly Exploring Random Tree (RRT) RRT 는트리 (tree) 자료구조를이용한경로계획의일종으로출발점을기준으로지도의무작위정점을샘플링하여도착점까지의정점및간선 (edge) 을구하는방법이다 [7,8]. 알고리즘 1. RRT 생성알고리즘. Algorithm 1. The RRT generation algorithm. _,, 1. init ; 2 1 3 _ ; 4 _, ; 5 _, ; 6 _,, ; 7. add_node ; 8. add_edge,, ; 9 Return 알고리즘 1은 RRT를생성하는알고리즘을의사코드 (pseudocode) 로나타낸것이다. 먼저지도에서무작위정점 를추출한다. 기존트리 에있는정점중에서 와가장가까운정점 을찾고, 에서 에도달하기위한입력 를입력셋 (set) 에서찾는다., 를이용하여 만큼시간이지났을때의실제상태 를구한다. 이 는 의자식정점 (children node) 으로저장되고간선, 정점의정보가트리 에저장된다. RRT는여러장점들이있으나, 가장중요한장점은탐색하지않은위치를더욱효과적이고빠르게탐색해나간다는것이다. 이는 RRT가 Voronoi bias를가지고있다는성질이기인하는장점이다. 알고리즘 1의의사코드에따라서알고리즘이진행될때, 트리 내부의한정점이 로선택될확률은그정점의 Voronoi region의크기와비례한다. Voronoi region의크기가크다는것은빈공간이크다는것을의미하므로결국빈공간을탐색할확률이커지게되고, 이것이바로 Voronoi bias를의미한다. 2. Single Polar Polynomial (SPP) 곡선 SPP 곡선은경로의평활화기법으로사용되는이론으로써곡률이연속적인경로를생성하여로봇의기구학적제약조건을만족하는경로를생성하는기법이다 [9]. 경로계획을통해생성된경로들은일반적으로직선만으로이루어져있거나, 직선과원호를결합한형태로이루어져있는경우가많다. 그러나이러한경로를로봇이완벽하게추종할수있는경우는많지않다. 실제로봇에는기구학적제약조건이있으나, 경로계획을통해생성된경로가이를고려하지않았기때문이다. 제약조건을만족하는곡선을얻기위해서, 곡선상의거리 에대해독립변수들이균등하게변할수있는극좌표계에서 그림 1. 주행로봇의회전각 θ 에따른 SPP 곡선의반경변화. Fig. 1. The radius change of the SPP curves for different rotation angle θ. SPP를이용하여곡선을표현할수있다. 그림 1은임의의 SPP 곡선 b를나타낸그림이다. SPP 곡선이반지름이 이고 를원의중심으로하는원호를대체한다고할때, 로봇의회전각 θ 에따라변화하는반지름을나타내는변수 r( θ ) 와 θ 에대한 1차도함수 r ( θ ), 2차도함수 r( θ ) 는 (1) 과같고, (2) 와같은경계조건을만족해야한다. 2 3 4 5 r( θ) = a + aθ + aθ + aθ + aθ + aθ + 0 1 2 3 4 5 dr 2 3 4 r ( θ) = = a + 2aθ + 3aθ + 4aθ + 5aθ + 1 2 3 4 5 dθ 2 dr 2 3 r( θ) = = 2a + 6aθ + 12aθ + 20aθ + 2 2 3 4 5 d θ r( θ) = R, r ( θ) = 0, k = 0, at θ = 0 r( θ) = R, r ( θ) = 0, k = 0, at θ = μ 여기서 ϕ 는헤딩각 (heading angle) 이고, s 는원주거리일때, 곡률 k 는다음과같다. ϕ ( θ) + 2 ( θ) ( θ) ( θ) k( θ ) = = 2 2 d r r r r 3 ds 2 2 2 ( r ( θ) + r ( θ) ) (3) 에 (1), (2) 를대입하여계수 a ~ a 0 5 를구하면다음과같다. R R R a = R, a = 0, a =, a =, a =, a = 0 (4) 0 1 2 3 4 2 5 2 µ 2µ 그러므로다음과같은식을얻을수있고, 이는 SPP 곡선의궤적을나타낸다. 2 3 4 θ θ θ r( θ ) = R 1+ + + 2 2 μ 2μ 상기 SPP 곡선을사용하더라도출발점및도착점의헤딩각 ϕ 에따라서 1-segment, 즉하나의곡선혹은직선만으로는경로를생성하지못할수도있다. 이때는 2-segments를사용하여경로를생성해야하는데, 이를판별하는기준이출발점과도착점이대칭적인지혹은비대칭적인지확인하는것이다. 대칭성을판별하기위해 β 를다음과같이정의한다. (1) (2) (3) (5)

Path Planning and Obstacle RRT Avoidance 와 SPP 경로 Algorithm 평활화를 of an 이용한 Autonomous 자동주행 Traveling 로봇의경로 Robot 계획 Using 및장애물 the RRT 회피 and 알고리즘 the SPP Path Smoothing 219 그림 2. 비대칭적인두점을연결하는경로 (a), (b) 와대칭적인두점을연결하는경로 (c) ~ (e). Fig. 2. Path (a) and (b) which are connecting asymmetrical two points and (c) ~ (e) which are connecting symmetrical two points. 알고리즘 2. 도착점편향 RRT를이용한경로생성알고리즘. Algorithms 2. The path generation algorithm using the goal biased RRT. _ _,,,, 1. init ; 2 1 3 _ _ ; 4 5 ; 6 7 _ ; 8 _, ; 9 _, ; 10 _,, ; 11. dd_node ; 12. dd_edge,, ; 13 14. path_to_root, ; 15 ; 16 Return 출발점 p x y ϕ 0 0 0 0 y 1 f y 0 β = tan x f x 0 (6) = (,, ) 와도착점 p = ( x, y, ϕ ) 가다 음을만족하면두점이대칭적이라고한다. f f f f ϕ β = ( ϕ β) (7) 0 그림 2와같이대칭적인두점을연결하는경로는 1- segment로생성하고비대칭적인두점을연결하는경로는 2- segments를사용하여생성하면된다. 1-segment를이용한경로는직선또는 SPP 곡선 1개로이루어져있으며, 2-segments를이용한경로는직선 + SPP 곡선, SPP 곡선 + 직선또는 SPP 곡선 2개로이루어져있다. 그림 2의경로에서곡선부는 SPP 곡선이아닌원호로표현되어있으나실제 SPP 곡선을나타내며, 각경로가생성될조건은논문 [10] 을참조하였다. III. 추가적인방법제안된방법을사용하기위하여기존사용되었던 RRT 및경로평활화방법들을일부수정하여적용하여야한다. 이를위하여다음의 2가지수정된방법들을제시한다. 1. 도착점편향 RRT RRT는 Voronoi bias에따라서빈공간을빠르게탐색할수있고, 장애물이있는공간이나막혀있는공간에서도샘플링의무작위성으로인하여회피및탈출할수있다. 그러나기본적으로비용함수에의한 bias가생성되는그래프자료구조를이용한경로생성알고리즘에비해경로의수렴가능성이낮다는단점이있다. 이단점을상쇄시키기위하여일정확률로도착점에편향된 bias를인가한다. 이에관한연구들도진행되고있으나 [14], 제안된방법에적용하기위해서는추가적인알고리즘이필요하다. 도착점편향에대한알고리즘을다음과같이제시한다. f 알고리즘 2는도착점으로편향된 RRT 경로생성알고리즘이다. 기존 RRT와의차이점은 Line 3~7과 13~15이다. 먼저 Line 3~7은확률 에따라 가 로선택되도록하는일종의 bias를적용한부분이다. 확률 는빠른수렴성과장애물회피간의 trade off 관계에따라결정할수있다. 일반적인 RRT는 Voronoi bias에따라탐색하지않은지역에대한방향성이부여되나, 목표점에대한방향성이부여되지않은상태이기때문에수렴이굉장히늦다. 이러한문제를해결하기 위하여일정확률 만큼의도착점에대한방향성을부여한다. 이방향성이너무작다면목표점에대한방향성이매우낮을수있다. 반면에이방향성이너무크다면지역최소점 (Local minima) 에빠졌을때도착점의방향으로만무작위샘플링을진행하므로탈출하기위한시간이오래걸린다. 장 애물이적은상황에서는확률 를크게잡아서빠르게수렴하도록선정할수있고, 장애물이많은상황에서는확률 를작게잡아서지역최소점에서충분히빠져나오도록선정할수있다. Line 13~15는제안된방법에적용하기위해추가된알고리즘이다. 샘플 에서로봇의상태 가 에도달했다고볼수있는반경 ε 근처에들어가면 RRT 생성을마치고, 도착점에서부터부모노드를거슬러올라가서출발점까지도달하는실제경로를추출하여경로에해당하는정점셋 를얻는다. 반경 ε 은 RRT의특성상도착점근처에도달하였더라도정확히도착점이아니라면수렴한것으로보지않고계속알고리즘을진행하기때문에, 수렴하였다고볼수있는범위내에서계산량을줄이기위하여적용되었다. 그림 3과 4는 RRT에수렴반경 ε 을적용하지않았을때와적용하였을때의시뮬레이션결과이다. 시뮬레이션은출발점 (0,0) 과도착점 (400,400) 을입력으로하여진행하였고수렴반경 ε 은 50으로설정하였다. 실선으로이루어진원은 RRT가한스텝당무작위로샘플링한위치를나타내며파선으로이루어진원은수렴반경을나타낸다. 무작위샘플링을

220 박영상, 이영삼 450 400 350 300 250 200 150 100 50 0 0 100 200 300 400 그림 3. 수렴반경 ε 을적용하지않았을때의 RRT 결과. Fig. 3. The result of the RRT obtained when the convergence region ε is not used. 400 350 300 250 200 150 100 50 0 0 50 100 150 200 250 300 350 400 그림 4. 수렴반경 ε 을적용하였을때의 RRT 결과 (ε = 50). Fig. 4. The result of the RRT obtained when the convergence region ε (ε = 50) is used. 사용하는알고리즘인 RRT의특성으로인하여수렴반경이커질수록트리의가지 (branch), 즉샘플링횟수가적다는것을알수있다. 그러나정확한도착점 (400,400) 에는미치지못하므로두상관관계를적절히고려하여수렴반경 ε 을선정하여야한다. 수렴반경을정하는부분인 Line 13은일반적인유클리드거리 (Euclidean distance) 를기준으로작성하였으 나, 확률적정보가존재할경우마할라노비스거리 (Mahalanobis distance) [15] 를사용하여더적절한수렴반경을지정할수도있다. 2. SPP 곡선생성을위한전처리평활화도착점으로편향된 RRT로생성된출발점부터도착점까지의정점셋 N RRT 는후처리를거치지않으면흔들림을가지고있는최적이아닌경로를나타내게된다. 이를제거하기위해먼저가장기본적인평활화기법을이용하여 N SMOOTHED 를생성한후, SPP 곡선을위한새로운정점셋 N SPP 를만든다. 알고리즘 3. SPP 곡선을생성하기위한전처리평활화. Algorithm 3. The pre-smoothing for the generation of the SPP curve. _ _,, 1.init, ; 2 length ; 3 1 4,, ; 5,, ; 6,, ; 7 tan ; 8 1 9 cos ; 10 sin ; 11 s _,, ; 12 s TRUE 13. _, ; 14 Return 알고리즘 3은가장간단한평활화기법을나타낸표이다. 에서먼저인접한정점의거리를원하는만큼등분한다. 이후출발점에서부터도착점까지간선의길이를등분한만큼증가시켜나가면서장애물충돌검사를실행한다. 장애물과충돌한다면두인접한정점중에서나중샘플의정점을 에저장한다. 이평활화알고리즘을이용하면장애물과충돌하지않는선에서그사이의정점들이간략화되어더최적인경로가생성된다. IV. 방법 Section 4에서는상기 RRT와 SPP 곡선을융합하여 RRT로계획된경로를평활화하고이륜로봇의기구학적제약조건을만족하면서도장애물을회피하는경로생성방법을제시한다. 1. N SPP 의선정및 N SPP 를경유하는 SPP 곡선생성 N SMOOTHED 를 SPP 곡선생성에이용하려면먼저새로운정점셋 N SPP 를만들어야한다. 그림 5는임의의출발점과도착점에서정점의위치에따른 SPP 곡선경로가어떻게생성되는지도시한그림이다. 타원은출발점과도착점을나타내고마름모는 SPP 곡선의중심, 사각형은 N SMOOTHED, 원은 N SPP 를나타낸다. 점선은기존의 N SMOOTHED 를그대로사용할경우의경로이고, 일점쇄선은 N SPP 를사용할경우의경로이다. 기존의 N SMOOTHED 를그대로사용할경우에는생성된경로가최적경로의외부로이탈하여전체경로의길이가길어지는것을볼수있고, 반대로 를사용할경우에는최적경로의내부로이탈하여전체경로의길이가짧아지는것을볼수있다. 그림 6은 N SPP 가기존 N SMOOTHED 에서얼마나떨어져있느냐에따라서 SPP 곡선경로가어떻게생성되는지나타낸그림이다. 주행로봇을구동시키는환경과개발자가중요하게생각하는상황에따라 N SPP 를생성하는기준이달라진다. N SPP 가 N SMOOTHED 에가까울수록경로에서덜이탈하는모습을볼수있다. 이는장애물이많은환경에서는 N SPP 를 N SMOOTHED 에가깝게정해서기존경로를최대한추종하게

RRT 와 SPP 경로평활화를이용한자동주행로봇의경로계획및장애물회피알고리즘 221 하면장애물과의충돌을방지할수있다는뜻이다. 반대로장애물이많지않은환경에서는 N SPP 를 N SMOOTHED 에서멀도록지정하여경로를단축하도록할수도있다. 제안된방법에서초기 N SPP 는그림 5와같이 N SMOOTHED 에있는출발정점과도착정점은그대로사용하면서, 연속한두정점의중간지점을새로운정점으로생성하여사용하였다. 이와같은방법은전체경로의길이를가장짧게하고, 곡률이작은곡선을생성하여로봇의기구학적제약조건을최대한만족하는초기경로를생성한다. 그림 5. N SMOOTHED 와 N SPP 를사용한경로의차이. Fig. 5. The difference of the path between N SMOOTHED and N SPP. 그림 6. N SPP 의위치에따라생성된경로들의차이. Fig. 6. The difference of the path according to the location of the N SPP. 2. 장애물충돌판단 Section 4-1의방법을사용하면기구학적제약조건을만족하는경로가생성되지만 SPP 곡선을사용한경로는장애물회피기능을가지고있지않기때문에장애물회피알고리즘을사용하여야한다. 장애물회피알고리즘을사용하기위해서는먼저장애물이현재경로를통과하는로봇과충돌했는지를판단할수있는기준이필요하다. 제안된방법은먼저장애물의반경이 SPP 곡선의반경보다더큰지확인하고, 장애물이경로와충돌할가능성이있는상태인지확인한후, 충돌할가능성이있는상태라면실제충돌하는경로인지확인하는세가지판단을내린다. 이세가지판단을내릴기준을위하여세가지가정을세운다. 첫번째, 장애물의모양을원으로가정하고실제장애물보다더크게설정한다. 장애물은모양에따라크게벽, 물체의 2가지로나눌수있다. 그중물체는일반적으로유한한구간의폐쇄된도형의형태를가지고있는데, 이로인해장애물을해당장애물이내접하는원으로가정하는데큰문제가없다. 따라서제안된방법은모든장애물을고려하는것이아닌물체만으로이루어진장애물들을고려한다. 이렇게가정된원형장애물은장애물의원점으로부터표면까지일정한거리를가지고있고, 곡률이일정하다는성질로인하여 SPP 곡선을사용하여장애물을회피할때, 특성을고려하기쉬워진다. 또, 추후사용할알고리즘의특성상장애물과경로의접점이생기더라도실제로봇이충돌하지않도록장애물을더크게설정한다. 두번째, SPP 곡선을원으로가정한다. SPP 곡선은 (2) 에서알수있듯이, 중심 p c 에서부터시작정점과종료정점까지의거리가반경 R 으로일정하다. 이는곧반경이 R 인원호로가정할수있다는뜻이며, Section 4-3 의장애물회피알고리즘을이용하기위하여반경이 인원으로가정하였다. 마지막으로, SPP 곡선 1개에대해서만장애물충돌판단을하였다. 제안된방법은 Section 2-2에의해모든경로가직선과 SPP 곡선으로이루어져있으며, 직선부는 RRT에서생성한경로를그대로추종하면장애물에충돌하지않는다. 결국 SPP 곡선 1개에대한장애물회피문제로간략화할수있다. 상기세가지의가정을통하여 SPP 곡선과장애물의관계는두원의관계로성립하게된다. 장애물충돌을판단하는조건은다음과같다. 먼저, 장애물의반경과 SPP 곡선의반경을비교한다. 그림 7은장애물의반경이 SPP 곡선의반경보다클때의한가지상태를도시한그림이다. RRT로생성된직선경로 a 와 b는장애물을회피하도록생성되기때문에, 장애물과직선 a, b 사이에각각 2개의교점이생기는상태는일어나지않는다. 그러므로그림 7의상태가가장최악의상황으로생각할수있으나, 반경이 R 보다큰직선 a, b의내접원중에서 SPP 곡선과교차하는내접원은없으므로장애물의반경이 SPP 곡선의반경보다크다면충돌할가능성은없다는것을알수있다. 두번째로, 장애물과 SPP 곡선의관계로부터충돌가능성을판별한다. 그림 8은장애물과초기 SPP 곡선의중심거리에따른관계를나타낸그림이다. 이점쇄선은실제 SPP 곡선을나타내고, 반지름이 R 인실선으로이루어진원은초기

222 Yeong-Sang 박영 Park 상 and, 이 Young-Sam 영삼 Lee (a) External and externally tangent. (b) Secant. 그림 9. 장애물이초기 SPP 곡선과충돌하는영역. Fig. 9. The region of the collision between an obstacle and the initial SPP curve. 그림 7. 장애물의반경이 SPP 곡선의반경보다큰경우. Fig. 7. The case where the radius of an obstacle is bigger than the radius of the SPP curve. (a) External. (b) Externally tangent. 마지막으로, 상기한충돌가능성판단에서충돌할가능성이있는외부, 외접그리고만남상태일경우, 실제로장애물과 SPP 곡선이충돌하는지확인할수있는조건을만들어야한다. 그림 9에서실제 SPP 곡선과충돌하는장애물의위치는각각의영역 에해당한다. 그러므로외부, 외접일때는그림 9(a) 와같이직선,, 로이루어진영역 에원의중심이있다면충돌하는것으로처리하였고, 만남일때는그림 9(b) 와같이직선,,, 로이루어진영역 에원의중심이있다면충돌하는것으로처리하였다. 3. 장애물회피알고리즘상기 Section 4-2를통해장애물이경로와충돌하는상태가되면그림 10과같이반경이 인 SPP 곡선을새로만들어야한다. 이때가장최적의 는기존 RRT로생성된경로와내접이면서, 장애물과내접의관계를가지고있어야한다. 초기 SPP 곡선을나타내는원의중심을, 라고하고, 반경을 이라고할때, 새로운 SPP 곡선을나타내는원의중심, 과 는다음과같은수식을연립하여얻을수있다. R = l = x x + y y R' r = d = ( x' x ) + ( y' y ) R' = ( ps + ( lcos σ ) uf) p' 2 2 ' sin σ ( ( ' s) ( ' s) )sin 2 2 obs obs σ (8) (c) Secant. (d) Internally tangent. p obs 는장애물의중심, p s 는 N SMOOTHED 의한정점, 그리고 u 0 와 u f 는각각시작정점의단위방향벡터와종료정점의단위방향벡터를나타낸다. (8) 을연립하여생성된, 와 를사용하여새로운시작정점과종료정점을구할수있고, 이를통해 SPP 곡선을생성하면장애물에내접하는최적의 SPP 곡선을생성할수있다. (e) Internal. 그림 8. 장애물과초기 SPP 곡선의관계. Fig. 8. The relation between an obstacle and the initial SPP curve. SPP 곡선을나타내며, 일점쇄선으로이루어진원은장애물을나타낸다. 그림 8을통하여두원의관계에서로봇과장애물이충돌할수있는관계는두원이만남일때로고려할수있다. 가정에의하면외부, 외접일때는충돌하지않으나, 실제 SPP 곡선은가정한원보다반지름이더크기때문에충돌할가능성이생기므로외부, 외접일때도충돌하는것으로판단해야한다. 그림 10. 장애물에충돌하지않는최적의 SPP 곡선. Fig. 10. The optimal SPP curve that does not collide with an obstacle.

Path Planning and Obstacle RRT Avoidance 와 SPP 경로 Algorithm 평활화를 of an 이용한 Autonomous 자동주행 Traveling 로봇의경로 Robot 계획 Using 및장애물 the RRT 회피 and 알고리즘 the SPP Path Smoothing 223 V. 시뮬레이션첫번째시뮬레이션은출발점 (0,0) 과도착점 (400,400) 을입력으로하여진행하였다. 장애물은임의의네점 (180,180), (310,230), (150,350), (300,350) 을중심으로하고반경 50인원을사용하였다. 일확률변수 는 0.5로지정하였다. 프로그램을구동한 PC는클럭속도가 3.40GHz인 Intel Core i7-4770 프로세서를기반으로하고 8GB 메모리를가지고있다. 그림 11은시뮬레이션결과이다. 원은장애물을나타내며, 실선은제안된방법으로생성된경로를나타내고, 점선은기존 RRT에간단한직선평활화만을적용한경로를나타낸다. 직선부에서는기존 RRT와큰차이가없지만, 곡선부에서제안된방법은부드러운곡선을그리며제약조건을만족시키는것을볼수있다. 두번째시뮬레이션은장애물회피알고리즘의성능을판별하기위해서, (180,180) 에있는장애물의위치를 (188,203) 으로변경하여장애물과경로가충돌하도록조정하였다. RRT 는기본적으로절대장애물에부딪히지않는장애물회피기능을가지고있기때문에직선구간에서의장애물회피는고 려할필요가없다. 그러므로곡선구간에서의장애물회피, 즉 SPP 곡선이생성되는구간에서만장애물회피기능이적용되어있으며, 이구간에서장애물회피가되는것을증명한다면전구간에서의장애물회피가보장된다. 추가적으로첫번째시뮬레이션에서구해진 N SMOOTHED 를이용하여기존경로와같은경로를생성하도록함으로써 RRT가경로를변경하지않게하였다. 그림 12는제안된장애물회피알고리즘을사용하지않는경로생성그래프이고, 그림 13과 14는제안된장애물회피알고리즘을사용하는경로생성그래프이다. 점선으로이루어진원은새로운 SPP 곡선을가정한원을나타내는데, 장애물에내접한최적의 SPP 곡선이생성되었다는것을볼수있다. 세번째시뮬레이션은제안된경로계획의성능을판별하기위해서목표 bias 확률 에따른평균실행시간을측정하였다. 400 350 300 250 200 그림 11. 제안된방법과기존 RRT 경로의차이. Fig. 11. The difference between the proposed method and the original RRT path. 150 100 50 0 0 50 100 150 200 250 300 350 400 그림 13. 제안된장애물회피알고리즘을사용하는경로생성. Fig. 13. The path generation using the proposed obstacle avoidance algorithm. 260 250 240 230 220 210 200 그림 12. 제안된장애물회피알고리즘을사용하지않는경로생성. Fig. 12. The path generation not using the proposed obstacle avoidance algorithm. 190 130 140 150 160 170 180 190 200 그림 14. 제안된장애물회피알고리즘을사용하는경로생성 ( 확대 ). Fig. 14. The path generation using the proposed obstacle avoidance algorithm (zoom-in).

224 박영상, 이영삼 446 522UOQQVJKPI 6QVCN 그림 15. 제안된방법을 500회반복했을때의실행시간그래프 ( p = 0.20). Fig. 15. The execution time graph when the proposed method is iterated 500 times ( p = 0.20). 표 1. 목표 bias 확률 p 에따른총실행시간. Table 1. The total execution time for various goal bias probability p. p RRT (s) SPP smoothing (s) Total (s) 0.10 0.6303 0.0294 0.6597 0.20 0.5451 0.0312 0.5763 0.25 0.5088 0.0346 0.5435 0.30 0.5299 0.0338 0.5637 0.35 0.5478 0.0343 0.5821 0.40 0.5272 0.0352 0.5623 0.45 0.5833 0.0356 0.6189 0.50 0.6463 0.0349 0.6812 그림 15는확률 0.20일때, 제안된방법을 500회반복한실행시간을나타낸그래프이다. 평균실행시간은약 0.5763초로, RRT가무작위샘플링이기때문에편차가심했다. 기존 RRT는약 0.5451초의실행시간을가지고있었으며, SPP 평활화및장애물회피알고리즘이전체실행시간의약 5.5% 로, 무시할수있는수준인것으로나타났다. 표 1은확률 에따른총실행시간을나타낸표이다. 모두 500회반복한평균값이며, RRT와 SPP 평활화를나누어서나타내었다. RRT의특성때문에확률 와총실행시간의관계가선형적이지않다는것을알수있다. 실제제안된방법을사용할환경을먼저시뮬레이션해보고가장적절한확률 를선정하는것이중요하다. 마지막으로대표적인경로계획알고리즘인 A* 알고리즘과제안된방법의성능차이를알아보았다. A* 알고리즘은개발자가선정한휴리스틱방법에따라서비용함수가최소가되는방향으로경로를만드는알고리즘으로써, 비용함수 f ( n) 은다음과같다. f ( n) = g( n) + h( n) (9) gn ( ) 은격자한칸을이동할때의이동거리이고, 은목적지까지의거리이다. 대표적으로 A* 알고리즘에사용하는휴리스틱방법은맨해튼방법, 직선방법등이있으며, 이는 hn ( ) 에영향을미친다. 그림 16. A* 알고리즘을사용한경로계획 ( 맨해튼거리 ). Fig. 16. The path planning using the A* algorithm (Manhattan distance). 그림 17. A* 알고리즘을사용한경로계획 ( 직선거리 ). Fig. 17. The path planning using the A* algorithm (Straight distance). A* 알고리즘의시뮬레이션을위해 Alex Andriën의 report [16] 에수록된프로그램을사용하였으며, 프로그램을구동한 PC는상기제안된방법의시뮬레이션에서사용한 PC와같다. 그래프또는트리를이용한알고리즘은시뮬레이션을할때마다다른결과가출력되는무작위알고리즘에비해항상같은경로를출력하고알고리즘수행시간이크게달라지지않으므로 1회의시뮬레이션만수행하였다. 그림 16은맨해튼거리를사용한 A* 알고리즘을사용한경로계획이고, 그림 17은직선거리를사용한 A* 알고리즘을사용한경로계획이다. A* manhattan은총 2.971초의실행시간을사용하였고, A* straight는총 397.784초의실행시간을사용하였다. 제안된방법에비해매우큰실행시간을보여주었으며, 기구학적제약조건을만족하지않는경로가생성되어실제실험에적용하기힘들것이라는것을알수있다.

RRT 와 SPP 경로평활화를이용한자동주행로봇의경로계획및장애물회피알고리즘 225 VI. 결론일반적으로사용되는경로계획들은계산량이많거나, 직선만으로이루어진한계때문에계획된경로를그대로로봇에적용하지않는다. 이논문에서는다른경로계획들에비해계산량및계산속도측면에서현저한향상을보여주고있는 RRT를이용하여경로계획을한뒤, SPP 곡선을이용한평활화를통해로봇의제약조건을만족하는경로가생성될수있는방법을제안하였다. 제안된방법을이용하여시뮬레이션한결과단순히기존 RRT만사용한결과에비하여좋은성능을가지면서도실행시간이다른경로계획들에비해적었다. 기존제시된방법들에비해초기에전역적으로경로를생성하기때문에추가적인계산부하가발생하지않고, 직선경로를최대한이용함으로써최단거리경로를만족하는장점을가진다는것을확인하였다. 제안된방법을통해서경로계획만이아닌실제로봇에적용할경로를생성할경우에도로봇의기구학적제약조건을고려하여최적의결과를얻어낼수있을것으로기대된다. REFERENCES [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, pp. 595-601, 2001. [2] W. Zeng and R. L. Church, Finding shortest paths on real networks: the case for A*, International Journal of Geographical Information Science, vol. 23, no. 3-4, pp. 531-543, Mar.-Apr. 2009. [3] G.-Y. Song and J.-W. Lee, Path planning for autonomous navigation of a driverless ground vehicle based on waypoints, Journal of Institute of Control, Robotics and Systems (in Korean), vol. 20, no. 2, pp. 211-217, 2014. [4] S. Anthony, Optimal and efficient path planning for partiallyknown environments, Proc. of the IEEE International Conference on Robotics and Automation, vol. 4, pp. 3310-3317, May 1994. [5] S. Anthony, The focussed D* algorithm for real-time replanning, Proc. of the International Joint Conference on Artificial Intelligence, pp. 1652-1659, Aug. 1995. [6] J. Barraquand, L. Kavraki, J.-C. Latombe, T.-Y. Li, R. Motwani, and P. Raghavan, A random sampling scheme for path planning, International Journal of Robotics Research, vol. 16, pp. 759-774, 1996. [7] S. M. Lavalle, Rapidly-exploring random trees: A new tool for path planning, 1998. [8] D.-H. Kim, Y.-S. Choi, R.-J. Yan, L.-P. Luo, J. Y. Lee, and C.-S. Han, Efficient path planning of a high DOF multibody robotic system using adaptive RRT, Journal of Institute of Control, Robotics and Systems (in Korean), vol. 21, no. 3, pp. 257-264, 2015. [9] I. Jeong and J. Lim, Trajectory generation for mobile robot, The Conference of The Institute of Electronics and Information Engineers (in Korean), pp. 25-30, Oct. 1992. [10] Henrie, Joshua and Wilde, Doran, Planning continuous curvature paths using constructive polylines, Journal of Aerospace Computing, Information, and Communication, vol. 4, no. 12, pp. 1143-1157, 2007. [11] H.-M. Lee, M.-H. Kim, and M.-C. Lee, A UGV hybrid path generation method by using B-spline Curve s control point selection algorithm, Journal of Institute of Control, Robotics and Systems (in Korean), vol. 20, no. 2, pp. 138-142, 2014. [12] Y. J. Yoon, J. Kim, and D.-J. Kang, The study of the autonomous driving method for tracking way point at the unmanned vehicle, Proc. of 2011 26th Institute of Control, Robotics and Systems (ICROS) Annual Conference (in Korean), Gwangju, pp. 1-5, May 2011. [13] C. Moon and W. Chung, Motion planning scheme on the basis of RRT for a high-speed navigation of a two wheeled mobile robot, Proc. of the Annual Spring & Fall Conference of The Korean Society of Mechanical Engineers (in Korean), pp. 2178-2183, 2013. [14] C. Urmson and R. Simmons, Approaches for heuristiclly biasing RRT growth, Proc. of IEEE International Conference on Intelligent Robots and Systems (IROS), pp. 1178-1183, 2003. [15] P. C. Mahalanobis, On the generalised distance in statistics, Proceedings National Institute of Science, India, vol. 2, no. 1, pp. 49-55, Apr. 1936. [16] A. Andriën, Topology optimization versus A*: a comparison for 2D robot path planning, Eindhoven University of Technology, Netherlands, Report, Dec. 2012. 이영삼 박영상 2015년인하대학교전자공학과졸업. 2015년 ~ 현재인하대학교대학원전기공학과석사과정재학중. 관심분야는경로계획, 플랜트제어, 알고리즘. 제어 로봇 시스템학회논문지, 제 15 권제 4 호참조.