Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints

多智能体路径规划（MAPF）问题涉及为一组代理找到无碰撞路径，引导它们从起点到达目标位置。然而，MAPF并没有考虑到一些实际任务相关的限制。例如，代理可能需要在具有特定执行时间的目标位置执行操作，遵守预定的顺序和时间框架。此外，目标分配可能未预定义给代理，并且优化目标可能缺乏明确的定义。为了将任务分配、路径规划和用户定义的目标纳入一个连贯的框架中，本文研究了具有优先级和时间约束的任务分配和路径规划（TAPF-PTC）问题。我们增强了基于冲突的搜索（CBS），以同时生成遵守优先级和时间约束的任务分配和无碰撞路径，并通过强化学习（RL）中用户定义的奖励函数的回报量来最大化目标。实验表明，相对于多智能体强化学习（MARL）和自适应目标分配和路径规划（TAPF）方法，我们的算法CBS-TA-PTC可以高效地解决具有优先级和时间约束的高度具有挑战性的拆弹任务。

本文旨在解决任务分配和路径规划中的先决条件和时间约束问题，同时最大化强化学习中用户定义奖励函数的回报。

本文提出了一种基于冲突的搜索算法（CBS-TA-PTC），用于生成同时满足先决条件和时间约束的任务分配和无冲突路径，并最大化用户定义的奖励函数回报。

本文的算法在高难度的炸弹拆除任务中表现出色，并相对于MARL和TAPF方法具有高效性。实验使用的数据集未提及，但作者开源了算法的代码。

与本文相关的研究包括Multi-Agent Path Finding（MAPF）和Target Assignment and Path Finding（TAPF）等。