Document Open Access Logo

Solving the Non-Crossing MAPF with CP

Authors Xiao Peng, Christine Solnon, Olivier Simonin

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.45.pdf
  • Filesize: 1.04 MB
  • 16 pages

Document Identifiers

Author Details

Xiao Peng
  • CITI, INRIA, INSA Lyon, F-69621, Villeurbanne, France
Christine Solnon
  • CITI, INRIA, INSA Lyon, F-69621, Villeurbanne, France
Olivier Simonin
  • CITI, INRIA, INSA Lyon, F-69621, Villeurbanne, France

Funding

This work was supported by the European Commission under the H2020 project BugWright2 (871260): Autonomous Robotic Inspection and Maintenance on Ship Hulls and Storage Tanks.

Cite As Get BibTex

Xiao Peng, Christine Solnon, and Olivier Simonin. Solving the Non-Crossing MAPF with CP. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CP.2021.45

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.

Subject Classification

ACM Subject Classification
  • Computing methodologies
Keywords
  • Constraint Programming (CP)
  • Multi-Agent Path Finding (MAPF)
  • Assignment Problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed. edition, 2008. Google Scholar
  2. S. Bhattacharya, M. Likhachev, and V. Kumar. Topological constraints in search-based robot path planning. Autonomous Robots, 33(3):273-290, 2012. Google Scholar
  3. Rainer E. Burkard and Eranda Çela. Linear assignment problems and extensions. Handbook of Combinatorial Optimization, pages 75-149, 1999. Google Scholar
  4. J. Carlsson, B. Armbruster, Saladi Rahul, and Haritha Bellam. A bottleneck matching problem with edge-crossing constraints. Int. J. Comput. Geom. Appl., 25:245-262, 2015. Google Scholar
  5. Geoffrey Chu and Peter J. Stuckey. Chuffed solver description, 2014. Available at URL: http://www.minizinc.org/challenge2014/description_chuffed.txt.
  6. Susan Hert and Vladimir J. Lumelsky. The ties that bind: Motion planning for multiple tethered robots. Robotics Auton. Syst., 17(3):187-215, 1996. Google Scholar
  7. H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1‐2):83-97, 1955. Google Scholar
  8. Jean-Claude Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991. Google Scholar
  9. Jiaoyang Li, Pavel Surynek, Ariel Felner, Hang Ma, T. K. Satish Kumar, and Sven Koenig. Multi-agent path finding for large agents. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):7627-7634, July 2019. URL: https://doi.org/10.1609/aaai.v33i01.33017627.
  10. Tomás Lozano-Pérez and Michael A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM, 22(10):560–570, 1979. Google Scholar
  11. Nenad Mladenovic and Pierre Hansen. Variable neighborhood search. Comput. Oper. Res., 24(11):1097-1100, 1997. Google Scholar
  12. Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack. Minizinc: Towards a standard CP modelling language. In Principles and Practice of Constraint Programming - CP 2007, volume 4741 of LNCS, pages 529-543. Springer, 2007. Google Scholar
  13. David W. Pentico. Assignment problems: A golden anniversary survey. Eur. J. Oper. Res., 176(2):774-793, 2007. Google Scholar
  14. Putnam. Problem a4, 1979. Google Scholar
  15. Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40-66, 2015. URL: https://doi.org/10.1016/j.artint.2014.11.006.
  16. S. Thomas, Dipti Deodhare, and M. N. Murty. Extended conflict-based search for the convoy movement problem. IEEE Intelligent Systems, 30:60-70, 2015. Google Scholar
  17. Thayne T. Walker, Nathan R. Sturtevant, and Ariel Felner. Extended increasing cost tree search for non-unit cost domains. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI'18, page 534–540. AAAI Press, 2018. Google Scholar
  18. J. Yu and S. LaValle. Structure and intractability of optimal multi-robot path planning on graphs. In In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 1444-1449, 2013. Google Scholar
  19. Xu Zhang and Quang-Cuong Pham. Planning coordinated motions for tethered planar mobile robots. Robotics and Autonomous Systems, 118:189-203, 2019. URL: https://doi.org/10.1016/j.robot.2019.05.008.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact