Защита целей

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

Часть II. Применение языка Prolog в области искусственного интеллекта

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

Еще раз вернемся к задаче, показанной на рис. 17.1. Предположим, что Start -это описание начального состояния на рис. 17.1. В таком случае данную задачу мож­но сформулировать в виде следующей цели: planC Start, [ оп(a, b), on (Ь, с)], Plan, _)

План, найденный планировщиком, показан ниже.

Plan - [ move С Ъ, 3, с),

move! b, с, 3),

move (с, a, 2),

movet a, 1, b),

move [ a, b, 1),

movet b, 3, с),

mqve[ a, 1, b)]

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

нюте< b, 3, с), чтобы достичь цели оп(ь, с)

move(Ь, с, з>, чтобы достичь цели clear [ с) для обеспечения

дальнейшего перемещения Bovef с, а, 2), чтобы достичь цели clear [ а) для обеспечения

возможности выполнения действия move (а, 1, Ь) movet а, 1, Ь), чтобы достичь цели on i г, Ъ) move< a, ь_г 1), чтобы достичь цели clear(bj для обеспечения

возможности выполнения действия move (b, 3, с) move(b, 3, с), чтобы достичь цели on (Ь, с) (повторно) movet а, 1, ы, чтобы достичь цели on(a_r b) (повторно)

Обнаруживающийся здесь недостаток состоит в том, что планировщик иногда уничтожает цели, которые уже были достигнуты. Планировщик легко достиг одной из двух заданных целей, on (b, с), но затем немедленно ее уничтожил, приступив к работе над другой целью, on (a, b). После этого он снова перешел к попыткам достичь цели on [ b, с). Она была достигнута за два хода, но между тем была раз­рушена цель on { а_г Ь). К счастью, в следующий раз цель on (а, Ы была достиг­нута без повторного разрушения цели on (Ь, с). Такое довольно неорганизованное поведение в следующем примере приводит к еще более ярко выраженным отрица­тельным результатам — к полной неудаче:

plant Start, [ Clear; 2), clear (3) ], Plan, _)

Теперь планировщик до бесконечности продлевает показанную ниже последова­тельность действий.

itewi Ь, 3, 2J, чтобы достичь цели clear< 3}

movet Ь, 2, 3>, чтобы достичь цели clear(2

move! b, 3, 2), чтобы достичь цели clear 3

move (b, 2_Г 3), чтобы достичь цели clear(2)

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

Из приведенных выше примеров следует одна очевидная идея, что планировщик должен всегда пытаться сохранить уже достигнутые цели. Эту задачу можно решить,

Глава 17. Планирование

сопровождая список уже достигнутых целей и в дальнейшем избегая таких дейст­вий, которые уничтожают цели в этом списке. Поэтому введем новый параметр в от­ношение plan, таким образом: plant State, Goals, ProtectedGoals, Plan, FinalState)

где ProtectedGoals - это список целей, "защищаемых" планом Plan. Это означает, что ни одно из действий в плане Plan не должно удалять ни одну из целей в списке ProtectedGoals. После достижения новой цели она добавляется к списку защищен­ных целей. Программа, приведенная в листинге 17.4, представляет собой модифика­цию программы планировщика (см. листинг 17,3) с реализованной защитой целей. Теперь задача освобождения мест 2 и 3 решается с помощью следующего плана, со­стоящего из двух этапов:

move) Ь, 3, 2), чтобы достичь цели clear (3} move! b, 2, 4), чтобы достичь цели clear (2) и вместе с тем защитить цель clear (3)

Листинг 17.4. Планировщик с применением анализа целей и средств, в котором осуществляется защита целей. Предикаты satisfied.select, achieves и apply приведены в листинге 17.3

Планировщик с применением анализа целей и средств, в котором % осуществляется защита целей

plan{ InitialState, Goals, Plan, FinalState}:-plan! InitialState, Goals, [], Plan, FinalState).

% plan(InitialState, Goals, ProtectedGoals, Plan, FinalState):

цели Goals являются истинными в состоянии FinalState, защищенные цели никогда не разрушаются планом Plan

plan[ State, Goals, _, [], State):-

satisfiedt State, Goals). % Цели Goals являются истинными

% в состоянии State

plant State, Goals, Protected, Plan, FinalState*:-

conct Preplan, [Action PostPlan], Plan), % Выполнить декомпозицию плана

select(State, Goals, Goal), % Выбрать недостигнутую цель

achieves! Action, Goal),

can(Action, Condition),

preserves | Action, Protected), % He уничтожать защищенные цели

plant State, Condition, Protected, Preplan, MidStatel),

apply; Midstatel, Action, MidState2),

planf Midstate2, Goals, [Goal Protected], PostPlan, FinalState).

% preserves Action, Goals):

% действие Action не приводит к разрушению ни одной из целей Goals

preserves(Action, Goals):- % Действие Action не разрушает цели Goals deletes (Action, Relations), not [member! Goal, Relations), member(Goal, Goals]),

Очевидно, что эта программа работает гораздо лучше, чем прежняя, хотя все еще не позволяет найти оптимальное решение, поскольку фактически требуется только одно действие - move (Ь, 3, 4).

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

Часть I I. Применение языка Prolog в области искусственного интеллекта