Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 147
Текст из файла (страница 147)
В идеале желательно было бы иметь гарантию, что существует план с 1 уровнями действий, который достигает литерала е, а также, что литерал е не появится, если такого плана нет. К сожалению, предоставить такую гарантию столь же трудно, как и решить первоначальную задачу планирования. Поэтому граф планирования предоставляет вторую половину гарантии (если литерал о не появляется, то нет и плана его достижения), но если литерал е появляется, то весь этот граф планирования становится залогом того, что существует план, который, возможно, позволяет достичь литерала о и не имеет "очевидных" недостатков.
Очевид- Глава 11. Основы планирования 541 яый недостаток плана определяется как недостаток, который может быть выявлен путем рассмотрения двух действий или двух литералов одновременно; другими словами, путем проверки взаимно исключающих отношений. Могут существовать более трудно диагностируемые недостатки, охватывающие три, четыре или больше действий, но опыт показывает, что вычислительные затраты, связанные с отслеживанием этих возможных недостатков, не оправдываются.
Этот вывод аналогичен уроку, усвоенному по результатам исследования задач удовлетворения ограничений, в которых часто целесообразно вычислить 2-совместимость (совместимость на уровне 2) перед поиском решения, но вычисление 3-совместимости или совместимости более высокой степени часто бывает менее целесообразным (см. раздел 5.2). Алгоритм СкарЬр2азз В данном подразделе показано, как извлечь план непосредственно из графа планирования, а не просто использовать этот граф для получения эвристики. Алгоритм Сгарпр1ап (листинг 11.6) имеет два основных этапа, каждый из которых чередуется в цикле. Прежде всего в этом алгоритме проверяется, присутствуют ли все целевые литералы на текущем уровне без взаимно исключающих связей между любой парой из них. Если это требование соблюдается, то в текущем графе может существовать решение, поэтому в алгоритме выполняется попытка изнлечь это решение.
В противном случае граф расширяется путем добавления действий для текущего уровня и литералов состояния для следующего уровня. Процесс продолжается до тех пор, пока либо не обнаруживается решение, либо не выясняется, что решения не существует. Листинг 11.6. Алгоритм егарпр1ап.
В алгоритме агарир1ап чередуются этап нзвлечення решения н этап расширения графа. Функция цхсгаос -во1пебоп опрелеляет, может лн быть найден план, начиная с конца н выполняя поиск в обратном направлении. Функция нхрапа-егарп добавляет действия для текушего уровня н литералы состояния для следуюшего уровня гппоебоп Огарпр1ап!ргоЫею! геспгпя реыение во1иедоп ияи индикатор неудачи Га11цге дгарп е- 1пбеба1-Р1аппбпд-СгарЫргоо|ет! доа1в е- Соа1з(ргоЫее! 1оор оо бв все цеди доа1л не являются взаимно искдючаюввгми на последнем уровне графа угара Спеп сто во1иедоп г — Рхегасе-Бо1иебоп!дгарщ доа1в, Ьепдеп!дгарщ ! бг во1иебоо Е Га11цге Сйеп геепгп во1игбоп е1ве бг Ио-Яо1цг1оп-Роввбо1е!угара) спев геепгп Га11цге дгарл е- вкрапс-Эгарь !дгарщ ргоЫею! Теперь проследим за функционированием алгоритма Сгарйр1ап на примере задачи замены колеса, рассматриваемой в разделе 1!.!.
Полный граф показан на рис. 11.7. В первой строке алгоритма Стар)зр1ап граф планирования инициализируется значением одноуровневого графа (Яе), состоящего из пяти литералов, взятых из начального состояния. Целевой литерал АС ! Ураге, Лх1е) в состоянии 8, отсутствует, поэтому не требуется вызывать функцию Вхсгасс-Войцгбоп — мы можем быть уверены, что решение еше не существует. Вместо этого вызывается функция Глава 11.
Основы планирования 543 щие отношения позволяют обнаруживать непосредственные конфликты, которые становятся следствием попыток поместить два объекта в одно и то же место одновременно. После того как мы снова перейдем в начало цикла, на этот раз на уровне Б-, будут присутствовать все литералы из цели и ни один из них не булет взаимно исключающим по отношению к любому другому. Это означает, что может существовать решение и в функции цхсгасс-Бо1исгоп будет предпринята попытка его найти. По сути, функция цхсгасс-Бо1исзоп решает булеву задачу СЗР, переменными которой являются действия на каждом уровне, а значениями для каждой переменной служат индикаторы, показывающие, принадлежит ли она нли не принадлежит к плану. Для этого можно воспользоваться стандартными алгоритмами СЗР или онрелслить функцию цхсгасг-яо1ис1оп как задачу поиска, в которой каждое состояние в поиске содержит указатель на уровень в графе планирования и множество невыполненных целей.
Определим эту задачу поиска, как описано ниже. ° Первоначальным состоянием является последний уровень графа планирования, Б„наряду с множеством целей из задачи планирования. ° Действия, доступные в любом состоянии на уровне Б„должны выбирап любое бесконфликтное подмножество действий на уровне А, „резул ьтаты коз орых покрывают цели в этом состоянии. Результирующее состояние имеет уровень Б,, и включает в качестве своего множества целей все предусловия для выбранного множества действий. Под термином "бесконфликтныи" полразумевается множество таких действий, что никакие два из них не являются взаимно исключающими и никакие два из их предусловий не являются взаимно исключающими.
° Задача состоит в том, чтобы достичь на уровне Б, такого состояния, чтобы все цели были выполнены. ° Стоимость каждого действия равна 1. При решении данной конкретной задачи начнем с уровня Б., где имеется исль Ас ( Бра~с, Ах1е) . Единственным вариантом, который может применяться лля достижения этого множества целей, является РиСОп(Браге, Ах1е) .
В результате мы переходим в состояние поиска на уровне Б, с целями Ас(Браге, Огоипе) и - АС (чае, Ах1е) . Первой цели можно достичь только с помощью деиствпя )гетоие(Браге, тгип)г), а последней — с помощью либо летсие(Б1ас, Ах1е), либо ьеаиеоиегпхд)гс. Но действие ьеаиеОиегпудйс является взаимно исюпочаюшим по отношению к Летсие(Браге, тгип)г), поэтому единственное решение состоит в том, чтобы выбрать летсие( Бра~с, тгип)г) и летсие ( Б1 а с, Ах1е) .
В результате мы переходим в состояние поиска на уровне Б, с целями Ас ( Браге, тгип1с) и Ас (Р1ас, Ах1е) . Обе из этих целей присутствуют в данном состоянии, поэтому налицо готовое решение: действия летогге(Браге, тгипх) и г(етоие ( Б1 а с, Ах1е) на урОВНЕ А„за которыми следует действие РиСОп ( Браге, Ах1е) на уровне А,. Известно, что задача планирования является РЗРАСЕ-полной и что для построения графа планирования требуется полиномиальное время, поэтому в наихудьэсм случае может возникнуть ситуация, в которой извлечение решения окажется неосуществимым.
Таким образом, потребуется определенное эвристическое руководство 544 Часть ЪЧ. Планирование при выборе среди действий в ходе обратного поиска. Одним из подходов, хорошо зарекомендовавших себя на практике, является жадный алгоритм, основанный на учете уровневой стоимости литералов. Для каждого набора целей применение этой эвристики осуществляется в описанном ниже порядке. 1. Определить литерал с максимальной уровневой стоимостью. 2. Чтобы достичь этого литерала, выбрать в первую очередь действие с самыми легкими для выполнения предусловиями.
Это означает, что действие нужно выбирать так, чтобы сумма (или максимум) уровневых стоимостей его предусловий была минимальной. Завершение работы алгоритма ОкарЬр1ахх До сих пор мы обходили проблему завершения работы алгоритма. Если задача не имеет решения, можно ли быть уверенным в том, что алгоритм 6харпр1ап не будет проходить по пиклу до бесконечности, расширяя граф планирования при каждой итерации? Ответ на этот вопрос является положительным, но полное доказательство такого утверждения выходит за рамки настоящей книги. Здесь мы кратко опишем основные идеи, особенно те, которые проливают свет на графы планирования в целом. На первом этапе необходимо отметить, что характеристики некоторых свойств графов планирования монотонно увеличиваются или уменьшаются. Выражение "характеристика х увеличивается монотонно" означает, что множество экземпляров Х на уровне 1+1 является надмножеством (необязательно строгим) множества на уровне 1.
Соответствующие свойства графов перечислены ниже. ° Количество литералов увеличивается монотонно. После того как некоторый литерал появляется на данном конкретном уровне, он будет появляться на всех последующих уровнях. Это связано с наличием сохраняющих действий; после того как литерал появляется, сохраняющие действия вызывают его сохранение навечно. ° Количество действий увеличивается монотонно. После того как некоторое действие появляется на данном конкретном уровне, оно будет появляться на всех последующих уровнях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
