Итак, из описанного выше следует, что ни прямой, ни обратный поиск не может быть эффективным без хорошей эвристической функции. Как было указано в главе 4, эвристическая функция оценивает расстояние от некоторого состояния до цели; в планировании Strips стоимость каждого действия равна 1, поэтому расстояние измеряется количеством действий. Основная идея состоит в том, что нужно рассматривать результаты действий и цели, которые должны быть достигнуты, а после этого выдвигать предположение, сколько действий потребуется для достижения всех целей. Задача определения точного количества действий является NP-трудной, но чаще всего существует возможность найти приемлемые оценки без слишком большого объема вычислений. Необходимо также иметь возможность вывести допустимую эвристику, которая не приводит к переоценке. Такая эвристика может использоваться в сочетании с поиском А* для нахождения оптимальных решений.

Для составления эвристики могут быть опробованы два подхода. Первый из них состоит в том, чтобы вывести ослабленную задачу из заданной спецификации задачи (см. главу 4). Оптимальная стоимость решения для ослабленной задачи (которую можно надеяться очень легко решить) задает допустимую эвристику для первоначальной задачи. Второй подход состоит в том, что можно воспользоваться предположением о возможности применения алгоритма, действующего исключительно по принципу "разделяй и властвуй". Такое предположение называется предположением о независимости подцелей, согласно которому стоимость решения конъюнкции подцелей аппроксимируется суммой стоимостей решения каждой подцели независимо друг от друга. Предположение о независимости подцелей может быть оптимистическим или пессимистическим. Оно является оптимистическим, если имеются отрицательные взаимодействия субпланов для каждой подцели, например, если действие в одном субплане удаляет цель, достигнутую в другом субплане. С другой стороны, такое предположение является пессимистическим и поэтому недопустимым, если субпланы содержат избыточные действия, например, два таких действия, которые могут быть заменены одним действием в объединенном плане.