Safe Interval RRT* for Scalable Multi-Robot Path Planning in Continuous Space

本文考虑在连续空间中解决多机器人路径规划问题，以找到无冲突的路径。这个问题的难点来自于两个主要因素。首先，多个机器人的参与导致组合决策，使搜索空间呈指数级增长。其次，连续空间呈潜在的无限状态和动作。对于这个问题，我们提出了一个两级方法，其中低级是基于采样的规划器Safe Interval RRT*（SI-RRT*），用于为单个机器人找到无碰撞轨迹。高级可以使用任何可以解决机器人间冲突的方法，我们采用了两种代表性方法，即优先级规划（SI-CPP）和基于冲突的搜索（SI-CCBS）。实验结果表明，SI-RRT*可以快速找到高质量的解决方案，并且只需少量样本。SI-CPP表现出更好的可扩展性，而SI-CCBS相比于连续空间中的最先进规划器，可以产生更高质量的解决方案。与最具可扩展性的现有算法相比，SI-CPP在100个机器人的情况下可以实现高达94％的成功率提高，并且不会对解决方案质量（即流程时间，所有机器人的旅行时间之和）产生重大影响。SI-CPP还可以将流程时间缩短高达45％。SI-CCBS相比竞争对手可以将流程时间降低9％，尽管成功率降低了14％。

解决问题：本文旨在解决多机器人路径规划（MRPP）中的冲突问题，其中机器人在连续空间中移动，需要找到无冲突的路径。

关键思路：本文提出了一个两级方法，其中低级别是一个基于采样的规划器SI-RRT*，用于找到单个机器人的无碰撞轨迹。高级别可以使用任何能够解决机器人间冲突的方法，其中我们采用了两种代表性的方法：优先级规划（SI-CPP）和冲突基础搜索（SI-CCBS）。

其他亮点：实验结果表明，SI-RRT*可以快速找到高质量的解决方案，仅需少量样本。SI-CPP表现出更好的可扩展性，而SI-CCBS相对于连续空间的现有规划器产生了更高质量的解决方案。与最具可扩展性的现有算法相比，SI-CPP在100个机器人的情况下实现的成功率高达94％，同时保持解决方案质量（即流量时间，所有机器人的旅行时间之和）没有显着的妥协。SI-CPP还将完成时间缩短了45％。SI-CCBS相对于竞争对手将流量时间缩短了9％，尽管成功率降低了14％。

相关研究：最近在这个领域中，还有一些相关的研究，例如“Decentralized Multi-Robot Path Planning with Subdimensional Expansion”和“Decoupled Planning and Control for Multi-Robot Systems: A Review”。