Дерево поведения

Дерево поведения (behavior tree) - это ориентированное дерево, моделирующее принятие решений в виде иерархии задач. Каждый узел выполняет тик (срабатывает) и возвращает одно из трёх состояний: success, failure или running. Дерево вычисляется от корня на каждом тике, а поток управления проходит через составные узлы (composite), определяющие, какие дочерние узлы запускать.

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

Типы узлов

Составные узлы (composite) управляют потоком выполнения:

• Sequence - выполняет дочерние узлы слева направо, останавливается на первой ошибке. Завершается успехом, только если все дочерние узлы успешны. Логический вентиль "И" (AND) для деревьев поведения.
• Selector (также называется Fallback или Priority) - выполняет дочерние узлы слева направо, останавливается на первом успехе. Завершается ошибкой, только если все дочерние узлы завершились ошибкой. Логический вентиль "ИЛИ" (OR).
• Parallel - запускает все дочерние узлы одновременно с настраиваемыми порогами успеха и ошибки.

Декораторы (decorator) оборачивают один дочерний узел и модифицируют его результат:

• Inverter - меняет успех на ошибку и наоборот (вентиль "НЕ" / NOT).
• Repeat - перезапускает дочерний узел N раз или до первой ошибки.
• Timeout - завершается ошибкой, если дочерний узел не уложился в лимит по времени.
• Retry - повторяет выполнение упавшего дочернего узла до N раз.

Листовые узлы (leaf) выполняют непосредственную работу:

• Action - выполняет функцию, возвращает успех или ошибку.
• Condition - проверяет предикат по общему состоянию (blackboard), возвращает успех или ошибку без побочных эффектов.

Blackboard

Узлы взаимодействуют через общее хранилище данных - blackboard. Узлы Action записывают в него данные, а Condition - читают. Это избавляет от передачи данных через структуру дерева и сохраняет слабую связанность узлов: узлу Condition не нужно знать, какое именно действие установило проверяемое значение.

Почему не конечный автомат?

Конечные автоматы (FSM) становятся громоздкими по мере роста сложности. Добавление нового состояния требует учёта переходов в него и из него для каждого существующего состояния - число переходов растёт квадратично. Деревья поведения иерархичны: добавление нового поведения сводится к добавлению поддерева, а составные узлы берут на себя логику приоритетов и отката (fallback). Поддеревья также можно переиспользовать в разных деревьях.

Обратная сторона: деревья поведения вычисляются от корня на каждом тике, что может быть неэффективно, если большая часть дерева в данный момент неактуальна. Событийно-ориентированные (event-driven) и реактивные варианты деревьев поведения решают это, повторно вычисляя узлы только при изменении нужного состояния.

Состояние running

Третье возвращаемое значение - running - как раз и позволяет деревьям поведения работать с задачами, длящимися несколько тиков. Узел возвращает running, сообщая: "я ещё не закончил, вернись на следующем тике". Родительский составной узел запоминает, какой дочерний узел выполнялся (в вариантах с памятью вроде MemSequence), и на следующем тике возобновляет работу с него. Без этого каждый тик начинался бы заново с начала последовательности.

Реализации

• go-bt - минималистичная библиотека на Go с обобщённым типизированным blackboard и тестированием через time-travel
• Встроенный редактор деревьев поведения в Unreal Engine (самая известная мейнстримная реализация)
• BehaviorTree.CPP - широко используется в робототехнике на базе ROS2

Наследие архитектуры blackboard

Концепция blackboard здесь - общее состояние, которое узлы читают и пишут вместо прямых вызовов друг друга, - более старая идея, и она вновь всплывает в средах выполнения агентов. log-is-the-agent доказывает, что компоненты на базе LLM лучше координируются через общий граф, чем через цикл диалога, ссылаясь на ту же литературу по архитектуре blackboard (Nii, 1986). В ней поведения подписываются на структуры графа, а не тикают по порядку обхода дерева, но свойство "ни один компонент не командует другим" даёт ровно то же, что и blackboard.