We introduce a new Multi-Agent Path Finding (MAPF) problem which is motivated by an industrial application. Given a fleet of robots that move on a workspace that may contain static obstacles, we must find paths from their current positions to a set of destinations, and the goal is to minimise the length of the longest path. The originality of our problem comes from the fact that each robot is attached with a cable to an anchor point, and that robots are not able to cross these cables. We formally define the Non-Crossing MAPF (NC-MAPF) problem and show how to compute lower and upper bounds by solving well known assignment problems. We introduce a Variable Neighbourhood Search (VNS) approach for improving the upper bound, and a Constraint Programming (CP) model for solving the problem to optimality. We experimentally evaluate these approaches on randomly generated instances.
@InProceedings{peng_et_al:LIPIcs.CP.2021.45, author = {Peng, Xiao and Solnon, Christine and Simonin, Olivier}, title = {{Solving the Non-Crossing MAPF with CP}}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-211-2}, ISSN = {1868-8969}, year = {2021}, volume = {210}, editor = {Michel, Laurent D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.45}, URN = {urn:nbn:de:0030-drops-153367}, doi = {10.4230/LIPIcs.CP.2021.45}, annote = {Keywords: Constraint Programming (CP), Multi-Agent Path Finding (MAPF), Assignment Problems} }
Feedback for Dagstuhl Publishing