mindstorms_with_matlab_logo.png



(본 강좌에 사용된 이미지는 http://www.control.isy.liu.se 에서 발췌한 것임을 미리 밝혀 둡니다.)

반갑습니다. 교주 LGS입니다.

Path를 생성하는 방법에는 정말 많은 방법들이 있습니다.

특히 뽈~뽈~뽈~ 돌아다니면서 장애물 사이를 이리저리 해집고 다녀야하는 Mobile Robot의 경우는 Path 생성이 굉장히 중요한 이슈입니다.

Path 생성방법에는Tangent Bug Algorithm, Potential and Navigation Functions, Visibility Graphs,Probabilistic Roadmap 등등 많은 방법이 있지만

이번 시간에는 직관적으로 이해하기 쉬운 Probabilistic Roadmap(PRM)이라는 녀석을 간략히 소개하겠습니다. ^^

자~ 아래와 같은 지도가 있다고 합시다.


PRM01.png 


진한 갈색 부분은 벽이나 기둥, 장애물처럼 꽉찬 공간 즉 지나갈 수 없는 공간이구요~

흰색 부분은 마음대로 돌아다닐 수 있는 공간입니다.


PRM02.png 


우선 가로축을 x, 세로축을 y로 설정하고...


PRM03.png 

무작위로 점을 여러개 찍습니다.^^


PRM04.png 


찍힌 점들중 이동 가능한 공간에 찍힌 점과 지나갈 수 없는 곳에 찍힌 점을 구분한 후...


PRM05.png 


이동 가능한 공간에 찍힌 점만 골라냅니다.


PRM06.png 


점을 하나 잡아서 자신과 가장 가까운 녀석들과 연결하는 선을 긋습니다.(위의 그림에서는 5개의 선을 그었내요~)


PRM07.png 


그리고 나서 지나갈 수 없는 공간을 지나는 선들은 모두 지웁니다.


PRM08.png 


위의 과정을 이동 가능한 공간에 있는 모든 점에 대해서 수행하면 위와 같은 Map이 그려지구요~

점과 점 사이를 이동하는 각 path에 대해서 이동에 걸리는 시간을 계산하여 저장해 둡니다.


PRM09.png 


Start 포인트와 End Point(Goal)가 주어지면 각 점을 Map상에서 가장 가까운 점과 연결 후...


PRM10.png


마지막으로 Dijkstra's algorithm이나 Dynamic Programming과 같은 최적화 알고리즘으로 어떤 경로를 따라가야하는지 찾으면 되는 거죵~ o(^o^)o

일단 주어진 지도에 대해서 각 점으로 이동하는 Path를 계산해 놓았으므로 새로운 Start Point와 Goal을 주어도 금방 Path를 찾을 수 있습니다.

간단하죠? ㅋㅋ 물론 위의 path가 최적의 path(최단거리의 path)라고는 말할 수 없지만 

계산 능력에 제한이 있는 상황에서 실시간으로 path를 찾아야되는 경우라면 좋은 방법이 될 것입니다.


아래 그림은 MATLAB Robotic Toolbox에서 제공하고 있는 PRM 함수를 이용하여 path를 그린 것입니다.


PRM11.png 


오늘은 여기까지~ =(=^ㅅ^=)

다음 시간에 뵈요~ 뿅~

profile