Существует несколько способов ограничения комбинаторного взрыва. Как было показано в главе 5, есть несколько методов управления возвратами в задачах удовлетворения ограничений (Constraint Satisfaction Problem — CSP), таких как возвраты, управляемые зависимостями. Все эти методы могут применяться и в планировании. Например, задачу извлечения решения из графа планирования можно сформулировать как булеву задачу CSP, переменные которой указывают, должно ли данное конкретное действие произойти в данное конкретное время. Эту задачу CSP можно решить с использованием любого из алгоритмов, приведенных в главе 5, такого как алгоритм с минимальными конфликтами. Тесно связанный с этим метод, используемый в системе Blackbox, состоит в преобразовании графа планирования в выражение CNF, а затем извлечении плана с использованием решателя задач SAT. По-видимому, такой подход обладает более высокой производительностью, чем SATplan, и причиной этого, скорее всего, является то, что в графе планирования уже устранены многие невозможные состояния и действия из рассматриваемой задачи. Кроме того, такой подход действует лучше по сравнению с алгоритмом Graphplan, по-видимому, из-за того, что поиск условий выполнимости, подобный алгоритму WalkSAT, характеризуется гораздо большей гибкостью, чем ограниченный поиск с возвратами, используемый в алгоритме Graphplan.

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