Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 148
Текст из файла (страница 148)
Это — следствие увеличения количества литералов: если предусловия некоторого действия появляются на одном уровне, они будут появляться и на последующих уровнях и поэтому то же происходит и с действиями. ° Количество взаимно исключающих связей уменьшается монотонно. Если два действия на данном конкретном уровне А, являются взаимно исключающими, то они должны также быть взаимно исключающими на всех предыдущих уровнях, на которых они появлялись вместе. То же утверждение остается справедливым и по отношению к взаимно исключающим связям между литератами.
Это не означает, что взаимно исключающие связи характеризуются такими же особенностями и на рисунках с изображением графов планирования, поскольку на рисунках допускаются упрощения: на них не показывают ни литералов, которые не могут быть истинными на уровне Я„ни действий„ которые не могут быть выполнены на уровне л,. Можно убедиться в справедливости утверждения, что "количество взаимно исключающих связей умень- 545 Глава ! 1. Основы планирования шается монотонно", если учесть, что эти невидимые литералы и действия яв- ляются взаимно исключающими по отношению ко всем прочим.
Доказательство этих утверждений является довольно сложным, но может быть выполнено путем анализа отдельных случаев; если действия А и В являются взаимно исключающими на уровне л„, то должны быть таковыми из-за наличия одного из трех типов взаимно исключающих связей. Первые два из них, несогласованные результаты и вмешательство, обусловлены свойствами самих действий, поэтому, если действия являются взаимно исключающими на уровне л„то будут взаимно исключающими на каждом уровне.
Третий случай, с конкурирующими потребностями, зависит от условий на уровне Я,: этот уровень должен содержать предусловие действия л, которое является взаимно исключающим по отношению к предусловию действия в. Теперь отметим, что эти два предусловия могут быть взаимно исключающими, если они являются отрицаниями друг друга (и в этом случае они будут взаимно исключающими на каждом уровне) или все действия по достижении одного из них являются взаимно исключающими по отношению ко всем действиям, необходимым для достижения другого.
Но мы уже знаем, что количество допустимых действий увеличивается монотонно, поэтому по индукции количество взаимно исключающих связей должно уменьшаться. Поскольку количество действий и литералов увеличивается, а количество взаимно исключающих связей уменьшается, и поскольку имеется только конечное количество действий и литералов, каждый граф планирования в конечном итоге выравнивается — все последующие уровни в нем становятся идентичными. После того как граф выровнялся, он может быть проанализирован, и если в нем отсутствует одна из целей задачи или две цели являются взаимно исключающими, то данная задача никогда не может быть решена, поэтому мы можем остановить работу алгоритма Схар1зр1ап и вернуть индикатор неудачи. Если же граф выравнивается со всеми присутствующими и не взаимно исключающими целями, но функция ЕхсгассБо1псзоп оказывается не в состоянии найти решения, то может потребоваться снова расширить граф конечное количество раз, но так или иначе мы имеем возможность остановить работу алгоритма.
Последний вариант завершения является более сложным и здесь не рассматривается. 11.5. ПЛАНИРОВАНИЕ С ПОМОЩЬЮ ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКИ Как было описано в главе 10, планирование может осуществляться по принципу доказательства некоторой теоремы в рамках ситуационного исчисления. В подобной теореме утверждается, что при наличии начального состояния и аксиом состояния- преемника, которые описывают результаты действий, цель будет истинной в ситуации, которая является результатом некоторой последовательности действий.
В такой ранний период развития искусственного интеллекта, как 1969 год, данный подход считался слишком неэффективным для того, чтобы с его помощью можно было находить интересные планы. Проведенные в последнее время разработки в области эффективных алгоритмов формирования рассуждений для пропозициональной ло- 546 Часть)Ъ'. Планирование гики (см. главу 7) привели к возрождению интереса к планированию с помощью логических рассумллений. Подход, принятый в данном разделе, основан на проверке выполнимости логического высказывания, а не на доказательстве теорем.
Мы будем отыскивать модели для пропозициональных высказываний, которые выглядят примерно так: Начальное состояние и Все возможные описания действий л Цель Такое высказывание должно содержать пропозициональные символы, соответствующие каждому возможному проявлению действия; модель, в которой выполняется это высказывание, должна присваивать значение сдце действиям, являющимся частью правильного плана, и Еа2эе — другим действиям.
Присваивание, которое соответствует неправильному плану, не будет моделью, поскольку окажется несовместимым с утверждением, что цель истинна. Если задача планирования неразрешима, то данное высказывание будет невыполнимым. Описание задач планирования в пропозицнональной логике Процесс, который будет здесь применяться для перевода задач Б)пра на язык пропозициональной логики, представляет собой (так сказать) классический пример цикла представления знаний: мы начнем с множества аксиом, которое на первый взгляд кажется приемлемым, обнаружим, что эти аксиомы допускают появление фиктивных, не предусмотренных моделей, а затем запишем дополнительные аксиомы.
Начнем с очень простой задачи воздушной транспортировки. В начальном состоянии (время О) самолет Р, находится в аэропорту ЯРО, а самолет Р, — в аэропорту ЦРК. Задача состоит в том, чтобы Р, находился в тРК, а Р, — в ЯРО; иными словами, самолеты должны поменяться местами. Прежде всего, потребуются отдельные пропозициональные символы для формирования утверждений о каждом временном этапе. Для обозначения временного этапа будут использоваться верхние индексы, как и в главе 7.
Поэтому начальное состояние можно записать следующим образом: ЛС ) Р,, ЛРО) ' ь Ле ) Р„,тРК) ' (напомним, что ле (Р„БРО) ' — это атомарный символ.) поскольку в пропозициональной логике не принято предположение о замкнутом мире, необходимо также определить высказывания, которые не являются истинными в начальном состоянии.
Если же некоторые высказывания в начальном состоянии не известны, они могут оставаться неопределенными (предположение об открытом мире). В данном примере зададим следующее: — Ц)С) Ры ЯРК) и АЕ )Рр, ЯРО) Сама цель должна быть связана с конкретным временным этапом. Поскольку мы не знаем заранее, какое количество этапов потребуется для достижения цели, то можно попытаться сформулировать утверждение, что цель истинна в начальном состоянии, во время т=о. Это означает, что мы вводим утверждение лс (Р,,,тРк) ' л лс (Р„РРО) '. Если эта попытка окажется неудачной, повторим ее снова во время Т=1 и т.д. до тех пор, пока не достигнем осуществимого плана с минимальной длиной.
Для каждого значения т база знаний будет включать только высказывания, покрывающие временные этапы от 0 вплоть до т. Чтобы обеспечить завершение работы алгоритма, можно наложить произвольный верхний предел, 547 Глава 11. Основы планирования т „. Этот алгоритм приведен в листинге 11.7. Альтернативный подход, позволяющий избежать использования многочисленных попыток решения, обсуждается в упр.
11.17. Листинг 11.7. Алгоритм Ядтр1ап. Задача планирования преобразуется в высказывание в форме СГчр, н котором подтверждается истинность цели на фиксированном временном этапе т, а аксиомы добавляются на каждом временном этапе вплоть до т. (Подробные сведения о преобразовании приведены а тексте главы.) Если алгоритм проверки выполнимости находит модель, то план извлекается путем поиска тех пропознцнональных символов, которые относятся к действиям н которым в модели присвоено значение сгие.
Если модель не существует, то процесс повторяется после передвижения цели на один этап дальше Еипоадоп ЯАТр1ап(рхоЫет, Т,„) гесигпн решение зо1иезоп или индикатор неудачи Еаз1ихе Еприен: рхоЫет, задача планирования Т,, верхний предел длины плана Еог Т = О Со Т По спе, таррбпр + — тхапа1асе-то-ЯАт(рхоыем, т) аяябрптепе а- яАТ-яо1чех(спЕ) зе присваивание аэзбоптепс не является неопределенным сьеп гееигп Ехехасе-ло1иеьоп(ааз1дптепс, таррбпр) гесигп Еаз1ихе Следующая проблема состоит в том, как закодировать описания действий в пропозициональной логике.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
