STRIPS: обзор

Первой системой, которая создавалась именно для решения задачи планирования, была система STRIPS (STanford Research Institute Problem Solver). Эта система выступала в роли модуля планирования для мобильного робота Shakey (разработка Центра искусственного интеллекта при SRI). STRIPS был разработан в 1971 году двумя исследователями — Ричардом Файксом и Нильсом Нильсоном. Описание системы опубликовано в трудах 2-ой международной конференции по искусственному интеллекту (IJCAI'71) [Fikes, Nilsson, 1971].

Файкс и Нильсон сформулировали задачу планирования такой, какова она и по сей день. Задача планировщика найти такую последовательность действий, которая преобразует начальное состояние в такое состояние, в котором достигается заранее заданное целевое условие (в оригинальной статье используются понятия "модель мира" для обозначения состояния и "оператор" для обозначения действия; здесь мы будем придерживаться современной терминологии). Состояние представляется множеством формул логики первого порядка (в оригинальной статье, well-formed formulas (wffs)). Цель также описывается формулой. Действия описываются в виде специальных конструкций, которые мы рассмотрим ниже.

STRIPS пользуется методологией доказательства теорем только в рамках одного заданного состояния для получения ответа на вопросы "какие действия применимы" и "достигнуты ли целевые условия" (в отличие от QA3, где методы доказательства теорем использовались и для перехода из состояния в состояние). В 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).

Действия группируются в классы действий, называемые схемами действий (в оригинальной статье, соответственно, схемы операторов). Такой подход позволил существенно сократить описание задачи. Рассмотрим, например, действие goto, перемещающее робота из одной комнаты в другую (напомним, что STRIPS создавался для управления роботом). Существует множество таких действий для каждой пары сообщающихся комнат. Было бы удобно сгруппировать все такие действия в рамках одной параметризованной схемы goto(x, y), где параметр x — обозначает начальное месторасположение робота, а y — конечное. Конкретные действия получаются из описания схемы путем подстановки конкретных сущностей (констант) вместо параметров. Применять можно только конкретизированные схемы действий, т.е. сами действия.

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

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

Условия применимости действия, называемые также предусловием (precondition), задаются при помощи одной формулы. Для того, чтоб узнать применимо ли действие в некотором заданном состоянии, мы должны проверить истинность предусловия, т.е. доказать, что предусловие является логическим следствием множества аксиом данного состояния. Если предусловие истинно, то действие применимо.

Важно отметить, что в схеме действия мы имеем дело со схемами формул, т.к. параметры действия могут фигурировать и в формулах. Например, у вышеупомянутой схемы goto(x,y) может быть следующее предусловие Robot_at(x). Конкретизация предусловия может происходить в процессе доказательства его истинности в некотором состоянии. Сам процесс доказательства предлагает подстановку для данного параметра такую, чтобы сделать формулу истинной. Следует различать параметры схемы действия и связанные переменные формулы (квантифицированные переменные), и этот момент нужно учитывать при доказательстве истинности формул.

Фактически, с введением параметров в формулы изменения в подходе к доказательству теорем коснутся только двух аспектов. Во-первых, потребуется изменение алгоритма унификации. Так для связанных переменных допустимы следующие подстановки: переменные, константы, параметры и функциональные термы, не содержащие переменных. Для параметров же допустимы такие подстановки: константы, параметры и функциональные термы, не содержащие сколемовых функций, переменных и параметров. Во-вторых, один и тот же параметр может фигурировать в нескольких формулах и надо следить, чтобы подстановка затрагивала именно все формулы. Т.е. в данном случае это будет не набор одноименных сущностей (как это было бы с переменными), а одна сущность.

Приведем пример того, как схема действия может быть описана в STRIPS. Рассмотрим схему действия Fly — перелет самолета из одного аэропорта в другой.

fly (p, from, to)
precondition = At(p, from) & Plane(p) & Airport(from) & Airport(to)
delete list = { At(p, from) }
add list = { At(p, to) }.

