Skip to Main content Skip to Navigation
Conference papers

Solving the Non-Crossing MAPF with CP

Xiao Peng 1, 2 Christine Solnon 1, 2 Olivier Simonin 1, 2 
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