next up previous
Next: 2.3 Local Search in Combinatorial Optimization Up: 2 Preliminaries: Planning, Rewriting, and Local Search Previous: 2.1 AI Planning

2.2 Rewriting

Plan rewriting in PbR is related to term and graph rewriting. Term rewriting originated in the context of equational theories and reduction to normal forms as an effective way to perform deduction [8,9]. A rewrite system is specified as a set of rules. Each rule corresponds to a preferred direction of an equivalence theorem. The main issue in term rewriting systems is convergence, that is, if two arbitrary terms can be rewritten in a finite number of steps into a unique normal form. In PbR two plans are considered ``equivalent'' if they are solutions to the same problem, although they may differ on their cost or operators (that is, they are ``equivalent'' with respect to ``satisfiability'' as introduced above). However, we are not interested in using the rewriting rules to prove such ``equivalence''. Instead, our framework uses the rewriting rules to explore the space of solution plans.

Graph rewriting, akin to term rewriting, refers to the process of replacing a subgraph of a given graph, when some conditions are satisfied, by another subgraph. Graph rewriting has found broad applications, such as very high-level programming languages, database data description and query languages, etc. Schürr [73] presents a good survey. The main drawback of general graph rewriting is its complexity. Because graph matching can be reduced to (sub)graph isomorphism the problem is NP-complete. Nevertheless, under some restrictions graph rewriting can be performed efficiently [25].

Planning by Rewriting adapts general graph rewriting to the semantics of partial-order planning with a STRIPS-like operator representation. A plan-rewriting rule in PbR specifies the replacement, under certain conditions, of a subplan by another subplan. However, in our formalism the rule does not need to specify the completely detailed embedding of the consequent as in graph rewriting systems. The consistent embeddings of the rule consequent, with the generation of edges if necessary, are automatically computed according to the semantics of partial-order planning. Our algorithm ensures that the rewritten plans always remain valid (Section 3.1.3). The plan-rewriting rules are intended to explore the space of solution plans to reach high-quality plans.


next up previous
Next: 2.3 Local Search in Combinatorial Optimization Up: 2 Preliminaries: Planning, Rewriting, and Local Search Previous: 2.1 AI Planning
Jose-Luis Ambite 2001-08-09