R&E 연구노트 ③ A*와 가지치기로 경로 탐색하기

연구노트 시리즈.

경로가 너무 많다

화재 대피 경로 최적화의 첫 벽은 경우의 수였다.

가장 단순한 브루트 포스(모든 경로 다 따져보기)는 곧바로 막혔다. 건물 그래프에서 가능한 경로의 수가 폭발적으로 늘어 메모리 한계에 부딪혔다. 모든 경로를 메모리에 올려놓고 비교하는 방식은 애초에 불가능했다.

그래서 두 방향을 잡았다. 하나는 경로를 하나씩 처리하며 메모이제이션으로 중복 계산을 줄이는 것(DFS 기반), 다른 하나는 그래프 탐색 이론으로 최적이 될 수 없는 경로를 미리 잘라내는 것(가지치기)이다.

다익스트라에서 A*로

최단 경로 알고리즘으로는 다익스트라와 A*를 공부했다.

다익스트라는 출발점에서 모든 노드까지의 최단 거리를 차근차근 넓혀 나간다. 정확하지만 목적지가 정해져 있어도 사방으로 탐색해 낭비가 있다. A*는 여기에 목적지까지 대략 얼마나 남았는지를 추정하는 휴리스틱 함수를 더해 탐색을 목적지 쪽으로 집중시킨다.

우리는 휴리스틱을 직접 설계할 수 있는 A*를 택했다. 결국 이 프로젝트의 핵심 과제는 휴리스틱 함수를 얼마나 잘 설계하느냐였다. 휴리스틱이 실제 비용을 잘 근사할수록 탐색이 빨라지고, "이 경로는 가망 없다"고 잘라낼 근거도 생긴다.

가지치기 전략

탐색 공간을 줄이는 가지치기는 두 갈래로 설계했다.

첫째는 출구 기반 역방향 탐색이다. 출구에서 거꾸로 탐색해 각 위치에서 출구까지의 도달 시간 맵을 미리 계산해 둔다. 그러면 탐색 도중 어떤 위치에서든 출구까지 최소 얼마가 걸리는지 즉시 알 수 있고, 출구까지 가는 시간이 예측 가능한 최대 대피 시간보다 크면 그 경로는 답이 될 수 없으니 제거한다. 이 도달 시간 맵은 A*의 휴리스틱으로도 쓸 수 있는 정보다.

둘째는 반(class)별 대피 시간 기준 가지치기다. 학교라는 맥락에 맞춘 전략이다.

1. 각 반마다 대피로별 대피 시간을 구하고 그 최솟값을 정한다. 그 반이 가장 빨리 나갈 수 있는 시간이다.
2. 반들의 이 최소 대피 시간 중 최댓값을 기준선으로 삼는다. 가장 불리한 반이 빠져나가는 데 필요한 시간이다.
3. 이 기준선보다 더 오래 걸리는 경로는 각 반에서 제거한다.
4. 남은 경로들만으로 전체 대피 시나리오를 조합한다.

전체 대피가 끝나는 시간은 마지막으로 빠져나가는 사람이 결정하므로 이런 최소-최대 기준은 의미가 있었다.

보여줄 수 있는 것

알고리즘만으로는 전달이 안 돼서, 모의 화재 대피를 테스트해 볼 수 있는 UI도 만들었다. 가상 평면도에서 사람들이 어떤 경로로 빠져나가는지 시뮬레이션하는 도구였다.

여기까지가 화재 대피 경로 탐색의 절정이었다. 그러나 곧 한계에 부딪혀 이 주제를 접게 된다.