Dynamic Backtracking
In solving a search problem, it is important to remember which
possible solutions you've considered and which you haven't. By doing
so, you drastically reduce the number of possibilities you need to
consider in the future. This general technique is known as
"dependency maintenance" and, until recently, was of limited practical
value because there were simply too many possible dependencies to
maintain and use at each point in the search.
This technique has been made viable in practice by the introduction of
"dynamic backtracking," or "relevance-bounded learning." The basic
idea is to only store information about possible solutions that seem
likely to be considered later during the overall search; if a piece of
information seems unlikely to be useful later, it gets dropped.
Relevance-bounded learning is the technique of choice on a wide range
of problems of practical interest.
CIRL
Dynamic backtracking was invented at CIRL. It was renamed
relevance-bounded learning by Bayardo and Schrag (U Texas at Austin).
Pointers
-
Dynamic Backtracking.
- This article introduces dynamic backtracking, an intelligent
backtracking method, developed by Matt Ginsberg. Appeared in
JAIR 1993. Compressed postscript document.
- Parent areas:
- Systematic Methods
- Implementation:
- PLRS
Back to the CIRL Overview Page.