[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publication: [PUBLink])

A key property of refinement search is that completeness can easily be realized. This is much harder to accomplish for local search, and mostly one cannot guarantee finding global optima or satisfying solutions. This also implies that proofs of global optima or inconsistency are beyond the reach of local search. Refinement search should therefore be the first choice for safety-critical problems.

Local search has other advantages. The production of a solution by refinement takes a lot of time, as a lot of labeling/propagation (and maybe backtracking) cycles have to be performed. In contrast, a local-search iteration can usually be computed very fast. This results in a temporally tight sequence of improvement steps, i.e., in an anytime behavior [PUBLink], and initial approximate results are computed much faster (see figure below). Later on, when the search gets more constrained (less options lead to an increase in the objective/cost function's value) and the probability that local search gets caught in local minima increases, superiority is reversed. This is also confirmed by a couple of empirical studies, which report that short time limits and large problems usually mean that local-search methods are significantly superior to complete refinement methods (e.g., [PUBLink] [PUBLink]).

A dynamic environment promotes local search as well because the search heuristics do not normally bother about modifications of the search space. This is different from complete methods, which have to update their memory of the already explored search space.

For a satisfaction task, local search's intermediate states are inconsistent. Thereby, local search is inherently a partial constraint satisfaction [PUBLink]. An extension of refinement search with partial constraint satisfaction is much less efficient because the search space grows enormously.

To sum up, the application of local search should be considered if the problem domain features

• short computation time limits
• only restricted claims on optimality/satisfaction
• dynamics
• large problems

This is definitely the case in EXCALIBUR's computer game environment, where the limited time available for AI computation (most of the CPU power is used for the game engine and graphics) and a complex and highly dynamic environment make reasoning properties like completeness and optimality only rough objectives to strive for. Furthermore, as argued in Section [Decision-Theoretic Planning], local-search techniques can better exploit plan-quality information for realistic problems that have more complex objective functions.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek