Front-to-Attractors: 양방향 탐색에서 Front-to-Front 휴리스틱 수정
Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search
한국어 초록
휴리스틱은 양방향 탐색 알고리즘의 성능에서 핵심적인 역할을 하며, 이러한 알고리즘은 일반적으로 두 가지 주요 유형에 의존한다. Front-to-end(F2E) 휴리스틱은 상태 s에서 탐색의 목표(순방향 탐색의 경우 목표 상태, 역방향 탐색의 경우 시작 상태)까지의 거리를 추정한다. 반면 front-to-front(F2F) 휴리스틱은 s'가 프론티어 상태들에 걸쳐 변하는 쌍별(pairwise) 함수 h(s, s')를 사용하여 s에서 반대 방향 탐색 프론티어까지의 거리를 추정한다. F2F 휴리스틱은 일반적으로 더 정보가 풍부하여 노드 확장 횟수를 줄이지만, 광범위한 쌍별 평가에 의존하기 때문에 상당한 계산 오버헤드가 발생한다. 이 한계를 해결하기 위해, F2F의 정보성 대부분을 유지하면서 계산 비용을 크게 줄이는 새로운 휴리스틱 유형인 front-to-attractors(F2A)를 제안한다. F2A는 반대 프론티어의 모든 상태까지의 거리를 평가하는 대신, 반대 탐색 방향에서 동적으로 유지되는 소규모 attractor 집합까지 s에서의 거리를 추정한다. 이 attractor들은 전체 프론티어의 대리(surrogate) 역할을 하여, F2F가 제공하는 최적성 보장을 유지하면서 계산 비용의 일부만으로 풍부한 휴리스틱 안내를 가능하게 한다. 여러 도메인에서 F2A를 평가한 결과, F2F 대비 쌍별 평가 횟수를 최대 11.2배 줄이면서, 평균적으로 F2E 대비 노드 확장 횟수를 4.8배 적게 달성함을 보인다.
원문 초록
Heuristics play a central role in the performance of bidirectional search algorithms, which commonly rely on two main classes. Front-to-end (F2E) heuristics estimate the distance from a state s to the target of the search (the goal for forward search or the start for backward search). In contrast, front-to-front (F2F) heuristics estimate the distance from s to the opposite search frontier using a pairwise function h(s, s'), where s' ranges over frontier states. Although F2F heuristics are typically more informative and therefore reduce the number of node expansions, their reliance on extensive pairwise evaluations incurs substantial computational overhead. To address this limitation, we introduce a new heuristic class, front-to-attractors (F2A), that preserves much of the informativeness of F2F while dramatically reducing its computational cost. Rather than evaluating distances to all states on the opposite frontier, F2A estimates the distance from s to a small, dynamically maintained set of attractors in the opposite search direction. These attractors serve as a surrogate for the full frontier, enabling rich heuristic guidance at a fraction of the computational expense while maintaining the optimality guarantees offered by F2F. We evaluate F2A across multiple domains and show that it reduces the number of pairwise evaluations by up to 11.2x compared to F2F, while achieving 4.8x fewer node expansions than F2E on average.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.07047v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
지수적으로 더 적은 공간으로 계획을 탐색하는 방법 학습
Learning How to Search for Plans with Exponentially Less Space
계획(plan)에 대한 휴리스틱 탐색(heuristic search)은 휴리스틱이 거의 완벽하더라도 지수적으로 많은 상태를 저장할 수 있다. 우리는 대신 탐색 제어(search control)를 학습하는데, 이는 도메인별로 하나씩 작성되는 인덱시컬 정책(indexical policy)으로서, 객체를 담는 레지스터(register)와 규칙을 순서화하는 모드를 갖는 일반화된 정책(generalized policy)이다. 우리는 객체를 레지스터에 적재하고 백트래킹 지점을 표시하는 choose 규칙을 추가하는데, 이 지점에서는 하나의 후보만으로 충분하다. 그 외의 모든 규칙은 가능한 모든 결과에 대해 작동해야 하며 탐색을 필요로 하지 않는다. 우리의 주요 결과는, 무한 실행을 배제하는 구조적 종료성(structural termination)이 객체 수에 대한 다항식으로 모든 실행을 제한한다는 것이다. 그러면 깊이 우선 절차(depth-first procedure)는 상태 공간이 얼마나 크더라도 방문한 상태의 목록 없이 다항식 공간(polynomial space) 안에서 계획을 찾아낸다. 그 대가는 시간이며, 이는 실행 과정에서의 실제 선택 횟수인 선택 깊이(choice depth)에 대해서만 지수적이다. 따라서 이러한 정책이 풀 수 있는 모든 클래스는 NP에 속하며, 선택 깊이가 상수일 때는 P에 속한다. 우리는 종료성을 증명하고 학습 과제를 검증하며 선택 깊이를 작게 유지하는 반례 기반(counterexample-guided) 루프에서 언어 모델로 이러한 정책들을 학습시킨다. 학습된 정책을 사용하여, 이 절차는 IPC 2023 Learning Track과 Autoscale Agile 스위트의 1,890개 테스트 과제 중 1,709개를 풀어내며, 이는 LAMA, BFWS, Levitron보다 더 많고, 그중 대부분을 1초와 100MiB 이내에 해결한다.
동적 환경에서의 최적 계획 수립
Optimal Planning in a Dynamic World
배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.
마지막 고원(Final Plateau)에서 표준 A* 타이 브레이킹 전략에 따른 확장 횟수
Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau
A* 탐색 알고리즘에서 동일한 $f$-값을 갖는 노드에 대한 타이 브레이킹(tie-breaking, 동점 처리) 전략은 A*가 마지막 $f$-층(layer)에서 어떤 상태들을 확장할지 결정합니다. 9가지 표준 타이 브레이킹 전략에 대해, 일관적인 휴리스틱(consistent heuristic) 하에서 모든 전략 쌍마다 임의로 큰 가산적 확장 차이(additive expansion gap)로 상대 전략보다 특정 전략을 선호하게 만드는 양의 비용 인스턴스가 존재함을 보입니다. 매개변수화된 단위 비용 격자 예시 또한 FIFO 및 LIFO를 사용하는 low-$h$ 간에 무한한 확장 횟수 비율을 발생시킵니다. 목표가 아닌 상태에서 $h > 0$인 단위 비용 탐색에서, 목표 근처의 정확한 휴리스틱 값은 상호보완적인 극단적 결과로 이어집니다. 완벽 영역(perfect region) 내의 공통 형상(configuration)으로부터 남은 확장 횟수는 low-$h$가 최소화하는 반면, $h=1$인 모든 마지막 고원 상태가 목표 직전 상태(goal predecessor)일 때 전체 확장 횟수는 high-$h$가 최대화합니다. 마지막으로, 평가 함수 $f_{\alpha} = g + \alpha h$를 사용할 때 목표가 아닌 상태에서 $h>0$이면, 모든 휴리스틱 가중치(weight) $0 \leq \alpha<1$은 타이 브레이킹 민감도를 제거하며 모든 타이 브레이킹 전략이 동일한 상태 집합을 확장합니다.
비일관적 A*의 평활 분석
Smoothed Analysis of Inconsistent A*
A* 탐색은 인공지능에서 기본적인 경로 탐색 알고리리즘이다. 허용 가능하고 일관적인 휴리스틱은 각 상태를 최대 한 번만 확장함으로써 효율적인 성능을 보장하지만, 현대 탐색 응용에서는 기계 학습, 무작위 평가 등에서 유도된 강력하지만 비일관적인 휴리스틱을 자주 사용한다. 이러한 비일관적 휴리스틱 사용에 대한 오랜 이론적 장벽은 치명적인 노드 재확장(re-expansion) 위험이며, 이는 최악의 경우 $\Omega(2^n)$의 지수적 시간 복잡도를 초래한다. 그러나 경험적 관찰은 이 비관적 상한과 모순되며, 비일관적 A*가 실제로는 매우 효율적으로 동작함을 보여 준다. 이론과 실무 사이의 이 큰 격차를 메우기 위해, 본 논문은 비일관적 휴리스틱을 사용하는 A* 알고리리즘에 대한 최초의 평활 분석(smoothed analysis)을 제시한다. 우리는 최악 경우 탐색 그래프의 간선 가중치에 미세한 무작위 perturbation을 적용하여 전형적인 실세계 노이즈를 모델링한다. 주요 결과는 비일관적 A*의 기대 평활 시간 복잡도가 다항식으로 bounded됨을 증명하며, 구체적으로 총 반복 횟수가 $O(n^2 m \kappa)$임을 보인다. 여기서 $n$은 노드 수, $m$은 간선 수, $\kappa$는 무작위 perturbation의 규모를 조절한다. 또한 이 결과가 음수 가중치 그래프에서의 Dijkstra 알고리리즘과 기능적으로 동등한 문제로 자연스럽게 확장됨을 보인다.
Key-Interval A*: 구조적 추상화를 통한 격자 경로 탐색 가속
Key-Interval A*: Accelerating Grid Pathfinding via Structural Abstraction
기존 4-연결 격자 경로 탐색을 위한 정확(exact) 방법들은 온라인 탐색을 줄이지만, 종종 세밀한 탐색 상태를 유지하거나 상당한 전처리(preprocessing)를 요구한다. 본 논문은 경량 전처리를 사용하여 자유 공간(free space)의 간결한 구간(interval) 수준 추상화를 구성하고 탐색하는 최적 경로 탐색 알고리즘인 Key-Interval A* (KIA*)를 제안한다. KIA*는 구간을 사용하여 자유 공간을 표현하며, 구간이란 통과 가능한 셀들의 최대 연속 구간(maximal contiguous runs)이다. 구조적 경계 변화를 포착하는 핵심 구간(key interval)을 추출하고, 연속적인 비핵심(non-key) 영역을 통해 이를 연결한다. KIA*는 이로부터 얻어진 핵심-구간(key-interval) 그래프에서 A* 스타일 탐색을 수행하고, 셀 수준의 지역 탐색 없이 구간 체인(interval chain)으로부터 격자 경로를 구성적으로 재구성한다. 4-연결 격자에서 KIA*의 완전성(completeness)과 최적성(optimality)을 증명한다. 표준 벤치마크(benchmark) 실험에서 KIA*는 정확한 최단 경로 길이를 유지하고 8개 벤치마크 그룹 중 7개에서 최고 실행 시간을 달성하며, 구조화된 맵과 게임 맵에서 가장 큰 성능 향상을 보인다.
다목적 탐색에서 다중값 휴리스틱과 차원 축소의 통합
Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search
다목적 최단경로(MOSP) 알고리즘은 전통적으로 각 상태에 허용 가능한 단일 비용 벡터를 연결하는 단일값 휴리스틱(SVH)에 의존한다. SVH는 안전한 하한을 제공하지만, 파레토 프론트(Pareto frontier)의 트레이드오프 구조를 포착하지 못하고 종종 약한 탐색 가이던스를 제공한다. 다중값 휴리스틱(MVH)은 상태를 비용 추정치 집합에 매핑함으로써 이 한계를 해결하여, 가능한 트레이드오프의 더 풍부한 근사를 가능하게 한다. 현대 MOSP 알고리즘은 지배성(dominance) 검사를 효율적으로 수행하기 위해 차원 축소(DR) 기법에 크게 의존한다. 그러나 MVH와 DR을 통합하면 미묘한 정확성 문제가 발생한다. 우리는 DR과 MVH를 단순히 결합하면 DR에 필요한 순서 불변성(ordering invariants)이 파괴되어 부정확하고 불완전한 탐색으로 이어짐을 보인다. 이 문제를 해결하기 위해, 우리는 MVH와 DR을 안전하게 통합하기 위한 최초의 이론적 프레임워크를 개발한다. 먼저 휴리스틱 일관성(heuristic consistency)을 강제함으로써 탐색 정확성을 복원하는 이론적 기준선인 $\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$를 제안한다. 이 접근법의 실용적 한계를 인식하여, 우리는 주요 기여인 $\text{L}\text{-}\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$를 소개한다. 이 알고리즘은 DR에 대한 "게으른(lazy)" 낙관적 접근을 사용하여, 국소적 순서 위반을 동적으로 감지하고 수정함으로써 허용 가능한 MVH만으로도 엄밀한 정확성을 유지한다. 다양한 벤치마크(benchmark)에서 $\text{L}\text{-}\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$는 최첨단 MOSP 알고리즘과 동등하거나 그보다 나은 성능을 보이며, MVH가 제공하는 추가 가이던스가 더 강한 가지치기로 이어지는 경우 10배 이상의 속도 향상을 달성한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.