STT-CBS: A Conflict-Based Search Algorithm for Multi-Agent Path Finding with Stochastic Travel Times
This addresses path planning for robots or agents with uncertain travel times, offering a robust solution for applications like autonomous vehicles, though it is incremental as it builds on existing CBS methods.
The paper tackles multi-agent path finding with stochastic travel times by developing STT-CBS, an algorithm that ensures a user-specified maximum pairwise collision probability while optimizing expected travel times. Simulations and hardware experiments show it significantly reduces conflict probability compared to CBS without increasing complexity.
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.