5.1 Top-Down Hierarchical Planning and Coordination

The formalism of summary conditions culminated in Section 4 in algorithms that determine if a set of plans (abstract or primitive) under a partial set of ordering constraints is definitely conflict-free ($CanAnyWay$) or has unresolvable conflicts ($\neg MightSomeWay$). Here we integrate these algorithms into one that searches for a consistent plan for one or more agents. The particular algorithm we describe here is shown to be sound and complete [Clement, 2002]. The search starts out with the top-level plans of each agent. A solution is one where there are no possible conflicts among the agents' plans. The algorithm tries to find a solution at this top level and then expands the hierarchies deeper and deeper until the optimal solution is found or the search space has been exhausted. A pseudocode description of the algorithm is given in Figure 16.

A state of the search is a partially elaborated plan that we represent as a set of $and$ plans (one for each agent), a set of temporal constraints, and a set of blocked plans. The subplans of the $and$ plans are the leaves of the partially expanded hierarchies of the agents. The set of temporal constraints includes synchronization constraints added during the search in addition to those dictated by the agents' individual hierarchical plans. Blocked subplans keep track of pruned $or$ subplans.

Decisions can be made during search in a decentralized fashion. The agents can negotiate over ordering constraints to adopt, over choices of subplans to accomplish higher level plans, and over which decompositions to explore first. While the algorithm described here does not specify (or commit to) any negotiation technique, it does provide the mechanisms for identifying the choices over which the agents can negotiate. Although agents can make search decisions in a decentralized fashion, we describe the algorithm given here as a centralized process that requests summary information from the agents being coordinated.

In the pseudocode in Figure 16, the coordinating agent collects summary information about the other agents' plans as it decomposes them. The $queue$ keeps track of expanded search states. If the $CanAnyWay$ relation holds for the search state, the Dominates function determines if the current solutions are better for every agent than the solution represented by the current search state and keeps it if the solution is not dominated. If $MightSomeWay$ is false, then the search space rooted at the current search state can be pruned; otherwise, the coordinator applies operators to generate new search states.

The operators for generating successor search states are expanding non-primitive plans, blocking $or$ subplans, and adding temporal constraints on pairs of plans. When an agent expands one of its plans, each of the plan's summary conditions are replaced with only the original conditions of the parent plan. Then the subplans' summary information and ordering constraints are added to the search state. A subplan of an $or$ plan is added (or selected) only when all other subplans are blocked. When ApplyOperator is called for the select and block operators, search states are generated for each selectable and blockable subplan, respectively. Blocking an $or$ subplan can be effective in resolving a constraint in which the other $or$ subplans are not involved. For example, if the inventory manager plans to only use transport2, the production manager could block subplans using transport2, leaving subplans using transport1 that do not conflict with the inventory manager's plan. This can lead to least commitment abstract solutions that leave the agents flexibility in selecting among the multiple applicable remaining subplans. The agents can take another approach by selecting a subplan (effectively blocking all of the others) to investigate a preferred choice or one that more likely avoids conflicts.

When the operator is to add a temporal constraint, a new search state is created for each alternative temporal constraint that could be added. These successor states are enqueued so that if backtracking is needed, each alternative can be tried. Adding temporal constraints should only generate new search states when the ordering is consistent with the other global and local constraints. In our implementation, we only add constraints that will help resolve threats as determined by the must/may achieves and clobbers algorithms. When a plan is expanded or selected, the ordering constraints must be updated for the subplans that are added.

Figure 16: A concurrent hierarchical coordination algorithm.

The soundness and completeness of the coordination algorithm depends on the soundness and completeness of identifying solutions and the complete exploration of the search space. Soundness and completeness is not defined with respect to achieving particular goal predicates but resolving conflicts in the plan hierarchies. A domain modeler may represent goals as abstract CHiPs that decompose into possible plans that accomplish them or as a series of actions for an agent to execute successfully.

Consider how the algorithm would find coordinated plans for the manufacturing agents. At the beginning of the search, a coordinating agent gathers the summary information for the top-level plans of the three agents in $plans$. At first, there are no ordering constraints, so $order$ is empty in the first search state (shown in Figure 13a) popped from the $queue$. $CanAnyWay$ is false, and $MightSomeWay$ is true for this state as described earlier in this section, so the coordinator chooses an $operator$ to apply to the search state. It could choose constrain and order the $maintenance$ plan before $produce\_H$ to resolve all conflicts between those two plans. The $order$ is updated with the new constraint, and the new search state is inserted into the $queue$ by according to some ranking function. On the next iteration of the loop, the only search state in the queue that was just inserted is popped. The coordinator again finds that $CanAnyWay$ is false, and $MightSomeWay$ is true since $move\_parts$ may still conflict with other plans over the use of transports. It can choose to constrain $produce\_H$ before $move\_parts$ to resolve the remaining conflicts. This is detected on the next cycle of the search loop where $CanAnyWay$ is found to be true for this search state (shown in Figure 13b). The $plans$, the two constraints in $order$, and the empty set of blocked plans are added as a solution since there is no previously found solution that Dominates it. The Dominates function uses domain specific criteria for determining when a solution has value as an alternative and should be kept or is inferior compared to another and should be dropped. In this manufacturing domain, one solution dominates another if the finish time for at least one agent is earlier and no finish times are later for any agents. The search then continues to find alternative or superior solutions, although the agents may decide to terminate the search in the interest of time.