디스타알고리즘 (D* Algorithm)

한 줄 정의: 환경 정보가 변화할 때 이전 탐색 결과를 최대한 재사용하여 경로를 빠르게 재계산하는 동적 최단 경로 탐색 알고리즘.

쉽게 풀면

길을 가다가 갑자기 새로운 장애물을 발견했을 때, 처음부터 다시 계산하지 않고 이미 알던 정보를 최대한 활용해 빠르게 새 길을 다시 찾는 방법입니다.

왜 중요한가

미지 환경을 주행하다가 새 장애물을 발견했을 때 경로 전체를 다시 계산하지 않고 영향받은 부분만 갱신하므로, 화성 로버와 무인 지상 차량의 실시간 재계획에 채택되었습니다. 동적 환경 경로계획 논문에서 D* Lite가 사실상의 기준 알고리즘입니다. 화성 로버처럼 통신 지연 때문에 지구의 실시간 개입이 불가능한 원격 로봇에서는, 로봇 스스로 새 장애물을 빠르게 재계획할 수 있는 이 알고리즘의 가치가 특히 크다.

어떤 절차인가

초기 계획: 목표 노드에서 거꾸로 각 노드까지의 최단 비용을 계산합니다. 모르는 구역은 통행 가능하다고 가정하는 것(자유공간 가정)이 보통입니다.
이동과 감지: 로봇이 경로를 따라 이동하며 센서로 간선 비용의 변화(새 장애물 등)를 감지합니다.
국소 갱신: 비용이 바뀐 간선 주변에서 값이 불일치하게 된 노드만 우선순위 큐에 올려 비용을 전파합니다. 전체 지도를 처음부터 다시 탐색하지 않습니다.
경로 추종: 현재 위치에서 목표 쪽으로 비용이 가장 작게 이어지는 이웃으로 이동합니다.

원조 D*는 Stentz(1994)가 제안했고, D* Lite(Koenig & Likhachev, 2002)는 Lifelong Planning A*(LPA*)에 기반해 더 단순하게 같은 동작을 구현한 알고리즘입니다. 연구와 실무에서는 D* Lite가 기준으로 자주 쓰입니다.

언제 쓰고 무엇을 얻나

언제 쓰나: 지도가 부분적으로만 알려졌거나 환경이 바뀌는 곳에서 로봇이 반복적으로 경로를 다시 계획해야 할 때 씁니다.
무엇을 얻나: 현재 알려진 지도에서 최적 경로이면서, 변경이 국소적일 때 A*를 매번 새로 실행하는 것보다 재계획 시간이 짧습니다.
한계: 격자(또는 그래프) 표현을 전제하므로 연속 공간이나 고차원 형상공간에는 그대로 쓰지 못합니다. 변경이 지도 전체에 걸치면 이점이 줄어듭니다.

논문에는 이렇게 적는다

격자 해상도, 이웃 연결(4방향/8방향), 비용 함수와 휴리스틱을 적습니다.
비교 대상(매번 A* 재실행, 다른 증분 알고리즘)과 환경 변화의 규모·빈도를 적습니다.
재계획 횟수, 노드 확장 수, 계산 시간을 보고합니다. 변화 규모가 커질 때의 성능 저하도 보입니다.
D*(원조), Focused D*, D* Lite 중 무엇을 썼는지 구분해서 적습니다.

논문에서는 이렇게 쓰입니다

실제 논문에서

이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.

예시 문장

아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.

D* 계열 알고리즘은 변경된 에지 비용 주변의 노드만 선택적으로 재계산하는 증분 탐색 기법으로, 정적 A* 대비 재계획 시간을 크게 단축한다.

지도의 일부만 바뀌었을 때 지도 전체를 다시 훑지 않고 바뀐 부분과 관련된 곳만 다시 계산해 계산량을 크게 줄인다는 의미입니다.

"한 연구는 실내 배송 로봇이 예기치 못한 사람의 이동을 장애물로 감지했을 때, D* Lite 알고리즘이 전체 경로를 다시 계산하는 A*보다 재계획 시간을 얼마나 단축하는지 실측하였다."

이 문장은 이론적 설명이 아니라 실제 로봇 실험에서 시간을 측정하여, 변화가 생겼을 때 부분만 다시 계산하는 방식이 얼마나 빠른지를 확인한 예입니다.

조금 더 깊게 보면

A*를 목표에서 역방향으로 탐색하도록 바꾼 것이어서 로봇이 움직여도 목표 쪽 정보가 재사용되며, 환경 변화가 적을 때 효율이 극대화됩니다. 변화가 크면 재계획 비용이 A*를 새로 돌리는 것과 비슷해지고, 격자 지도를 전제로 하므로 연속 공간이나 고차원 형상공간에는 그대로 쓸 수 없습니다.

D* 계열은 목표 지점에서부터 역방향으로 각 노드까지의 비용을 미리 계산해 두고, 로봇이 이동하며 새로운 장애물을 발견하면 그 주변 노드들의 비용만 다시 계산해 그래프 전체가 아닌 국소적인 파급 범위 안에서만 갱신이 전파되도록 설계된 것이 핵심 아이디어다.

D* Lite는 이 원리를 우선순위 큐 기반으로 더 간결하게 재구성한 버전으로, 구현이 비교적 단순해 실제 로봇 소프트웨어에 널리 채택되었다.

주의할 점

구현이 A*보다 복잡하며, 변경이 매우 광범위하게 발생하면 증분 갱신의 이점이 줄어듭니다. 환경 변화가 국소적으로 작을 때는 A*보다 훨씬 빠르지만, 변화 범위가 지도 전체에 걸쳐 크게 발생하면 갱신해야 할 노드 수가 늘어나 그 이점이 크게 줄어든다.

헷갈리기 쉬운 용어

경로 계획 계열의 용어를 구분합니다.

알고리즘	하는 일	특징
A*	알려진 정적 지도에서 최단 경로 탐색	환경이 바뀌면 다시 탐색
*D / D* Lite**	환경 변화 시 이전 탐색을 재사용해 경로 갱신	증분 재계획, 전역 경로
동적윈도우접근법	속도·가속도 제약 안에서 순간 속도 명령을 선택	지역 장애물 회피
점유격자지도	격자 셀의 장애물 점유 확률을 담는 지도 표현	알고리즘이 아니라 지도 형식

참고 문헌

Stentz, A. (1994). Optimal and efficient path planning for partially-known environments. Proceedings of the IEEE International Conference on Robotics and Automation, 3310–3317.
Koenig, S., & Likhachev, M. (2002). D* Lite. Proceedings of the AAAI Conference on Artificial Intelligence, 476–483.
Koenig, S., Likhachev, M., & Furcy, D. (2004). Lifelong planning A*. Artificial Intelligence, 155(1–2), 93–146.
Koenig, S., & Likhachev, M. (2005). Fast replanning for navigation in unknown terrain. IEEE Transactions on Robotics, 21(3), 354–363.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.

표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.