在树状网络中，让多智能体在通信范围内高效避撞移动。
Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
- 基于树结构设计三种精确算法，支持有限通信范围下的路径规划。
- 当通信范围和智能体数量固定时，算法在树或近似树结构上高效运行。
- 适用于需保持通信连通性的机器人协同场景，如无人机编队。
多个智能体需在网络中以最快速度到达目标位置，同时避免碰撞，目标是最小化方案的完成时间（makespan）。本文在多智能体路径规划问题中引入通信约束：每个智能体的通信范围有限，需维持通信连通性。研究在参数化复杂度框架下，针对具有树拓扑或有界最大度（即有界树宽）的网络，提出三种精确算法。算法效率依赖于通信范围、智能体数量（或完成时间）作为参数。进一步证明：即使完成时间仅为3、通信范围为1，若将智能体数量作为输入参数，则几乎不可能存在高效算法。
原文摘要 · Abstract (English)
Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated by a measure known as the makespan of the proposed solution. This is the setting studied in the Multiagent Path Finding problem. In this work, we additionally provide the agents with a way to communicate with each other. Due to size constraints, it is reasonable to assume that the range of communication of each agent will be limited. What should be the trajectories of the agents to, additionally, maintain a backbone of communication? In this work, we study the Multiagent Path Finding with Communication Constraint problem under the parameterized complexity framework. Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network. We provide such algorithms for the case when the communication range and the number of agents (the makespan resp.) are provided in the input and the network has a tree topology, or bounded maximum degree (has a tree-like topology, i.e., bounded treewidth resp.). We complement these results by showing that it is highly unlikely to construct efficient algorithms when considering the number of agents as part of the input, even if the makespan is $3$ and the communication range is $1$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。