Bikramjit Banerjee's Publications

• Selected Publications • All Sorted by Date • All Classified by Publication Type •

Multi-agent Path Finding with Persistence Conflicts

B. Banerjee and C. Davis. Multi-agent Path Finding with Persistence Conflicts. IEEE Transactions on Computational Intelligence and AI in Games, 9(4):402–409, Wiley, 2017.

Download

[PDF] 

Abstract

Multi-agent path finding (MAPF) 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.

BibTeX

@Article{Banerjee16:Multi-agent,
  author = 	 {B. Banerjee and C. Davis},
  title = 	 {Multi-agent Path Finding with Persistence Conflicts},


  journal = 	 {IEEE Transactions on Computational Intelligence and AI
                 in Games},
  year = 	 {2017},
  volume = 	 {9},
  number = 	 {4},
  pages = 	 {402--409},
  publisher =    {Wiley},
  abstract =     {Multi-agent path finding (MAPF) 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.},
}

---

Generated by bib2html.pl (written by Patrick Riley ) on Sat May 29, 2021 15:48:22