길 찾기. Path Finding에 관한 논문

일반적으로 주행 로봇을 공부하고 나면, 그 다음 보통 넘어가는 과제가 어떻게 가야할 길을 인식하는 가의 문제가 나타납니다. 동선이 하나 뿐이고 사람이 그것을 지정한다면, 당연히 가장 손쉽게 접근하는 것은 라인트레이서 방식이나, 혹은 또 요즘 많이들 쓰고 있는 스타게이져와 같은 센서로 해결할 겁니다. 또, 비젼과 관련해서 카메라로 길을 인식도 하고 말이죠. 그런데, 그런 길을 인식하는 문제를 또 넘어서게 되면, 그 다음으로 다가 오는 것은 바로, 로봇이 스스로 경로를 인식하게 하는 겁니다.

이것이 지금 로봇 자신이 가야하는 길이라는 인식과 함께, 또 앞으로 어떤 길을 가야만, 목표지점에 도달할 수 있을지. 어떤 것이 최적의 길인지를 어떻게 판단하는가의 문제와 직면하게 됩니다. 물론 여기서, 완전히 로봇 입장에서는 새로운 길을 가는 것이 아니라, 경로는 로봇, 혹은 로봇에게 지령을 내리는 Control Center에서는 알고 있다는 가정이 있습니다.

이런 경우의 길찾기(Path Finding)에 대한 손쉬운 접근법을 이야기하는 논문이 꽤 오래전인 1993년에 나와 있길래 관심있는 분들은 읽어보시라고 권해드립니다.

Planning Paths of complete Coverage of an Unstructured Environment by a Mobile Robot
A.Zelinsky, R.A.Jarvis, J.C.Byrne and S.Yuta

10.1.1.53.7617.pdf