Неконкретизированные действия и цели
Все алгоритмы, применяемые в этой главе, были значительно упрощены благодаря тому, что к ним предъявлялось требование, чтобы все цели для планировщика всегда были полностью конкретизированы. Это требование соблюдалось в силу того, что использовалось соответствующее ему пространство планирования (отношения adds, deletes и can). Например, в листинге 17.1 полная конкретизация переменных обеспечивается с помощью отношения сап, которое определено следующим образом:
can( move< Block, From, Та), [ clear{ Block), clear{ To), on ( Block, From)]) :-block{ Block},
□bj ectС То),
Конкретизацию переменных обеспечивают такие цели, как block ( Block), показанная выше. Но конкретизация может привести к выработке многочисленных не относящихся к делу альтернативных действий, которые также должны учитываться планировщиком. Например, рассмотрим ситуацию, показанную на рис. 17.1, в которой к планировщику поступает запрос на достижение цели clear ( а) . В отношении achieves предлагается следующее общее действие для достижения цели clear ; а): move) Something, a, Somewhere)
В таком случае для поиска предпосылок достижения этой цели применяется следующее отношение: can( move( Something, a, Somewhere), Condition)
В результате того, что используется перебор с возвратами, планировщик вынужден рассматривать всевозможные варианты конкретизации переменных Something и Somewhere. Поэтому проверяются все следующие действия, прежде чем будет найдено одно из них, позволяющее достичь цели: move( b, а, 1) move( b, a, 2) move! b, £, 3) move( b, a, 4) move! b, a, c) move [ c, a, 1) move ( c, a, 2)
Более выразительное представление, позволяющее исключить эти неэффективные операции, может предусматривать применение в целях неконкретизированных переменных. Например, для мира блоков одна из попыток определить такое альтернативное отношение сап может состоять в следующем: сап(rr,ove( Block, From, To), [ clear ( Block;, clear I To}, or. ( Block, From)]).
Теперь снова рассмотрим ситуацию, показанную на рис. 17.1, и цель clear( а). И s этом случае отношение achieves предусматривает использование такого действия: nove( something, a, Somewhere)
Но на этот раз при обработке отношения сап переменные остаются неконкретизи-рованными и список предпосылок достижения цели принимает следующий вид: [ clear< something), clear! Somewhere), on( Something, a)]
Обратите внимание на то, что этот список целей, которых теперь должен попытаться достичь планировщик, содержит переменные. Данный список целей в начальном состоянии достигается немедленно, если применяется следующая конкретизация:
Something = с Somewhere = 2
Часть II. Применение языка Prolog в области искусственного интеллекта
Ключом к достигнутому повышению эффективности, при котором правильное действие обнаруживается практически без какого-либо поиска, является то, что множества вариантов действий и целей заменяются неконкретизированными действиями и целями. Их конкретизация откладывается до более позднего времени, когда становится очевидно, какими значениями должны быть конкретизированы эти переменные. С другой стороны, спецификация, приведенная в листинге 17.1, вынуждает программу немедленно выполнять конкретизацию действий, а значит, и целей в предпосылках действий.
Приведенный выше пример показывает, что использование представления с помощью переменных открывает широкие возможности. Но реализация данного метода связана с определенными сложностями. Прежде всего, показанная выше попытка иначе определить отношение саг, является недопустимой, поскольку она позволяет использовать в ситуации, показанной на рис. 17.1, следующее действие: move ( с, а, с)
В результате возникает невероятное положение, в котором блок с должен стоять сам на себе! Поэтому более качественное определение отношения сап не должно допускать, чтобы была предпринята попытка поставить блок сам на себя, а также должно учитывать все прочие аналогичные ограничения. Такое определение приведено ниже.
can( move ( Block, From, To),
[ Clear! Block), clear ( TO}, on{ Block, From), different ( BlOCk, To), different! From, To), different; Block, From)]).
Здесь different) X, Y) означает, что переменные X и Y не могут обозначать один и тот же объект. Условие наподобие different; X, Y) не зависит от состояния мира. Поэтому его значение не может стать истинным в результате какого-либо действия, но его соблюдение должно контролироваться путем проверки соответствующего предиката. Один из способов учета подобных фиктивных целей состоит во введении следующего дополнительного предложения в процедуру satisfied, применяемую в рассматриваемых планировщиках:
satisfied! State, [Goal [ Goals]) ;-holds ( Goal), % Цель Goal независима or состояния State satisfied! Goals)
В соответствии с этим, такие предикаты, как different [ X, Y), должны быть определены процедурой holds следующим образом: holds! different (X, Y) )
Подобное определение может быть сформулировано в соответствии с приведенными ниже рекомендациями.
• Если X и Y не согласуются, то предикат different ( X, Y) принимает истинное значение.
• Если X и Y буквально совпадают друг с другом (X == Y), то это условие становится ложным и всегда будет оставаться ложным независимо от дальнейших действий в плане, В таком случае подобные условия могут учитываться таким же образом, как и цели, объявленные в отношении impossible.
• В противном случае (X и Y согласуются, но не являются полностью одинаковыми) оказывается, что пока невозможно оценить текущую ситуацию. Решение о том, следует ли использовать эти переменные для обозначения одинакового объекта или этого делать нельзя, должно быть отложено до тех пор, пока переменные X и Y не станут более конкретизированными.
Как показывает этот пример, проверку условий, подобных different; X, Y), которые являются независимыми от состояния, иногда приходится откладывать. Поэтому было бы целесообразно представлять такие условия в качестве дополнительного параметра процедуры plan и учитывать их отдельно от тех целей, которые достигаются с помощью действий.
Глава 17. Планирование
Это — не единственная сложность, обусловленная введением переменных. Например, рассмотрим следующее действие: move (а, 1, X)
Приводит ли это действие к удалению отношения clear ( b) ? Да, если X = Ь, и нет, если different( X, b). Это означает, что существуют две возможности и со значением х связаны два соответствующих варианта: в одном варианте X равен Ь, а в другом вводится дополнительное условие different( X, Y).
Планирование с частичным упорядочением
Один из недостатков рассматриваемых планировщиков состоит в том, что в них рассматриваются все возможные варианты упорядочения действий, даже в тех случаях, если эти действия являются полностью независимыми. В качестве примера рассмотрим задачу планирования, показанную на рис. 17.4, в которой целью является составление двух столбиков блоков из двух отдельных наборов блоков, которые уже и так достаточно разделены. Эти два столбика можно составить независимо друг от друга с помощью следующих двух планов, соответствующих каждому отдельному столбику:
Planl = | [ move ( | b, | а, | с) , | move | a, | 1, | b) |
Р1ап2 = | [ move( | е, | d, | t), | move ( | d, | 8, | a)] |
.'; в
ас f d
__ i____ i____ I_____ i____ i____ i____ i__
L
1234S678 1 Я 3 4 5 S 7 8
Рис. 17.4, Задача планирования, состоящая ш двух независимых подзадач
Важной отличительной особенностью этой ситуации является то, что эти два плана не связаны друг с другом. Поэтому имеет значение лишь порядок действий в каждом отдельном плане, но не важно, в какой последовательности выполняются сами планы: вначале Planl, а затем Flan2, или вначале Р1ап2, а затем Planl, или даже происходит ли переключение между ними и выполняется часть одного плана, а затем часть другого. Например, ниже показана одна из допустимых последовательностей выполнения. 1 move! Ьг аг с), move! е, d, f}, move; d, 8, e), move ( a, 1, b) ]
Несмотря на это, рассматриваемые в этой главе планировщики в процессе планирования скорее всего будут учитывать все 24 перестановки четырех действий, хотя имеются, по сути, лишь четыре варианта: по две перестановки для каждого из двух независимых планов, составляющих общий план. Возникающая при этом проблема является следствием того факта, что рассматриваемые планировщики строго ориентированы на полное упорядочение всех действий в плане. Поэтому возможное усовершенствование состоит в том, что если в какой-то ситуации порядок действий не имеет значения, то отношение предшествования между действиями может оставаться неопределенным. Таким образом, разрабатываемые планы могут представлять собой частично упорядоченные множества действий, а не полностью упорядоченные последовательности. Планировщики, которые допускают частичное упорядочение, называют планировщиками с частичным упорядочением (иногда также нелинейными планировщиками).
Рассмотрим основной принцип планирования с частичным упорядочением, снова обратившись к примеру, приведенному на рис. 17.1. Ниже приведено краткое описание того, как нелинейный планировщик может решить эту задачу. Анализируя цели
Часть II.Применение языка Prolog в области искусственного интеллекта
on ( a, b) и on ( b, с), планировщик приходит к выводу, что в план должны быть обязательно включены следующие два действия:
Ml = move ( a, X, b} М2 = move ( b, Y, с)
Иного способа достичь этих двух целей не существует. Но порядок, в котором должны быть выполнены два указанных действия, еще не задан. Теперь рассмотрим предпосылки этих двух действий. Предпосылка для действия move ( а, X, Ь} содержит условие clear ( а] . Это условие не соблюдается в начальном состоянии, поэтому требуется еще какое-то действие в следующей форме:
КЗ = move ! II, а, V)
Оно должно предшествовать действию Ml, поэтому теперь необходимо учитывать следующее ограничение при выборе последовательности действий: before ( ИЗ, к!)
После этого рассмотрим, не могут ли действия м2 и МЭ заменяться одним и тем же действием, с помощью которого достигаются цели обоих действий. Это условие не соблюдается, поэтому план должен включать три разных действия. Затем планировщик должен ответить на вопрос о том, есть ли такая перестановка трех действий [ Ml, M2, МЗ], что МЗ предшествует Ml, перестановка выполнима в начальном состоянии и общие цели достигаются в результирующем состоянии. С учетом приведенного выше ограничения предшествования должны рассматриваться только следующие три из общего количества перестановок, равного шести:
[ КЗ, Ml, К2]
[ МЗ, м2, Hi]
( К2, МЗ, Ml]
Ограничениям, применяемым в данном сеансе выполнения программы, соответствует вторая из этих перестановок, если используется такая конкретизация: О = с, V - 2, X = 1, Y = 3. Как показывает этот пример, благодаря использованию планирования с частичным упорядочением нельзя полностью устранить комбинаторную сложность, а можно лишь ее уменьшить.
Проекты
С использованием методов, описанных в этой главе, разработайте программу плакирования для применения в более интересном варианте простого мира блоков, который рассматривался в этой главе. На рис. 17.5 показан пример задачи, которая должна быть решена в этом новом мире блоков. Он состоит из блоков разных размеров, и в нем должна учитываться устойчивость конструкций. Чтобы упростить данную задачу, примите предположение, что блоки могут занимать только целое количество позиций и всегда должны стоять на надежной опоре, таким образом, чтобы построенные из них конструкции были полностью устойчивыми. Кроме того, примите предположение, что блоки никогда не бывают повернуты роботом и траектории их перемещения остаются простыми: блок поднимается прямо вверх до тех пор, пока не будет находиться выше всех других блоков, после этого перемещается по горизонтали, а затем опускается прямо вниз. Разработайте специализированные эвристические функции, предназначенные для использования этим планировщиком.
В мире роботов более реальная и интересная задача по сравнению с той, что представлена в листинге 17.1, может также предусматривать действия по восприятию общей картины, осуществляемые с помощью телевизионной камеры или контактного датчика. Например, действие look; Position, Object) позволяет распознать объект, обнаруженный телевизионной камерой в позиции Position (т.е. конкретизировать переменную object). В подобном мире становится реальным предположение, что сцена действия не полностью известна для робота, поэтому он может включить в свой план такие действия, единственной целью которых является получение информации. Такую задачу можно дополнительно усложнить с учетом того факта, что некоторые наблюдения подобного рода не могут быть выполнены немедленно (напри-
Глава 17. Планирование
мер, объекты, закрытые другими объектами, нельзя рассмотреть с помощью телевизионной камеры, которая доказывает вид сверху). Введите другие соответствующие отношения с определением целей и в случае необходимости внесите исправления в рассматриваемые программы планировщиков.
Откорректируйте планировщик с регрессией целей, приведенный в листинге 17.5, таким образом, чтобы он правильно обрабатывал переменные в целях и действиях, в соответствии с описанием, содержащимся в разделе 17.7.1.
Напишите программу нелинейного планировщика в соответствии с общими рекомендациями, изложенными в разделе 17.7.2.
If
с в >■
0 1 2 3 4 5 6
Рис, 17.5. Задача планирования для другого мира блоков: достичь целей оп{ а, с),сп ( Ь, с), on ( с, d)
Резюме
В планировании возможные действия должны быть представлены с помощью таких средств, которые позволяют явно формировать рассуждения об их результатах и предпосылках. Указанное требование можно выполнить, задавая для каждого действия его предпосылки, а также соответствующие ему списки связей: список добавления (связи, устанавливаемые этим действием) и список удаления (связи, уничтожаемые этим действием).
Процедура составления планов по принципу целей и средств основана на поиске действий, с помощью которых достигаются заданные цели и создаются предпосылки для таких действий.
Защитой целей называется механизм, который предотвращает разрушение планировщиком уже достигнутых целей.
Планирование по принципу целей и средств предусматривает поиск в пространстве возможных действий. Поэтому для решения задач планирования могут также применяться обычные методы поиска: поиск в глубину, поиск в ширину и поиск по заданному критерию.
Для уменьшения сложности, поиска на некоторых этапах планирования по принципу целей и средств могут использоваться знания о данной конкретной проблемной области, которые, в частности, позволяют определить, какой цели в заданном списке целей следует пытаться достичь на очередном этапе и какое действие среди всех вариантов действий необходимо выполнить в первую очередь, а также применить эвристическую оценку сложности достижения целей в списке целей при поиске по заданному критерию.
Регрессия целей — это процесс, позволяющий определить, какие цели должны быть истинными перед выполнением некоторого действия для того, чтобы можно было гарантировать истинность определенных целей после этого действия. В процессе планирования с применением регрессии целей обычно предусматривается обратный логический вывод действий.
Применение неконкретизированныхпеременных в целях и действиях позволяет повысить эффективность планирования, но, с другой стороны, приводит к значительному усложнению планировщика.
Часть II. Применение языка Prolog в области искусственного интеллекта
Е подходе к планированию с частичным упорядочением учитывается тот факт, что действия в планах не всегда должны быть полностью упорядоченными. Если последовательность выполнения действий при любой такой возможности остается неопределенной, это позволяет упростить обработку множеств эквивалентных перестановок действий,
В данной главе рассматриваются следующие понятия:
• предпосылки действия, списки добавления, списки удаления;
• планирование по принципу целей и средств;
• защита целей;
• регрессия целей;
• планирование с частичным упорядочением.