Работы Аврима Блюма и Меррика Фурста [139], [140] способствовали дальнейшему пробуждению интереса к этой области планирования, поскольку созданная ими система Graphplan оказалась на несколько порядков величин быстрее по сравнению с планировщиками с частичным упорядочением, применявшимися в то время. За ней вскоре последовали разработки других систем с графами планирования, такие как IPP [813], Stan [491] и SGP [1569]. Структура данных, весьма напоминающая граф планирования, была разработана немного раньше Галлабом и Ларуэл-лем [549], которые использовали такую структуру данных в планировщике с частичным упорядочением IxTeT для получения точных эвристик, применяемых для управления поиском. В [1136] приведен очень подробный анализ эвристик, полученных на основе графов планирования. Приведенное в этой главе описание графов планирования главным образом основано на этой работе и на конспектах лекций, подготовленных Суббарао Камбхампати (Subbarao Kambhampati). Как уже указывалось в этой главе, граф планирования позволяет управлять поиском решения задачи с помощью многих способов. Например, победителем соревнования по планированию на конференции AIPS 2002 года стал алгоритм LPG [544], в котором осуществляется поиск в графах планирования с использованием метода локального поиска, основанного на алгоритме WalkSAT.

Подход к планированию как проверке выполнимости и алгоритм SATplan были предложены Каутцем и Селманом [778], которых натолкнул на эту идею поразительный успех в использовании жадного локального поиска для решения задач проверки выполнимости (см. главу 7). Кроме того, Каутц и др. [777] исследовали различные формы пропозициональных представлений для аксиом Strips и обнаружили, что наиболее компактные формы не обязательно способствуют достижению наименьшей продолжительности вычисления решения. Систематический анализ был проведен Эрнстом и др. [442], которые разработали также автоматический "компилятор" для формирования пропозициональных представлений из формулировок задач на языке PDDL. Планировщик Blackbox, в котором объединены идеи алгоритмов Graphplan и SATplan, был разработан Каутцем и Селманом [779].