Граф планирования может формироваться инкрементно, начиная с начального состояния. Каждый его уровень содержит надмножество всех литералов или действий, которые могут обнаруживаться на данном временном этапе. Кроме того, на каждом уровне условно задаются отношения взаимного исключения, или взаимно исключающие отношения между литералами или действиями, которые не могут происходить одновременно. Графы планирования позволяют получать полезные эвристики для планировщиков в пространстве состояний и планировщиков с частичным упорядочением и могут использоваться непосредственно в алгоритме Graphplan.

Алгоритм Graphplan обрабатывает граф планирования, используя обратный поиск для извлечения плана. Этот алгоритм допускает определенное частичное упорядочение между действиями.

В алгоритме SATplan задача планирования преобразуется в пропозициональные аксиомы и после этого к ним применяется алгоритм проверки выполнимости для поиска модели, соответствующей действительному плану. Было разработано несколько разных пропозициональных представлений, обладающих различной степенью компактности и эффективности.

Каждый из основных подходов к планированию имеет своих сторонников, и еще не достигнуто полное согласие в том, какой из этих подходов является наилучшим. Конкуренция между этими подходами и их взаимное обогащение привели к существенному повышению эффективности систем планирования.