STRIPS

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

Эта статья о системах автоматического планирования, которое является подразделом Искусственного интеллекта

Содержание

1 Определение
2 Пример задачи
3 Общий алгоритм
4 Рекомендуемая литература

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

[править] Определение

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

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

Выражаясь математически, мгновенное значение STRIPS есть четыре объекта $\langle P,O,I,G \rangle$ , каждый из которых имеет следующее значение:

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