RobAIR/Pilotage Automatique/Algorithmes

De fablab
Aller à : navigation, rechercher

Le pilotage du robot requiert le calcul d'un chemin optimal à suivre au sein de la foule. On regroupe ici les points clés du problème, les idées de résolution, et les algorithmes mis en oeuvre pour y parvenir.

Contraintes importantes

  • Carte incomplète
  • Obstacles en mouvement
  • Temps de déplacement limité par l'énergie restante dans la batterie (ne pas dépasser la distance critique à partir de laquelle on ne peut plus atteindre un point de rechargement sans mourir en chemin)

Algorithme d'évitement de foule

Si on arrive à éviter efficacement la foule en mode semi-automatique (c'est-à-dire dans le mode où un pilote distant donne des instructions au robot grâce à une tablette), alors le passage au mode automatique sera simple. Il faudra calculer un plus court chemin du départ à l'arrivée. On aura alors une liste d'instructions de pilotages qu'on pourra traiter de la même manière que si elles venaient d'un humain derrière sa tablette.

On commence donc par chercher un algorithme d'évitement de la foule.

Pourquoi éviter la foule ?

  1. Les humains n'aiment pas qu'on leur rentre dedans.
  2. On doit pouvoir se déplacer, il faut donc contourner les obstacles, comme on le fait avec les murs.

Première étape : ne pas rentrer dans les gens

Une première étape, en mode semi-automatique, serait d'empêcher la progression du robot si un humain lui bloque le passage. Cela permettrait d'éviter les collisions. Ensuite, l'humain qui est aux commandes pourra diriger lui-même le robot dans une autre direction où le passage est possible. Dans cette étape, on ignore simplement les commandes non réalisables. Pour progresser, le robot doit recevoir des instructions valides.

Note : il faudrait vérifier que cette étape n'est pas déjà implémentée sous forme de "réflexes" du robot. Même si c'est le cas, il faudra voir à quel point ces réflexes fonctionnent, pour qu'en plus d'éviter les collisions (point de vue technique), le robot reste à distance respectable de la foule (point de vue acceptation sociale du truc à roulettes qui se maintient à 1cm de ma chaussure).

Algorithme en pseudo-code

tant que I := instruction de pilotage faire
   si la voie est libre dans la direction de I alors
      effectuer I
   fin si
fin tant que

Bien sûr, toutes les questions d'évitement de foule ne s'appliquent qu'aux instructions qui déplacent le robot, pas à celles qui par exemple le feraient tourner sa caméra.

Deuxième étape : autonomie

Une deuxième étape consisterait en le contournement de la foule par le robot, pour qu'il puisse atteindre de manière autonome un but très proche. En situation concrète, on aimerait que le pilote puisse dire "avance d'un mètre" pour par exemple se rapprocher d'un tableau, et que le robot s'arrange tout seul pour parcourir ce mètre (sans que le pilote ait besoin de lui répéter d'avancer jusqu'à qu'il ait fini son déplacement).

En plus d'être plus agréable pour le pilote, cette seconde étape permettra de passer facilement une liste de commandes simples au module d'évitement de foule, dans le cadre du pilotage automatique, sans avoir à surveiller leur bonne réalisation.

La notion de "point très proche" rassemble plusieurs critères :

  • l'objectif à atteindre doit être assez proche de la Kinect, dans la zone où elle peut détecter les squelettes des obstacles humains
  • l'objectif doit être atteignable par le robot s'il n'y avait pas de personnes dans la pièce (c'est-à-dire que seuls les humains constituent des obstacles). On peut ainsi se concentrer sur la gestion de la foule. Les problèmes de contournement de murs seront gérés dans le mode pilotage automatique.

Algorithme en pseudo-code

1 B := ensemble de points très proches à atteindre
2 tant que B non vide faire
3   P := position actuelle du robot
4   M := carte locale /* Contient au moins tous les obstacles fixes (SLAM),
5                        le point P et le point B */
6   tant que P != B faire
7      mettre à jour M avec les positions des personnes présentes
8      trouver dans M un chemin de P à B
9      LI := liste des instructions de pilotage de ce chemin
10     tant que la voie est libre en direction de première(LI) faire
11        effectuer première(LI)
12        pop(LI)
13     fin faire
14     P := position actuelle du robot
15  fin faire
16 fin tant que

