3

IA Robot 2012

Astar_progress_animation

Ce post fait écho aux derniers articles présentés par Plativore et l’APBTeam sur leur blog respectif au sujet de la gestion des déplacements du robot et notamment du problème du pathfinding

Je vous invite d’ailleurs à lire en introduction de cet article leurs 2 articles sur leur mise en place du pathfinding (cf lien ci-dessus).

Pour notre robot de 2012, nous avons d’abord envisagé d’utiliser une technique de maillage du terrain pour mettre en place an alogrithme de pathfinding classique : un dikstra voir un astar. Les tests de performance de l’algorithme en .Net étaient très bon et permettaient même sur un maillage à 50×50 une résolution du chemin en moins de 500ms.

Le portage de ce code en micro framework nécessite quelques adaptations notamment du fait de l’absence des types « Génériques ». Cependant la plus grosse déception reste les piètres performance de cet algorithme sur notre carte une FEZ Panda II ayant quand meme un CPU à 72Mhz. Impossible de générer une trajectoire en dessous de la seconde même avec un maillage très faible : 5×5. De plus, les quelques 62Ko octets de mémoire disponible laisse peu de place pour un maillage très fin.

Par exemple, pour un maillage linéaire de case de 10x10cm, cela représente 30×20 cases soit 600 cases. En maintenant en permanence en mémoire le maillage, cela laisse peu d’espace mémoire pour le calcul à proprement parlé.

Il est à noter que ce maillage était uniquement là pour but de tester l’algorithme et qu’il n’est pas du tout optimisé. Il est beaucoup plus intéressant d’utiliser des maillages tenant compte de la particularité du terrain comme celui de plastivore.

Pour résoudre cette problèmatique de performance sans se tomber dans la simplicité qui consiste à mettre en place un chemin pré-établi que le robot ne ferait que suivre point après point, nous avons trouvé l’alternative suivante.

Cette idée part du principe que nous n’avions cette année que peu d’informations sur l’environnement extérieur à savoir :

  • la position de notre robot sur le terrain
  • les actions de jeu déjà réalisées par notre robot
  • la détection d’une robot devant ou derrière nous
et des postulats suivants :
  • le plateau de jeu étant très encombré les manoeuvres d’évitement / contournement sont difficiles
  • le risque de rester coincer par un robot sur notre trajectoire est assez important
  • le nombre de trajectoire (au sens de successions de points par lesquels passent le robot) possible sur le terrain est faible. par exemple pour aller du haut du plateau à une bouteille il faut forcément passer par un des deux cotés des totems et de préférence du notre pour éviter de croiser l’adversaire.
L’ensemble de ces postulats nous a inciter à mettre en place un découpage du plateau en 14 grandes cases. Pour chaque case du plateau nous avons réfléchi aux différentes trajectoires que le robot devrait employer si il se trouvait sur cette case et avons implémenté tout cela dans le robot.
Au final on obtiens un trentaine de trajectoire chacune rattachée à une case bien précise. Par exemple, la photo ci-contre montre l’exemple d’une des trajectoire de la case 10 qui consiste à aller ramasser l’ensemble des CDs le long des totems. La présence de rond pour entrecouper les trajectoire symbolisaient des pauses pour ouvrir et fermer nos mâchoires. Si le robot ne rencontre pas d’obstacle, le robot doit terminer sa trajectoire en case 2. A ce moment il regardera quelle est la prochaine trajectoire de la case 2 non réalisée et tentera de la faire. Si toutes les trajectoires d’une case sont déjà réalisées, on recommence la premiere trajectoire de la case.
Si a un instant T le robot rencontre un obstacle, il s’arrête et choisit la prochaine trajectoire qui correspond à la case ou il se trouve à cet instant. Pour le bon succès de cette technique, il est important de penser à créer pour chaque case des trajectoires qui permettent de sortir de la case par différent côté pour parer à toutes les éventualités.
Les avantages de cette méthode :
  • Chaque trajectoire étant pré-codée, il n’y a aucune chance de percutée aucun élément de jeu ni un bord
  • L’enchaînement des différents points est facilement reproductible est permet donc de finement adapter une trajectoire
  • Dès qu’il rencontre un robot adverse (faut-il déjà qu’il arrive à le détecter mais passons…) le robot part sur une trajectoire différente sans perte de temps en contournement délicat dans une aire de jeux exiguë.
  • Algorithme très simple à mettre en place et très facile à débugger car très prévisible. les trajectoires s’enchaînent de manière très reproductible et on peut les tester facilement toutes les unes après les autres.
  • Le robot réessaye de lui même plusieurs fois les mêmes objectifs. Comme on ne sait jamais si on a réussi ou non un objectif le robot réessaye naturellement plusieurs fois le même si il a déjà tout essayé sur une case. En poussant un peu on pourrait se dire que le robot pourrait rentrer dans une boucle sans fin sur le même objectif mais si les trajectoires prévoient des chemins de fuite de tous les cotés pas de souci.
  • Temps de calcul CPU quasi nul car c’est entièrement pré-calculé.
  • Il suffit d’utiliser une symétrie pour créer les trajectoires quand on démarre de l’autre côté.
  • Possibilité de modéré certaines trajectoire en rajoutant des objectifs prioritaires. Ces objectifs prioritaires ne peuvent pas être shunté au moindre obstacle. Notre robot patientait un peu sur ce genre d’objectif pour essayer de l’atteindre.
