Дерево поведения (искусственный интеллект, робототехника и управление)

Математическая модель исполнения плана

Дерево поведения — это математическая модель выполнения плана, используемая в информатике , робототехнике , системах управления и видеоиграх . Они описывают переключение между конечным набором задач по модульному принципу. Их сила заключается в способности создавать очень сложные задачи, состоящие из простых задач, не беспокоясь о том, как простые задачи реализуются. Деревья поведения имеют некоторое сходство с иерархическими конечными автоматами с тем ключевым отличием, что основным строительным блоком поведения является задача, а не состояние. Простота человеческого понимания делает деревья поведения менее подверженными ошибкам и очень популярными в сообществе разработчиков игр. Было показано, что деревья поведения обобщают несколько других архитектур управления. ^{[1] [2]}

Дерево поведения, моделирующее план поиска и захвата двурукого робота

Фон

Структура управления, основанная на поведении, была первоначально предложена Родни Бруксом в его статье под названием «Надежная многоуровневая система управления для мобильного робота». В первоначальном предложении список поведений ^мог работать как альтернатива друг другу, позже подход был расширен и обобщен в древовидной организации поведений с широким применением в игровой индустрии ^{в качестве} мощного инструмента для моделирования поведение неигровых персонажей ( NPC). ^{[3] [4] [5] [6]} Они широко использовались в таких громких видеоиграх, как Halo , Bioshock и Spore . В недавних работах деревья поведения предлагаются в качестве многоцелевой системы управления БПЛА , сложными роботами, роботизированными манипуляциями и системами с несколькими роботами. ^{[7] [8] [9] [10] [11] [12]} Деревья поведения теперь достигли той степени зрелости, которую можно рассматривать в учебниках по игровому ИИ, ^{[13] [14],} а также в общих игровых средах, таких как Unity (игровые engine) и Unreal Engine (см. ссылки ниже).

Деревья поведения стали популярными благодаря своей парадигме разработки: возможность создавать сложное поведение, только программируя действия NPC, а затем проектируя древовидную структуру (обычно посредством перетаскивания ), чьи конечные узлы являются действиями, а внутренние узлы определяют принятие решений NPC. Деревья поведения визуально интуитивно понятны, их легко проектировать, тестировать и отлаживать, а также они обеспечивают большую модульность, масштабируемость и возможность повторного использования, чем другие методы создания поведения.

На протяжении многих лет разнообразные реализации деревьев поведения продолжали улучшаться как по эффективности, так и по возможностям удовлетворения потребностей отрасли, пока не превратились в деревья поведения , управляемые событиями . ^{[15] [5]} Деревья поведения, управляемые событиями, решили некоторые проблемы масштабируемости классических деревьев поведения, изменив способ внутреннего выполнения дерева и представив новый тип узла, который может реагировать на события и прерывать выполнение узлов. В настоящее время концепция дерева поведения, управляемого событиями, является стандартом и используется в большинстве реализаций, хотя для простоты их до сих пор называют «деревьями поведения».

Ключевые идеи

Дерево поведения графически представляется в виде ориентированного дерева , узлы которого классифицируются как корневые, узлы потока управления или узлы выполнения (задачи). Для каждой пары связанных узлов исходящий узел называется родительским, а входящий узел называется дочерним. У корня нет родителей и ровно один дочерний элемент, у узлов потока управления есть один родительский элемент и хотя бы один дочерний элемент, а у узлов выполнения — один родительский элемент и нет дочерних элементов. Графически дочерние элементы узла потока управления располагаются под ним, упорядоченные слева направо. ^[16]

Выполнение дерева поведения начинается с корня, который с определенной частотой отправляет тики своему дочернему элементу. Галочка – разрешающий сигнал, разрешающий выполнение дочернего элемента. Когда выполнение узла в дереве поведения разрешено, он возвращает родительскому узлу статус выполнения, если его выполнение еще не завершено, успех , если он достиг своей цели, или отказ в противном случае.

Узел потока управления

Узел потока управления используется для управления подзадачами, из которых он состоит. Узел потока управления может быть либо узлом выбора (резервного) узла, либо узлом последовательности. Они по очереди выполняют каждую из своих подзадач. Когда подзадача завершена и возвращает свой статус (успех или неудача), узел потока управления решает, выполнять следующую подзадачу или нет.

Селекторный (резервный) узел

Рисунок I. Графическое представление резервной композиции из N задач.

Резервные узлы используются для поиска и выполнения первого дочернего узла, который не вышел из строя. Резервный узел вернется с кодом состояния успеха или работы сразу же, как только один из его дочерних узлов вернет успех или работу (см. рисунок I и псевдокод ниже). Дети отмечены галочками в порядке важности слева направо.

В псевдокоде алгоритм резервной композиции следующий:

1 для я от 1 до n делать2 childstatus ← Tick(child(i))3 , если статус ребенка = работает4 возвратный бег5 иначе, если статус ребенка = успех6 возврат успеха7 конец
8 возврат неудачи

Узел последовательности

Рисунок II. Графическое представление последовательности из N задач.

Узлы последовательности используются для поиска и выполнения первого дочернего элемента, который еще не завершился успешно. Узел последовательности вернется с кодом состояния «сбой» или «работает» немедленно, когда один из его дочерних элементов вернет «сбой» или «работает» (см. рисунок II и псевдокод ниже). Дети отмечены галочками по порядку, слева направо.

В псевдокоде алгоритм композиции последовательности:

1 для я от 1 до n делать2 childstatus ← Tick(child(i))3 , если статус ребенка = работает4 возвратный бег5 иначе, если статус ребенка = неудача6 возврат неудачи7 конец
8 возврат успеха

Математическое определение пространства состояний

