Что такое деревья поведения и как они используются25.07.2016 12:03

/ фото Harry Li CC

Нас в компании «ИТ-ГРАД» очень интересуют вопросы искусственного интеллекта. Мы уже затрагивали тему автопилотируемых автомобилей, а неделю назад публиковали материал, в котором рассказывали о новых достижениях ученых и разработчиков в сфере ИИ, а также об опасениях скептиков.

Сегодня мы вновь коснемся этого вопроса и поговорим о том, что такое деревья поведения, как они используются в робототехнике и есть ли у них будущее.

Программирование робота на выполнение определенных действий — сложный процесс. Входные переменные зачастую неизвестны, потому машине приходится на лету подстраиваться под окружающие условия. Стандартные модели управления роботами разрабатывались в виде конечных автоматов [FSM — Finite-State Machine], однако этот способ плохо подходит для создания сложных алгоритмов, поскольку по мере добавления новых элементов модели, её сложность начинает быстро увеличиваться.

Чтобы сгладить эти недостатки, стал использоваться подход, широко применяемый разработчиками видеоигр. Речь идет о деревьях поведения. В отличие от конечных автоматов, деревья имеют более формальную структуру, поэтому с их помощью проще программировать поведение машины.

Дерево поведения [BT — Behavior Tree] — это ориентированный ациклический граф, узлами которого являются возможные варианты поведения робота. «Ширина» дерева указывает на количество доступных действий, а «длина» его ветвей характеризует их сложность.

Конечный автомат с четырьмя состояниями

В чем преимущество деревьев поведения над конечными автоматами? По мере увеличения числа состояний конечного автомата, его сложность резко возрастает. Число переходов в FSM с количеством состояний N равняется N*(N-1). Если взять N = 4, то получим 12 возможных переходов. Если добавим еще одно состояние, переходов станет 20, еще одно — 30.

Частично эту проблему решают так называемые иерархические FSM, однако при большом количестве состояний структура по-прежнему получается чересчур сложной.

Архитектуры конечного автомата и дерева поведений

«Древесная» архитектура лишена этого недостатка. Если в FSM для каждого состояния прописывается своя логика принятия решений, то в BT она как бы выведена за их пределы. Это позволяет добавлять и удалять узлы даже в процессе работы программы: просто пишется новый код для вызова узла или удаляется старый.

Кроме того, дерево с большим числом состояний можно разбить на мелкие поддеревья — это дополнительно упрощает «ориентирование на местности» и поиск багов.

Принцип работы дерева поведения

Узлы BT называют задачами или поведениями. Каждая задача может иметь четыре состояния:

• «Успех», если задача выполнена успешно;
• «Неудача», если условие не выполнено или задача, по какой-то причине, невыполнима;
• «В работе», если задача запущена в работу и ожидает завершения
• «Ошибка», если в программе возникает неизвестная ошибка.

Среди узлов выделяют следующие типы: действие (action), узел исполнения последовательности (sequence), параллельный узел (parallel), селектор (selector), условие (condition), инвертор (inverter).

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

Узлы параллельных действий исполняют поведения дочерних узлов до тех пор, пока заданное количество из них не вернет статусы «Неудача» или «Успех».

Селекторы поочередно исполняют поведения каждого дочернего узла до тех пор, пока один из них не выдаст значение «Успех», «В работе» или «Ошибка». Если этого не произошло, возвращает значение «Неудача».

Условия содержат критерий, по которому определяется исход, и переменную. Например, условие «Есть ли в этой комнате человек?» перебирает все объекты в комнате и сравнивает их с переменной «Человек». Узлы инверсии выполняют функцию оператора NOT.

На GitHub приводится пример реализации дерева, моделирующего поведение собаки, которая умеет лаять, гулять и делать другие собачьи дела.

Дерево представлено в виде кода на libGDX. libGDX — это фреймворк, написанный на Java с использованием C и C++.

#
# Dog tree
#

# Alias definitions
import bark:"com.badlogic.gdx.ai.tests.btree.dog.BarkTask"
import care:"com.badlogic.gdx.ai.tests.btree.dog.CareTask"
import mark:"com.badlogic.gdx.ai.tests.btree.dog.MarkTask"
import walk:"com.badlogic.gdx.ai.tests.btree.dog.WalkTask"

# Tree definition (note that root is optional)
root
  selector
    parallel
      care urgentProb:0.8
      alwaysFail
        com.badlogic.gdx.ai.tests.btree.dog.RestTask # fully qualified task
    sequence
      bark times:"uniform,1,3"  # the type of attribute times is a IntegerDistribution 
      walk
      com.badlogic.gdx.ai.tests.btree.dog.BarkTask # fully qualified task
      mark

Схему дерева поведения пса вы можете найти по ссылке. Чуть более сложный вариант дерева поведения представлен здесь: собака гуляет по саду до тех пор, пока ее не позовет хозяин. В этой модели уже используются обращения к поддеревьям.

Главным преимуществом деревьев поведения является формальность. При помощи набора инструментов, шаблонов и структур могут быть реализованы очень интересные и выразительные поведения, даже связанные друг с другом. В этом кроется одна из причин того, что именно BT стали частым выбором для реализации искусственного интеллекта в компьютерных играх и создании небольших роботов.

Например, группа ученых из Делфтского технического университета в Нидерландах разработала робота на базе платформы DelFly Explorer, получающего данные об окружении с помощью двух встроенных камер. В своей статье они описали эксперимент, во время которого робот должен был найти в комнате открытое окно и пролететь в него.

Ученые решили отказаться от искусственных нейронных сетей: в платформах для небольших роботов возможности для сбора данных и вычисления сильно ограничены, к тому же развитые ИНС с трудом поддаются анализу и их сложно настраивать вручную. Вместо них были выбраны деревья поведения, имеющие более простую и понятную структуру, а также эволюционные алгоритмы для оптимизации обучения.

Что касается игровой тематики, то вот пример. Деревья поведения использовались при создании автомобильного симулятора для университета Саншайн Кост. Данный симулятор сейчас применяется для психологического тестирования водителей.

Дерево поведения этого проекта строилось на языке программирования C# с использованием библиотеки Fluent-Behaviour-Tree. Весь код и блок-схемы вы можете найти по ссылке.

Современный ИИ требует технологий, способных поддерживать комплексные системы с качественно сложным и своеобразным поведением. Необходим ИИ, который умеет совершать непредсказуемые действия и принимать решения в ситуациях, не предусмотренных разработчиком.

Для этого используются более мощные решения и алгоритмы, вычислительным требованиям которых аппаратура роботов зачастую не отвечает. Однако выход есть — облачная робототехника. В этом случае вся логика работы хранится на удаленном сервере, а маленький робот получает лишь команды к действию.

Такой подход автоматически решит еще одну проблему — позволит сделать электронно-механических помощников интеллектуальными. Подключение к облаку снабдит робота всей необходимой информацией об окружающем мире. Работа в этом направлении уже ведется, например, этими вопросами занимается небезызвестный исследователь робототехники Эндрю Ын (Andrew Ng).

Возможно, уже в ближайшем будущем роботы начнут обмениваться данными и кодом друг с другом по беспроводным сетям.

P.S. Интересные материалы из нашего блога на Хабре:

• Пятничный формат: IaaS и наука — как это работает
• «Пятничный формат»: AI — новый враг или новый бог
• Как не выбить разработчика из состояния «потока»
• Не самолет, но в «облаках»: Автомобили и облачные технологии

Комментарии (0)