arXiv:2606.20644v1 cs.AI

다목적 탐색에서 다중값 휴리스틱과 차원 축소의 통합

Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search

Maya Wolff, Ariel Felner, Oren Salzman

제출 2026-06-05

한국어 초록

다목적 최단경로(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배 이상의 속도 향상을 달성한다.

원문 초록

Multi-objective shortest-path (MOSP) algorithms traditionally rely on single-valued heuristics (SVHs), which associate each state with a single admissible cost vector. While SVHs provide safe lower bounds, they fail to capture the trade-off structure of the Pareto frontier and often yield weak search guidance. Multi-valued heuristics (MVHs) address this limitation by mapping states to sets of cost estimates, enabling a richer approximation of possible trade-offs. Modern MOSP algorithms are highly dependent on dimensionality reduction (DR) techniques to efficiently perform dominance checks. However, integrating MVHs with DR introduces subtle correctness challenges. We show that naively combining DR with MVHs destroys the ordering invariants required for DR, leading to unsound and incomplete search. To address this issue, we develop the first theoretical frameworks for safely integrating MVHs with DR. First, we introduce $\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$, a theoretical baseline that restores search correctness by enforcing heuristic consistency. Recognizing the practical limitations of this approach, we then introduce our primary contribution, $\text{L}\text{-}\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$. This algorithm employs a "lazy," optimistic approach to DR, preserving exact correctness with only an admissible MVH by dynamically detecting and repairing local ordering violations. Across a range of benchmarks, $\text{L}\text{-}\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$ matches or improves over state-of-the-art MOSP algorithms, and achieves speedups of over 10x in instances where the additional guidance provided by the MVH translates into stronger pruning.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.20644v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.23680v1cs.DS공통 태그 Combinatorial Optimization, Heuristic Search, shortest path

비일관적 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 알고리리즘과 기능적으로 동등한 문제로 자연스럽게 확장됨을 보인다.

arXiv:2610.10954v1cs.AI공통 태그 Combinatorial Optimization, Heuristic Search

지수적으로 더 적은 공간으로 계획을 탐색하는 방법 학습

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 이내에 해결한다.

arXiv:2610.03312v1cs.AI공통 태그 Combinatorial Optimization, Heuristic Search

동적 환경에서의 최적 계획 수립

Optimal Planning in a Dynamic World

배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.

arXiv:2609.23293v1cs.AI공통 태그 Combinatorial Optimization, Heuristic Search

마지막 고원(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$은 타이 브레이킹 민감도를 제거하며 모든 타이 브레이킹 전략이 동일한 상태 집합을 확장합니다.

arXiv:2607.04875v2cs.CC공통 태그 Dimensionality Reduction, Combinatorial Optimization

저랭크 행렬 부호화 및 원소별 거듭제곱 행렬 분해의 복잡도에 관하여

On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization

비음수 행렬 $X$, 분해 랭크 $r$, 그리고 양의 정수 $p$가 주어질 때, 원소별 거듭제곱 행렬 분해(EPMF)는 $X = |X_r|^{\circ p}$ (정확한 경우) 또는 $X \approx |X_r|^{\circ p}$ (근사 경우)를 만족하는 저랭크 행렬 $X_r$을 탐색하는 문제이며, 여기서 $(\cdot)^{\circ p}$는 원소별 지수를 나타낸다. EPMF는 모듈러스 모델($p=1$)과 원소별 제곱 분해($p=2$)를 특수 경우로 포함하며, 후자는 제곱근 랭크와 밀접하게 관련된다. 본 논문에서는 정확한 결정 문제와 Frobenius 노름 근사 문제의 계산 복잡도를 분석하고 완전한 복잡도 전경을 확립한다. 정확한 경우에서, EPMF는 주어진 행렬 $X$의 원소 부호를 뒤집어 랭크-$r$ 행렬을 얻는 조합론적 문제—본 논문에서 저랭크 행렬 부호화(LRMS) 문제라 칭함—와 동치임을 보인다. 먼저 LRMS, 그리고 이에 따라 정확한 EPMF가 강 NP-난해(strongly NP-hard)임을 보임으로써, 제곱근 랭크에 대한 약 NP-난해 결과(Math. Prog., 2015)를 개선한다. 이어서 $r$이 고정될 때 LRMS가 다항 시간에 풀림을 보인다. 더 나아가, 랭크 $r$이 입력의 일부인 경우, 일반 행렬에 대해 알고리즘이 매개변수 $r$에 대해 고정-매개변수 다루기 가능(FPT)함을 보이며, 실제로 수행 시간은 입력 행렬의 원소 수에 대해 고정-매개변수 선형임을 증명한다. Frobenius 노름을 오차 척도로 사용하는 근사 경우에서는, 가장 작은 비자명 경우인 $r=2$일 때조차 EPMF가 NP-난해임을 보인다.

arXiv:2606.28907v1cs.NE공통 태그 Combinatorial Optimization, shortest path

대규모 병렬 뉴로모픽 하드웨어에서 효율적인 그래프 탐색을 위한 확장성 로드맵

Road to scalability for efficient graph search on massively parallel neuromorphic hardware

가중 그래프에서의 최단 경로를 효율적으로 계산하는 것은 다양한 응용 분야를 가진 근본적인 문제다. 뉴로모픽(neuromorphic) 하드웨어 플랫폼은 대규모 병렬 및 효율적인 연산을 제공하여 병렬성 트레이드오프를 변화시킬 것으로 기대된다. 본 연구에서는 뉴로모픽 시스템에서 활용 가능한 로컬 연산과 네트워크 통신을 활용하도록 설계된 분산 최단 경로 알고리즘인 NEURO-MAPP(Neuromorphic-based Min-Add Parallel Propagation)을 제안한다. SpiNNaker 2 플랫폼에 최적화된 알고리즘 구현을 제공하고, 다양한 합성 그래프 및 실세계 그래프를 대상으로 성능을 평가한다. 평가 결과는 최신 CPU에서의 Dijkstra 알고리즘과 비교된다. NEURO-MAPP 구현은 대부분의 그래프 유형에서 실행 시간 측면의 확장성이 우수하며, 거의 모든 경우에서 최단 경로 쿼리당 에너지 소비가 CPU 구현보다 적음을 확인하였다. 이러한 결과는 희소하고 스파이크(spike) 기반 통신을 특징으로 하는 뉴로모픽 하드웨어가 그래프 탐색 및 관련 작업에서 확장 가능하고 에너지 효율적인 연산 플랫폼으로서의 잠재력을 지님을 보여준다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.