The ADI Project: Anytime Default Inference
Department of Business
Systems, University of Wollongong
Project Outline
Default reasoning approaches play a fundamental role in
a
variety of knowledge
processing applications. Default
inference, is inherently computationally
hard and practical applications, especially time-bounded
ones, may require that some notion of approximate inference be used.
Any approximation algorithm must provide
useful partial results and the trade-offs involved must be clearly
identified.
Approximate default inference has received scant attention
in the literature. Notable exceptions include the work of Cadoli and
Schaerf in which they improve on the complexity of
reasoning with Reiter's default logic by using consequence relations
that are sound and incomplete in one case and complete but unsound in
the other), the recent results of Etherington and Crawford
involving using limited contexts and fast
incomplete consistency checks as well as the earlier work of Perlis.
Motivated by such deficiencies in the state-of-the-art,
this project seeks to develop a system for approximate default
inference by means of anytime algorithms.
Real-time algorithms are usually designed to satisfy a variety of
application-specific requirements:
some are required to provide partial,
but useful results whenever they are stopped while others have the
additional
requirement that their partial results improve with time. Anytime
algorithms are a useful conceptualization of processes that may be
prematurely terminated whenever necessary to return useful partial
answers, with the
quality of the answers improving in a well-defined manner with time.
Dean and Boddy
define an anytime algorithm to be one which:
- Lends itself to preemptive scheduling techniques.
- Can be terminated at any time and will give some meaningful
answer.
- Returns answers that improve in some well-behaved manner as a
function of
time.
The broad goals of this project are to define, implements and test
anytime algorithms for default inference.
This
paper discusses some of these issues in greater detail.
Funding
Post-Graduate Research Opportunities
Click here to
find out more about opportunities for research and post-graduate studies
related to this project.
Contact Information
Direct enquiries to
Dr. Aditya K. Ghose
.
|