Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 149
Текст из файла (страница 149)
Наиболее прямолинейный подход состоит в том, чтобы было предусмотрено по одному пропозиционаяьному символу на каждое проявление действия; например, символ Р1у(Р„ЕРО, трк) ' является истинным, если самолет Р, вылетает из аэропорта ЯРО в аэропорт трк во время О. Как и в главе 7, мы запишем пропозициональные версии аксиом состояния-преемника, разработанных для ситуационного исчисления в главе 1О. Например, иь)еет место следующее: Ас(р,,,ткк)" аа (Ас(р,,ткк) ' к -(Р1у(), .ткк, яко) ' к Ас(Р,„ткк)') ) ч (Рзу(Р, ЯРО,,ГРК) к АС (, ЯРО) ) (11.1) Это означает, что самолет Р, должен находиться в аэропорту тРК во время 1, если он был в .трк во время О и не улетел или если он был в аэропорту яРО во время О и прилетел в аэропорт ткк.
Необходимо иметь по одной такой аксиоме лля каждого самолета, аэропорта и временного этапа. Более того, каждый лополнительный аэропорт добавляет еще один способ путешествия из каждого конкретного аэропорта или в этот аэропорт и поэтому вносит еше больше дизъюнктов в правую часть каждой аксиомы. После подготовки всех этих аксиом можно вызвать алгоритм проверки выполнимости, чтобы найти план. Это должен быть план, который достигает цели во время Т=1, а именно план, в котором эти два самолета меняются местами.
Теперь предположим, что база знаний представляет собой следующее высказывание: Начальное состояние ь Аксиомы состояния-преемника к Пель (11.2) в котором утверждается, что цель истинна во время Тм1. Читатель может проверить, что утверждение, в котором символы Р1у(Рз, ЯРО, 7РК) и Р1у(Рз, ГКК, ЯРО) 548 Часть 1Ч. Планирование являются истинными, а все другие символы действий являются ложными, представляет собой модель этой базы знаний. До сих пор все идет хорошо.
Но есть ли другие возможные модели, которые способен вернуть этот алгоритм проверки выполнимости? Безусловно, да. Являются ли все эти другие модели удовлетворительными планами? К сожалению, нет. Рассмотрим довольно глупый план, заданный с помощью указанных символов действий: Р1у(р„дРО,.тРК)' н РЗу(р,,тух,яРО)' н РЗу(Р„ОРК,ВРО)' Этот план глуп потому, что самолет Р, вначале находится в аэропорту ЯРО, поэтому действие Р)у(Р„.?РК, яРО) ' является неосуществимым. Тем не менее этот план действительно представляет собой модель высказывания из уравнения 11.2! Иными словами, он согласуется со всем, чтобы сказано до сих пор об этой задаче.
Чтобы понять, чем может быть вызвано появление такого плана, мы должны проанализировать более тщательно, что сказано в аксиомах состояния-преемника (таких как уравнение 11.1) о действиях, предусловия которых не выполнены. Аксиомы правильно предсказывают, что ничего не произойдет при попытке выполнить подобное действие (см. упр. 11.15), но в них ничего не сказано, что такое действие не может быть выполнено! Чтобы предотвратить выработку планов с недопустимыми действиями, мы должны добавить Ъ.аксиомы предусловий (ргесопгй(юп ах(опз), которые указывают, что для совершения любого действия требуется, чтобы были выполнены его предусловия'.
Например, требуется указать следующее: РЗу(Р„.тРК,ДРО)' ~ ЛЕ(Р,„тРК)' Поскольку указано, что в начальном состоянии символ дс (Р,, 7Рк) является ложным, зта аксиома гарантирует, что в каждой модели символу Р2у( Р,, ТЕК, ЯРО) ' также будет присвоено ложное значение. После введения аксиом предусловия существует одна и только одна модель, которая удовлетворяет всем аксиомам, если цель должна быть достигнута во время 1, а именно модель, в которой самолет Р, летит в аэропорт ,тРК, а самолет Р, — в аэропорт КРО.
Обратите внимание на то, что это решение обеспечивает выполнение двух параллельных действий, как и при использовании алгоритма Сгар)зр1ап или РОР. Неожиданности возникают после добавления третьего аэропорта, АХ Теперь для каждого самолета имеются два действия, которые являются допустимыми в каждом состоянии. После применения алгоритма проверки выполнимости мы обнаружим, что модель с символами Р)у(Р„, ыРО,,тРк) ', а также Р)у(Р, .тук, яРО)' и Р2у( Р, .тРк, г з(х) ' удовлетворяет всем аксиомам. Это означает, что аксиомы состояния-преемника и аксиомы предусловия разрешают самолету вылететь в два аэропорта назначения одновременно! Предусловия для двух полетов самолета Р, выполнены в начальном состоянии; аксиомы состояния-преемника указывают, что самолет Р, должен находиться и в аэропорту ЯРО, и в аэропорту БАХ во время 1, поэтому цель выполнена. Очевидно, что необходимо ввести дополнительные аксиомы для устранения таких фиктивных решений. Один из подходов состоит в том, что требуется ввести 'ъ.
аксиомы исключения действий (асйоп ехс1ойоп аиогп), которые предотвращают одновременное выполнение несовместимых действий. Например, можно принудительно ввести полное исключение, добавив все возможные аксиомы в такой форме: Ь Обратите внимание нв то, что добавление аксиом предусловий означает, что не нужно будет включать предусловия для действий в аксиомы состояния-преемника. 549 Глава ! 1. Основы планирования (Рзу(Р2, Тек, явэ) к Р1у(рр, трк, балх) ) Эти аксиомы гарантируют, что никакие два действия не могут происходить одновременно. Они устранят все фиктивные планы, но приведут также к полному упорядочению каждого плана.
В результате гибкость частично упорядоченных планов будет потеряна; кроме того, в результате увеличения количества временных этапов в плане может увеличиться продолжительность вычислений. Вместо полного исключения можно потребовать только частичного исключения, т.е. предотвращения одновременных действий, только если они мешают друг другу. Применяемые при этом условия являются аналогичными условиям для взаимно исключающих действий: два действия не могут происходить одновременно, если одно из них отрицает предусловие или результат другого. Например, не могут происходить одновременно действия р.)у( р, трк, ярО) ' и р2у( р, .трК, Ых) ', поскольку каждое из них отрицает предусловие другого; с другой стороны, действия р2у( р„ярО, .трп) ' и р2у( р„трК, ррО) ' могут осуществляться одновременно, поскольку в них два самолета не мешают друг другу.
Частичное исключение позволяет устранять фиктивные планы, не вводя принудительно полное упорядочение. Аксиомы исключения иногда выглядят как довольно слепой инструмент. Поэтому вместо формирования утверждения о том, что ни один самолет не может вылетать в два аэропорта одновременно, можно просто выдвинуть требование, чтобы ни олин объект не мог находиться в двух местах одновременно: Чр,х,у, е х Ф у => (ле(р,х) л лс(р,у) ) Из этого факта, применяемого в сочетании с аксиомами состояния-преемника, следует, что самолет не может вылететь в два аэропорта одновременно. Факты, подобные этому, называются 'ж ограничениями состояния (з(а(е сопмгаш().
Безусловно, в пропозициональной логике необходимо будет записать все базовые экземпляры каждого ограничения состояния. Для задачи с аэропортами этого ограничения состояния будет достаточно, чтобы исключить все фиктивные планы. Ограничения состояния часто являются гораздо более компактными по сравнению с аксиомами исключения действия, но их не всегда можно легко вывести из первоначального описания задачи на языке Б(г)рк Подводя итог, отметим, что планирование в форме доказательства выполнимости предусматривает поиск моделей для высказывания, включающего описание начального состояния, цели, аксиом состояния-преемника, аксиом предусловий, а также либо аксиом исключения действия, либо аксиом ограничения состояния. Можно показать, что эта коллекция аксиом является достаточной, в том смысле, что при их использовании больше не возникают какие-либо фиктивные "решения".
Любая модель, в которой выполняется такое пропозициональное высказывание, будет представлять собой действительный план для первоначальной задачи; это означает, что любая линеаризация этого плана будет представлять собой допустимую последовательность действий, которая позволяет достичь цели.
Сложности, связанные с использованием пропозицнональных кодировок Основным недостатком описанного пропозиционального подхода являются колоссальные размеры пропозициональной базы знаний, которая формируется на основе первоначальной задачи планирования. Например, схема действий рХу(р, а,, а,) пре- 550 Часть|К. Планирование образуется в Р х ~ р1апез( х )Аулрогсз ~ ' различных пропозициональных симво- лов. Вообще говоря, общее количество символов действий ограничено значением т х )Асс( х )О(', где (Асс( — количествосхемдействий; (О! — количествообь- ектов в проблемной области; Р— максимальная арность (количество параметров) лю- бой схемы действий.
Количество выражений еще больше. Например, при 10 времен- ных этапах, 12 самолетах и 30 аэропортах полная аксиома исключения действий состо- ит из 583 миллионов выражений. Поскольку количество символов действий экспоненциально зависит от арности схемы действий, одним из способов преодоления указанного недостатка может ока- заться попытка уменьшить арность. Это можно сделать, заимствовав одну идею из области семантических сетей (см.
главу 10). В семантических сетях используются только бинарные предикаты; предикаты с большим количеством параметров сводят- ся к множеству бинарных предикатов, которые описывают каждый параметр от- дельно. Применяя эту идею к символу действий, такому как Р1у(Р„ЯРО, ОГК) ', получим следующие три новых символа: Ргу»(Р»)» самолет Р» прилетел во время О Рзуг(ЯРО) » аэропортом отправления в этом полете был ЯРО О, Рзу»( ТЕК)» аэропортом назначения в этом полете был ТРК о, Этот процесс, называемый з.
расщеплением символов (зутпЬо! зр1!п(пя), позволяет устранить необходимость в использовании экспоненциального количества символов. Теперьтребуется толькот х (Асе( х Р х ~ О~ символов. Расщепление символов само по себе позволяет сократить количество символов, но не приводит к автоматическому уменьшению количества аксиом в базе знаний. Это означает, что если бы каждый символ действия в каждом выражении был просто заменен конъюнкцией трех символов, то общий размер базы знаний остался бы примерно тем же самым. Расщепление символов фактически приводит к уменьшению базы знаний потому, что некоторые из расщепленных символов станут нерелевантными для определенных аксиом и могут быть удалены. Например, рассмотрим аксиому состояния-преемника, приведенную в уравнении 11.1, модифицированную так, чтобы в нее был включен символ аэропорта ьАХ и исключены предусловия действия (которые будут учитываться с помощью отдельных аксиом предусловия): ткк)' а» (яе(р-„.тяк)' а Рту(р„,ткк,яко)' я Рту(р„,ткк,ьлх)') ч Угу(Р», ЯРО, тРК) ч Ргу(Р»,ГАХ, ТЕК) В пеРвом Условии сказано, что самолет Рг должен быть в аэРопоРтУ .ТРК, если он находился в нем во время 0 и не улетел из тЕК в какой-то другой город, неважно, какой именно; во втором условии сказано, что он должен находиться в аэропорту .так, если он прилетел туда из другого города, неважно, из какого именно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
