Árbol de comportamiento (inteligencia artificial, robótica y control)

Modelo matemático de ejecución del plan

Un árbol de comportamiento es un modelo matemático de ejecución de planes utilizado 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 de tareas simples, sin preocuparse de cómo se implementan las tareas simples. Los árboles de comportamiento presentan algunas similitudes con las máquinas de estados 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]}

Árbol de comportamiento que modela el plan de búsqueda y agarre de un robot de dos brazos

Fondo

Una estructura de control basada en el comportamiento fue propuesta inicialmente por Rodney Brooks en su artículo titulado 'Un sistema de control robusto en capas para un robot móvil'. En la propuesta inicial, una lista de comportamientos podría funcionar como alternativa entre sí, más tarde el enfoque se ha extendido y generalizado en una organización de comportamientos en forma de árbol, con una amplia aplicación en la industria del juego ^{[ cita requerida ]} como una poderosa herramienta para modelar el comportamiento de 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 multimisión para UAV , robots complejos, manipulación robótica y sistemas multi-robot. ^{[7] [8] [9] [10] [11] [12]} Los árboles de comportamiento ahora han alcanzado la madurez para ser tratados en libros de texto de Game AI, ^{[13] [14]} así como en entornos de juego genéricos como Unity (motor de juego) y Unreal Engine (ver enlaces a continuación).

Los árboles de comportamiento se hicieron populares por su paradigma de desarrollo: poder crear un comportamiento complejo con solo programar las acciones del NPC y luego diseñar una estructura de árbol (generalmente mediante arrastrar y soltar ) cuyos nodos de 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 brindan 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 impulsados ​​por eventos resolvieron algunos problemas de escalabilidad de los árboles de comportamiento clásicos al cambiar la forma en que el árbol maneja internamente su ejecución y al introducir 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 los llama "á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 denomina padre y el nodo entrante se denomina hijo. El nodo raíz no tiene padres y tiene 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. ^[16]

La ejecución de un árbol de comportamientos comienza desde la raíz, que envía ticks con una frecuencia determinada a su hijo. Un tick es una señal de habilitación que permite la ejecución de un hijo. Cuando se permite la ejecución de un nodo del árbol de comportamientos, este devuelve al padre un estado de ejecución si su ejecución aún no ha finalizado, éxito si ha alcanzado 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 se completa una subtarea y devuelve su estado (éxito o fracaso), el nodo de flujo de control decide si ejecutar la siguiente subtarea o no.

Nodo selector (de reserva)

Figura I. Representación gráfica de una composición de respaldo de N tareas.

Los nodos de reserva se utilizan para buscar y ejecutar el primer nodo secundario que no falla. Un nodo de reserva regresará con un código de estado de éxito o en ejecución inmediatamente cuando uno de sus nodos secundarios devuelva éxito o en ejecución (consulte la Figura I y el pseudocódigo a continuación). Los nodos secundarios se marcan en orden de importancia, de izquierda a derecha.

En pseudocódigo, el algoritmo para una composición de respaldo es:

1 para i de 1 a n hacer2 estado del niño ← Marcar(niño(i))3 si el estado del niño = en ejecución4 retorno corriendo5 de lo contrario, si el estado del niño es exitoso6 retorno exitoso7. Fin
8. Fallo de retorno

Nodo de secuencia

Figura II. Representación gráfica de una composición secuencial de N tareas.

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á con un código de estado de falla o en ejecución inmediatamente cuando uno de sus hijos regrese con falla o en ejecución (consulte la Figura II y el pseudocódigo a continuación). Los hijos se marcan en orden, de izquierda a derecha.

En pseudocódigo, el algoritmo para una composición de secuencia es:

1 para i de 1 a n hacer2 estado del niño ← Marcar(niño(i))3 si el estado del niño = en ejecución4 retorno corriendo5 de lo contrario, si el estado del niño es igual a fracaso6 fallos de retorno7 fin
8 regreso éxito

Definición de espacio de estados matemáticos

Para aplicar herramientas de la teoría de control al análisis de árboles de comportamiento, estos pueden definirse como tres-tuplas. ^[17]

${\displaystyle T_{i}=\{f_{i},r_{i},\Delta t\},}$

donde es el índice del árbol, es un campo vectorial que representa el lado derecho de una ecuación diferencial ordinaria, es un paso de tiempo y es el estado de retorno, que puede ser igual a En ejecución , Éxito o Falla . ${\displaystyle i\in \mathbb {N} }$ ${\displaystyle f_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}$ ${\displaystyle \Delta t}$ ${\displaystyle r_{i}:\mathbb {R} ^{n}\rightarrow \{R_{i},S_{i},F_{i}\}}$ ${\displaystyle R_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle F_{i}}$

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 diferenciales ordinarias estándar:

${\displaystyle x_{k+1}(t_{k+1})=f_{i}(x_{k}(t_{k}))}$

${\displaystyle t_{k+1}=t_{k}+\Delta t}$

donde representa el tiempo discreto, y es el espacio de estados del sistema modelado por el árbol de comportamiento. ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle x\in \mathbb {R} ^{n}}$

Composición de la secuencia

Dos árboles de comportamiento se pueden componer en un árbol de comportamiento más complejo utilizando un operador de secuencia. ${\displaystyle T_{i}}$ ${\displaystyle T_{j}}$ ${\displaystyle T_{0}}$

