Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!decvax!ucbvax!MCC.COM!AI.PETRIE
From: AI.PETRIE@MCC.COM (Charles Petrie)
Newsgroups: mod.ai
Subject: TMS Query Response
Message-ID: <12242874895.16.AI.PETRIE@MCC.COM>
Date: Mon, 29-Sep-86 16:40:24 EDT
Article-I.D.: MCC.12242874895.16.AI.PETRIE
Posted: Mon Sep 29 16:40:24 1986
Date-Received: Mon, 6-Oct-86 05:58:06 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Petrie@MCC
Organization: The ARPA Internet
Lines: 50
Approved: ailist@sri-stripe.arpa

More detail on Don Rose's TMS query:
 
  Does anyone know whether the standard algorithms for belief revision
  (e.g. dependency-directed backtracking in TMS-like systems) are
  guaranteed to halt?  That is, is it possible for certain belief networks 
  to be arranged such that no set of mutually consistent beliefs can be found
  (without outside influence)? 

There are at least three distinct Doyle-style algorithms. Doyle's doesn't
terminate on unsatisfiable cicularities.  James Goodwin's algorithm
does.  This algorithm is proved correct in "An Improved Algorithm for
Non-monotonic Dependency Net Update", LITH-MAT-R-82-23, Linkoping
Institute of Technology. David Russinoff's algorithm not only halts
given an unsatisfiable circularity, but is guaranteed to find a
well-founded, consistent set of status assignments, even if there are
odd loops, if such a set is possible. There are dependency nets for
which Russinoff's algorithm will properly assign statuses and Goodwin's
may not.  An example and proof of correctness for this algorithm is
given in "An Algorithm for Truth Maintenance", AI-068-85,
Microelectronics and Computer Technology Corporation.  Also, Doyle made
the claim that an unsatisfiable circularity can be detected if a node is
its own ancestor after finding a valid justification with a NIL status
in the Outlist. Detection of unsatisfiable circularities turns out to be
more difficult than this. This is noted in "A Diffusing Computation for
Truth Maintenance" wherein I give a distributed computation for status
assignment (published in the Proc. 1986 Internat. Conf. on Parallel
Processing, IEEE) that halts on unsatisfiable circularities. 

The term "unsatisfiable circularity" was introduced by Doyle and refers
to a dependency network that has no correct status labeling.  The term
"odd loop" was introduced by Charniak, Riesbeck, and McDermott in
section 16.7 of "Artificial Intelligence Programming".  An equivalent
definition is given by Goodwin.  In both, an odd loop refers to a
particular circular path in a dependency net.  As Goodwin notes, such
odd loops are a necessary, but not sufficient, condition for an unsatisfiable
circularity.

All of the algorithms mentioned above are for finding a proper set of
status assignments for a dependency network.  A distinct issue is the
avoidance of the creation of odd loops, which may introduce
unsatisfiable circularities, by Doyle-style dependency-directed
backtracking.  Examples of creation of such odd loops and algorithms to
avoid such are described in my technical reports on DDB. Michael
Reinfrank's report on the KAPRI system also notes the possibility of
odd loops created by DDB. (DDB references on request to avoid an even
longer note.)

Charles Petrie
PETRIE@MCC
-------