Еще раз напомним, что действия, рассматриваемые в алгоритмах поиска при такой формулировке, представляют собой этапы уточнения плана, а не реальные действия из самой проблемной области. Поэтому, строго говоря, стоимость пути не имеет значения, поскольку важна только суммарная стоимость реальных действий в плане, к которому ведет этот путь. Тем не менее существует возможность определить функцию стоимости пути, которая отражает стоимости реальных планов; для этого можно назначать цену 1 за каждое реальное действие, добавленное к плану, и 0 — за все остальные этапы уточнения. В таком случае значение функции д{п), где п — некоторый план, будет равно количеству реальных действий в плане. Может также использоваться эвристическая оценка h(n).

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