Поиск в обратном направлении иногда называют регрессивным планированием. Основной вопрос регрессивного планирования состоит в следующем: есть ли такие состояния, из которых применение некоторого действия приводит к цели? Вычисление описаний таких состояний называется регрессией цели через действие. Для того чтобы определить, как можно найти ответ на указанный выше вопрос, рассмотрим пример с воздушными грузовыми перевозками. Мы имеем цель

и релевантное действие Unload(C1,p, В), которое позволяет достичь первого конъюнкта. Соответствующее действие будет выполнимо, только если выполнены его предусловия. Поэтому любое состояние-преемник должно включать эти предусловия:. Более того, подцель At(C1, В) не должна быть истинной в состоянии-преемнике4. Поэтому описание состояния-преемника является таковым:

Кроме выполнения того требования, чтобы действия достигали некоторого желаемого литерала, должно также соблюдаться требование, чтобы действия не отменяли какие-либо желаемые литералы. Любое действие, удовлетворяющее этому ограничению, называется совместимым. Например, действие Load(C2, р) не будет совместимым с текущей целью, поскольку оно отрицает литерал At (С2, В).

Составив определения понятий релевантности и совместимости, мы можем описать общий процесс формирования преемников для обратного поиска. Допустим, что при наличии описания цели G имеется действие А, которое является релевантным и совместимым. Соответствующий преемник может быть определен, как описано ниже.

•    Любые положительные результаты действия А, которые появляются в цели G, удаляются.

•    Добавляется каждый литерал предусловия А, если он еще не присутствует в определении действия.

Для осуществления обратного поиска могут использоваться любые из стандартных алгоритмов поиска. Завершение работы происходит после выработки такого описания преемника, которое соответствует начальному состоянию задачи планирования. В случае использования логики первого порядка для обеспечения соответствия с начальным состоянием может потребоваться подстановка переменных в описание преемника. Например, описание преемника, приведенное в предыдущем абзаце, будет соответствовать такому начальному состоянию после подстановки {р/ Р12}:

Затем данная подстановка должна быть применена к действиям, ведущим из этого состояния к цели, что приводит к получению решения