Неконкретизированные действия и цели

Все алгоритмы, применяемые в этой главе, были значительно упрощены благодаря тому, что к ним предъявлялось требование, чтобы все цели для планировщика всегда были полностью конкретизированы. Это требование соблюдалось в силу того, что ис­пользовалось соответствующее ему пространство планирования (отношения 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 в области искусственного интеллекта

Е подходе к планированию с частичным упорядочением учитывается тот факт, что действия в планах не всегда должны быть полностью упорядоченными. Если последовательность выполнения действий при любой такой возможности остается неопределенной, это позволяет упростить обработку множеств эквива­лентных перестановок действий,

В данной главе рассматриваются следующие понятия:

• предпосылки действия, списки добавления, списки удаления;

• планирование по принципу целей и средств;

• защита целей;

• регрессия целей;

• планирование с частичным упорядочением.