PROFDINFO.COM

Votre enseignant d'informatique en ligne


Discussion sur la programmation du cerveau de Deimos

Introduction

Le cerveau de Deimos a accès aux informations suivantes:

En fonction de ces informations, le cerveau de Deimos doit choisir parmi les quatre actions suivantes:

  1. Avancer
  2. Tourner à gauche sur place
  3. Tourner à droite sur place
  4. Arrêter

Réglons tout de suite les cas les plus faciles. Dans le cas où un manque d'informations empêche Deimos de prendre une décision (par exemple, la position de Deimos est inconnue, ou la position à atteindre est inconneu) ou si l'état de Deimos doit être à arrêt, alors Deimos doit s'arrêter.

Pour les autres cas, il faut que Deimos calcule un chemin à suivre pour éviter les obstacles. Un chemin est une suite de positions intermédiaires que Deimos doit franchir pour atteindre la destination finale. Pour fins de simplifications, je vous suggère de choisir les positions intermédiaires parmi la listes des sommets des obstacles. Il vous faut cependant vous assurer que les descriptions des obstacles inscrites dans la base de données sont plus larges que les obstacles réels pour éviter que Deimos ne s'y frappe. Ceci est une condition nécessaire au bon fonctionnement des algorithmes présentés ici.

Établir la liste des voisins

Dans un premier temps, il faut déterminer si Deimos peut se déplacer d'un noeud à l'autre sans embûche. Pour simplifier les explications, nous allons nommer des noeuds les sommets des obstacles, la position actuelle de Deimos et la destination finale. Pour chaque noeud, il faut établir la liste des voisins de ce noeud. Un noeud est voisin d'un autre noeud si le segment de droite formé par un noeud et son voisin n'intersecte pas une arête d'un obstacle. Voici le pseudo-code d'un algorithme qui détermine si deux segments de droites s'intersectent:

// Le premier segment de droite est donné par les points (x1,y1) et (x2,y2) 
// et le deuxième segment de droite est donné par (x3,y3) et (x4,y4)
dx12 = x2 - x1
dy12 = y2 - y1
dx34 = x4 - x3
dy34 = y4 - y3

Si dx34 * dy12 - dy34 * dx12 = 0 Alors 
   // Les droites sont parallèles!
   Intersection = FAUX
Sinon
   s = (dx12 * (y3 - y1) + dy12 * (x1 - x3)) / (dx34 * dy12 - dy34 * dx12)
   t = (dx34 * (y1 - y3) + dy34 * (x3 - x1)) / (dy34 * dx12 - dx34 * dy12)
   Si s>0 et s<1 et t>0 et t<1 Alors
      // Intersection à  x = x1 + t * dx12 et y = y1 + t * dy12
      Intersection = VRAI
   Sinon
      Intersection = FAUX

Algorithme du plus court chemin

Maintenant que nous avons une liste de noeuds et que pour chacun des noeuds nous avons la liste de ses voisins, nous somme en présence d'un réseau et il faut alors déterminer le plus court chemin à travers ce réseau pour passer du noeud initial (la position courante de Deimos) au noeud final (la position finale). La théorie des graphes nous apporte plusieurs solutions à ce problème typique. Je vous propose d'utiliser ici l'algorithme A* qui est une approximation (plus rapide mais pas nécessairement optimale) du célèbrissime algorithme de Edsger Dijkstra. Voici le pseudo-code de l'algorithme A* appliqué à Deimos:

  
// OPEN : liste des nœuds à traiter 
// CLOSED : liste des nœuds traités
// N : nombre de nœuds
// h(i) : distance à vol d'oiseau du nœud i au nœud final 
//        (pour i allant de 1 à N)
//        Ces distances peuvent être pré-calculées
// g(i) : distance cumulée du nœud i au nœud initial 
//        (pour i allant de 1 à N)
//        Le vecteur doit être initialisé à 0
// f(i) : somme des distances h(i) et g(i)
//        Le vecteur doit être initialisé à 0
// parent(i) : parent d'un nœud i (parent(x) donne la
//        position dans parent() du nœud précédant x))   

