Un árbol de comportamiento es un modelo matemático de ejecución de planes que se utiliza en informática , robótica , sistemas de control y videojuegos . Describen cambios entre un conjunto finito de tareas de forma modular. Su fortaleza proviene de su capacidad para crear tareas muy complejas compuestas por tareas simples, sin preocuparse de cómo se implementan las tareas simples. Los árboles de comportamiento presentan algunas similitudes con las máquinas de estado jerárquicas.con la diferencia clave de que el componente principal de un comportamiento es una tarea en lugar de un estado. Su facilidad de comprensión humana hace que los árboles de comportamiento sean menos propensos a errores y muy populares en la comunidad de desarrolladores de juegos. Se ha demostrado que los árboles de comportamiento generalizan varias otras arquitecturas de control. [1] [2] Matemáticamente, son gráficos acíclicos dirigidos .
Fondo
Los árboles de comportamiento se originan en la industria de los juegos de computadora como una herramienta poderosa para modelar el comportamiento de los personajes no jugadores (NPC). [3] [4] [5] [6] Se han utilizado ampliamente en videojuegos de alto perfil como Halo , Bioshock y Spore . Trabajos recientes proponen árboles de comportamiento como un marco de control de múltiples misiones para UAV , robots complejos, manipulación robótica y sistemas de múltiples robots. [7] [8] [9] [10] [11] [12] Los árboles de comportamiento ahora han alcanzado la madurez para ser tratados en los libros de texto de Game AI, [13] [14] así como en entornos de juegos genéricos como Unity (game engine) y Unreal Engine (consulte los enlaces a continuación).
Los árboles de comportamiento se hicieron populares por su paradigma de desarrollo: poder crear un comportamiento complejo solo programando las acciones del NPC y luego diseñando una estructura de árbol (generalmente mediante arrastrar y soltar ) cuyos nodos hoja son acciones y cuyos nodos internos determinan la toma de decisiones del NPC. Los árboles de comportamiento son visualmente intuitivos y fáciles de diseñar, probar y depurar, y proporcionan más modularidad, escalabilidad y reutilización que otros métodos de creación de comportamiento.
A lo largo de los años, las diversas implementaciones de árboles de comportamiento siguieron mejorando tanto en eficiencia como en capacidades para satisfacer las demandas de la industria, hasta que evolucionaron hacia árboles de comportamiento impulsados por eventos . [15] [5] Los árboles de comportamiento controlados por eventos resolvieron algunos problemas de escalabilidad de los árboles de comportamiento clásicos cambiando cómo el árbol maneja internamente su ejecución e introduciendo un nuevo tipo de nodo que puede reaccionar a los eventos y abortar los nodos en ejecución. Hoy en día, el concepto de árbol de comportamiento impulsado por eventos es un estándar y se utiliza en la mayoría de las implementaciones, aunque todavía se llaman "árboles de comportamiento" por simplicidad.
Conceptos clave
Un árbol de comportamiento se representa gráficamente como un árbol dirigido en el que los nodos se clasifican como raíz, nodos de flujo de control o nodos de ejecución (tareas). Para cada par de nodos conectados, el nodo saliente se llama padre y el nodo entrante se llama hijo. La raíz no tiene padres y exactamente un hijo, los nodos de flujo de control tienen un padre y al menos un hijo, y los nodos de ejecución tienen un padre y ningún hijo. Gráficamente, los hijos de un nodo de flujo de control se colocan debajo de él, ordenados de izquierda a derecha. [dieciséis]
La ejecución de un árbol de comportamiento comienza desde la raíz que envía tics con cierta frecuencia a su hijo. Un tic es una señal habilitadora que permite la ejecución de un niño. Cuando se permite la ejecución de un nodo en el árbol de comportamiento, devuelve al padre un estado en ejecución si su ejecución aún no ha finalizado, éxito si ha logrado su objetivo o fracaso en caso contrario.
Nodo de flujo de control
Un nodo de flujo de control se utiliza para controlar las subtareas que lo componen. Un nodo de flujo de control puede ser un nodo selector (de reserva) o un nodo de secuencia. Ejecutan cada una de sus subtareas por turno. Cuando una subtarea se completa y devuelve su estado (éxito o fracaso), el nodo de flujo de control decide si ejecutar la siguiente subtarea o no.
Nodo selector (respaldo)
Los nodos de reserva se utilizan para buscar y ejecutar el primer hijo que no falla. Un nodo de reserva regresará inmediatamente con un código de estado de éxito o en ejecución cuando uno de sus hijos devuelva éxito o en ejecución (consulte la Figura I y el pseudocódigo a continuación). Los niños están marcados en orden de importancia, de izquierda a derecha.
En pseudocódigo, el algoritmo para una composición alternativa es:
1 para i de 1 an do2 childstatus ← Tick (child (i))3 si childstatus = running4 volver corriendo5 más si childstatus = éxito6 retorno exitoso7 final 8 falla de retorno
Nodo de secuencia
Los nodos de secuencia se utilizan para buscar y ejecutar el primer hijo que aún no ha tenido éxito. Un nodo de secuencia regresará inmediatamente con un código de estado de falla o en ejecución cuando uno de sus hijos devuelva falla o en ejecución (consulte la Figura II y el pseudocódigo a continuación). Los niños están marcados en orden, de izquierda a derecha.
En pseudocódigo, el algoritmo para una composición de secuencia es:
1 para i de 1 an do2 childstatus ← Tick (child (i))3 si childstatus = running4 volver corriendo5 más si childstatus = failure6 falla de retorno7 final 8 regreso exitoso
Definición de espacio de estados matemáticos
Para aplicar las herramientas de la teoría de control al análisis de árboles de comportamiento, se pueden definir como tres tuplas. [17]
dónde es el índice del árbol, es un campo vectorial que representa el lado derecho de una ecuación en diferencias ordinarias, es un paso de tiempo y es el estado de retorno, que puede ser igual a Running , Éxito , o fracaso .
Nota : Una tarea es un árbol de comportamiento degenerado sin padre ni hijo.
Ejecución del árbol de comportamiento
La ejecución de un árbol de comportamiento se describe mediante las siguientes ecuaciones en diferencias ordinarias estándar:
dónde representan el tiempo discreto, y es el espacio de estado del sistema modelado por el árbol de comportamiento.
Composición de la secuencia
Dos árboles de comportamiento y se puede componer en un árbol de comportamiento más complejo utilizando un operador de secuencia.
Entonces devuelve el estado y el campo vectorial asociado con están definidos (para [ definición necesaria ] ) de la siguiente manera:
Ver también
Referencias
- ^ Colledanchise, Michele; Ögren, Petter (2017). "Cómo los árboles de comportamiento modularizan los sistemas de control híbridos y generalizan las composiciones de comportamiento secuenciales, la arquitectura de subsunción y los árboles de decisión" . Transacciones IEEE sobre robótica . 33 (2): 372–389. doi : 10.1109 / TRO.2016.2633567 . S2CID 9518238 .
- ^ Colledanchise, Michele; Ögren, Petter (2018). Árboles de comportamiento en robótica e inteligencia artificial: una introducción . Prensa CRC. arXiv : 1709.00084 . doi : 10.1201 / 9780429489105 . ISBN 978-1-138-59373-2. S2CID 27470659 .
- ^ Isla, D. (2005). "Manejo de la complejidad en Halo 2 AI" . Conferencia de desarrolladores de juegos (Vol. 12) .
- ^ Isla, D. (2008). Halo 3: construye una batalla mejor . Conferencia de desarrolladores de juegos 2008 .
- ^ a b Agis, Ramiro A .; Gottifredi, Sebastián; García, Alejandro J. (2020). "Una extensión de árboles de comportamiento impulsados por eventos para facilitar la coordinación de múltiples agentes sin jugadores en los videojuegos" (PDF) . Sistemas expertos con aplicaciones . 155 (1): 113457. doi : 10.1016 / j.eswa.2020.113457 .
- ^ Lim, CU; Baumgarten, R .; Colton, S. (2010). "Evolución de los árboles de comportamiento para el juego comercial DEFCON" (PDF) . Aplicaciones de la Computación Evolutiva . Berlín: Springer. págs. 100-110. doi : 10.1007 / 978-3-642-12239-2_11 . ISBN 978-3-642-12238-5.
- ^ Ögren, Petter (2012). "Incremento de la modularidad de los sistemas de control de UAV utilizando árboles de comportamiento de juegos de computadora" (PDF) . Conferencia de orientación, navegación y control de la AIAA, Minneapolis, Minnesota . págs. 13-16.
- ^ Colledanchise, Michele; Marzinotto, Alejandro; Ögren, Petter (2014). "Análisis de rendimiento de BT estocásticos" (PDF) . Robótica y Automatización (ICRA), 2014 IEEE International Conference on . doi : 10.1109 / ICRA.2014.6907328 . S2CID 14719083 .
- ^ Marzinotto, Alejandro; Colledanchise, Michele; Smith, Christian; Ögren, Petter (2014). "Hacia un marco de BT unificado para el control de robots" (PDF) . Robótica y Automatización (ICRA), 2014 IEEE International Conference on .
- ^ Klöckner, Andreas. "Conectar BT con el mundo mediante la lógica descriptiva". En la Conferencia de Orientación, Navegación y Control de AIAA, Boston, MA. 2013.
- ^ Klöckner, Andreas (2013). "Árboles de comportamiento para la gestión de misiones UAV". GI-Jahrestagung . págs. 57–68.
- ^ Bagnell, J. Andrew; Cavalcanti, Felipe; Cui, Lei; et al. (2012). "Un sistema integrado para la manipulación robótica autónoma" (PDF) . Robots y sistemas inteligentes (IROS), Conferencia internacional IEEE / RSJ de 2012 sobre . IEEE. págs. 2955-2962. doi : 10.1109 / IROS.2012.6385888 . hdl : 20.500.11937 / 14608 . ISBN 978-1-4673-1736-8. S2CID 419179 .
- ^ Millington; Funge (2009). Inteligencia artificial para juegos . Prensa CRC. ISBN 978-0-12-374731-0.
- ^ Rabin, S. (2014). Juego AI Pro . Prensa CRC. ISBN 978-1-4665-6596-8.
- ^ Champandard, Alex J .; Dunstan, Philip (2012). "Kit de inicio del árbol de comportamiento" (PDF) . Game AI Pro: sabiduría recopilada de los profesionales de la inteligencia artificial del juego . págs. 72–92.
- ^ craft ai (2015). "BT 101 - conceptos básicos de gramática de árboles de comportamiento" .
- ^ Colledanchise, Michele; Ögren, Petter (2014). "Cómo los árboles de comportamiento modularizan la robustez y la seguridad en los sistemas híbridos" (PDF) . En Intelligent Robots and Systems (IROS), 2014 IEEE / RSJ International Conference on . IEEE.
enlaces externos
- Biblioteca de árbol de comportamiento ROS
- Documentación del árbol de comportamiento de Unreal Engine 4
- Árboles de comportamiento para la IA: cómo funcionan
- Árboles de comportamiento: IA simple pero potente para su robot