5.2 Search Techniques and Heuristics

Although summary information is valuable for finding conflict free or coordinated plans at abstract levels, this information can also be valuable in directing the search to avoid branches in the search space that lead to inconsistent or suboptimal coordinated plans. A coordinator can prune away inconsistent coordinated plans at the abstract level by doing a quick check to see if $MightSomeWay$ is false. For example, if the search somehow reached the state shown in Figure 8b, the coordinator could backtrack before expanding the hierarchies further and avoid reasoning about details of the plans where they must fail.

Another strategy is to first expand plans involved in the most threats. For the sake of completeness, the order of plan expansions does not matter as long as they are all expanded at some point when the search trail cannot be pruned. But, employing this ``expand on most threats first'' (EMTF) heuristic aims at driving the search down through the hierarchy to find the subplan(s) causing conflicts with others so that they can be resolved more quickly. This is similar to a most-constrained variable heuristic often employed in constraint satisfaction problems. For example, if the facilities and inventory managers wished to execute their plans concurrently as shown in Figure 17a, at the most abstract level, the coordinator would find that there are conflicts over the use of transports for moving parts. Instead of decomposing $produce\_H$ and reasoning about plan details where there are no conflicts, the EMTF heuristic would choose to decompose either $maintenance$ or $move\_parts$ which have the most conflicts. By decomposing $maintenance$ the agents can resolve the remaining conflicts and still execute concurrently.

Figure 17: EMTF heuristic resolving conflicts by decomposing the $maintenance$ plan

Another heuristic that a coordinator can use in parallel with EMTF is ``choose fewest threats first'' (CFTF). Here the search orders states in the search queue by ascending numbers of threats left to resolve. In effect, this is a least-constraining value heuristic used in constraint satisfaction approaches. As mentioned in Section 4.1, threats are identified by the $CanAnyWay$ algorithm. By trying to resolve the threats of coordinated plan search states with fewer conflicts, it is hoped that solutions can be found more quickly. So, EMTF is a heuristic for ordering $and$ subplans to expand, and CFTF, in effect, orders $or$ subplan choices. For example, if the production manager chooses to use machine M1 instead of M2 to produce G, the coordinator is likely closer to a solution because there are fewer conflicts to resolve. This heuristic can be applied not only to selecting $or$ subplan choices but also to choosing temporal constraints and variable bindings or any search operator from the entire set of operators.

In addition, in trying to find optimal solutions in the style of a branch-and-bound search, the coordinator can use the cost of abstract solutions to prune away branches of the search space whose minimum cost is greater than the maximum cost of the current best solution. This is the role of the Dominates function in the description of the coordination algorithm in Section 5.1. This usually assumes that cost/utility information is decomposable over the hierarchy of actions, or the cost of any abstract action is a function of its decompositions.