Edward Lam, Pierre Le Bodic |
PosterID:
76
PDF
Poster
BibTeX
|
| BCP, a state-of-the-art algorithm for optimal Multi-agent Path Finding, uses the branch-and-cut-and-price framework to decompose the problem into (1) a master problem that selects a set of collision-free low-cost paths, (2) a pricing problem that adds lower-cost paths to the master problem, (3) separation problems that resolve various kinds of conflicts in the master problem, and (4) branching rules that split the nodes in the high-level branch-and-bound search tree. This paper focuses on the separation aspects of the decomposition by introducing five new classes of fractional conflicts and valid inequalities that remove these conflicts to tighten the linear programming relaxation in the master problem. Experimental results on 9695 instances across 16 maps indicate that including the five families of inequalities allows BCP to solve an additional 276 instances, optimize the same instances 39% faster, and solve 1208 more instances than CBSH-RM and 590 more than Lazy CBS. | |
| Canb | 10/29/2020, 11:00 – 12:00 |
| 10/30/2020, 20:00 – 21:00 |
| Paris | 10/29/2020, 01:00 – 02:00 |
| 10/30/2020, 10:00 – 11:00 |
| NYC | 10/28/2020, 20:00 – 21:00 |
| 10/30/2020, 05:00 – 06:00 |
| LA | 10/28/2020, 17:00 – 18:00 |
| 10/30/2020, 02:00 – 03:00 |
Online Computation of Euclidean Shortest Paths in Two Dimensions
Ryan Hechenberger, Peter J Stuckey, Daniel Harabor, Pierre Le Bodic, Muhammad Aamir Cheema
Bounded Suboptimal Path Planning with Compressed Path Databases
Shizhe Zhao, Mattia Chiari, Adi Botea, Alfonso E. Gerevini, Daniel Harabor, Alessandro Saetti, Peter J. Stuckey
Computing Close to Optimal Weighted Shortest Paths in Practice
Nguyet Tran, Michael J. Dinneen, Simone Linz
New Valid Inequalities in Branch-and-Cut-and-Price for Multi-Agent Path Finding
Edward Lam, Pierre Le Bodic