We consider a chance-constrained multi-robot motion planning problem in the presence of Gaussian motion and sensor noise. Our proposed algorithm, CC-K-CBS, leverages the scalability of kinodynamic conflict-based search (K-CBS) in conjunction with the efficiency of the Gaussian belief trees used in the Belief-A framework, and inherits the completeness guarantees of Belief-A's low-level sampling-based planner. We also develop three different methods for robot-robot probabilistic collision checking, which trade off computation with accuracy. Our algorithm generates motion plans driving each robot from its initial state to its goal while accounting for the evolution of its uncertainty with chance-constrained safety guarantees. Benchmarks compare computation time to conservatism of the collision checkers, in addition to characterizing the performance of the planner as a whole. Results show that CC-K-CBS can scale up to 30 robots.
翻译:我们考虑在高斯运动和传感器噪声存在的情况下进行机会约束下的多机器人运动规划问题。我们提出的算法CC-K-CBS利用运动学冲突检测算法(K-CBS)的可扩展性以及Belief-A框架中使用的高斯置信树的效率,并继承Belief-A低级采样路径规划器的完整性保证。我们还开发了三种不同的机器人-机器人概率碰撞检测方法,它们权衡计算和准确性之间的关系。我们的算法生成每个机器人的运动规划,从其初始状态驱动到其目标状态,同时考虑其不确定性的演变以满足机会约束的安全保证。基准测试比较碰撞检测器的保守性与计算时间,并表征规划器作为一个整体的性能。结果表明,CC-K-CBS可以扩展到30个机器人。