STRIPS

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

Определение

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

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

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

$P$ — множество условий (conditions)
$O$ $\text{[math]}$ — множество операторов; каждый оператор в свою очередь является четверкой $\langle \alpha ,\beta ,\gamma ,\delta \rangle$ $\text{[math]}$ . Все элементы четверки являются множествами. В порядке очерёдности, это условия, которые:
1. должны быть удовлетворены перед выполнением операции
2. должны быть нарушены (чтобы выполнение операции имело смысл)
3. удовлетворяемые данной операцией
4. нарушаемые данной операцией
$I$ — начальное состояние — набор условий, которые считаются уже удовлетворенными (все прочие условия считаются неудовлетворенными);
$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.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.