ПЛАНИРОВАНИЕ С ЧАСТИЧНЫМ УПОРЯДОЧЕНИЕМ
Прямой и обратный поиск в пространстве состояний представляют собой особые формы поиска полностью упорядоченного плана. В них рассматриваются только строго линейные последовательности действий, непосредственно связанные с начальным или целевым состоянием. Это означает, что такие методы поиска не позволяют воспользоваться преимуществами декомпозиции задачи. Вместо того чтобы обеспечить отдельную проработку каждой подзадачи, эти методы вынуждены всегда поддерживать принятие решений о том, как упорядочить действия, относящиеся ко всем подзадачам. Но обычно более предпочтительным является подход, позволяющий работать над несколькими подцелями независимо, достигать их с помощью нескольких субпланов, а затем объединять эти субпланы.
Подобный подход обладает также тем преимуществом, что позволяет добиться большей гибкости при определении последовательности, в которой составляется окончательный план. Это означает, что планировщик вначале может работать над "очевидными" или "важными" решениями, не будучи вынужденным прорабатывать все этапы в хронологическом порядке. Например, планирующий агент, который находится в Беркли и желает попасть в Монте-Карло, может вначале попытаться найти рейс из Сан-Франциско в Париж; получив информацию о времени отправления и прибытия этого рейса, он может затем заняться поиском способов того, как доехать и выехать из соответствующих аэропортов.
Общая стратегия, в которой в процессе поиска выбор определенных этапов откладывается на более позднее время, называется стратегией с наименьшим вкладом (least commitment). Формального определения стратегии с наименьшим вкладом не существует, поскольку очевидно, что на любом этапе поиска должен быть сделан определенный вклад в окончательное решение, так как в противном случае поиск окажется непродуктивным. Несмотря на такую неформальность, наименьший вклад — это полезная концепция для анализа того, какие решения должны быть приняты в любой задаче поиска.
Приведенный в этом разделе первый конкретный пример будет гораздо проще по сравнению с планированием отпуска, проводимого в Монте-Карло. Рассмотрим простую задачу надевания пары туфель. Ее можно описать как формальную задачу планирования следующим образом:
Goal{RightShoeOn л LeftShoeOn) Init()
Action{RightShoe,Precond: RightSockOn,Effect: RightShoeOn) ActioniRightSock,Effect: RightSockOn)
Action{LeftShoe,Precond: LeftSockOn,Effect: LeftShoeOn) Action(LeftSock,Effect: LeftSockOn)
Планировщик должен быть способен предложить последовательность из двух действий, RightSock (Надеть правый носок), затем RightShoe (Надеть правую туфлю), чтобы достичь первого конъюнкта этой цели, и последовательность LeftSock (Надеть левый носок), затем LeftShoe (Надеть левую туфлю), чтобы достичь второго конъюнкта. После этого эти две последовательности могут быть объединены для создания окончательного плана. В ходе этого планировщик будет манипулировать двумя подпоследовательностями независимо, не задумываясь над тем, должно ли какое-то действие в одной последовательности быть выполнено до или после некоторого действия в другой. Любой алгоритм планирования, способный включить в план два действия без указания того, какое из них должно быть выполнено первым, называется планировщиком с частичным упорядочением (partial-order planner). На рис. 11.2 показан план с частичным упорядочением, который представляет собой решение задачи надевания туфель и носков. Обратите внимание на то, что это решение представлено в виде графа, а не последовательности действий. Заслуживают также внимания "фиктивные" действия, называемые Start и Finish, которые отмечают начало и конец плана. Назвав эти ситуации действиями, мы можем упростить структуру плана, поскольку теперь каждый этап плана становится действием. Это решение с частичным упорядочением соответствует шести возможным планам с полным упорядочением; каждый из них называется линеаризацией плана с частичным упорядочением.
Планирование с частичным упорядочением может быть реализовано в виде поиска в пространстве планов с частичным упорядочением. (Начиная с этого момента, мы будем называть их просто "планами".) Это означает, что поиск начинается с пустого плана. После этого рассматриваются способы уточнения плана до тех пор, пока не удастся составить полный план, который решает данную задачу. Действия, рассматриваемые в этом поиске, являются не действиями в мире, а действиями в планах: добавление в план этапа; наложение упорядочения, согласно которому одно действие должно занять место перед другим; и т.д.
В данном разделе будет определен алгоритм POP (Partial-Order Planning) для планирования с частичным упорядочением. В соответствии с общепринятой традицией алгоритм POP оформляется в виде отдельной программы, но мы вместо этого определим задачу планирования с частичным упорядочением как экземпляр задачи поиска. Это позволит нам сосредоточиться на этапах уточнения плана, которые могут быть применены, и не задумываться над тем, каким образом алгоритм осуществляет исследование пространства поиска. В действительности после формулировки задачи поиска может быть применен широкий перечень неинформированных или эвристических методов поиска.
Напомним, что состояниями рассматриваемой задачи поиска должны быть планы (в основном незаконченные). Чтобы избежать путаницы с состояниями мира, мы будем вести речь о планах, а не о состояниях. Каждый план имеет описанные ниже четыре компонента, где первые два определяют этапы плана, а последние два выполняют функции учета, позволяющие определить, как может быть дополнен план.
• Множество действий, из которых состоят этапы плана. Эти действия берутся из множества действий в задаче планирования. "Пустой" план содержит только действия Start и Finish. Действие Start не имеет предусловий, а его результатом являются все литералы в начальном состоянии задачи планирования. Действие Finish не имеет результатов, а его предусловиями являются литералы цели в задаче планирования.
• Множество ограничений упорядочения. Каждое ограничение упорядочения находится в форме А -< В, которая читается как "А перед в" и означает, что действие А должно быть выполнено в какое-то время перед действием в, но не обязательно непосредственно перед ним. Ограничения упорядочения должны описывать правильный вариант частичного упорядочения. Любой цикл (такой как А -< В и В -< А) представляет противоречие, поэтому ни одно ограничение упорядочения не может быть добавлено в план, если оно создает цикл.
• Множество причинных связей. Причинная связь между двумя действиями А и Б в плане записывается как А—и читается как "А достигает р для В". Например, в следующей причинной связи:
Ri ghtSockRi95k0nRi ghtShoe
утверждается, что RightSockOn (надет правый носок) представляет собой результат действия RightSock и предусловие действия RightShoe. В ней также содержится утверждение, что предусловие RightSockOn должно оставаться истинным со времени действия RightSock до времени действия RightShoe. Другими словами, план не может быть дополнен путем добавления какого-либо нового действия С, которое конфликтует с причинной связью. Действие С конфликтует со связью А—->в, если С имеет результат -р и если С может (в соответствии с ограничениями упорядочения) происходить после А и перед В. Некоторые авторы называют причинные связи интервалами защиты, поскольку связь A—->B защищает предусловие р от его отрицания в интервале от А до В.
• Множество .открытых предусловий. Предусловие является открытым, если оно не достигнуто с помощью какого-то действия в плане. Планировщики действуют по принципу сокращения множества открытых предусловий до пустого множества без внесения противоречия.
Например, окончательный план, показанный на рис. 11.2, имеет следующие компоненты (не показаны ограничения упорядочения, которые распространяются на каждое действие после действия Start и перед действием Finish):
Действия: {RightSock, RightShoe, LeftSock, LeftShoe, Start, Finish} Упорядочения: {RightSock < RightShoe, LeftSock < LeftShoe} Связи: { RightSock RightShoe, LeftSockhet-±0nLeftShoe,
RightShoe Rige0nFinish, LeftShoeLet-e0nFinish} Открытые предусловия: {}
Мы определяем согласованный план (consistent plan) как план, в котором не имеется циклов в ограничениях упорядочения и нет конфликтов с причинными связями. Согласованный план без открытых предусловий представляет собой решение. Даже краткие размышления должны убедить читателя в справедливости следующего утверждения: каждая линеаризация решения с частичным упорядочением представляет собой решение с полным упорядочением, выполнение которого из начального состояния позволяет достичь целевого состояния. Это означает, что можно распространить понятие "выполнения плана" с планов с полным упорядочением на планы с частичным упорядочением. План с частичным упорядочением выполняется путем повторного выбора любого из возможных следующих действий. Как будет показано в главе 12, такая гибкость, предоставляемая агенту в ходе выполнения плана, может быть очень полезной в тех обстоятельствах, когда мир к нему не благосклонен. Гибкое упорядочение позволяет также упростить комбинирование меньших планов в более крупные, поскольку каждый из меньших планов допускает переупорядочение его действий для предотвращения конфликтов с другими планами.
Теперь мы готовы сформулировать задачу поиска, которую решает алгоритм POP, как показано ниже. Начнем с формулировки, подходящей для задач планирования в пропозициональной логике, оставляя на будущее осложнения, связанные с использованием логики первого порядка. Как обычно, это определение включает начальное состояние, действия и проверку цели.
• Начальный план содержит действия Start и Finish, ограничение упорядочения Start -< Finish, не включает ни одной причинной связи и имеет все предусловия в действии Finish в качестве открытых предусловий.
• Функция определения преемника произвольным образом выбирает одно открытое предусловие р действия В и вырабатывает план-преемник для каждого возможного согласованного способа выбора действия А, которое достигает р. Согласованность обеспечивается принудительно следующим образом.
1. Причинная связь А-->В и ограничение упорядочения А -< В добавляются к плану. Действие А может быть существующим действием в плане или новым действием. Если оно является новым, добавить его к плану, а также добавить Start ?< АиА ?<; Finish.
2. Разрешаются конфликты между новой причинной связью и всеми существующими действиями, а также между действием А (если оно является новым) и всеми существующими причинными связями. Конфликт между А Р >в и С разрешается путем обеспечения того, чтобы действие С происходило в какое-то время за пределами интервала защиты, либо за счет добавления ограничения В -< С, либо путем добавления ограничения С -< А. Для одного из них или обоих добавляются состояния-преемники, если они приводят к созданию согласованных планов.
• В ходе проверки цели осуществляется проверка того, является ли текущий план решением первоначальной задачи планирования. Поскольку вырабатываются только согласованные планы, в проверке цели достаточно только проконтролировать, есть ли еще открытые предусловия.
Еще раз напомним, что действия, рассматриваемые в алгоритмах поиска при такой формулировке, представляют собой этапы уточнения плана, а не реальные действия из самой проблемной области. Поэтому, строго говоря, стоимость пути не имеет значения, поскольку важна только суммарная стоимость реальных действий в плане, к которому ведет этот путь. Тем не менее существует возможность определить функцию стоимости пути, которая отражает стоимости реальных планов; для этого можно назначать цену 1 за каждое реальное действие, добавленное к плану, и 0 — за все остальные этапы уточнения. В таком случае значение функции д{п), где л— некоторый план, будет равно количеству реальных действий в плане. Может также использоваться эвристическая оценка h(n).
На первый взгляд может показаться, что функция определения преемника должна вырабатывать преемников для каждого открытого предусловия р, а не только для одного из них. Но такой подход был бы избыточным и неэффективным по той же причине, по которой алгоритмы удовлетворения ограничений не включают преемников для каждой возможной переменной, поскольку порядок, в котором рассматриваются открытые предусловия (как и порядок, в котором рассматриваются переменные CSP), является коммутативным (см. с. 214). Таким образом, мы можем выбирать произвольное упорядочение и все еще иметь полный алгоритм. Выбор правильного упорядочения может привести к более быстрому поиску, но все упорядочения оканчиваются одним и тем же множеством решений-кандидатов.