Первой системой, которая создавалась именно для решения задачи планирования, была система STRIPS (Sеanford Research Institute Problem Solver). Эта система выступала в роли модуля планирования для мобильного робота Shakey (разработка Центра искусственного интеллекта при SRI). STRIPS был разработан в 1971 году двумя исследователями – Ричардом Файксом и Нильсом Нильсоном. Описание системы опубликовано в трудах 2-ой международной конференции по искусственному интеллекту.
Файкс и Нильсон сформулировали задачу планирования такой, какова она и по сей день. Задача планировщика найти такую последовательность действий, которая преобразует начальное состояние в такое состояние, в котором достигается заранее заданное целевое условие (в оригинальной статье используются понятия «модель мира» для обозначения состояния и «оператор» для обозначения действия). Состояние представляется множеством формул логики первого порядка. Цель также описывается формулой. Действия описываются в виде специальных конструкций, которые будут рассмотрены ниже.
STRIPS пользуется методологией доказательства теорем только в рамках одного заданного состояния для получения ответа на вопросы «какие действия применимы» и «достигнуты ли целевые условия». В STRIPS поиск в пространстве состояний осуществляется по аналогии с системой GPS, а именно, используется стратегия «анализ средств и целей».
Формально, постановка задачи в STRIPS включает три составляющие: начальное состояние, множество действий и целевую формулу. Как уже было отмечено, состояния описываются множеством формул. Например, то, что объект obj1 находится в комнате room2, можно выразить следующей формулой: At(obj1, room2). Кроме таких «описательных» аксиом, можно включать аксиомы-правила, наподобие тех, что использовал Грин (в другой системе QA3). Например, можно написать, что если объект находится в комнате room2, то он не находится ни в какой другой комнате. Формально это можно представить так:
(» x, y, z) [At (x, y) & (y = z) –> At (x, z)].
Если формула, описывающая состояние, является литералом, то это должен быть позитивный литерал (без знака отрицания). Все атомарные формулы во множестве формул, описывающих состояние, должны быть означены (ground), т.е. не иметь свободных переменных. Утверждения, не входящие в число формул, описывающих состояние, и не являющиеся их логическим следствием, считаются ложными. Это последнее допущение в литературе называют допущение о замкнутости мира (closed-world assumption).
Действия группируются в классы действий, называемые схемами действий (в оригинальной статье, соответственно, схемы операторов). Такой подход позволил существенно сократить описание задачи. Конкретные действия получаются из описания схемы путем подстановки конкретных сущностей (констант) вместо параметров. Применять можно только конкретизированные схемы действий, т.е. сами действия.
Напомню, что STRIPS создавался для управления роботом. Введение понятия схемы было необходимо для задачи управления роботом, т.к. в этой задаче было также действие перемещения между двумя точками в комнате, а точек могло быть очень много. Без схем, описание задачи было бы очень большим. С тех пор понятие схемы действия вошло в практику планирования как постоянный компонент. В настоящее время все планировщики прибегают именно к такой (параметризованной) форме описания действий.
Описание каждой схемы действия (а, соответственно, и самого действия) состоит из двух основных частей: описания эффекта действия и описания условий, при которых действие применимо. Эффект действия определяется через два списка: список формул, которые добавляются к состоянию, и список формул, которые удаляются из состояния, т.к. становятся ложными в результате применения действия. Отметим, что если формула из списка добавления уже присутствует в текущем состоянии (состоянии, к которому применяется действие), то эта формула не будет добавлена вторично. Аналогично, если формула из списка удаления уже отсутствует в текущем состоянии, то ее удаление игнорируется. Все формулы, которые не упоминаются в эффекте, остаются неизменными в новом состоянии. Это последнее утверждение в литературе называют STRIPS-допущением (STRIPS assumption).
Условия применимости действия, называемые также предусловием (precondition), задаются при помощи одной формулы. Для того, чтоб узнать применимо ли действие в некотором заданном состоянии, мы должны проверить истинность предусловия, т.е. доказать, что предусловие является логическим следствием множества аксиом данного состояния. Если предусловие истинно, то действие применимо.
Важно отметить, что схема действия имеет дело со схемами формул, т.к. параметры действия могут фигурировать и в формулах. Конкретизация предусловия может происходить в процессе доказательства его истинности в некотором состоянии. Сам процесс доказательства предлагает подстановку для данного параметра такую, чтобы сделать формулу истинной. Следует различать параметры схемы действия и связанные переменные формулы (квантифицированные переменные), и этот момент нужно учитывать при доказательстве истинности формул.
Фактически, с введением параметров в формулы изменения в подходе к доказательству теорем коснутся только двух аспектов. Во-первых, потребуется изменение алгоритма унификации. Так для связанных переменных допустимы следующие подстановки: переменные, константы, параметры и функциональные термы, не содержащие переменных. Для параметров же допустимы такие подстановки: константы, параметры и функциональные термы, не содержащие сколемовых функций, переменных и параметров. Во-вторых, один и тот же параметр может фигурировать в нескольких формулах и надо следить, чтобы подстановка затрагивала именно все формулы. Т.е. в данном случае это будет не набор одноименных сущностей (как это было бы с переменными), а одна сущность.
STRIPS начинает работу с попытки доказать, что цель является следствием множества формул, описывающих начальное состояние. Если цель следует из начального состояния, то задача решена. В противном случае незавершенное доказательство теоремы (то, что пока не удалось доказать) рассматривается в качестве различия между состоянием и целью. Затем выполняется поиск схемы действия, эффект которой может добавить (или удалить) такую формулу, что доказательство будет продолжено. Здесь может потребоваться частичная или полная конкретизация формулы эффекта. Подходящих схем действий может быть несколько, поэтому будут формироваться ветви поиска, в каждой из которых прорабатывается один способ. После того, как схема действия выбрана, ее предусловие (возможно частично конкретизированное) рассматривается в качестве новой подцели. При попытке доказать это предусловие выполняется конкретизация предусловия. Т.е. процесс доказательства ищет такие подстановки для параметров формулы, чтобы сделать эту формулу истинной в текущем состоянии. Если такая подстановка находится, то схема действия конкретизируется и действие применяется, иначе в процессе доказательства вновь формируется различие и процесс повторяется.
Файкс и Нильсон отмечают, что интересно было бы попробовать применять не полностью конкретизированные действия. Тогда бы получались не состояния, а схемы состояний. Но авторы не стали сами пробовать такой подход.
Авторы также отмечают, что в списке удалений иногда удобно записывать не сами формулы, а некоторые их прототипы. Например, одним из эффектов действия goto для робота должно быть удаление информации о том, куда робот был направлен лицом, даже если эта информация не указывается в качестве параметра схемы действия. В этом случае в список удаления можно поместить запись вида facing($), смысл которого следующий: «всякая формула соответствующая этому прототипу (независимо от значения $) должна быть удалена».
Иерархия целей, подцелей и состояний, полученных в процессе поиска, называется деревом поиска (search tree). Как уже упоминалось ветвление обусловлено тем, что различие между целью и состоянием может быть уменьшено несколькими способами. Каждый узел дерева поиска представляет собой пару (состояние, список целей). Фактически в узле описывается текущее состояние и стек целей (подцелей), которые нужно достичь. Всякий раз, когда STRIPS порождает очередной узел, он проверяет, достигается ли первая цель списка целей нового узла в состоянии, означенном в новом узле. Если это так, и целью является предусловие некоторого действия, то действие применяется (напомним, что предусловие – это одна формула), после чего порождается новый узел с новым состоянием и тем же самым списком целей, в котором отсутствует первая цель (мы ее уже достигли). Если же первая цель не достигается в состоянии, означенном в узле, то на основании различия отыскивается подходящее действие и формируется новый узел путем добавления предусловия этого действия. STRIPS пользуется эвристикой для выбора, какой узел рассматривать следующим. Эвристическая функция оценивает такие факторы, как количество оставшихся целей в списке целей и количество и виды предикатов в целевых формулах.
Т.к. описание модели мира может быть достаточно большим в задаче с роботом, не очень выгодно хранить копии модели мира в каждом узле по двум причинам. Во-первых, одна и та же модель мира может использоваться в описании нескольких узлов. Во-вторых, большинство утверждений в описании модели мира остаются неизменными. Лишь небольшое их число изменяется в ответ на воздействие робота. Поэтому было предложено следующее решение по организации памяти. Все формулы всех моделей мира хранятся в единой структуре памяти. В узлах же хранятся только флаги, какие формулы стали истинны, а какие ложны по сравнению с начальным состоянием.
В последствии STRIPS подвергался обширной критике и за подход к описанию мира и действий, и за алгоритм поиска. Однако многие идеи и решения, предложенные Файксом и Нильсоном, и по сей день остаются основополагающими в планировании.