Дерево поведения является математической моделью из плана выполнения , используемое в вычислительной технике , робототехнике , системы управления и видеоиграх . Они описывают переключение между конечным набором задач по модульному принципу. Их сила заключается в их способности создавать очень сложные задачи, состоящие из простых задач, не беспокоясь о том, как простые задачи реализуются. Деревья поведения имеют некоторое сходство с иерархическими конечными автоматами.с той ключевой разницей, что основным строительным блоком поведения является задача, а не состояние. Простота понимания человеком делает деревья поведения менее подверженными ошибкам и очень популярными в сообществе разработчиков игр. Было показано, что деревья поведения обобщают несколько других архитектур управления. [1] [2] Математически это ориентированные ациклические графы .
Задний план
Поведенческие деревья происходят из индустрии компьютерных игр , как мощный инструмент для моделирования поведения в неигровых персонажей (НПС). [3] [4] [5] [6] Они широко использовались в громких видеоиграх, таких как Halo , Bioshock и Spore . Недавние работы предлагают деревья поведения в качестве основы управления несколькими миссиями для БПЛА , сложных роботов, роботизированных манипуляций и систем с несколькими роботами. [7] [8] [9] [10] [11] [12] Теперь деревья поведения достигли зрелости, чтобы их можно было рассматривать в учебниках по игровому ИИ, [13] [14], а также в общих игровых средах, таких как Unity (game engine) и Unreal Engine (см. ссылки ниже).
Деревья поведения стали популярными благодаря своей парадигме разработки: возможность создавать сложное поведение только путем программирования действий NPC и последующего проектирования древовидной структуры (обычно с помощью перетаскивания ), конечные узлы которой являются действиями, а внутренние узлы определяют принятие решений NPC. Деревья поведения визуально интуитивно понятны, их легко проектировать, тестировать и отлаживать, они обеспечивают большую модульность, масштабируемость и возможность повторного использования, чем другие методы создания поведения.
С годами различные реализации деревьев поведения продолжали улучшаться как по эффективности, так и по возможностям для удовлетворения требований отрасли, пока не превратились в деревья поведения, управляемые событиями . [15] [5] Управляемые событиями деревья поведения решили некоторые проблемы масштабируемости классических деревьев поведения, изменив способ внутренней обработки дерева своим выполнением и введя новый тип узла, который может реагировать на события и прерывать работу узлов. В настоящее время концепция дерева поведения, управляемого событиями, является стандартом и используется в большинстве реализаций, хотя для простоты они все еще называются «деревьями поведения».
Ключевые идеи
Дерево поведения графически представлено как ориентированное дерево, в котором узлы классифицируются как корневые, узлы потока управления или узлы выполнения (задачи). Для каждой пары подключенных узлов исходящий узел называется родительским, а входящий узел - дочерним. У корня нет родителей и ровно одного дочернего элемента, у узлов потока управления есть один родительский элемент и хотя бы один дочерний элемент, а у исполнительных узлов есть один родительский элемент и нет дочерних элементов. Графически дочерние элементы узла потока управления расположены под ним в порядке слева направо. [16]
Выполнение дерева поведения начинается с корня, который с определенной частотой отправляет тики своему дочернему элементу. Галочка - это разрешающий сигнал, разрешающий казнь ребенка. Когда выполнение узла в дереве поведения разрешено, он возвращает родительскому элементу статус выполнения, если его выполнение еще не завершено, успех, если он достиг своей цели, или сбой в противном случае.
Узел потока управления
Узел потока управления используется для управления подзадачами, из которых он состоит. Узел потока управления может быть либо узлом селектора (резервным), либо узлом последовательности. Они по очереди выполняют каждую из своих подзадач. Когда подзадача завершена и возвращает свой статус (успех или неудача), узел потока управления решает, выполнять следующую подзадачу или нет.
Селекторный (резервный) узел
Резервные узлы используются для поиска и выполнения первого исправного дочернего элемента. Резервный узел немедленно вернется с кодом состояния успеха или выполнения, когда один из его дочерних узлов вернет успех или выполнение (см. Рисунок I и псевдокод ниже). Дети отмечены в порядке важности слева направо.
В псевдокоде алгоритм резервной композиции:
1 для я от 1 до n делать2 childstatus ← Отметьте (ребенок (i))3, если childstatus = running4 обратный ход5 иначе, если childstatus = успех6 вернуть успех7 конец 8 возврат неудачи
Узел последовательности
Узлы последовательности используются для поиска и выполнения первого дочернего элемента, который еще не завершился успешно. Узел последовательности немедленно вернется с кодом состояния сбоя или выполнения, когда один из его дочерних узлов вернет сбой или выполнение (см. Рисунок II и псевдокод ниже). Дети отмечены галочками слева направо.
В псевдокоде алгоритм композиции последовательности:
1 для я от 1 до n делать2 childstatus ← Отметьте (ребенок (i))3, если childstatus = running4 обратный ход5 иначе, если childstatus = failure6 возврат отказа7 конец 8 вернуть успех
Математическое определение пространства состояний
Чтобы применить инструменты теории управления к анализу деревьев поведения, их можно определить как трехкортежные. [17]
где это индекс дерева, - векторное поле, представляющее правую часть обыкновенного разностного уравнения, это временной шаг и - это статус возврата, который может быть равен либо «Работает» , Успех , или отказ .
Примечание . Задача - это вырожденное дерево поведения без родительского и дочернего элементов.
Выполнение дерева поведения
Выполнение дерева поведения описывается следующими стандартными обыкновенными разностными уравнениями:
где представляют дискретное время, а пространство состояний системы, моделируемой деревом поведения.
Состав последовательности
Два дерева поведения а также можно объединить в более сложное дерево поведения с помощью оператора последовательности.
Затем вернуть статус и векторное поле связаны с определены (для [ требуется определение ] ) следующим образом:
Смотрите также
Рекомендации
- ^ Colledanchise, Микеле; Огрен, Петтер (2017). «Как деревья поведения модулируют гибридные системы управления и обобщают последовательности последовательного поведения, архитектуру подчинения и деревья решений» . IEEE Transactions по робототехнике . 33 (2): 372–389. DOI : 10.1109 / TRO.2016.2633567 . S2CID 9518238 .
- ^ Colledanchise, Микеле; Огрен, Петтер (2018). Деревья поведения в робототехнике и искусственном интеллекте: введение . CRC Press. arXiv : 1709,00084 . DOI : 10.1201 / 9780429489105 . ISBN 978-1-138-59373-2. S2CID 27470659 .
- ^ Исла, Д. (2005). «Управление сложностью в Halo 2 AI» . Конференция разработчиков игр (Том 12) .
- ^ Исла, Д. (2008). Halo 3 - построение лучшей битвы . Game Developers Conference 2008 .
- ^ а б Agis, Ramiro A .; Готтифреди, Себастьян; Гарсия, Алехандро Х. (2020). «Расширение деревьев поведения, управляемого событиями, для облегчения координации действий нескольких агентов, не связанных с игроками, в видеоиграх» (PDF) . Экспертные системы с приложениями . 155 (1): 113457. DOI : 10.1016 / j.eswa.2020.113457 .
- ^ Lim, CU; Baumgarten, R .; Колтон, С. (2010). «Развивающиеся деревья поведения для коммерческой игры DEFCON» (PDF) . Приложения эволюционных вычислений . Берлин: Springer. С. 100–110. DOI : 10.1007 / 978-3-642-12239-2_11 . ISBN 978-3-642-12238-5.
- ^ Огрен, Петтер (2012). «Повышение модульности систем управления БПЛА с использованием деревьев поведения компьютерных игр» (PDF) . Конференция AIAA по руководству, навигации и управлению, Миннеаполис, Миннесота . С. 13–16.
- ^ Colledanchise, Микеле; Марзинотто, Алехандро; Огрен, Петтер (2014). «Анализ производительности стохастических BT» (PDF) . Робототехника и автоматика (ICRA), 2014 IEEE Международная конференция по . DOI : 10.1109 / ICRA.2014.6907328 . S2CID 14719083 .
- ^ Марзинотто, Алехандро; Colledanchise, Микеле; Смит, Кристиан; Огрен, Петтер (2014). «На пути к единой платформе BT для управления роботами» (PDF) . Робототехника и автоматика (ICRA), 2014 IEEE Международная конференция по .
- ^ Klöckner, Андреас. «Сопряжение ТТ с миром с помощью логики описания». На конференции AIAA по руководству, навигации и управлению, Бостон, Массачусетс. 2013.
- ^ Клёкнер, Андреас (2013). "Деревья поведения для управления полетами БПЛА". GI-Jahrestagung . С. 57–68.
- ^ Багнелл, Дж. Эндрю; Кавальканти, Фелипе; Цуй, Лей; и другие. (2012). «Интегрированная система для автономных манипуляций робототехникой» (PDF) . Интеллектуальные роботы и системы (IROS), 2012 IEEE / RSJ Международной конференции по . IEEE. С. 2955–2962. DOI : 10.1109 / IROS.2012.6385888 . ЛВП : 20.500.11937 / 14608 . ISBN 978-1-4673-1736-8. S2CID 419179 .
- ^ Миллингтон; Funge (2009). Искусственный интеллект для игр . CRC Press. ISBN 978-0-12-374731-0.
- ^ Рабин, С. (2014). Игра AI Pro . CRC Press. ISBN 978-1-4665-6596-8.
- ^ Шампандард, Алекс Дж .; Дунстан, Филипп (2012). «Стартовый комплект дерева поведения» (PDF) . Game AI Pro: Сборник мудрости профессионалов в области игрового ИИ . С. 72–92.
- ^ Крафт ИИ (2015). "BT 101 - основы грамматики Behavior Trees" .
- ^ Colledanchise, Микеле; Огрен, Петтер (2014). «Как деревья поведения модулируют надежность и безопасность в гибридных системах» (PDF) . В «Интеллектуальных роботах и системах» (IROS), Международная конференция IEEE / RSJ, 2014 г., посвященная . IEEE.
Внешние ссылки
- Библиотека дерева поведения ROS
- Документация по дереву поведения Unreal Engine 4
- Деревья поведения для ИИ: как они работают
- Деревья поведения: простой, но мощный ИИ для вашего робота