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

Планирование главным образом представляет собой такое занятие, в котором приходится держать под контролем комбинаторный взрыв. Если в проблемной области имеется ρ примитивных высказываний, то количество состояний становится равным. В сложных проблемных областях величина ρ может стать весьма значительной. Следует также учитывать, что объекты в проблемной области характеризуются не только свойствами (Location, Color и т.д.), но и отношениями (At, On, Between и т.д.). При наличии d объектов в проблемной области с тернарными отношениями количество состояний достигает. На этом основании можно сделать вывод, что в наихудшем случае попытка решить задачу планирования становится безнадежной.

Мощным средством преодоления подобной пессимистической ситуации становится подход по принципу "разделяй и властвуй". В наилучшем случае (при полной декомпонуемости задачи) подход "разделяй и властвуй" обеспечивает экспоненциальное ускорение работы. Однако декомпонуемость нарушается из-за отрицательных взаимодействий между действиями. Планировщики с частичным упорядочением позволяют справиться с такой ситуацией с помощью причинных связей — мощного подхода к формированию представлений, но, к сожалению, каждый конфликт должен быть разрешен с помощью выбора определенного варианта (связанного с размещением конфликтующего действия до или после связи), а количество таких вариантов может увеличиваться экспоненциально. Алгоритм Graphplan позволяет избежать необходимости использования этих вариантов на этапе формирования графа, поскольку в нем для регистрации конфликтов используются взаимно исключающие связи, а выбор варианта, касающегося того, как должны быть разрешены эти конфликты, фактически не осуществляется. Алгоритм SATplan предоставляет аналогичный набор взаимно исключающих отношений, но в нем для этого применяется общая форма CNF, а не специальная структура данных. Насколько успешным окажется такой подход, зависит от области применения решателя задач SAT.