Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 146
Текст из файла (страница 146)
Грубо говоря, литералы представляют собой то, что может быть истинным на каждом временном этапе в зависимости от действий, выполненных на предьщуших временных этапах. Также грубо говоря, действиями являются все те действия, которые 537 Глава 11. Основы планирования могут иметь все свои предусловия выполненными на данном временном этапе в зависимости от того, какие из литералов фактически являются истинными. В этих двух определениях применяется выражение "грубо говоря", поскольку в графе планирования регистрируется только ограниченное подмножество возможных отрицательных взаимодействий между действиями; поэтому граф может давать оптимистическую оценку минимального количества временных этапов, требуемых для того, чтобы некоторый литерал стал истинным.
Тем не менее такое количество этапов в графе планирования предоставляет хорошую оценку того, насколько трудно достичь указанного литерала из начального состояния. Еше важнее то, что граф планирования определен таким образом, что может быть сформирован очень эффективно. Графы планирования могут применяться только для решения задач планирования в пропозициональной логике, т.е, тех задач, в которых отсутствуют переменные. Как упоминалось в разделе 1!.1, в пропозициональную форму могут быть преобразованы и представления 5(г!рз, и представления АОЕ. Если в задаче имеется большое количество объектов, это может привести к весьма существенному возрастанию количества возможных схем действий.
Несмотря на это, было показано, что графы планирования представляют собой эффективное инструментальное средство решения трудных задач планирования. Проиллюстрируем применение графов планирования на простом примере. (Использование более сложных примеров привело бы к созданию графов, которые не поместились бы на одной странице книги.) В листинге 1 !.5 приведена задача, а на рис. 11.б показан ее граф планирования. Начнем с уровня состояния Б,, который представляет начальное состояние задачи. Затем перейдем на уровень действия л, и поместим на него все действия, предусловия которых были выполнены на предыдущем уровне. Каждое действие соединено с его прелусловиями в состоянии Б, и его результатами в состоянии Еп а это в данном случае влечет за собой введение в Е, новых литералов, которых не было в Ее Листинг 11.5.
Задача "получить кекс, и также съесть кекс" тпхс(Наие(Са)се)) Еоа1(лаее(Са)ге) л Еасеп(Сале)) Ассхоп(Еас(Са)се) Рпесопд: Наее(Са)ге) Еукесс: Наее(Саке) л Еасеп(саке)) Лссхоп(ла)се(СаКе) Рпесопо: -пнаее(Са)ге) Егйесс: Наее(са)ге) Должны быть предусмотрены способы представлять на графе планирования не только действие, но и бездействие. Это означает, что необходимо иметь своего рола эквивалент аксиом окружения ситуационного исчисления, которые позволяют литералу оставаться истинным от одной ситуации к другой, если его не изменяет ни одно действие. В графе планирования это осуществляется с помощью множества ж сохраняющих действий (регз!з(епсе ас(юп). Для кажлого положительного или отрицательного литерала С в задачу вводится сохраняющее действие с предусловием С и результатом С.
На рис. 11.6 в состоянии л, показано одно "реальное" действие, Глава 11. Основы планирования 539 графе просто регистрируется невозможность осушествления некоторых выборов с использованием взаимно исключаюших связей. Сложность формирования графа планирования оценивается полиномиальной зависимостью низкого порядка от количества действий и литералов, тогда как размеры пространства состояний определяются экспоненциальной зависимостью от количества литералов.
Теперь определим взаимно исключаюшие связи как для действий, так и для литералов. Между двумя действиями на данном конкретном уровне имеет место взаимно исключаюшее отношение, если соблюдается любое из трех перечисленных ниже условий. ° Несогласованные результаты. Одно действие отрицает результат лр>того. Например, действие еас(са)ге) и сохраняюшее действие наое(са)ге) имеют несогласованные результаты, поскольку они не согласуются в результате Наче(Са)ге) (съедение кекса приводит к его исчезновению). ° Вмешательство.
Один из результатов одного действия является отрицанием предусловия другого действия. Например, действие Вас (са)ге) мешает осушествлению сохраняющего действия Наое(Са)ге), поскольку отрицасз с~о предусловие (если кекса больше нет, то нечего и хранить). ° Конкурируюшие потребности. Одно из предусловий одного действия является взаимно исключающим по отношению к предусловию другого.
Например. литералы Ва)ге( са)ге) (Испечь кекс) и Вас (са)ге) (Съесть кекс) являюзся взаимно исключающими, поскольку конкурируют за значение прелусловия Нане ( Са)ге) (в одном литерале кекс создается, а в другом — уничтожается). Взаимно исключаюшее отношение имеет место между двумя литералами на олпом и том же уровне, если один из них является отрицанием другого или если каждая возможная пара действий, которые позволяют достичь двух литералов, является взаимно исключающей.
Такое условие называется несоглисованной ноддгрзюкои Например, на уровне Я, литералы нане ( Са)ге) и еа с ел ( Са)ге) являются взаимно исключаюшими, поскольку единственный способ достичь литерала наме(сане) (применения сохраняюшего действия) является взаимно исключаюшим с единственным способом достижения литерала еасеп(са)ге), а именно Вас(саке). На уровне Е, эти два литерала не являются взаимно исключающими, поскольк> сушествуют новые способы их достижения, такие как действие ВаЛе ( Са)ге1 и сохраняюшее действие Еаееп(Са)ге), которые не являются взаимно исключающими. Применение графов планирования для получения эвристической оценки Граф планирования после его построения становится богатым источником информации о задаче.
Например, очевидно, что гр литерал, который не нояатлгтсн па заключительном уровне графа, не может быть достигну(п с помощью любого олино. Такое наблюдение может использоваться в обратном поиске следуюшим образом: любое состояние, содержашее недостижимый литерал, имеет стоимость )з (и) = . гЛналогичным образом, при планировании с частичным упорядочением любой план с недостижимым открытым условием имеет Н (п) = Эту идею можно сделать более обобшенной. Стоимость достижения любого целевого литерала может оцениваться как номер уровня, на котором он впервые появ- 540 Часть 1Н. Планирование ляется в графе планирования.
Назовем эту оценку еь уровневой стоимостью (!ече! сои) цели. На рис. 11.6 литерал даче(са)ге) имеет уровневую стоимость О, а дасеп (са)се) — уровневую стоимость 1. Можно легко показать (упр. 11.9), что эти оценки являются допустимыми дяя отдельных целей. Однако сами эти оценки могут оказаться не очень качественными, поскольку графы планирования допускают наличие несколько действий на каждом уровне, тогда как в этой эвристике учитывается только номер уровня, а не количество действий.
По этой причине для вычисления эвристики принято использовать Ж последовательный граф планирования (зепа! р)апшпя агарЬ). Последовательный граф требует, чтобы на каждом конкретном временном этапе фактически могло происходить только одно лействие; такое требование осуществляется путем введения взаимно исключающих связей между каждой парой действий, кроме сохраняющих действий. Уровневые стоимости, извлеченные из последовательных графов, часто представляют собой вполне приемлемые оценки фактических стоимостей.
Чтобы оценивать стоимость достижения конъюнкции целей, можно воспользоваться одним из трех простых подходов. В эвристике 'в. максимального уровня (шах-1ече1) просто берется максимальная уровневая стоимость любой из целей; такая эвристика является допустимой, но не обязательно очень точной. Эвристика Ъ. уровневой суммы (1ече! зип), в основе которой лежит предположение о независимости полцелей, возвращает сумму уровневых стоимостей целей; эта эвристика является недопустимой, но очень хорошо действует на практике при решении задач, которые являются в значительной степени декомпонуемыми. Она характеризуется гораздо более высокой точностью по сравнению с эвристикой, в которой учитывается количество невыполненных целей, описанной в разлеле 11.2. В рассматриваемой задаче эвристическая оценка для конъюнктивной цели Нече(Са)ге) а Еаееп(СаКе) будет равна Оь1=1, тогда как правильный ответ равен 2.
Кроме того, если будет удалено действие ва)ге(Са)се), эта оценка по-прежнему будет равна 1, но достижение этой конъюнктивной цели станет невозможной. Наконец, эвристика 'а. множественного уровня (зе(-1ече1) находит уровень, на котором все литералы в конъюнктивной цели появляются в графе планирования без любой пары из них, которая была бы взаимно исключающей. Эта эвристика дает правильное значение, равное 2, для первоначальной задачи и равное бесконечности для задачи без действия на)ге ( са)ге) .
Она доминирует над эвристикой максимального уровня и действует чрезвычайно успешно в задачах, характеризующихся весьма существенным взаигиодействием субпланов. Для использования его в качестве инструментального средства формирования точных эвристик граф планирования можно рассматривать как ослабленную задачу, которая может быть эффективно решена. Чтобы понять характер этой ослабленной залачи, нужно точно определить, что означает появление литерала П на уровне Яг в графе планирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
