Reasoning in Multiple Belief Spaces

1. Introduction

This paper reports a small feature of a large system, the MBR (Multiple Belief Reasoner> system [31 . MBR is fully implemented in Franz Lisp, running on a VAX-11/750. HBR is a reasoning system which allows multiple beliefs <beliefs from multiple agents, contradictory beliefs, hypothetical beliefs) to be ,represented 5imultaneously in the same knowledge base and performs reasoning within sets of these sets of beliefs. MBR also contains contradictions provisos and for for detecting recovering from

them.

The problem of detecting and recording contradictions has been considered by several researchers <e.g., [2, 4, 511. The part of HBR that deals with this problem differs from the previous approaches because, ll It is

· Current

address: Departamento de Engenharia Mecanica, Institute Superior Tecnico, Av . Rovisco Pais, 1000 Lisboa, Portugal

This work was supported in part by the National Science Foundation under Grant HCSS0-06314 and by the Institute Nacional de Investiga~&o Cientifica <Portugal) under Grant No.20536.

REASONING IN MULTIPLE BELIEF SPACES

Jo~o P. Martins· and Stuart C. Shapiro

Department of Computer Science State University of New York at Buffalo

Amherst, N.Y. 14226, U.S.A.

based on a logic developed for such purpose; 2> It is implemented such that the detection of the hypotheses underlying the contradiction is done by following only two types of arcs; there is no need to explicitly mark propositions as believed or disbelieved; there is no need to worry about circular proofs; there is no need to keep a separate data structure to record previous contradictions.

2. The SWM system

The SWM system is the logical system underlying HBR. It is loosely based on the logical systems of [ 1 J and [ 71. Uistinguishing features of SWM include recording dependencies of wffs, not allowing irrelevancies to be introduced, and providing for dealing with contradictions.

The SWM system deals with objects called supported wffs which are of the. form F:T,a,p, in which E is a wft, T <the origin tag> is an element of the set <hyp, der, ext>, a <the origin setl is a set of hypotheses, and p <the restriction set> is a set of sets of hypotheses. The origin ~ <OTl tells whether F is an hypotheses (T=hypl, a normally derived wtf (T=derl or a wtt with an extended OS <T=extl <this latter case Will not be discussed in this paper>. The origin set <OS> contains all the hypotheses which were actually used in the derivation of F. The restriction set <RSl contains sets ot hypotheses, each of which when unioned with the hypotheses in the OS forms a set which is known to he inconsistent. An inconsistent set, is a set of wtfs from which a contradiction may be derived .

RSs are very different entities from OTs and OSs . Whereas the OT and OS of a proposition reflect the way the proposition was derived, the RS of a proposition reflects the current knowledge about how the hypotheses underlying that proposition relate to the other hypotheses in the system. Once a proposition is

derived its OT and OS remain constant, whereas J.ts inconSJ.StenCJ.es system. RS are changes uncovered as in new the

3. Contexts and Belief Spaces

MBR is to be used as the deduction system in a knowledge base whJ.ch may contal.n J.nformatJ.on entered by many users, Wl.th dJ.tferent and even conflicting J.nterests. We assume that each user of the knowledge base has some basic set of belJ.ets Whl.ch he/she told MBR about. Such beliefs are the user's basJ.c assumptions and were entered into the knowledge base as hypotheses. Every proposition derived tram this set of assumptions l.S assumed to be be belJ.eved by the user.

We defJ.ne a context to be a set of hypotheses. A context represents the set of assumptl.ons of some user. A context determines a Belief Space IBSl which is the set of all the hypotheses defining the context and all the proposJ.tions whl.ch were derived from them. Within the SWM formalism lthe logic underlying MBRl, the proposJ.tions in a given BS are characterized by having an OS which is contal.ned l.n the context.

the set ot all At any point, hypotheses believed is context ICC!, which belief space ICBSl. termed the current defines the current

Contexts delimit smaller knowledge bases (called Belief Spaces> within the knowledge base. The knowledge base retrJ.eval operatl.ons . onl.y retrJ.eve propositions Wl.thin the CBS, ignoring other propositJ.ons. the all

4. The handling of contradictions

In this section, we will discuss how contradictions are handled by MBR.

MDR inferenc~ relies of on the SWM two that rules of handle contradictions: negation introduction I~I> and updating gf restriction sets IURSl.

The rule gf ~r states that from A:T,«,~ and ~A:~.~.e (meaning that from the hypotheses in au~ a contradiction, A&~A, can be derl.vedl we can deduce the negation ot the con)unction of any number of hypotheses in au~ under an OS containing the remaining hypotheses. The meaning of this newly derived wff is that such con)unction can not be considered under the assumption of the other hypotheses.

The rule of URS states that from A:T,a,~ and ~A:~.~.e we~ update the RS ot every hypothesis in Tu~ and of all the wtfs derived from them. This updatJ.ng has the effect of recordJ.ng the existence of the inconsistent set au~. Details of how thl.s is done can be found in [3!.

Based in these of inference, whenever two MBR rules tJ.nds a the contradiction it takes following actions: one ot

1. It only one of the contradictory wtfs belongs to the CBS the contradJ.ction l.S recorded (through the appll.catJ.on of URSl but nothJ.ng more happens. The effect of doJ.ng so is to record that some set of hypotheses, strictly containl.ng the CC, is now known to be J.nconsistent.
2. If both contradJ.ctory wtfs belong to the CBS. Then the rule ot URS is applied but, in addJ.tion, the rule of ~1 l.S also applied. This has the effect of adding new wtfs to the knowledge base and also will cause the CC to be revJ.sed.

5. An Annotated Example

We present in this section a sample run using MBR. Suppose that MBR is being used by some university as a meeting scheduling system. The knowledge base contains, in thJ.s case, general statements reflecting policies for scheduling meetings and also statements concerning the particular schedules of the users of the system.

MBR is asked to schedule meetings among a certain number of its users and it does so either by finding a time slot which is compatible with their particular schedules or by reporting that the schedules of the users do not allow the scheduling of the desired meeting. In this example we will assume that:

1. Meetings are beJ.ng scheduled within one day only, therefore information about dates is absent from our representation;
2. MeetJ.ngs can not both be in the morning and in : the afternoon lhypl, Fig.l l.
3. Two different meetings can not fill the same time slot, i.e., morning or afternoon lhyp2, Fig.ll.

We will follow MBR's behavior using the information contained in the schedules of two of its users, Stu and Tony. Both Stu and Tony already have some scheduled meetings:

1. Stu's schedule: Stu teaches a seminar in the morning lhyp6, Fig.ll.
2. Tgny's schedule: Tony has a tennis

game sheduled for the afternoon <hyp/, Fig.l).

The knowledge base also contains in~ormation about which ob)ects are meetings <hyp3, hyp4 and hyp5, Fig .l l . rigure l shows the knowledge base for this small example . As a shorthand, we do not represent OS 's as sets of hypotheses but rather as sets of mnemonics representing the hypotheses.

hypl : Ytxllmeetingtxl · C t.ima t x ,aorn1ng I · ~tiaa tx, attarnoon 1 1 l ; hyp , lhypl >, < > hyp2 Vtx,ylttaaat.inghcl "'maatingtyl 1o x.-yl · 1 ttiaatx,aorningl · tiaacy,attarnoonl I ~ ttiaatx,attarnoonl · tiaaty,morningl I I l 'byp, (byp2l. (} hyp3 aaating laaa1nar I : nyp, lhyp3 >, ( > hyp4 aaatingc tannia-gamal : hyp, <nyp4 >, < > hyp5 meatingttaeulty-aaat.l : hyp,<hyp5>,<> byp6 byp7 tiaa t aaainar ,morning I : hyp, <hyp6 >, < l t1aat't.ann1a-g .. a,attarnoonl : nyp, lhyp7> , <>

Hypotheses in the knowledge base

Suppose that Stu wants to schedule a faculty meeting and he wants to do so according to his schedule: he considers the general statements about meetings <hypl, nyp2, hyp3 and hyp5l and also considers the statements that reflect his schedule <hyp6l. ln other words he does reasoning within the BS defined by the context Stu-schedule={hypl, hyp2, hyp3, hyp5, hyp6l. Within this BS, MBR derives the wffs represented in Figure 2. After

vffl : t1aataaa1nar , aorn1ngl · t1aatt.aculty- maat,aftarnoonl

I dar, thyp2 ,hyp3 ,hyp5>, < > vff2 : tiaa t taculty-···t, afternoon J : d.er, <hyp2, hyp3, hYP', byp6 >, < > vtf3 : timet faculty-n~~aat ,morning I · "'ti·al faculty-meat, aftarnoonl : d.ar, <hypl, hyp5 >, < >

vtf4 : ... t1··t faculty-···t .·orningl IeSer, lhypl,hyp2 , hyp3 ,hyp5 ,hyp6>, I>

figure 2 wffs derived from "Stu-schedule"

this session Stu concludes that the best time, for him, for scheduling the faculty meeting is in the afternoon <wff2l.

Suppose now that Tony also tries to find the most convenient time, for him, to have a faculty meeting. In this case, he does reasoning in the BS defined by the context Tony-schedule=<hypl, hyp2, hyp4, hyp5, hyp7>. Some results of such

vff': t.iaattannia-gaaa,aftarnoonJ tiaatfaculty-meat ,11orn1ngl : d.ar, thyp2,hyp4,byp!tl, 1 > vff6 : ttaattaculty-aaat ,·orningl; d.ar , <hyp2 , hyp4 ,byp~.hyp7 >, < >

figure J

wffs derived from "Tony-schedule"

reasoning are represented in Figure 3. In this case, however, when wff6 ltime(faculty- meet,morningll is derived the system finds out that it contradicts wff4 <~timelfaculty-meet,morningll. The implementation of MBR guarantees that this wff is found without having to search the entire knowledge base . Since wff4 does not belong to the CBS <which is now the BS defined by the context "Tony-schedule") there is no visible contradiction. However the system records that the union of the contexts "Stu-schedule" and "Tony-schedule" ({hypl, hyp2, hyp3, hyp4, hyp5, hyp6, hyp7>l is an inconsistent context. The rule URS is applied resulting in the knowledge base represented in Figure 4. The system

hypl: Vtxl laaatinglxl ·

tt1aatx,aorn1ngl · "'timatx,aftarnoonl l J

'byp. ( bypl) · ( ( byp2 · bypJ · byp4 · byp> . byp6 · byp7) )

byp2: Vlx,yl ( tmaatingtxl " maatingtyl " xfllyl · 1 lt1aalx,aorn1ngl · timaty,aftarnoonl l ..

ltiaelx,aftarnoonl · timatx,aorninglll J 'byp. (byp2l. ('(bypl,bypl,byp4 ,byp> .byp6 . byp7))

hypl : aaatingtaaainarl lbyp, (bypl). ( (bypl,byp2 ,byp4 ,byp>. byp6 .byp7l)

hyp4: maatingt tann1a-g-· J l byp. <byp4). ( <bypl, byp2 ,bypl,byp> .byp6 .hyp7))

hyp5 : aaatingtfaculty-···tl I byp, ( byp5) , ( (bypl , byp2 · bypl , byp4 , byp6 , byp7 l)

hyp6 : tiaa I aaainar ,aorning l I byp, <byp6l, ( (bypl,byp2 ,bypl,byp4 ,byp5 .byp7 ll

hyp7 : ttaa 1 tann1a-gaaa, afternoon l : byp. <byp7l . ( <bypl,byp2 ,bypl,byp4 .byp> .byp6l )

11ffl: tiaalaa·inar,aorningl · tiaetfaculty-aaat,attarnoonl 1 clar, <hyp:il: , hyp3 ,hyp4>, < <hypl , hyp5 ,hyp6 ,hyp7 > >

vff:il: : tiaa I faculty-aaat, aftarnoonl 1 der. <nyp2 .byp3 ,byp> .nyp6l, < <bypl,byp4 ,byp7 l l

vffJ: tiaa t faculty-aaat, afternoon) · ... tiaat faculty-aaat ,aorning l l d.ar, thypl, hyp5>, < thyp:il:, hyp3, hyp4 , hyp6 , hyp7 > >

vff4: ... t.a.aalfaculty- aaat,aorningJ lder , (bypl,byp2,bypl,byp5 , byp6l. ( <byp4 .hyp7l l

vff5 : t1aaltann1a-g-a,aftarnoonl · t1aatfaculty-aaa't.,morn1ngJ 1 der, (byp2 ,byp4 ,byp>l, ( <bypl,bypl.byp6 ,byp7 ll

vff6: t1aatfaculty-aaat,aorn1ngJ l d.ar, < hyp2, hyp4, hyp5, hyp7 > , < < hypl , hyp3 , hyp6 > >

figure 4

knowledge base after URS

reports to Tony that the faculty meeting should be in the afternoon.

Suppose that someone now wants to schedule a faculty meeting with all the members of the faculty, which include both Stu and Tony. When that request is made considering a context containing "Stu-schedule" and "Tony-schedule" the system immediately reports that such context is inconsistent. Notice that this context contains, possibly among other hypotheses, the hypotheses hypl, hyp2, hyp3, hyp4, hyp5, hyp6 and hyp7. The RS ot hypl, for example, is <<hyp2, hyp3, hyp4, hyp5, hyp6, hyp7}} <Figure 41, which records that the set of hypotheses hypl through hyp7 is inconsistent. The system responds that such context is inconsistent and a revision of the CC should be performed.

Suppose now that starting from the knowledge base represented in Figure 1 the request is made to schedule the faculty meeting in a BS defined by a context conta1ning "Stu-schedule" and "Tony-schedule".

In this case, there are no recorded inconsistencies and the system will try to schedule the faculty meeting in that BS. Among the results derived are the wtfs represented in Figure 5. In this case,

vf'fl' : ""ti·al faculty-·aat ,aorningl I dar, <hypl,hyp:l,hyp3 ,hyp5 ,hyp6>, < >

vft2': t1·aUaculty-··at,aorningl :dar, (hyp2 ,hyp4 ,hyp5 ,hyp7>, < >

figure 5 wffs derived within the CC

both wtfl' and wft2' belong to the CBS !the CC contains the hypotheses hypl, hyp2, hyp3, hyp4, hyp5, hyp6, hyp7l. Therefore, not only the rule of URS is applied, recording the inconsistent set, but also ~I is applied in order to rule out some hypothesis lor hypotheses> defining the CC.

6. Concluding Remarks

MBR has been implemented in Franz Lisp lr~ning on a VAX-11/750) using the SNePS system [6l. The example presented here was obtained from an actual run just just by slightly changing the output syntax.

One of the main distinguishing characteristics of MER is that it is based on a logic ISWMl especially designed for Belief Revision systems.

In MBR propositions are represented by network nodes and are linked with the hypotheses in their OS and the sets in their RS. This way of representing propositions makes it possible to know a priori the number of arcs that has to be traversed to find out all the hypotheses underlying a contradiction.

_ Another characteristic of MBR concerns the way contexts and BS are defined. By defining a context as a set o~ hypotheses we can have as many contexts in the system as the power set of the hypotheses introduced. Also, the network retrieval functions only consider the propositions in the CBS. When a contradiction is detected, after selecting one hypothesis tor several hypotheses) as the culprit for the contradiction, the disbelief in all the propositions depending on such hypothesis lhypothesesl is done just by dropping it ttheml from the CC. propositions From then on, all are disregarded by MBR. such F1na11y the def1nition ot RSs waives the need to keep a separate data strucure to record all the prev1ous contradictions !e.g., the NOGOOD list !21>.

ACKNOWLEDGEMENTS

Many thanks to Gerard Donlon, Donald McKay, ~rnesto Morgado, Terry Nutter, Bill Rapaport and the other members of the SNePS Research Group for their comments and cr1ticisms concerning the current

work.

REFERENC£5

• LlJ Anderson A. and Belnap N., Entailme~ The Logic ot Relevance and Necessity, Vol.l, Pr1nceton Un1versity Press,
• 1975.
• [2 l Doyle J., "A Truth Maintenance System", Artificial .rntelligence 12:3
• 231-272.
• !31 Martins J., "Reasoning Belief Spaces", Ph.D. Department of Computer at Buffalo, May 1983. in Multiple Dissertation, Science, SUNY
• !41 McAllester D., "An Outlook on Truth Maintenance", A.I. Lab., M.I.T., AI Memo 551, 1980.
• [51 McDermott D., "Contexts and Data Dependencies: A Synthesis", Department of Computer Science, Yale University, 1982.
• [6 l Shapiro S., "The network process1ng SNePS semantic system", in N.V.Findler pp.l79- 203, Associative Networks, led.l, Academic Press, 1979.
• [71 Shapiro S. and Wand M., "The Relevance of Relevance", Technical Report No.46, Computer Science Department, Indiana U~iversity, Indiana, 1976.