Systematic Search Methods

When faced with a difficult search problem, there are two approaches that can be used. In a "systematic" approach, all possible solutions are either eliminated inferentially or examined explicitly. In a nonsystematic or "local" approach, a variety of solutions are examined but there is no guarantee that every possibility will eventually be considered.

Both methods have advantages and disadvantages. Local search is often faster when it manages to find an answer, but it doesn't always do so. Systematic methods are guaranteed to find solutions when they exist, and can also report conclusively that no solution is possible.

CIRL

A substantial portion of CIRL's work on search focuses on systematic methods. This includes our experimental work on phase transitions, our discovery of relevance-bounded learning and dynamic backtracking, our attempts to generalize existing search engines to deal with pseudo-Boolean or lifted representations, and the development of new search algorithms like limited discrepancy search and weighted discrepancy search.

Parent areas:

Subareas:

Dynamic Backtracking and RELSAT

Adversary and partition search

Multi-Pass A*

Limited Discrepancy Search and WLDS

Procedural Reasoning

Back to the CIRL Overview Page.