${\displaystyle T_{0}={\mbox{sequence}}(T_{i},T_{j}).}$

Luego, el estado de retorno y el campo vectorial asociado se definen (para ^{[ definición necesaria ]} ) de la siguiente manera: ${\displaystyle r_{0}}$ ${\displaystyle f_{0}}$ ${\displaystyle T_{0}}$ ${\displaystyle {\mathcal {S}}_{1}}$

${\displaystyle r_{0}(x_{k})={\begin{cases}r_{j}(x_{k})&{\text{ if }}x_{k}\in {\mathcal {S}}_{1}\\r_{i}(x_{k})&{\text{ otherwise }}.\end{cases}}}$

${\displaystyle f_{0}(x_{k})={\begin{cases}f_{j}(x_{k})&{\text{ if }}x_{k}\in {\mathcal {S}}_{1}\\f_{i}(x_{k})&{\text{ otherwise }}.\end{cases}}}$

Véase también

• Árbol de decisión
• Sistema híbrido
• Arquitectura de subsunción

Referencias

1. Colledanchise, Michele; Ögren, Petter (2017). "Cómo los árboles de comportamiento modularizan los sistemas de control híbridos y generalizan las composiciones de comportamiento secuencial, la arquitectura de subsunción y los árboles de decisión". IEEE Transactions on Robotics . 33 (2): 372–389. doi :10.1109/TRO.2016.2633567. S2CID  9518238.
2. Colledanchise, Michele; Ögren, Petter (2018). Árboles de comportamiento en robótica e inteligencia artificial: una introducción . CRC Press. arXiv : 1709.00084 . doi :10.1201/9780429489105. ISBN . 978-1-138-59373-2. Número de identificación del sujeto  27470659.
3. Isla, D. (2005). "Manejo de la complejidad en la IA de Halo 2". Game Developers Conference (Vol. 12) .
4. Isla, D. (2008). Halo 3: cómo construir una mejor batalla . {{cite book}}: |work=ignorado ( ayuda )
5. Agis, Ramiro A.; Gottifredi, Sebastian; García, Alejandro J. (2020). "Una extensión de árboles de comportamiento impulsados ​​por eventos para facilitar la coordinación multiagente sin jugadores en videojuegos" (PDF) . Sistemas expertos con aplicaciones . 155 (1): 113457. doi :10.1016/j.eswa.2020.113457. S2CID  218995637.
6. Lim, CU; Baumgarten, R.; Colton, S. (2010). "Evolución de árboles de comportamiento para el juego comercial DEFCON" (PDF) . Aplicaciones de la computación evolutiva . Apuntes de clase en informática. Vol. 6024. Berlín: Springer. págs. 100-110. doi :10.1007/978-3-642-12239-2_11. ISBN 978-3-642-12238-5.
7. Ögren, Petter (2012). "Aumento de la modularidad de los sistemas de control de vehículos aéreos no tripulados mediante árboles de comportamiento de juegos de ordenador" (PDF) . Conferencia de guía, navegación y control de la AIAA, Minneapolis, Minnesota . págs. 13–16.
8. Colledanchise, Michele; Marzinotto, Alejandro; Ögren, Petter (2014). "Análisis de rendimiento de árboles de comportamiento estocástico" (PDF) . 2014 IEEE International Conference on Robotics and Automation (ICRA) . pp. 3265–3272. doi :10.1109/ICRA.2014.6907328. ISBN . 978-1-4799-3685-4. Número de identificación del sujeto  14719083.
9. Marzinotto, Alejandro; Colledanchise, Michele; Smith, Christian; Ögren, Petter (2014). "Hacia un marco BTs unificado para el control de robots" (PDF) . Robótica y automatización (ICRA), Conferencia internacional IEEE 2014 sobre .
10. Klöckner, Andreas. "Interfaz de los BT con el mundo mediante lógica descriptiva". En la Conferencia de guía, navegación y control de la AIAA, Boston, MA, 2013.
11. Klockner, Andreas (2013). "Árboles de comportamiento para la gestión de misiones de vehículos aéreos no tripulados". GI-Jahrestagung . págs. 57–68.
12. 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. Número de identificación del sujeto  419179.
13. Millington; Funge (2009). Inteligencia artificial para juegos . CRC Press. ISBN 978-0-12-374731-0.
14. Rabin, S. (2014). Game AI Pro . Prensa CRC. ISBN 978-1-4665-6596-8.
15. Champandard, Alex J.; Dunstan, Philip (2012). "El kit de inicio del árbol de comportamiento" (PDF) . Game AI Pro: Recopilación de la sabiduría de los profesionales de la IA en juegos . pp. 72–92.
16. craft ai (2015). "BT 101 – Fundamentos gramaticales de árboles de comportamiento".
17. Colledanchise, Michele; Ögren, Petter (2014). "Cómo los árboles de comportamiento modularizan la robustez y la seguridad en sistemas híbridos" (PDF) . En Intelligent Robots and Systems (IROS), Conferencia internacional IEEE/RSJ de 2014 sobre . IEEE.

Enlaces externos

• Biblioteca de árboles de comportamiento de ROS
• Documentación del árbol de comportamiento de Unreal Engine 4
• Árboles de comportamiento para IA: cómo funcionan
• Árboles de comportamiento: IA simple pero poderosa para su robot Archivado el 25 de febrero de 2020 en Wayback Machine
• Videoconferencias sobre árboles de comportamiento