Method for representing a directed acyclic graph of worlds using an assumption-based truth maintenance system

• US 4,918,621 A
• Filed: 12/13/1988
• Issued: 04/17/1990
• Est. Priority Date: 08/13/1986
• Status: Expired due to Term

• Current Assignee: Intellicorp Incorporated
• Original Assignee: Intellicorp Incorporated
• Inventors: Nado, Robert A., Morris, Paul H.
• Primary Examiner(s): MacDonald, Allen
• Application Number:
  US07/285,323
• Time in Patent Office: 490 Days
• Field of Search: 364/513, 364/300, 364/200 MS File, 364/900 MS File
• US Class Current: 706/51
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models

Abstract

In artificial intelligence, a method is provided for representing a directed acyclic graph of worlds using an assumption-based truth maintenance system (ATMS) as a tool. The invention introduces the concepts of a nondeletion assumption and a deletion nogood, in order to allow deletion of an assertion upon transition between worlds. The traditional (de Kleer) ATMS tool is augmented to allow distinction between two kinds of assumptions, namely the nondeletion assumption and the world assumption. The nondeletion assumption is the elementary stipulation indicating the presence of an added assertion in a world. The world assumption is the elementary stipulation representing existence of a world. According to the invention, a method for testing assertions is provided for determining whether an assertion holds in a world. The method involves taking into account the presence of deletion nogoods relevant to the tested assertion. A deletion nogood is a nogood which indicates the contradiction between a world assumption and a nondeletion assumption which arises from a deletion of an assertion. Deletion nogoods are introduced at a world to block any further inheritance of an assertion from an ancestor world. The ATMS tool is further modified by replacing the traditional ATMS notion of inconsistency with a concept of inconsistency wherein only world assumptions are blamed for inconsistencies. The present invention may be used in connection with planning systems and diagnosis systems as well as with other types of knowledge-based systems.

Claims

1. In an artificial intelligence worlds mechanism implemented on a computer system, said worlds mechanism containing a graph of worlds, each one of said worlds having associated therewith a first set of assertions, said first set of assertions being determined from a second set of assertions inherited from ancestor worlds together with additions and deletions specific to each one of said worlds, and each said world having a method for testing if an assertion is properly within said first set of assertions, a method for creating worlds comprising:

creating a graph of worlds by employing an assumption-basedtruth maintenance system (ATMS), said ATMS comprising in combination an ATMS tool for carrying out ATMS procedures and an ATMS database comprising a collection of assumptions; and

thereafter

constructing justifications between said worlds by means of said ATMS, wherein a justification is a data structure representing derivation steps linking an assertion with other assertions and/or assumptions such that assertions and/or assumptions are in a conditions so they can be arbitrarily deleted.

2. The method according to claim 1 wherein said graph of worlds includes world assumptions and world assertions and wherein said justifications constructing step comprises constructing justifications between said world assumptions and said world assertions.

3. In an artificial intelligence worlds mechanism implemented on a computer system, said worlds mechanism containing a graph of worlds, each one of said worlds having associated therewith a first set of assertions, a world assumption comprising an assumption about a world and a world environment comprising an environment for a world, said first set of assertions being determined from a second set of assertions inherited from ancestor worlds together with additions and deletions specific to each one of said worlds, and each said world having a method for testing if an assertion is properly within said first set of assertions, said world mechanism employing an assumption-based truth maintenance system (ATMS), said ATMS comprising in combination an ATMS tool for carrying out ATMS procedures and an ATMS database comprising a collection of assumptions, to create a graph of worlds and to effect additions and deletions of assertions and wherein an assertion has been added after creation of said each said world, a method for providing for deletion of an assertion at another world comprising:

creating a distinct nondeletion assumption for each said added assertion at each world where an assertion has been added; and

thereafter

constructing a justification from the world assertion of said each said world and said distinct nondeletion assumption to said assertion to be deleted so that said assertion to be deleted can be arbitrarily deleted.

4. A method according to claim 3 further for deleting an added assertion comprising:

thereafter supplying from said world environment to the ATMS a justification from the world assumption and the nondeletion assumption to a "false"-type assertion in order to cause the ATMS tool to update the ATMS database; and

only thereafter deleting said added assertion.

5. A method according to claim 4 further for determining if a nondeletion assumption is relevant to deletion of an added assertion comprising:

thereafter testing whether an adding world corresponding to said nondeletion assumption is an ancestor of the deleting world of said deletion.

6. A method according to claim 4 further for determining if a nondeletion assumption is relevant to deletion of an added assertion comprising thereafter:

testing whether an adding world corresponding to said nondeletion assumption is not an ancestor of the deleting world of said deletion;

testing whether said adding world is not said deleting world;

testing whether said adding world is not a descendant of said deleting world; and

