AITEC Contract Research Projects in FY1997:Intermediate Report

1.Title of the Research Project, Principal Investigator

(1) Title of the Research Project

    Anytime Hypothetical Reasoning

(2) Principal Investigator

    Dr. Aditya Kumar Ghose, Professor, 
    University of Wollongong, Australia

2.Purpose of the research

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 [2] 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.

In the THEORIST system for hypothetical reasoning [16][15], a knowledge base 
is a triple (F, H, C) where F is a set of closed formulae representing the 
facts, H is a set of (not necessarily closed) formulae representing the 
hypotheses and C is another set of closed formulae representing the 
constraints.  A scenario is a set F ∪ h where h is a set of ground instances
of H such that F ∪ h ∪ C is consistent. We shall define an extension to be 
the deductive closure of a maximal (w.r.t. set inclusion) scenario. 

This project seeks to implement a hypothetical reasoning system which
supports anytime query processing. The proposed system will support the
following classes of queries:

   ●Explanation: Given an observation g, find a minimal scenario which 
     explains g (i.e. a minimal, w.r.t. set inclusion, F ∪ h such that F ∪ h
      g).
   ●Coherence: Compute an extension of a given knowledge base (F, H, C).
   ●Set-membership: Determine if a given formula φ is an element of any 
     extension of (F, H, C). 
   ●Set-entailment: Determine if a given formula φ is an element of all 
     extensions of (F, H, C). 

It will be possible to arbitrarily interrupt the system during the
processing of each of these queries to obtain partial solutions. The
quality of the solutions, obtained by applying solution quality metrics
defined for each class of queries, would improve in a well-defined
manner with the time available to compute the partial solutions.

3.Contents

(1)Current progress of the project

Progress has been made in the following three areas:

* Theoretical basis: Our efforts have focused on further elucidating the
theoretical basis of default abstraction - a prerequisite for the
implementation of abstraction-based strategies in Anytime THEORIST. 

* Implementation: The implementation of Anytime THEORIST has been
initiated and is proceeding well.

* Development of real-world test-bed: In parallel with the
implementation effort that constitutes part of this project, progress
has been made on a formal web query/information retrieval language that
permits the robust specification of complex queries. The implementation
of this querying/retrieval system would rely on the Anytime THEORIST 
system being developed for the this project and would thus serve as a 
useful test-bed for conducting realistic experiments. Preliminary
studies are also being conducted on using a real-time constraint-based 
scheduling system that relies on partial constraint satisfaction techniques 
as a test-bed, exploiting our earlier work on translations between partial
constraint satisfaction problems and hypothetical reasoning.

(2)Obtained research results 

(3)Planned schedule till the end of February 1998

Further work on default abstractions: 
December 1997.
Further work on real-world test-beds:
December 1997.
Anytime THEORIST implementation completed: 
February 1998.
Code, documentation and user manual of Anytime THEORIST delivered:
February 1998.

(4)Expected software by the end of February 1998

A complete prototype implementation of Anytime THEORIST, with the
functionality described in the original proposal.