11.4.2. Система STRIPS

Система STRIPS (Файкс и Нильсон, 1971; Файкс, Харт и Нильсон, 1972) порождает планы путем обобщения уже решенных задач. STRIPS представляет собой часть программной управляющей системы для работы Шейки — самоходного аппарата, совершающего передвижения в упрощенной среде по командам, данным на упрощенном английском языке. Для того чтобы понять необходимы некоторые пояснения, касающиеся Шейки. Робот содержит четыре основные физические системы: собственно аппарат (тележку) и двигательную систему; сенсорную систему, состоящую

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

Внешний мир этого робота состоит из комнат, дверей между ними, подвижных ящиков и, в более сложных ситуациях, источников света и окон. Этот физический мир в каждом частном случае описывается для STRIPS множеством утверждений, выраженных в форме предложений исчисления предикатов. Например, появление предложения

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

Управляющие программы содержат также ряд подпрограмм, ответственных за прохождение робота в дверь, проталкивание ящика в дверь, выключение света и выполнение других физических действий. Эти программы сами по себе весьма сложны, но они не связаны непосредственно с решением задач. Они примерно так же соотносятся с решением задач роботом, как сложные действия хождения или собирания чего-либо с решением задач человеком.

Пусть модель мира содержит предложения

и роботу дается задача поместить ящик в комнату Рассмотрим более общую задачу помещения ящика в комнату где — переменные. (Договоримся обозначать переменные строчными буквами, а константы — прописными.) Формально от STRIPS требуется получить модель, содержащую утверждение Эту задачу можно решить тремя способами.

(а) Возможно, желаемые утверждения уже содержатся в модели. Это было бы эквивалентно тому, что GPS или FDS дана „задача" вывода цепочки из самой себя.

(б) Возможно, удастся вывести желаемые утверждения из модели, не изменяя соответствующий ей физический мир. Предположим, что мы добавили к (35) предложения

и STRIPS может осуществить вывод

К утверждению можно прийти путем вывода, без каких-либо действий робота в физическом мире. STRIPS располагает мощными возможностями вывода, основанными на принципе резолюции, а не на методах, использующихся в GPS и FDS. В гл. 12 мы подробнее изучим принцип резолюции, а сейчас будем считать, что STRIPS действительно может осуществлять логический вывод.

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

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

Заметим, что (38) составлено на языке требований к переменным. В конкретной попытке активации переменные заменятся константами. Это называется выбором (основного) частного случая.

Возвратимся к примеру с для завершения операции необходимо изменить модель, включив в нее

и убрать

Обратим внимание на сходство между предусловиями и списками добавлений и вычеркиваний, с одной стороны, и левыми и правыми частями операторов правил переписывания в GPS и FDS — с другой. Они используются совершенно одинаково.

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

После решения задачи STRIPS может обобщить его, представив в виде плана. Рассмотрим ситуацию после того, как робот решил задачу передвижения из и затем проталкивания ящика обратно в Решение программы STRIPS таково:

Наиболее очевидный способ обобщить это решение — заменить все константы переменными:

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

одной произвольной комнаты в другую и толкания объекта из второй комнаты в третью. Излишняя специализация возникает в (42) от того, что каждая отдельная константа в решении была заменена везде в этом плане единственной переменной. Мы могли бы пользоваться более общим правилом замещения, в котором отдельная переменная использовалась бы для каждого аргумента оператора без учета исходных совпадений аргументов различных операторов в решении. Это, к сожалению, еще менее удовлетворительно. Действительно, пусть мы применили такое правило замещения к решению (41). В результате

