디스타알고리즘 (D* Algorithm)
한 줄 정의: 환경 정보가 변화할 때 이전 탐색 결과를 최대한 재사용하여 경로를 빠르게 재계산하는 동적 최단 경로 탐색 알고리즘.
쉽게 풀면
길을 가다가 갑자기 새로운 장애물을 발견했을 때, 처음부터 다시 계산하지 않고 이미 알던 정보를 최대한 활용해 빠르게 새 길을 다시 찾는 방법입니다.
논문에서는 이렇게 쓰입니다
D* 계열 알고리즘은 변경된 에지 비용 주변의 노드만 선택적으로 재계산하는 증분 탐색 기법으로, 정적 A* 대비 재계획 시간을 크게 단축한다.
지도의 일부만 바뀌었을 때 지도 전체를 다시 훑지 않고 바뀐 부분과 관련된 곳만 다시 계산해 계산량을 크게 줄인다는 의미입니다.
주의할 점
구현이 A*보다 복잡하며, 변경이 매우 광범위하게 발생하면 증분 갱신의 이점이 줄어듭니다.