Solving the Non-Crossing MAPF with CP - Archive ouverte HAL Access content directly
Conference Papers Year :

Solving the Non-Crossing MAPF with CP

(1, 2) , (1, 2) , (1, 2)
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.
Fichier principal
Vignette du fichier
main.pdf (993.25 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

hal-03320987 , version 1 (16-08-2021)

Identifiers

Cite

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⟩
87 View
89 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More