Espace d'état (informatique)

En informatique , un espace d'état est un espace discret représentant l'ensemble de toutes les configurations possibles d'un « système ». C'est une abstraction utile pour raisonner sur le comportement d'un système donné et est largement utilisée dans les domaines de l'intelligence artificielle et de la théorie des jeux .

Par exemple, le problème du jouet « Le monde du vide » a un espace d'états finis discret dans lequel il existe un ensemble limité de configurations dans lesquelles le vide et la saleté peuvent se trouver. Un système « compteur », où les états sont des nombres naturels commençant à 1 et sont incrémentés au fil du temps a un espace d'états discret infini. La position angulaire d'un pendule non amorti est un espace d'états continu (et donc infini).

Les espaces d'états sont utiles en informatique comme modèle simple de machines. Formellement, un espace d'états peut être défini comme un tuple [ N , A , S , G ] où :

• N est un ensemble d'états
• A est un ensemble d'arcs reliant les états
• S est un sous-ensemble non vide de N qui contient les états de départ
• G est un sous-ensemble non vide de N qui contient les états objectifs.

Un espace d'état a certaines propriétés communes :

• complexité, où le facteur de ramification est important
• structure de l'espace, voir aussi théorie des graphes :
  • directionnalité des arcs
  • arbre
  • graphe enraciné

Par exemple, le monde de l'aspirateur a un facteur de ramification de 4, car l'aspirateur peut se retrouver dans l'une des 4 cases adjacentes après s'être déplacé (en supposant qu'il ne puisse pas rester dans la même case ni se déplacer en diagonale). Les arcs du monde de l'aspirateur sont bidirectionnels, car n'importe quelle case peut être atteinte à partir de n'importe quelle case adjacente, et l'espace d'état n'est pas un arbre puisqu'il est possible d'entrer dans une boucle en se déplaçant entre 4 cases adjacentes.

Les espaces d’états peuvent être infinis ou finis, discrets ou continus.

La taille de l'espace d'état pour un système donné est le nombre de configurations possibles de l'espace.

Si la taille de l'espace d'état est finie, le calcul de la taille de l'espace d'état est un problème combinatoire . Par exemple, dans le puzzle des huit reines , l'espace d'état peut être calculé en comptant toutes les manières possibles de placer 8 pièces sur un échiquier 8x8. Cela revient à choisir 8 positions sans remise dans un ensemble de 64, ou

Ce nombre est nettement supérieur au nombre de configurations légales des reines, soit 92. Dans de nombreux jeux, l'espace d'état effectif est petit par rapport à tous les états atteignables/légaux. Cette propriété est également observée aux échecs , où l'espace d'état effectif est l'ensemble des positions qui peuvent être atteintes par des mouvements légaux. C'est bien plus petit que l'ensemble des positions qui peuvent être obtenues en plaçant des combinaisons des pièces d'échecs disponibles directement sur l'échiquier.

Tous les espaces d'état continus peuvent être décrits par une fonction continue correspondante et sont donc infinis. Les espaces d'état discrets peuvent également avoir une taille ( dénombrable ) infinie, comme l'espace d'état du système de « compteur » dépendant du temps, similaire au système de la théorie des files d'attente définissant le nombre de clients dans une file, qui aurait un espace d'état {0, 1, 2, 3, ...}.

L'exploration d'un espace d'états est le processus d'énumération des états possibles à la recherche d'un état final. L'espace d'états de Pacman , par exemple, contient un état final chaque fois que toutes les boulettes de nourriture ont été mangées, et est exploré en déplaçant Pacman sur le plateau.

Un état de recherche est une représentation compressée d'un état du monde dans un espace d'états et est utilisé pour l'exploration. Les états de recherche sont utilisés car un espace d'états code souvent plus d'informations que nécessaire pour explorer l'espace. La compression de chaque état du monde pour n'inclure que les informations nécessaires à l'exploration améliore l'efficacité en réduisant le nombre d'états dans la recherche. Par exemple, un état dans l'espace Pacman comprend des informations sur la direction vers laquelle Pacman fait face (vers le haut, vers le bas, vers la gauche ou vers la droite). Comme il ne coûte rien de changer de direction dans Pacman, les états de recherche pour Pacman n'incluraient pas ces informations et réduiraient la taille de l'espace de recherche d'un facteur 4, un pour chaque direction vers laquelle Pacman pourrait faire face.

Les algorithmes de recherche standard sont efficaces pour explorer les espaces d'états discrets. Les algorithmes suivants présentent à la fois une complétude et une optimalité dans la recherche d'un espace d'états.

• Recherche en largeur
• A* Recherche
• Recherche de coût uniforme

Ces méthodes ne s'étendent pas naturellement à l'exploration d'espaces d'états continus. L'exploration d'un espace d'états continus à la recherche d'un état objectif donné équivaut à optimiser une fonction continue arbitraire , ce qui n'est pas toujours possible, voir optimisation mathématique .