testing whether a pessimistic merge is in effect, a pessimistic merge being a merge in which an assertion is inherited from an ancestor world unless there has been some deletion of said assertion by an ancestor of said adding world.

7. In an artificial intelligence worlds mechanism implemented on a computer system, said worlds mechanism containing a graph of world, each one of said worlds having associated therewith a first set of assertions, said first set of assertions being determined from a second set of assertions inherited from ancestor worlds and from additions and deletions specific to each one of said worlds, and each said world having a method for testing if an assertion is properly within said first set of assertions, a method for representing a directed acyclic graph of worlds comprising:

constructing a link between assumption-based truth maintenance system (ATMS) assumption and each said world, wherein an ATMS assumption is an elementary stipulation of an assumption-based truth maintenance system; and

thereafter constructing a connection between an ATMS environment and each said world, wherein said ATMS environment comprises said ATMS assumption of said each said world and said ATMS assumptions of all ancestor worlds of said each said world.

8. In an artificial intelligence worlds mechanism implemented on a computer system, said worlds mechanism containing a graph of worlds, said mechanism employing an assumption-based truth maintenance system (ATMS) to create a graph of worlds and to effect additions and deletions of assertions, wherein said ATMS comprises an ATMS tool for performing ATMS procedures and an ATMS data base, said ATMS data base comprising assertions, and a "false"-type assertion, each assertion having a label, wherein a label consists of zero, one or a plurality of assertion environments, an assertion environment providing a mechanism for associating said each assertion with a world, said assertion environment consisting of world assumptions and nondeletion assumptions, wherein an assumption is an elementary stipulation, a world assumption is an elementary stipulation of existence of a world and a nondeletion assumption is an elementary stipulationn of the presence of an assertion in a world, said "false"-type assertion having a label consisting environments called nogoods, nogoods being minimal inconsistent sets of assumptions, one type of nogood being a deletion nogood, a deletion nogood consisting of only one nondeletion assumption and either none or one world assumption, a method for testing a specific assertion at said each said world comprising:

for each environment in said label of said specific assertion,

determining if all said world assumptions of said specific assertion are present in said world environment by comparing said world assumptions of said specific assertion with said world assumptions of said world environment; and

thereafter determining if nondeletion assumptions are not in any deletion nogood with world assumptions said world environment by comparing said nondeletion assumptions of said specific assertion with the nondeletion assumption in each said deletion nogood while comping said world assumptions in said world environment with world assumption in said deletion nogood.

9. In an artificial intelligence worlds mechanism implemented on a computer system, said worlds mechanism containing a graph of worlds, said worlds mechanism employing an assumption-based truth maintenance system (ATMS) to create a graph of worlds and to effect additions and deletions of assertions, wherein said ATMS comprises an ATMS tool for performing ATMS procedures and an ATMS data base, said ATMS data base comprising assertions, and a "false"-type assertion, a world having an assertion with a label, wherein a label consists of zero, one or a plurality of environments, a method for determining if said world is internally consistent comprising:

removing environments from the label of said world upon derivation of said "false"-type assertion in said world; and

thereafter determining if any environments are present in said label of said world by examining the label of the world assertion of said world.

10. In an artificial intelligence worlds mechanism containing a graph of worlds, said worlds mechanism implemented on a computer system, said worlds mechanism employing an assumption-based truth maintenance system (ATMS) to create a graph of worlds and to effect additions and deletions of assertions, wherein said ATMS comprises an ATMS tool for performing ATMS procedures and an ATMS data base, said ATMS data base comprising assertions, and a "false"-type assertion, each assertion having a label, wherein a label consists of zero, one or a plurality of assertion environments, an assertion environment providing a mechanism for associating said each assertion with a world, said assertion environment consisting of world assumptions and nondeletion assumptions, wherein an assumption is an elementary stipulation, a world assumption is an elementary stipulation of existence of a world and a nondeletion assumption is an elementary stipulation of the presence of an assertion in a world, said "false"-type assertion having a label consisting environments called nogoods, nogoods being minimal inconsistent sets of assumptions, one type of nogood being a deletion nogood, a deletion nogood consisting of only one nondeletion assumption and either none or one world assumption, a method for determining if said world is internally consistent comprising:

removing environments from the label of said world upon derivation of said "false"-type assertion in said world by applying a feedback procedure, said feedback procedure comprising;

filtering said nogoods other than said deletion nogoods in said label of said "false"-type assertion for world assumptions and thereafter adding to said ATMS data base a justification from said world assumptions to said "false"-type assertion to cause said ATMS tool to generate nogoods containing only world assumptions,

which in turn

causes said ATMS tool to remove environments from said label; and

thereafter

determining if any environments are present in said label of said world by examining the label of the world assertion of said world.