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

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

Фон

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

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

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

Ключевые понятия

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

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

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

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

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

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

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

1 for i from 1 to n do2     childstatus ← Tick(child(i))3     if childstatus = running4         return running5     else if childstatus = success6         return success7 end8 return failure

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

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

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

1 for i from 1 to n do2     childstatus ← Tick(child(i))3     if childstatus = running4         return running5     else if childstatus = failure6         return failure7 end8 return success

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

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

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

где $i\in \mathbb {N}$ индекс дерева, $f_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}$ — векторное поле, представляющее правую часть обыкновенного разностного уравнения, $\Delta t$ это шаг по времени и $r_{i}:\mathbb {R} ^{n}\rightarrow \{R_{i},S_{i},F_{i}\}$ — это статус возврата, который может быть равен либо Бег $R_{i}$ ,Успех $S_{i}$ , илиОтказ $F_{i}$ .

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

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

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

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

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

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

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

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

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

Затем вернуть статус $r_{0}$ и векторное поле $f_{0}$ связанный с $T_{0}$ определены (для ${\mathcal {S}}_{1}$ ^{[ необходимо определение ]}) следующее:

$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}}$

$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}}$

См. также

Ссылки

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

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

[Colledanchise_TRO16-1] Колледанчиз, Мишель; Огрен, Петтер (2017). «Как деревья поведения модулируют гибридные системы управления и обобщают последовательные композиции поведения, архитектуру включения и деревья решений» . Транзакции IEEE в робототехнике . 33 (2): 372–389. дои : 10.1109/TRO.2016.2633567 . S2CID 9518238 .

[Colledanchise_BOOK17-2] Колледашизе, Мишель; Огрен, Питер (2018). Деревья поведения в робототехнике и искусственном интеллекте: введение . ЦРК Пресс. arXiv : 1709.00084 . дои : 10.1201/9780429489105 . ISBN 978-1-138-59373-2 . S2CID 27470659 .

[Damian_Isla-3] Исла, Д. (2005). «Управление сложностью в Halo 2 AI» . Конференция разработчиков игр (Том 12) .

[Damian_Isla2-4] Исла, Д. (2008). Halo 3: построение лучшей битвы . {{cite book}}: |work= игнорируется ( помогите )

[agis2020-5] Перейти обратно: ^а ^б Агис, Рамиро А.; Готтифреди, Себастьян; Гарсия, Алехандро Х. (2020). «Расширение деревьев поведения, управляемых событиями, для облегчения многоагентной координации без игроков в видеоиграх» (PDF) . Экспертные системы с приложениями . 155 (1): 113457. doi : 10.1016/j.eswa.2020.113457 . S2CID 218995637 .

[lim-6] Лим, CU; Баумгартен, Р.; Колтон, С. (2010). «Развитие деревьев поведения для коммерческой игры DEFCON» (PDF) . Приложения эволюционных вычислений . Конспекты лекций по информатике. Том. 6024. Берлин: Шпрингер. стр. 100–110. дои : 10.1007/978-3-642-12239-2_11 . ISBN 978-3-642-12238-5 .

[ogren2-7] Огрен, Петтер (2012). «Повышение модульности систем управления БПЛА с использованием деревьев поведения компьютерных игр» (PDF) . Конференция AIAA по руководству, навигации и управлению, Миннеаполис, Миннесота . стр. 13–16.

[colledanchise-8] Колледанчиз, Мишель; Марзинотто, Алехандро; Огрен, Петтер (2014). «Анализ производительности деревьев стохастического поведения» (PDF) . 2014 Международная конференция IEEE по робототехнике и автоматизации (ICRA) . стр. 3265–3272. дои : 10.1109/ICRA.2014.6907328 . ISBN 978-1-4799-3685-4 . S2CID 14719083 .

[marzonotto-9] Марзинотто, Алехандро; Колледанчиз, Мишель; Смит, Кристиан; Огрен, Петтер (2014). «На пути к единой платформе BT для управления роботами» (PDF) . Робототехника и автоматизация (ICRA), Международная конференция IEEE 2014 г., посвященная .

[Klocker-10] Клёкнер, Андреас. «Взаимодействие BT с миром с использованием логики описания». На конференции AIAA по руководству, навигации и управлению, Бостон, Массачусетс. 2013.

[Klocker2-11] Клёкнер, Андреас (2013). «Деревья поведения для управления миссиями БПЛА». Ежегодное собрание ГИ . стр. 57–68.

[Bagnell-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 .

[Millington-13] Миллингтон; Фунге (2009). Искусственный интеллект для игр . ЦРК Пресс. ISBN 978-0-12-374731-0 .

[Rabin-14] Рабин, С. (2014). Игра AI Pro . ЦРК Пресс. ISBN 978-1-4665-6596-8 .

[champandard2012-15] Шампандар, Алекс Дж.; Данстан, Филип (2012). «Начальный набор дерева поведения» (PDF) . Game AI Pro: Собранная мудрость профессионалов Game AI . стр. 72–92.

[craft_ai-16] ремесло ИИ (2015). «BT 101 – Основы грамматики деревьев поведения» .

[colledanchise2-17] Колледанчиз, Мишель; Огрен, Петтер (2014). «Как деревья поведения модулируют надежность и безопасность в гибридных системах» (PDF) . Международная конференция IEEE/RSJ 2014 г. по интеллектуальным роботам и системам (IROS), посвященная . IEEE.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]