Knowledge compilation improves search-intensive problem-solvers that are
easily specified but inefficient. One promising approach improves efficiency by constructing
a database of problem-instance/best-action pairs that replace problem-solving
search with efficient lookup. The database is constructed by reverse enumeration-
expanding the complete search space backwards, from the terminal problem
instances. This approach has been used successfully in counter-planning to construct
perfect problem-solvers for sub domains of chess and checkers. However, the
approach is limited to small problems because both the space needed to store the
database and the time needed to generate the database grow exponentially with
problem size.
This thesis addresses these problems through two mechanisms. First, the
space needed is reduced through an abstraction mechanism that is especially suited
to counter-planning domains. The search space is abstracted by representing problem
states as equivalence classes with respect to the goal achieved and the operators
as equivalence classes with respect to how they influence the goals. Second, the time
needed is reduced through a hueristic best-first control of the reverse enumeration.
Since with larger problems it may be impractical to run the compiler to completion,
the search is organized to optimize the tradeoff between the time spent compiling
a domain and the coverage achieved over that domain.
These two mechanisms are implemented in a system that has been applied to
problems in chess and checkers. Empirical results demonstrate both the strengths
and weaknesses of the approach. In most problems and 80/20 rule was demonstrated,
where a small number of patterns were identified early that covered most
of the domain, justifying the use of best-first search. In addition, the method was
able to automatically generate a set of abstract rules that had previously required
two person-months to hand engineer. / Graduation date: 1992
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/36260 |
| Date | 12 December 1991 |
| Creators | Flann, Nicholas S. |
| Contributors | Dietterich, Tom G. |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0017 seconds