Title

Multiagent Path Finding With Persistence Conflicts

Document Type

Article

Publication Date

12-2017

Department

Computing

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

Find in your library

Share

COinS