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

«Динамическое планирование» перенаправляется сюда. Для аниме-студии см. Динамическое планирование .

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

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

Представление реактивного плана

Есть несколько способов представить план реагирования. Для всех требуется базовая репрезентативная единица и средства для объединения этих единиц в планы.

Правила действия-условия (постановки)

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

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

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

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

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

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

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

Конечные автоматы

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

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

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

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

Нечеткие подходы

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

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

Подходы коннекционистов

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

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

Алгоритмы реактивного планирования

Типичный алгоритм реактивного планирования просто оценивает правила «если-то» или вычисляет состояние сети связи. Однако у некоторых алгоритмов есть особенности.

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

Рулевое управление

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

  • к цели навигации
  • поведение избегания препятствий
  • стена, следующая за поведением
  • приближается враг
  • избегание хищников
  • поведение толпы

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

Смотрите также

Ссылки


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