Multiagent Path Finding With Persistence Conflicts
Document Type
Article
Publication Date
12-2017
Department
Computing
School
Computing Sciences and Computer Engineering
Abstract
Multiagent path finding is the problem of finding paths for a set of agents-one for each agent-in a graph that the agents navigate simultaneously. Agents must navigate from their individual start to goal vertices without any collision. We argue that the prevalent treatment of path conflicts in the literature is incomplete for applications, such as computer games and crowd simulations, and extend the definition of path conflicts to accommodate cases where agents persist in their intermediate locations and even after reaching their goals. We show that an existing algorithm, conflict-based search (CBS), can be extended to handle these cases while preserving its optimality. Experiments show that our variant of CBS generates fewer nodes and runs faster than a competing algorithm.
Publication Title
IEEE Transactions on Computational Intelligence and AI in Games
Volume
9
Issue
4
First Page
402
Last Page
409
Recommended Citation
Banerjee, B.,
Davis, C. E.
(2017). Multiagent Path Finding With Persistence Conflicts. IEEE Transactions on Computational Intelligence and AI in Games, 9(4), 402-409.
Available at: https://aquila.usm.edu/fac_pubs/15315