Nonlinear problem solving using intelligent casual-commitment

Abstract: "Complex interactions among conjunctive (simultaneous) goals motivate the need for nonlinear planners. Whereas the literature addresses least-commitment approaches that require breadth-first search and theorem proving style-reasoning to seek a possible answer, we advocate a casual-commitment approach that finds viable plans incrementally. In essence, all decision points (operator selections, goal orderings, backtracking points, etc.) are open to introspection and reconsideration.However, in the presence of background knowledge--heuristic or definitive--only the most promising parts of the search space will be explored in satisficing mode to produce a solution plan efficiently. In the limiting case, however, casual commitment can backtrack, explore the entire space subsuming all goal orderings, and generate partial orders guaranteeing synthesis of all possible plans including the optimal one. This paper reports on the full implementation of the efficient, casual-commitment nonlinear problem solver of the PRODIGY architecture. The principles of nonlinear planning are discussed, the algorithms in the implementation are described in some detail, and the use of knowledge (if present) to focus search is considered."