Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 152
Текст из файла (страница 152)
Многие авторы используют термин нелииейиый (поп!!псвг) вместо "частично упорядочсииыи" (рвп(а!!у огдсгсб). Такое употребление терминов немного отличается ат первоначального употребления, которое в работах Саксрдоти относилось к чередующимся планам. Глава 11. Основы планирования 557 время. За ней вскоре последовали разработки других систем с графами планирования, такие как 1РР [813], Бгап [491] и БОР [1569]. Структура данных, весьма напоминающая граф планирования, была разработана немного раньше Галлабом и Ларуэллем [549], которые использовали такую структуру данных в планировщике с частичным упорядочением 1хТеТ для получения точных эвристик, применяемых для управления поиском.
В [1136] приведен очень подробный анализ эвристик, полученных на основе графов планирования. Приведенное в этой главе описание графов планирования главным образом основано на этой работе и на конспектах лекций, подготовленных Суббарао Камбхампати (БцЬЬагао КагпЬЬатрай). Как уже указывалось в этой главе, граф планирования позволяет управлять поиском решения задачи с помощью многих способов. Например, победителем соревнования по планированию на конференции А! РБ 2002 года стал алгоритм БРС [544], в котором осуществляется поиск в графах планирования с использованием метода локального поиска, основанного на алгоритме Иа2)сЯАТ.
Подход к планированию как проверке выполнимости и алгоритм ЯАТр1ап были предложены Каутцем и Селманом [778], которых натолкнул на эту идею поразительный успех в использовании жадного локального поиска для решения задач проверки выполнимости [см. главу 7). Кроме того, Каутц и др. [777] исслеловали различные формы пропозициональных представлений для аксиом Бгг!рз и обнаружили, что наиболее компактные формы не обязательно способствуют достижению наименьшей продолжительности вычисления решения. Систематический анализ был проведен Эрнстом и др.
[442], которые разработали также автоматический "компилятор" для формирования пропозициональных представлений из формулировок задач на языке РОР].. Планировщик в).ас)сЬох, в котором объединены идеи алгоритмов СхарЬр2ап и ВАтр1ап, был разработан Каутцем и Селманом [779]. Повторное пробуждение интереса к планированию в пространстве состояний было в основном вызвано появлением программы 1)пРОР, разработанной Маклермоттом [1024], который впервые предложил эвристику с учетом расстояния, основанную на ослабленной задаче с исключенными списками удаления.
Само название 1!пРОР [отказ от РОР) стало реакцией на чрезмерное в то время сосредоточение работ на планировании с частичным упорядочением; Макдермотт считал, что другие подходы не получают того внимания, которого они заслуживают. В алгоритме НБР [Нецпы!с БеагсЬ Р!аппег — планировщик с эвристическим поиском) Бонета и Геффнера [147] и его разработанных позже аналогах впервые удалось добиться практического применения поиска в пространстве состояний при решении крупных задач планирования. В то время самым успешным алгоритмом поиска в пространстве состояний был алгоритм РазгРопчагг), или ЕР, Хоффмана [667], который стал победителем в соревновании по планированию на конференции А!РБ в 2000 году.
В алгоритме РР используется упрощенная эвристика для графа планирования в сочетании с очень быстрым алгоритмом поиска, представляющим собой новаторское объединение прямого и локального поиска. В дальнейшем появился интерес к использованию представления планов в виде Ж бинарных диаграмм решения (Ь|пагу г!ес!з!оп б!айгаш — ВОР) — компактного описания конечных автоматов, которое широко исследовалось в сообществе разработчиков средств проверки аппаратного обеспечения [266], [103!].
Существуют методы доказательства свойств бинарных диаграмм решения, включая свойство быть решением задачи планирования. В [261] представлен планировщик, основанный на этом 558 Часть |Ч. Планирование подходе. Применялись также другие представления; например, в [1549] приведен обзор использования целочисленного программирования для планирования. Точки над "(" в этом вопросе еше окончательно не расставлены, но уже появились некоторые интересные сопоставления различных подходов к планированию.
В [646] проанализировано несколько классов задач планирования и показано, что подходы на основе ограничений, такие как Ясар)гр1ап и ЯАтр1ап, являются наилучшими для ХР-трудных проблемных областей, а подходы на основе поиска лучше подходят для проблемных областей, в которых приемлемые решения могут быть найдены без поиска с возвратами. Алгоритмы Стар)гр1ап и ЯАТр1ап сталкиваются с затруднениями при использовании в проблемных областях со многими объектами, поскольку наличие большого количества объектов означает, что в этих алгоритмах приходится создавать много действий. В некоторых случаях возникновение такой проблемы можно отсрочить или вообще ее избежать, вырабатывая пропозиционализированные действия динамически, по мере необходимости, а не конкретизируя их все до начала поиска.
В [1567], [1568] приведены два превосходных обзора современных алгоритмов планирования. Любопытно наблюдать за тем, какие изменения произошли за пять лет, которые прошли за время между этими двумя обзорами: первый из них сосредотачивался на планировании с частичным упорядочением, а во втором были представлены алгоритмы ссар)гр1ап и ядтр1ап. В книге Яеаг(гпхз гп Р(апп(лх [19] приведена всеобъемлющая антология многих из самых лучших ранних статей в этой области, включая несколько хороших обзоров.
В [!629] приведен обзор методов планирования с частичным упорядочением, который занимает целую книгу. Исследования по планированию играли центральную роль в искусственном интеллекте со времени появления этого научного направления, а статьи по планированию занимают основной объем ведущих журналов и материалов конференций по искусственному интеллекту. Проволятся также специализированные конференции по планированию, такие как (пгегпа((опа( Соп~егспсе оп А! Р(апп(лх Бух(епгз (А1РБ), Гп(егла((опа( ))~ог(сз(гор оп р(апп(п8 апг( Бс(гег(и((л87ог Брасе и Еигореап Солгсгепсе оп Р(апп(пх.
УПРАЖНЕНИЯ 11.1. Опишите различие и сходство между решением задач и планированием. 11.2. При наличии аксиом, приведенных в листинге 11.1, определите все применимые конкретные экземпляры действия Р2у(р, Гсолг, со) в состоянии, описанном следующим выражением: АС(Р„тРК) л АС(Рг, ЯРО) л Р1апе(Рг) л Р1але(Рг) л Агграг.е(.ТРК) л Агсросе(ЯРО) 11.3. Рассмотрим, как можно было бы преобразовать множество схем 8(г)рз в аксиомы состояния-преемника ситуационного исчисления (см. главу 10). ° Изучите схему для действия Р1у(р, гсопг, СО) .
Запишите логическое определение для предиката Р2урсесопС((р, скот, СО, а), КОторЫй являЕтся Глава ! !. Основы планирования 559 истинным, если предусловия для действия в1у(р, Екогп, со) выполнены в ситуации в. ° Затем, предположив, что в'1у(р, Ез.огл, со) является единственной схемой действия, доступной для агента, запишите аксиому состояния-преемника лля литерала лс (р, х, в), который представляет ту же информацию в виде схемы действия. ° Теперь предположим, что есть еше один метод перемещения в пространстве — телепортация: те1ерохг (р, Ггогв, Со). Он имеет дополнительное предусловие — жахрес((р) (пространство не искривлено) и дополнительный результат !уагрес((р) (пространство искривлено).
Объясните, как должна быть модифицирована база знаний ситуационного исчисления. ° Наконец, разработайте общую и точно заданную процедуру для осушествления преобразования из множества схем 5гг(рз в множество аксиом состояния-преемника. 11.4. Лабораторная обезьяна сталкивается с задачей "обезьяна и бананы", в которой с потолка свисают бананы, не достижимые непосредственно. Имеется ящик, позволяющий обезьяне достать бананы, если она на него заберется. Первоначально обезьяна находится в позиции д, бананы — в позиции В, а ящик — в позиции б'. Обезьяна и ящик имеют высоту ьоь, но после того как обезьяна заберется на ящик, она будет иметь высоту н1 р)з, такую же, как и у бананов. Действия, доступные для обезьяны, включают Со (Переход с олного места в другое), див)з (Перемещение объекта из одного места в другое), б11глЬир (Подъем на объект) или С1згпЬпоюп (Спуск с объекта), а также Огавр (Схватывание объекта) или ипузавр (Отпускание объекта).
Схватывание приводит к овладению объектом, если обезьяна и объект находятся в олпом и том же месте и на одной и той же высоте. а) Составьте начальное описание состояния. б) Запишите определения указанных шести действий в стиле 5гпрз. в) Предположим, что обезьяна хочет поставить в тупик ученых (которые перестали за ней следить и отправились пить чай), схватив бананы, но оставив ящик на первоначальном месте. Запишите эту задачу как общую цель (т.е. не предполагая, что ящик обязательно находится в позиции с) на языке ситуационного исчисления. Может ли задача достижения этой цели быть решена с помощью системы в стиле 5гг(рз? г) Можно не сомневаться в том, что аксиома для действия по перемешению, составленная читателем, будет неправильной, поскольку, если объект слишком тяжел, то его позиция после применения оператора Ров)з должна оставаться неизменной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
