Реактивное планирование

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

Хотя термин реактивное планирование восходит по крайней мере до 1988 года, термин «реактивный» теперь стал уничижительным, используемым в качестве антонима для инициативного. Поскольку почти все агенты, использующие реактивное планирование, являются активными, некоторые исследователи начали ссылаться на реактивное планирование как на динамическое планирование.

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

Правила условий действия (постановления)
Правило действия условия или правило if-then является правилом в форме: if condition then action. Эти правила называются постановками. Смысл этого правила заключается в следующем: если условие выполнено, выполните действие. Действие может быть либо внешним (например, выбрать что-то вверх и переместить его), либо внутренним (например, записать факт во внутреннюю память или оценить новый набор правил). Условия обычно являются логическими, и действие может быть выполнено или нет.

Производственные правила могут быть организованы в относительно плоских структурах, но чаще всего организованы в какую-либо иерархию. Например, архитектура подчинения состоит из слоев взаимосвязанных поведений, каждый из которых фактически является конечным автоматом, который действует в ответ на соответствующий вход. Эти слои затем упорядочиваются в простой стек, причем более высокие уровни включают в себя цели нижних. Другие системы могут использовать деревья или могут включать специальные механизмы для изменения того, какое подмножество цели / правила в настоящее время наиболее важно. Плоские структуры относительно просты в построении, но допускают только описание простого поведения или требуют чрезвычайно сложных условий для компенсации недостающей структуры.

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

заранее назначая приоритеты в правилах,
назначение предпочтений (например, в архитектуре Soar),
изучение относительных утилит между правилами (например, в ACT-R),
используя форму планирования.
Экспертные системы часто используют другие более простые эвристики, такие как переход для выбора правил, но трудно гарантировать хорошее поведение в большой системе с простыми подходами.

Разрешение конфликтов необходимо только для правил, которые хотят принимать взаимоисключающие действия (см. Blumberg 1996).

Некоторые ограничения такого рода реактивного планирования можно найти в Brom (2005).

Конечные машины
Конечный автомат (FSM) является моделью поведения системы. FSM широко используются в информатике. Моделирование поведения агентов является лишь одним из их возможных применений. Типичный FSM, используемый для описания поведения агента, состоит из набора состояний и переходов между этими состояниями. Переходы на самом деле являются правилами действия условий. В каждый момент времени только одно состояние FSM активно, и его переходы оцениваются. Если переход выполняется, он активирует другое состояние. Это означает, что в целом переходы являются правилами в следующем виде: если условие активирует-новое состояние. Но переходы также могут соединяться с состоянием «я» в некоторых системах, чтобы позволить выполнение переходных действий без фактического изменения состояния.

Существует два способа создания поведения с помощью FSM. Они зависят от того, что ассоциируется с состояниями дизайнером — они могут быть либо «действиями», либо скриптами. «Действие» — это атомное действие, которое должно выполняться агентом, если его FSM является данным состоянием. Это действие выполняется на каждом временном шаге. Однако чаще всего это последний случай. Здесь каждое состояние связано со сценарием, который описывает последовательность действий, которые агент должен выполнить, если его FSM находится в определенном состоянии. Если переход активирует новое состояние, первый скрипт просто прерывается, а новый запускается.

Если сценарий более сложный, его можно разбить на несколько сценариев, и можно использовать иерархический FSM. В таком автомате каждое состояние может содержать подстанции. Только состояния на атомном уровне связаны со сценарием (что не сложно) или атомарным действием.

Вычислительно, иерархические FSM эквивалентны FSM. Это означает, что каждый иерархический FSM может быть преобразован в классический FSM. Однако иерархические подходы облегчают проектирование. См. Статью Дамиана Исла (2005) на примере ASM компьютерных игровых ботов, в которой используются иерархические FSM.

Нечеткие подходы
И правила if-then, и FSM можно комбинировать с нечеткой логикой. Условия, состояния и действия не более логичны или «да / нет» соответственно, но являются приблизительными и гладкими. Следовательно, приведенное поведение будет более плавным, особенно в случае переходов между двумя задачами. Однако оценка нечетких условий намного медленнее, чем оценка их четких копий.

Посмотрите на архитектуру Алекса Шампандара.

Подходы к подключению
Реактивные планы могут быть выражены также сетями подключений, такими как искусственные нейронные сети или иерархии свободного потока. Основной репрезентативный блок представляет собой блок с несколькими входными ссылками, которые снабжают блок «абстрактным действием» и выходными ссылками, которые распространяют активность на следующие единицы. Каждый блок сам по себе работает как преобразователь активности. Как правило, блоки соединены в слоистой структуре.

Положительные стороны сетей-подключений — это, во-первых, то, что приведенное поведение более плавное, чем поведение, создаваемое четкими правилами if-then и FSM, во-вторых, сети часто адаптивны, и, в-третьих, механизм ингибирования может быть использован, и, следовательно, поведение может быть также описывается прописным образом (с помощью правил можно описать поведение только предписывающе). Однако методы также имеют несколько недостатков. Во-первых, для дизайнера гораздо сложнее описать поведение сети по сравнению с правилами if-then. Во-вторых, можно описать только относительно простое поведение, особенно если использовать адаптивную функцию.

Реактивные алгоритмы планирования
Типичный алгоритм реактивного планирования просто оценивает правила if-then или вычисляет состояние сети соединений. Однако некоторые алгоритмы имеют специальные функции.

Оценка Rete: с правильным логическим представлением (которое подходит только для четких правил), правила не должны пересматриваться на каждом временном шаге. Вместо этого может использоваться форма кеша, хранящая оценку с предыдущего шага.
Языки сценариев. Иногда правила или FSM являются непосредственно примитивами архитектуры (например, в Soar). Но чаще, реактивные планы программируются на языке сценариев, где правила являются лишь одним из примитивов (например, в JAM или ABL).
Рулевое управление
Рулевое управление представляет собой специальную реактивную технику, используемую для навигации агентов. Простейшая форма реактивного рулевого управления используется в транспортных средствах Брайтенберга, которые отображают входные сигналы датчиков непосредственно на эффекторные выходы и могут следовать или избегать. Более сложные системы основаны на суперпозиции привлекательных или отталкивающих сил, которые воздействуют на агента. Такое рулевое управление основано на оригинальной работе над боевыми машинами Крейга Рейнольдса. С помощью рулевого управления можно достичь простой формы:

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