4.1 Threats on Summary Conditions

Agents can attempt to resolve conflicts among their plans by considering commitments to particular decompositions and ordering constraints. In order to do this, the agents must be able to identify remaining conflicts (threats) among their plans. Here we present simple algorithms for reasoning about threats between abstract plans and their required conditions.

Formally, for a set of CHiPs $P$ with ordering constraints $order$, a threat between an abstract plan $p\in P$ and a summary condition $c'$ of another plan $p'\in P$ exists iff $p$ may-clobber $c'$. We say that the threat is unresolvable if $p$ must-clobber $c'$ and $must(c')$ because there are no decomposition choices or ordering constraints that could be added to resolve the threat.

So, a simple algorithm for identifying threats is to check to see if each of the $O(nc)$ summary conditions of $n$ plans in $P_{sum}$ is must- or may-clobbered by any other plan. Since the complexity of checking to see if a particular condition is must- or may-clobbered is $O(nc)$, this algorithm's complexity is $O(n^2c^2)$.

In many coordination tasks, if agents could determine that under certain temporal constraints their plans can be decomposed in any way ($CanAnyWay$) or that under those constraints there is no way they can be successfully decomposed ($\neg MightSomeWay$), then they can make coordination decisions at abstract levels without entering a potentially costly search for valid plan merges at lower levels. Here are the formal definitions of $CanAnyWay$ and $MightSomeWay$:

Definition 13   $$\begin{array}{@{}l@{}l} [CanAnyWay&,MightSomeWay](order, P_{... ... \\ &[\forall, \exists] e \in E(h), succeeds(e,h) \end{array}$$

Definition 13 states that the plans with summary information $P_{sum}$ under ordering constraints can execute in any way if and only if all sets of plans $P$ that have summary information $P_{sum}$ will execute successfully in any history. $MightSomeWay$ is true if there is some set of plans that could possibly execute successfully. We could also describe $CanSomeWay(order$,$P_{sum})$ and $MightAnyWay(rel$,$P_{sum})$ in the same fashion, but it is not obvious how their addition could further influence search. Exploring these relations may be an interesting topic for future research.

In Figure 13a, the three top-level plans of the managers are unordered with respect to each other. The leaf plans of the partially expanded hierarchies comprise $P_{sum}$. Arrows represent the constraints in $order$. $CanAnyWay$({},{$produce\_G$, $maintenance$, $move\_parts$}) is false because there are several conflicts over the use of machines and transports that could occur for certain executions of the plans as described in Section 3.3 for Figure 8. However, $MightSomeWay$({}, {$produce\_G$, $maintenance$, $move\_parts$}) is true because the plans might in some way execute successfully as shown in Figure 13b. With the ordering constraints in Figure 13b, $CanAnyWay$({before(1,0), before(0,2)},{$produce\_G$, $maintenance$, $move\_parts$}) is true because the plans can execute in any way consistent with these ordering constraints without conflict. Figure 8b is an example where $MightSomeWay$ is false because $calibrate\_M2$ must-clobber the $available$(M2)MuF summary precondition of $build\_H$.

Figure 13: The top-level plans of each of the managers for the manufacturing domain

Figure 14: Algorithm determining whether plans with the given summary information CanAnyWay or MightSomeWay execute successfully.

As shown in Figure 14, the algorithm for determining $CanAnyWay$ for summary conditions is simple in that it only needs to check for threats. $MightSomeWay$ is more complicated because just checking for an unresolvable threat is not enough. As shown in Figure 15, it is not the case that plan $p$ must clobber $p'$ because $p''$ could come between and achieve the precondition $\ell$ of $p'$. Thus, $p$ may-clobbers $\ell$ in $p$ and in $p''$. However, obviously $p$ will clobber one or the other, so $MightSomeWay$ is false. In order to determine $MightSomeWay$ is $false$, an agent must exhaustively search through an exponential number of schedules to see if not all conflicts can be resolved. Instead of performing an exponential search to determine $MightSomeWay$, we use the simple algorithm in Figure 14 that just checks for must-clobber relationships. In Section 5.1 we describe a more flexible search to find conflict-free abstract plans than just scheduling at an abstract level.

Figure 15: $MightSomeWay$ is false even though there is no must-clobber relationship.

Thus, while the $CanAnyWay$ algorithm is sound and complete, the $MightSomeWay$ algorithm is complete but not sound. This also means that determining $\neg MightSomeWay$ is sound but not complete. We will still make use of both of these algorithms in a sound and complete planning/coordination algorithm in Section 5.1. The complexity of these algorithms is $O(n^2c^2)$ since the $O(nc)$ procedures for determining must/may-clobber must be run for each of $nc$ conditions ($c$ summary conditions in each of $n$ plans represented by $P_{sum}$).