Automates à états finis
Un article de Wikibot.
Automate à états finis ou FSM (acronyme de Finite State Machine)
Le concept de cette approche est de décomposer le comportement du système en états discernables et surtout en nombre fini d'états. A partir de chaque état il est alors possible d'effectuer une transition vers un autre état (ce qui rappelle le fonctionnement des chaînes de Markov). Il est donc nécessaire de déterminer les conditions de transitions (définissant ainsi les arcs dans un graphe d'états). Ces conditions de transition d'états peuvent dépendre de paramètres déterministes ou aléatoires, cependant ils doivent tous être accessibles depuis l'état en cours.
L'exemple rudimentaire suivant permettra à chacun de mieux cerner le concept.
[modifier] Exemple du chat
Le chat peut effectuer 4 activités distinctes :
- dormir.
- manger.
- jouer.
- marcher.
On aura donc 4 états distincts
Le chat dispose aussi d'indicateurs simples que sont :
- fatigue 0:100
- faim 0:100
Chaque transition peut être probabiliste ou déterministe, et point important la transition ne doit faire appel qu'aux variables (ou à la description) de l'état en cours. En continuant l'exemple précédant on peut définir les transitions suivantes : Dormir -> Manger si fatigue < faim Dormir -> Jouer si fatigue < 25 et faim < 25 et aléatoire 1/10 Dormir -> Marcher si fatigue < 25 et faim < 25 et aléatoire 9/10
Manger -> Dormir si faim < 25 et fatigue > 50
Jouer -> Marcher si fatigue > 40 Jouer -> Manger si faim > 50
Bien entendu il faut veiller à former un graphe parcourable entièrement (sinon certains états ne sont jamais visités )
La programmation de ce type de comportement peut se faire en C++ en réalisant une classe abstraite Chat qui est ensuite dérivée en ChatJouant, ChatDormant ... chaque classe dérivée implémentant les conditions de transitions et bien sûr la modification des paramètres du chat avec le temps.
L'exemple du chat se transpose facilement à d'autres types d'automates à états finis, en particulier la gestion de plusieurs automates, dans la philosophie multi-agents peut se faire grâce à un système de communication de type pipeline.