Initialiser la liste OPEN à vide
Initialiser la liste CLOSED à vide
Ajouter le noeud initial à la liste OPEN

Tant que la liste OPEN n'est pas vide
   Retirer le nœud n de la liste OPEN qui a le f(n) le plus petit
   Si n est le noeud final 
      Un solution a été trouvé  
      FIN
   Sinon 
      Ajouter n à CLOSED
      Pour chaque voisin n' du nœud n
         G = g(n) + la distance de n à n'
         F = G + h(n') 
         Si n' se trouve déjà dans OPEN avec un f(n') < F 
            Passer au noeud n' suivant
         Si n' se trouve déjà dans CLOSED avec un f(n') < F 
            Passer au noeud n' suivant
         parent(n') = n
         g(n') = G 
         f(n') = F 
         Retirer n' des deux listes OPEN et CLOSED
         Ajouter n' à la liste OPEN

Si une solution est trouvée, le meilleur chemin est déterminé en partant du noeud final puis en remontant jusqu'au noeud initial à l'aide du vecteur de parents parent(i).

Deimos n'a plus alors qu'à se diriger vers la position finale en passant par chacun des positions intermédiaire. On détermine qu'une position intermédiaire (ou la position finale!) est atteinte lorsque la distance entre la position actuelle de Deimos et la position à atteindre est plus petite qu'une certain marge d'erreur acceptable appelée Epsilon:

sqrt ( dx*dx + dy*dy ) < Epsilon

Cet Epsilon sera déterminé par expérimentation mais doit nécessairement être plus grand que la précision de la position calculée par le module de vision.

Déterminer l'action à prendre

Pour envoyer des commandes à Deimos pour atteindre un position intermédiaire, il faut dans un premier temps calculer:

dx = Xintermédiaire - Xactuel
dy = Yintermédiaire - Yactuel

L'angle à donner à Deimos pour faire face à la prochaine position à atteindre est :

AngleSouhaité  = atan2f(dy, dx) //  varie entre -pi à pi

Si la différence entre l'angle souhaité et l'angle actuel de Deimos (donné par le module de vision) est inférieure à une marge acceptable, on peut alors faire avancer Deimos:

Si fabs (AngleSouhaité - AngleActuel) < Epsilon Alors
   Avancer
Sinon
   Si AngleSouhaité > AngleActuel Alors
      Tourner à gauche sur place 
   Sinon
      Tourner à droite sur place 

ATTENTION: cet algorithme se doit d'être peaufiné pour tenir compte de la façon dont le module de vision calcule son angle et peut être optimisé pour éviter de faire tourner Deimos sur plus de 180°. À suivre...

Conclusion: l'adaptabilité de Deimos

Le cerveau de Deimos doit effectuer dans l'ordre les étapes suivantes:

  1. Obtenir la liste des obstacles de la base de données, la position la plus récente de Deimos et la position à atteindre.
  2. Calculer les points intermédiaires (le plus court chemin).
  3. Déterminer le prochain point intermédiaire à atteindre.
  4. Déterminer l'action à prendre en fonction de la position actuelle de Deimos et du prochain point intermédiaire à atteindre.

Le cerveau de Deimos peut commencer par les étapes 1 et 2 puis boucler sur les étapes 3 et 4. Cette façon de faire a pour avantage de concentrer les calculs avant même que Deimos ne démarre puis, une fois parti, le cerveau ne fait presque plus rien sinon que de suivre la route préétablie. Cette solution, quoique valable dans le contexte d'un projet d'intégration, souffre d'adaptablité. Effectivement, si les obstacles se déplacent en cours de route, Deimos n'en saura rien.

Si vous désirez rendre votre Deimos plus adapté à son environnement changeant (et donc plus intelligent) il vous suffit de boucler sur les étapes 1,2,3 et 4. Dans ce cas, le prochain point intermédiaire à atteindre sera toujours le noeud suivant le noeud initial. De plus, il faut veiller à nettoyer proprement vos vecteurs et vos listes de noeuds pour éviter les fuites de mémoire et les problèmes d'initialisation.