论文

研究表明:即使给出最优规划,规划宽度也难以近似

Planning Width Is Hard to Approximate Even Given the Unique Optimal Plan

精选理由

理论计算机科学这边的新结果:即使把最优规划直接给你,判断任务规划宽度是不是很小依然是 NP-hard,连 o(N) 近似都做不到。做启发式搜索或规划算法的人可以看看复杂度证明和那个对数近似的贪心正面结论。

arXiv 论文 2611.25484 研究规划宽度(planning width)的可近似性。作者构造了一类带正前提条件的 STRIPS 任务:提供唯一最优规划、单一可达目标状态、二叉分支和常数大小的动作,所有可达状态都位于最多比最优长一步的可达执行上。即便如此,区分宽度 1 与 Θ(N)(N 为原子数)对 set、chain、goal-admissible 三种宽度而言都是 NP-hard 的。

正文

论文证明了两个复杂性结论:除非 P=NP,不存在多项式时间算法能实现 o(N) 的单侧近似比或 o(√N) 的对称近似比,而简单估计方法恰好能达到这两个阶;对于给定长度至少为 2 的唯一最优规划的任务,针对固定阈值 k≥1 测试 set 或 chain 宽度是 coNP-complete 的,当 k 属于输入时为 Σ₂^P-complete。若只有一个目标状态可达,这些结论对 goal-admissible 宽度同样成立。

这项工作补充了迭代宽度搜索的理论基础:固定 k 时迭代宽度搜索可在有界 tuple-chain 宽度任务上多项式时间找到最优规划,但本文表明知道最优规划并不能消除认证更小宽度的困难。论文同时给出一个正面结果:在显式状态图上,贪心算法即使最优规划存在分支也能以对数因子近似 set 宽度。

原文 · arXiv cs.AI

Planning Width Is Hard to Approximate Even Given the Unique Optimal Plan

For each fixed $k$, iterative-width search finds optimal plans in polynomial time on tasks of bounded tuple-chain width, but the approximability of planning width has remained open even when an optimal plan is supplied. When all optimal plans visit the same state sequence, we characterize set and chain width as hitting numbers of competing states. We construct positive-precondition STRIPS tasks with a supplied unique optimal plan, a single reachable goal state, binary branching, and constant-size actions. Every reachable state lies on a goal-reaching execution at most one action longer than optimal, yet distinguishing width $1$ from $Θ(N)$, where $N$ is the number of atoms, is NP-hard for set, chain, and goal-admissible width. Unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm achieves a one-sided approximation factor $o(N)$ or a symmetric factor $o(\sqrt{N})$, and simple estimates attain both orders. For positive-precondition tasks with a supplied unique optimal plan of length at least two, testing set or chain width against a threshold $k\geq 1$ is coNP-complete for each fixed $k$ and $Σ_2^{\mathrm{P}}$-complete when $k$ is part of the input. Both results also hold for goal-admissible width if only one goal state is reachable. On an explicit state graph, a greedy algorithm approximates set width within a logarithmic factor even when optimal plans branch. Thus, knowing an optimal plan does not eliminate the difficulty of certifying substantially smaller width.

产业坐标与信源核验

本条情报归属 AITOP「论文」核心追踪栏目。涉及核心实体与技术议题包括:planning、STRIPS、复杂性理论、迭代宽度搜索,读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。

信源核验说明:本文原始线索采编自「arXiv cs.AI」(@Viet Bac Nguyen),经 AITOP 多维评分管线结构化提炼。