29 July 2021
Original Citation:
Exploiting abstractions in cost-sensitive abductive problem solving with observations and actions
Published version:
DOI:10.3233/AIC-140593
Terms of use:
Open Access
(Article begins on next page)
Anyone can freely access the full text of works made available as "Open Access". Works made available under a
Creative Commons license can be used according to the terms and conditions of said license. Use of all other works
requires consent of the right holder (author or publisher) if not exempted from copyright protection by the applicable law.
Availability:
This is the author's manuscript
This full text was downloaded from iris - AperTO: https://iris.unito.it/
iris - AperTO
University of Turin’s Institutional Research Information System and Open Access Institutional Repository
G. Torta; L. Anselma; D. Theseider Dupré. Exploiting abstractions in
cost-sensitive abductive problem solving with observations and actions. AI
COMMUNICATIONS. 27 (3) pp: 245-262.
DOI: 10.3233/AIC-140593
When citing, please refer to the published version.
Link to this full text:
Exploiting abstra tions
in ost-sensitive abdu tive problem solving
with observations and a tions
Gianlu aTorta a;
,Lu aAnselma a
and Daniele TheseiderDupre
b a
Dipartimentodi Informati a, Universitadi Torino
Corso Svizzera185, 10149Torino (Italy) E-mail:ftorta,anselmagdi.unito.it b
DiSIT, Universita delPiemonteOrientale VialeTeresaMi hel 11,15121Alessandria(Italy) E-mail:dtddi.unipmn.it
Severalexplanation and interpretation tasks, su h as diagnosis, plan re ognition and image interpretation, an be formalized as abdu tive and onsisten y rea-soning.Theinterpretationtaskisusuallyexe utedfor the purpose of performing a tions, e.g., in diagnosis, repaira tionsortherapy.Someproposalsaddressthe problem based on a task-independent representation ofadomainwhi hin ludes anontologyortaxonomy ofhypothesesandobservations.Inthispaperwerely onthe sametypeofrepresentation,andwe pointout theroleofabstra tionsinaniterativeabdu tion pro- ess.Atea hiteration,asinmodel-baseddiagnosisand troubleshooting,ouralgorithm hoosestoperform fur-therobservationsora tionstaking intoa ount their ostsandthelikelihoodof andidatehypotheses.The maingoalofthealgorithmistoensuredis rimination amonghypothesesand,moreimportantly,toperform theappropriatea tions forthe ase athand.We dis- ussanimplementationof the proposedmethodand report experimental results that support the on lu-sionthatabstra tionsareindeedusefulforthe onsid-eredtask.
Keywords:Abdu tion,Abstra tion,A tions,Costs
1. Introdu tion
Several explanation and interpretation tasks, su h asdiagnosis,plan re ognitionand image
in-*
Correspondingauthor: Gianlu aTorta,CorsoSvizzera 185,10149Torino(Italy).
terpretation, anbe formalized asabdu tive rea-soning or related forms of nonmonotoni reason-ing.A numberofapproa hes[4, 14, 7, 17, 2℄address the problem based on a representation of a do-main whi h in ludes anontologyortaxonomy of hypotheses.
However, explanation or interpretation is usu-ally anintermediatestepto a nal goal,whi h is performing a tions, su h as repair or therapy in diagnosis, or rea ting to the re ognized plan, in plan re ognition.In some ases, su h a tions are alsoneeded,or,atleast,useful,fordis riminating among alternative explanationsduring the expla-nation/interpretationpro ess itself (e.g., tryinga repaira tionwouldeithersolvetheproblemorat leastprovidetheinformationthatthe orrespond-inghypothesisisnotthe orre tone).
Ontologieshave been proposed asthebasis for large knowledge bases to be used also for other problemsolvingtasks(in ludingplanning,see[21, 11℄), but, as noted in [6℄, they should be shared among di erentproblemsolversforrelatedtasks; therefore,theyshouldbedevelopedindependently of thereasoningtask
1
:i.e., theirstru tureshould re e tanaturalrepresentationofthedomain,but itmightnotdire tlyprovidethebeststru turefor diagnosis,interpretation,orplanningand a ting.
Inthispaperweproposeanovelapproa hwhere asimilarrepresentation isadopted inthe ontext ofaniterativeabdu tionpro esswhere:
{ furtherobservationsora tions(e.g. substitut-ingasuspe t omponentinthesystem),asin model-based diagnosis [12℄ and troubleshoot-ing [13℄, an be proposed with the interme-diate goalofdis riminatingamong andidate explanations and the ultimate goal of
per-1
Inperspe tive,asharedontologyfordi erentreasoning tasksmaybeavailableontheWeb.
forming a tions that are appropriate for the aseathand.A tionsmaybeinterleavedwith observations[10℄.
{ The osts of observations are balan ed with redu ed osts of the a tions performed for solvingtheproblem.
The ostsasso iated withtheresultsof abdu -tion,inadiagnosti setting, orrespondtothe ost of repaira tions or therapy, and are expe ted to de rease aslong asmoreinformation is available onthehypotheses;similarly,inaplanre ognition or in an interpretation task, the human or soft-wareagentusingtheresultsshoulda hievean ad-vantagefrom abetterdis rimination of hypothe-sesorfrommorespe i hypotheses,leadingtoa morefo used a tion, possibly with redu ed osts |e.g.,ifhypothesesarethreatstotheagentwith ostly defense a tions. In all settings, we intend thatsomea tionshavetobetakenbased,in gen-eral,ontheremaining andidatehypotheses.Ifthe setof andidatesistoobroadortooabstra t,the agentisexpe tedtoin urintohighera tion osts dueto(a ombinationof)thefollowingreasons:
{ ana tionwhi h is strongerthanne essaryis taken,inordertoa ountforall urrent pos-sibilities;
{ unne essarya tionsaretaken, e.g.,repairing thewrongpart,takingthewrongtherapy, de-fendingfrom thewrongthreat.
The di erent issues are related: dis rimination maybeperformedamonghypothesesatthesame level of abstra tion, but it ould also involve re- ninghypotheses.In any ase, dis rimination re-quires more observations, whose ost should be balan edwiththebene ts,intermsofmore suit-ablea tions,ofbetterdis rimination.
The presen e of a domain representation with IS-Aabstra tionshasasigni antimpa tonthis trade-o . The ost of observing the same phe-nomenon at di erent levels of abstra tion is ex-pe ted to vary signi antly; in fa t,itmayrange from subje tive information from a human (pa-tientoruser)tomoreorless ostlymedi alor te h-ni altests, or,in an imageinterpretationtask, it may involve omputationally ompleximage pro- essing,tobeperformedintera tivelywiththe rea-soningtask,assuggestedin[15℄.Notethat,inany ase,thepresen e ofabstra tionsshould not pre-ventin generaltheability to exploit detailed
ob-Inseveralsettings,anobservationwhi hisitself expensive,be auseit onsumesresour esandtime to be performed, implies additional osts due to thedelaybeforetakingana tion:breakdown osts in diagnosing a physi al system, risk of death of the patientin medi al diagnosis,taking defensive a tionstoolate, missing theopportunityof earn-ingmoney.Notethat similardrawba ksresult,at least in some s enarios,from time spent in om-puting anoptimal or near-optimal solution,with respe ttoperformingasuboptimala tionearlier. Moreover, if the knowledge base has been de-signed independently of the explanation/a tion task (e.g., diagnosis and repair), it ould in lude adetailed des riptionof thedomain whi his not ne essaryforthetask;moregenerally,the useful-ness of a detailed dis rimination may depend on thespe i aseathand.
Finally,humanproblemsolvershaveknowledge and are able to reason on abstra t a tions, su h as \taking an antibioti therapy" if the leading hypothesisis\ba terialinfe tion",andevaluating their ostsinabroadsense,forexamplein luding side e e ts,withoutne essarilyreasoningon spe- i instan es. Of ourse, anabstra t a tion an-not beexe uted dire tly, but abstra t knowledge may be used to onsider it as a andidate \next step"before ommittingtoaspe i instan e.
Themainexpe tedbene tinexpli itly onsider-ingabstra tionsintheiterativeabdu tionpro ess isasigni antredu tionofthe omputational ost of de iding what to do next (observeor perform ana tion?whi h observationora tion?),without signi antlyin reasingthetotal ostofthe obser-vations and a tionsperformed to solve the prob-lem.
Inthefollowing,we rstdes ribetheknowledge weexpe t to beavailable and de ne the on ept of explanation of a set of observations in general terms.Then, wedes ribeaspe i syntaxfor ex-pressing the knowledge (based on ausal graphs) andasso iateapre isesemanti swithsu hsyntax intermsofpropositionallogi .Thesyntaxandthe asso iatedsemanti sdes ribedinthepaperareby no means the only possible hoi e; however they makethegeneri notionofexplanationmore on- rete for illustrative purposes, and theyare used forbuildinganimplementationofthemethod.
In the subsequent se tions wedes ribea basi iterative abdu tive problem solving loop and we
estimated osts,and onthe riterionforsele ting thenextstepin theloop:either performinga fur-therobservationat somelevelofdetail,oran ab-stra t or on rete a tion. Then, we des ribe the key points of our implementation of the method and present experimental results whi h on rm theexpe tationsabouttheadvantagesofusing ab-stra thypothesesanda tions.
Forthesamepurposeofmakingtheframework on rete, in the problem solving loop we assume thata tionsare\repair"a tions,inthesensethat, as in most forms of diagnosti problem solving, they make a orresponding hypothesis false, i.e., they removethe ause of the problem (as far as auses are modeled in the domain), while obser-vationsare eviden eof theproblem. Inother set-tings, e.g., plan re ognition, the purpose of the a tion, to be hosen appropriately for the situa-tion (whi h an only be assessed through hypo-theti alreasoning),maybedi erentfrommaking thehypothesizedsituation false.However,also in thesesettingsperformingana tionisatleast use-ful (like performing further observations) to on- rmordis on rmthe orre tnessofthe hypothe-sis,eventhough omputingthepredi tede e tsof performing the a tion may be di erent from \re-moving symptomsif thehypothesis was orre t", asin the on reteframework des ribedinthe pa-per.
2. DomainRepresentation
2.1. Hierar hies
Thebasi elements of the domain model area set of abdu ibles (i.e., assumptions, hypotheses)
A = fA
1
; :::; A n
g and a set of manifestations (i.e.,observables)M=fM 1 ;:::;M m g. Ea h abdu ible A i
is asso iated with an IS-A hierar hy (A
i
) ontaining abstra t valuesof A i aswellastheirre nementsatmultiplelevels; sim-ilarly,ea hmanifestationM
j
isasso iatedwithan IS-Ahierar hy(M
j ).
Weassumethatthedire tre nementsv 1
;:::;v q ofavalueV inahierar hy(either(A
i
)or(M j
)) are mutually ex lusive,i.e., the hierar hies are trees; moreover,in agivensituation, exa tly one ground instan e (i.e., leaf) of ea h manifestation M
j
is true while, for ea h abdu ible A i
, either onegroundinstan e is true (i.e.,the abdu ible is
present)ornoneofthemistrue(i.e.,theabdu ible is notpresent).The assumption that there is al-waysatrueleafforea hmanifestationM
j
ismade justfor onvenien e,sothatin reasingour knowl-edge about manifestations an always be viewed asare nementofthepreviousknowledge; learly, knowingthattherootofamanifestationhierar hy (M
j
) is true represents omplete la kof knowl-edgeaboutM
j
(seese tion3).
Theoverallgoalofourproblemsolvingpro ess is to perform a tions that remove all of the ab-du ibles whi hare presentin agivensituation at an(approximately)minimum ost.
Theabdu ibles set vals(A i
)ofanabdu ibleA i is the set of all of the elements of the hierar hy (A
i
),whilegndvals(A i
)isthesubsetofvals(A i
) ontainingonlygroundabdu ibles,i.e.,theleaves ofhierar hy(A
i
).Thede nitionofsetvals (resp. gndvals) an be extended to a set of abdu ibles by takingtheunionof thevals (resp. gndvals) of ea h abdu ible in the set; wealso de ne set vals (resp. gndvals) for an abdu ible value belong-ingtothehierar hy(A
i
)by onsideringonlythe values(resp.groundvalues)belongingto the sub-hierar hy( )of(A
i
)rootedat .
Thesetsvals andgndvals arede nedfor mani-festationsM
j
in thesamewayasforabdu ibles. We assume that ana-priori probabilityp(a) is givenfor ea h leaf valuea of an abdu ible A: in fa t,weassumethatdi erentabdu iblesare inde-pendent.Instead,theprobabilityofaninnernode isde ned asthesumoftheprobabilitiesofits di-re tre nements(whi h, assaidbefore,are mutu-allyex lusive).
Wealsoasso iate ostswiththe(ground)values ofabdu iblesandthe(abstra t)valuesof manifes-tations.
The ostofagroundabdu iblevaluerepresents the ostof the a tionneeded to remove(e.g., re-pair)it;ingeneral,su ha ostmaydependonthe urrent status of the world, however, in this pa-perweassumethatforea hleafvalueaofan ab-du ible,a ostr (a)isassigned, independently of the urrenthypotheses.
As for the manifestations, let ! be an inter-nal value belonging to the IS-A hierar hy of M
j (i.e., ! 2 vals(M
j
)ngndvals(M j
)); its ost o (!) isthe ostofmakingtheobservationwhi hre nes the value ! into oneof its hildren !
1 ;:::;!
q in (M ).
2.2. Explanatory Knowledge
The hypotheses spa e S(A) is the set of all of the ombinations =f
1 ;:::;
r
gofvaluesdrawn fromzeroormoredistin t hierar hies(A
i )(i.e., we allow the presen e of multiple abdu ibles at the same time) and, similarly, the observations spa e S(M) is the set of all of the ombinations =f!
1 ;:::;!
m
gofvaluesdrawnfromea hofthe distin thierar hies(M
j
).Inthepaper, willbe referredto asa andidate explanation ( andidate forshort)andasanobservation.
If and A
are two andidates with the same number r of abdu ible values, and ea h value
i
2 is a (possibly improper) re nement of a value
A;i 2
A
a ordingtotheIS-A hierar hies ofabdu ibles,thenwesaythat
A
isan abstra -tionof and, onversely,that isare nementof
A
.A similarrelationship anbede nedbetween twoobservationsand
A
,bytakingintoa ount theIS-Ahierar hiesofmanifestations.
Therelationship betweenabdu ibles and man-ifestations is de ned by the explanatory domain knowledgeK
E
S(A) S(M).Givenan obser-vation 2S(M)and a andidate 2S(A),the fa t that ( ;) 2 K
E
means that is a possi-bleobservation orrespondingto andidate (and, onversely,that isapossibleexplanationfor).
Ourde nitionof K E
asarelationbetweensets S(A) andS(M)doesnotimplythat su ha rela-tionshouldberepresentedextensionallyand that thereasoningalgorithms should dire tly manipu-latesu hanextensionalrepresentation.Ingeneral, K
E
will be spe i ed intensionally with a multi-valuedpropositionalor ausalmodelwhose seman-ti s orrespondstotheextensionalenumerationof the tuples in K
E
(in the next se tion we dis uss theintensionalrepresentationtowhi hwewill re-ferinthispaper).Moreover,alsothereasoning in-volvingK
E
maytakepla eat thesynta ti level, e.g.,aspropositionalor ausalinferen e.
Given the abovede nition of K E
, the set of andidate explanations( andidate set)for an ob-servation2S(M)is:
=f 2S(A):( ;)2K E
g
Animportantissueisthattheremaybetoomany ground explanations of the given observations. Thisproblemmaybesolvedmu hmoreeÆ iently thankstothepresen eofabstra tionsinthemodel
as ground abdu ibles may take part in explana-tions.
Ageneral riterionwhi hissuitableinthissetting isthepreferen eforleastpresumptiveexplanations [18℄, whi hgeneralize minimal (wrtset in lusion) explanations, in order to avoid both unne essary assumptions,whenasubsetofassumptionsis suÆ- ienttoexplaintheobservations,andassumptions thatareunne essarilyspe i ,whenalessspe i assumptionissuÆ ient.Anexplanation ismore presumptivethan another explanation
0
if (also basedontheIS-Ahierar hies(A
i
)) implies 0
. Guaranteeing that a set of explanations is the setofleastpresumptiveexplanationsis,ingeneral, omputationally omplex;inthefollowing,wejust requirethat thesets of andidate explanations omputed during the problem solving pro ess do not ontainexplanationsthat are more presump-tivethanothermembersof .
3. A CausalGraphRepresentationFormalism
In Figure 1we show a fragment of a titious medi al domainmodel, where wehaveadopted a ausalgraphformalisminspiredby[7℄.Inthis se -tionwedes ribetheformalismandrelateittothe explanationknowledgeK
E
throughitssemanti s.
3.1. RepresentationFormalism
We des ribe the formalism (whi h should be fairly intuitive) throughtheexampleof Figure 1. Ontheleft, thereisthenosologi aldes riptionof some diseases, represented as three IS-A hierar- hiesofabdu ibles (withroots D1,D2,andD3). Forexample,D1:1 andD1:2 aretwore nements of D1. The a-priori probabilities of the leaves of abdu ibles(not shownin the gure) are assumed tobe 1 2 8 ,ex eptforp(D1:1)= 1 2 7 .The ostsr of thea tionsthatremovethegroundabdu iblesare showninthe gure.
On theright,there are possible symptoms and possible medi al examinations (lab tests) to be performed,representedasthreeIS-Ahierar hiesof manifestations(withrootsSym1,LT1,andLT2). Observation ostso asso iatedwithea hinternal nodeof manifestationhierar hiesare the osts of performingtherelatedlaboratorytest(weassume that the ost of observing the presen e of
symp-D1
D1.1
D1.2
D1.2.1
D1.2.2
rc=4
rc=4
D2
D2.1
D2.2
rc=6
rc=8
D3
rc=15
LT1
LT1Neg
LT1Pos
LabTest1+
LabTest1++
oc=2
oc=8
LT2
LT2Neg
LT2Pos
oc=8
oc=12
LT2+
LT2++
Sym1Pres
Sym1
Sym1Abs
rc=8
Fig.1.A( titious)medi aldomainmodel.
Therelationshipsbetweenabdu iblesand man-ifestations are represented by rightwards dashed arrows. For example,D1 auses LT2 to be posi-tive; D1:2 auses LT1 to be positive,and its re- nementsD1:2:1 andD1:2:2 ausemorespe i positivevaluesof LT1.
3.2. Propositional Semanti s
In order to map the graph-based formalism adoptedinourexampletotheexplanatory knowl-edgeK
E
,weinterpretthegraphasapropositional theoryT
E
;thetuplesofK E
willthenbe straight-forwardly obtained from the logi al models that satisfysu hatheory(seese tion3.3).
First of all, ea h value in a hierar hy (A i
) or (M
j
) is mapped to a propositional variable. If value V has hildren v
1 ;:::;v q in a hierar hy, a naturalrepresentationinT E wouldbe: V ,v 1 _:::_v q 8i6=j:(v i ^v j ) (1)
expressing the fa t that an abstra t value V an bere nedinexa tlyoneofits hildrenv
1 ;:::;v
q , whi h is what westated in our dis ussion in se -tion2.1.
However, ouraim in de ning T E
is to be able tomapits(2-valued)logi almodelsasdire tlyas
theproblem with theabovetranslationisthat in ea hlogi almodelofformulas(1)whereV istrue, also one hild v
i
mustbetrue while, for the pur-poseof omputingexplanations,wewanttoallow andidateswherenoneofthe hildrenistrue,i.e., where V alone isan(abstra t)explanation.
Consider,e.g.,thegraphofFigure1andassume thatweknowthatLT1Posistrue;wewouldliketo haveanexplanationwhere D1:2 is truebut none ofits hildrenD1:2:1 andD1:2:2 istrue,toavoid ommitment.
In order to handle this issue, for ea h internal valueV of ea h hierar hy,weaddavariable uk
V to represent expli itly, in a 2-valued model, the fa t that it is unknown whi h re nementof V is true.IfvalueV has hildrenv
1 ;:::;v
q
, insteadof formulas (1), thefollowingformulasare addedto T E : V ,v 1 _:::_v q _uk V 8i6=j:(v i ^v j ); 8i:(v i ^uk V ) (2)
Notethatthistranslationisnotintendedasa gen-eral,logi allysatisfa toryapproa htothelogi of knowledge;itspurposeistohaveabstra t explana-tionsas2-valuedpropositionalinterpretations(see se tion5.1).
Therelationshipsbetweenabdu ibles and man-ifestations are translatedasfollows,adapting the ompletionsemanti sofabdu tiondes ribedin[8℄
tionsmay not be predi tive enough to entail ob-servations [14℄. Let ! be a value in a manifesta-tionhierar hy(M),su hthatinthe ausalgraph theabdu iblevalues
1 ;:::;
k
pointto!through ausal arrows (note that
1 ;:::;
k
are, in gen-eral, valuesbelonging to di erent abdu ible hier-ar hies).Moreover,let
1 ;:::;
l
beabdu ible val-ues that point to possibly not distin t an estors !
1 ;:::;!
l
of!,su hthatnoneofthedes endants of ea h
i
points to ! or an an estor of ! below !
i
.Then,weaddthefollowingformulastoT E : 1 _:::_ k )! !) 1 _:::_ k _ 1 _:::_ l (3)
Notethat,ifforamanifestationvalue! thereare no
i
sandno j
ssatisfyingtheabove onditions, we do notadd anyformula. In other words, ! is interpretedasavaluewhi his onsistentwithany abdu ible value , asfaras doesnotexpli itly predi t avalue !
0
su h that ! and ! 0
are mutu-ally ex lusive a ording to formulas (2). In Fig-ure1,thisroleisplayedbySym1Abs,LT1Negand LT2Neg, whi h do nothave any in oming ausal ar .
Letus onsidersomeexamplesfromthemodelof Figure1.Twoabdu ible valuespointto LT2Pos, namely D1 and D2; sin e no abdu ible value pointstothe(only)an estorLT2 ofLT2Pos (i.e., there are no
i
s in formula (3)), we add the fol-lowingformulas:
D1 _D2 )LT2Pos
LT2Pos)D1 _D2
A ordingto the rstformula,ifLT2Pos isfalse, then also D1 and D2 are false, i.e., neither D1, norD2, noranyre nementsof su h diseases an beexplanations.If, ontheotherhand,LT2Pos is observedtobetrue,then,a ordingtothese ond formula, either D1 orD2 must be true; in turn, this may be due to, e.g.,the fa t that the re ne-mentD1:2 ofD1 istruebut,asdis ussedabove,it mayalsobethe asethat uk
D1
istrue,i.e.,wedo notneed to ommit to anyparti ular re nement ofD1 inordertoexplainLT2Pos.
Let us now onsider a more omplex example, wherethe
i
sofformula(3)areinvolved.Theonly abdu ible value pointing to LT2+ is D2:1; how-ever,D1 pointstothean estorLT2Pos ofLT2+; thereforeweaddthefollowingformulas:
D2:1 )LT2+
The se ond formula states that if LT2+ is true, then D2:1 orD1 mustbetrue: the rstone, be- auseitdire tly ausesLT2+;these ondone be- auseit ausesthean estorLT2Pos ofLT2+and itsdes endantsdonotpredi tmorespe i values. In this way, although the abdu ible hierar hy of D1 predi tsthe valueofmanifestationLT2 at a oarser level of granularity than the abdu ible hierar hyofD2,westillallowD1 toexplainsome ne-grainedvaluesofLT2,su h asLT2+ .
Adoptingthehierar hi alformulas(2)withuk V variables has the bene t of allowing abstra t ex-planations,asdis ussedabove,butitalsoweakens the theory T
E
. In parti ular, let us assume that an observation value ! is not unknown (i.e., one of its hildren!
j
is known to be true), and that a hild
i
of an abdu ible value points to one oftheother hildren!
h
of!,h6=j.A ordingto formulas (2), it may still be possible that uk
is true, i.e.,that isan abstra texplanation of!
j . Wewouldliketoavoid beinganexplanation of !
j
when (atleast) oneof its hildren, namely i
, is ertainlynottrue.Tothisend,weaddtoT
E the formula: :uk ! )(:! h ):uk ) (4)
The formula says that, unless the value of ! is unknown,ifvalue!
h
isfalsethenabdu iblevalue is notunknown, i.e., annot be an(abstra t) explanation.
To illustrate this point, let us onsider value LT1 in Figure 1,and letusassume that wehave ex luded its hild LT1Pos byobserving LT1Neg. Thankstothepresen eoftheformula:
:uk LT1
)(:LT1Pos):uk
D1 )
the manifestation value LT1Neg annot be ex-plained byD1 alone, although it an still be ex-plained byoneofitsre nements,namelyD1:1.
3.3. Mapping tothe ExplanatoryKnowledge
On ethetheoryT E
hasbeengeneratedfromthe ausalgraph,itslogi almodelsareeasilymapped toanexplanatoryknowledgeK E S(A)S(M) asde nedinse tion 2.2. Let=f! 1 ;:::;! m
gbeanyobservation. Start-ingfromtheoryT
E
,wewanttode netheportion K
E
() of K E
whi h ontains theexplanations of .Tothisend,westartby onsideringthe propo-sitionaltheory:
T E ()=T E [f! 1 ^:::^! m g
whi hassertsobservation=f! 1 ;:::;! m ginT E . LetusdenoteasM()alogi almodelofT
E (), andrestri tittoapartialmodelM()
A
whi h as-signstruth valuesonlytothevariablesasso iated withabdu ibles: M() A =M A 1 [:::[M A n whereM A i
isatruthassignmentto ea hvariable in vals(A
i
). Note that M() A
does not ontain thetruthassigmentstotheunknownvariablesuk
asso iatedwiththeabdu iblevalues.
Fromea hmodelM() A
we anderiveexa tly one andidate asfollows:
{ if M A
i
assigns false to ea h variable, then none of the values vals(A
i ) of abdu ible A i belongsto ; { otherwise,let i
bethemostspe i valueof A i su hthat M Ai assignstrueto i ;then i belongsto .
The andidate derived from M() A
as we have justexplainedisdenoted as (M()
A ). TherelationK
E
() ontainingtheexplanations ofisthusde nedas:
K E ()=f( ;)j9M() A : = (M() A )g
i.e., the explanations of are the andidates de-rivedfromthe(partial)modelsM()
A ofT E (). Finally, K E
itself is de ned as the union of K
E
() forea h possible observation . As stated before, our purpose is notthat of expli itly enu-merating all of the tuples of relation K
E , whi h wouldbeinfeasibleforallbutthesmallestdomain models.Instead,theabovedis ussionimpliesthat we an omputethe explanationsof any observa-tionby dire tlymanipulating thepropositional theoryT
E .
Let us onsider again an example from the modelofFigure1.Wemayaskwhether,a ording to the above de nitions, andidate = fD1:2g isan explanation ofobservation =fSym1Pres; LT1; LT2g, i.e., whether (fD1:2g;fSym1Pres; LT1;LT2g)2K
E .
It is easy to see that the propositional seman-ti s of the graph in ludes a logi al model where the only abdu ible variables that are true are D1, D1:2 and uk
D1:2
, while the true manifesta-tionvariablesareSym1Pres,LT1,LT1Pos,LT2, LT2Pos plus other unknown variables and
vari-input:asetofvalues'^=f^! 1
;:::;!^ m
g representingtheinitialobservations
':='^ :=[℄
generateaset of andidates whi h explain'^ loop if =f;gthenexit :=f j9 i 2 : 2 i g :=ChooseNextStep( ,',) := if=!2' (', ):=Observe(', ,,!) elseif = 2 (', ):=Remove(', ,, ) endif end
Fig.2.Mainloopofthetroubleshootingalgorithm.
Clearly, if = fSym1Pres; LT1; LT2g, this is also a logi al model M() of T
E
() = T
E [ fSym1Pres; LT1; LT2g.Letus now onsider the restri tionM()
A
ofM()totheAvariables;by eliminating all the assignments to uk and mani-festationvariables,M()
A
assignstruejustto ab-du iblevariablesD1 andD1:2,bothbelongingto theportionM
D1
of M()
A .
Fromtherules forderivinga andidate from M()
A
,itfollowsthat (M() A
)=fD1:2g,sowe nally on lude that (fD1:2g; fSym1Pres; LT1; LT2g)2K
E .
Fromthisexample,weeasilyseethatfD1:2gis alsoanexplanationfor,e.g.,fSym1Pres;LT1Pos; LT2g or fSym1Pres; LT1Pos; LT2Posg, where morere nedobservationvalueshavebeenin luded into theobservationthatwewanttoexplain.
4. MethodDes ription
4.1. Troubleshooting Algorithm
ThealgorithmshowninFigure2illustratesthe overallapproa hto troubleshooting with abstra -tionsweproposein thispaper.
We de ne ' = f!
1 ;:::;!
m
g as the urrent fringeoverthemanifestations, ontainingthemost spe i values!
j
knowntobetruesofarfor man-ifestationsM
j
ea h manifestationistruein ea h situation,ifwe donothaveanyinformationaboutthevalueofa manifestationM
j
,itsvaluein 'istherootofthe hierar hy for M j , i.e., ! j = root((M j )) ; other-wise,! j
maybeamorespe i valueinvals(M j
). An initial fringe'^of observationsis givenand thefringe isupdatedas the problemsolving pro- ess goes on. We also initialize the sequen e of observations/a tions performed so far to the emptysequen e [℄. Thesequen e will beuseful for ignoring a tions that have already been per-formed[22℄.
Given theset of initialobservations',^ aset of andidateexplanations aregenerated.
Atea hiterationofthemainloop,we rst he k whether ontains just an empty andidate ;, meaningthat theproblemis solvedandthe algo-rithm anterminate.Ifthisisnotthe ase,theset ofabdu iblevaluesthatappearin is omputed. Then,wehaveto hoosewhethertoperforman observation, inorder tore neordis riminatethe andidates,ortoremoveanabdu ible,by impli -itly performing the related a tion(for examplea repaira tionin thetroubleshooting ontext).We sele twhattodonextbasedonthe urrent andi-dateset ,thefringe'andthesetofabdu ibles. Clearly,this hoi eisingeneralsuboptimal,dueto the prohibitive omplexity of making an optimal hoi e.
If the hoi e is to perform an observation, the andidateset and thefringe 'are updated a - ordingto itsout ome( allto fun tion Observe). Inparti ular,if!isavalueinmanifestation hier-ar hy(M)andtheout omeofobserving!is!
k , then ! is repla edby !
k
asthevalue ofM in '; the andidate set is updatedby generatingthe andidateexplanationsfortheupdatedfringe.
Alsowhenthe hoi eisto removeanabdu ible value , and'mustbeupdated( alltofun tion Remove).Thedetails ofsu h anupdatearegiven inthenextse tion.
4.2. Removing Abdu ibles
Inthisse tionwedes ribehowthefringe'and the andidateset areupdatedwhenanabdu ible value is removed. We denote as '
0 and
0 the updatedfringeand andidateset,respe tively.
Letus startby onsidering theupdateof '.In ordertoupdate',the rststepisatransformation oftheprevious andidateset .Inparti ular,if
is a ground abdu ible valuea, we ompute aset a
byupdatingea h andidate 2 asfollows:
0
= nfag
( learly, if a 62 then 0
= ; note also that if =fag,then
0 =;). Ea h updated andidate
0
will make, in gen-eral, a set of possibly non-deterministi predi -tions f
1 ;:::;
q
g on the values of manifesta-tions M, where ea h predi tion is a set
i = f! i;1 ;:::;! i;m g. Ea h andidate 0 represents all of its possibleextensions and re nements; there-fore the predi tions of
0
are all the observa-tions
i
that an be indu ed by any of its ex-tensions/re nements. Forexample, the andidate
0
=;will makeessentiallynopredi tion(ex ept theobviousfa t that therootsofea h manifesta-tionare present),sin eit anbeextended toany other andidate.
Let us denote with LUB( 0 ;M j ) the value in (M j
)thatistheleastupperboundoff! 1;j
;:::; !
q;j
g (i.e., of the set of values for M j
predi ted by
0
). The new fringe predi ted by 0 will then be'( 0 )=fLUB( 0 ;M 1 );:::;LUB( 0 ;M m )g (re- allthat avaluein the fringe forM
j
isthe most spe i valueofM
j
knowntobe ertainlytrue). Similarly,wedenotewith LUB(
a ;M j )thevalue in (M j
)thatis theleastupperbound oftheset fLUB( 0 ;M j ): 0 2 a
g(i.e.,of theset ofvalues forM
j
predi tedby a
).Thenewfringepredi ted by a will therefore be '( a ) = fLUB( a ;M 1 ); :::;LUB( a ;M m ) g. The updated fringe '
0
should be set to '( a
); note howeverthat '(
a
) may ontain veryweak (i.e.,abstra t)valuesformanifestations,sin ethey mustbe onsistentwithallofthepossible predi -tions madeby allof the(modi ed) andidatesin
a
.Forthisreason,itisusefultoassumethat,for a (possibly empty) subset M
of manifestations, it ispossibleto performat no ostanimmediate he k(atagivenlevelofabstra tion)afterthe re-movalofanabdu ible.
In parti ular, following [23℄, we de ne a ut C(M) on a hierar hy (M) to be a set of val-ues ! 2 vals(M) su h that ea h groundvalue in gndvals(M)isaninstan eofexa tlyone!2C(M) (i.e.,a ut anbeseenasa urvelinewhi hmakes anhorizontal utofthetree(M)intwopartsby tou hingasetofvaluesatpossiblydi erentlevels ofabstra tion).
M
will result in exa tly one (abstra t) value !
j
belonging to the ut C (M j ) asso iated with (M j ).
Forinstan e,inourrunningexample,the manifes-tationSym1 isasso iatedwiththe utfSym1Pres; Sym1Absg, i.e., after performing an a tion we know for free whether the symptom persists (Sym1Pres)orithasdisappeared(Sym1Abs).For theothermanifestationsLT1 andLT2,weassume trivial uts onsisting just in the roots of the re-spe tivehierar hies.
Note that a ut may in general onsist of both groundandabstra tvalues:forinstan e,fLT1Pos; LT1Neggwould beavalid utforLT1, although LT1Pos is an abstra t value, while LT1Neg is a groundvalue.
In general,the observed value ! j 2 C (M j ) of a manifestation M j 2 M
may be more pre ise thanthepredi tedvalueLUB(
a ;M
j
)anditwill thereforebein ludedinthenewfringe'
0 . Theupdated andidateset
0
willbe omputed bygeneratingtheexplanationsfor'
0
,taking into a ountthattheabdu iblesinthesequen e (in- ludinga)willnotbepartofanyexplanation.
Letus now onsiderthe exe utionof ana tion forremovinganabstra tabdu ible value .Sin e ,bybeingabstra t,isnotasso iatedwithan a -tionwhi h ouldremoveit, weneedtoiteratively removethe values a : a 2 gndvals( ) until we ensurethat has indeed been removed(i.e., has be omefalse)inthe andidates .
The algorithm starts by sele ting an approxi-mately best valuea to remove(see below). After theremovalofabdu iblevaluea,therearetwo pos-sible ases:eithersomemanifestationsinM
have hanged,ornot.Inthe rst ase,awas learlythe real re nementof , sothe removalof is om-plete.Otherwise,anewapproximatelybestvalue a
0
issele ted,andsoonuntilsomemanifestations in M
hange. It is possible (in parti ular when wehave hosentoremoveanadbu ible thatwas notpresentin the rstpla e),that weneedto re-moveallthegroundvaluesingndvals( ),sin ewe don'tdete tany hangein themanifestations.
The sele tion of the best value to remove is based on a slight modi ation of the eÆ ien y measurede nedin[13℄.Inparti ular,letusdenote with
a
thesubsetof whose andidates ontain theabdu iblevaluea(i.e.,
a
=f 2 :a2 g); theeÆ ien yofvalueaisde ned as:
ef(a)= p(
a j ) r (a)
Intuitively, the eÆ ien y of a is in reased by the probability that the abdu ible value a is in the andidate set, and it is de reasedby the ost of removingit.Thevalueatoberemovednextisthe onewiththehighesteÆ ien y.
Independentlyofthesequen eofvalues(a 1
;:::; a
q
)whi hisa tuallyremoved,on etheremovalof is ompletewe anpro eedtoupdate'and as in the aseof aground abdu iblevaluedes ribed above.
4.3. EstimatedCost ofRemovingAbdu ibles
In theprevious se tion wehave onsidered the a tual removalof an abdu ible value, and its ef-fe ts on' and . In this se tion we onsider the problem of estimating the ost of su h aremoval before a tually exe uting any a tion. This esti-mate isneededinorderto hoosewhat shouldbe done next, i.e., observe or remove,in the allto ChooseNextStep in Figure 2;wewill explain su h a hoi ein detailin thenextse tion.
If isagroundabdu iblevaluea,thenthe ost r (a) is de ned dire tly in the model, sothere is no need to estimate it. If, on the other hand, is anabstra t value,its ost anbeestimated by adapting to our setting a simple te hnique from the troubleshooting literature, namely the greedy approa hof[16℄.Let(a 1 ;:::;a q )bethe sequen e ofgroundvaluesa i
2gndvals( )inde reasing ef- ien yordera ordingtotheformulaintrodu ed in the previousse tion.Theestimated ost of re-moving from a andidate set is omputed as follows: r ( )= q X i=1 r (a i ) 1 p( j )p( 62 i j ) (5) where i
is the andidateset after valuesa 1
; :::; a
i 1
have been removed starting from andidate set .When onvenient,wewill usethe notation r (a)todenotethe xed ostr (a)de nedinthe modelforagroundabdu iblevaluea.
To understand this de nition, let us rst note thatthemosteÆ ientgroundvaluea
1
willalways beremovedatthe ostr (a
1 ):indeed, 1 = and therefore p( 62 1 j ) = 0,sin e is onsidered forremovaljustbe auseitappearsin .Asfora
2 , its ost r (a ) will be paid, ex ept in ase, after
removing a 1
, theresulting andidate set 2
does nolonger ontain (i.e., hasbeenremovedby removinga
1
,andthisfa thasbeendete ted-see below).Similarly,the ostofa
i
;i>2,willbepaid ex eptin ase,afterremovinga
1 ;:::;a
i 1
,the re-sulting andidateset
i
doesnolonger ontain . The exa t way p( 62
i
j ) is omputed de-pendsonthesetofmanifestationsM
that anbe he kedat no ostafterthe exe utionofea h a -tion,andonthe utsasso iatedwithsu h he ks. Onepossibility isto makethestrong assumption thattheremovalofanyvaluea
i
(whena i
is a tu-ally present) always makes the manifestations in M
hange;in su ha ase:
p( 62 i j )= i 1 X j=1 p(a j j ) i.e., i
willnot ontain providedoneofthevalues a
1 ;:::;a
i 1
waspresent.
If, on theother hand,wemakethe weaker as-sumption that the manifestations in M
hange onlywhentheproblemhasbeensolved,then:
p( 62 i j )= 0 iff g62 P i 1 j=1 p(a j j )otherwise (6)
sin e,ifthereisno andidate ontainingjustf g, theproblemwill ertainlynotbesolvedby remov-ing while, otherwise, dete ting that the prob-lemissolvedisequaltodete tingthat hasbeen removed.
Theassumptionwe hoosetomake(the strong or weak ones des ribed above, as well as other ones) will not a e t the orre tness of the algo-rithm,sin eit isusedjust forestimatingthe ost ofremoving .However,theassumptionshould re- e tasfaraspossiblethe hara teristi softhe do-main(inthis ase,thenumberanddis rimination powerofmanifestationsM
),inordertomakethe estimate as pre ise (and useful) as possible. For theexampleinse tion4.5andforthe experimen-talevaluationin se tion5,wewill usetheweaker assumption.
4.4. Choosing the NextStep
As dis ussed in se tion 4.1, at ea h iteration ofthe problemsolvingpro ess weneed to hoose whethertoobserveavalue! inthefringe'orto removeanabdu ible intheset.
Forea h !2',weevaluatetheestimated ost
! andtheexpe ted ostofthe andidatesetafter re ning!,i.e.: (!)=o (!)+ q X k =1 p(! k j ) ( k ) (7) where 1 ;:::; q
are the possible andidate sets that would resultbyobserving! andgetting val-ues ! 1 ;:::;! q respe tively; p(! k j ) is the proba-bilityofgettingvalue!
k
( omputedbasedon ur-rent andidates );and (
k
)istheestimated ost of
k
asdetailed below.
Forea h 2,weevaluate theestimated ost ( ),whi histhesumofthe ostr ( )of remov-ing and theexpe ted ost of the andidate set after removing ,i.e.:
( )=r ( )+ X k2PW( ; ) p( k j ) ( k ) (8)
where PW( ; ) (for possible worlds) is an esti-mateofthepossible andidatesets resultingfrom the removal of and p(
k
j ) is the probability that the a tual andidate set after removing is
k .
Letus onsiderthesetPW( ; )inmoredetail. Asinthea tualremovalofanabdu iblevalue,we rst omputethe andidateset
obtainedby re-moving from ea h andidate in . In order to simplifyourestimate,we onsiderthatea h andi-date
0 2
representsjust itself, insteadof rep-resentingalsoallofitsextensionsandre nements, e.g.,wedonotinterpret;astherepresentationof anypossible andidateaswedo in thea tual ex-e ution of a tions, but just asthe representation of the asewhere none ofthe abdu ible values is present.Thisapproximationmakesthepredi tions of andidates
0
mu hmorepre ise,improvingthe eÆ ien y oftheestimateasweshallsee shortly.
We then onsider the predi tions made by the andidatesin
ontheM
manifestationsatthe levelofthe utsC
(M
j
),andgroupallofthe an-didates
0
whi h make the samepredi tions into thesamepossibleworld
k
.ThesetPW( ; )will ontainallofthe andidatesets
k
obtained in thisway.
In general, the number of possible (non deter-ministi )predi tionsonmanifestationsM
anbe exponentialinjM
j,andthereforePW( ; )may be intra table to ompute if M
is large. How-ever,even when M
is large, it is suÆ ient that thepredi tionsmadebythe andidates
0 2
on
at the level of the uts C
(M j
); in su h a ase it iseasy to seethat jPW( ;a)j isbounded bythe numberof andidatesj j.
Inbothequations 7 and 8,weneed to beable toestimatethe ostoftheproblemsolvingpro ess fora andidateset
k .
Inorderto omputesu ha ost,weadopt a te h-nique similar to the one adopted for estimating r ( )(se tion4.3),inspiredby[16℄.Inparti ular, westartby omputing
k
,i.e.,thesetofabdu ible valuesthat appearin
k
; thenweorder su h ab-du iblesinde reasingeÆ ien yorderusingthe fol-lowing formula, whi h was introdu ed previously forgroundabdu iblevaluesbut anbe straightfor-wardlyappliedalsotoabstra tabdu iblevalues:
ef k ( )= p( j k ) r k ( ) Let^ k =( 1 ;:::; q
)bethesequen eofabdu ible values ordered by de reasing order of eÆ ien y. The ostof k is omputedasfollows: ( k )= q X i=1 r k ( i )p( i k 6=f;g) (9) where i k
isthe andidateset after abdu ible val-ues
1 ;:::;
i 1
havebeenremovedstartingfrom andidateset
k .
Note that the ost of ea h abdu ible i
is weighted with the probability that the a tion to removeitwill a tually beexe uted, i.e., that the andidate set
i k
is not equal to f;g, whi h or-responds to the situation where the problem has alreadybeensolvedandthishasbeendete ted,so thattheonly andidateleftis;.
As in the ase of the estimate of r ( ), the way p(
i k
6=f;g) is omputeddepends onthe set ofmanifestationsM
andon the utsC
(M j
). If weassume that,after ea h a tion exe ution,it is possibleto he kat no ost whetherthe problem hasbeensolvedornot,then:
p( i k 6=;)= X 0 2 k : 0 6f 1;:::; i 1g p( 0 j k )
sin e, if the real world status is a andidate
0
2 whi h is ompletely removed by remov-ing
1 ;:::;
i 1
, we must be aware(through our he ks) that the problem is solved, and
i must thereforebeequalto f;g.
Afterwehave omputed theexpe ted observa-tion osts (!)andexpe teda tion osts ( ),we
simply hoose the observation or a tion su h that:
=argmin ^ 2('[)
[ (^)℄
i.e., the observation or a tion of minimum ex-pe ted ost.
4.5. Example
In order to get a better understanding of the problem solvingpro ess, let us onsider in detail theexe ution ofthealgorithm inFigure 2onthe medi alexamplein Figure1.A s hemati viewof thesolutionpro essisshowninFigure 3.
Initialobservations.Letussupposethat an ini-tial manifestation of Sym1 is dete ted, i.e., '^ = fSym1Pres;LT1;LT2g.Theinitial andidateset is =ffD1g;fD2g;fD3gg,representingthe pos-sible alternative diagnoses (in fa t, D1, D2 and D3explainSym1Pres).
Firstiteration.Theabdu iblestobe onsidered forremovalare=fD1;D2;D3g,whilethefringe 'isinitiallyequalto'^=fSym1Pres;LT1;LT2g. Figure3showsthepossible hoi esasdashedar s leaving theroot ofthe graph;note that we don't onsider the observation of Sym1Pres sin e it is a ground value in the hierar hy of manifestation Sym1.
The osts are estimated as follows. Regarding theobservation!=LT1,twoout omesare possi-ble:thetestiseithernegative(LT1Neg)orpositive (LT1Pos). The andidate set
N
resulting from observingLT1Neg is:
N
=ffD1:1g;fD2g;fD3gg
Indeed, a ording to se tion 3.2, LT1Neg is ex-plained by any abdu ible valueex eptthose that predi t LT1Pos, namely D1:2 and its hildren, i.e.,exa tlybythe(leastpresumptive) andidates ontainedin
N
. Note that these andidates also explain the manifestation values already in ', in parti ularSym1Pres.
On the other hand, if the out ome is LT1Pos, the andidatesetis:
P
=ffD1:2gg
sin e,a ordingtoequation(3)inse tion3.2,the followingholds:
LT1Pos)D1:2
LT1
LT2
D1
D2
D3
observe LT1 = LT1Pos
LT1Pos
LT2
D1.2
remove D1.2
16.89
24.62
20.14
23.57
29.48
2
8
14
12
6
Fig.3.Graphrepresentingthesolutionoftheexampleproblem.Dashedar srepresentalternative hoi esto onsider,while solidar srepresenta tualobservationsanda tions.
p( N j )= p( N ) p( ) = 2 2 8 + 2 2 8 + 1 2 8 7 2 8 = 5 7
Similarly,theprobabilityof P
given is 2 7 . Inordertoestimatethe ost (
N
)we rstneed toestimater
N
(D2)(the otherabdu iblevalues in
N
are ground, therefore their ost needs not be estimated). Theground valuesD2:1,D2:2 of D2 havethesameprobability,andD2:1 ostsless thanD2:2, thus we onsiderthemin theorderof eÆ ien y(D2:1;D2:2).Wealsonotethat,assoon aswesolvetheproblem, we willimmediately de-te titatno ostfromthesymptomSym1 (equa-tion(6)); theestimated ostis then omputed as followsa ordingtoequation(5):
r (D2:1)=6;r (D2:2)=8 p(D2j N )= 2 5 p(D262 1 jD2)=0 p(D262 2 jD2)=p(D2:1jD2)= 1 2 r N (D2)=r (D2:1)+r (D2:2) 1 2 5 1 2 =12:4
Theestimated ost ( N
)is omputedbasedon thefa tthattherelativeprobabilitiesofthe andi-datesfD1:1g,fD2g,fD3gare2,2,1,their osts are8,12:4,15andthereforethesequen einorder of de reasing eÆ ien y is fD1:1g, fD2g, fD3g. Then,a ordingtoequation(9):
( N)=8+ 3 5 12:4+ 1 5 15=18:44
Let us onsider the estimated ost of ( P
). Firstofall,we omputer
P (D1:2)asfollows: r (D1:2:1)=4;r (D1:2:2)=4 p(D1:2j P )=1 p(D1:2:1jD1:2)= 1 2 p(D1:2 62 1 jD1:2)=0 p(D1:2 62 2 jD1:2)=p(D1:2:1jD1:2)= 1 2 r P (D1:2)=r (D1:2:1)+r (D1:2:2) 1 1 1 2 ) =6
Sin e, a ording to equation (9), ( P ) = r P (D1:2), it follows that ( P ) =6.The total expe ted ost asso iated withobservationLT1 is therefore: (LT1)=2+ 5 7 ( N )+ 2 7 ( P )=16:89
a ording to equation (7) and re alling that the immediate osto (LT1)ofperformingLT1 is2.
Regardingtheobservation!=LT2, ifthe out- ome of this observation is negative (LT2Neg), then theresulting andidate setis
0 N
=ffD3gg. On the other hand, if the out ome is positive (LT2Pos),the andidatesetis
0 P
=ffD1g;fD2gg. Theexpe ted ostsare:
( 0 N )=r (D3)=15 ( 0 P )=r 0 P (D1)+ 1 3 r 0 P (D2) =12:67+ 1 3 12:67=16:89 andthen: (LT2)=8+ 1 7 15+ 6 7 16:89=24:62
sin e the immediate ost of performing LT2 is 8 and the probabilitiesof
0 N , 0 P are, respe tively, 1 7 and 6 7 .
Theexpe ted ostasso iatedwithremovingD1 isasfollows,a ordingtoequation(8):
(D1)=r (D1)+ 3 7
(ffD2g;fD3gg)
sin efD1ghasprobability 4 7
in ,and, if remov-ingfD1gdoesnotsolvetheproblem,theonly re-maining possibleworldis
D1
=ffD2g;fD3gg. The omputationofr (D1)gives13:14.Asfor the ostof ,itsvalueis11:33+
1
giventhat D2 hashighereÆ ien ythan D3,and thatr
D 1
(D2)=11:33andr (D3)=15.
Theresultingexpe ted ost if we hooseto re-pairD1 isthen:
(D1)=13:14+ 3 7
16:33=20:14
Similarly,theexpe ted ostsforremovingD2and D3are:
(D2)=23:57
(D3)=29:48
The estimated osts of the alternative hoi es are reported in Figure 3. We hoose to observe LT1, whose expe ted ost of 16:89 is the lowest one.Letusnowsupposethattheout omeofLT1 is positive (i.e., LT1Pos); the andidate set is updated to
P
= ffD1:2gg and the fringe ' is updatedto fSym1Pres; LT1Pos;LT2g.
Se onditeration.Weneedtoestimatethe osts ofre ningobservationsLT1Pos andLT2,andthe ostofremovingabdu ibleD1:2.Asshownin Fig-ure3,thebest hoi e is toremoveD1:2, withan expe ted ost of 6. In order to removeD1:2, we startremovingitsgroundvaluesD1:2:1,D1:2:2 in that order (sin e theyhavethe same ost and probability, they have the same eÆ ien y, and thus theorderis hosenarbitrarily).After remov-ing D1:2:1, symptom Sym1 is still present (i.e., Sym1Presisstilltrue),sowealsoremoveD1:2:2. Now,Sym1 disappears,andwe on ludethatthe problemhasbeensolved.Overall,the ostpaidfor thissolution is10: 2forobserving LT1 and8for removingD1:2.
5. ExperimentalEvaluation
5.1. Implementationof the Method
We have implemented the proposed approa h as aPerl program. The models onsist in ausal graphsGasspe i edin se tion3;su hgraphsare storedinthe lesysteminYAMLformat,andare loaded into appropriate memory data stru tures whenneeded.
A key part of the program, starting from the ausalgraphG ofamodel,generatesthe proposi-tionaltheory T
E
orrespondingwith the explana-tory knowledge K
E
, as des ribed in se tion 3.2.
into an OBDD (Ordered Binary De ision Dia-gram), denoted asO(T
E
). OBDDs are a spe ial, anoni alformforrepresentingBooleanfun tions [3℄ that makes some important reasoning tasks
2
tra table,withalinearoreven onstant omplex-ity.Duetothese features,OBDDshavebeen su - essfully employed for knowledge ompilation in severalAIreasoning tasks,in luding planning[1℄ anddiagnosis[5, 19℄.
The implementation of theproblem-solving al-gorithm shown in Figure 2 depends on the avail-ability of an explanation fun tion that, given a fringe ', omputesaset of andidatesthat ex-plain the observations in '. Su h a fun tion is needed both to bootstrap the omputation, and to update the urrent andidateset afteranew observationismade.
Ourimplementationofthefun tionisbasedon suitable manipulations of OBDD O(T
E
). In par-ti ular:
1. weassertthetruthofthefringe'inO(T E
); this operation an be done in linear time w.r.t.to thesize ofO(T
E );
2. weassert the(negationof the) removed ab-du ibles inO(T
E
)(alsoin lineartime); 3. we extra t explanations from the resulting
OBDD by employing a well-known
algo-rithmforextra tingminimalmodelsfroman OBDD[9℄whose omplexityisexponentialin theworst ase,butusuallytra tablein pra -ti e;su hanalgorithmisslightlymodi edin ordertoenumeratethemodelsthat ontaina minimal set (w.r.t.set in lusion)of true ab-du ible variablesvals(A
1 )[:::[vals(A n ), ex ludinguk V
variables(inordertoeliminate non-leastpresumptive andidates).
Giventhis fun tion, theimplementation of the rest of the algorithm ofFigure 2was straightfor-wardlybasedonthe ontentsofse tion4.
5.2. Resultsofthe Experiments
In order to empiri ally evaluate our approa h, we ran a set of experiments. A main goal was omparing abdu tive problem solving performed byexploiting abstra tionsandabdu tiveproblem solving not relying on abstra tions,i.e., the ase
2
Problemset na nt ns h ba bt eb Na
SMALL 5 3 3 2 3 2 3 49.4
MEDIUM 8 3 3 2 4 2 6 104.8
LARGE 8 3 3 2-3 4 2 7 166.8
Table1
Parametersforproblemsets
Problemset to NOABSvsABS o ABSvsNOABS to ABSvsRND o RNDvsABS SMALL 3.829 1.117 4.417 2.166 MEDIUM 8.265 1.121 1.789 3.354 LARGE 18.622 1.101 1.919 5.663 Table2
Comparisonwithnoabstra tionsandwithrandom hoi es
wherethereasoningpro essisrestri tedto formu-lateonlygroundhypotheses.Moreover,we evalu-atedthe asewherefurtherlookaheadin ost esti-matesisused, toget loserto theoptimal hoi e. Thedi erentapproa heswere ompared interms of omputation time and in termsof observation anda tion oststo solvetheproblem.
Tothispurpose,weimplementedageneratorof randommodels. Modelsaregenerated basedona numberofparameters,in luding:
{ n a ,n t ,n s
numberofhierar hiesofabdu ibles, testsandsymptoms;
{ hheight ofthe hierar hiesof abdu ibles and tests;
{ b a
, b t
bran hing of the hierar hies of ab-du iblesandtests;
{ eb (explanation bran hing), number of ab-du ibles explaining a symptom: a larger eb providesmore andidateexplanations.
Threesets,SMALL,MEDIUMandLARGE,of ve models ea h, were generated, with di erent valuesforparameters,asfromtable1,whereN
a is theresultingaveragetotalnumberofnodesinthe abdu ible hierar hies. Observation osts in rease whengoingdeeperin thehierar hies,withan av-erage50%in reasefromoneleveltothenextone. For ea h model, a set of 50 ases was gener-ated randomly, based on the a-priori probabili-ties of abdu ibles; i.e., for ea h ase, a set of groundabdu iblesisgenerated|and,sin etheir probabilitiesare used,inalargefra tionof ases, is a singleton (i.e., a single fault in diagno-sis/troubleshooting).Theobservationstobe ex-plained for solvingthe aseare the onsequen es of .
{ ABSisthemethoddes ribedin thepaper; { NOABSonlyusesgroundhypothesesand
a -tions;
{ RND performs a random hoi e of the next observation ora tion (among the sets and 'ofrelevanta tionsandobservations).
The omparison is provided in terms of the average relative overhead of a method with re-spe t to one another, in terms of omputation time, andin termsofobservationand a tion ost paid to a tually solve the problem. For example, to
NOABSvsABS
providestheaveragerelativetime overheadofNOABSwithrespe ttoABS, andwe see that for the SMALL problems, the omputa-tion time of NOABS is almost 4 times with re-spe ttoABS,whiletheoverheadofABSinterms ofobservationanda tion ost( o
ABSvsNOABS )is 11.7%.
Weseethattheadditional ostofABSwith re-spe t to NOABS isaround 10%and doesnot in- rease with the size ofmodels, whilethe running time of NOABS divergeswith respe t to the one for ABS. We also see that ABS has an a ept-ableadditionalrunningtime(lessthandouble,for MEDIUMand LARGE)withrespe tto hoosing the next observation or a tion at random, while RNDhas,asit anbeexpe ted,una eptableand divergingadditional osts.
Table3reportsresultsrelatedto using, forthe SMALLproblem set, additionallookahead for es-timating thebest hoi e, i.e., tryingto get loser to theoptimal hoi e.
Column to provides the average relative over-headintimewithrespe ttotheABSmethodsfor variants, with lookahead 2, 3 and 4, of the basi
to o 2 10.156 1.046 3 27.355 1.048 4 71.784 1.053
Table3
Resultsforadditionallookahead
o provides the average relativeoverhead in ost (forobservationsanda tions)oftheABSmethod withrespe ttotheadditionallookaheadmethods. Aswe ansee,runningtimesin reasesigni antly andonlyprovideminor ostsavings.
The experiments on rm that the approa h in thepaperprovidesa eptableadditional observa-tion/a tion osts, with respe t to not using ab-stra thypotheses, with majorsavingson ompu-tation time. The experiments also illustrate that using further lookahead provides small savings while adding signi ant omputational osts. As observedintheintrodu tion,smalloratleast fea-sible omputationtimemaymeanthatana tion, even thoughpossibly suboptimal,is taken before itis toolate; in aspe i setting,the ostof de-layinga tionsmightbemeasuredinthesameunit asobservationanda tion osts.
6. Con lusions
In this paper, we proposed a novel abdu tive problem solving method whi h extends previous work on measurement sele tion in Model-Based Reasoningandonde ision-theoreti troubleshoot-ing.Unlikepreviousapproa hestotroubleshooting whi hdonotexploitstru turedrepresentationsof the domain (e.g., [13, 16℄), our work is based on arepresentationwithabstra tionswhereboth ab-stra t observations and abstra t hypotheses are takeninto a ount.
We present a general abdu tive problem solv-ing loop where, depending on the osts of obser-vations and the osts of a tions to be taken, a further observation may be hosen for dis rimi-nating or re ning urrent andidates, or an a -tion an be taken based on the urrent andi-date(s). In this respe t, the paper is also a sig-ni ant generalization of previous works whi h use ontologies or taxonomies of hypotheses for explanation/interpretation purposes, but assume that all of the observations are given in advan e
[20℄.Interleavingobservationsanda tionsrequires more sophisti ated reasoning, but the in reased exibility inthewaytheproblem issolvedallows for better solutionsto be found; in thediagnosis domain,this orrespondstothedi eren ebetween (sequential)diagnosisandtroubleshooting.
Costs of observations and a tions maybe very di erentat di erentlevelsof abstra tion:there is atrade-o betweenpayingthe ostoffurther ob-servations (ormorepre ise observations)and the one ofperforming unne essary a tions,or unne -essarily general a tions. Given that in pra ti al ases omputinganoptimal hoi eisnotfeasible, we adopt a greedy, approximate approa h from model-baseddiagnosisandde ision-theoreti trou-bleshooting,basingthe hoi e onexpe ted osts.
Theapproa hisaimedatbeinggeneral,be ause its motivations anbefound in several tasks and domainsin ludingte hni alandmedi aldiagnosis aswellasinterpretationtaskssu hasplan re ogni-tion.Di erentinstan esmaybederivedwith spe- i approa hes for representing domain knowl-edge and for generating and updating andidate explanationsbasedonobservations.
Nevertheless,inthe paperwehavealsode ned the syntax andsemanti sof aspe i knowledge representation formalismbasedon ausalgraphs. We havefo usedon su h arepresentationfor de-rivinganalgorithmfor the omputationof expla-nationsandforimplementingthewholeabdu tive problemsolvingloop.Theexperimentsperformed withtheimplementedsystemsuggestthattheuse of abstra tion results in a verylimited overhead on observation/a tion osts, while thesavingson omputationtime aremajor.
Referen es
[1℄P.Bertoli, A. Cimatti,M. Roveri, and P. Traverso. Planning in nondeterministi domains under partial observabilityvia symboli model he king. InPro . IJCAI,pages473{478,2001.
[2℄Ph. Besnard, M.-O. Cordier, and Y. Moinard. Ontology-based inferen e for ausal explanation. In Knowledge S ien e, Engineering and Management, 2
nd
Int.Conf.,LNCS4798,pages153{164,2007. [3℄R.Bryant. Symboli boolean manipulation with
or-deredbinary-de isiondiagrams.ACMComputing Sur-veys,24:293{318,1992.
[4℄B.ChuandJ.Reggia. Modelingdiagnosisatmultiple levelsofabstra tionIandII. InternationalJournalof
[5℄ A.Cimatti,C.Pe heur,andR.Cavada. Formal veri- ationofdiagnosabilityviasymboli model he king. InPro .IJCAI,pages363{369,2003.
[6℄ P.Cohen,R.S hrag,E.Jones,A.Pease,B.Starr,and D. Gunning. The DARPA high-performan e knowl-edgebasesproje t.AIMagazine,19(4),1998. [7℄L.Console and D.TheseiderDupre. Abdu tive
rea-soningwithabstra tionaxioms. InG.Lakemeyerand B.Nebel, editors, Foundations of Knowledge Repre-sentationandReasoning,pages98{112.Le tureNotes inComputerS ien e810,SpringerVerlag,1994. [8℄L. Console, D. Theseider Dupre, and P. Torasso.
On the relationship between abdu tion and dedu -tion.JournalofLogi andComputation,1(5):661{690, 1991.
[9℄ O.CoudertandJ.-C.Madre.Impli itandin remental omputationofprimesandessentialprimesofboolean fun tions.InPro .29
th
ACM/IEEEDesign Automa-tionConf.,1992.
[10℄ GerhardFriedri handWolfgangNejdl. Choosing ob-servationsanda tionsinmodel-baseddiagnosis/repair systems.InPro .KR92,pages489{498,1992. [11℄ Y.GilandJ.Blythe.Planet:Ashareableandreusable
ontologyforrepresentingplans.InAAAI2000 Work-shoponRepresentationalIssuesforReal-world Plan-ningSystems,2000.
[12℄ W.Hams her, L. Console, and J. de Kleer, editors. Readings in Model-Based Diagnosis. Morgan Kauf-mann,1992.
[13℄ D. He kerman, J.S. Breese, and K. Rommelse. De ision-theoreti troubleshooting. Communi ations oftheACM,38(3):49{56,1995.
[14℄ H.Kautz. A formal theory of plan re ognition and its implementation, 1991. In J. Allen, H. Kautz, R.PelavinandJ.Tenenberg,Reasoning aboutPlans, MorganKaufmann,1991.
[15℄ Evelina Lamma, Paola Mello, Mi helaMilano, Rita Cu hiara, Mar o Gavanelli, and Massimo Pi ardi. Constraintpropagationandvaluea quisition:Whywe shoulddo it intera tively. InIJCAI,pages 468{477, 1999.
[16℄ H.Langsethand F.Jensen. De isiontheoreti trou-bleshootingof oherentsystems.Reliability Engineer-ing&SystemSafety,80(1):49{62,2003.
[17℄ B.Neumannand R.Moller. Ons eneinterpretation withdes riptionlogi s. InH.-H.NagelandH. Chris-tensen,editors,CognitiveVisionSystems,pages247{ 275.Springer,2006.
[18℄ D.Poole. Explanation,predi tion:anar hite turefor default,abdu tive reasoning. Computational Intelli-gen e,5:97{110,1989.
[19℄ P. Torasso and G. Torta. Model-based diagnosis throughobdd ompilation:a omplexityanalysis. Le -tureNotesinComputerS ien e,4155:287{305,2006. [20℄ G.Torta,D. TheseiderDupre,and L.Anselma.
Hy-pothesisdis riminationwithabstra tionsbasedon ob-servation and a tion osts. In Pro . Int. Work. on
[21℄ A.Valente,T.Russ,R.Ma Gregor,andW.Swartout. Building and (re)using an ontology of air ampaign planning. IEEE Intelligent Systems, 14(1):27{36, 1999.
[22℄ H. Warnquistand M. Nyberg. A heuristi for near-optimal troubleshooting using AO
. In Pro . Int. Work. on Prin iples of Diagnosis, pages 197{204, 2008.
[23℄ J. Zhang, D. Caragea, and V. Honavar. Learning ontology-aware lassi ers. LNCS,3735:308{321,2005. [24℄ J. Zhang, A. Silves u, and V. Honavar. Ontology-drivenindu tionofde isiontreesatmultiplelevelsof abstra tion.LNCS,2371:316{323,2002.
