Navigation Among Movable Obstacles (NAMO) Extended to Social and Multi-Robot Constraints
NAvigation en milieu MOdifiable (NAMO) étendue à des contraintes sociales et multi-robots
Résumé
As robots become ever more commonplace in human environments, taking care of ever more tasks such as cleaning, security or food service, their current limitations only become more apparent. One such limitation is of their navigation capability in the presence of obstacles: they always avoid them, and freeze in place when avoidance is impossible.
This is what brought about the creation of Navigation Among Movable Obstacles (NAMO) algorithms, expected to allow robots to manipulate obstacles as to facilitate their own movement. However, these algorithms were designed under the hypothesis of a single robot per environment, biasing NAMO algorithms into only optimizing the single robot's displacement cost - without any consideration for humans or other robots. While it is desirable to endow robots with the human capability of moving obstacles, they must however do so while respecting social norms and rules of humans.
We have thus extended the NAMO problem as to take into account these new social and multi-robots aspects. By relying on the concept of affordance spaces, we have developed a social occupation cost model allowing the evaluation of the impact of moved objects on the environment's navigability. We implemented (and improved) reference NAMO algorithms, in our open source simulation tool, and modified them so that they may plan compromises between robot displacement cost and social occupation cost of moved obstacles - resulting in improved navigability. We also developed an implicit coordination strategy allowing the concurrent execution of these same algorithms by multiple robots as is, without any explicit communication requirements, while preserving the no-collision guarantee; verifying the relevance of our social occupation cost model in the actual presence of other robots. As such, this work constitutes the first steps towards a Social and Multi-Robot NAMO.
Alors que les robots deviennent toujours plus présents dans les environnements humains, endossant toujours plus de tâches telles que le nettoyage, la surveillance ou encore le service en salle, leurs limites actuelles n’en deviennent que plus évidentes. Une de ces limites concerne leur capacité à naviguer en présence d’obstacles: ils chercheront systématiquement à les éviter, et resteront bloqués à défaut.
Ce constat a mené à la création d’algorithmes de NAvigation en milieu MOdifiable (NAMO), devant permettre aux robots de manipuler les obstacles pour faciliter leurs déplacements. Néanmoins, ces algorithmes ont été conçus sous l’hypothèse qu’un seul robot agîsse dans l’environnement, biaisant les algorithmes à n’optimiser que son seul coût de déplacement – sans considération pour les humains ou d’autres robots. S’il est souhaitable que les robots puissent bénéficier de la capacité humaine à déplacer des obstacles, ils doivent néamoins le faire dans le respect des normes et règles sociales humaines.
Nous avons donc étendu le problème de NAMO pour prendre en compte ces nouveaux aspects sociaux et multi-robots. En nous basant sur le concept d’espaces d’affordance, nous avons développé un modèle de coût d’occupation sociale permettant d’évaluer l’impact des objets déplacés sur la navigabilité de l’environnement. Nous avons implémenté (et amélioré) des algorithmes NAMO de référence, dans notre outil de simulation open source, puis les avons modifiés afin qu’ils puissent trouver un compromis entre coût de déplacement et coût d’occupation des obstacles manipulés – résultant en une amélioration de la navigabilité. Nous avons également développé une stratégie de coordination permettant d’exécuter ces mêmes algorithmes tels quels, sur plusieurs robots en parallèle, en absence de communication explicite, tout en préservant la garantie d’absence de collisions; vérifiant la pertinence de notre modèle de coût social en présence effective d’autres robots. Ces travaux constituent les premiers pas d’une NAMO Sociale et Multi-Robots.
Origine : Fichiers produits par l'(les) auteur(s)
