Многотельное планирование
В данном разделе речь пойдет в основном о формировании правильных совместных планов, а вопросы координации мы пока отложим. Авторы называют данный подход многотельным планированием (multibody planning); по сути именно в этом состоит задача планирования, с которой сталкивается также один централизованный агент, который может раздавать указания по выполнению действий каждой из нескольких физических сущностей. А если рассматривается случай, в котором действует несколько настоящих агентов, такое планирование дает возможность каждому агенту выяснить, каковы возможные совместные планы, которые позволили бы агентам добиться успеха, если бы они действовали согласованно.
Применяемый нами подход к многотельному планированию будет основан на планировании с частичным упорядочением, которое описано в разделе 11.3. Чтобы упростить решение этой проблемы, мы будем исходить из предположения о полной наблюдаемости среды. Есть еще один дополнительный вопрос, который не возникает в одноагентном случае: среда больше не является в полном смысле этого слова статической, поскольку другие агенты могут действовать, пока какой-то конкретный агент размышляет. Поэтому необходимо позаботиться о синхронизации. Для упрощения мы будем предполагать, что каждое действие занимает одно и то же количество времени и что действия, выполняемые в каждом пункте совместного плана, являются одновременными.
В любой момент времени каждый агент выполняет одно и только одно действие (возможно, включая пустую операцию NoOp). Такое множество одновременных действий называется совместным действием (joint action). Например, совместным действием в проблемной области тенниса (с. 1) с агентами А и в является
Это планирование может быть выполнено с помощью обычного алгоритма POP, применяемого к множеству всех возможных совместных действий. Единственная проблема состоит в огромных размерах этого множества: при наличии 10 действий и 5 агентов количество совместных действий составляет 105. Было бы очень утомительным правильное определение предусловий и результатов каждого действия, а разработка плана на таком большом множестве стала бы неэффективной.
Альтернативный подход заключается в том, что совместные действия определяются неявно путем описания того, как каждое отдельное действие сочетается с другими возможными действиями. Такой подход должен быть проще, поскольку большинство действий независимы друг от друга, поэтому нам потребуется перечислить лишь немного действий, которые действительно взаимодействуют друг с другом. Это можно сделать, дополнив обычные описания действий Strips или ADL одним новым средством — списком одновременных действий (concurrent action list). Этот список аналогичен предусловию любого описания действия, за исключением того, что в нем описываются не переменные состояния, а действия, которые должны или не должны выполняться одновременно. Например, действие удара по мячу, Hi t, может быть описано следующим образом:
Action{Hit{A, Ball),
Concurrent: -iHit(B, Ball),
Precond: Approaching{Ball, [x, у] ) л At{A, [x, y] ) , Effect: Returned{Ball))
В данном случае мы встречаемся с ограничением, запрещающим одновременное выполнение, согласно которому при выполнении действия Hi t одним агентом не должно быть выполнения действия Hi t другим агентом. А иногда как раз и требуются одновременные действия, например, если портативный холодильник, заполненный напитками, смогут отнести на теннисный корт только два агента. В описании для этого действия должно быть сказано, что агент А не сможет выполнить действие Carry, если нет другого агента, в, который одновременно выполнил бы действие Carry применительно к тому же холодильнику:
Action(Carry{A, cooler, here, there),
Concurrent: Carry(B, cooler, here, there),
Precond: At{A, here) л At{cooler, here) л Cooler(cooler), Effect: At (A, there) л At (cooler, there) л —At (A, here) л —\At(cooler, here))
При использовании такого представления появляется возможность создать планировщик, который весьма напоминает планировщик с частичным упорядочением, действующий по алгоритму POP. Но между этими двумя планировщиками существуют три различия, которые описаны ниже.
1. Кроме отношения временного упорядочения А -< В разрешается использовать отношения А = В и А В, которые означают "одновременно" и "прежде или одновременно", соответственно.
2. Если какое-то новое действие требует одновременных действий, необходимо конкретизировать эти действия, используя новые или существующие действия в плане.
3. Запрещенные одновременные действия являются дополнительным источником ограничений. Каждое ограничение должно быть разрешено путем наложения на конфликтующие действия таких ограничений, чтобы они могли быть выполнены либо прежде, либо позже другого конфликтующего действия.
Такое представление позволяет создать алгоритм планирования для многотельных проблемных областей, эквивалентный алгоритму POP. Мы могли бы дополнить этот подход с помощью уточнений, приведенных в последних двух главах (сетей HTN, частичной наблюдаемости, условных планов, контроля выполнения и перепланирования), но такая задача выходит за рамки настоящей книги.