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

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

В языке Strips применяются описания действий в терминах их предусловий и результатов, а также описания начальных и целевых состояний в виде конъюнкций положительных литералов. В языке ADL некоторые ограничения языка Strips ослаблены и допускается использование дизъюнкции, отрицания и кванторов.

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

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