[AD] D*(Dynamic A*) 알고리즘 설명

Author: Joonhee Lim
Date: 2022/09/03

출처: https://airkims.tistory.com/51

https://velog.io/@al_potato/D-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

---

0. Motivation

다양한 Path Planning 알고리즘에 대해서 공부를 하던 중 A*를 넘어 D*를 알게 되었다. 필자는 지속적으로 변화하는 환경에서의 Path Planner를 찾고 있었는데 A*와 다르게 빠르게 연산하여 갑자기 나타난 장애물을 회피할 수 있는 알고리즘을 발견하여 이에 대해서 정리해보고자 한다.

---

1. Difference between A* and D*

이번에는 바로 알고리즘에 대해 설명을 하였었던 이전과 달리 A*와 비교를 해보면서 왜 이 알고리즘이 쓸만한가에 대해 이야기해보도록 하겠다.

 

A*

- 시작점에서 도착점까지의 경로를 찾는 그래프 탐색 알고리즘

- 기존의 다익스트라 알고리즘과 다른 점은 도착점에 얼마나 근접했는지를 평가하는 휴리스틱 기법이 추가되었다.

- Heuristic은 발견법으로 경험에 기반하여 문제를 해결하거나 학습하여 발견해 내는 방법

- 전산학 등 과학분야에서는 한정된 시간 내에 수행하기 위해 최적의 해 대신 현실적으로 만족할 만한 수준의 해를 구하는방법이다.

 

D* (Dynamic A*)

- D*는 A*보다 동적 환경에 유리하다.

- 부분적으로만 알고 있는 환경에서 주행하는 것이다.

- 즉 주행하면서 기존에 알고 있던 정보와는 다른 장애물이 나타났을 때,

A*라면 일단 멈춰서서 현재 ㅜ이치를 시작점으로 하는 경로를 다시 계산하지만

D*는 기존에 계산해놓은 Back Pointer 정보들을 최대한 이용하여 계산량을 줄이겠다는 것이다.

- 현세대의 대부분의 차량 내비게이션은 이를 활용하여 Planning을 한다고 한다(오우 쉣)

---

2. D* (Dynamic A*)

D*는 Global Path Planning과 Local Path Planning 모두가 가능한 알고리즘인데

1) Global Planning에서는 도착지점에서 거꾸로 시작점을 찾아가는 Backward 서치 방법으로 이루어진다.

2) Local Planning에서는 로봇의 이동 중 새로운 장애물이 발견된 경우 기존 계획된 Global Path를 바탕으로 새로운 장애물 근방의 고유 비용을 수정한 후 이를 바탕으로 주위셀들의 경로비용과 Back Pointer를 수정하게 된다.

 

해당 그림에서 화살표는 Global Path를 나타낸다. 화살표의 방향은 주변 셀 중 가장 경로비용이 작은 셀을 나타낸다.

 

• D* Cost Function

$h(X)$는 상태 X까지 소요되는 총 경로 비용

$h(Y)$는 바로 이전 상태 Y까지 소요되는 총 경로 비용

$c(Y,X)$는 근접 경로 비용으로 Y -> X로의 경로 비용

$A(Y,X)$은 상태 Y -> X로의 경로 비용

$I(X)$은 상태의 고유 비용으로 인접 고정 & 이동 장애물을 고려한 비용 함수이다.