Procedural Attachments in Search
In many search problems there are subproblems that can be solved in
polynomial time using special-purpose knowledge or methods.
Procedural attachment in reasoning allows these methods to be used
directly when searching, thus splitting the problem into polynomial
parts performed by the procedures, and a pure search part done by the
search engine(s).
CIRL
An important part of the CSP research at CIRL concerns this separation
of polynomial subproblems from the harder parts. This is evident in
our approach to scheduling problems, and in the work on formalizing
this separation. The formalization is based on the idea that
procedures can be viewed as functions from the set of partial
assignments to itself. This allows the procedures to be defined and
implemented independently of the search method being used.
Furthermore theoretical properties of solvers and procedures can be
proved.
Pointers
-
Procedural Reasoning in Constraint Satisfaction
-
This article introduces a simple, but powerful formalism for using
procedural calculations in search engines. Useful properties such as
completeness and systematicity are proven to hold for a large class of
search engines and procedures. Written by Ari Jonsson and
Matt Ginsberg and appeared in Proc. KR in 1996. Postscript document.
- Parent areas:
- Systematic Search
Back to the CIRL Overview Page.