Здесь fly — имя схемы действия, за которым следует список параметров схемы (p, from, to). Следующая строка описывает предусловие. Для того, чтобы действие перелета совершилось, нужно чтобы самолет находился в аэропорту отправления. В предусловии мы указываем, что p — это самолет (Plane(p)), а from и to — аэропорты (Airport(from) & Airport(to)), и что самолет находится в пункте отправления (At(p, from)). В следующей строке описан список удаления. Он состоит всего из одного элемента — At(p, from). Удаляя эту формулу из состояния, мы получим эффект того, что самолет больше не находится в пункте отправления. И наконец, последняя строка описывает список добавления, который также состоит из одной формулы — At(p, to) — постулирующей то, что самолет окажется в пункте назначения после того, как действие будет выполнено.

Для осуществления поиска плана была использована стратегия GPS, которая определяет "различие" между текущим состоянием и целью и находит действия, способные уменьшить это различие. После того, как подходящее действие найдено, мы решаем подзадачу порождения состояния, к которому данное действие применимо. Если такое состояние обнаруживается, то действие применяется и изначальная цель рассматривается вновь уже в новом состоянии. Когда действие признано подходящим (релевантным), мы еще не знаем, где оно появится в конечном плане. Т.е. может оказаться, что перед ним должны стоять другие действия, которые делают возможным выполнение данного действия. После него также могут оказаться действия, которые обеспечивают выполнение всей цели (ведь одно действие служит уменьшению различия, а не обязательно достижению цели сразу).

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

Файкс и Нильсон отмечают, что интересно было бы попробовать применять не полностью конкретизированные действия. Тогда бы получались не состояния, а схемы состояний. Но авторы не стали сами пробовать такой подход.

Авторы также отмечают, что в списке удалений иногда удобно записывать не сами формулы, а некоторые их прототипы. Например, одним из эффектов действия goto для робота должно быть удаление информации о том, куда робот был направлен лицом, даже если эта информация не указывается в качестве параметра схемы действия. В этом случае в список удаления можно поместить запись вида facing($), смысл которого следующий: "всякая формула соответствующая этому прототипу (независимо от значения $) должна быть удалена".

Коль скоро мы имеем дело со сложными формулами, мы должны учитывать следующий момент, связанный с удалением формул. Если мы удаляем некоторую формулу, мы должны будем также удалить и все формулы, которые были выведены на основании данной.

Иерархия целей, подцелей и состояний, полученных в процессе поиска, называется деревом поиска (search tree). Как уже упоминалось ветвление обусловлено тем, что различие между целью и состоянием может быть уменьшено несколькими способами. Каждый узел дерева поиска представляет собой пару (состояние, список целей). Фактически в узле описывается текущее состояние и стек целей (подцелей), которые нужно достичь. Всякий раз, когда STRIPS порождает очередной узел, он проверяет, достигается ли первая цель списка целей нового узла в состоянии, означенном в новом узле. Если это так, и целью является предусловие некоторого действия, то действие применяется (напомним, что предусловие — это одна формула), после чего порождается новый узел с новым состоянием и тем же самым списком целей, в котором отсутствует первая цель (мы ее уже достигли). Если же первая цель не достигается в состоянии, означенном в узле, то на основании различия отыскивается подходящее действие и формируется новый узел путем добавления предусловия этого действия. STRIPS пользуется эвристикой для выбора, какой узел рассматривать следующим. Эвристическая функция оценивает такие факторы, как количество оставшихся целей в списке целей и количество и виды предикатов в целевых формулах.

Т.к. описание модели мира может быть достаточно большим в задаче с роботом, не очень выгодно хранить копии модели мира в каждом узле по двум причинам. Во-первых, одна и та же модель мира может использоваться в описании нескольких узлов. Во-вторых, большинство утверждений в описании модели мира остаются неизменными. Лишь небольшое их число изменяется в ответ на воздействие робота. Поэтому было предложено следующее решение по организации памяти. Все формулы всех моделей мира хранятся в единой структуре памяти. В узлах же хранятся только флаги, какие формулы стали истинны, а какие ложны по сравнению с начальным состоянием.

В последствии STRIPS подвергался обширной критике и за подход к описанию мира и действий, и за алгоритм поиска. Однако многие идеи и решения, предложенные Файксом и Нильсоном, и по сей день остаются основополагающими в планировании.

 

Библиография

[Fikes, Nilsson, 1971]
Fikes R.E., Nilsson N.J., STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. IJCAI'71, стр. 608-620.

 

Трофимов И.В.

апрель 2005