examples of non-chronological search

[Don Smith]

Good morning,

Fergus wrote:
>I think it would be helpful if someone could give a pointer to one or
>two examples of constraint-based applications for which chronological
>backtracking is not appropriate.

References at end.

Last time I looked (about a year ago!), two of the fastest methods for 
solving SAT problems were:  walksat and relevance-bounded-learning.   

Walksat and the older gsat use local greedy search with noise.  They're 
based on variations of the following algorithm, related to simulated 
annealing.

LOOP FOREVER
  Choose a RANDOM assignment of true/false to the propositional variables
  FOR (j=1 to MAX_ITERATIONS)
     if the current assignment satisfies all clauses
         RETURN the assignment  /* (hurray!) */
 /* At this point we could just flip that variable which results
    in the best improvement in the number of satisfied clauses.
    But if we did only that, we'd likely get caught in a local maximum.
  */

     With probabilty p  
         Randomly choose an unsatisfied clause, and flip that 
         variable appearing in it that leads to the best overall 
         improvement in the number of satisfied clauses.
     With probabilty 1-p  
         Make a random choice of variable to flip.
   END FOR
END LOOP
		
(I'm doing this mostly from memory, so the above may not be exact.)
Kautz and Selman showed that wsat beats the pants off many other
search techniques (including chronological backtracking and
forward checking) -- at least for applications in which the
density of solutions was rather high. (That is, as long
as you're not trying to find the optimum solution, there
will be many solutions, and so stochastic greedy search is likely to
come close to one.)
   
Relevance bounded learning is described in Bayardo & Schrag, "Using 
CSP Look-Back Techniques to Solve Real-World SAT Instances". AAAI-97.
The authors showed that it was competitive with/better than wsat
on some instances.   It  uses conflicted-directed-backjumping,
and to avoid storing an unlimited number of nogoods, it deletes
old nogoods that are no longer relevant, as measured by the number
of variables still having their old values.

As Pascal Van Hentenryck showed in his book "Constraint Satisfaction 
in Logic Programming", solving n-queens with forward checking is
much faster (orders of magnitude even for small n, I believe) than 
solving it with chronological backtracking.   But forward checking
(or arc consistency or path consistency) is not inconsistent with
chronological backtracking: finite domain CLP uses forward checking.
Backjumping and its variations require major modifications.

Some other AI search techniques not based on chronological backtracking
are backjumping, dynamic backtracking,  genetic algoritms, 
simulated annealing, iterative sampling (ISAMP), and LDS (limited 
discrepancy search).

BTW, stochastic search is related to committed choice nondeterminism!
Choose a candidate (maybe randomly) and do _some_ (not systematic)
search.   Systematic search is impossible on most real problems.
Someone -- I don't know who -- said, "Search and you're dead."

For scheduling applications such as bin packing, and for solving 
Traveling Salesman Problems (TSPs), again stochastic search with local
optimization steps seem to be best.  Chronological backtracking would
be hopelessly inefficient.  David Johnson (half of Garey and Johnson)
has a long, clear, technical article describing heuristics for TSP.  

   Don

@inproceedings{gsat,
Author = "B. Selman and H. Levesque and D. Mitchell",
Title  = "A New Method for Solving Hard Satisfiability Problems",
Year = "1992",
Booktitle = {Proceedings of AAAI-92},
pages = {440-446}
   	}

@inproceedings{wsat,
Author = "H. Kautz and B. Selman",
Title  = "Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search",
Year = "1996",
Booktitle = {Proceedings of the Natinal Conference on Artificial Intelligence},
pages = {1194-1201}
   	}

@inproceedings{ISAMP,
Author = "J. Crawford and A. Baker",
Title  = "Experimental Results on the Application of Satisfiability Algorithms to
Scheduling Problems",
Year = "1994",
Booktitle = {AAAI-94}
   	}

Bayardo & Schrag, "Using CSP Look-Back Techniques to Solve Real-World 
SAT Instances". AAAI-97.


     P. Prosser "Hybrid algorithms for the constraint satisfaction
     problem", to appear in Computational Intelligence 9(3), 
     Autumn 1993 (previously technical report AISL-46-91)

     P. Prosser "BM+BJ=BMJ" Proc CAIA-93, 257-262

     P. Prosser "Domain filtering can degrade intelligent
     backjumping search" to appear in Proc IJCAI-93

     P. Prosser "Forward checking with backmarking" Technical
     Report AISL-48-93, Dept CS, Univ Strathclyde, Scotland