В программах плакировщиков, приведенных в листингах 17,3 и 17.4, по сути используются стратегии поиска в глубину, но не в полной мере. Для того чтобы получить исчерпывающее представление о том, что происходит, необходимо определить, в какой последовательности планировщик вырабатывает возможные планы. В этом отношении очень важной является следующая цель в процедуре plan:
conc(Preplan, [Action | PostPlan], Plan)
В данный момент переменная Plan еще не конкретизирована и процедура cone вырабатывает с помощью перебора с возвратами альтернативные варианты для переменной PrePlan в следующем порядке: Preplan = []; PrePlan = [ _1; Preplan - [, ]; Preplan = [ _ _, _ _, _];
Вначале появляются более короткие варианты для переменной PrePlan. Переменная PrePlan устанавливает предпосылки для действия Action. Этот процесс сводится к поиску действия, предпосылки которого могут быть созданы с помощью наиболее короткого плана из всех возможных (по методу итеративного углубления), С другой стороны, список вариантов для переменной PostPlan является полностью неконкретизированным и поэтому его длина не ограничена. Таким образом, результирующее поведение процедуры поиска представляет собой в "глобальном аспекте" поиск в глубину, а в "локальном аспекте" - поиск в ширину. Он является поиском в глубину по отношению к определению с помощью прямого логического вывода тех действий, которые добавляются к формируемому плану. Предпосылки для каждого действия создаются с помощью "предварительного плана". С другой стороны, поиск этого предварительного плана происходит в режиме поиска в ширину.
Один из способов максимального сокращения длины планов состоит в том, что планировщик можно вынудить использовать режим поиска в ширину таким образом, чтобы все короткие варианты планов рассматривались прежде, чем длинные. Такую стратегию можно реализовать, встроив планировщик в процедуру, которая вырабатывает варианты планов в порядке возрастания длины. Например, следующая программа приводит к реализации режима итеративного углубления: bteadth_first_plan(state, Goals, Plan, FinalState):-
candidate < Plan), % Вначале формировать короткие планы
plan(State, Goals, Plan, Finalstatej,
candidate! [First I Rest]):-candidate (Rest).
Более изящное решение состоит в том, что в программе можно достичь аналогичного эффекта, вставив соответствующий генератор вариантов плана непосредственно в процедуру plan. Такой подходящий генератор представляет собой следующую процедуру: cone! Plan, _, _)
Эта процедура с помощью перебора с возвратами вырабатывает списки действий все возрастающей длины. Теперь в программу планировщика (см. листинг 17.3) можно внести следующие изменения: plant state, Goals, Plan, FinState);-
cone (Plan, _, _), % в первую очередь формировать более короткие списки
<к возможных действий eonc(PrePlan, [Action | PostPlan], Plan),
Глава 17. Планирование
Аналогичная модификация позволяет также перевести в режим поиска в ширину программу планировщика с защитой целей, приведенную в листинге 17.4.
Проверим работу модифицированных планировщиков, которые теперь работают в режиме поиска в ширину, на двух примерах задач. Если предположить, что Start — это начальное состояние, показанное на рис. 17.1, то цель
plant Start, [ clear! 2), clear(3}], Plan, _)
приводит к получению такого плана: Plan = [ move ( b, 3, 4) ]
Данный план уже является оптимальным. Но задача, показанная на рис. 17.1, все еще является источником определенных проблем. После постановки цели plant Start, t cn( а, Ь), on(b, с]], Plan, _) вырабатывается такой план:
move (с, а, 2)
move (Ь, 3, а}
move! Ь, а, с]
mcve(а, 1, Ы
Этот результат был получен от обоих планировщиков, с защитой и без защиты целей, работающих в режиме поиска в ширину. Второе из приведенных выше действий является излишним и, безусловно, не имеет смысла. Рассмотрим, как оно вообще попало в план и почему даже поиск в ширину приводит к созданию плана, более длинного, чем оптимальный.
Для этого необходимо ответить на два вопроса. Во-первых, в результате какой цепочки рассуждений планировщик приходит к формированию приведенного выше не совсем разумного плана? Во-вторых, почему планировщик не находит оптимальный план, в который не включено это загадочное действие move (Ъ, 3, а)? Начнем с поиска ответа на первый вопрос. Последнее действие, move (а, 1, Ь), позволяет достичь цели on [ a, b), а первые три действия создают предпосылки для действия move [ а, 1, Ь), в частности, создают состояние clear (а). После третьего действия открывается верхняя грань блока а, при этом частью предпосылок для третьего действия является on (b, а). Такое состояние достигается с помощью второго действия, move [ Ь, 3, а). Первое действие открывает верхнюю грань блока а для обеспечения возможности второго действия. Таким образом, найдено объяснение хода рассуждений, лежащего в основе полученного громоздкого плана, а также показано, какие странные "идеи" могут обнаруживаться во время планирования с помощью анализа целей и средств.
Второй вопрос состоит в том, почему после действия move \ с, а, 2) планировщик не приступает немедленно к рассмотрению действия move (Ъ, 3, с), которое ведет к созданию оптимального плана. Причина этого состоит в том, что планировщик постоянно работает над целью on (а, Ь). Действие move [ Ь, 3, с) является полностью излишним с точки зрения достижения этой цели, и поэтому попытки его использования не предпринимаются. В этом четырехэтапном плане достигается цель on (а, Ь), а также, по стечению обстоятельств, - цель on [ b, с), Поэтому достижение цели on (Ь, с} является исключительно результатом удачи, а не каких-либо сознательных усилий со стороны планировщика. Слепо преследуя лишь цель оп{ а, Ь) и относящиеся к этому предпосылки, планировщик не видит причин для выполнения действия aiove (Ъ, 3, с) перед действием move (b, 3, а).
Из приведенного выше примера следует, что механизм планирования по принципу целей и средств в том виде, в каком он реализован в рассматриваемых планировщиках, является неполным. Он не предоставляет для процесса планирования возможность проверить все возможные действия, ведущие к цели. Причина этого состоит в его узкой направленности. Планировщик рассматривает только те действия, которые относятся к текущей цели, и игнорирует другие цели до тех пор, пока текущая цель не будет достигнута. Поэтому он не вырабатывает планы, в которых чередуются действия, относящиеся к разным целям (кроме как в результате счастливо-
Часть II. Применение языка Prolog в области искусственного интеллекта
го стечении обстоятельств). Основным способом достижения требуемой полноты анализа, которая гарантирует включение оптимальных планов в реализуемую схему планирования, является обеспечение взаимодействия различных целей. Такая задача будет решена в следующем разделе с помощью механизма регрессии целей.
Прежде чем завершить данный раздел, необходимо сделать замечание, касающееся эффективности описанных здесь планировщиков с поиском в глубину и в ширину. Хотя режим поиска в ширину в рассматриваемом примере задачи обеспечивает получение гораздо более короткого плана (хотя тл все еще неоптимального!), затраты ресурсов времени, необходимые для поиска этого короткого плана, оказались намного больше по сравнению с затратами времени на поиск более длинного плана с семью этапами в планировщике, работающем в режиме поиска в глубину. Поэтому планировщик, который осуществляет поиск в глубину, не следует заведомо рассматривать как худший по сравнению с планировщиком, работающим в режиме поиска в ширину, даже если он вырабатывает не такие короткие планы. Следует также отметить, что в рассматриваемых планировщиках эффект поиска в ширину достигнут благодаря использованию метода итеративного углубления (см. главу 11).
Упражнение
17.4. Знания в области планирования, относящиеся к конкретной проблемной области, могут быть введены в рассматриваемый планировщик естественным образом с помощью предикатов select и achieves. Эти предикаты выбирают следующую цель, попытка достижения которой должна быть предпринята планировщиком (определяя порядок, в котором достигаются цели), и предпринимаемое при этом действие. Переопределите эти два предиката для мира блоков таким образом, чтобы выбор целей и действий осуществлялся бплее обоснованно. Для этого удобно ввести текущее состояние State в качестве дополнительного параметра в предикат achieves.
