Decomposition and Cut Generation Strategies for Solving Multi-Robot Deployment Problems

Autor: Adriana Pacheco, Cédric Pralet, Stéphanie Roussel
Přispěvatelé: ONERA / DTIS, Université de Toulouse [Toulouse], ONERA-PRES Université de Toulouse
Rok vydání: 2019
Předmět:
Zdroj: Lecture Notes in Computer Science ISBN: 9783030300470
CP
Principles and Practice of Constraint Programming25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019, Proceedings
CP 2019 The 25th International Conference on Principles and Practice of Constraint Programming
CP 2019 The 25th International Conference on Principles and Practice of Constraint Programming, Sep 2019, STAMFORD, United States. ⟨10.1007/978-3-030-30048-7_28⟩
DOI: 10.1007/978-3-030-30048-7_28
Popis: International audience; In this paper, we consider a multi-robot deployment problem involving a set of robots which must realize observation tasks at different locations and navigate through a shared network of waypoints. To solve this problem, we develop a two-level approach which alternates between (a) quickly obtaining high-level schedules based on a coarse grain CP model which approximates navigation tasks as setup times between observations , and (b) generating more accurate schedules based on a fine grain CP model which takes into account all resource usage conflicts during traversals of the shared network. The low-level layer also contains an explanation module able to generate constraints holding on high-level decision variables. These constraints (or cuts) account for interferences found in the low-level solutions and which the high-level scheduler should take into account to minimize the makespan. The proposed variants of the cut generation strategy are incomplete, the aim being to obtain good quality solutions in a short time, and they differ in the way they allow to diversify search. Experiments show the efficiency of this approach and the complementarity of the cut generation schemes proposed.; Dans cet article, nous examinons un problème de déploiement de plusieurs robots qui doivent réaliser des tâches d'observation à différents endroits et naviguer dans un réseau partagé de points de cheminement. Pour résoudre ce problème, nous développons une approche à deux niveaux qui alterne entre (a) l'obtention rapide d'ordonnancements de haut niveau basés sur un modèle de PC à gros grain qui se rapproche des tâches de navigation comme temps de préparation entre les observations, et (b) la génération d'ordonnancements plus précis basés sur un modèle de PC à grain fin qui prend en compte tous les conflits d'utilisation des ressources pendant les traversées du réseau partagé. La couche de bas niveau contient également un module d'explication capable de générer des contraintes tenant compte des variables de décision de haut niveau. Ces contraintes (ou coupes) tiennent compte des interférences trouvées dans les solutions de bas niveau et dont le planificateur de haut niveau doit tenir compte pour minimiser le makespan. es variantes proposées de la stratégie de génération de coupes sont incomplètes, le but étant d'obtenir des solutions de bonne qualité dans un délai court, et elles diffèrent dans la manière dont elles permettent de diversifier la recherche. Les expériences montrent l'efficacité de cette approche et la complémentarité des schémas de génération de coupes proposés.
Databáze: OpenAIRE
Externí odkaz: