[논문]비용 인지 RRT 경로 계획 알고리즘

서정훈; 오성회

doi:10.7746/jkros.2012.7.2.150

비용 인지 RRT 경로 계획 알고리즘
A Cost-Aware RRT Planning Algorithm 원문보기

로봇학회논문지 = The journal of Korea Robotics Society, v.7 no.2, 2012년, pp.150 - 159

서정훈 (서울대학교 전기.정보공학부) , 오성회 (서울대학교 전기.정보공학부)

Abstract ▼ AI-Helper

In this paper, we propose a cost-aware Rapidly-exploring Random Tree (RRT) path planning algorithm for mobile robots. A mobile robot is presented with a cost map of the field of interest and assigned to move from one location to another. As a robot moves, the robot is penalized by the cost at its current location according to the cost map. The overall cost of the robot is determined by the trajectory of the robot. The goal of the proposed cost-aware RRT algorithm is to find a trajectory with the minimal cost. The cost map of the field can represent environmental parameters, such as temperature, humidity, chemical concentration, wireless signal strength, and stealthiness. For example, if the cost map represents packet drop rates at different locations, the minimum cost path between two locations is the path with the best possible communication, which is desirable when a robot operates under the environment with weak wireless signals. The proposed cost-aware RRT algorithm extends the basic RRT algorithm by considering the cost map when extending a motion segment. We show that the proposed algorithm gives an outstanding performance compared to the basic RRT method. We also demonstrate that the use of rejection sampling can give better results through extensive simulation.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

로봇들이 할당된 임무를 수행하는 공간 Χ를 생각해 보자.
본 논문에서는 비용 인지 경로 계획 알고리즘을 제안하였다. 상태 공간에 대한 비용 지도가 이용 가능하면 제안하는 알고리즘은 최소의 비용을 갖는 로봇의 경로를 찾는다.
온도, 습도, 화학 물질의 밀집도, 신호 강도 그리고 은밀도 등과 같은 환경의 파라미터들을 나타내는 비용 지도를 가지고 있다고 가정한다. 본 논문의 목적은 시작점에서 목적지까지 이동 시간, 경로의 종료 시점의 비용 그리고 이동 경로의 비용을 고려하여 최소의 비용을 갖는 경로로 로봇을 이동시키는 경로 계획 방식을 설계하는 것이다. 본 논문에서 비용지도는 복잡한 물리적 현상을 잘 모델링할 수 있는 가우시안 프로세스(Gaussian processes)를 사용하여 구한다.
하지만 그들은 로봇의 경로에 따른 비용을 고려하지 않았다. 이러한 발전들이 동기가 되어 본 논문에서 우리는 비용 인지 네비게이션 기술을 제안한다. 온도, 습도, 화학 물질의 밀집도, 신호 강도 그리고 은밀도 등과 같은 환경의 파라미터들을 나타내는 비용 지도를 가지고 있다고 가정한다.

가설 설정

x0∈χ를 로봇의 시작점, xgoal ⊂ X을 목적지라고 하고 πu를 시간 t=0부터 t=T까지 주어진 제어 입력 u(t)를 적용했을 때의 상태 방정식의 해라고 가정하자.
본 논문에서는 v(t)가 상수라고 가정했다. 그러나 이러한 연속 시간상의 다이나믹 모델은 다루기 어렵기 때문에 우리는 다음과 같이 이산 시간상의 다이나믹 모델로 변환한다.
비용함수 C로 정의하는 환경 파라미터가 프로세스이고 공간 Χ에서 N개의 데이터를 측정했다고 가정해 보자.
이러한 발전들이 동기가 되어 본 논문에서 우리는 비용 인지 네비게이션 기술을 제안한다. 온도, 습도, 화학 물질의 밀집도, 신호 강도 그리고 은밀도 등과 같은 환경의 파라미터들을 나타내는 비용 지도를 가지고 있다고 가정한다. 본 논문의 목적은 시작점에서 목적지까지 이동 시간, 경로의 종료 시점의 비용 그리고 이동 경로의 비용을 고려하여 최소의 비용을 갖는 경로로 로봇을 이동시키는 경로 계획 방식을 설계하는 것이다.
온도, 습도, 화학 물질의 밀집도, 신호 강도 그리고 은밀도 등과 같은 환경의 파라미터들을 나타내는 비용지도가 공간 Χ에 정의되어 있다고 가정하자.

제안 방법

각 알고리즘의 수행시간이 다르기 때문에 본 논문에서는 종료 시한을 설정했고 각 종료 시한 내에서 알고리즘 수행을 반복했다. 각 알고리즘의 최소 비용 경로는 최종 종료 시한까지 알고리즘을 여러 번 수행하여 그 중 가장 적은 비용을 갖는 경로로 선택했다. 본 논문에서는 200초부터 최종 종료 시한 600초까지 100초 간격으로 5개의 종료 시한을 설정했다.
각각의 비용 지도에 대해서 10번의 독립적인 시행을 하였고 각각의 시행은 600초 동안 진행되었다. 이 시간은 각각의 알고리즘의 최종 종료시한을 의미한다.
본 논문에서 제안하는 경로 계획 알고리즘은 RRT tree를 확장해 나갈 때 비용 지도를 고려하여 최소의 비용을 갖는 모션 세그먼트를 결정하므로 기존 RRT의 변형된 알고리즘이다. 또한 제안하는 알고리즘은 랜덤 포인트를 선택할 때 비용 지도를 기반으로 기각표본추출법(rejection sampling)^[21]을 사용하여 샘플링을 하여 경로의 질을 개선시킨다. 이는 기존 RRT의 장점인 국소최저치에 빠지지 않고 확률적으로 완전하게 목적지에 도달하게 하면서 동시에 경로의 질을 개선하여 최소의 비용으로 로봇을 제어할 수 있다는 것을 의미한다.
본 논문에서 제안하는 경로 계획 알고리즘은 RRT tree를 확장해 나갈 때 비용 지도를 고려하여 최소의 비용을 갖는 모션 세그먼트를 결정하므로 기존 RRT의 변형된 알고리즘이다. 또한 제안하는 알고리즘은 랜덤 포인트를 선택할 때 비용 지도를 기반으로 기각표본추출법(rejection sampling)^[21]을 사용하여 샘플링을 하여 경로의 질을 개선시킨다.
각 알고리즘의 최소 비용 경로는 최종 종료 시한까지 알고리즘을 여러 번 수행하여 그 중 가장 적은 비용을 갖는 경로로 선택했다. 본 논문에서는 200초부터 최종 종료 시한 600초까지 100초 간격으로 5개의 종료 시한을 설정했다. 그림 4는 각 알고리즘에서 10번의 시행에 대한 평균 비용과 함께 표준 편차를 나타내는 에러 바를 보여준다.
기각표본추출법은 직접적으로 추출하기 어려운 다양한 분포로부터의 표본추출을 가능하게 하는 강력한 도구이다. 본 논문에서처럼 비용 지도와 같은 분포를 가지고 있다면 우리는 상태 공간상에서의 분포를 완벽하게 구현할 수가 없기 때문에 기각표본추출법 (rejection sampling)을 사용하여 표본을 추출하기 쉬운 분포로 바꾼다. 즉 다시 말하면, 균등분포로부터 임의의 한 점 x를 선택하고 그 점에서의 비용 C(x)에 따라 샘플링한 점을 선택할지 결정한다.
본 논문은 또한 앞서 모의 실험한 시나리오들을 바탕으로 CA-RRT에 기각표본추출법을 사용하여 모의실험을 수행했다. 그림 5는 기각표본추출법과 균등분포를 사용했을 때의 경로의 평균 비용을 나타낸다.
본 논문에서는 비용 인지 경로 계획 알고리즘을 제안하였다. 상태 공간에 대한 비용 지도가 이용 가능하면 제안하는 알고리즘은 최소의 비용을 갖는 로봇의 경로를 찾는다. RRT 트리를 키워나갈 때 비용지도를 고려하여 모션 세그먼트를 결정하므로 기존 RRT를 확장한 알고리즘이다.
시뮬레이션에서 로봇의 상태 공간 Χ를 x축, y축의 2차원 공간 ( Χ ⊂ R2)으로 설정하였고 상태 공간의 각 축의 경계는 [-45m, 45m]로 설정하였다.
알고리즘은 로봇의 다이나믹에 각각의 제어 입력 u(k)를 적용하여 xnear 부터 xrand까지 총 Nt개의 경로를 찾고 전체 경로 중에서 작은 CT(πu(k))를 갖는 ηa개의 경로를 선택한다.
하지만 만약 우리가 비용함수로써 (4)를 사용하게 되면 목적지에 도달하지는 못하지만 목적지까지 도달하는 경로들 보다 더 적은 비용을 갖는 경로가 존재할 수 있는 문제가 발생할 수 있게 된다. 이러한 상황을 피하기 위해서 우리는 최소 비용의 경로 계획 문제를 다음의 최적화 문제로 수정하였다.
본 논문에서 제안하는 알고리즘(CA-RRT)의 성능을 확인하기 위해 경로의 비용을 고려하여 기존 RRT(B-RRT) 알고리즘과 비교했다. 커널 함수 (2)를 갖는 가우시안 프로세스 (1)을 사용하여 6개의 각각 다른 비용지도를 갖는 시나리오를 만들었다. 본 논문에서는 #, #을 사용했다.

