Планировщик должен быть способен предложить последовательность из двух действий, RightSock (Надеть правый носок), затем RightShoe (Надеть правую туфлю), чтобы достичь первого конъюнкта этой цели, и последовательность LeftSock (Надеть левый носок), затем LeftShoe (Надеть левую туфлю), чтобы достичь второго конъюнкта. После этого эти две последовательности могут быть объединены для создания окончательного плана. В ходе этого планировщик будет манипулировать двумя подпоследовательностями независимо, не задумываясь над тем, должно ли какое-то действие в одной последовательности быть выполнено до или после некоторого действия в другой. Любой алгоритм планирования, способный включить в план два действия без указания того, какое из них должно быть выполнено первым, называется планировщиком с частичным упорядочением (partial-order planner). На рис. 11.2 показан план с частичным упорядочением, который представляет собой решение задачи надевания туфель и носков. Обратите внимание на то, что это решение представлено в виде графа, а не последовательности действий. Заслуживают также внимания "фиктивные" действия, называемые Start и Finish, которые отмечают начало и конец плана. Назвав эти ситуации действиями, мы можем упростить структуру плана, поскольку теперь каждый этап плана становится действием. Это решение с частичным упорядочением соответствует шести возможным планам с полным упорядочением; каждый из них называется линеаризацией плана с частичным упорядочением.

Планирование с частичным упорядочением может быть реализовано в виде поиска в пространстве планов с частичным упорядочением. (Начиная с этого момента, мы будем называть их просто "планами".) Это означает, что поиск начинается с пустого плана. После этого рассматриваются способы уточнения плана до тех пор, пока не удастся составить полный план, который решает данную задачу. Действия, рассматриваемые в этом поиске, являются не действиями в мире, а действиями в планах: добавление в план этапа; наложение упорядочения, согласно которому одно действие должно занять место перед другим; и т.д.

В данном разделе будет определен алгоритм POP (Partial-Order Planning) для планирования с частичным упорядочением. В соответствии с общепринятой традицией алгоритм POP оформляется в виде отдельной программы, но мы вместо этого определим задачу планирования с частичным упорядочением как экземпляр задачи поиска. Это позволит нам сосредоточиться на этапах уточнения плана, которые могут быть применены, и не задумываться над тем, каким образом алгоритм осуществляет исследование пространства поиска. В действительности после формулировки задачи поиска может быть применен широкий перечень неинформированных или эвристических методов поиска.

Рис. 11.2. План надевания туфель и носков с частичным упорядочением и шесть соответствующих линеаризации в виде планов с полным упорядочением