Planification de chemin en environnement inconnu et dynamique

Auteur : Francis Colas

Informations générales

Encadrants	Francis Colas
Adresse	INRIA Nancy Grand Est, 615 rue du Jardin Botanique, 54600 Villers-lès-Nancy
Téléphone	03 54 95 86 30
Email	francis.colas@inria.fr
Bureau	C125

Motivation

La navigation en robotique est traditionnellement structurée en séparant la perception, la planification et l’exécution de la trajectoire . Une fois la carte obtenue (perception), la planification calcule un chemin ou une trajectoire. Cette trajectoire est ensuite fournie à un module de contrôle ou suivi de trajectoire.

Il existe plusieurs approches de planification de trajectoire : les approches par décomposition telles qu’A^* , les approches par optimisation , ou les approches stochastiques. Celles-ci, comme RRT^* ou PRM^*, échantillonnent l’environnement pour en reconstruire efficacement la connectivité afin de planifier un chemin .

Si la carte change, il faut planifier totalement une nouvelle trajectoire, ce qui peut être coûteux. Pour l’évitement d’obstacles dynamiques qui ne sont pas dans la carte, on court-circuite la planification et c’est le suivi de trajectoire qui se charge de l’évitement.

Il est néanmoins possible que la carte soit invalide et qu’il faille complétement changer de plan. C’est le cas, par exemple, lorsqu’une porte, observée comme ouverte lors de la cartographie, se retrouve fermée. Il faut alors en emprunter une autre et pas simplement l’éviter comme s’il s’agissait d’un obstacle temporaire. Dans ce cas, il serait préférable de mettre à jour le plan.

Sujet

Le sujet de ce stage est d’étudier, proposer et évaluer des algorithmes permettant de planifier des chemins efficacement en cas de mise à jour de la carte. Des approches existent pour certains algorithmes comme D^*-lite qui étend A^* ou RRT^X qui étend RRT^* .

Néanmoins ces algorithmes ne sont capables que de traiter une seule requête (c’est-à-dire la navigation vers un but donné) et doivent recommencer de zéro si le but change. À l’inverse, des algorithmes à base de roadmaps permettent de planifier à moindre coût des chemins vers des buts différents mais seulement dans une carte statique.

L’idée de ce sujet est :

• de proposer une adaptation de RRG^* ou PRM^* permettant de se mettre à jour en cas de changement dans la carte,
• de comparer les performances des différentes approches, à la fois en simulation et sur un robot réel.

Cadre du travail

Ces méthodes seront mises en œuvre et évaluées sur des robots mobiles évoluant dans l’appartement intelligent d’Inria Nancy Grand Est. Cet appartement, plate-forme expérimentale pour l’étude notamment de l’assistance à la personne, comporte une grande variété de capteurs distribués dans l’environnement et plusieurs robots, tels que des turtlebots ou un robot Tiago.

References

Hart, P. E., Nilsson, N. J., and Raphael, B. (1968).  A formal basis for the heuristic determination of minimum cost paths.  IEEE transactions on Systems Science and Cybernetics, 4(2), 100–107.

Koenig, S., and Likhachev, M. (2002).  D^* lite.  Aaai/iaai, 15.

Marder-Eppstein, E. and Berger, E. and Foote, T., and Gerkey, B. and Konolige, K. (2010)  The office marathon: Robust navigation in an indoor office environment.  In 2010 IEEE international conference on robotics and automation, pp. 300–307. IEEE, 2010.

Karaman, S., and Frazzoli, E. (2011).  Sampling-based algorithms for optimal motion planning.  The international journal of robotics research, 30(7), 846–894.

Schulman, J., Duan, Y., Ho, J., Lee, A., Awwal, I., Bradlow, H., Pan, J., Patil, S., Goldberg, K., and Abbeel, P. (2014).  Motion planning with sequential convex optimization and convex collision checking.  The International Journal of Robotics Research, 33(9), 1251–1270.

Otte, M., and Frazzoli, E. (2016).  RRT^X: Asymptotically optimal single-query sampling-based motion planning with quick replanning.  The International Journal of Robotics Research, 35(7), 797–822.

Macenski, S., Martín, F., White, R., and Clavero, J. G. (2020).  The Marathon 2: A Navigation System.  In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS20), 2020.