대상 데이터

모의실험을 위해 #부터 #까지 0.01의 간격으로 총 99개의 제어 입력을 사용했다.
본 논문에서 우리는 로봇의 이산 시간 다이나믹 모델을 사용했고 (5)의 목적함수는 #로 근사화 한다.
본 논문에서는 Dubin 차와 같이 두 개의 바퀴를 가진 로봇의 다이나믹 모델을 사용했다. r_x와 r_y를 로봇의 x축, y축의 위치라고 하고 Θ를 로봇의 진행 방향이라고 정의하자.

데이터처리

온도, 습도, 화학 물질의 밀집도, 신호 강도 그리고 은밀도 등과 같은 환경의 파라미터들을 나타내는 비용지도가 공간 Χ에 정의되어 있다고 가정하자. 각각의 모든 장소에서 환경의 파라미터를 구할 수 없기 때문에 측정할 수 없는 장소에서의 환경 파라미터를 추정하기 위해서 비모수적 regression방법인 가우시안 프로세스 regression을 사용한다. 가우시안 프로세스 regression은 비정상 geostatistical 데이터 분석^[15], 비선형 regression^[16], 무선 신호강도 추정^[17], 실내 온도 필드 모델링^[18], 그리고 지형 지도제작^[19]과 같은 복잡한 물리적 현상을 모델링하기 위해 널리 사용되는 비모수적 regression 기술이다.
본 논문에서 제안하는 알고리즘(CA-RRT)의 성능을 확인하기 위해 경로의 비용을 고려하여 기존 RRT(B-RRT) 알고리즘과 비교했다. 커널 함수 (2)를 갖는 가우시안 프로세스 (1)을 사용하여 6개의 각각 다른 비용지도를 갖는 시나리오를 만들었다.

이론/모형

본 논문의 목적은 시작점에서 목적지까지 이동 시간, 경로의 종료 시점의 비용 그리고 이동 경로의 비용을 고려하여 최소의 비용을 갖는 경로로 로봇을 이동시키는 경로 계획 방식을 설계하는 것이다. 본 논문에서 비용지도는 복잡한 물리적 현상을 잘 모델링할 수 있는 가우시안 프로세스(Gaussian processes)를 사용하여 구한다. 가우시안 프로세스는 복잡한 물리적 현상을 추정하고 예측하기 위해 사용되는 비모수적 regression 방법이다^[14].
각 시나리오는 x∈[-45,45]²에 대한 비용지도 C(x)로 구성되어 있고 그림에서 진한 갈색은 장애물을 나타낸다. 본 논문에서 사용된 비용 지도를 모델링하기 위해 가우시안 프로세스 MATLAB toolbox^[11]를 사용했다. 그 예가 그림 2에 나타난다.
. 본 논문에서 우리는 커널 함수로써 가장 많이 사용되는 squared exponential 함수를 사용하며 그 형태는 다음과 같다.

성능/효과

각 알고리즘의 수행시간이 다르기 때문에 본 논문에서는 종료 시한을 설정했고 각 종료 시한 내에서 알고리즘 수행을 반복했다. 각 알고리즘의 최소 비용 경로는 최종 종료 시한까지 알고리즘을 여러 번 수행하여 그 중 가장 적은 비용을 갖는 경로로 선택했다.
기각표본추출법과 균등분포를 사용했을 때의 결과가 각각 빨간색과 녹색으로 나타난다. 모든 경우에 기각표본추출법을 사용했을 때 균등분포를 사용했을 때와 유사하거나 더 적은 비용의 경로를 찾는 것을 확인했다. 모든 시나리오에 대한 평균 비용이 표 3에 나타나 있다.
모든 시나리오에 대해서 제안한 알고리즘이 더 적은 비용의 경로를 찾았다는 것을 확인할 수 있다. 각 알고리즘의 평균 경로 비용은 표 2에 나타나 있다.
RRT 트리를 키워나갈 때 비용지도를 고려하여 모션 세그먼트를 결정하므로 기존 RRT를 확장한 알고리즘이다. 모의실험을 통해서 제안하는 알고리즘과 기존의 RRT를 비교하였고 기존 RRT에 비해 성능이 뛰어나다는 것을 보여 주었다. RRT의 장점인 국소최저치에 빠지지 않고 확률적으로 완전하게 목적지에 도달하게 하면서 동시에 비용 지도에 따라 모션 세그먼트를 결정하여 경로의 질을 개선할 수 있다.
본 논문에서 제안한 알고리즘은 기존 RRT와 전체적인 구조를 공유하기 때문에 국소최저치에 빠지지 않고 목적지에 도달할 수 있다. 반면에, 경로를 따라 움직일 때 발생하는 비용을 고려하지 않은 기존의 RRT와는 다르게 트리를 확장할 때 비용 지도를 고려하여 모션 세그먼트를 결정하므로 경로의 질도 개선시킬 수가 있다.
이는 기존 RRT의 장점인 국소최저치에 빠지지 않고 확률적으로 완전하게 목적지에 도달하게 하면서 동시에 경로의 질을 개선하여 최소의 비용으로 로봇을 제어할 수 있다는 것을 의미한다. 본 논문에서는 모의실험을 통해 제안된 알고리즘의 타당성을 검증하고 기존의 RRT보다 더 좋은 결과를 얻을 수 있다는 것을 보여준다.
각 알고리즘의 평균 경로 비용은 표 2에 나타나 있다. 역시 제안한 알고리즘의 성능이 모든 종료 시한에 대해서 더 좋다는 것을 보여준다.

후속연구

RRT의 장점인 국소최저치에 빠지지 않고 확률적으로 완전하게 목적지에 도달하게 하면서 동시에 비용 지도에 따라 모션 세그먼트를 결정하여 경로의 질을 개선할 수 있다. 우리는 제안한 알고리즘이 경로 계획 문제에 있어 로보틱스 분야의 많은 문제들에 적용될 수 있기를 기대한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	RRT의 특징은?	자주 사용되는 경로 계획 방식인 RRT(Rapidly-Exploring random tree)[4]는 샘플링을 기반으로 하는 알고리즘이다. RRT는 상태 공간 내에서 랜덤으로 포인트를 선택 함으로써 재빨리 상태공간을 탐색하고 랜덤 포인트 방향으로 tree를 확장하여 점차적으로 tree를 키워나간다. RRT는 정적 환경[5-7]에서 그리고 동적 환경[8-10]에서 많은 연구자에 의해 응용되어 지고 있다.
	경로 계획 방식의 목적은 무엇인가?	경로 계획은 로보틱스 분야에서 매우 중요한 문제 이기 때문에 연구자들의 많은 관심을 끌어 왔다[1-3]. 경로 계획 방식의 목적은 로봇의 세부 제한 사항을 만족하면서 동시에 장애물과 충돌하지 않고 시작점에서부터 목적지까지 로봇의 연속적인 경로를 찾는 것이다. 자주 사용되는 경로 계획 방식인 RRT(Rapidly-Exploring random tree)[4]는 샘플링을 기반으로 하는 알고리즘이다.
	가우시안 프로세스의 장점은?	가우시안 프로세스(Gaussian Process, 이하 GP)는 함수의 공간상에서 가우시안 분포를 갖는 확률 변수들을 무한차원으로 일반화한 개념이다. GP는 비모수적 방법을 이용하여 복잡하거나 노이즈가 심한 확률과정을 추정할 수 있다. 만약 z(X)가 GP의 분포를 갖는 함수라면, 여기서 X∈D ⊆ Rn, z(X)는 평균함수μ(X)와 공분산 함수 K(X,X′)로 완전하게 나타낼 수있고 z(X)∼GP(μ(X),K(X,X′)) 로 표시한다.

참고문헌 (21)

D. Kim and D. Kang, "Optimal Path Planning of Mobile Robot for Multiple Moving Obstacles," The Journal of Korea Robotics Society, Vol.2, pp.183-190, 2007.
J. Beak and C. Lee, "An Analysis on the Influential Factors to Set the Path Planning Algorithm for Unmanned Ground Vehicle in Combat Environment," The Journal of Korea Robotics Society, Vol.4, pp.233-242, Aug. 2009.
Y. Chang and Y. Yamamoto, "Path planning of wheeled mobile robot with simultaneous free space locating capability," Intelligent Service Robotics, Vol.2, pp.9-22, 2009.

상세보기
S. M. LaValle and J. J. Kuffner, "Randomized kinodynamic planning," The International Journal of Robotics Research, Vol.20, pp.378-400, May 2001.

상세보기
S. Rodriguez, X. Tang, J. Lien, and N. M. Amato, "An obstacle-based rapidly-exploring random tree," in IEEE International Conference on Robotics and Automation, May 2006.
N. A. Melchior and R. Simmons, "Particle RRT for path planning with uncertainty," in IEEE International Conference on Robotics and Automation, Roma, Apr. 2007.
J. V. der Berg, P. Abbeel, and K. Goldberg, "LPG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information," The International Journal of Robotics Research, Vol.30, pp.895-913, Jun. 2011.

상세보기
C. Fulgenzi, C. Tay, A. Spalanzani, and C. Laugier, "Probabilistic navigation in dynamic environment using rapidly-exploring random trees and gaussian processes," in Intelligent Robots and Systems, Nice, Sep. 2008, pp.1056-1062.
M. Zucker, J. Kuffner, and M. Branicky, "Multipartite rrts for rapid replanning in dynamic environments," in IEEE International Conference on Robotics and Automation, Apr. 2007.
Y. Kuwata, G. A. Fiore, J. Teo, E. Frazzoli, and J. P. How, "Motion planning for urban driving using rrt," in IEEE/RSJ Intl. Conference on Intelligent Robotics and Systems, Sep. 2008.
C. Urmson and R. Simmons, "Approaches for heuristically biasing rrt growth," in IEEE/RSJ Intl. Conference on Intelligent Robotics and Systems, Oct. 2003.
D. Ferguson and A. Stentz, "Cost based planning with rrt in outdoor environment," in IEEE/RSJ Intl. Conference on Intelligent Robotics and Systems, Oct. 2006.
J. Choi, J. Lee, and S. Oh, "Swarm intelligence for achieving the global maximum using spatio-temporal gaussian processes," in American Control Conference, Seattle, WA, Jun. 2008, pp.135-140.
C. E. Rasmussen and C. K. Williams, Eds., Gaussian Processes for Machine Learning. Cambridge: The MIT Press, 2006.
N. Cressie, "Kriging nonstationary data," Journal of the American Statistical Association, Vol.81, pp.625-634, Nov. 1986.

상세보기
M. N. Gibbs and D. J. C. MacKay, "Efficient implementation of gaussian processes," Cambridge, Tech. Rep. 1997.
B. Ferris, D. Fox, and N. Lawrence, "WiFi-SLAM using Gaussian process latent variable models," in Proc. of the 20th International Joint Conference on Artificial Intelligence, 2007.
A. Krause, A. Singh, and C. Guestrin, "Nearoptimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies," Journal of Machine Learning Research, Vol.9, pp.235-284, Feb. 2008.
H. Durrant-Whyte, F. Ramos, E. Nettleton, A. Blair, and S. Vasudevan, "Gaussian process modeling of large scale terrain," in Proc. of the 2009 IEEE International Conference on Robotics and Automation, 2009.
S. Petti and T. Fraichard, "Safe motion planning in dynamic environments," in IEEE-RSJ Int. Conf. on Intelligent Robots and Systems, Aug. 2005.
C. M. Bishop, "Pattern Recognition and Machine Learning," Springer, New York, 2006

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증