Чтобы применить инструменты теории управления к анализу деревьев поведения, их можно определить как трехкортежные. ^[17]

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

где — индекс дерева, — векторное поле, представляющее правую часть обычного разностного уравнения, — временной шаг и — статус возврата, который может быть равен «Выполнение» , «Успех » или «Ошибка» . ${\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}}$

Примечание . Задача представляет собой вырожденное дерево поведения без родительского и дочернего элементов.

Выполнение дерева поведения

Выполнение дерева поведения описывается следующими стандартными обыкновенными разностными уравнениями:

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

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

где представляют собой дискретное время, а – пространство состояний системы, моделируемое деревом поведения. ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle x\in \mathbb {R} ^{n}}$

Состав последовательности

Два дерева поведения , которые можно объединить в более сложное дерево поведения с помощью оператора Sequence. ${\displaystyle T_{i}}$ ${\displaystyle T_{j}}$ ${\displaystyle T_{0}}$

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

Затем статус возврата и связанное с ним векторное поле определяются (для ^{[ необходимо определение ]} ) следующим образом: ${\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}}}$

Смотрите также

• Древо решений
• Гибридная система
• Архитектура подчинения

Рекомендации

1. Колледаншизе, Мишель; Огрен, Петтер (2017). «Как деревья поведения модулируют гибридные системы управления и обобщают последовательные композиции поведения, архитектуру включения и деревья решений». Транзакции IEEE в робототехнике . 33 (2): 372–389. дои : 10.1109/TRO.2016.2633567. S2CID  9518238.
2. Колледаншизе, Мишель; Огрен, Петтер (2018). Деревья поведения в робототехнике и искусственном интеллекте: введение . ЦРК Пресс. arXiv : 1709.00084 . дои : 10.1201/9780429489105. ISBN 978-1-138-59373-2. S2CID  27470659.
3. Исла, Д. (2005). «Обработка сложности в AI Halo 2». Конференция разработчиков игр (Том 12) .
4. Исла, Д. (2008). Halo 3: построение лучшей битвы . {{cite book}}: |work=игнорируется ( помощь )
5. Агис, Рамиро А.; Готтифреди, Себастьян; Гарсия, Алехандро Х. (2020). «Расширение деревьев поведения, управляемых событиями, для облегчения многоагентной координации без игроков в видеоиграх» (PDF) . Экспертные системы с приложениями . 155 (1): 113457. doi :10.1016/j.eswa.2020.113457. S2CID  218995637.
6. Лим, CU; Баумгартен, Р.; Колтон, С. (2010). «Развитие деревьев поведения для коммерческой игры DEFCON» (PDF) . Приложения эволюционных вычислений . Конспекты лекций по информатике. Том. 6024. Берлин: Шпрингер. стр. 100–110. дои : 10.1007/978-3-642-12239-2_11. ISBN 978-3-642-12238-5.
7. Огрен, Петтер (2012). «Повышение модульности систем управления БПЛА с использованием деревьев поведения компьютерных игр» (PDF) . Конференция AIAA по руководству, навигации и управлению, Миннеаполис, Миннесота . стр. 13–16.
8. Колледаншизе, Мишель; Марцинотто, Алехандро; Огрен, Петтер (2014). «Анализ производительности деревьев стохастического поведения» (PDF) . 2014 Международная конференция IEEE по робототехнике и автоматизации (ICRA) . стр. 3265–3272. дои : 10.1109/ICRA.2014.6907328. ISBN 978-1-4799-3685-4. S2CID  14719083.
9. Марцинотто, Алехандро; Колледанчиз, Мишель; Смит, Кристиан; Огрен, Петтер (2014). «На пути к единой платформе BT для управления роботами» (PDF) . Робототехника и автоматизация (ICRA), Международная конференция IEEE 2014 г., посвященная .
10. Клёкнер, Андреас. «Взаимодействие BT с миром с использованием логики описания». На конференции AIAA по руководству, навигации и управлению, Бостон, Массачусетс. 2013.
11. Клёкнер, Андреас (2013). «Деревья поведения для управления миссиями БПЛА». GI-Jahretagung . стр. 57–68.
12. Багнелл, Дж. Эндрю; Кавальканти, Фелипе; Цуи, Лей; и другие. (2012). «Интегрированная система автономного манипулирования робототехникой» (PDF) . Интеллектуальные роботы и системы (IROS), Международная конференция IEEE/RSJ 2012 г., посвященная . IEEE. стр. 2955–2962. дои : 10.1109/IROS.2012.6385888. hdl : 20.500.11937/14608. ISBN 978-1-4673-1736-8. S2CID  419179.
13. Миллингтон; Фунге (2009). Искусственный интеллект для игр . ЦРК Пресс. ISBN 978-0-12-374731-0.
14. Рабин, С. (2014). Игра AI Pro . ЦРК Пресс. ISBN 978-1-4665-6596-8.
15. Шампандар, Алекс Дж.; Данстан, Филип (2012). «Начальный набор дерева поведения» (PDF) . Game AI Pro: мудрость профессионалов в области игрового AI . стр. 72–92.
16. ремесло ИИ (2015). «BT 101 - Основы грамматики деревьев поведения».
17. Колледаншизе, Мишель; Огрен, Петтер (2014). «Как деревья поведения модулируют надежность и безопасность в гибридных системах» (PDF) . Международная конференция IEEE/RSJ 2014 г. по интеллектуальным роботам и системам (IROS), посвященная . IEEE.

Внешние ссылки

• Библиотека деревьев поведения ROS
• Документация по дереву поведения Unreal Engine 4
• Деревья поведения для ИИ: как они работают
• Деревья поведения: простой, но мощный искусственный интеллект для вашего робота. Архивировано 25 февраля 2020 г. на Wayback Machine.
• Видеолекции по деревьям поведения