Abstract
This paper presents an algebra for conflict resolution in nonlinear planning. A set of conflicts in a plan is considered as a constraint network. Each node in the network represents a conflict, and is associated with a set of alternative ways for resolving it. Thus, resolving conflicts in a plan corresponds to selecting a set of consistent resolution methods so that, after they are applied to the plan, every conflict can be removed. The paper discusses the representational issues related to the conflict resolution, presents an algebra for resolving conflicts, and illustrates that some modified algorithms for preprocessing networks of constraints can greatly enhance the efficiency of conflict resolution.
Introduction
In AI planning, a "conflict" typically arises when one action in a plan inadvertently undoes a condition required by another action—a scenario often referred to as the "clobberer" problem. For instance, if a plan requires painting a chair and then sitting on it, a conflict occurs if the sitting action is scheduled while the paint is still wet. Traditional nonlinear planners, such as TWEAK or SIPE, address these conflicts through branching: they attempt to reorder actions, modify variables, or insert new steps. However, as plan complexity increases, the number of potential resolutions grows exponentially, leading to a massive search space. Many planners either commit to a resolution prematurely or exhaustively search every branch, often wasting significant computational resources on redundant or logically impossible paths.
Methodology: Conflict Algebra and Constraint Networks
The proposed approach streamlines conflict resolution by treating it as a constraint satisfaction problem (CSP) and applying algebraic simplification. This involves two primary components:
- Conflict Algebra: The paper formalizes resolution methods using algebraic operations. It defines rules for subsumption (where one resolution is a stronger version of another) and inconsistency (where two resolutions are mutually exclusive). For example, if Resolution A implies Resolution B, then the conjunction of both is logically equivalent to just Resolution A.
- Modified CSP Algorithms: Conflicts are mapped onto a Constraint Network. While standard CSP algorithms focus on eliminating inconsistent values, this work introduces a modified "Path Consistency" algorithm designed to also remove redundant values.
The PP (Pre-Processing) algorithm is introduced to interleave inconsistency pruning with redundancy removal. If every resolution for Conflict A also resolves Conflict B, Conflict B is deemed redundant and pruned from the network. This process continues until the network reaches a stable, simplified state.
Theoretical Framework: Planning as CSP
A key insight of this research is viewing the meta-problem of conflict resolution itself as a CSP. Instead of merely searching for a plan, the system searches for a consistent set of "fixes" for a draft plan.
Central to this is the concept of subsumption. In planning, identifying what is unnecessary is as crucial as identifying what is impossible. If a specific ordering of tasks is already guaranteed by existing constraints, branching on that ordering is redundant. By applying algebraic rules—similar to Boolean algebra (e.g., $R_1 \cdot R_2 = R_1$ if $R_1$ subsumes $R_2$)—complex logical expressions of plan fixes can be collapsed into their simplest forms before the planner begins its search.
Results and Analysis
The effectiveness of this algebraic approach was demonstrated through a specific example involving a plan with multiple conflicts and operators. In this scenario, the algebraic preprocessing significantly reduced the number of backtracking points, for instance from six down to two in the paper's primary test case.
From a computational standpoint, the Pre-Processing (PP) algorithm has a worst-case complexity of $O(k^5n^3)$, where $n$ is the number of conflicts and $k$ is the number of resolution methods per conflict. Although this polynomial complexity might seem high, the reduction in the overall exponential search space of the planner typically justifies the preprocessing overhead. Furthermore, these modified CSP algorithms for redundancy removal are generalizable to any domain involving subsumption relations.
Conclusion
This paper introduces a formal algebraic framework to mitigate the search space explosion in nonlinear planning. By identifying and pruning redundant resolution paths early, the system can focus on the most critical constraints. Future work may involve exploring the trade-off between analysis time and search time to find an optimal balance, as well as extending the algebra to handle consumable resources like fuel or budget constraints.
Summary updated