Повторное пробуждение интереса к планированию в пространстве состояний было в основном вызвано появлением программы UnPOP, разработанной Макдер-моттом [1024], который впервые предложил эвристику с учетом расстояния, основанную на ослабленной задаче с исключенными списками удаления. Само название UnPOP (отказ от POP) стало реакцией на чрезмерное в то время сосредоточение работ на планировании с частичным упорядочением; Макдермотт считал, что другие подходы не получают того внимания, которого они заслуживают. В алгоритме HSP (Heuristic Search Planner — планировщик с эвристическим поиском) Бонета и Гефф-нера [147] и его разработанных позже аналогах впервые удалось добиться практического применения поиска в пространстве состояний при решении крупных задач планирования. В то время самым успешным алгоритмом поиска в пространстве состояний был алгоритм FastForward, или FF, Хоффмана [667], который стал победителем в соревновании по планированию на конференции AIPS в 2000 году. В алгоритме FF используется упрощенная эвристика для графа планирования в сочетании с очень быстрым алгоритмом поиска, представляющим собой новаторское объединение прямого и локального поиска.

В дальнейшем появился интерес к использованию представления планов в виде бинарных диаграмм решения (binary decision diagram — BDD) — компактного описания конечных автоматов, которое широко исследовалось в сообществе разработчиков средств проверки аппаратного обеспечения [266], [1031]. Существуют методы доказательства свойств бинарных диаграмм решения, включая свойство быть решением задачи планирования. В [261] представлен планировщик, основанный на этом подходе. Применялись также другие представления; например, в [1549] приведен обзор использования целочисленного программирования для планирования.