인공지능(AI)이 복잡한 문제의 최적 또는 준최적 해를 찾는 과정은 여전히 많은 연산 자원을 요구합니다. 이러한 배경에서 '제한적 비최적 탐색(Bounded-suboptimal search)'은 최적해에 가까운(w배 이내) 해를 찾으면서도 탐색 노력을 줄이는 것을 목표로 합니다. 최근 '확률적 포컬 탐색(Probabilistic Focal Search, PFS)'이라는 새로운 알고리즘이 제안되어, 기존 방법론의 한계를 극복하고 탐색 효율을 획기적으로 개선할 가능성을 보여주었습니다.
기존의 '포컬 탐색(Focal Search, FS)'은 휴리스틱(heuristic) 안내를 통해 탐색 공간을 효율적으로 줄여나갑니다. FS는 'FOCAL'이라는 특정 임계값(w * f_min) 내의 노드들 중에서 가장 유망한 노드를 확장합니다. 하지만 이 결정론적(deterministic) 방식은 때때로 f_min(현재까지 발견된 최적 경로의 하한선)이 오랫동안 변하지 않아 FOCAL 영역이 확장되지 못하고 탐색이 지연되는 문제가 있었습니다. PFS는 이러한 문제를 해결하기 위해 FS의 휴리스틱 선택을 따르되, 일정 확률(1-p)로 f_min 값을 가진 노드를 확장하는 방식을 도입했습니다. 이 확률적 접근은 f_min을 더 빠르게 진전시켜 FOCAL 영역을 넓히고, 결과적으로 더 많은 유망 노드를 탐색에 포함시켜 해를 찾는 시간을 단축합니다.
연구진은 N-퍼즐(N-Puzzle), 팬케이크 정렬(Pancake Sorting), 외판원 문제(Traveling Salesperson Problem, TSP) 등 다양한 벤치마크를 통해 PFS의 성능을 검증했습니다. 특히 f_min 값이 오랫동안 정체되어 탐색 병목 현상이 발생하는 시나리오에서 PFS는 기존 FS 대비 노드 확장 수를 90% 이상 줄이는 놀라운 성능 향상을 보였습니다. 이는 PFS가 FOCAL 영역 확장이 지연될 때 가장 큰 효과를 발휘한다는 것을 의미합니다. 또한, '언제든지(anytime) 알고리즘'으로 확장된 '언제든지 확률적 포컬 탐색(Anytime Probabilistic Focal Search, APFS)'은 일반화된 외판원 문제(Generalized Covering TSP, GCTSP)에서 테스트된 모든 알고리즘 중 가장 우수한 성능을 보여주었습니다. 이 연구는 복잡한 최적화 문제 해결에 있어 AI 알고리즘의 효율성을 높이는 중요한 진전을 가져왔으며, 자율 시스템, 로봇 공학, 물류 최적화 등 다양한 분야에 적용될 잠재력을 가지고 있습니다.