Local search has a long tradition in combinatorial optimization [1,64]. Local improvement ideas have found application in many domains. Some of the general work most relevant to PbR is on constraint satisfaction, scheduling, satisfiability testing, and heuristic search.
In constraint satisfaction, local search techniques have been able to solve problems orders of magnitude more complex than the respective complete (backtracking) approaches. Minton et al. [58,56] developed a simple repair heuristic, min-conflicts, that could solve large constraint satisfaction and scheduling problems, such as the scheduling of operations in the Hubble Space Telescope. The min-conflicts heuristic just selects the variable value assignment that minimizes the number of constraints violated. This heuristic was used as the cost function of a gradient-descent search and also in an informed backtracking search.
In satisfiability testing a similar method, GSAT, was introduced by Selman, Levesque, & Mitchell [75]. GSAT solves hard satisfiability problems using local search where the repairs consist in changing the truth value of a randomly chosen variable. The cost function is the number of clauses satisfied by the current truth assignment. Their approach scales much better than the corresponding complete method (the Davis-Putnam procedure).
In work on scheduling and rescheduling, Zweben, Daun, & Deale [85] define a set of general, but fixed, repair methods, and use simulated annealing to search the space of schedules. Our plans are networks of actions as opposed to their metric-time totally-ordered tasks. Also we can easily specify different rewriting rules (general or specific) to suit each domain, as opposed to their fixed strategies.
Our work is inspired by these approaches but there are several differences. First, PbR operates on complex graph structures (partial-order plans) as opposed to variable assignments. Second, our repairs are declaratively specified and may be changed for each problem domain, as opposed to their general but fixed repair strategies. Third, PbR accepts arbitrary measures of quality, not just constraint violations as in min-conflicts, or number of unsatisfied clauses as GSAT. Finally, PbR searches the space of valid solution plans, as opposed to the space of variable assignments which may be internally inconsistent.
Iterative repair ideas have also been used in heuristic search. Ratner & Pohl [67] present a two-phase approach similar to PbR. In the first phase, they find an initial valid sequence of operators using an approximation algorithm. In the second phase, they perform local search starting from that initial sequence. The cost function is the plan length. The local neighborhood is generated by identifying segments in the current solution sequence and attempting to optimize them. The repair consists of a heuristic search with the initial state being the beginning of the segment and the goal the end of the segment. If a shorter path is found, the original sequence is replaced by the new shorter segment. A significant difference with PbR is that they are doing a state-space search, while PbR is doing a plan-space search. The least-committed partial-order nature of PbR allows it to optimize the plans in ways that cannot be achieved by optimizing linear subsequences.