2026-08-08T07:39:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15336 2024-03-06T10:55:10Z ddc:004 open_access

Solving the Non-Crossing MAPF with CP Peng, Xiao Solnon, Christine Simonin, Olivier Constraint Programming (CP) Multi-Agent Path Finding (MAPF) Assignment Problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiao Peng and Christine Solnon and Olivier Simonin 2021 Is Part Of LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2021.45 urn:nbn:de:0030-drops-153367 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.45 eng https://creativecommons.org/licenses/by/4.0/legalcode