Un behavior tree (dell'Iglese, tradotto in italiano in albero comportamentale) è un modello matematico di esecuzione del piano utilizzato in informatica, robotica, sistemi di controllo e videogiochi . Descrivono in modo modulare i passaggi tra un insieme finito di attività. La loro forza deriva dalla capacità di creare compiti molto complessi composti da compiti semplici, senza preoccuparsi di come vengono implementati i compiti semplici. Gli alberi comportamentali presentano alcune somiglianze con le macchine a stati gerarchici, con la differenza fondamentale che l'elemento fondamentale di un comportamento è un'attività e non uno stato. La loro facilità di comprensione da parte dell'uomo rende gli alberi comportamentali meno soggetti a errori e molto apprezzati dalla comunità degli sviluppatori di giochi. È stato dimostrato che gli alberi comportamentali generalizzano diverse altre architetture di controllo. [1] [2]
Contesto
[modifica | modifica wikitesto]Una struttura di controllo basata sul comportamento è stata inizialmente proposta da Rodney Brooks nel suo articolo intitolato "A robust layered control system for a mobile robot". Nella proposta iniziale, un elenco di comportamenti poteva funzionare come alternativa l'uno all'altro. In seguito, l'approccio è stato esteso e generalizzato in un'organizzazione ad albero dei comportamenti, con ampia applicazione nell'industria dei giochi </link> come un potente strumento per modellare il comportamento dei personaggi non giocanti (NPC). [3] [4] [5] [6] Sono stati ampiamente utilizzati in videogiochi di alto profilo come Halo, Bioshock e Spore . Lavori recenti propongono alberi comportamentali come un framework di controllo multi-missione per UAV, robot complessi, manipolazione robotica e sistemi multi-robot. [7] [8] [9] [10] [11] [12] Gli alberi comportamentali hanno ormai raggiunto la maturità per essere trattati nei libri di testo di Game AI, [13] [14] così come in ambienti di gioco generici come Unity (motore di gioco) e Unreal Engine (vedere i link sotto).
I behavior trees sono diventati popolari per il loro paradigma di sviluppo: essere in grado di creare un comportamento complesso programmando solo le azioni del NPC e quindi progettare una struttura ad albero (solitamente tramite trascinamento della selezione ) i cui nodi foglia sono le azioni e i cui nodi interni determinano il processo decisionale dell'NPC. I behaviour trees sono visivamente intuitivi e facili da progettare, testare e correggere, e offrono maggiore modularità, scalabilità e riutilizzabilità rispetto ad altri metodi di creazione di comportamenti.
Nel corso degli anni, le diverse implementazioni dei behavior trees hanno continuato a migliorare sia in termini di efficienza che di capacità di soddisfare le richieste del settore, fino a trasformarsi in alberi comportamentali guidati dagli eventi . [15] [5] I behavior trees basati sugli eventi hanno risolto alcuni problemi di scalabilità dei behavior trees modificando il modo in cui l'albero gestisce internamente la propria esecuzione e introducendo un nuovo tipo di nodo in grado di reagire agli eventi e di annullare i nodi in esecuzione. Al giorno d'oggi, il concetto di behavior tree guidato dagli eventi è uno standard e viene utilizzato nella maggior parte delle implementazioni, anche se per semplicità vengono ancora chiamati "alberi comportamentali".
Concetti chiave
[modifica | modifica wikitesto]Un behavior tree è rappresentato graficamente come un albero diretto in cui i nodi sono classificati come radice, nodi di flusso di controllo o nodi di esecuzione (attività o tasks). Per ogni coppia di nodi connessi, il nodo in uscita è chiamato nodo padre (parent) e quello in arrivo è chiamato nodo figlio (child). La radice non ha genitori e ha solo un figlio, i nodi del flusso di controllo hanno un genitore e almeno un figlio, mentre i nodi di esecuzione hanno un genitore e nessun figlio. Graficamente, i figli di un nodo di flusso di controllo sono posizionati sotto di esso, ordinati da sinistra a destra. [16]
L'esecuzione di un behavior tree inizia dalla radice, che invia tick (un segnale di abilitazione che consente l'esecuzione di un figlio) con una certa frequenza al suo figlio. Quando l'esecuzione di un nodo nel behavior tree è consentita, restituisce al nodo padre lo stato "in esecuzione" (running) se la sua esecuzione non è ancora terminata, "successo" (success) se ha raggiunto il suo obiettivo, " fallimento" (failure) in caso contrario.
Nodo di controllo del flusso
[modifica | modifica wikitesto]Un nodo di flusso di controllo viene utilizzato per controllare le sottoattività di cui è composto. Un nodo di flusso di controllo può essere un nodo selettore (fallback) o un nodo sequenza (sequence). A turno svolgono ciascuno dei loro sottocompiti. Quando una sottotask viene completata e restituisce il suo stato (successo o fallimento), il nodo del flusso di controllo decide se eseguire o meno il sottotask successivo.
Nodo selettore (fallback)
[modifica | modifica wikitesto]I nodi di fallback vengono utilizzati per trovare ed eseguire il primo figlio che non rstituisce errori. Un nodo di fallback restituirà immediatamente un codice di stato di successo o in esecuzione quando uno dei suoi figli restituisce successo o in esecuzione (vedere la Figura I e lo pseudocodice seguente). I figli vengono contrassegnati in ordine di importanza, da sinistra a destra.
In pseudocodice, l'algoritmo per una composizione di fallback è:
1 for i from 1 to n do 2 childstatus ← Tick(child(i)) 3 if childstatus = running 4 return running 5 else if childstatus = success 6 return success 7 end 8 return failure
Nodo sequenza
[modifica | modifica wikitesto]I nodi sequenza vengono utilizzati per trovare ed eseguire il primo figlio che non ha ancora avuto successo. Un nodo sequenza restituirà immediatamente un codice di stato di errore o di esecuzione quando uno dei suoi figli restituisce errore o di esecuzione (vedere Figura II e lo pseudocodice seguente). I figli vengono contrassegnati in ordine, da sinistra a destra.
In pseudocodice, l'algoritmo per la composizione di una sequenza è:
1 for i from 1 to n do 2 childstatus ← Tick(child(i)) 3 if childstatus = running 4 return running 5 else if childstatus = failure 6 return failure 7 end 8 return success
Voci correlate
[modifica | modifica wikitesto]Bibliografia
[modifica | modifica wikitesto]- ^ vol. 33, 2017, DOI:10.1109/TRO.2016.2633567, http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-202922.
- ^ Michele Colledanchise e Petter Ögren, Behavior Trees in Robotics and AI: An Introduction, CRC Press, 2018, DOI:10.1201/9780429489105, ISBN 978-1-138-59373-2.
- ^ gamasutra.com, https://www.gamasutra.com/view/feature/130663/gdc_2005_proceeding_handling_.php .
- ^ D. Isla, Halo 3-building a better battle, 2008.
- ^ a b vol. 155, DOI:10.1016/j.eswa.2020.113457, https://cs.uns.edu.ar/~ragis/Agis%20et%20al.%20(2020)%20-%20An%20event-driven%20behavior%20trees%20extension%20to%20facilitate%20non-player%20multi-agent%20coordination%20in%20video%20games.pdf. Errore nelle note: Tag
<ref>
non valido; il nome "agis2020" è stato definito più volte con contenuti diversi - ^ C. U. Lim, R. Baumgarten e S. Colton, Applications of Evolutionary Computation, Lecture Notes in Computer Science, vol. 6024, Springer, 2010, pp. 100–110, DOI:10.1007/978-3-642-12239-2_11, ISBN 978-3-642-12238-5.
- ^ Petter Ögren, AIAA Guidance, Navigation and Control Conference, Minneapolis, Minnesota, 2012, pp. 13–16.
- ^ Michele Colledanchise, Alejandro Marzinotto e Petter Ögren, 2014 IEEE International Conference on Robotics and Automation (ICRA), 2014, pp. 3265–3272, DOI:10.1109/ICRA.2014.6907328, ISBN 978-1-4799-3685-4.
- ^ Alejandro Marzinotto, Michele Colledanchise e Christian Smith, Robotics and Automation (ICRA), 2014 IEEE International Conference on, 2014.
- ^ Klöckner, Andreas. "Interfacing BTs with the World Using Description Logic." In AIAA Guidance, Navigation and Control Conference, Boston, MA. 2013.
- ^ Andreas Klöckner, GI-Jahrestagung, 2013, pp. 57–68.
- ^ J. Andrew Bagnell, Felipe Cavalcanti e Lei Cui, Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on, IEEE, 2012, pp. 2955–2962, DOI:10.1109/IROS.2012.6385888, ISBN 978-1-4673-1736-8.
- ^ Millington e Funge, Artificial Intelligence for Games, CRC Press, 2009, ISBN 978-0-12-374731-0.
- ^ S. Rabin, Game AI Pro, CRC Press, 2014, ISBN 978-1-4665-6596-8.
- ^ Alex J. Champandard e Philip Dunstan, Game AI Pro: Collected Wisdom of Game AI Professionals, 2012, pp. 72–92.
- ^ craft ai, craft.ai, https://www.craft.ai/post/bt-101-behavior-trees-grammar-basics .
Collegamenti esterni
[modifica | modifica wikitesto]- Libreria di behavior trees ROS
- Documentazione del behavior tree di Unreal Engine 4
- Behavior trees per l'intelligenza artificiale: come funzionano
- Behavior trees: intelligenza artificiale semplice ma potente per il tuo robot Archiviato il 25 febbraio 2020 in Internet Archive. </link>
- Videolezioni sui behavior trees