Напомним, что при отсутствии функциональных символов пространство состояний задачи планирования является конечным. Поэтому полным алгоритмом планирования должен быть любой алгоритм поиска в графе, который является полным (например, А*).

Начиная с самых первых дней исследований по планированию (примерно с 1961 года) и до сравнительно недавнего времени (примерно до 1998 года), предполагалось, что прямой поиск в пространстве состояний был бы слишком неэффективен для того, чтобы иметь практическое значение. Причины этого понять совсем несложно — достаточно вернуться в начало раздела 11.1. Во-первых, прямой поиск не решает проблему не относящихся к делу действий — рассматриваются все действия, применимые из каждого состояния. Во-вторых, без хорошей эвристики этот подход быстро приводит к чрезмерному увеличению объема вычислений. Рассмотрим задачу воздушных грузовых перевозок с 10 аэропортами, где в каждом аэропорту имеется 5 самолетов и 20 единиц груза. Цель состоит в том, чтобы переместить все грузы из аэропорта А в аэропорт В. Существует простое решение этой задачи: погрузить 20 единиц груза в один из самолетов в аэропорту А, полететь на этом самолете в аэропорт В и выгрузить груз. Но формальный поиск этого решения может оказаться затруднительным, поскольку средний коэффициент ветвления является огромным: каждый из этих 5x10 = 5 0 самолетов может полететь в 9 других аэропортов, а каждая из 2 0x10=200 единиц груза может быть либо разгружена (если она загружена), либо загружена в любой самолет в аэропорту, где она находится (если она разгружена). Допустим, что в среднем существует около 100 0 возможных действий, поэтому дерево поиска с глубиной, равной глубине очевидного решения, имеет около узлов. Очевидно, что для обеспечения эффективности такого поиска потребуется очень точная эвристика. Мы рассмотрим некоторые возможные эвристики после описания обратного поиска.