多智能体路径规划（MAPF）详解

"这篇笔记主要介绍了多智能体路径规划问题（MAPF）的基本概念、问题描述以及冲突类型。作者李拥祺探讨了MAPF在解决多个智能体路径冲突中的重要性，强调了全局路径规划和局部路径优化的核心部分。文中以离散时间步长为基础，阐述了每个agent在每个时间单位内只能占据一个节点并执行移动或等待的动作。此外，还区分了两种基本动作类型：move和wait，并定义了单智能体规划路径的概念。最后，提出了三种冲突类型：节点冲突、边冲突和跟随冲突。" 在多智能体路径规划问题（MAPF）中，主要目标是计算出一组没有碰撞的路径，让一组智能体从各自起点到达指定终点。这个问题在物流、机器人、游戏等多个领域有着广泛的应用。首先，MAPF的定义是为一群智能体寻找从当前位置到目标位置的碰撞自由路径。在实际应用中，解决MAPF问题有助于减少智能体之间的交互冲突，提高效率。 问题描述部分，MAPF被设定在无向图的环境中，每个智能体关联一个源节点和一个目标节点。时间被离散化为时间步长，每个agent在每个时间步长只能位于图的一个节点，并执行move（移动到相邻节点）或wait（保持原地）的动作。move动作遵循图的邻接关系，而wait动作则意味着agent在原地停留。通过一系列动作，agent可以形成一条从起点到终点的单智能体规划路径。 冲突类型是MAPF问题的核心挑战。节点冲突发生在同一时间点，当一个节点上有两个或更多agent时；边冲突则指多个agent在同一时间步长沿同一边移动，可能造成碰撞；跟随冲突是指一个agent计划在下一时间点占据当前被其他agent占用的节点。这些冲突情况需要在规划过程中有效避免。 解决MAPF问题通常涉及全局路径规划，即找到所有智能体的初始到目标的路径，以及局部路径优化，调整路径以避免或减少冲突。在实际算法设计中，可以采用搜索算法、优化方法或者组合优化策略。例如，A*搜索、Conflict-Based Search (CBS) 和 Optimal CBS (OCBS) 是常用的MAPF解决方案。 总结来说，这篇笔记提供了MAPF问题的基础知识，包括其定义、问题表述和冲突类型，为理解多智能体路径规划问题的关键要素提供了基础。对于进一步研究和开发解决MAPF问题的算法，这些基础知识是不可或缺的。