움직이는 Mobile Robot을 활용하는 시스템이라면 어리도 움직일지 탐색하는 경로탐색 Path Planning은 필수적인 기반기술 입니다. 꽤 오래전부터 여러 방법으로 연구가 되었던 분야이고 이제는 일반적인 환경에서는 어느정도 솔루션이 나와있는 분야이기도 합니다. 그럼에도 연구는 계속되고 있는데, 아직 더 잘 풀어낼 여지가 있는 문제들이 남아있기 때문일 것입니다. 이번 포스팅에서는 높은 빈도로 사용되는 Path Planning 방법에 대해 간단히 소개하고, 여전히 남아있는 몇가지 문제점들에 대해 제 생각을 적어보려고 합니다.
내용이 관련 분야에 익숙하신 분들이 보실 포스팅이라 너무 기초적인 내용은 넘기고 전문적으로 더 중요한 내용에 대해 더 신경을 써보도록 하겠습니다.
Table of Contents
Path Planning 경로탐색
최근 Mobile Robot 분야를 보면 거의 대부분 Discrete Search를 위해 Grid Map을 구성한 후 Cell 단위로 탐색해 나가는 Search 방식을 사용하는 듯 한데, 연구 초기에는 그렇지 않았다는 기록(?)이 있습니다. 대표적으로 Visibility Graph나 Voronoi Diagram과 같이 단순하고 통제된 환경에서 Geometry를 이용하는 제한적으로 잘 되는 방법인데, 현실성이 떨어져 실제로 그대로 쓰이는 경우는 거의 없습니다. 그러다 Grid Space에서 탐색을 하다보니 Dijkstra’s Algorithm과 같이 (본질적으로는 그래프에서) Optimality를 보장할 수 있는 방법이 연구되고, 그 뒤로 Optimality도 보장하는데 탐색이 빠른 A*까지 알려지면서 왠만하면 A*로 가는 쪽으로 굳어진 것 같습니다.
하지만, 일반적으로 알려진 일명 Original A* Search는 여전히 현실적이지 않은 가정이 여럿 있습니다. 그 중 몇가지를 적어보면 이렇습니다.
- 로봇은 방향전환을 언제나 할 수 있음 (제자리 회전 혹은 Omni-directional)
- Acceleration은 무시 (한 Cell씩 Uniform velocity로 이동)
- 로봇은 하나의 Cell을 차지함
이 외에도 몇가지 더 있는데, 이번 포스팅에서는 1번에 대해서 적어보려고 합니다.
Non-Holonomic Robot과 Kinematic Constraints
연구실에서 사용하는 Mobile Robot이나 식당 서빙로봇 등 상대적으로 자주 보이는 로봇들은 거의 다 제자리 회전이 가능한 Differential Drive 로봇이거나 Holonomic 로봇, 간단히는 Omni-directional과 같이 아무 방향이나 갈 수 있는, 조금 더 정확히 말하면 Controllable DoF와 Total DoF가 같은 로봇 입니다. 엄밀히 말해 Differential Drive 로봇은 옆으로는 못가니 Holonomic은 아니지만, 제자리회전이 가능하니 주행 자체에 있어서는 실질적으로 많이 다르다고 생각하지는 않습니다.
하지만 자동차와 같이 옆으로도 못가고 제자리 회전도 불가능한 non-holonomic 로봇이라면 가정이 많이 달라집니다. 이를 Car-like 혹은 Ackermann Steering이라고 합니다.
오리지널 A*는 이런 제약은 고려하지 않습니다. 예를 들어 우측 5미터 옆에있는 지점으로 가야한다면 A*는 우측으로 가는 경로를 찾지만 자동차는 옆으로 못가니 멀리 돌아가거나 전진과 후진을 반복하며 방향을 돌려서 가야합니다. 이런 시스템에서는 오리지널 A*는 쓸모가 없는 것이죠.
이런 이유로 오리지널 A* 만으로는 자율주행을 완성할 수 없습니다. 그렇다면 왜 Car-like 로봇을 써야하는지에 대해서도 생각해 볼 수 있는데, 자동차와 같은 형태의 시스템이 가지는 장점들이 여럿 있다는 정도로만 넘어가도록 하겠습니다.
Non-Holonomic Constraints를 고려하는 Path Planner
필요한 기능인 만큼 위와 같은 Kinematic Constraint가 분명한 로봇들을 위해 연구된 내용들도 여럿 있습니다. 그 중에서 제가 가장 의미있는 것으로 보고 있는 두가지를 골라 소개드리고자 합니다.
Dubins Curve (Path)
제자리 회전은 못하지만 Steering은 할 수 있다라고 하면 자연스럽게 원을 그리며 이동할 수 있겠다는 생각을 해볼 수 있습니다. Dubins Curve는 간단히 적어보면 원 반경과 직선을 이용해 경로를 찾는 직관적이면서도 효과적인 path planner 입니다. Analytic한 방법이며 연산이 상당히 빠른것이 특징입니다. 알려진지 오래된 방법이지만, 특정 조건 하에서 Optimal Solution을 찾아주는 좋은점도 있어 아직도 종종 사용됩니다.
참고로, Dubins Path와 비슷하지만 필요하면 후진도 시키는 Reep-and-Sheep Path도 종종 사용됩니다.
Hybrid A*
큼직한 Path Planning 알고리즘 중에는 최근 방식에 속하는데, SLAM의 아버지라고 불리는 Thrun이 DARPA URBAN Challenge에서 사용한 방법이라 더 관심을 많이 받은 것 같습니다. [논문링크]
위 영상은 아직 알지 못하는 환경을 탐색하면서 목표지점에 도달하는 Exploration에 무게가 있는 내용이지만, Hybrid A*를 기반으로 동작하는 시스템 입니다. 시뮬레이션이지만 꽤 타이트한 환경에서도 잘 동작하는 것을 알 수 있습니다.
Hybrid A*는 A* 모델인 f = g + h 사용하지만, 여기서 heuristic이 하나가 아니라 두가지 중 더 큰 값을 그때 그때 선택하는 방식입니다.
- Non-holonomic without Obstacles – 장애물을 없는 샘 치고 Start/Goal pose만으로 계산하는 Heuristic
- Holonomic with Obstacles – Dynamic Programming 방식으로 장애물을 피하는 최단거리로 계산
이 외에도 더 현실에 가깝게 만드는 요소들이 여럿 있는데, 자세한 내용은 논문을 참고하시는 것이 좋겠습니다.
오리지널 A*와 달리 Hybrid A*는 최단경로를 보장하는 optimal algorithm은 아닙니다. 하지만 A*가 해주지 못하는 ‘Drivability’, 즉 실제 로봇이 주행할 수 있는 경로를 찾아줍니다.
마무리
이번 포스팅에서는 Mobile Robot의 경로탐색 모델 중 Non-Holonomic 로봇의 Kinematic Constraints를 고려하지 못하는 A*의 한계점과 이를 해결하기 위해 사용되는 다른 알고리즘 중 두 가지를 소개해 보았습니다. 이 외에도 더 최신 모델들도 있지만, 많은 연구가 위 방법을 이용한 변형이 많은 것 같습니다. 정말 간단하게만 적어보았는데, 개념적으로나마 이해에 도움이 되었길 바랍니다.