Применение графов планирования для получения эвристической оценки
Граф планирования после его построения становится богатым источником информации о задаче. Например, очевидно, что литерал, который не появляется па заключительном уровне графа, не может быть достигнут с помощью любого плана. Такое наблюдение может использоваться в обратном поиске следующим образом: любое состояние, содержащее недостижимый литерал, имеет стоимость п(п) =°°. Аналогичным образом, при планировании с частичным упорядочением любой план с недостижимым открытым условием имеет п(п) =<*>.
Эту идею можно сделать более обобщенной. Стоимость достижения любого целевого литерала может оцениваться как номер уровня, на котором он впервые появляется в графе планирования. Назовем эту оценку уровневой стоимостью (level cost) цели. На рис. 11.6 литерал Have (Саке) имеет уровневую стоимость О, a Eaten(Cake) — уровневую стоимость 1. Можно легко показать (упр. 11.9), что эти оценки являются допустимыми для отдельных целей. Однако сами эти оценки могут оказаться не очень качественными, поскольку графы планирования допускают наличие несколько действий на каждом уровне, тогда как в этой эвристике учитывается только номер уровня, а не количество действий. По этой причине для вычисления эвристики принято использовать последовательный граф планирования (serial planning graph). Последовательный граф требует, чтобы на каждом конкретном временном этапе фактически могло происходить только одно действие; такое требование осуществляется путем введения взаимно исключающих связей между каждой парой действий, кроме сохраняющих действий. Уровневые стоимости, извлеченные из последовательных графов, часто представляют собой вполне приемлемые оценки фактических стоимостей.
Чтобы оценивать стоимость достижения конъюнкции целей, можно воспользоваться одним из трех простых подходов. В эвристике максимального уровня (max-level) просто берется максимальная уровневая стоимость любой из целей; такая эвристика является допустимой, но не обязательно очень точной. Эвристика уровневой суммы (level sum), в основе которой лежит предположение о независимости подцелей, возвращает сумму уровневых стоимостей целей; эта эвристика является недопустимой, но очень хорошо действует на практике при решении задач, которые являются в значительной степени декомпонуемыми. Она характеризуется гораздо более высокой точностью по сравнению с эвристикой, в которой учитывается количество невыполненных целей, описанной в разделе 11.2. В рассматриваемой задаче эвристическая оценка для конъюнктивной цели Have {Саке) л Eaten (Саке) будет равна 0 + 1 = 1, тогда как правильный ответ равен 2. Кроме того, если будет удалено действие Баке (Саке), эта оценка по-прежнему будет равна 1, но достижение этой конъюнктивной цели станет невозможной. Наконец, эвристика множественного уровня (set-level) находит уровень, на котором все литералы в конъюнктивной цели появляются в графе планирования без любой пары из них, которая была бы взаимно исключающей. Эта эвристика дает правильное значение, равное 2, для первоначальной задачи и равное бесконечности для задачи без действия Баке (Саке). Она доминирует над эвристикой максимального уровня и действует чрезвычайно успешно в задачах, характеризующихся весьма существенным взаимодействием субпланов.
Для использования его в качестве инструментального средства формирования точных эвристик граф планирования можно рассматривать как ослабленную задачу, которая может быть эффективно решена. Чтобы понять характер этой ослабленной задачи, нужно точно определить, что означает появление литерала д на уровне SL в графе планирования. В идеале желательно было бы иметь гарантию, что существует план с i уровнями действий, который достигает литерала д, а также, что литерал д не появится, если такого плана нет. К сожалению, предоставить такую гарантию столь же трудно, как и решить первоначальную задачу планирования. Поэтому граф планирования предоставляет вторую половину гарантии (если литерал д не появляется, то нет и плана его достижения), но если литерал д появляется, то весь этот граф планирования становится залогом того, что существует план, который, возможно, позволяет достичь литерала дине имеет "очевидных" недостатков. Оневыдный недостаток плана определяется как недостаток, который может быть выявлен путем рассмотрения двух действий или двух литералов одновременно; другими словами, путем проверки взаимно исключающих отношений. Могут существовать более трудно диагностируемые недостатки, охватывающие три, четыре или больше действий, но опыт показывает, что вычислительные затраты, связанные с отслеживанием этих возможных недостатков, не оправдываются. Этот вывод аналогичен уроку, усвоенному по результатам исследования задач удовлетворения ограничений, в которых часто целесообразно вычислить 2-совместимость (совместимость на уровне 2) перед поиском решения, но вычисление 3-совместимости или совместимости более высокой степени часто бывает менее целесообразным (см. раздел 5.2).