Algorithme A*

In [ ]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib

Le problème

La figure ci-dessous représente une scène d'un jeu vidéo où ont été placés des obstacles. Le personnage en haut à gauche doit se rendre au point cible situé en bas à droite. Le chemin dessiné en vert est un chemin de longueur minimale qui relie le personnage à la cible. L'objectif du TP est de calculer un tel chemin en implémentant l'algorithme $A^*$.

In [ ]:
pixels = plt.imread("scene-1.png")
plt.imshow(pixels, interpolation='none')
Out[ ]:
<matplotlib.image.AxesImage at 0x7f96306564e0>

Génération d'une scène aléatoire

Une scène est représentée par un tableau numpy 2D world contenant des valeurs 0 ou 1. Un obstacle occupe la position $z$ si et seulement si world[z] == 1.

La fonction ci-dessous vous permettra de représenter une scène.

In [ ]:
def display_world(world, path=None):
    """ Représente la scène world ainsi que l'éventuel chemin path.
    """
    width, height = world.shape
    pixels = 255 * np.ones((width, height, 3), dtype=np.uint8)
    pixels[world == 1] = np.array([0, 0, 0])
    if path is not None:
        start, target = path[0], path[-1]
        pixels[start] = np.array([0, 0, 255])
        for z in path[1:-1]:
            pixels[z] = np.array([0, 255, 0])
        pixels[target] = np.array([255, 0, 0])
    figsize(10, 10)
    pixels = np.swapaxes(pixels, 0, 1)
    plt.imshow(pixels, interpolation='none')
    plt.show()

Question 1

Écrire le code de la fonction gen_world.

In [ ]:
def gen_world(width, height, n, size):
    """ Retourne une scène de dimensions (width, height).
        La scène contient n obstacles rectangulaires générés aléatoirement.
        Les dimensions des obstacles ne dépassent pas size.
    """
    #### À COMPLÉTER

world = gen_world(100, 50, n=80, size=10)
display_world(world)

Description de l'algorithme $A^*$

Dans la suite du texte la longueur d'un chemin est aussi appelé son coût.

On définit pour chaque case $z$ :

  • $g(z)$, le coût exact du meilleur chemin découvert jusqu'ici pour aller du point de départ start jusqu'à $z$.
  • $h(z)$, le coût estimé du meilleur chemin pour aller de $z$ à la cible target.
  • $f(z)=g(z)+h(z)$.

L'algorithme $A^*$ explore les cases en étudiant à chaque itération la case qui minimise la valeur $f(z)$. Le déroulement de l'algorithme dépend de la fonction d'estimation $h$. Cette fonction est appelée une heuristique.

L'algorithme tient à jour deux ensembles de cases. L'ensemble OPEN contient les cases candidates pour être étudiées. Initialement, l'ensemble OPEN contient un seul élément : la case de départ start. L'ensemble CLOSED contient les cases qui ont déjà été étudiées. Initialement, l'ensemble CLOSED est vide. Graphiquement, l'ensemble OPEN est la frontière et l'ensemble CLOSED est l'intérieur de l'ensemble des cases visitées. La parente de chaque case est également mémorisée. Il s'agit de la case qui permet de reconstruire le chemin solution.

La boucle principale de l'algorithme consiste à étudier la case $z$ de OPEN pour laquelle $f(z)$ est minimal. Si $z$ est la cible target alors l'algorithme est terminé. Sinon, la case $z$ est supprimée de OPEN et ajoutée à CLOSED. On considère alors chacune de ses voisines. Les voisines qui sont dans l'ensemble CLOSED ont déjà été étudiées et sont par conséquent ignorées. Les voisines qui ne sont pas déjà ouvertes sont ajoutées à l'ensemble OPEN et leurs parentes sont définies comme étant $z$. Si une voisine de $z$ est déjà ouverte on regarde si le chemin venant de $z$ est meilleur que celui déjà mémorisé. Si c'est le cas, $z$ est défini comme étant la case parente de cette voisine.

Lorsque la boucle est terminée, c'est-à-dire lorsque l'ensemble OPEN est vide, il suffit de suivre les cases parentes depuis target jusqu'à start pour construire le chemin solution.

Vous trouverez ici une animation interactive de l'algorithme $A^*$ : https://qiao.github.io/PathFinding.js/visual/

L'heuristique

Question 2

On choisit une fonction heuristique $h$ telle que, pour toute case $z$, $h(z)$ est inférieure ou égale au coût de tout chemin allant de $z$ à target. Montrer que sous cette hypothèse, la solution fournie par l'algorithme $A^*$ est un chemin de coût minimal.

Question 3

Supposons que pour toute case $z$, $h(z)$ soit égale au coût minimal des chemins allant de $z$ à $t$. Comment se déroule l'algorithme dans ce cas ?

Question 4

Si on choisit $h(z)=0$ pour tout $z$, on obtient alors un algorithme classique. Quel est le nom de cet algorithme ?

Question 5

Proposer une fonction heuristic(z1, z2) qui retourne une estimation du coût pour aller de la case $z_1$ à la case $z_2$.

Cette fonction ne doit pas sur-estimer le coût minimal.

In [ ]:
def heuristic(z1, z2):
    """ Retourne une estimation de la distance entre z1 et z2.      
    """
    ### À COMPLÉTER

Question 6

À chaque itération, l'algorithme sélectionne dans l'ensemble OPEN la case qui minimise la valeur $f(z)$. Pour que cette étape de l'algorithme soit efficace il est judicieux de choisir une structure de donnée adaptée. Quelle structure de donnée proposez-vous ? Quelles sont les primitives d'accès à cette structure de données ? Précisez la complexité en temps de ces primitives.

On ne vous demande pas d'écrire une implémentation de cette structure. En recherchant sur l'internet vous trouverez un module Python que implémente cette structure.

Implémentation de l'algorithme

Question 7

Écrire le code de la fonction get_path.

parent est un tableau Numpy 2D qui donne la case parente de chacune des cases visitées.

In [ ]:
def get_path(start, target, parent):
    """ Construit et retourne le chemin solution.
    """
    ### À COMPLÉTER

Question 8

Écrire le code de la fonction neighbors.

In [ ]:
def neighbors(world, z):
    """ Retourne la liste des cases voisines de z.
    
        Les cases occupées par un obstacle ne sont pas considérées comme des voisines.
    """
    ### À COMPLÉTER

world = np.zeros((3, 3), dtype=int)
world[0, 0] = 1
print(neighbors(world, (1, 1)))
print(neighbors(world, (2, 2)))

Question 9

Écrire la fonction find_path(world, start, target) qui retourne un chemin de distance minimale dans world allant de start à target.

Introduire autant de fonctions auxilliaires que nécessaire, afin de produire un code lisible et facilement débogable.

In [ ]:
 

Question 10

Tester la fonction find_path.

In [ ]: