Encadreur : João Rendas, en collaboration avec le Prof. José Brazio de l'IST de Lisbonne, Portugal

Mots clefs : Planification de trajectoires, robotique mobile, planification probabiliste

Connaissances requises : Théorie des Probabilités, Chaines de Markov, optimisation

Travail antérieur

Nous avons proposé [1] une approche probabiliste à la planification des déplacements des robots équipés de capteurs de faible portée, qui n'ont pas d'accès à des informations sur leur position dans un repère global, et qui opèrent dans des milieux inconnus avec une faible densité d'objets. Un exemple paradigmatique du type de régions considérées est le milieu sous-marin : très mal connu, pas de mesures GPS, capteurs — sonar ou vision — myopiques.  Contrairement à ce qui se passe dans des environnements où la densité d'objets est grande (espaces industriels, bureaux, etc.), le plus grand risque dans ce type d'environnements est de perdre le robot.
L'approche proposée est basée sur la définition d'un graphe de planification, dont les noeuds représentent les objets détectés par le robot, et chaque arc indique la probabilité pour que le robot transite effectivement du noed origine au noed but de l'arc quand il reçoit cette ordre.

Ces probabilités résument l'impact de tous les facteurs intervenant dans la qualité du positionnement propre du robot (précision de ses capteurs, qualité du positionnement du robot par rapport à l'objet),  la confiance sur la position relative de l'objet de départ et l'objet but, la distance entre les deux objets, la taille de l'objet but. Leur calcul fait appel à des outils des théories de l'estimation paramétrique et des processus aléatoires [1].
En utilisant ce graphe, nous cherchons le trajet (chemin du noeud correspondant à l'objet d'origine à celui qui correspond à l'objet but) qui maximise la probabilité pour que le robot arrive effectivement  à son but (ou, d'une forme équivalente, qui minimise la probabilité pour que le robot se perde). Cette approche cherche donc un chemin unique qui devra être réalisé par le robot. L'ensemble de trajets optimaux entre tous les pairs de noeuds dans le graphe est alors sauvergardé dans une table d'acheminement, T_ij , qui indique le noeud O_n vers lequel le robot devra se diriger pour aller de O_i à O_j . Cette table peut être récursivement actualisée, au fur et mesure que le robot découvre de nouveaux objets.

Déscription du stage

L'objectif de ce stage est d'étudier l'extension de cette approche de façon à prendre en compte dans le choix du plan la possibilité que le robot se repositionne pendant son chemin et replanifie ses mouvements. Cette approche plus réaliste considère les probabilités pour que le robot arrive  à un objet différent de celui vers lequel il a été dirigé, et permet ainsi d'utiliser efficacement l'existence des clusters de petits objets. Dans cette approche on admet la possibilité que le robot s'éloigne du trajet pré-spécifié, détecte cet éloignement a travers de son arrivée à un autre object, et à ce moment corrige son plan. Dans ce cas, le planificateur ne cherche plus un chemin unique du noeud de départ au noeud d'arrivée, mais plutôt une arborescence dont la probabilité conjointe des différents chemins qui la composent soit élevée.

La figure précédente illustre un example : le chemin en gras est celui qui est exécuté avec une plus grande probabilité, mais la proximité d'un autre noeud est aussi exploitée, correspondant à un chemin alternatif qui augmente, globalement, la probabilité pour que le robot se déplace de l'objet de départ à l'objet d'arrivée.

Formalisation du problème

Ce problème peut se formaliser dans le cadre de la théorie des chaînes de Markov,  de la façon suivante.
Soient O₁,...,O_N, les objets détectés par le robot, et p_ij^k, i,j,k=1,...N, les probabilités pour que le robot passe de l'objet i à l'objet j quand il est dirigé vers l'objet k. Notons que, en général,  S_j=1..N p_ij^k< 1, car il peut se perdre en passant de O_i à O_k .

Nous définissons une chaîne de Markov controllée, dont l'espace d'états est

L'action prise dans l'état s_i (l'ensemble des actions possibles à partir d'un état est de se diriger vers un autre état - objet) détermine l'ensemble des probabilités de transition vers les autres états : les valeurs p_ij^k . Nous admettons, pour simplifier le problème, que le robot reconnaît toujours, sans ambiguité, l'objet où il se trouve.

Le problème à résoudre est le suivant : déterminer, pour chaque état s_i, l'action optimale pour conduire le robot dans n'importe quel autre état s_j . Le critère d'optimalité sera précisé plus tard.  On désignera génériquement par a(i,j) l'action prise dans l'état s_i pour aller à s_j. On appelle stratégie pour aller à O_j un ensemble d'actions  A^j= {a(i,j), i=1,...,j-1,j+1,N} — où chaque a(i,j)appartient  à {O₁, O₂, ....,O_i-1,O_i+1,...,O_N} . Chaque stratégie détermine une matrice de transitions de la chaîne de Markov, et donc le  vecteur de probabilités pour que le robot arrive éventuellement à  O_j  :

Ce type de problèmes est connu par le nom de Markov Decision Problems. Des algorithmes existent, qui permettent de déterminer la stratégie optimale pour ce type de problèmes. L'objectif du stage est de définir un algorithme itératif qui, au fur et mesure que le robot découvre des nouveaux objets (et ajoute donc des noeuds au graphe existant), détermine d'une façon efficace la nouvelle stratégie optimale.  Des relations avec des méthodes basés sur le regroupement d'états, ou sur la définition d'actions abstraites (elles mêmes des stratégies définies sur un sous-ensemble de l'espace d'états) seront exploitées.

L'efficacité du nouveau planificateur sera comparée à celui de la version existente sur des expériences réelles avec le mini-robot Khepera (voir page d'accueil).

Ce sujet de stage peut se poursuivre par une thèse dans le domaine de la planification des actions de robots mobiles sous conditions de forte incertitude.