论文标题
STT-CBS：一种基于冲突的搜索算法，用于使用随机旅行时间进行多代理路径查找
STT-CBS: A Conflict-Based Search Algorithm for Multi-Agent Path Finding with Stochastic Travel Times
论文作者
论文摘要
我们提出了一种用于在图中找到多个随机剂的最佳路径的算法，以使用用户指定的最大成对碰撞概率到达其目的地。我们的算法称为STT-CB，使用基于冲突的搜索（CB），并为代理使用随机旅行时间（STT）模型。我们通过独立的伽马分布的随机变量沿图的每个边缘进行机器人行进时间，并提出概率碰撞识别和约束创建方法，以稳健地处理旅行时间不确定性。我们表明，在合理的假设下，我们的算法在预期的旅行时间之和，同时确保每个成对冲突概率上的上限。模拟和硬件实验表明，STT-CBS能够显着降低CBS的冲突概率，同时保持在同一复杂性类别中。
We present an algorithm for finding optimal paths for multiple stochastic agents in a graph to reach their destinations with a user-specified maximum pairwise collision probability. Our algorithm, called STT-CBS, uses Conflict-Based Search (CBS) with a stochastic travel time (STT) model for the agents. We model robot travel time along each edge of the graph by independent gamma-distributed random variables, and propose probabilistic collision identification and constraint creation methods to robustly handle travel time uncertainty. We show that under reasonable assumptions our algorithm is optimal in terms of expected sum of travel times, while ensuring an upper bound on each pairwise conflict probability. Simulations and hardware experiments show that STT-CBS is able to significantly decrease conflict probability over CBS, while remaining within the same complexity class.
