증분 휴리스틱 탐색은 그래프가 시간에 따라 변화할 때 그래프에서 경로를 찾는 문제를 다루는 인공지능의 알고리즘 계열이다. A*와 같은 고전적 휴리스틱 탐색 방법이 환경이 변할 때마다 처음부터 완전한 해를 다시 계산하는 것과 달리, 증분 휴리스틱 탐색 알고리즘은 이전 탐색 노력에서 가능한 한 많은 정보를 재사용한다. 이러한 재사용은 동적이거나 부분적으로 알려진 환경에서 계산 비용을 크게 줄일 수 있으며, 로봇 내비게이션, 비디오 게임 경로 탐색, 자율 주행 차량 경로 지정과 같은 응용 분야에서 특히 유용하다.
핵심 아이디어는 간선 비용이 변경되거나 새로운 장애물이 발견됨에 따라 휴리스틱 함수와 탐색 트리를 증분적으로 갱신하는 것이다. 변경이 발생하면 알고리즘은 이전 탐색의 어느 부분이 여전히 유효한지, 어느 부분을 수정해야 하는지 식별한 후 필요한 갱신을 전파한다. 이 접근 방식은 정적 그래프를 가정하는 고전적 휴리스틱 탐색과 휴리스틱 없이 경로를 재사용할 수 있지만 휴리스틱의 안내가 부족한 증분 탐색 모두와 대조된다.
역사적 발전
증분 휴리스틱 탐색의 기초는 1990년대 후반과 2000년대 초반에 마련되었다. 가장 영향력 있는 알고리즘인 D Lite는 2002년 Sven Koenig와 Maxim Likhachev가 소개했다. D Lite는 1994년 Anthony Stentz가 모바일 로봇 내비게이션을 위해 설계한 초기 D 알고리즘에 기반한다. D Lite는 원래 D*를 단순화하면서도 효율성을 유지하며, 이 분야의 표준 참조가 되었다.
또 다른 핵심 알고리즘은 2001년 Koenig와 Likhachev가 소개한 Lifelong Planning A(LPA)이다. LPA는 휴리스틱을 일관되게 유지하면서 간선 비용의 변화를 처리하며, D Lite의 기초를 형성한다. 이 분야는 이후 Generalized Adaptive A(GAA)와 Anytime D*와 같은 변형으로 확장되었으며, 이들은 해의 품질과 계산 시간을 맞바꾼다.
알고리즘 원리
증분 휴리스틱 탐색 알고리즘은 일반적으로 각 노드에 대해 두 가지 유형의 값을 유지한다: g-값(시작점에서 알려진 최상의 경로 비용)과 h-값(목표까지의 휴리스틱 추정치)이다. 또한 노드가 일관적인지, 즉 g-값이 선행 노드들의 최솟값과 같은지 추적한다. 간선 비용이 변경되면 알고리즘은 영향을 받는 노드의 g-값을 갱신하고 f = g + h로 정렬된 우선순위 큐를 사용하여 탐색 트리를 통해 변경 사항을 전파한다.
핵심 혁신은 LPA와 D Lite에서 "rhs-값"(오른쪽 변 값)을 사용하는 것이다. 이는 선행 노드의 g-값과 간선 비용의 합의 최솟값을 나타낸다. 노드의 g-값이 rhs-값과 같으면 로컬 일관성이 있다고 한다. 알고리즘은 로컬 비일관 노드 목록을 유지하고 키 순서로 처리하며, 키는 (min(g, rhs) + h, min(g, rhs)) 쌍이다. 이는 탐색의 필요한 부분만 다시 계산되도록 보장한다.
로봇 공학 및 AI 응용
증분 휴리스틱 탐색은 알려지지 않거나 변화하는 환경에서 경로 계획을 위해 로봇 공학에서 널리 사용된다. 예를 들어, 건물을 탐색하는 로봇은 처음에 지도를 기반으로 경로를 계획할 수 있지만, 새로운 장애물(예: 닫힌 문)을 발견하면 처음부터 다시 시작하지 않고 증분적으로 계획을 갱신할 수 있다. 이는 계산 시간이 제한된 실시간 내비게이션에서 중요하다.
비디오 게임에서 비플레이어 캐릭터(NPC)는 이동 장애물이나 변경되는 목표가 있는 동적 지형을 탐색해야 하는 경우가 많다. 증분 휴리스틱 탐색은 효율적인 재계획을 가능하게 하여 게임 응답성을 향상시킨다. 이 기술은 교통 상황에 적응해야 하는 배달 경로의 물류와 링크 비용이 변동하는 네트워크 라우팅에도 적용된다.
다른 탐색 방법과의 비교
고전적 A 탐색은 정적 그래프에서 최적이고 완전하지만, 그래프가 변경될 때 이전 작업을 모두 폐기하므로 동적 환경에서는 비효율적이다. 증분 휴리스틱 탐색은 A의 최적성 보장을 유지하면서 이전 계산을 재사용한다. 그러나 탐색 트리와 일관성 정보를 저장하기 위해 추가 메모리가 필요하다.
또 다른 관련 접근 방식은 anytime 탐색으로, 좋은 해를 빠르게 찾은 다음 시간이 주어지면 개선하는 것을 목표로 한다. Anytime D*와 같은 일부 증분 알고리즘은 두 속성을 모두 결합한다: 시간이 허락하면 빠르게 차선의 해를 반환하고 정제할 수 있다. 이는 시간이 중요한 응용 분야에서 특히 유용하다.
현재 연구 및 미래 방향
증분 휴리스틱 탐색의 최근 연구는 매우 큰 그래프로의 확장, 연속 상태 공간 처리, 기계 학습과의 통합에 초점을 맞추고 있다. 예를 들어, 학습 기반 휴리스틱을 사용하여 초기 h-값을 개선하고 확장 수를 줄일 수 있다. 다중 코어 프로세서를 위한 증분 탐색 병렬화와 고차원 문제를 위한 RRT*와 같은 샘플링 기반 계획기와의 결합에 대한 연구도 있다.
현대 Artificial intelligence 시스템의 맥락에서 증분 휴리스틱 탐색은 Waymo 자율 주행 차량이나 Tesla 시스템과 같은 구현 에이전트에게 여전히 관련이 있으며, 실시간 재계획이 필수적이다. 이 원리는 Machine learning 및 Deep learning의 탐색 학습 연구에도 영향을 미치지만, 고전적 알고리즘은 보장된 최적성을 위한 표준으로 남아 있다.
같이 보기
참고 문헌
- Koenig, S., & Likhachev, M. (2002). D* Lite. Proceedings of the National Conference on Artificial Intelligence.
- Koenig, S., & Likhachev, M. (2001). Lifelong Planning A*. Artificial Intelligence.
- Stentz, A. (1994). Optimal and Efficient Path Planning for Partially-Known Environments. IEEE International Conference on Robotics and Automation.