Граф планирования после его построения становится богатым источником информации о задаче. Например, очевидно, что литерал, который не появляется на заключительном уровне графа, не может быть достигнут с помощью любого плана. Такое наблюдение может использоваться в обратном поиске следующим образом: любое состояние, содержащее недостижимый литерал, имеет стоимость. Аналогичным образом, при планировании с частичным упорядочением любой план с недостижимым открытым условием имеет

Эту идею можно сделать более обобщенной. Стоимость достижения любого целевого литерала может оцениваться как номер уровня, на котором он впервые появляется в графе планирования. Назовем эту оценку уровневой стоимостью (level cost) цели. На рис. 11.6 литерал Have (Саке) имеет уровневую стоимость 0, a Eaten(Cake) — уровневую стоимость 1. Можно легко показать (упр. 11.9), что эти оценки являются допустимыми для отдельных целей. Однако сами эти оценки могут оказаться не очень качественными, поскольку графы планирования допускают наличие несколько действий на каждом уровне, тогда как в этой эвристике учитывается только номер уровня, а не количество действий. По этой причине для вычисления эвристики принято использовать последовательный граф планирования (serial planning graph). Последовательный граф требует, чтобы на каждом конкретном временном этапе фактически могло происходить только одно действие; такое требование осуществляется путем введения взаимно исключающих связей между каждой парой действий, кроме сохраняющих действий. Уровневые стоимости, извлеченные из последовательных графов, часто представляют собой вполне приемлемые оценки фактических стоимостей.