Behavior trees: Моделирование поведения интеллектуальных систем
Перед тем как мы начнем, я предлагаю совершить небольшое историческое путешествие примерно в 17-й век, так как именно в это время можно наблюдать появление механических кукол - автоматонов, предназначенных в основном для развлечения людей.
Несмотря на то, что первые автоматоны известны еще со времен Древней Греции, они несли в себе в основном утилитарную функцию и были очень редким явлением. По сути их можно назвать первыми роботами или их предшественниками. Положение вещей резко изменилось с изобретением в 1504 году заводной пружины для часов мастером из Нюрнберга - Питером Генлайном. Изобретение пружины для часов подстегнуло развитие механики, пружина стала движителем для большого количества новых изобретений на протяжении длительного временного периода, вплоть до 18-го века, когда появляются первые легендарные автоматоны, умеющие играть на музыкальных инструментах, писать, рисовать и даже играть в шахматы.
Но даже самые уникальные экземпляры не обладали тем уровнем интеллекта, о котором мечтали их создатели. Легендарный «Турок», обыгравший в шахматы Наполеона, по факту оказался автоматоном всего наполовину, и ровно на ту, которая перемещала фигуры по доске, а управлял им все же человек, который сидел в ящике – подставке для автомата.
С развитием электроники идеи и принципы, заложенные в автоматонах разделились: часть трансформировалось в робототехнику, а часть в первые электронные игры. Таким образом, роботы вернулись к своим истокам, и по образу и подобию древнегреческих механических помощников стали помогать человеку в повседневной жизни, а игровая индустрия оставила себе задачи развлекать человечество и начала активную эволюцию в этом сегменте.
Как известно, человеку всегда мало достигнутого, и с развитием технического прогресса росли требования к технике и ожидания от прогресса. В какой-то момент развития науки человек научился наделять машины зачатками интеллекта.
Понятие интеллекта.
Если посмотреть на этимологию слова «интеллект», то оно происходит от латинского «Intellectus», что обозначает восприятие. Конечно, если посмотреть на понятие интеллекта в широком смысле, то одного восприятия внешних воздействий и факторов будет недостаточно. В процессе исследования и описания интеллекта человека в психологии были выдвинуты теории о множественном интеллекте и сформулированы несколько типов интеллекта: ментальный интеллект (IQ), эмоциональный интеллект (EI), социальный интеллект (SI), духовный интеллект и физический интеллект. Вероятно, в ближайшее время появятся новые типы в результате высокого интереса к изучению данной области. Надо сказать, что все выявленные типы интеллекта построены на двух основных базисах - это восприятие чего-либо и реакция или поведение основанное на восприятии. Если вернуться обратно к точным наукам, то с задачей восприятия, формализации и классификации не формализованных данных замечательно справляются столь популярные на сегодня нейросети, а вот за реакцию на восприятие и формирование определенного поведения отвечают поведенческие модели.
Моделирование поведения при помощи Behavior tree.
Вопросы искусственного интеллекта волнуют человечество достаточно давно, и для описания поведенческих моделей была разработана масса различных нотаций. Каждая из них имеет свои достоинства и недостатки, и предназначена для применения в различных ситуациях.
Нотация Behavior tree впервые была предложена Родни Бруксом в 1985 году в своей статье «A robust layered control system for a mobile robot». Достаточно быстро эта нотация зарекомендовала себя в области программирования интеллектуальных систем. Она полюбилась разработчикам за простоту понимания структуры, что, в свою очередь, снижает вероятность появления ошибок при проектировании и разработке. Дерево описывает переключения между конечным набором задач в модульном виде. Его преимущество заключается в способности создавать очень сложные задачи, состоящие из простых задач, не беспокоясь о том, как реализуются простые задачи. Особенности структуры и модульного подхода к разработке функций позволяют практически безгранично масштабировать поведение системы, не внося изменении в конкретные реализации.
Графически дерево поведения представлено в виде направленного дерева. Для каждой пары связанных узлов исходящий узел называется родительским, а входящий узел называется дочерним. Узлы разделяются на два типа: узлы потока управления и узлы выполнения (узлы задач). Узлы потока управления имеют одного родителя и по крайней мере один дочерний узел, узлы выполнения имеют одного родителя и не имеют потомков. За базовые управляющие узлы принято брать Sequence node (узел последовательности) и Selector node (узел выбора). Сигналы, которыми обмениваются узлы, принимают следующие значения: failed, success, running. На узлах исполнения (Execution node) я хочу немного задержаться. Для простоты дальнейшего восприятия и для облегчения первых шагов в проектировании, несмотря на то, что узлы исполнения всегда возвращают одно из трех значения, их стоит рассматривать как процедуры, а не как функции. Значение, которое возвращает узел исполнения, является управляющим сигналом, а не результатом каких-либо вычислений или иной полезной работы, произведенной узлом. Давайте разберем каждый узел подробнее.
Узел последовательности (Sequence node).
Данный тип узла поочередно выполняет дочерние узлы в той последовательности, в которой они определены. Узел возвращает значение failed если хотя бы один дочерний узел вернул failed, в противном случае возвращает success. На диаграмме узел отображается следующим образом (См. рис. 1).
Последовательность выполнения дочерних элементов начинается с крайнего левого узла и заканчивается крайним правым (См. рис. 2).
Узел выбора (Selector node).
Данный тип узла запускает последовательно дочерние узлы пока один из них не вернет значение success и возвращает соответствующее значение, в противном случае возвращает failed. На диаграмме узел отображается следующим образом (См. рис. 3).
Последовательность выполнения узлов аналогична предыдущему узлу, и тоже производится слева направо (См. рис. 4).
Узел исполнения (Execution node).
Этот узел содержит ссылку на выполняемый код и может являться только дочерним, на диаграмме он выглядит следующим образом. (См. рис. 5).
Набор управляющих узлов не должен ограничиться базовым набором и может быть расширен любыми управляющими узлами, необходимых для выполнения конкретных задач.
Узел повтора (Loop node).
Для себя я добавил еще один управляющий узел - узел повтора (Loop node). Этот узел может иметь только одного потомка и продолжает его выполнение до того момента пока потомок не вернет failed, это значение передается родительскому узлу. На диаграмме узел выглядит следующим образом (См. рис. 6).
Вероятно вы заметили, что я не упомянул про управляющий сигнал running. Это не случайно. Я не забыл про него. Дело в том, что этот сигнал связан с еще одним полезным свойством дерева поведения, но об этом чуть позже. Сейчас предлагаю перейти от теории к практике.
Примеры.
Для удобства проектирования и отладки логики я разработал приложение, позволяющее визуально конструировать дерево, компилировать диаграмму в кодовую структуру и программировать конечные реализации узлов исполнения при помощи встроенного редактора (GitHub: https://github.com/sergey-k-lapin/bt_tool). В качестве языка программирования я выбрал JavaScript, что позволяет выполнять код модели непосредственно в браузере.
Для начала предлагаю реализовать простую конструкцию условного оператора
if ( condition ) {
// then execution
} else {
// else execution
}
при помощи дерева. Выглядеть это будет следующим образом (См. рис. 7).
Выполнение дерева начинается с корневого узла, на этой диаграмме это узел выбора, и продолжается сверху вниз. Начиная от корня, мы спустимся по левой ветке до узла исполнения if_conditon1 и при положительном результате передадим управление следующему узлу исполнения or_condition, от которого будет зависеть дальнейшее управление. Если ни один из узлов if_condition и or_condition не вернули failed, то узел выбора, являющегося для них родительским, тоже вернет значение success, что является сигналом узлу последовательности к выполнению следующего дочернего узла then_run_task.
В том случае, если узел последовательности получит значение failed, то он мгновенно перенаправит это значение корневому узлу. Так как корневой узел — это узел выбора, то сигнал failed будет означать переключение на следующей дочерний узел else_run_task и запуск его в попытке получить значение success. В противном случае, если корневой узел выбора получит сигнал success - это будет означать мгновенное окончание исполнения и выход.
Следующие важной языковой конструкцией в программировании являются циклы. Предлагаю немного усложнить задачу и сделать сразу два цикла, вложенные друг в друга и имеющие разные условия. В виде алгоритма на языке программирования конструкция будет выглядеть следующим образом:
do{
//loop_task
while( inner_loop_condition ) {
//inner_loop
}
} while( loop_post_condition)
В качестве диаграммы эта логика будет иметь следующий вид (См. рис. 8).
Здесь в качестве корня дерева выступает узел повтора. При выполнении дерева первым узлом выполнения будет узел loop_task, который всегда возвращает значение success, что автоматически передает управление узлу выбора. При дальнейшем выполнении дерева продолжается обход по левой ветви до следующего узла выполнения inner_loop_condition. Этот узел выбирает из стека значение и если это значение существует, то возвращает родителю значение success, что в свою очередь дает команду узлу последовательности перейти к выполнению следующего узла inner_loop. Этот узел выполняет какие-то полезные действия и всегда возвращает сигнал success. Так как узлы inner_loop и inner_loop_condition вернули success, то узел последовательности, являющийся их родителем, тоже вернет значений success, что даст сигнал узлу цикла перезапустить все поддерево. Если же в стеке закончились значения, то узел inner_loop_condition вернет значение failed, что даст команду узлу последовательности прервать выполнение и транслировать значение родителю. Значение failed будет транслировано выше по иерархии до узла выбора, при этом узел цикла прекратит выполнение, и управление будет передано узлу loop_post_condition. Если требование всех условий выполнено, то loop_post_condition вернет значение success. Это значение будет также транслировано выше по иерархии до корня и выполнение дерева будет запущено заново. В противном случае, если loop_post_condition вернет значение failed, оно также будет транслировано вверх по иерархии до корня, но выполнение будет прервано.
Далее я бы хотел рассказать о еще одном полезном свойстве дерева повеления. Давайте сперва рассмотрим как производится выполнение дерева. Для этого придется углубиться в программную реализацию. Каждый из узлов дерева представлен классом, наследованным от базового, который имеет одно свойство state, характеризующее текущее состояние узла, и абстрактного метода tick(). Выполнение дерева начинается с вызова метода tick() корневого элемента, далее в зависимости от сигналов управления каждый узел вызывает этот же метод дочерних узлов, следуя логике, заложенной в конкретной реализации, будь то узел последовательности, выбора или какие-либо иной, разработанный для решения какой-то конкретной задачи. Лучшей практикой в разработке систем на основе дерева поведения считается минимальная затрата процессорного времени на выполнение метода tick(). Связано это с тем, что сущность, поведение которой мы описываем, может быть связана с несколькими деревьями одновременно или в системе могут присутствовать различные сущности с различным поведением, и таких примеров можно придумать множество. Для обеспечения параллельного исполнения всех деревьев на вычислительной платформе с одним CPU необходимо реализовать переключение между задачами, в нашем случае задача - это узел исполнения. При этом, чем меньше машинного времени тратится на метод tick() конкретного дерева, тем выше будет частота переключение задач. А чем выше частота переключения, тем точней будет отражаться состояние всей системы в единицу времени и минимизируются временные задержки между поступлением входящей информации и реакцией на нее. Как раз для прерывания выполнения дерева и передачи управления основной системе с сохранением текущего состояния существует третий сигнал running, о котором я вскользь упомянул выше. Это сигнал передается от точки его генерации до корня дерева. При последующем запуске выполнения дерева методом root.tick(), выполнение начнется с того узла, на котором было осуществлено прерывание. В моей реализации библиотеки, обеспечивающей работу с деревом поведения, сложность алгоритма возвращения от корня до точки остановки будет составлять O(n), где n - глубина дерева. При повышенных требованиях с производительности можно сократить сложность до O(1), это требует смены алгоритма обхода дерева, но рассматривать сейчас мы это не будет, так как это совсем другая тема. Пример прерывания выполнения дерева я приведу ниже (См. рис. 9).
В диаграмме никаких изменений не потребовалось. Я добавил в задачу inner_loop запрос подтверждения пользователя на пребывание выполнения дерева.
if (confirm('Interrupt?')){
return BT_STATES.RUNNING;
}
В случае если пользователь согласится и нажмет кнопку «OK», то будет сгенерирован сигнал running и управление перейдет системе. В этом примере система отображает статус, с которым завершилась выполнение дерева, если статус running, то выполнение дерева возобновился от корня.
const example = new ExampleTree();
do {
var result = example.tree.tick();
console.log('Interrupt with status: '+result);
} while( result == BT_STATES.RUNNING);
Этот пример является учебными и на самом деле управление системе не передается в силу архитектуры браузера и движка JavaScript. Для того чтобы действительно прервать исполнение программы и дать возможность движку JavaScript выполнить другие задачи, необходимо каждый вызов example.tree.tick() помещать в очередь задач. Одна из возможных реализаций проведена ниже.
const example = new ExampleTree();
const treeTick = () => {
var result = example.tree.tick();
console.log(`Interrupt with status: ${result}`);
if (result == BT_STATES.RUNNING){
setTimeout(treeTick,10);
}
} setTimeout(treeTick,10);
В заключение, хотелось бы отметить ряд очевидных преимуществ, данной методики. Только на первый взгляд может показаться, что обилие управляющих узлов вносят некоторую избыточность кода и в приведенных примерах можно обойтись стандартными языковыми конструкциями. От части это так, но давайте представим, что система должна выполнять какие-то сложные действия и количество выполняемых узлов и параметров, от которых зависит логика поведения, исчисляется десятками. В этом случае не получится избежать громоздких логических выражений, сопровождающихся глубокой вложенностью условных операторов и циклов. Со временем сложность сопровождения таких проектов возрастает экспоненциально. При использовании дерева поведения большая часть логики реализуется совокупностью узлов управления и топологией дерева, что позволяет менять логику без каких-либо модификаций узлов исполнения и свободно масштабировать проекты.