解决多智能体在受限环境中的运动规划复杂性问题
On the complexity of constrained reconfiguration and motion planning
- 提出k-兼容排序框架，建模多智能体状态转换约束
- 证明该问题在多种条件下均为NP完全，包含平面、无环等情况
- 给出k=1或图结构树宽有界时的多项式时间解法，适合机器人调度应用
在受限环境中协调多个智能体的运动是机器人学、路径规划与调度中的基础挑战。一个典型例子是：将n个机械臂（每条表示为线段）依次旋转至垂直方向，每次仅允许顺时针或逆时针旋转一次，且不发生碰撞。这属于更一般的k-兼容排序问题——每个智能体有k种状态变化动作，需在由一组有向图对G编码的约束下到达目标状态。我们证明，即使G为平面、退化或无环图，该问题仍为NP完全。但当k=1或G具有有界树宽时，存在多项式时间算法。我们还引入支持每智能体多动作的推广形式，显著拓展了该框架在调度、重构及路径规划等场景的应用范围。
原文摘要 · Abstract (English)
Coordinating the motion of multiple agents in constrained environments is a fundamental challenge in robotics, motion planning, and scheduling. A motivating example involves $n$ robotic arms, each represented as a line segment. The objective is to rotate each arm to its vertical orientation, one at a time (clockwise or counterclockwise), without collisions nor rotating any arm more than once. This scenario is an example of the more general $k$-Compatible Ordering problem, where $n$ agents, each capable of $k$ state-changing actions, must transition to specific target states under constraints encoded as a set $\mathcal{G}$ of $k$ pairs of directed graphs. We show that $k$-Compatible Ordering is $\mathsf{NP}$-complete, even when $\mathcal{G}$ is planar, degenerate, or acyclic. On the positive side, we provide polynomial-time algorithms for cases such as when $k = 1$ or $\mathcal{G}$ has bounded treewidth. We also introduce generalized variants supporting multiple state-changing actions per agent, broadening the applicability of our framework. These results extend to a wide range of scheduling, reconfiguration, and motion planning applications in constrained environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。