STRIPS

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

STRIPS (Stanford Research Institute Problem Solver) — это автоматический планировщик, разработанный Ричардом Файксом и Нильсом Нилсоном в 1971. В последующем слово STRIPS стало также использоваться для обозначения формального языка, описывающего входные данные этого планировщика. Этот язык является основой большинства современных языков описания задач автоматического планирования. Данная статья описывает только язык (так называемый STRIPS-формализм), а не сам планировщик.

Определение[править | править исходный текст]

Описание задачи планирования на языке STRIPS включает в себя следующие компоненты:

  • Начальное состояние;
  • Определение целевых состояний — ситуаций, которые планировщик пытается достичь;
  • Набор возможных действий (операторов). Каждое действие включает:
    • предусловия (preconditions) — предварительное условие, которое должно быть удовлетворено, чтобы действие могло быть выполнено;
    • постусловия (postconditions) — изменения состояния, которые произойдут после выполнения действия.

Выражаясь математически, задача планирования в STRIPS-формализме — это четверка \langle P,O,I,G \rangle, компоненты которой имеют следующие значения:

  1. P — множество условий (conditions)
  2. O — множество операторов; каждый оператор в свою очередь является четверкой \langle \alpha, \beta, \gamma, \delta \rangle. Все элементы четверки являются множествами. В порядке очередности, это условия, которые:
    1. должны быть удовлетворены перед выполнением операции
    2. должны быть нарушены (чтобы выполнение операции имело смысл)
    3. удовлетворяемые данной операцией
    4. нарушаемые данной операцией
  3. I — начальное состояние — набор условий, которые считаются уже удовлетворенными (все прочие условия считаются неудовлетворенными);
  4. G — спецификация конечной цели; задается парой \langle N,M \rangle, которая определяет, какие условия должны быть удовлетворены и нарушены, чтобы цель считалась достигнутой.

Планом (решением) такой задачи планирования является последовательность действий (операторов), которая может быть выполнена, начиная с состояния I, и приведет в какое-либо из целевых состояний G.

Пример задачи[править | править исходный текст]

Общий алгоритм[править | править исходный текст]

Литература[править | править исходный текст]

  • R. Fikes and N. Nilsson (1971). STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189-208.

Ссылки[править | править исходный текст]