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

С (R2): holding (х)(R2): ontable (х), clear (х), handempty (R2): holding (х)

R3: stack (х,у) - положить кубик на другой кубик

C(R3): holding (х) & clear (у)(R3): handempty, on (x,y), clear (x)(R3): holding (x), clear (y)4: unstack (x,y) - снять кубик с другою кубика

C(R4): handempty & on(x,y) & clear (x)(R4): holding (x), clear (y)(R4): handempty, on(x,y), clear (x)

Начальное состояние s0 и цель G изображены на рис.3.

Таким образом, цель G= {On (А,В) & On (В,С)}.

Поскольку цель G является составной, то STRIPS расщепляет её на отдельные компоненты - On (А,В) и On (В,С), которые помещаются в стек и удовлетворяются по очереди.

Рисунок 3 - Аномалия Суссмана

Положим, что On (А,В) наверху стека, тогда планировщик находит следующую последовательность правил для удовлетворения On (А,В):

UNSTACK(C,A), PUTDOWN(C), PICKUP(A), STACK (A,B).

Применяет найденную последовательность к состоянию So. Получается ситуация, изображённая на рис.4, в которой On (А,В) выполнима. Цель On (А,В) удаляется из стека целей. On (А.В) удовлетворено.

Далее, из ситуации на рисунке 4 , удовлетворяется следующая цель в стеке - On (В,С). В результате имеем: UNSTACK(C,A), PUTDOWN(C), PICKUP(A), STACK (A,B), UNSTACK(A.B). PUTDOWN(A) PICKUP(B), STACK (B.C).

Рисунок 4 - Удовлетворение первой цели

Применяем последовательность подчёркнутых правил. И, получаем ситуацию на рисунке 5. Цель On (В,С) удовлетворена и удаляется из стека. Однако цель Оn(А,В), удовлетворённая на предыдущем этапе, перестает быть выполнимой.

И, поэтому, теперь планировщик пытается из ситуации на рисунке 5 удовлетворить On (А,В). Это приводит к добавлению ещё двух правил к имеющейся последовательности.

Рисунок 5 - Удовлетворение второй цели

В результате получаем план:

(C,A), PUTDOWN(C),

PICKUP(A), STACK (A,B), UNSTACK(A,B), PUTDOWN(A), PICKUP(B),STACK (B,C), PICKUP(A), STACK (А.В)

Подчёркнутые правила применяются. Цель On (А,В) & On (В,С) достигается. План построен.

Однако существует другой план, содержащий меньше действий:

UNSTACK(C,A), PUTDOWN(C), PICKUP(B), STACK (B,C), PICKUP(A), STACK(A,B)

Рассмотрим вычислительную сложность задачи STRIPS-планирования.

Описание задачи классического планирования в терминах STRIPS допускается любым планировщиком. Поэтому рассмотрим вычислительную сложность задачи STRIPS-планирования [23,17, 22].

Далее будем рассматривать случай разрешимой задачи планирования, вычислительная сложность которой (таблица 1), варьируется от постоянного времени до EXPSPACE-полноты в зависимости от ограничений, накладываемых на язык домена, планирования Р.

Таблица 1 - Вычислительная сложность задачи планирования