HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Solving the Non-Crossing MAPF with CP

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Contributor : Christine Solnon Connect in order to contact the contributor
Submitted on : Monday, August 16, 2021 - 6:22:06 PM
Last modification on : Monday, May 16, 2022 - 4:46:03 PM
Long-term archiving on: : Wednesday, November 17, 2021 - 6:38:07 PM


Publisher files allowed on an open archive




Xiao Peng, Christine Solnon, Olivier Simonin. Solving the Non-Crossing MAPF with CP. CP 2021 - 27th International Conference on Principles and Practice of Constraint Programming, Oct 2021, Montpellier (on line), France. pp.1-17, ⟨10.4230/LIPIcs.CP.2021.20⟩. ⟨hal-03320987⟩



Record views


Files downloads