План (43) означает, что робот может войти в комнату и затем выталкивать объект из комнаты которая может оказаться совсем другой комнатой. Очевидно, что это неверно. При замене констант переменными следует учитывать, какие переменные на различных шагах решения с необходимостью относятся к одному и тому же объекту. STRIPS осуществляет это, учитывая, какие переменные на шагах, предшествующих шагу плана, должны упоминаться в предварительных условиях к шагу. Технические подробности того, как это делать, зависят от механизма действия принципа резолюции при доказательстве теорем, который мы еще не обсуждали. Для наших текущих целей важно заметить, что существуют правильные способы обобщить решения так, чтобы они не были слишком общими, как в (43), и избежать чрезмерной специализации, пример которой приведен в (42). С другой стороны, хотя Файкс и др. (1972) предлагают ряд полезных методов обобщения, они первыми признают, что используют эвристические процедуры, не всегда приводящие к требуемой степени общности.

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

таблицу для простого, правильно обобщенного плана

требует в качестве предварительного условия, чтобы робот был в и чтобы соединяла Оператор требует, чтобы робот и ящик были в и чтобы соединяла

Рис. 11.8. Треугольная таблица.

Наконец, заметьте, что список дополнений для содержит что является одним из предварительных условий вычеркивает это предварительное условие из своей модели, добавляя в этот момент и Это означает, что должен содержаться в модели перед выполнением а нет. Предварительные условия плана должны учитывать это.

Треугольная таблица для плана (44) показана на рис. 11.8. В более общей форме: если план состоит из шагов, таблица будет состоять из строк и столбцов, образующих треугольник. Строки нумеруются от 1 до а столбцы от 0 до При построении таблицы можно выделить следующие шаги:

(а) В столбце строке поместить список дополнений оператора .

(б) В столбце строке поместить те предложения столбца строки которые останутся в модели после применения оператора т. е. предложения столбца

строки не содержащиеся в списке вычеркиваний оператора На рис. 11.8 в столбце 1 перечисляются результаты оператора на разных стадиях. Вначале помещает робот в комнату поэтому предложение добавлено к модели и помещено в столбец 1 строку 2. Следующий оператор выводит робота из поэтому в столбце 1 строке 3 пусто. Подобным образом предложения и добавленные к модели мира оператором следует поместить в столбец 2 строку 3. Ясно, что эту процедуру можно применить к плану с произвольным числом шагов.

(в) Осталось построить столбец 0. Это получается после рассмотрения предусловий оператора, который нужно применить на шаге В столбце 0 строке помещаются утверждения предварительного условия, которые должны быть в модели до применения оператора но которые еще не появились в строке в результате предыдущих операций. Так, в столбце 0 строке 2 перечисляются предварительные условия за исключением которое появилось в результате предыдущего действия

При данных правилах построения треугольной таблицы должно быть, вообще говоря, несколько входов в строку которые не являются предусловиями для оператора Для того чтобы отличить предложения предусловия в строке от других предложений, они помечаются звездочкой.

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

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

Хотя широкое применение планов — очень новое достижение, мы считаем, что существуют по крайней мере три более ранние

программы, порождавшие планы подобного рода. Сэмюэль (1967) предложил программу игры в шахматы, которая накапливает статистику в ситуациях, когда определенная последовательность оказывается хорошей, и пользуется этой статистикой для построения сложного нелинейного распознавателя, показывающего, насколько текущая игра похожа на предыдущие. Куинлан (1969) построил аналогичное расширение FDS и показал, что „обучение" в одной области — логике — можно обобщить на сходные области элементарной математики. Оба приложения имели успех, но казались более примером на тему распознавания образов при доказательстве теорем, чем планированием в том смысле, как мы употребляли здесь это слово. Гелернтер (1959) использовал метод планирования, названный синтаксической симметрией, который сходен со „сверхспециализированным" планированием в STRIPS, проиллюстрированным в (42); он применил этот метод при доказательстве геометрических теорем для того, чтобы избежать повторных решений одной и той же подзадачи. Клинг (1971) предложил систему, в чем-то похожую на систему Гелернтера, для использования при доказательстве теорем, основанном на принципе резолюции. О методе Клинга нельзя говорить, не объяснив сначала, как на основе принципа резолюции доказываются теоремы, поэтому мы отложим его до конца следующей главы.