GOAP : rechercher une séquence d'actions, puis valider son exécution

Rechercher parmi les états possibles du monde

La planification d'actions orientée but, ou GOAP (Goal-Oriented Action Planning), recherche une séquence d'actions qui satisfait une condition souhaitée du monde. Une action expose des préconditions, des effets et un coût de planification. La recherche opère sur des états hypothétiques ; l'exécution des actions retenues est réalisée ensuite par le runtime. Orkin décrit cette approche dans l'explication originale de F.E.A.R., et ReGoap en fournit une implémentation concrète, avec une séparation des responsabilités entre planification et exécution. [1][2]

Fournir au modèle suffisamment d'informations

Il faut représenter les faits qui modifient réellement la disponibilité des actions. Posséder une clé et se tenir à côté d'une porte verrouillée sont deux conditions distinctes. Il faut définir ce que chaque action ajoute, retire ou consomme, et empêcher la recherche de traiter silencieusement des faits inconnus comme des faits confirmés. Les coûts doivent exprimer le compromis que l'on cherche à optimiser, comme le temps ou la consommation de ressources, dans des unités comparables. Un plan à faible coût ne l'est que dans le cadre de ce modèle.

Exemple détaillé : rétablir le courant par deux voies

À titre d'illustration, un ouvrier part d'un magasin sans fusible ; le générateur est éteint. Le but est powerOn = true. Un premier plan enchaîne FetchFuse (coût 2), puis ReachGenerator (coût 3), puis InstallFuse (coût 1). L'installation exige à la fois le fusible et la présence au générateur, consomme le fusible et met le courant. Le coût total est 2 + 3 + 1 = 6.

Un autre plan consiste en ReachGenerator suivi de HandCrank (coût 5 une fois sur place), soit 3 + 5 = 8. Si le fusible est disponible, la première voie modélisée est la moins chère. Si le magasin est vide, FetchFuse doit être indisponible et la seconde voie reste possible. Ces coûts de planification sont inventés ; ce ne sont pas des durées d'action mesurées.

Exécuter face à un monde qui change

Avant de démarrer chaque action, il faut revérifier les conditions réelles pertinentes. Les ressources disputées doivent être réservées via le système de gameplay : un planificateur qui trouve un fusible ne le réserve pas. Les faits confirmés du monde doivent être mis à jour lorsque l'effet réel au runtime a réussi, plutôt que de recopier dans la réalité les effets prédits à la fin de la planification.

Il faut créer une trace de diagnostic contenant le but, les faits initiaux, les liaisons d'actions retenues, les coûts estimés et les résultats d'exécution. Retirer le fusible après la planification mais avant son ramassage. Fermer la route vers le générateur. Interrompre l'ouvrier pendant l'installation. Il faut vérifier qu'un échec libère les réservations, met à jour l'état connu et soit déclenche une replanification, soit sélectionne un repli explicite. Il faut éviter de rejouer indéfiniment le même plan devenu impossible.

Maîtriser la recherche et ses limites

Un grand nombre de cibles possibles multiplie les liaisons d'actions et élargit l'espace de recherche. Il faut borner le travail par requête de planification et distinguer l'épuisement du budget de la preuve qu'aucun plan n'existe. Le cache ne doit servir que tant que ses hypothèses restent valides. Les plans courts sont plus faciles à inspecter, mais un horizon de planification trop réduit peut manquer des préparations nécessaires. GOAP ne coordonne pas automatiquement plusieurs ouvriers, n'invente pas les actions manquantes et ne prédit pas les conséquences non modélisées. Le succès se juge à la fois sur la validité de l'exécution et sur le comportement obtenu par rapport à celui visé.

Sources

• [1] Three States and a Plan: The A.I. of F.E.A.R. — Jeff Orkin, Game Developers Conference 2006.
• [2] ReGoap — luxkun et les contributeurs de ReGoap.