Процедурные аспекты и режим поиска в ширину

В программах плакировщиков, приведенных в листингах 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, все еще является источником определенных проблем. После постановки цели plantStart, 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.