Reasoning
Complementing general questions of how to represent knowledge is the
need to understand how knowledge can be used. In general,
realistic problems have enormous associated spaces of possible
solutions which must be explored (searched) to find an actual solution that
meets the requirements of the problem. These spaces are much too
large to be searched in their entirety, and ways must be found to
focus or short-circuit the search for solutions if systems are to have
any practical utility.
Put another way, almost every interesting problem class is
computationally intractable (NP-complete or worse), meaning that in
the worst case problems may take time exponential in the problem size
to solve.
Important questions include ways to reduce problem size and to focus
search, and techniques for finding approximate solutions quickly.
CIRL
CIRL is working on reasoning on many fronts, including systematic and nonsystematic search and polytime
limited reasoning methods. An
important focus of our work is how KR systems can be made to be usable
for solving real problems, for example by exploiting structure in the problems themselves or
in the associated solution space.
Pointers
Subareas:
Search
Tractable Reasoning
Back to the CIRL Overview Page.