Hybrid A star 경로 계획 알고리즘 설명

알고리즘 설명

• Hybrid A star 은 시작지점에서 목적지점까지 충돌 없이 Kinematic Feasible한 Sub Optimal Path를 생성할 수 있는 알고리즘이다. 
• Hybrid A star 경로 계획 알고리즘은 아래 논문에서 제안된 방법이다. 
  • Dolgov, Dmitri, et al. "Practical search techniques in path planning for autonomous driving." Ann Arbor 1001.48105 (2008): 18-80.
• 기존 A star 경로 계획 알고리즘 대비 2가지가 개선되었다.
  • Kinematic Feasible 경로 생성 가능
  • H cost 사용하여 Search 횟수 절감 (Non-holonomic without obstacle Cost, Obstacle with holonomic Cost)

알고리즘 특징

1. Path Node Propagation (Tree search)
   • Kinematic Bicycle Model을 사용해 Parent Node로부터 Child Node를 Propagation 한다.
   • Propagation 시 Kinematic Bicycle Model의 Steer 개수, Steer Resolution, Move Distance_m 는 파라미터로 사용
   • Child Node는 Occupancy Grid Map, State Grid Map 에서 충돌 판단 및 점수 비교를 수행한다.
2. State Grid Map
   
   • Path Node를 Propagation 하면 비슷한 상태 값의 노드가 굉장히 많이 생성되는데, 이를 모두 저장하여 관리하는 것은 비효율적이다. (연산 시간, 메모리 측면 모두)
   • 따라서 Path Node를 State Grid Map에 사영시켜, 비슷한 State의 Path Node는 Cost가 가장 낮은 1개만 저장하게 된다. 이렇게 해도 Sub Optimal의 Path를 생성할 수 있다.
3. Occupancy Grid Map
   
   • 공간을 나타내는 2차원 배열로 장애물, 주행 가능 영역 등이 위치한 Occupancy Grid Map 상 영역을 1로 Occupied 시킨다.
   • Occypancy Grid Map Marking 알고리즘으로는 Bresenham's algorithm을 자주 사용한다.
4. 기타 요소
   • Open List, State Grid Map Cost 계산 시 min priority queue (min heap), queue 의 자료 구조가 사용된다.
   • 동적 메모리를 사용하면 구현이 용이하되, 메모리 누수가 발생하지 않도록 잘 관리 해야 한다.
   • 본 알고리즘에서는 Path Node의 State 값, State Grid Map Index, Occupancy Grid Map Index 총 3개의 좌표계가 사용된다. 각 좌표계 간 변환 함수를 잘 설계 해야 한다. State Grid Map과 Occupancy Grid Map의 원점을 통일하고, 원점을 Path Node의 State 좌표계로 표현하면 사용이 편리하다.
5. Analytic Expansion
   • 본 알고리즘은 Propagation된 Child Node가 목적지점에 도달한 경우 종료된다. (Max Iteration이 초과 하거나 Open List의 요소가 0이거나, 최대 배열 값을 초과해도 종료될 수 있다.)
   • 하지만 Child Node가 목적지점에 도달했다는 조건을 설정하기가 애매하고, 목적지점 주변에 애매하게 위치하여 불필요한 Propagation이 추가로 수행될 수 있다.
   • 이를 방지하기 위해 Child Node에서 충돌 없이 목적지점까지의 경로 계획이 가능한지 Reed Shepp curve (or Dubins Path)를 생성하여 확인한다.

알고리즘 구현

• TD
• 본 알고리즘을 구현하면 A star를 기반으로 한 Grid Search는 모두 구현 가능하다고 볼 수 있다.