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

Граф планирования состоит из последовательности уровней, которые соответствуют временным этапам в плане, где уровень 0 представляет собой начальное состояние. Каждый уровень содержит множество литералов и множество действий. Грубо говоря, литералы представляют собой то, что может быть истинным на каждом временном этапе в зависимости от действий, выполненных на предыдущих вре-менных этапах. Также грубо говоря, действиями являются все те действия, которые могут иметь все свои предусловия выполненными на данном временном этапе в зависимости от того, какие из литералов фактически являются истинными. В этих двух определениях применяется выражение "грубо говоря", поскольку в графе планирования регистрируется только ограниченное подмножество возможных отрицательных взаимодействий между действиями; поэтому граф может давать оптимистическую оценку минимального количества временных этапов, требуемых для того, чтобы некоторый литерал стал истинным. Тем не менее такое количество этапов в графе планирования предоставляет хорошую оценку того, насколько трудно достичь указанного литерала из начального состояния. Еще важнее то, что граф планирования определен таким образом, что может быть сформирован очень эффективно.

Графы планирования могут применяться только для решения задач планирования в пропозициональной логике, т.е. тех задач, в которых отсутствуют переменные. Как упоминалось в разделе 11.1, в пропозициональную форму могут быть преобразованы и представления Strips, и представления ADL. Если в задаче имеется большое количество объектов, это может привести к весьма существенному возрастанию количества возможных схем действий. Несмотря на это, было показано, что графы планирования представляют собой эффективное инструментальное средство решения трудных задач планирования.