После проведения экспериментов по использованию данного планировщика в мире блоков и в мире фотокамеры обнаруживается, что мир блоков является гораздо более сложным. Это может на первый взгляд показаться удивительным, поскольку определение мира блоков выглядит проще по сравнению с миром фотокамеры. Истинная причина большей сложности мира блоков заключается в том, что он характе-
Часть 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(ar 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 в области искусственного интеллекта
