Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 140
Текст из файла (страница 140)
Для повышения удобства чтения в некоторых системах планирования предусмотрено разделение результата на сь список добавления для положительных литералов и Ъ. список удаления для отрицательных литералов. Определив синтаксис представлений задач планирования, можно приступить к определению семантики. Наиболее простой способ выполнения этой задачи со- 516 Часть 1Ч.
Планирование стоит в том, чтобы описать, как действия влияют на состояния. (Альтернативный метод предусматривает определение непосредственного преобразования в аксиомы состояния-преемника, семантика которых основана на логике первого порядка; см. упр. ! 1.3.) Вначале необходимо отметить, что действие 'ж применимо в любом состоянии, в котором выполняется предусловие; в противном случае действие не имеет эффекта. Для схемы действий первого порядка задача определения применимости связана с поиском подстановки О для переменных в предусловии. Например, предположим, что текущее состояние описано следующим образом: ле(п...гпк) л ле(п,, яро) л пзепе(г1) л пзепе(г ) л лтгреге(ппк) л лтгреге(яро) Это состояние удовлетворяет такому предусловию: ле(р, Егот) л птепе(р) л лхгрегг(жгет) л лтгроге(ео) с подстановкой (рур,, гголь',танк, со! ЯЕ01 (кроме всего прочего; см.
упр. 11.2). Поэтому конкретное действие в'1у( рз,,твтг, ~в'0) является применимым. Начиная с состояния э, 'в. результатом выполнения применимого действия а является состояние э', представляющее собой то же самое, что и э, за исключением того, что любой положительный литерал Р в результате а добавляется к э', а любой отрицательный литерал — р удаляется из э '. Таким образом, после выполнения действия Г2у( Р„,тек, яЕО) показанное выше текущее состояние принимает вид ле(п,, яго) л ле(п,, яро) л и. (п1) л пз е(п,) л лтгроге( танк) л лтгроге(япо) Следует отметить, что если какой-то положительный результат уже находится в состоянии а, то не добавляется повторно, а если какой-то отрицательный результат отсутствует в состоянии в, эта часть результата игнорируется. Такое определение воплощает в себе так называемое Ж предположение Б(прз, что каждый литерал, не упомянутый в результате, остается неизменным.
Благодаря этому язык Б(прз позволяет избежать возникновения проблемы представительного окружения, описанной в главе ! О. Наконец, можно определить 'ж решение для задачи планирования. В своей простейшей форме это всего лишь последовательность действий, которая, будучи выполненной в начальном состоянии, приводит к состоянию, удовлетворяющему цели. Далее в этой главе будет показано, как обеспечить возможность использовать решение, представляющее собой частично упорядоченные множества действий, при условии, что каждая последовательность действий, которая отвечает этому частичному упорядочению, является решением.
Выразительность и расширения языка Всевозможные ограничения, налагаемые в представлении 5(прз, были выбраны в надежде на то, что алгоритмы планирования станут более простыми и эффективными и вместе с тем при описании реальных задач не будут возникать слишком значительные трудности. Одно из самых важных ограничений состоит в том, что литералы должны быть свободными от функций. Благодаря наличию такого ограничения можно быть уверенным в том, что каждую схему действий для каждой конкретной задачи удастся пропозиционализировать, т.е.
преобразовать в конечную коллекцию чисто пропозициональных представлений действий без переменных (дополнительную информа- Глава 11. Основы планирования 517 Таблица 11.1. Сравнение языков представления задач планирования 5)г)рз и А1Н. В обоих случаях це- ли выглядят как цредусловця некоторого действия без параметров Язык 5(г)рз Язык А)оь Положительные и отрицательные литералы в состояниях: Ятс)г л Яалгсца Только положительные литералы Всостояниях: РООс л цп)глоб Предположение об открытом мире: неупомянутые литералы являются неизвестными Предположение о замкнутом мире: неупомянутые литералы являются ложными Результат я л Дозиачаетдобавление я и удаление О Результат Я л 0 означает добавление Я и гз и удаление Яиа Квантифицированиые переменные в целях: цель Эх Ас(ртх) л Ас(зэ,х) состоит атом, чтобы Яг и Ях нахолились в одном и том же месте Только базовые литералы в це- лях: Ятсд л Яатсца В целях допускается использование конъюнкций и д изъюикций.
Росс л (яатсца ч ятагс) 1(ели представляют собой конь- юикции:Ятсд л Яатсца Результаты представляют собой конъюнкции Разрешены условные результаты: иивц Я: Я означает, что Я является результатом, только если выполнено условие я Отсутствует поддержка от но шел- ияя равенства Предикат равенства (х=у) является встроенным Отсутствует поддержка типов Переменные могут иметь типы, как, например, в выражении (р;Язаце) Обозначение р: р1апе в списке параметров представляет собой сокрашение для Р1апе(р) в предусловии; применение такого обозначения не приводит к повышению выразительной мощи, но позволяет повысить удобство для чтения. (Применение этого обозначения приводит также к сокращению количества возможных пропозициональных действий, которые могут быть сконструированы.) Предусловие ( Есолха со) выражает тот Факт, что полет не может быть совершен из некоторого аэропорта в сам этот аэропорт.
Такое условие не может быть выражено кратко в языке 5(прз. цию по этой теме см. в главе 9). Например, в проблемной области грузовых авиационных перевозок для задачи с десятью самолетами и пятью аэропортами можно преобразовать схему Я1у(р, Есот, со) в 10х5х5=250 чисто пропозициональных действий. Планировщики, описанные в разделах 11.4 и 1!.5, работают непосредственно с пропозиционализированными описаниями.
Если же будут разрешены функциональные символы, то количество состояний и действий, которые могут быть сконструированы, станет бесконечно большим. В послелние годы стало очевидно, что язык 5(прз является недостаточно выразительным для некоторых реальных проблемных областей. В результате этого было разработано много вариантов данного языка. В табл.
11.1 кратко описан наиболее важный из них, язык аь АЭЬ (Асйоп Резспр(!оп Ьапяцаяе — язык описания действий), на основе его сравнения с базовым языком 5(прз. В языке АРЬ действие р1у можно записать следуюшим образом: Ассхсп (я1у(рг я1апе, Еготглтгросс, со;Атгрсхс), Рхесоцгы АС(р, Егот) л (Есот Х Со), ВЕЕесС: АС(р, Егот) л АС(р, Со)) 518 Часть !Ч.
Планирование Различные формальные средства планирования, применяемые в искусственном интеллекте, были систематизированы в рамках стандартного синтаксиса, получившего название РРР1. (Р)апп(п8 Ротпаш Рейпгйоп ).апйиаде — язык определения проблемной области планирования). Этот язык позволяет исследователям обмениваться эталонными тестовыми задачами и сравнивать полученные результаты.
Язык РРР(. включает подязыки для 5(г(рз, АР(. и иерархических сетей задач (Н(егагсЫса) Таз)[ Хе(тчог)[ — НТ)ч'), которые будут рассматриваться в главе 12. Системы обозначений 8(г(рз и АР). являются вполне приемлемыми для многих реальных проблемных областей. В приведенных ниже подразделах описаны некоторые простые примеры.
Тем не менее эти языки все еше характеризуются некоторыми сушественными ограничениями. Наиболее очевидным из них является то, что эти языки не позволяют представить естественным образом последствия действий. Например, если в самолете есть люди, пакеты или частички пыли, то все они в процессе полета самолета также меняют свое местонахождение.
Можно было бы представить эти изменения как прямой результат полета, но кажется более естественным представить изменение местонахождения содержимого самолета как логическое следствие изменения местонахождения самого самолета. Дополнительные примеры подобных Ж ограничений состояния приводятся в разделе 11.5. Кроме того, в классических системах планирования не предпринимается даже попытка решить проблему спецификации: проблему не представленных в определении задачи обстоятельств, которые могут вызвать неудачное завершение действия. Способы решения проблемы спецификации описаны в главе 12. Пример: воздушный грузовой транспорт В листинге 11.! показана одна из задач организации перевозок с помошью воздушного грузового транспорта, в которой предусматривается загрузка и разгрузка грузов в самолеты и из самолетов, а также перелет из одного места в другое.
Эта задача может быть определена с помошью трех действии: ьоаг(, ((п1оас( и Р1у. Действия влияют на значения двух предикатов: предикат Зп(с, р) означает, что груз с находится в самолете р, а предикат АС (х, а) ОЗНаЧаЕт, Что Объект х (либо самолет, либо груз) находится в аэропорту а. Следует отметить, что предикат Ас больше вообн(е не обусловливает местонахождение груза, если предикат тп определяет, что груз находится в самолете, поэтому Ас фактически означает "доступен для использования в указанном местонахождении". Для того чтобы научиться прорабатывать все эти детали должным образом, необходимо приобрести определенный опыт составления определений действий. Ниже приведен план, который является решением данной задачи.
(воат)(С„Р,,$РО), Р1у(Р,, $РО, .тРК), () 1оац(С,,Р,,ЯРК), Ьоаг((Сг, Рт, $РК), Р1у(Рт, тРК, $РО), цп1оаа (С,, Рт, $РО) ) Листинг 11.1. Задача Б(прэ, в которой предуематрпеаетеп транспортировка груза между аэропортами 1пхс(Ае(с;, $РО) л Ас(ст, ТРк) л Ас[Р;, $РО) л Ас(Рт,,ткк) л Сагдо(С,) л Сахдо(Сг) л Р1аае(Рт) л Р1апе(Р2) л Ахгроге( тРК) л Азгроге($РО)) Соа1(АС(С,, $РК) л АС(Се, $РО)) Ассхоп(ьоац(а, р, а), 519 Глава 11. Основы планирования Ргесопеп Ас(с, а) л Ас(р, а) л сатдо(с) л Р1апе(р) л Ахтротс(а) ЕЕЕесг: АС(с, а) л 1п(с, р) ) Ассцоп ( цп1оаг) (с, р, а), Ртесопсн гп(с, р) л Ас(р, а) л сагоо(с) л Р1апе(р) л Аттротс(а) ЕЕЕесг: АС(с, а) л 1п(с, р) ) Асг1оп (Р1у(р, Егот, Со), Ргесопсн Ас(р, етот) л Р1апе(р) л Ахгрогс(егот) л А1тротс(со) ЕЕЕесг: АС(р, Етот) л АС(р, Со)) В применяемом здесь представлении используется чистый (т.е.
не дополненный) язык 5(г(рз. В частности, это представление не исключает того, что самолет может вылететь и прилететь в один и тот же аэропорт. Возникновение такой ситуации могут предотвратить литералы неравенства, предусмотренные в языке АО1.. Пример: задача с запасным колесом Рассмотрим задачу смены колеса со стертой покрышкой. Точнее, цель состоит в том, чтобы на оси автомобиля было правильно смонтировано исправное запасное колесо, тогда как в начальном состоянии на оси имеется колесо со стертой покрышкой, а в багажнике находится исправное запасное колесо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
