Главная arrow книги arrow Копия Глава 11. Основы планирования arrow Планирование с частичным упорядочением
Планирование с частичным упорядочением

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

•    Множество действий, из которых состоят этапы плана. Эти действия берутся из множества действий в задаче планирования. "Пустой" план содержит только действия Start и Finish. Действие Start не имеет предусловий, а его результатом являются все литералы в начальном состоянии задачи планирования. Действие Finish не имеет результатов, а его предусловиями являются литералы цели в задаче планирования.

•    Множество ограничений упорядочения. Каждое ограничение упорядочения находится в форме, которая читается как "А перед Б" и означает, что действие А должно быть выполнено в какое-то время перед действием Б, но не обязательно непосредственно перед ним. Ограничения упорядочения должны описывать правильный вариант частичного упорядочения. Любой цикл (такой как ) представляет противоречие, поэтому ни одно ограничение упорядочения не может быть добавлено в план, если оно создает цикл.

•    Множество причинных связей. Причинная связь между двумя действиями А и B в плане записывается каки читается как "А достигает ρ для В". Например, в следующей причинной связи:

утверждается, что RightSockOn (надет правый носок) представляет собой результат действия RightSock и предусловие действия RightShoe. В ней также содержится утверждение, что предусловие RightSockOn должно оставаться истинным со времени действия RightSock до времени действия RightShoe. Другими словами, план не может быть дополнен путем добавления какого-либо нового действия С, которое конфликтует с причинной связью. Действие С конфликтует со связью, если С имеет результат и если С может (в соответствии с ограничениями упорядочения) происходить после А и перед В. Некоторые авторы называют причинные связи интервалами защиты, поскольку связьзащищает предусловие ρ от его отрицания в интервале от А до B.