L'algorithme termine-t-il ?

  • Problème 1 : Si le robot est entouré de personnes immobiles, non. Dans ce cas, il lui serait impossible de trouver un chemin de P à B dans M.
    • Solution 1 : attendre que la foule bouge et libère un chemin.
    •       trouver dans M un chemin de P à B
      

      devient

            tant que il n'existe pas de chemin de P à B dans M faire
               attendre un peu
               mettre à jour M avec les positions des personnes présentes
            fin faire
            trouver dans M un chemin de P à B
      
    • Solution 2 : demander aux personnes l'entourant de bouger. Il suffirait d'activer la synthèse vocale et d'émettre un "pardon, excusez-moi".
    •       tant que il n'existe pas de chemin de P à B dans M faire
               dire "excusez-moi, je voudrais passer"
               attendre un peu
               mettre à jour M avec les positions des personnes présentes
            fin faire
            trouver dans M un chemin de P à B
      
  • Problème 2 : L'algorithme peut aussi échouer si les personnes bougent et libèrent des chemins, mais les bloquent de nouveau ensuite. Par exemple, lorsque deux personnes se croisent dans la rue, et que les deux essayent de se croiser par le même côté. Alors les deux personnes changent de côté, et rebelote, ça ne passe pas. Dans le cas de notre robot, une situation similaire conduirait à une boucle infinie. Dans ce cas, le robot serait coincé dans la boucle tant que P != B faire.... À chaque tour, il trouverait bien un chemin à suivre, mais il serait systématiquement bloqué à un moment de son chemin, avant d'atteindre B.
    • Solution possible 1 : on pourrait imposer aux chemins de n'emmener le robot que dans des positions de plus en plus proches de B. En effet, l'algorithme simple ne contraint pas le chemin lui permettant d'atteindre B. En pratique, c'est normal de ne pas le contraindre : il arrive souvent que dans un musée bondé, pour atteindre une oeuvre proche, il faille d'abord s'en éloigner en contournant la foule. Finalement, en empêchant le robot de s'éloigner de sa cible, on garantit qu'il l'atteindra un jour, mais on risque aussi de tomber dans une situation où seule une manoeuvre d'éloignement permettrait d'avancer.
    • Solution possible 2 : on pourrait aussi jouer sur le comportement des humains qui entourent le robot, sans pour autant les apostropher en permanence à coups de synthèse vocale. Il suffirait que le robot indique clairement sa direction à son entourage, par exemple en montrant une volonté de s'y rendre. C'est-à-dire : quand on voit quelqu'un qui avance clairement dans une direction, on évite par automatisme de se mettre devant lui. Pris dans le sens inverse, ça voudrait dire qu'un robot qui n'avance pas dans une direction claire aura plus de chance de se faire "passer devant" et donc bloquer par les personnes qui l'entourent. TODO : Je ne sais pas à quel point cet argument est valide, il faudrait trouver une étude là dessus ou faire des essais.

Troisième étape : amélioration de l'autonomie

On vient de proposer un algorithme qui prend en compte les positions des personnes. On va maintenant voir si on pourrait utiliser leurs trajectoires. En effet, si deux humains marchent selon deux lignes sécantes et vont bientôt se croiser, alors il est courant qu'un des deux ralentisse ou accélère (même inconsciemment) pour éviter la collision. Dans le cas du robot, l'information "vont bientôt se croiser" correspond à la trajectoire et à la vitesse des personnes.

En effet, si on connaissait parfaitement les déplacements futurs de toutes les personnes présentes, le problème 2 (ci-dessus) serait résolu : il suffirait de prendre en compte une carte dynamique, avec les mouvements des personnes, lors du calcul du plus court chemin. Ça se fait, de tels algorithmes sont présentés dans la bibliographie plus loin.

Pour s'approcher de ce cas idéal, on pourrait utiliser les informations fournies en temps réel par la Kinect pour prédire la trajectoire des personnes en fonction de leur vitesse actuelle, et/ou de leur trajectoire passée.


Quatrième étape : Raffinement de l'algorithme

Analyse de l'algorithme ligne par ligne.

Calcul de l'ensemble B
A partir de la position courante P du robot, et de la destination D entrée par l'utilisateur, on calcule un plus court chemin sans tenir compte de la foule. Le plus court chemin est alors décomposé en positions "Checkpoints" Ci où pour tout i, [Ci, Ci+1] est fixée.
L'ensemble B est alors l'ensemble des Ci.


Calcul préliminaire de M
Nous réutilisons la carte fournie par l'équipe SLAM, en ajoutant la position courante du robot P, et le prochain checkpoint Ci.


Calcul de M avec position des personnes locales
Pour estimer la position des personnes présentes autour du robot, nous utilisons :

  • l'image de profondeur de la kinect, qui nous donne la distance entre le robot et la personne,
  • l'angle entre l'axe de vision de la Kinect et un point de repère de la personne.

Ainsi, à l'aide de fonctions trigonométriques, nous pouvons approximer sa position sur la carte M.
TODO: détailler l'algo.

Savoir si la voie est libre dans une direction donnée
Il suffit pour cela de regarder les données de la kinect car les obstacles fixes ont déjà été pris en compte dans le calcul du plus court chemin préliminaire.
En reprenant l'algorithme précédant dans le sens inverse, nous pouvons à partir d'une position, associer un pixel de l'image de la kinect, et ainsi tester si une personne se trouve à cette position.

Algorithmes du plus court chemin

Recherche documentaire

http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths
Contient plein de liens à propos de la recherche de plus courts chemins
http://theory.stanford.edu/~amitp/GameProgramming/
Du même auteur, une explication détaillée avec de nombreux exemples et graphiques des algorithmes de plus court chemin. D'abord prévu pour les jeux, mais applicable à la robotique. Contient des informations pertinentes sur les cartes qui évoluent dans le temps, les obstacles dont on connaît a trajectoire...
http://www.hessmer.org/blog/wp-content/uploads/2011/06/2d_Navigation_ROS.pdf
Pdf intéressant car traite de ROS et de l'implémentation (et certainement de qualité puisqu'il contient des liens vers ceux du dessus).

Modélisation de la carte pour le calcul

Choix d'un algorithme

Implémentation

Dépendances logicielles

Insertion dans l'architecture globale