Planification réactive

En intelligence artificielle, la planification réactive désigne un ensemble de techniques de sélection d’action par des agents autonomes. Ces techniques diffèrent de la planification classique par deux aspects. Premièrement, ils fonctionnent rapidement et peuvent donc faire face à des environnements hautement dynamiques et imprévisibles. Deuxièmement, ils calculent une seule action suivante à chaque instant, en fonction du contexte actuel. Les planificateurs réactifs exploitent souvent (mais pas toujours) des plans réactifs, qui sont des structures stockées décrivant les priorités et le comportement de l’agent.

Bien que le terme planification réactive remonte au moins à 1988, le terme « réactif » est maintenant devenu péjoratif, utilisé comme un antonyme de proactif. Étant donné que presque tous les agents utilisant la planification réactive sont proactifs, certains chercheurs ont commencé à parler de planification réactive comme de planification dynamique.

Représentation réactive du plan
Il y a plusieurs façons de représenter un plan réactif. Tous nécessitent une unité de représentation de base et un moyen de composer ces unités en plans.

Règles condition-action (productions)
Une règle d’action de condition, ou règle if-then, est une règle sous la forme: si condition, action. Ces règles s’appellent des productions. La signification de la règle est la suivante: si la condition est remplie, effectuez l’action. L’action peut être externe (par exemple, prendre quelque chose et la déplacer) ou interne (par exemple, écrire un fait dans la mémoire interne ou évaluer un nouvel ensemble de règles). Les conditions sont normalement booléennes et l’action peut être exécutée ou non.

Les règles de production peuvent être organisées dans des structures relativement plates, mais le plus souvent sont organisées dans une hiérarchie quelconque. Par exemple, l’architecture de sous-consommation consiste en couches de comportements interconnectés, chacun étant en réalité une machine à états finis qui agit en réponse à une entrée appropriée. Ces couches sont ensuite organisées en une simple pile, les couches les plus hautes englobant les objectifs des plus basses. D’autres systèmes peuvent utiliser des arbres ou inclure des mécanismes spéciaux pour changer le sous-ensemble d’objectifs / de règles le plus important à l’heure actuelle. Les structures plates sont relativement faciles à construire, mais ne permettent que la description d’un comportement simple, ou nécessitent des conditions extrêmement compliquées pour compenser le manque de structure.

Un mécanisme de résolution de conflit est un élément important de tout algorithme de sélection d’actions distribuées. Il s’agit d’un mécanisme permettant de résoudre les conflits entre les actions proposées lorsque la condition de plusieurs règles est vérifiée à un instant donné. Le conflit peut être résolu par exemple par

attribuer à l’avance des règles fixes aux règles,
attribution de préférences (par exemple dans l’architecture SOAR),
apprendre les utilitaires relatifs entre les règles (par exemple dans ACT-R),
exploiter une forme de planification.
Les systèmes experts utilisent souvent d’autres méthodes heuristiques plus simples, telles que la récence pour la sélection de règles, mais il est difficile de garantir un bon comportement dans un système de grande taille avec des approches simples.

La résolution des conflits n’est nécessaire que pour les règles qui veulent prendre des mesures qui s’excluent mutuellement (cf. Blumberg 1996).

Brom (2005) donne certaines limites à ce type de planification réactive.

Machines à états finis
La machine à états finis (FSM) est un modèle de comportement d’un système. Les FSM sont largement utilisés en informatique. Le comportement de modélisation des agents n’est qu’une des applications possibles. Un FSM typique, lorsqu’il est utilisé pour décrire le comportement d’un agent, consiste en un ensemble d’états et de transitions entre ces états. Les transitions sont en réalité des règles d’action conditionnelles. À chaque instant, un seul état du FSM est actif et ses transitions sont évaluées. Si une transition est prise, cela active un autre état. Cela signifie que, dans les transitions générales, les règles sont les suivantes: si condition, alors activer-nouvel-état. Mais les transitions peuvent également se connecter à l’état « self » dans certains systèmes, pour permettre l’exécution d’actions de transition sans changer réellement l’état.

Il existe deux manières de produire le comportement d’un FSM. Ils dépendent de ce qui est associé aux états par un concepteur – ils peuvent être des « actes » ou des scripts. Un ‘acte’ est une action atomique qui doit être effectuée par l’agent si son FSM est dans l’état donné. Cette action est alors effectuée à chaque pas de temps. Cependant, le plus souvent est le dernier cas. Ici, chaque état est associé à un script, qui décrit une séquence d’actions que l’agent doit effectuer si son FSM est dans un état donné. Si une transition active un nouvel état, l’ancien script est simplement interrompu et le nouveau est démarré.

