Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 153
Текст из файла (страница 153)
Является ли это примером проблемы распространения последствий или проблемы спецификации? Исправьте составленное вами описание задачи, чтобы в нем учитывались тяжелые объекты. 11.5. Объясните, почему процесс формирования преемников в обратном поиске не требует добавления литералов, представляющих собой отрицательные результаты в рассматриваемом действии. 560 Часть 1У. Планирование 11.6. Объясните, почему удаление отрицательных результатов из каждой схемы действия в задаче Бгпрз приводит к получению ослабленной задачи. 11.7. Изучите определениедвунаправленного поиска в главе 3.
а) Была бы идея двунаправленного поиска в пространстве состояний перспективной для использования в планирования? 6) А что можно сказать применительно к двунаправленному поиску в пространстве планов с частичным упорядочением? в) Разработайте версию планирования с частичным упорядочением, в которой любое действие может быть добавлено к плану, если выполнения его предусловий можно добиться с помощью результатов действий, уже имеюшихся в плане. Объясните, как следует поступать с конфликтами и ограничениями упорядочения.
Является ли этот алгоритм по сути идентичным прямому поиску в пространстве состояний? г) Рассмотрите планировшик с частичным упорядочением, в котором сочетается метод, описанный в упр. 11,7, в, со стандартным методом добавления действий для достижения открытых условий. Будет ли результирующий алгоритм таким же, как описано в упр. 11.7, б? 11.8.
Сконструируйте уровни О, 1 и 2 графа планирования для задачи, приведенной в листинге 11.1. 11.9. Докажите приведенные ниже утверждения о графе планирования. ° Литерал, который не появляется на заключительном уровне графа, не может быть достигнут. ° Уровневая стоимость литерала в последовательном графе не больше фактической стоимости оптимального плана его достижения.
11.10. Авторы подчеркнули различие между планировщиками с прямым и обратным поиском в пространстве состояний и планировшиками с частичным упорядочением, указав, что последние представляют собой средства поиска в пространстве планов. Объясните, на основании чего средства прямого и обратного поиска в пространстве состояний можно также рассматривать как средства поиска в пространстве планов, и укажите, каковыми являются операторы уточнения плана. 11.11. На рис.
11.8 показана задача в мире блоков, известная как?э аномалия Зюссмана. Эта задача рассматривается как аномальная, поскольку планировщики без чередования, применявшиеся в начале !970-х годов, не могли ее решить. Запишите определение этой задачи в системе обозначений Бгг1рз и решите ее либо вручную, либо с использованием программы планирования. Планировшиком без чередования является такой планировшик, который после получения двух подцелей, б, и б,, вырабатывает либо план для бы который соединяется с планом С„либо наоборот. Объясните, почему планировшик без чередования не мог решить эту задачу. бб1 Глава 11. Основы планирования () Начальное состояние целевое состояние Рис.
11,8. Задача планирования в мире блоков, получившая название анома- лии Зюссмана 11.12. Рассмотрите задачу надевания туфель и носков, которая определена в разделе 11.3. Примените для решения этой задачи алгоритм Оз ар)тр1ап и покажите полученное решение. Добавьте действия для надевания пальто и шляпы. Продемонстрируйте план с частичным упорядочением, который представляет собой одно из решений, и покажите, что существует 180 различных линеаризаций плана с частичным упорядочением. Каково минимальное количество различных решений с графом планирования, необходимых для представления всех 180 линеаризаций? 11.13.
Первоначальная программа Япрз была разработана для управления роботом Б)та(сеу. На рис. 11.9 показана версии мира 5Ьа)сеу, состоящего из четырех комнат (лоот), расположенных вдоль коридора (Ооз г1с)ог), где в каждой КОМНатЕ ИМЕЕтСя дВЕрЬ (ООО Г) И ВЫКЛЮЧатЕЛЬ СВЕта (сыт ССН). Действия в мире робота Яза)сеу включают перемещение из одного места в другое, передвижение подвижных объектов (таких как ящики), подъем и спуск с прочных обьектов (таких как ящики), а также включение и выключение выключателей света. Сам этот робот никогда не был достаточно находчивым, чтобы забраться на ящик или щелкнуть выключателем, но планировщик Япрз оказался способным находить и выводить на печать планы, превосходящие мыслительные способности робота. Ниже перечислены шесть действий робота Ята)сеу.
° Действие О э (х, у), которое требует, чтобы БЬа)сеу был в позиции х, и определяет, что позиции х и у находятся в одной и той же комнате. В соответствии с общепринятым соглашением дверь между двумя комнатами считается находящейся одновременно в обеих этих комнатах. ° Действие по перемещению ящика )з из позиции х в позицию у в пределах одной той же комнаты, ринй ()з, х, у) . Нам потребуются предикат нох и константы для описания ящиков. ° Действия по подъему на ящик, О11тЬОр (Ь), и спуску с ящика, с11тЬОоичз ( Ы .
Нам потребуются предикат Оп и константа р1 сок (Пол). ° Действия по включению выключателя света, таз зон (э), и его выключению, тилпОбб(э) . Для того, чтобы включить или выключить свет, робот Жа)сеу должен стоять на ящике, расположенном в том месте, где находится выключатель света. 562 Часть )т?. Планирование Рис. П.9. Мир робота ББа)сеу. Робот бда)сеу моясет передвигаться между отметками в пределах комнаты, проходить через двери между комнатами и коридором, взбираться на те обьекты, на которые ему разрешено взбираться, и двигать те обьекты, которые ему разрешено двигая~в, а также мозкет щелкать выключателями света Опишите в системе обозначений бгг)рз шесть действий робота Яза)сеу и показанное на рис. ) 1.9 начальное состояние.
Составьте план, с помощью которого робот Б)1а)сеу мог бы переместить ящик похе в комнату лоот,. 11.14. В этой главе встречались только такие графы планирования, которые позволяли использовать лишь пропозициональные действия. А что было бы, если возникла необходимость применять графы планирования лля задач с переменными в цели, таких как Ас(р,,х) м Ас(рг,зс), где х пРобегает по конечной области определения местонахождений? Как можно было бы представить такую задачу, чтобы для ее решечия могли использоваться графы планирования? (Подсказка. Вспомните действие Рбпбв?г из области планирования РОР. Какие предусловия оно должно иметь?) 11.15.
Вплоть до настоящего момента предполагалось, что действия выполняются только в подходящих для этого ситуациях. Рассмотрим, что должны угвер- 563 Глава 11. Основы планирования ждать пропозициональные аксиомы состояния-преемника, такие как уравнение 11.1, в отношении действий, предусловия которых не выполнены. а) Покажите, что эти аксиомы предсказывают, что ничего не произойдет, если действие будет осуществлено в таком состоянии, в котором не выполнены его предусловия.
б) Рассмотрите план р, который содержит действия, требуемые для достижения цели, но включает также недопустимые действия. Является ли истинным или ложным приведенное ниже высказывание? Начальное состояние л Аксиомы состояния-ореемника и р И цель аксиом предусловия и аксиом исключения действий. Выведите общую формулу для оценки размера каждого множества аксиом в терминах количества вре- менных этапов, количества схем действий, их арностей и количества объектов. 11.17. В алгоритме Ндтр1ап, приведенном в листинге 11.7, предусмотрено, что каждый вызов алгоритма проверки выполнимости подтверждает цель ц', где т находится в пределах от 0 до т,„. Предположим вместо этого, что алгоритм проверки выполнимости вызывается только один раз, с целью р~ Ч д1 ч ч ~цеа», Будет ли такой вызов всегда возвращать план с длиной, меньшей или равной Т, если таковой существует? Приведет ли такой подход к появлению каких-либо новых фиктивных "решений" ? Обсудите, как можно было бы модифицировать алгоритм проверки вы- полнимости, такой как ха1кндт, чтобы он находил короткие решения (если они существуют) после получения дизъюнктивной цели в указан- ной выше форме.
а) б) в) в) Возможно ли с помощью аксиом состояния-преемника первого порядка в ситуационном исчислении (как в главе 10) доказать, что план, содержащий недопустимые действия, позволяет достичь цели? 11.16. Приводя примеры из проблемной области грузового аэропорта, объясните, каким образом метод расщепления символов позволяет уменьшить размеры В эгпоб главе показано, что более выразительные представления и более интерактивные архитектуры агентов обеспечивают возмозкность создания планирови!иков, применимых в реальном мире. В предыдущей главе описывались наиболее важные понятия, представления и алгоритмы для планирования.
Планировщики, применяемые в реальном мире для решения таких задач, как планирование наблюдений с помощью космического телескопа Хаббл, управление заводами и фабриками, а также осуществление поставок для военных кампаний, являются более сложными; они превосходят свои более простые аналоги и с точки зрения языка представления, и с точки зрения того способа, который применяется в планировщике для взаимодействия с его средой. Такие различия описаны в настоящей главе. В разделе 12.1 рассматриваются задачи планирования и составления расписаний с учетом временных и ресурсных ограничений, а в разделе 12.2 описывается планирование с помощью предопределенных субпланов. В разделах 12.3 — ! 2.б рассматривается ряд архитектур агентов, предназначенных для осуществления действий в неопределенных вариантах среды.
В разделе 12.7 показано, как должны составляться планы, когда среда содержит и других агентов. 12.1. ВРЕМЯ, РАСПИСАНИЯ И РЕСУРСЫ В представлении на языке бгг1рз говорится о том, какие действия должны быть выполнены, но это представление основано на ситуационном исчислении, поэтому с его помощью нельзя показать, сколько времени потребуется на проведение того или иного действия, или даже обозначить время, когда должно произойти это дейст- "'., помимо указаний на то, что оно должно быть осуществлено до или после дру- Глава 12. Планирование и осу(цествление действий в реальном мире 565 гого действия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
