Template Matching and Decision Diagrams for Multi-agent Path Finding

September 2020

Template Matching and Decision Diagrams for Multi-agent Path Finding

Authors:

Jayanth Krishna Mogali, Willem-Jan Van Hoeve, and Stephen F. Smith

Abstract:

We propose a polyhedral cutting plane procedure for computing a lower bound on the optimal solution to multi-agent path finding (MAPF) problems. We obtain our cuts by projecting the polytope representing the solutions to MAPF to lower dimensions. A novel feature of our approach is that the projection polytopes we used to derive the cuts can be viewed as ‘templates’. By translating these templates spatio-temporally, we obtain different projections, and so the cut generation scheme is reminiscent of the template matching technique from image processing. We use decision diagrams to compactly represent the templates and to perform the cut generation. To obtain the lower bound, we embed our cut generation procedure into a Lagrangian Relax-and-Cut scheme. We incorporate our lower bounds as a node evaluation function in a conflict-based search procedure, and experimentally evaluate its effectiveness.

Notes:

Willem-Jan van Hoeve was partially supported by Office of Naval Research Grant No. N00014-18-1-2129 and National Science Foundation Award #1918102. The authors thank Viraj Parimi for his help with generating the plots.
@conference{Mogali-2020-126716,
author = {Jayanth Krishna Mogali And Willem-Jan Van Hoeve And Stephen F. Smith},
title = {Template Matching and Decision Diagrams for Multi-agent Path Finding},
booktitle = {Proceedings of International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR '20)},
year = {2020},
month = {September},
pages = {347 - 363},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.