Recherche dans un espace d'états


Soit un système évolutif dans son état actuel.

Supposons connaître les différentes actions pouvant être effectuées à partir de cet état, et pouvoir déterminer le nouvel état du système. Et ainsi de suite...

Par exemple, évolution d'une machine en utilisant les différentes commandes d'un tableau de bord, ou évolution dans un jeu en se déplaçant ou en effectuant telle ou telle action.

Comment trouver la suite d'action permettant d'atteindre un état "acceptable" (connu à l'avance, ou évalué comme tel au fur et à mesure de la recherche) ?

Si chaque action a un coût, comment le faire avec le coût cumulé (global) le plus faible possible ?


Partant du principe qu'un système peut engendrer un nombre très important d'états (voire même un nombre illimité), considérant également que l'ensemble des états et les actions menant de l'un à l'autre n'est pas connu à l'avance (même si c'est le cas, cela peut vite devenir impossible à prendre en compte d'un point de vue opérationnel), les techniques de recherche de chemin optimum abordées par ailleurs sur MOMIrandum ne peuvent pas être utilisées.


Nous voyons d'abord, de façon générale, comment un tel problème est formalisé / modélisé à l'aide d'un "espace d'états" représenté (partiellement) sous la forme d'un graphe construit au fur et à mesure de la recherche, et nous parlons d'arborescence des chemins menant à chacun des états découverts.


Nous définissons tout d'abord un algorithme générique de recherche, qui est ensuite "adapté" pour satisfaire différentes stratégies de recherche, incluant ou non une notion de coût, avec ou sans utilisation de connaissance spécifique 'heuristique'.

Parmi les algorithmes abordés, nous trouvons bien entendu A*.


Les différentes stratégies étudiées sont finalement comparées en terme de complétude et optimalité, ainsi que selon leur complexité en temps et en espace.