A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution

简介

在多智能体路径规划的研究中，一个研究领域是确定在执行过程中代理被延迟时如何有效地实现重新规划。其中一个选项是重新安排代理的通过顺序，即代理访问同一位置的顺序。为此，我们提出了Switchable-Edge Search (SES)算法，这是一种类似于A*的算法，旨在寻找最优的通过顺序。我们证明了SES的最优性，并通过模拟评估了其效率。SES的最佳变体对于小型和中型问题只需不到1秒的时间，对于大型问题，其运行速度比基线快4倍。
作者讲解

目前尚无作者解读视频，你可点击下方【许愿开讲】按钮，许愿作者开讲~
图表
解决问题

论文旨在解决多智能体路径规划中的重新规划问题，即在执行过程中代理被延迟时如何有效地重新规划行动顺序的问题。
关键思路

论文提出了Switchable-Edge Search (SES)算法，用于寻找最优的通过顺序，该算法基于A*算法，并证明了其最优性。
其它亮点

SES算法在小到中等规模的问题上只需要不到1秒的时间，对于大规模问题比基线算法快4倍。论文还提供了实验结果和数据集，并探讨了未来的研究方向。
相关研究

在这个领域中，最近的相关研究包括：Multi-Agent Path Finding (MAPF)、Conflict-Based Search (CBS)、M*算法等。