Les inconvénients :
  • Le robot reste très prévisible contre une équipe qui étudierait un peu nos déplacement….
  • Le robot n’est pas persévérant est change d’objectif au moindre obstacle. Notez que c’est aussi tout l’objectif du truc !!!
  • Dans le cas où les obstacles et/ou les objectifs ne seraient pas si statiques que cette année le déterminisme des trajectoires serait à tempérer.
  • Un astar avec un beau maillage ça reste la classe.

Notre retour d’expérience suite à l’utilisation de cette technique est très bonne. L’ajout/ modification / suppression de trajectoire est très aisé et nous a permis de le faire pendant la coupe entre chaque match. De plus, le développement d’un petit programme nous permettait de créer des trajectoires à la souris sur une fenêtre représentant l’aire de jeux.

Si vous avez des retours ou des questions, n’hésitez pas.

Pour info, voici ci-dessous un petit extrait du code d’une trajectoire, le code complet est sur notre codeplex.

#region Case 1
matrajlist = new ListeDeTrajectoire();
q = new Queue();
q.Enqueue(new Position(1650, 660, false,true));
q.Enqueue(new Actionneurs.MouvementMachoire(Robot.Machoires.LocalisationMachoire.Gauche, Robot.Machoires.EtatMachoire.Ouverte, true));
q.Enqueue(new Position(1403, 660, true,true));
q.Enqueue(new Position(960, 660, true,true));
q.Enqueue(new Position(300, 900, true,true));
q.Enqueue(new Position(680, 900, false));
q.Enqueue(new Actionneurs.MouvementMachoire(Robot.Machoires.LocalisationMachoire.LesDeux, Robot.Machoires.EtatMachoire.Fermee, false));
matrajlist.Add(new Trajectoire(q));

q = new Queue();
q.Enqueue(new Position(1947, 523, false));
q.Enqueue(new Position(2330, 685, false));
q.Enqueue(new Actionneurs.MouvementMachoire(Robot.Machoires.LocalisationMachoire.Gauche, Robot.Machoires.EtatMachoire.Ouverte, true));
q.Enqueue(new Position(1911, 725, true));
q.Enqueue(new Actionneurs.MouvementMachoire(Robot.Machoires.LocalisationMachoire.Gauche, Robot.Machoires.EtatMachoire.Milieu,true));
q.Enqueue(new Position(1267, 725, true));
q.Enqueue(new Actionneurs.MouvementMachoire(Robot.Machoires.LocalisationMachoire.Gauche, Robot.Machoires.EtatMachoire.Ouverte, true));
q.Enqueue(new Position(1043, 725, true));
q.Enqueue(new Actionneurs.MouvementMachoire(Robot.Machoires.LocalisationMachoire.Gauche, Robot.Machoires.EtatMachoire.Milieu, true));
q.Enqueue(new Position(420, 725, true));
q.Enqueue(new Position(600, 725, false));
q.Enqueue(new Actionneurs.MouvementMachoire(Robot.Machoires.LocalisationMachoire.LesDeux, Robot.Machoires.EtatMachoire.Fermee, false));
matrajlist.Add(new Trajectoire(q));
AireDeJeu.ListDesCases.Add(new CaseDeJeu(0, 0, 447, 500, 1, matrajlist));
#endregion
  1. samir ammarcha dit :

    bonjours
    vous avez fait un découpage du plateau en 14 grandes cases
    et pré programmer des action a fair pour le robot selon chaque case suivant un scénario ..
    ma question est comment votre robot sait il ou il ce trouve ? ( comment il s’est dans quelle case il trouve ?
    je suis un amateur d’électronique
    jais commander une carte arduino
    et je suis a stade 0 (allumage des leds , commande moteur en pwm …)
    j’aiemerai bien un jour peut etre arriver a réaliser un petit robot
    mercie pour votre aide
    et bon courage

  2. Pacman dit :

    Salut,

    Désolé pour le temps de réponse mais je reviens juste de vacances. Pour notre robot on se sert de linformation données par des codeurs pour connaître notre position.
    Ta carte arduino te permettra de commencer quelques tours de roues. Et en y allant pas à pas tu pourras te déplacer puis corriger tes déplacements en t aidant de roues codeuses.

    Si tu veux plus d infos n hesite pas a poser des questions ou venir faire un tour surle forum de planète science dans la section robotique. Tu trouveras plein de monde pour répondre à tes questions.