В первой половине 1970-х годов планировщики в основном применялись для получения полностью упорядоченных последовательностей действий. Декомпозиция задачи осуществлялась путем вычисления субплана для каждой подцели с последующей увязкой субпланов в единую цепочку в некотором порядке. Вскоре было обнаружено, что такой подход, названный линейным планированием в [1337], является неполным. Он не позволяет решать некоторые очень простые задачи, такие как аномалия Зюссмана, обнаруженная Алленом Брауном во время экспериментов с системой Hacker [1474]. Полный планировщик должен обеспечивать чередование действий из различных субпланов в пределах единой последовательности. Понятие упорядочиваемых подцелей [837] точно соответствует множеству задач, для которых планировщики без чередования позволяют получить полное решение.

Одним из решений проблемы чередования оказалось планирование с регрессией от цели. Это — метод, в котором этапы полностью упорядоченного плана переупорядочиваются так, чтобы можно было избежать конфликта между подцелями. Данный подход был предложен Уолдингером [1551], кроме того, использовался в системе Warplan Уоррена [1554]. Система Warplan замечательна также тем, что была первым планировщиком, написанным на языке логического программирования (Prolog), и остается одним из лучших примеров невероятной экономии объема кода, которая иногда может быть достигнута с использованием логического программирования: программа Warplan состоит только из 100 строк кода, что составляет лишь небольшую часть размера сравнимых с ней планировщиков на то время. Система Interplan [1493], [1494] обеспечивала также произвольное чередование этапов плана, что дало возможность преодолеть аномалию Зюссмана и связанные с ней проблемы.

К основным идеям, лежащим в основе планирования с частичным упорядочением, относятся обнаружение конфликтов [1493] и защита достигнутых условий от вмешательства [1474]. Первыми примерами средств создания планов с частичным упорядочением (которые в то время назывались сетями задач) были планировщик Noah Сакердоти [1337], [1338] и система Nonlin Тейта [1494], [1495]