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

Применяемый нами подход к многотельному планированию будет основан на планировании с частичным упорядочением, которое описано в разделе 11.3. Чтобы упростить решение этой проблемы, мы будем исходить из предположения о полной наблюдаемости среды. Есть еще один дополнительный вопрос, который не возникает в одноагентном случае: среда больше не является в полном смысле этого слова статической, поскольку другие агенты могут действовать, пока какой-то конкретный агент размышляет. Поэтому необходимо позаботиться о синхронизации. Для упрощения мы будем предполагать, что каждое действие занимает одно и то же количество времени и что действия, выполняемые в каждом пункте совместного плана, являются одновременными.

В любой момент времени каждый агент выполняет одно и только одно действие (возможно, включая пустую операцию NoOp). Такое множество одновременных действий называется совместным действием (joint action). Например, совместным действием в проблемной области тенниса (с. 1) с агентами А и в является . Совместный план состоит из частично упорядоченного графа совместных действий. Например, план 2 для описанной выше задачи игры в теннис может быть представлен как такая последовательность совместных действий: