호주 연구진, 격자 지도 경로 탐색 'A*' 최대 수십 배 빠르게 하는 '점프 포인트' 기법 발표...최적 경로 보장하면서 사전 작업도 추가 메모리도 필요 없어
호주 연구진이 격자 경로 탐색을 수십 배 빠르게 하는 '점프 포인트'를 발표했다.
[한국정보기술신문] 로봇과 비디오 게임에서 널리 쓰이는 격자(그리드) 지도 위 경로 탐색을, 최적 경로를 보장하면서도 기존보다 수십 배 빠르게 처리하는 새 탐색 기법이 제시됐다. 호주 정보통신기술연구소(NICTA)와 호주국립대학교(ANU)의 대니얼 해러보어와 알반 그라스티엥 연구진은 이런 내용을 담은 논문 '격자 지도 경로 탐색을 위한 온라인 그래프 가지치기'를 인공지능 분야 학술대회 'AAAI 2011'에서 발표했다. 연구진이 '점프 포인트(jump point·도약점)'라고 이름 붙인 일부 노드만 골라 탐색하는 방식으로, 사전 준비 작업이나 추가 메모리 없이 표준 경로 탐색 알고리즘 'A*(에이스타)'의 속도를 한 자릿수 배 이상 끌어올린다는 것이 핵심이다.
격자 지도는 공간을 바둑판처럼 정사각형 칸으로 나눈 뒤, 각 칸을 지나갈 수 있는 곳과 장애물로 구분해 경로를 찾는 가장 보편적인 표현 방식이다. 한 칸에서 상하좌우로 움직이면 비용 1, 대각선으로 움직이면 약 1.41(2의 제곱근)의 비용이 든다. A*는 이런 환경에서 출발점부터 목표점까지 비용이 가장 적게 드는 길을 찾는 대표적 알고리즘이다.
격자 지도의 '경로 대칭성'이 만든 비효율
연구진은 격자 지도가 본질적으로 안고 있는 '경로 대칭성' 문제에 주목했다. 경로 대칭성이란 출발점과 도착점이 같고 길이도 같지만, 칸을 밟는 순서만 다른 사실상 동일한 경로가 수없이 많이 존재하는 현상을 뜻한다. 예컨대 오른쪽으로 한 칸, 위로 한 칸 가는 길과 위로 한 칸, 오른쪽으로 한 칸 가는 길은 도착 지점과 거리가 같다.
문제는 일반적인 탐색 알고리즘이 이렇게 사실상 똑같은 길들을 일일이 따로 평가한다는 점이다. 연구진은 이 때문에 알고리즘이 의미 없이 많은 상태를 검토하게 되고, 목표를 향한 실질적 진전이 가로막힌다고 설명했다. 그동안 학계와 산업계에서는 이 비효율을 줄이기 위해 여러 기법을 내놓았으나, 대부분 속도를 얻는 대신 최적 경로를 포기하거나, 미리 계산해 둔 정보를 메모리에 저장해 두어야 하는 한계가 있었다.
핵심은 '점프 포인트'만 펼치기
점프 포인트 기법의 발상은 단순하다. 탐색 도중 굳이 따져 볼 필요가 없는 이웃 칸을 규칙에 따라 걸러 내고, 한 방향으로 계속 '건너뛰며' 나아가다가 의미 있는 분기점에 해당하는 칸에 도달했을 때만 그 칸을 탐색 대상으로 삼는 것이다. 연구진은 이 분기점에 해당하는 칸을 점프 포인트라고 정의했다.
구체적으로는 어떤 칸을 펼칠 때, 부모 칸에서 그 칸을 거치지 않고도 같거나 더 짧게 도달할 수 있는 이웃은 평가 대상에서 제외한다. 직선 이동과 대각선 이동에 각각 적용되는 이 '이웃 가지치기 규칙'을 통과해 남는 칸을 '자연 이웃'이라 부른다. 다만 주변에 장애물이 있어 다른 길로는 도달할 수 없는 이웃이 생기면, 그 칸은 반드시 평가해야 하는 '강제 이웃'이 된다.
알고리즘은 한 방향으로 한 칸씩 나아가면서 목표 칸이거나 강제 이웃을 가진 칸을 만나면 그곳을 점프 포인트로 보고 멈춘다. 장애물을 만나 더 나아갈 수 없으면 그 방향 탐색은 성과 없이 종료한다. 대각선으로 이동할 때는 한 걸음을 내딛기 전에 먼저 좌우 직선 방향에 점프 포인트가 있는지를 확인하는데, 연구진은 이 절차가 최적성을 지키는 데 핵심적이라고 강조했다. 이렇게 점프 포인트와 점프 포인트 사이의 중간 칸들은 한 번도 펼쳐지지 않기 때문에 탐색량이 크게 줄어든다.
"최적 경로를 보장한다" 증명
연구진은 점프 포인트만 펼쳐도 항상 최적 경로를 찾을 수 있다는 점을 수학적으로 증명했다. 핵심 논리는 경로상에서 진행 방향이 바뀌는 지점인 '전환점'이 모두 점프 포인트와 일치한다는 데 있다. 이들은 임의의 최적 경로를 동일한 길이의 대칭 경로로 변형한 뒤, 그 경로를 같은 방향으로만 움직이는 구간들로 나누었다. 그리고 각 구간의 시작과 끝, 즉 모든 전환점이 점프 포인트의 조건을 만족함을 보였다. 출발점은 탐색 시작 시 반드시 펼쳐지고 목표점은 정의상 점프 포인트이므로, 결국 최적 경로 위의 모든 핵심 칸이 빠짐없이 탐색된다는 결론이다.
이 기법은 별도의 사전 처리 과정이 필요 없는 '온라인' 방식이라는 점도 특징이다. 지도를 미리 분석해 데이터를 저장해 두는 기존 기법과 달리, 탐색을 진행하는 동안 그때그때 점프 포인트를 찾아낸다. 이 때문에 추가 메모리 부담이 없고, 다른 속도 향상 기법과도 대부분 충돌 없이 함께 쓸 수 있다고 연구진은 설명했다.
기존 기법보다 수십~수백 배 적은 노드 탐색
연구진은 공개 경로 탐색 라이브러리 'HOG'에서 가져온 네 가지 표준 시험 환경에서 성능을 측정했다. 시험 환경에는 무작위 장애물과 방으로 구성된 '어댑티브 뎁스', 게임 '발더스 게이트 2'와 '드래곤 에이지: 오리진'에서 추출한 실제 게임 지도, 작은 방들이 통로로 연결된 '룸스'가 포함됐다. 비교 대상은 최적 경로를 지키는 또 다른 가지치기 기법 '스웜프(Swamps)'와, 빠르지만 최적이 아닌 경로를 내놓는 계층형 알고리즘 'HPA*'였다.
탐색한 노드 수를 기준으로 한 효율 측정에서 점프 포인트는 네 환경에서 각각 20.37배, 215.36배, 35.95배, 13.41배의 개선을 보였다. 같은 조건에서 스웜프는 1.89~4.70배, HPA*는 4.14~9.63배에 그쳤다. 실제 탐색 시간 역시 발더스 게이트와 드래곤 에이지 지도에서 점프 포인트는 목표 지점에 25~30배 빨리 도달한 반면, 스웜프는 3~5배 빨라지는 데 머물렀다.
연구진은 스웜프가 목표와 무관한 영역을 걸러 내는 데 효과적이지만 남은 영역을 탐색하는 데는 여전히 적지 않은 노력이 든다고 분석하며, 두 기법이 상호 보완적이어서 함께 쓰면 더 큰 효과를 낼 수 있다고 덧붙였다. HPA*와 비교해서는, 점프 포인트가 펼치는 노드 수는 훨씬 적지만 노드 하나를 처리하는 시간은 더 길다는 점도 함께 제시했다. 실험은 2.93기가헤르츠(GHz) 인텔 코어 2 듀오 프로세서와 4기가바이트(GB) 메모리를 갖춘 컴퓨터에서 이뤄졌다.
게임·로봇 활용과 남은 과제
점프 포인트 기법은 단순하면서도 효과가 크고, 최적 경로를 보장하면서 추가 메모리가 필요 없으며, 사전 처리 없이도 매우 빠르다는 점에서 기존 기법들이 안고 있던 단점을 동시에 피했다는 평가를 받는다. 연구진은 이런 장점을 모두 갖춘 알고리즘을 아직 본 적이 없다고 밝혔다. 다만 이 기법은 정사각형 격자에 특화돼 있어, 실험에 쓰인 환경 밖에서의 범용성은 후속 연구로 검증할 부분으로 남는다.
연구진은 향후 과제로 육각형 격자 등 다른 형태의 격자에도 적용할 수 있도록 가지치기 규칙을 확장하는 방안을 제시했다. 이런 격자는 한 칸에서 갈라지는 방향의 수가 정사각형 격자보다 적어, 점프 포인트의 효과가 더 클 수 있다는 것이다. 아울러 스웜프나 HPA* 같은 다른 속도 향상 기법과 결합하는 방향도 후속 연구 주제로 꼽았다. 경로 탐색은 자율주행과 로봇, 게임 등 실시간 판단이 중요한 분야에서 두루 쓰이는 만큼, 메모리와 사전 작업 부담 없이 속도를 끌어올리는 이런 접근이 어떻게 확장될지 주목된다.
- Citation:
Harabor, D., & Grastien, A. (2011). Online Graph Pruning for Pathfinding On Grid Maps. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1114–1119. https://doi.org/10.1609/aaai.v25i1.7994
한국정보기술신문 인공지능분과 정유리 기자 news@kitpa.org
