УПРАЖНЕНИЯ
истинным, если предусловия для действия Fly{p, from, to) выполнены в ситуации s.
• Затем, предположив, что Fly(p, from, to) является единственной схемой действия, доступной для агента, запишите аксиому состояния-преемника для литерала At {р,х, s), который представляет ту же информацию в виде схемы действия.
• Теперь предположим, что есть еще один метод перемещения в пространстве— телепортация: Teleportip, from, to). Он имеет дополнительное предусловие —\Warped(p) (пространство не искривлено) и дополнительный результат Warped(р) (пространство искривлено). Объясните, как должна быть модифицирована база знаний ситуационного исчисления.
• Наконец, разработайте общую и точно заданную процедуру для осуществления преобразования из множества схем Strips в множество аксиом состояния-преемника.
11.4. Лабораторная обезьяна сталкивается с задачей "обезьяна и бананы", в кото-
рой с потолка свисают бананы, не достижимые непосредственно. Имеется
ящик, позволяющий обезьяне достать бананы, если она на него заберется.
Первоначально обезьяна находится в позиции А, бананы — в позиции в,
а ящик — в позиции С. Обезьяна и ящик имеют высоту Low, но после того как
обезьяна заберется на ящик, она будет иметь высоту High, такую же, как и у
бананов. Действия, доступные для обезьяны, включают Go (Переход с одного
места в другое), Push (Перемещение объекта из одного места в другое),
ClimbUp (Подъем на объект) или ClimbDown (Спуск с объекта), а также
Grasp (Схватывание объекта) или Ungrasp (Отпускание объекта). Схватыва-
ние приводит к овладению объектом, если обезьяна и объект находятся в од-
ном и том же месте и на одной и той же высоте.
а) Составьте начальное описание состояния.
б) Запишите определения указанных шести действий в стиле Strips.
в) Предположим, что обезьяна хочет поставить в тупик ученых (которые пе-
рестали за ней следить и отправились пить чай), схватив бананы, но оста-
вив ящик на первоначальном месте. Запишите эту задачу как общую цель
(т.е. не предполагая, что ящик обязательно находится в позиции С) на
языке ситуационного исчисления. Может ли задача достижения этой це-
ли быть решена с помощью системы в стиле Strips?
г) Можно не сомневаться в том, что аксиома для действия по перемеще-
нию, составленная читателем, будет неправильной, поскольку, если объ-
ект слишком тяжел, то его позиция после применения оператора Push
должна оставаться неизменной. Является ли это примером проблемы
распространения последствий или проблемы спецификации? Исправьте
составленное вами описание задачи, чтобы в нем учитывались тяжелые
объекты.
11.5. Объясните, почему процесс формирования преемников в обратном поиске не
требует добавления литералов, представляющих собой отрицательные резуль-
таты в рассматриваемом действии.
11.6. Объясните, почему удаление отрицательных результатов из каждой схемы действия в задаче Strips приводит к получению ослабленной задачи.
11.7. Изучите определение двунаправленного поиска в главе 3.
а) Была бы идея двунаправленного поиска в пространстве состояний пер-
спективной для использования в планирования?
б) А что можно сказать применительно к двунаправленному поиску в про-
странстве планов с частичным упорядочением?
в) Разработайте версию планирования с частичным упорядочением, в кото-
рой любое действие может быть добавлено к плану, если выполнения его
предусловий можно добиться с помощью результатов действий, уже
имеющихся в плане. Объясните, как следует поступать с конфликтами и
ограничениями упорядочения. Является ли этот алгоритм по сути иден-
тичным прямому поиску в пространстве состояний?
г) Рассмотрите планировщик с частичным упорядочением, в котором соче-
тается метод, описанный в упр. 11.7, со стандартным методом добавле-
ния действий для достижения открытых условий. Будет ли результирую-
щий алгоритм таким же, как описано в упр. 11.7, 61
11.8. Сконструируйте уровни 0, 1 и 2 графа планирования для задачи, приведенной в листинге 11.1.
11.9. Докажите приведенные ниже утверждения о графе планирования.
• Литерал, который не появляется на заключительном уровне графа, не может быть достигнут.
• Уровневая стоимость литерала в последовательном графе не больше фактической стоимости оптимального плана его достижения.
11.10. Авторы подчеркнули различие между планировщиками с прямым и обратным поиском в пространстве состояний и планировщиками с частичным упорядочением, указав, что последние представляют собой средства поиска в пространстве планов. Объясните, на основании чего средства прямого и обратного поиска в пространстве состояний можно также рассматривать как средства поиска в пространстве планов, и укажите, каковыми являются операторы уточнения плана.
11.11. На рис. 11.8 показана задача в мире блоков, известная как аномалия Зюсс-мана. Эта задача рассматривается как аномальная, поскольку планировщики без чередования, применявшиеся в начале 1970-х годов, не могли ее решить. Запишите определение этой задачи в системе обозначений Strips и решите ее либо вручную, либо с использованием программы планирования. Планировщиком без чередования является такой планировщик, который после получения двух подцелей, G1 и G2, вырабатывает либо план для Gl9 который соединяется с планом G2, либо наоборот. Объясните, почему планировщик без чередования не мог решить эту задачу.
11.10.
11.12. Рассмотрите задачу надевания туфель и носков, которая определена в разделе 11.3. Примените для решения этой задачи алгоритм Graphplan и покажите полученное решение. Добавьте действия для надевания пальто и шляпы. Продемонстрируйте план с частичным упорядочением, который представляет собой одно из решений, и покажите, что существует 180 различных линеаризации плана с частичным упорядочением. Каково минимальное количество различных решений с графом планирования, необходимых для представления всех 180 линеаризации?
11.13. Первоначальная программа Strips была разработана для управления роботом Shakey. На рис. 11.9 показана версии мира Shakey, состоящего из четырех комнат (Room), расположенных вдоль коридора (Corridor), где в каждой комнате имеется дверь (Door) и выключатель света (Swi ten).
Действия в мире робота Shakey включают перемещение из одного места в другое, передвижение подвижных объектов (таких как ящики), подъем и спуск с прочных объектов (таких как ящики), а также включение и выключение выключателей света. Сам этот робот никогда не был достаточно находчивым, чтобы забраться на ящик или щелкнуть выключателем, но планировщик Strips оказался способным находить и выводить на печать планы, превосходящие мыслительные способности робота. Ниже перечислены шесть действий робота Shakey.
• Действие Go (х, у), которое требует, чтобы Shakey был в позиции х, и определяет, что позиции х и у находятся в одной и той же комнате. В соответствии с общепринятым соглашением дверь между двумя комнатами считается находящейся одновременно в обеих этих комнатах.
• Действие по перемещению ящика Ъ из позиции х в позицию у в пределах одной той же комнаты, Push(b, х,у). Нам потребуются предикат Box и константы для описания ящиков.
• Действия по подъему на ящик, ClimbUp(b), и спуску с ящика, ClimbDown(b). Нам потребуются предикат On и константа Floor (Пол).
• Действия по включению выключателя света, ТитОп (s), и его выключению, TumOff(s). Для того, чтобы включить или выключить свет, робот Shakey должен стоять на ящике, расположенном в том месте, где находится выключатель света.
•
Опишите в системе обозначений Strips шесть действий робота Shakey и показанное на рис. 11.9 начальное состояние. Составьте план, с помощью которого робот Shakey мог бы переместить ящик Вох2 в комнату Room2.
11.14. В этой главе встречались только такие графы планирования, которые позволяли использовать лишь пропозициональные действия. А что было бы, если возникла необходимость применять графы планирования для задач с переменными в цели, таких как At (Pltx) л At(P2;x), где х пробегает по конечной области определения местонахождений? Как можно было бы представить такую задачу, чтобы для ее решения могли использоваться графы планирования? (Подсказка. Вспомните действие Finish из области планирования POP. Какие предусловия оно должно иметь?)
11.15. Вплоть до настоящего момента предполагалось, что действия выполняются только в подходящих для этого ситуациях. Рассмотрим, что должны утвер
11.14.
ждать пропозициональные аксиомы состояния-преемника, такие как уравнение 11.1, в отношении действий, предусловия которых не выполнены.
а) Покажите, что эти аксиомы предсказывают, что ничего не произойдет,
если действие будет осуществлено в таком состоянии, в котором не вы-
полнены его предусловия.
б) Рассмотрите план р, который содержит действия, требуемые для дости-
жения цели, но включает также недопустимые действия. Является ли ис-
тинным или ложным приведенное ниже высказывание?
Начальное состояние л Аксиомы состояния-преемника л р И Цель
в) Возможно ли с помощью аксиом состояния-преемника первого порядка
в ситуационном исчислении (как в главе 10) доказать, что план, содер-
жащий недопустимые действия, позволяет достичь цели?
11.16. Приводя примеры из проблемной области грузового аэропорта, объясните, каким образом метод расщепления символов позволяет уменьшить размеры аксиом предусловия и аксиом исключения действий. Выведите общую формулу для оценки размера каждого множества аксиом в терминах количества временных этапов, количества схем действий, их арностей и количества объектов.
11.17. В алгоритме SATplan, приведенном в листинге 11.7, предусмотрено, что каждый вызов алгоритма проверки выполнимости подтверждает цель дт, где Т находится в пределах от 0 до Ттах. Предположим вместо этого, что алгоритм проверки выполнимости вызывается только один раз, с целью д° v д1 v ... v gTmax.
а) Будет ли такой вызов всегда возвращать план с длиной, меньшей или
равной Тщах, если таковой существует?
б) Приведет ли такой подход к появлению каких-либо новых фиктивных
"решений"?
в) Обсудите, как можно было бы модифицировать алгоритм проверки вы-
полнимости, такой как WalkSAT, чтобы он находил короткие решения
(если они существуют) после получения дизъюнктивной цели в указан-
ной выше форме.