Si un script est plus compliqué, il peut être divisé en plusieurs scripts et un FSM hiérarchique peut être exploité. Dans un tel automate, chaque état peut contenir des sous-états. Seuls les états au niveau atomique sont associés à un script (ce qui n’est pas compliqué) ou à une action atomique.

En termes de calcul, les FSM hiérarchiques sont équivalents aux FSM. Cela signifie que chaque FSM hiérarchique peut être converti en FSM classique. Cependant, les approches hiérarchiques facilitent mieux les conceptions. Voir le document de Damian Isla (2005) pour un exemple d’ASM de robots de jeux informatiques, qui utilise des FSM hiérarchiques.

Approches floues
Les règles if-then et les FSM peuvent être combinés avec une logique floue. Les conditions, états et actions ne sont plus respectivement booléens ou « oui / non » mais sont approximatifs et lisses. Par conséquent, le comportement obtenu va évoluer en douceur, en particulier dans le cas de transitions entre deux tâches. Cependant, l’évaluation des conditions floues est beaucoup plus lente que celle de leurs homologues croquants.

Voir l’architecture d’Alex Champandard.

Approches connexionnistes
Les plans réactifs peuvent également être exprimés par des réseaux connexionnistes tels que des réseaux de neurones artificiels ou des hiérarchies à flux libre. L’unité de représentation de base est une unité avec plusieurs liens d’entrée qui alimentent l’unité avec « une activité abstraite » et des liens de sortie qui propagent l’activité vers les unités suivantes. Chaque unité elle-même fonctionne comme un transducteur d’activité. En règle générale, les unités sont connectées dans une structure en couches.

Les points positifs des réseaux connexionnistes sont, premièrement, que le comportement obtenu est plus lisse que les comportements produits par des règles claires si-alors et des FSM, deuxièmement, les réseaux sont souvent adaptatifs, et troisièmement, le mécanisme d’inhibition peut être utilisé et donc également décrit de manière proscriptive (au moyen de règles, on ne peut décrire un comportement que de manière normative). Cependant, les méthodes ont aussi plusieurs défauts. Tout d’abord, pour un concepteur, il est beaucoup plus compliqué de décrire le comportement d’un réseau par rapport aux règles if-then. Deuxièmement, seul un comportement relativement simple peut être décrit, en particulier si la fonctionnalité adaptative doit être exploitée.

Algorithmes de planification réactifs
L’algorithme de planification réactif typique n’évalue que les règles if-then ou calcule l’état d’un réseau connexionniste. Cependant, certains algorithmes ont des caractéristiques spéciales.

Évaluation approfondie: avec une représentation logique appropriée (qui ne convient que pour des règles précises), les règles ne doivent pas être réévaluées à chaque étape. Au lieu de cela, une forme de cache stockant l’évaluation de l’étape précédente peut être utilisée.
Langages de script: Parfois, les règles ou les FSM sont directement les primitives d’une architecture (par exemple, dans Soar). Mais le plus souvent, les plans réactifs sont programmés dans un langage de script, où les règles ne sont que l’une des primitives (comme dans JAM ou ABL).
Pilotage
Le pilotage est une technique réactive spéciale utilisée dans la navigation des agents. La forme la plus simple de direction réactive est utilisée dans les véhicules Braitenberg, qui cartographient les entrées du capteur directement aux sorties des effecteurs, et peuvent suivre ou éviter. Les systèmes plus complexes reposent sur une superposition de forces attractives ou répulsives agissant sur l’agent. Ce type de direction est basé sur le travail original de Craig Reynolds sur les boids. Au moyen de la direction, on peut obtenir une forme simple de:

vers un objectif de navigation
comportement d’évitement des obstacles
un comportement de mur après
l’ennemi approche
évitement des prédateurs
comportement de la foule
L’avantage du pilotage est qu’il est très efficace sur le plan informatique. Dans les jeux informatiques, des centaines de soldats peuvent être conduits par cette technique. En cas de terrain plus compliqué (par exemple un bâtiment), toutefois, la direction doit être combinée à la recherche de trajectoire (comme par exemple à Milani), qui est une forme de planification.