Modelling human behaviour using behaviour trees

Abstract

English summary Behaviour trees (BTs) are a relatively new and increasingly popular approach for developing behaviour models for artificial intelligence (AI) and intelligent agents. The approach has become especially popular for creating behaviours for non-player characters in computer games, robots, and autonomous vehicles. The first high-profile computer game which used BTs was Halo 2 from Bungie Software, which was released in 2004. BTs are represented as directed trees with a hierarchy of control flow nodes and task nodes that control the behaviour of an agent. The control flow nodes are interior nodes (nodes with one or more children) and contain some decision logic for flow control. The task nodes are leaf nodes (nodes without children) and contain conditional tasks which test some property in the simulated environment (or the real world in the case of robots and autonomous vehicles), or action tasks which alter the state of the simulation (or the real world) in some way. What makes BTs so powerful is their composability and modularity. Task nodes and control flow nodes are composed into subtrees which represent more complex actions, and these actions can be composed into higher level behaviours. Task nodes and action subtrees can be reused, and different subtrees can be developed independently of each other. BT editors with graphical user interfaces enable users without programming skills to create modular behaviour models. Furthermore, to reduce complexity and ensure readability of the graphical model of large BTs, they can be decomposed into smaller subtrees. Examples of AI engines (or AI middleware) for military simulation systems that use BTs are Virtual Battlespace (VBS) Control and MASA Life. In this report we focus on BTs for human behaviour modelling, and more specifically on using BTs to model battle drills for computer generated forces in military simulation systems. We conduct constructive entity-level simulations of battalion to brigade level operations for experimentation and analysis purposes. To support this work we are developing human behaviour models for semi-automated forces in VBS, using the new AI framework VBS Control. First, we briefly describe the background for this work. Secondly, we give a short introduction to human behaviour modelling and artificial intelligence. Thirdly, we give an introduction to BTs and look at the process of developing BTs. We also look at the advantages and limitations of BTs and some of the extensions to the BT concept that have been proposed. Finally, we describe how we are using BTs to build a library of behaviour models of battle drills for mechanized infantry platoons, and provide an example of a modelled battle drill.

Sammendrag Behaviour trees (BT-er) er en relativt ny og stadig mer populær tilnærming for utvikling av oppførselsmodeller for kunstig intelligens (AI) og intelligente agenter. Tilnærmingen har blitt spesielt populær til å utvikle oppførsel for ikke-spillbare karakterer i dataspill, roboter og autonome kjøretøy. Det første høyprofilerte dataspillet som anvendte BT-er var Halo 2 fra Bungie Software, som ble utgitt i 2004. BT-er representeres som rettede trær med et hierarki av kontrollflytnoder og oppgavenoder som styrer oppførselen til en agent. Kontrollflytnodene er indre noder (noder som har ett eller flere barn) og inneholder beslutningslogikk for flytkontroll. Oppgavenodene er bladnoder (noder uten barn) og inneholder oppgaver for betingelser som tester en egenskap i det simulerte miljøet (eller den virkelige verden når det gjelder roboter og autonome kjøretøy), eller oppgaver for handlinger som endrer tilstanden til simuleringen (eller den virkelige verden) på en eller annen måte. Det som gjør BT-tilnærming så kraftfull, er komponerbarheten og modulariteten til BT-ene. Oppgavenoder og kontrollflytnoder settes sammen til subtrær som representerer mer komplekse handlinger, og disse handlingene kan videre settes sammen til oppførsel på høyere nivå. Oppgavenoder og subtrær for handlinger kan gjenbrukes, og forskjellige subtrær kan utvikles uavhengig av hverandre. BT-editorer med grafiske brukergrensesnitt gjør brukere uten programmeringsferdigheter i stand til å utvikle modulære oppførselsmodeller. Dessuten kan den grafiske modellen til et stort BT dekomponeres til mindre subtrær for å redusere kompleksiteten og dermed øke lesbarheten. Eksempler på AI-motorer (eller AI-mellomvare) for militære simuleringssystemer som bruker BT-er er Virtual Battlespace (VBS) Control og MASA Life. I rapporten fokuserer vi på bruk av BT-er for å modellere menneskelig oppførsel, og særlig på å bruke BT-er til å modellere stridsdriller for datagenererte styrker i militære simuleringssystemer. Vi utfører “constructive”-simuleringer på entitetsnivå av operasjoner på bataljons- til brigadenivå for eksperimenterings- og analyseformål. For å støtte dette arbeidet utvikler vi menneskelige oppførselsmodeller for semiautomatiske styrker i VBS ved hjelp av AI-rammeverket VBS Control. Først i rapporten beskriver vi kort bakgrunnen for dette arbeidet. Videre gir vi en kort introduksjon til modellering av menneskelig oppførsel og kunstig intelligens. Etter dette gir vi en introduksjon til BT-er og ser på prosessen med å utvikle dem. Vi ser også på fordelene og begrensningene til BT-er, samt på noen av utvidelsene av BT-konseptet som har blitt foreslått. Til slutt beskriver vi hvordan vi bruker BT-er for å bygge opp et bibliotek av oppførselsmodeller for stridsdriller for mekaniserte infanteritropper og gir et eksempel på en modellert stridsdrill.