Планирование с частичным упорядочением в течение следующих 20 лет стало ведущим направлением разработок, несмотря на то, что в течение основной части этого периода специфика данной области не нашла широкого понимания. Система Tweak Чепмена [234] стала образцом логической реконструкции и упрощения работ по планированию, проводимых в то время; формулировки, используемые в этой системе, были достаточно ясными для того, чтобы можно было доказывать полноту и разрешимость (либо NP-трудность и неразрешимость) различных формулировок задач планирования. Эта работа Чепмена привела к созданию Макаллестером и Ро-зенблиттом [1008] полного планировщика с частичным упорядочением, который впервые можно было вполне обоснованно считать имеющим достаточно простое и доступное для чтения описание [1008]. Одна из реализаций алгоритма Макаллестера и Розенблитта, разработанная Содерлендом и Уэлдом и получившая название SNLP [1444], нашла широкое распространение и впервые позволила многим исследователям изучать и проводить эксперименты по планированию с частичным упорядочением. Алгоритм POP, описанный в этой главе, основан на алгоритме SNLP.

Кроме того, группа Уэлда разработала UCPOP [1202], первый планировщик для задач, представленных на языке ADL. В планировщике UCPOP применяется эвристика, в которой учитывается количество невыполненных целей. Применяемый в нем алгоритм работал немного быстрее, чем SNLP, но редко оказывался способным находить планы, состоящие больше чем примерно из десяти этапов. Хотя для планировщика UCPOP были разработаны усовершенствованные эвристики [543], [751], направление планирования с частичным упорядочением постепенно вытеснялось из перспективных исследований в 1990-х годах по мере появления более быстрых методов. Но в [1135] было показано, что эта область исследований вполне заслуживает возобновления к ней интереса: предложенный в этой работе планировщик RePOP при использовании точной эвристики, полученной из графа планирования, оказался намного более масштабируемым по сравнению с планировщиком Graphplan и сумел составить конкуренцию самым быстрым планировщикам в пространстве состояний.