Анализ методов интеллектуального планирования.

Применение правила R преобразует состояние s в s¢ следующим образом: s' = (s-(D(R)q))È(A(R)q)).

Это преобразование обозначается так: S S¢. можно видеть использование STRIPS-допущения для решения проблемы фрейма.

STRIPS-допущение при применении некоторого правила R к состоянию s выполнимость факта fÎs изменяется, только если факт f описан либо в списке удалений D(R), либо в списке добавлений A(R).

Технически, при проверке применимости некоторого правила R, STRIPS выполняет полную подстановку на место всех переменных некоторых констант. Возможны различные варианты подстановок. Некоторые варианты подстановки могут давать примеры правил, применимые (или же неприменимые) в состоянии s. Однако, как подметили авторы STRIPS [24], в алгоритм STRIPS можно внести незначительные модификации для применения не полностью означенных правил. В этом случае, в состоянии S появились бы факты с переменными в описании. Как будет видно далее, неполная подстановка активно используется планировщиками в пространстве планов. Соответствующее свойство этих планировщиков получило название малого связывания (least commitment).

Дадим постановку задачи STRIPS-планирования.

Будем называть доменом планирования Р = <, SR>, где , - начальное состояние, SR - конечное множество правил.

Будем называть задачей планирования Т = <Р, G>, где G -описание целевого факта агента, или просто цель.

Решение задачи планирования Т заключается в нахождении плана, который достигает цели G.

План Plan- это последовательность состояний , …, sn, последовательность правил

, ., , и последовательность подстановок , ., , такая что, G выполнима в sn. Длина плана Plan равна n.

Plan:

Опишем сам алгоритм STRIPS (Рисунок 2).

Изначально на вход алгоритма STRIPS подаётся множество правил SR, начальное состояние So, цель G.

Будем полагать, что в множестве SR. все правила полностью конкретизированы.

Рисунок 2 - Алгоритм STRIPS

Вначале в стек целей помещается главная цель G.

Если цель не является простой, т.е. содержит конъюнкцию литералов, то система STRIPS добавляет в стек в некотором порядке каждый из литералов составной цели (п. 1.1). Когда верхняя цель стока является однолитераьной,

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

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

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

Впервые некорректность STRIPS 'a была вскрыта в 1973 году Аленом Брауном в Массачусетском технологическом институте. Браун попытался решить задачу, рассматриваемую в этом разделе на планировщике HACKER. HACKER был создан Джеральдом Суссманом на основе планировщика STRIPS, поэтому задача получила название аномалия Суссмана (Sussman Anomaly).

Рассмотрим аномалию Суссмана [49].

Дано:

Объекты:

кубика - А, В, С.

Состояние описывается предикатами:

ontable (х) - кубик х на столе,

clear (х) - над кубиком х пусто,

handempty - рука агента пуста,

holding (х) - рука агента держит кубик х,

on (х,у) - кубик х находится на кубике у.

х, у -переменные.

Правила:

Rl: pickup (x) - поднять кубик со стола

С (Rl): ontable (х) & clear (х) handempty(Rl): holding (х)(Rl): ontable (х), clear (х), handempty R2: putdown (x) - опустить кубик на стол