1.1 Manufacturing Example

As a running example to motivate this work, consider a manufacturing plant where a production manager, a facilities manager, and an inventory manager each have their own goals with separately constructed hierarchical plans to achieve them. However, they still need to coordinate over the use of equipment, the availability of parts used in the manufacturing of other parts, storage for the parts, and the use of transports for moving parts around. The state of the factory is shown in Figure 1. In this domain, agents can produce parts using machines M1 and M2, service the machines with a tool, and move parts to and from the shipping dock and storage bins on the shop floor using transports. Initially, machines M1 and M2 are free for use, and the transports (transport1 and transport2), the tool, and all of the parts (A through E) shown in their storage locations are available.

Figure 1: A simple example of a manufacturing domain

The production manager is responsible for creating a part H using machines M1 and M2. Either M1 and M2 can consume parts A and B to produce G, and M2 can produce H from G. The production manager's hierarchical plan for manufacturing H involves using the transports to move the needed parts from storage to the input trays of the machines, manufacturing G and H, and transporting H back to storage. This plan is shown in Figure 2. Arcs through subplan branches mean that all subplans must be executed. Branches without arcs denote alternative choices to achieving the parent's goal. The decomposition of $produce\_G\_on\_M1$ is similar to that of $produce\_G\_on\_M2$.

Figure 2: The production manager's hierarchical plan

The facilities manager services each machine by equipping it with a tool and then calibrating it. The machines are unavailable for production while being serviced. The facilities manager's hierarchical plan branches into choices of servicing the machines in different orders and uses the transports for getting the tool from storage to the machines (Figure 3). The decomposition of $service\_M2M1$ is similar to that of $service\_M1M2$.

Figure 3: The facilities manager's hierarchical plan

The parts must be ``available'' on the space-limited shop floor in order for an agent to use them. Whenever an agent moves or uses a part, it becomes unavailable. The inventory manager's goal is just to move part C to the dock and move D and E into bins on the shop floor (shown in Figure 4).

Figure 4: The inventory manager's hierarchical plan

To accelerate the coordination of their plans, each factory manager can analyze his hierarchical plan to derive summary information on how each abstract plan operator can affect the world. This information includes the summary pre-, post-, and in-conditions that intuitively correspond to the externally required preconditions, externally effective postconditions, and the internally required conditions, respectively, of the plan based on its potential refinements. Summary conditions augment state conditions with modal information about whether the conditions must or may hold and when they are in effect. Examples are given at the end of Section 3.2.

Once summary information is computed, the production and inventory managers each could send this information for their top-level plan to the facilities manager. The facilities manager could then reason about the top-level summary information for each of their plans to determine that if the facilities manager serviced all of the machines before the production manager started producing parts, and the production manager finished before the inventory manager began moving parts on and off the dock, then all of their plans can be executed (refined) in any way, or $CanAnyWay$. Then the facilities manager could instruct the others to add communication actions to their plans so that they synchronize their actions appropriately.

This top-level solution maximizes robustness in that the choices in the production and facilities managers' plans are preserved, but the solution is inefficient because there is no concurrent activity--only one manager is executing its plan at any time. The production manager might not want to wait for the facilities manager to finish maintenance and could negotiate for a solution with more concurrency. In that case, the facilities manager could determine that they could not overlap their plans in any way without risking conflict ($\neg CanAnyWay$). However, the summary information could tell them that there might be some way to overlap their plans ($MightSomeWay$), suggesting that a search for a solution with more concurrency (at the cost of perhaps committing to specific refinement choices) has hope of success. In this case, the facilities manager could request the production manager for the summary information of each of $produce\_H$'s subplans, reason about the interactions of lower level actions in the same way, and find a way to synchronize the subplans for a more fine-grained solution where the plans are executed more concurrently. We give an algorithm for finding such solutions in Section 5.