树形结构上带通信约束的多智能体路径搜索的精确算法

Arxiv：2412.08556v4通告类型：替换-交叉摘要：考虑这样一种场景，即多个代理必须以最佳方式通过网络移动，每个代理都朝向其结束位置，同时避免冲突。所谓最优，我们指的是尽可能快，这是通过一个被称为拟议解决方案的最大完工时间的衡量标准来评估的。这是在多代理路径查找问题中研究的设置。在这项工作中，我们还为代理提供了一种相互通信的方式。由于大小的限制，可以合理地假设每个代理的通信范围将受到限制。此外，为了保持通信的主干，代理的轨迹应该是什么？在这项工作中，我们研究了在参数复杂性框架下具有通信约束的多智能体路径搜索问题。我们的主要贡献是三个精确的算法，它们在考虑输入网络的特定结构时是有效的。我们给出了当通信范围和代理数量(分别为最大完工时间)时的算法。并且网络具有树状拓扑或有界最大度(具有树状拓扑，即有界树宽)。我们通过证明当考虑代理的数量作为输入的一部分时，即使完工时间为$3$，通信范围为$1$，也不太可能构造有效的算法来补充这些结果。