The field of path planning for mobile robots has been widely explored and researched. However, large portion of the research has dealt with only offline path planning, the method robot plans its path in advance before its execution. This offline method has the weak point of long execution time and lack of real-time property.
Thus, online path planning will be the object of observation here. Strictly speaking, online path planning doesn’t plan and execute at the same time. But it do plan and execute alternately in a short time, so it is almost real-time. Using online path planning, robot can avoid unknown static obstacles which suddenly appear on robot’s path because it can replan the path at the moment it faces obstacles.
Various algorithms for online path planning have been considered in this research area. D* Lite is one of those efficient algorithms and is deeply dealt with in this thesis. Especially, its concept of edge cost, heuristic function, and data structure for managing priority queue are considered in a different perspective.
이동 로봇을 위한 경로 계획은 예전부터 다양하게 연구되어 오고 있는 분야이다. 그러나 연구의 많은 부분은 오프라인 경로 계획, 즉 로봇이 동작을 수행하기 전에 미리 경로를 계획해놓는 방법에 대한 것이었다. 이 방법은 수행 시간이 오래 걸리고 실시간성이 떨어진다는 단점이 있다.
그래서 여기에서는 온라인 경로 계획에 대해 살펴본다. 좀 더 정확히 말하자면 온라인 경로 계획에서의 실시간성이란 동시에 수행과 계획이 이루어지는 것이 아니라, 아주 짧은 시간에 수행과 계획이 이루어진다고 할 수 있다. 이러한 온라인 경로 계획 방법을 이용하여 로봇은 알려지지 않은 장애물을 회피할 수 있다. 장애물이 출현한 순간 로봇은 경로를 빠르게 다시 계획할 수 있기 때문이다.
온라인 경로 계획을 위한 알고리즘은 다양하지만, 그 중에서도 D* Lite 알고리즘이 이 논문에서 중점적으로 다루어졌다. 특히, D* Lite 알고리즘의 edge cost, heuristic function, priority queue 관리를 위한 data structure 개념이 다른 각도에서 재조명되었다.
또한 살펴본 온라인 경로 계획 알고리즘을, 센서와 모터, 주변 환경 모델링을 통해 실제 로봇의 물리적인 동작을 고려하여 시뮬레이션을 진행하였으며, 이를 실제 실험으로 수행할 경우 필요한 하드웨어와 소프트웨어 설계에 대해서도 살펴보았다.
