УПРАЖНЕНИЯ
12.1. Тщательно изучите представление времени и ресурсов, приведенное в разделе 12.1.
а) Почему целесообразно сделать предикат Duration (d) одним из результатов действия, а не предусмотреть в действии отдельное поле в форме
Duration: d? (Подсказка. Рассмотрите условные результаты и дизъюнктивные результаты.) б) Почему Resource: т задано как отдельное поле в действии, а не оформлено как результат?
12.2. Потребляемым ресурсом называется ресурс, который (частично) расходует-
ся при выполнении действия. Например, для крепления двигателей к автомо-
билям требуются винты. Винты после их использования становятся недоступ-
ными для создания других креплений.
а) Объясните, как модифицировать представление, приведенное в листинге
12.2, чтобы в нем первоначально было 100 винтов, для двигателя Е1 тре-
бовалось 40 винтов, а для двигателя Е2 — 50. В литералах результата для
ресурсов могут использоваться функциональные символы + и -.
б) Объясните, как должно быть модифицировано определение конфликта
между причинными связями и действиями в планировании с частичным
упорядочением для учета потребляемых ресурсов.
в) Некоторые действия (например, пополнение на заводе запасов винтов или
повторная заправка топливом автомобиля) способны увеличивать доступ-
ность ресурсов. Если ни одно действие не увеличивает доступность ресурса,
он становится монотонно невозрастающим. Объясните, как можно исполь-
зовать это свойство для отсечения ветвей в пространстве поиска.
12.3. Приведите декомпозиции для этапов HireBuilder и GetPermit, показанных на рис. 12.4, и объясните, как декомпонованные субпланы соединяются в общий план.
12.4. Приведите пример двух абстрактных субпланов из проблемной области строительства дома, которые не могут быть объединены в согласованный план без совместно выполняемых этапов. (Подсказка. Участками, в которых обычно должны взаимодействовать два субплана, являются те места, в которых совместно устанавливаются две физические детали дома.)
12.5. Некоторые специалисты утверждают, что одним из преимуществ планирования HTN является то, что оно позволяет решать задачи типа "совершить прямую и обратную поездку из Лос-Анджелеса в Нью-Йорк", которые трудно выразить в системах обозначения, отличных от HTN, поскольку начальное и целевое состояния должны быть одинаковыми (At (LA)). Можете ли вы предложить способ отображения и решения таких задач без сетей HTN?
12.6. Покажите, как может быть перезаписано стандартное описание действия Strips в виде декомпозиции HTN с использованием обозначения Achieve (р) для указания на деятельность по достижении условия р.
12.7. Некоторые операции в стандартных языках программирования можно промоделировать как действия, которые меняют состояние мира. Например, в операции присваивания копируется содержимое участка памяти, а в операции печати изменяется состояние выходного потока. Программа, состоящая из этих операций, может также рассматриваться как план, цель которого задана в спецификации программы. Поэтому алгоритмы планирования могут использоваться для создания программ, которые реализуют заданную спецификацию.
а) Запишите операторную схему для оператора присваивания (в котором
значение одной переменной присваивается другой). Помните, что перво-
начальное значение должно быть при этом перезаписано!
б) Покажите, как может использоваться в планировщике процедура созда-
ния объекта для разработки плана обмена значениями между двумя пере-
менными с применением временной переменной.
12.8. Ознакомьтесь со следующими доводами: "В инфраструктуре, которая допускает наличие неопределенных начальных состояний, дизъюнктивные результаты являются просто удобным способом обозначения, а не источником дополнительной выразительной мощи. Для любой схемы действий а с дизъюнктивным результатом Р v Q можно всегда заменить его условным результатом when jR: PA when -uR: Q, который, в свою очередь, можно свести к двум обычным действиям. Высказывание Я обозначает случайное высказывание, которое не известно в начальном состоянии и для которого не предусмотрено каких-либо действий по получению информации с помощью датчиков". Являются ли эти доводы правильными? Рассмотрите отдельно два случая, в одном из которых в плане имеется только один экземпляр схемы действия а, тогда как во втором имеется больше одного экземпляра.
12.9. Почему условное планирование не позволяет справиться с неограниченной недетерминированностью?
12.10. В мире блоков мы были вынуждены ввести два действия Strips (Move иMoveToTable), чтобы иметь возможность сопровождать предикат Clear должным образом. Покажите, как можно использовать условные результаты для представления обоих этих случаев с помощью одного действия.
12.11. Условные результаты были проиллюстрированы на примере действия Suck в мире пылесоса — от того, в каком квадрате находится робот, зависит, какой из квадратов станет чистым. Можете ли вы предложить новое множество пропозициональных переменных для определения состояний мира пылесоса, таких, что действие Suck имеет безусловное описание? С использованием этих пропозициональных переменных составьте описания действий Suck, Left и Right и покажите, что их достаточно для представления всех возможных состояний мира.
12.12. Составьте полное описание действия Suck для пылесоса в мире "двойного закона Мэрфи", который иногда оставляет мусор после его перемещения в чистый квадрат назначения, а иногда оставляет мусор после выполнения действия Suck в чистом квадрате.
12.13. Найдите достаточно грязный ковер, свободный от препятствий, и очистите его пылесосом. Нарисуйте путь, проделанный чистящей головкой пылесоса, настолько точно, насколько сможете. Объясните характер этого пути, ссылаясь на формы планирования, описанные в этой главе.
12.14. Приведенные ниже цитаты взяты из инструкций на задних стенках бутылок с шампунем. Обозначьте каждую из этих инструкций как безусловный план, условный план или план с контролем выполнения: а) "Разотрите пену. Прополосните волосы. Повторите процедуру"; б) "Нанесите шампунь на волосы и оставьте на несколько минут. Прополосните волосы и повторите процедуру в случае необходимости"; в) "Если не удается устранить проблемы, обратитесь к врачу".
12.15. В алгоритме And-Or-Graph-Search, приведенном в листинге 12.4, осуществляется проверка повторяющихся состояний только в пути от корня до текущего состояния. Предположим, что, кроме того, в этом алгоритме было бы предусмотрено хранение в виде списка каждого когда-либо посещенного состояния и проверка по этому списку (см., например, алгоритм Graph-Search, приведенный в листинге 3.6). Определите, какая информация должна записываться в список и как она должна использоваться в алгоритме при обнаружении повторяющегося состояния. (Подсказка. Вам потребуется, по меньшей мере, проводить различие между состояниями, для которых перед этим был успешно сконструирован субплан, и состояниями, для которых не удалось найти субплана.) Объясните, как можно использовать метки для предотвращения необходимости иметь несколько копий субпланов.
12.16. (а Объясните точно, как следует модифицировать алгоритм And-Or-Graph-Search для выработки циклического плана, если не существует ни одного ациклического плана. Вам придется рассмотреть три проблемы: применение меток для этапов плана так, чтобы циклический план мог указывать обратно на какую-то предыдущую часть плана, модификация алгоритма Or-Search так, чтобы он продолжал поиск ациклических планов после нахождения циклического плана, а также дополнение средств представления плана, чтобы они позволяли указать, является ли план циклическим. Покажите, как действует ваш алгоритм: а) в мире пылесоса с тройным законом Мэрфи и б) в альтернативном мире пылесоса с двойным законом Мэрфи. Вам может потребоваться реализация алгоритма на компьютере для проверки полученных результатов. Может ли план для случая б) быть записан с использованием стандартного синтаксиса цикла?
12.17. Полностью определите процедуру обновления доверительного состояния для частично наблюдаемых вариантов среды. Под этим подразумевается метод вычисления нового представления доверительного состояния (как списка высказываний с оценкой знаний) из текущего представления доверительного состояния и описания действия с условными результатами.
12.18. Составьте описания действий, аналогичные уравнению 12.2, для действий Right и Suck. Запишите также описание для действия CheckLocation, аналогичное приведенному уравнению 12.3. Повторите это упражнение, используя альтернативное множество высказываний из упр. 12.11.
12.19. Рассмотрите приведенный на с. 599 список действий, которые не могут быть выполнены перепланирующим агентом. Составьте набросок алгоритма, который позволяет выполнить одно или несколько таких действий.
12.20. Рассмотрите следующую задачу: пациент поступил в приемную врача с симптомами, которые могут быть вызваны либо обезвоживанием, либо болезнью D (но не обеими этими причинами вместе). Существуют два возможных действия: Drink (Питьё), которое, безусловно, позволяет справиться с обезвоживанием, и Medicate (Медикаментозное лечение), излечивающее заболевание
12.16.
д но имеющее нежелательный побочный эффект, который возникает, если организм пациента обезвожен. Составьте описание этой проблемы на языке PDDL и разработайте план без использования датчиков, позволяющий решить эту задачу, перечислив все относящиеся к ней возможные миры.
12.21. В задаче из области медицины, приведенной в предыдущем упражнении, добавьте действие Test (Лабораторный анализ), которое имеет условный результат CultureGrowth (Развитие бактериальной культуры), если предикат Disease имеет истинное значение, и в любом случае имеет результат из области восприятия Known (Cul tureGrowth). Составьте условный план, который решает эту задачу и сводит к минимуму использование действия Medi cat е.