APPLICATION À LA SYNTHÈSE
Animation de personnages
Généralités
Le dessin animé traditionnel a parfaitement réussi dans
un certain type de représentation, dite cartoon. L´utilisation
de l´image de synthèse, et singulièrement de la 3D, permet
l´automatisation du mouvement tout en posant un certain
nombre de problèmes.
La plupart de ces problèmes vient du fait que l´on utilise
un outil nouveau (l´ordinateur) et des méthodes différentes
(algorithmie) pour simuler des savoir_faire anciens. Ainsi la
méthode des dessins clés, extrêmement laborieuse, non
réutilisable et peu réaliste permet, au mieux, de faire comme avant.
Les méthodes dynamiques, ou méthodes basées sur la
physique, autorisent un haut degré de réalisme mais ne
résolvent pas les problèmes de scénographie. Les impulsions
(couples exercés sur les joints d´une structure
articulée) sont difficile à générer dans un but déterminé
(comme par exemple faire "marcher" un personnage).
La meilleure façon de proceder est d´accorder à ces créatures
une certaine autonomie via la notion de comportement
généralement encapsulé sous la forme d´un contrôleur
dans la créature elle-même. Mais comment construire des tels
contrôleurs ?
"Spacetime Constraints"
Il s´agit d´une méthode intermédiaire entre celle des dessins clés
et la dynamique: L´animateur contrôle globalement les mouvements
de son personnage en specifiant un ensemble de positions qu´il
veut voir se réaliser et il confie à la méthode le soin de
générer une animation continue passant par ces positions de
contrôle. Mais, au lieu d´utiliser la cinématique (interpolation par
des B-Splines par exemple), l´algorithme cherche à optimiser une
certaine fonction (par exemple minimiser l´énergie dépensée par
un modèle dynamique effectuant ce mouvement) [LIU 94]
Introduite en 1988 par Witkin et Kass [WITKIN 1988], la
méthode des spacetime constraints autorise un haut degré de
contrôle (comme par exemple réaliser
des actions du genre "aller de A en B") tout en produisant un
mouvement dynamiquement plausible. Cette méthode optimise les trajets
cinématiques des éléments d´une figure articulée en minimisant
l´énergie produite par un modèle dynamique lors de leur
réalisation.
L´animateur doit spécifier:
La structure physique du personnage à animer.
Les actuateurs contrôlant la configuration interne du personnage.
La description du mouvement.
La méthode trouve alors des trajectoires réalistes optimales
compatibles avec le mouvement désiré.
Mais de nombreuses solutions optimales sont en général possible,
et, de plus, le procédé est instable (un petit changement des
commandes des actuateurs peut produire des trajectoires très
différentes: Effet de chaos).
Méthode comportementale
Ngo et Marks [NGO 1993] proposent une méthode de codage
comportemental des trajectoires obtenues par "spacetime constraints"
et un algorithme génétique choisissant les paramètres comportementaux:
Un module dynamique simule un environnement virtuel physiquement
correct dans lequel les effets des comportements de créatures
peuvent être testés par essais et erreurs.
Un module générant de tels comportement à partir
d´un algorithme paramétrique basé sur le principe de stimulus-réponse.
Un module de recherche utilisant un algorithme génétique pour
choisir les stimulus et les réponses du module comportemental.
Stimulus-réponse
L´algorithme crée des réactions réflexes (les réponses)
déclenchées par des conditions captées dans l´environnement virtuel
(les stimulus). Ces réactions dépendent de paramètres
qui restent constants le temps de l´action. L´utilisation de ces
SR-paramètres à la place d´une série de forces caractérise
cette méthode.
Une réponse (une description de modification continue
de la créature) est constituée d´une constante de temps
t et d´un ensemble de valeurs cibles A0 (des angles):
A0 = {a0,1, a0,2, ..., a0,n}
L´équation du mouvement amorti pour le paramètre ai est:
t2 a"i + 2 t a´i + (ai - a0,i) = 0
Un stimulus est une fonction d´une variable sensorielle
captée selon différents modes dans l´environnement:
Proprioceptif: Angles des joints.
Tactile: Réaction du sol sur les éléments de la créature.
Kinesthésique: Vitesse du centre de masse.
De position: Centre de masse.
Soit {v1, v2, ..., vm) une variable
sensorielle normalisée, la fonction stimulus est définie par:
v0,j et cj sont les paramètres déterminés
par le module de recherche (voir 6-1-4 plus loin).
Dans l´espace à m dimensions des variables sensorielles, l´ensemble
des points pour lesquels la fonction stimulus est positive est un
hyper-rectangle de dimensions:
{2/c1, 2/c2, ..., 2/cm}
et centré en:
{v0,1, v0,2, ..., v0,m}
L´algorithme de génération d´un comportement est:
Initialiser la créature.
Activer la réponse 0.
Boucle pour t=1 jusqu´a T
Calculer la déformation au temps t par la réponse.
Simuler la dynamique au temps t.
Capter les variables sensorielles dans l´environnement.
Calculer le maximum de la fonction stimulus.
S´il est positif alors activer la réponse correspondante.
Fin de la boucle.
Il n´y a changement de réponse que si le maximum de la fonction stimulus
est positif, une réponse agit donc selon un certain temps, produisant
un mouvement choérent.
Algorithme génétique
Le maximum de la fonction stimulus est recherché par une
méthode évolutionniste: Les génomes sont des listes de paramètres
initialisés aléatoirement et qui, en fonction de leurs évaluations,
sont d´abord sélectionnés, puis croisés et mutés.
Ngo et Marks
ont implémenté l´algorithme génétique sur un multiprocesseur
(Thinking Machine) de 4096 processeurs arrangés dans un plan de 64 * 64.
Lors de la reproduction, chaque processeur s´occupe d´un génome, et
recherche son partenaire comme le meilleur
génome, autre que lui-même, rencontré sur un parcours aléatoire
limité a 10 pas; ainsi la meilleure solution d´un voisinage
est protégée lors du croisement et de la mutation (élitisme).
Ce procédé local de génération provoque une diffusion
des bonnes solutions conduisant à des poches de solutions semblables.
Les auteurs ont appliqués ces idées à des structures articulées
2D simples en choisissant des fonctions d´évaluation qui favorisent
par exemple les sauts ou les déplacements.
Contrôleur d´animation 3D de figures
Animation de figures
La méthode des dessins clés suppose un contrôle
exhaustif et ne sait pas résoudre les problèmes complexes ou
les mouvements à base de dynamique, elle échoue aussi
à gérer
un grand nombre d´acteurs interagissant.
Les méthodes dynamiques, si elles synthétisent bien les
mouvements réalistes, ne permettent pas de gérer convenablement
une scénographie.
En 1988, Witkin et Kass [WITKIN 1988] proposent la méthode
des spacetime constraints qui autorise un haut degré de
contrôle tout en produisant un mouvement dynamiquement plausible.
Ngo et Marks [NGO 1993] couplent cette méthode avec un
algorithme génétique (voir 6-1 ci-dessus).
Mais le fait d´utiliser
des génomes de taille fixe ne permet pas de faire varier la
compléxite du problème au cours de sa résolution.
En 1997, Gritz et Hahn [GRITZ 1997] proposent l´utilisation du
concept de programmation génétique, en appliquant les
idées de Koza [KOZA 1992]: Les contrôleurs de mouvements
sont des programmes résultats de l´évolution génétique d´une
population initialisée aléatoirement.
Évolution génétique de contrôleurs
L´utilisateur spécifie, en entrée, un modèle de figure
articulée (descriptions géométrique, topologique et dynamique) et
une mesure d´adaptation (codant les informations sur le mouvement
désiré). La mesure d´adaptation note une séquence de mouvement
proportionnellement à son écart par rapport au mouvement théorique.
Un optimiseur (à base de programmation génétique) et un module
dynamique constituent le coeur du système.
La sortie est un programme contrôleur optimal générant l´animation.
Contrôleurs et simulation
Les contrôleurs sont des
S-expressions
LISP donnant les
orientations de chaque joint d´une structure articulée à un instant
donné, il y a une sous-expression pour chaque degré de liberté. Chaque
joint est controlé par un ressort angulaire amorti dont la position
neutre est évaluée par la S-expression à chaque instant. Le joint
est soumis à un couple proportionnel à la différence entre son angle
actuel et l´angle désiré. Le système intègre également des contraintes,
des détections de collision et les réponses à ces collisions:
Pour évaluer un contrôleur, le module dynamique est invoqué, et
l´animation résultante est notée relativement à certaines conditions
(par exemple une distance parcourue, une direction suivie, etc...).
Résultats
Gritz et Hahn ont testé leur système pour animer les "petites
lampes" de Luxo Jr [PIXAR 1986]. Les mouvements produits sont
réalsites et organiques.
Mais les contrôleurs ne peuvent accomplir qu´une seule action et
ne sont donc pas réutilisables dans d´autres circonstances, ce
qui est pénalisant étant donné les temps considérables de calculs
du processus de génération génétique.
Pour construire des contrôleurs robustes on utilise la
méthode proposée par Koza [KOZA 1992] consistant à utiliser un
ensemble d´apprentissage pour évaluer la fonction d´adaptation:
Plutôt que d´évaluer par une métrique basée sur un ensemble
particulier de conditions initiales, un certain nombre d´évaluations
sont générées aléatoirement et la nouvelle mesure d´adaptation est
donnée par la moyenne sur N essais.
L´approche animat
Animats
Un animat est un agent, qui peut être simulé
sur ordinateur ou être un robot physique,
dont les comportements, inspirés de la nature, présentent
une certaine autonomie et des capacités d´adaptation. Un animat
est généralement constitué [MEYER 1998]:
De capteurs analysant l´environnement et son propre corps.
D´actuateurs, ou moteurs, contrôlant ses mouvements.
D´un programme reliant ses perceptions et ses actions et constituant
une architecture de contrôle. Celle-ci peut être innée
(programmée ou cablée d´avance) ou acquise c´est à dire
résultant d´un apprentissage effectué au cours de la vie d´un
animat particulier (par des réseaux neuronaux) ou au
cours de l´évolution d´une population d´animats (par des algorithmes
génétiques ou encore par de la programmation génétique).
L´intelligence collective
L´
intelligence collective
(ou en
en essaim),
inspirée de l´observation
des sociétés d´insectes, est une qualité émergente d´une
population dans laquelle chaque individu peut avoir un comportement
propre très simple, mais dont le comportement collectif, résultat
des nombreuses interactions entre individus, peut être très complexe
et hautement adaptatif. Reynolds [REYNOLDS 1987] a, le premier,
programmé de tels comportements collectifs.
On peut expliquer les comportements, en apparence très sophistiqués,
de fourmis suivant des chemins optimaux à la recherche de nourriture,
par le dépot d´une substance odorante, le phéromone, sur
leur trajet, attirant ainsi les autres fourmis. Lorsque la nourriture
diminue, les traces odorantes diminuent aussi et moins de fourmis
sont attirées. Le renforcement du marquage par les différentes
fourmis qui suivent un chemin et l´évaporation du phéromone au
cours du temps permettent d´optimiser le parcours, c´est à dire de
sélectionner le plus court.
Cette stratégie a été utilisée pour résoudre le fameux
problème du voyageur de commerce: Dans quel ordes faut-il visiter
N villes de manière à minimiser la distance totale parcourue sans
repasser deux fois par la même ville. On lâche une population de fourmis
sur le réseau des villes, chaque individu marquant son passage par
un dépot d´une substance qui s´évapore linéairement avec le temps. Au
bout d´un certain temps on constate que la majorité des fourmis suivent
le trajet optimal recherché.
Apprentissage
Les animats peuvent soit avoir un comportement préprogrammé,
soit se modifier par apprentissage au cours de leur vie, on
distingue:
L´apprentissage associatif qui consiste à apprendre,
mémoriser et reconstituer un ensemble de stimuli en les associant
les uns aux autres. Selon cette méthode l´animat peut
construire une carte cognitive de son environnement
(représentation spatiale de l´environnement par des repères que
l´animat apprend à distinguer), qu´il utilise ensuite pour se
déplacer. Un premier niveau d´analyse combine de simples réflexes
permettant de détecter les obstacles et d´en suivre les contours. Un
deuxième niveau détecte des repères remarquables. Enfin un
troisième niveau utilise ces informations pour construire la
carte cognitive. Cette carte est codée sous la forme de modules
de calculs correspondant à chaque repère (cellules de lieux) et
qui s´activent lorsque l´animat y passe physiquement, ce qui lui
permet de se repérer. Pour atteindre un but donné on déclenche
un processus de diffusion d´activation à partir de ce but. Comme
la vitesse de diffusion dépend de la taille de la région
traversée, le module le plus proche sera activé le premier et,
lorsque l´onde atteint la position actuelle, les modules
successivement activés constituent le chemin le plus court
pour atteindre le but.
L´apprentissage par renforcement qui se fait en
notant les actions par une fonction d´évaluation extérieure et en
corrigeant le comportement de façon à maximiser ces notes.
Ainsi on peut imaginer des objets "comestibles" et d´autres "douloureux",
l´animat apprend à classer les objets de son environnement en
catégories (manger les objets comestibles et fuire les objets
douloureux). L´architecture de contrôle est constituée de règle
manipulant des objets, des buts et des relations, elle permet
à l´animat de s´adapter à son environnement en construisant des
représentations internes. Un comportement instinctif de
bas niveau pousse l´animat à explorer son environnement. Cette
exploration est interrompue lorsqu´un signal externe (en provenance des
objets) ou interne (en provenance de ses représentations) lui parvient.
Voir aussi La Vie ART ificielle:
"L´approche animat".
Processus sélectif
S´inspirant de la nature qui élabore des êtres de plus en plus
évolués par la sélection naturelle, la vie artificielle
utilise une sélection artificielle qui favorise la reproduction
des individus les mieux adaptés à un environnement donné et répondant
le mieux à des problèmes de survie. Pour cela une population
d´animats est soumise à un algorithme génétique procédant par
sélection, croisement et mutation. À l´issue
d´un certain nombre de générations, le meilleur individu est
optimal.
Applications
Dans des applications mal définies ou hautement complexes (comme
par exemple la rechercher de certaines informations sur internet,
ou l´exploration d´une planète lointaine), il peut être utile de
disposer d´agents autonomes capables d´adapter leur comportement
à des circonstances imprévues sans une intervention humaine.
Les progrès dans le domaine de la vie artificielle aideront
à comprendre comment l´intelligence humaine peut s´expliquer
à partir des comportements adaptatifs élémentaires hérités de
l´animal. Alors que l´Intelligence Artificielle traditionnelle (I.A.)
explique les capacités cognitives de l´homme par des manipulations
de symboles, l´approche animat, elle, cherche à comprendre comment
ces capacités découlent de la simple aptitude à survivre.