Tout d'abord, nous obtenons un tableau d'actions_3D à partir de l'analyse syntaxico-sémantique de ce qu'a dit l'utilisateur. Chaque élément de ce tableau décrit à la fois l'endroit vers lequel regarder, l'endroit vers lequel s'orienter et l'endroit vers lequel aller. Il y a autant d'éléments que d'ordres donnés à l'agent.

C'est à partir d'un tel élément qu'entre en jeux le planifieur qui retourne une liste symbolique représentant un plan de la forme:

( (sous-plan 1) (sous-plan 2) ... (sous-plan n) )

Chaque sous-plan est rattaché à un but de manière à pouvoir stopper la simulation cinématique. Il y autant de sous-plans que de sous-problèmes indépendants générés au premier niveau. Par exemple lors du calcul de trajectoire en évitant les obstacles, on fera passer l'agent par plusieurs endroits différents au lieu de le faire aller tout droit vers son but.

Exemple de plan obtenu avec deux sous-plans:

( ( (move #OBJ1 a1) (move #OBJ2 a2) )
( BOUCLE (move #OBJ3 a3) (move #OBJ4 a4) PUIS (move #OBJ5 a5) ) )

Ce plan possède plusieurs types de symboles:

move : spécifie une position à atteindre.

PUIS : enchaînement, marque la séquence. Son absence marque la simultanéité.

BOUCLE : signifie l'enchaînement en boucle.

#nom : un objet articulé de l'agent, comme la tête ...

a1 : une intance de variable 3d (x,y,z).

Le premier sous-plan signifie qu'il faut bouger simultanément OBJ1 et OBJ2. Quand c'est terminé, on exécute le second sous-plan. Celui-ci dit de boucler sur l'action suivante: bouger simultanément OBJ3 et OBJ4 et seulement ensuite bouger OBJ5, puis recommencer ... Les ai du plan sont les angles de rotation à atteindre dans le repère Oxyz.

Ensuite, il s'agit de compiler ce plan de manière à fabriquer une chaîne d'opérateurs directement interprétable par le simulateur cinématique. Chaque opérateur décrit une position intermédiaire que l'agent virtuel devra atteindre. Il y a autant de compilations que de sous-plans. On regroupe tous les mouvements simultanés dans des opérateurs. Avec l'exemple précédent nous obtenons:

Le générateur de plan décompose un problème de manière linéaire et hiérarchique. C'est un objet (au sens C++) constitué des éléments suivants:

problemes: Liste symbolique représentant une pile où chaque élément est un problème à résoudre. Le planifieur va décomposer les problèmes de cette liste.

plan: Liste symbolique contenant le plan final. Chaque problème non décomposable y est enfilé.

plan_compile: C'est un tableau où chaque élément pointe sur une liste représentant la compilation d'un sous-plan. Chacune de ces listes sera soumise une à une au simulateur cinématique.

buts: C'est aussi un tableau des buts a atteindre en ralation avec les plans compilés.

genere_plan: Méthode qui décompose chaque problème en suspend en sous-problèmes, jusqu'à ce qu'il n'y ait plus de problèmes. On prend le premier problème. On commence par sélectionner les règles qui permettent de le résoudre: c'est la phase de restriction. Ensuite, parmis les régles sélectionnées, il faut en choisir une applicable: c'est la phase de filtrage et résolution de conflits. Enfin, il n'y a plus qu'à actionner cette règle: c'est à dire empiler les nouveaux problèmes, enfiler le plan calculé et simuler les changements dans le monde si c'est spécifié.

Des règles du premier ordre sont utilisées par le générateur. Elles décomposent un problème en sous-problèmes, et sont constituées de:

nom: Chaque problème posséde un nom. Il est résolu par une régle possédant le même nom. Ce nom n'est pas unique, ce qui signifie qu'il y a plusieurs manières de résoudre un problème, d'où la phase de résoltion de conflits.

var: Liste symbolique regroupant les variables externes. Elles sont instanciées par filtrage.

precond: Liste symbolique des préconditions requises pour effectuer la décomposition. Par exemple, on peut instancier des variables internes. C'est ici que l'applicabilité de la règle et vérifiée lors de la résolution de conflits . Chaque précondition renferme un symbole de fonction qui est exécuté.

new_pb: Liste symbolique des nouveaux problèmes posés à empiler.

plan: Liste symbolique regroupant un morceau de plan, c'est à dire des problèmes qui ne sont plus décomposables.

modif: Une modification à simuler, comme un déplacement par exemple. En effet, les cacluls ne seront plus les mêmes si l'agent doit bouger avant d'atteindre sont but (parcequ'il y a un obstacle par exemple). Ceci rend compte du fait que nous raisonons non seulement sur l'état initial du monde, mais aussi sur les états intermédiaires lors de la planification. C'est le frame problem .

filtre: C'est une méthode qui permet d'instancier les variables externes et internes de la règle en évaluant chacune des préconditions. Elle retourne FAUX dès que la vérification d'une précondition retourne FAUX. Sinon elle retourne VRAI. Cette méthode est appelée avec la liste des instances des variables externes.

Compiler le plan consiste à fabriquer des listes chaînées où chaque élément (qui est un opérateur) rend compte des objets de l'agent virtuel à bouger en parallèle. A chaque fois que le symbole "PUIS" est rencontré, on fabrique un nouvel opérateur. Si c'est le symbole "BOUCLE", alors non seulement on fabrique un nouvel opérateur, mais en plus on sauvegarde un pointeur sur cet opérateur de manière à y faire boucler la liste quand la compilation est terminée. De plus, on crée une nouvelle liste à chaque fois que l'on passe à un nouveau sous-plan. Ainsi il y a autant de compilations que de sous-plans.

Ensuite, cette chaîne d'opérateurs est soumise au simulateur cinématique, et c'est à ce moment que l'on voit l'animation 3D. Cette animation est interruptible : elle s'arrète quand l'agent a atteint son but (chaque sous-plan planifié possède son but à atteindre) ou alors lorsqu'un ordre d'interruption a été analysé tel que "arrète toi". De plus l'agent réagit lorsqu'il y a une collision qui n'a pas été prévue. En effet, lors de la phase de planification, nous faisons l'hyposthèse d'un monde statique.

Un exemple de séquence d'animation (5 images GIF).