Download Choices Without Backtracking - Association for the Advancement of

From: AAAI-84 Proceedings. Copyright ©1984, AAAI (www.aaai.org). All rights reserved.
CHOICES WITHOUT BACKTRACKING
John11 dc Klccr
Intcllipcnt
XEROX
Systems
I.aboratory
Palo Al to I<cscarch
3333 Coyote
Palo Alto,
Ccn tcr
IHill Road
California
94304
choices
at once,
is cxtrcmcly
for tasks in which:
attribute
many
no ‘I’MS
can do much
(hut
many
not
number
of
ncccssarily
howcvcr.
thcrc
altcrnativcs
Ii~l~LJll~l~CS, the
1~1th rcqllirc
lnaking
choices
fcjr- dc~tling with choice
am011g aitcrnilti\cs.
1980). ‘I’hcsc
for CVCII simple
bc WOCI~III~ initdcqtlatc
‘I‘hc K~SOIIS for this arc twofold.
one
with
multiple
in both
all the memory
L;II ioul;
Klccr
that
contradictory
of Sgmbolics
and
lhu~vn.
‘I‘hc
filr as memory
space is conccrncd:
as problem
‘I’his
paper
prcscnts
choice mcchnnism
tasks and designing
actually
for
hits
kinds
qualilativc
hccn
;I matching
‘I‘iming
the number
tasks.
tl~y
‘l’hc
used
i9X4)
is in the noise).
disjunction
‘I’MS
proble~ns,
str,~tcgy
ijl>d
proposed
successfully
in
in this
in (dc
Klccr,
with grcnt succcss (time
spent
It is atso used as the nlcchi~nism
in a constraint
I:~ng~~gc under
order
t:lsk
(rcportcd
1982)
analysis
(dc
shows
in the backtracking
is a misnomer
of justifications
grows
solution
a gcnclal
anntyzing
for a class of problem-solving
mcchnnism.
This mechanism
multiple
is
contradictory
79
01‘ dcri\ ing
infcrcnccs.
dcvciopmcnt.
‘I’hc rc;lsoning
solving.
and
;I data
ing process.
new
simplified
model
sol\cr
Most
infcrcnccs
base fi)r recording
option.
I.~Ic~ choice
Inay
involve
to bc contradictory
from
bc made
for problem
solving
to bc incorrect,
substantial
or fruiticss.
to proceed.
problctn
the
of ~hc problem-solving
Arta
must make choices aml~ll~ which
it proves
of
systcnl consists of ;I proccdurc
;~nd previously
All thcsc arc added to the data base. Somctimcs
problem
discovcrcd
as
problem
problem-sol\
consists
nladc
of this pnpcr an cxtrcmcly
sol\ ing sufliccs.
for performing
fill up
to using
choice
s;ltisf‘lction
and
i\nd I~Iww~,
assumptions
slate of the
i\I’C
It is the result of cnrcfully
as any ‘I-MS for the task, can handle
constrilint
ITi~SOllillg!
implcmcntcd
For the purposes
problem
proceeds.
nccdcd
is IIO
(a stiindard
t0 iI\‘Oicl SllCll hi)lCS). ‘I’llCSC six rcquircmcnts
to
something
problems
(f:orbus.
reasoning
an altcrnativc
such ;IS a TMS.
the kind uf backtracking
as gcncrdl
solving
time to cxplorc
of choices
(Q thcrc
from
incapabic
Second,
simple
of its time
“non-rnonotollic”
lTlOllOtlUliCilll~
at once -
rcaroning
spends the majority
term
reasoning
reasoning.
1983)).
the number
;I priori;
(c) the
cxclusivc;
of
for h;~ndling
have proven
or 3600 in short
1984) (Williams,
the rcasoncr
algorithms.
l-M-2
sjstcms
choices
in quittitativc
if:
and
packilgcs
dcrivcd
qu;llitiltivc
time and space. Very
rccc;~rchcrs
Various
primarily
they arc iutrinsically
needs LO do aII the Gmc in qualit:ltivc
very incficicnt
by
I:irst.
the choices,
IO IX known
infinite
bcttcr
finite
topics of my rcscarch,
have been dciclopcd,
(II01 Ic, 1079) ;IIKI (McAllcstcr,
of working
primary
arc
bc controlled
handling
and con\traint
fol
(c)
arc finitely
and choices.
pcrt’orms
choice
bcttcr):
(d) thcrc
many
for
1979) and (dc KIWI.
rc;lsoning
ic probably
solutions
each
one is only
hold
paper
Qualitative
in
the goal (if
‘INS
sclvm~
of 111~choices
rcquircs
(b) the user is intcrcstcd
CiIIl 0liCll
pirticul,lr
of this paper arc h0r11 out of frustration.
for
is no ncccssity
single .<olution which
‘I’l~c rCSlill:i
bounded)
to
on,
arc consistent:
~hc proposed
or the ;Iltcrll;ltivcs
bc possible
it dcpcnds
achicvc
a standard
of assumptions
Addition:illy,
is appropriate
‘J’MS it must
good;
which
in i\ single solution,
few combinAons
tcchniquc
to a small set of antcccdcnts
or all of the solutions
intcrcstcd
The
(a) as in a standard
all conclusions
othcrwisc
cfflcicnt.
thcrc
additioni~l
Clowcvcr,
If a choice
solvers typically
the
is no prcfcrrcd
work
bcforc
a choice
must
is subscqucntly
backtrack
tu wnc’
The subject
cfficicnt.
However,
additional
impt-ovcments
infortnation
when
has produced
cxplorcs
S,
cannot
bc avoided.
can bc made in the preservation
of rclcvant
a choice
data-base
itnplications
of sLttc
sotnc action
using
the problem
{A, B, C}
{A, L?, D}.
{A, B, D}
and
state that
Al
which
contributed
iS discovered
result
if the
fratnc
can
problem:
fi)llowing
II,
task
one of E or F,
problcnt
solver
this ortlcrittg
the
problctn
solbcr
which
perfortns
(It must first do one of A or B, lltcn
scqttcncc.
then
of
would
and then
C.
Adtnitrcdly.
do G first as it docsn’l
best brings
the
a choice
-
but
to {B, U}
infcrcnccs
to address.)
coniplcx
rcprcscnt
potcn-
;ttc itI1 ~hc possibilities
(or itll solutions
and
used strategy
try
arc fotttld):
each
one
{A, (3, E, G)
is cxponcntial:
ttntil
‘I‘llus
{A, C, F, G}
\ttggcsts
a tnodi~ic,ition
c!plic)n is ;tttctrtptcd,
problctn
{D, I’}
solver
bitt
wlicnc~ct~
backtracks
to the most
(A} {A, C} {A$}
often
so this
cnutncrntion
rcccnt
This
whcrc
p,c,I;‘)
lhc
;I
contctdiction
If {;I, C}
itnd
choice.
can
current
{B,c,F,G}
{B,D>
{Ll, C}
advant‘tgc
sets of
of this tcchniquc
options
than
cxplorcs
four
complctc
strategy
is called
applications
Chronological
{C, G}
(Rulifson,
backtracking
far more
cnumcration
work
than
has three
ncccssary.
Chronological
cxamplc,
cxpli\rcs
and
IIcrkson
this
eight.
one
of
scriotts
faults
Consider
backtracking
This
starch
{AC,
E, G}
{A, C, F}
{A, C, J’, G) {$D}
C v D, backtracking
..- (4
As G IS inconsistent
is not
result
tcchniqucs
tlCCCSSilry
(so far WC have
algorithm).
in the
ordering
to the last choice,
C, G)
with
to
the
itt~ttlcdiatcly
from
choice
backtrack
‘I‘his
the dcpcndctrcy
future.
l’ntrics
‘t‘hcsc
choices
‘lrc cnllcd
which
problem
the
arc mutually
of chronological
twice).
some option
records
once.
records
c,~tt>cci the contradiction,
on {E, G}
‘l’hc
dcpcn-
is included
citn bc consulted
arc nlilrkcd
front
in the
to dctcrminc
’t’hus. the conscqucnccs
‘I’his can bc affcctcd
xc
of {IT:, G}
quite
as tctnporarily
directly
unavailable
the set of choices
the biiSiS of the ‘I’MS
19SO). In the tnorc
to specify
been
‘I’hcy,
prcsutning
in cffcct.
can bc controlled
It is important
the overall
the sets of options
E V F
will
80
find as many
stratcgics
gcncrnl
cttrrcntly
ordering
~omcwhat
their
own
strategies
of the starch
by specifying
which
it
space
cnumcration
cttumcration
but
this
parts of the
first.
to note that all thcsc strategies
that
of (Doyle,
‘I’MS
some bimplc-tnindcd
choose
the choice
i.e., E from
‘I‘hc
C is it choice
b; httt 6 is it CO~SC~~CIICL’of a and
of those options.
search space to explore
two steps arc futile.
with
if they arc not dcrivhblc
‘I’hcsc
tltc case where
will
in lhc
‘l’ht~s. whcttcvcr
1979) and (McAllcstcr,
1972).
which
a
the CxittnplC
arc a\J;til;tblc.
the contradiction.
choices
by working
bc dctcrtnined
out)
When
being cxplorcd.
its early
ottd Wibldingcr,
(illustrated
the data bnsc.
(i.c.,
it
order:
The second
of C frotn
sets, while
far fewer cotnplctc
lit
cntttncration.
chr~~n~~logi~;~l backtrAcking
is inconsistent.
following
is that it cxplorcs
bt-tttc-force
was in QA4
in it doing
within
inllucnccs
is discovcrcd
bc avoided
set, the dcpcndcncy
need only
bttt
records also solve the third
the conscqucnccs
p,n,E}
OIICS.
Rcconsidcr
to.
1979) as they rcprcscnt
this is also rccordcd.
is:
then
thCsC
by maintaining
sho~~lcl b;tcktrack
which
of 6 OII a is rccordcd
dcncc
bilSC,
IWOI.~S arc consulted
SOIVC~ should
which
to dctcrtninc
choice
backtracking
(6 D, E, (;> {B, DD,J’)
‘fhc
Of
r~~~rllr//rlr’rrc.~‘-~~/f~(./e~~
hkrrtrcki~rg.
is citllcd
1)cpcndcncy
each
is dctcctcd,
{A, D, E) {A, D, E, G} {A, D,Z~‘} {B)
{B,C,E,G)
thcsc
of choices.
an inctmiW2ncy
the search order
in
SpilCC
rcdcrilc
on citrlicr
such records
solver
choice
;trc consulted
{A, D, X, G}
And
subsets
01’ the bruteforce
arc ittconsistcnt
{~,C,zq
in stnitll
tllC
scar&
is cnablcd
G is given,
the problctn
Whcncvcr
is f(jund
that
pr~bicm
rcccnt
contradictory.
arc inconsislcnt.
bc dctcctcd
rcsulls
is SOICIYtlcl>ctldctlt
and fittally
in fcrcncc
G when
to the most
Ctsu,~lly many
can
opci~~tliotls thn
(II, I^), 13, C}.
to bitcktr:tck
C V D. In gcncral,
Enutncr-
a solution
the
r~~goo~iscts (Stcclc.
of’ the combinations
of chronological
tl, tllC dLlt:l
thcsc dcpcndcttcy
with
t.ccc)rds state
{A, D, F, G} {U, C, 15,G} {B. C, F, G} (f-3,LJ,E, G} {U, D, F, G}
inconsistcncics
it
sh(~ltld
both I? and G cwicc.
{I?‘, (:}
Lhc infct-cnccs.
choice
C is inconststcnt
tcchniquc
0 liI)lll
of cxh
which
-1
v v P’
,~nd most ottcn
Once
sohxr
{E, G}
tlliit
to all three of thcsc dcfccts
to dctcrtninc
dcpcndcncy
operations.
‘I’hc simplest
effort
cxploritJg
ix cncountcrcd
wltcrc
and the lcttcrs
erasing
while
contradiction
C v D.
tially
solving
the combination
rccultitt,
records of tltc dcpcndcncc
CvD
arc cxclusivc
dcfcct
problem
backtr,tckin, 0 might
Chronologic~~l
A solution
G
the disjunctions
‘I’hc final
$0 it will do any cot~t~)tttitti~~t~S in\olving
backtrack
cr,wd
AvB
Assume
IIIOI’C
prohlctn-solving
It will add tllc infcrcnccs
ottc of C ot
any well-dcsigncd
rcquirc
out the issttcs I want
ag‘lin.
and last step.
the pt’oblctn
{ 13,c, I?‘,G} { 13,D} {I?, II, I?, G}
ln doing
the
of tllc
a
to it choice
not to the most recent choice.
by the third
that choosing
When
backtrack
SCtS iIS:
aSsutnption
is pcrformcd.
l‘t:CI INIQCIKS L;OH I)l;,,\I,lNG \%‘1’l’ll CtIOICK
Consider
Suppose
dc:tl
should
is inconsistent
that possibility
on E and G.
stittc is changed
{C, G}
iS th,tt it rcquircs
ncccssary.
i\ grc;tt
is illustrated
that
*lcvcr cxplorc
on the contradiction.
lhc scar&
to the contradiction.
dcfcct
b:tcktr;tckitlg
‘I his problctn
of the classic
as it has no influcncc
is discovered
is how much
wo~tld
Of tllC pt.oblcln-solvitlg
has no effect
contradiction
‘I‘hc second
solver
subscqucntly
‘I‘hc question
wcrc cxplorcd.
version
I~~llCll Of tltC description
when
Suppose
in the data-bnsc
as an “intCl’llill”
choice
is retracted.
state S,
of choices
bc 1 icwcd
information,
of choices
;irc valid
&nscqucnccs
IlOW
of this paper is how this process can bc made mot-c
Without
arc cxplorcd.
consistent
solutions
‘I‘hc
most
are equivalent
sophisticated
as pure cnutneration.
in
TMS
The goal
is to enhance
efficiency
without
sacrificing
cxpcnsivc
completeness.
operation
I'HORI,I:MS
Truth
WITH
maintcnnncc
For dealing
However,
circumstances
multiple
solutions,
two equally
Given
‘I’his
plausible
makes
solutions.
B, C, E, G arc both
only
allow
it cxtrcmcly
Howcvcr,
solving
.-
admits
one solution
to cxaminc
to bc
this is often
ditTcrcntial
both
exactly
diagllosis
what
cotrlrfldicliotl nsoidcrtlce.
OVCriCOlOUS
In
D will
this
IIN
is not ncccss;lrily
cast,
IX.
the
and
A and R is of no vnluc.
if B
of
Ihit
dccidcs
way to change
direct
global
All
in some way.
manipulate
‘I’MS
is lhal
gu‘irantccs
One inctcgant
This
rcintroduccs
and
later
rcsct
transfcrrcd
The do~uinnnce ofjus/$cnfions.
Furthcrmorc,
is context-dcpcndcnt:
as probtcm
and
hcncc
particularly
solving
the
proceeds
assumptions
problematic
the assumptions
underlying
to find
it is very
a solution
gcncrat
that
often
satisfies
The
spends
‘TMS
carlicr
but problem
tilsk. fix
solving
‘I‘MS
which
Of ttlc collScqLICl1CCS
styles
of solutions
though
to this
is of no
of (13, G}
without
task, IWIW complctcly
OCCII~‘S
;I contradiction
could
bc allowed
miiy
bc spent
to an overall
a siupshot
of
the
advantage
of Ihc previous
which
the cornpulation
co~~scq~~c~~cs
from
by looking
should
steps arc rncmoi/.cd
(dc Klccr
GCI)
from
Another
state
(its
time.
{I?, G},
(3)
taking
at the co~~scquc~~ccs and
without
bc unoutcd.
tcchniquc
taking
All
is just
ilIly
effort
cxpcnsive
so no time-consuming
to
problcm-
steps arc rcpcatcd.
1980) LISCS this
and Sussmnn,
OII a set of
(2)
at a later
(4) ‘1‘1~~casicst
{E, G}
analysis
plohlctn-sol\lcr’s
examining
result
working
soluiion.
thC c~)l~lpllt;ltion
ones arc missing.
during
to go on. ‘t‘hc difficulty
to rcstilrt
My
whose
current
For
Thus,
Lcchniquc
to
conlputations.
change.
‘t‘his
algorithm,
amount
of
cxamplc,
B is lab&d
is
c:lch
nsscrtion
each assertion
with
notate
time
it:
preceding
A particularly
81
with
<assertion,
infcrcncc
each assertion.
(assumptions)
derived
from
dcrivcd
(For
its assumptions
as:
which
assumption
if z =
B
clarity,
then
I’ll
WC
call
1, {A},>
A and
assumption
dcducc
y =
-1
the combin,Ltion
and justifications
if <z =
to its
ir holds.
A is labclcd
1 under
{assumptions},j.u.slification(s)>.
is written
in addition
under
from both assumptions
‘f’hus
assumption
set {A, B}.
assumption
of an assertion
be-
with
the set {A, D].
A and 5 -I- y L- 0 under
consult
partly
is to include
the set of choices
with the set {A},
justifications
must often
solution
justifications.
under
all the justifications.
may
ttlC
A C1;,NI*:RAI, SOI,U'L'ION
support
a surprising
is CXt)lOlTd
uses justifications,
node
assertions
to go
within
node being out.
solvers which
D, I?, C}
‘l‘hc dillicutt
bc irrclcvant
cache all symbolic
for assertions.
The machinery is cumbersome.
cause
garncrcd
to working
b;lcktracking
computation.
may
For cxnmplc,
the
for it
{II,
possitdc
1979) calls an assumplion
is any
underlying
and justifications
solely
on some other
for problem
from
Set
It is also
solving
,my point
this
OINX
based 011 {E,G}
C;III bc rcactivatcd
utilized
Suppose
ttl3t
~011ing ctfort.
is no Iongcr
which
see which
of TMS
problem
task ~UCUC)
is satislicd
to
not so simptc.
is C~~lltl;ldiCl~~l~y but
of {E, G} can bc included.
is to store
to rcslart
dat:!basc
Information
A ‘I’MS
the
of
to another.
what (Doyle,
dcpcnds
strltc.
~\dditic~llill
(13, C, E, C} was ncvcr pcrmittcd
tllC
a
set
C, E, G}
set {II,
without
dcpcndcncy-dircctcd
;I great deal of cIl;)rt
that
of
records assures Illat
Ilot illt infcrcllccs
for {E, G}.
(1) f:vcrl
is ttl‘lt
pending
is rhat it is contradiction-
to the spirit
WtlCil
arc four
tcchniquc
is no way to specify
1.11~cnlirc
an assumption
justification
hcrc
the
notion
thcrc
III p‘lrticular.
(tic cntirc
later
in the first
is unfortunately
is discovcrcd
IllildC.
is explored,
time
Set {II, I>, I?:, G}
htil[c and thcrcforc
conscqucnccs
choices
status
and out (not
the option
after cxtcnsivc
this.
Suppose
justification
until
of {E, G} this computation
a
time
in (hclicvcd)
rcsutts
some
the set {C, E,C}
to a
so the knowlcdgc
that is somctimcs
backtracking.
is not readily
not assumptions.
OCCll
this
often
set (13, C, E, G}
then
{ 13, E, G}
from
satisf,tctory.
of the s,tatus and justifications
is antithetical
chronological
one snapshot
to faciiit:ltc
and
‘I’hc situation
‘I’hcrc
solver
rcsponsc
altcrcd.
CiIClI
mcchanisnl
then
approach
in
the option
aid, is IlOW ti) lilt the “gilpS”
another
problem
the
bctwccn
‘l’lic use of dcpcridcncy
dcribcd
must contilluc
bctwccn
until
During
Worb on the situation
dcrivcd
infcrcnccs
is that a ‘I’M!3 has no useful
states is to take snapshots
of each assertion
supporting
IlilVC
arc rcsolvcd,
lllI.Oll~h to ttlc Secc~lld
to conclusion.
on both
is no way to go back to a previous
for thcsc oddities
stale.
snapshot.
begins.
all contradictions
is cxplorcd.
the conlracliction
This
set is to introduce
‘I’hcrc
can guarantee
thcrc
not
bc rcnmvcd
achicvcd.
All a ‘I‘MS
rhc
choice
is irrcconcilablv
of state was somchow
rcnson
that
rncchani~nl
it cannot
solver
So, in parlicular,
The
to draw
abandoned
(i.e.,
the current
but once added
state.
a choice
is IIO convcnicnt
the problem
the target
be.
of a contrirdiction
Suppose
change
‘I‘hcrc
free.
not
of the contradiction
backtracking.
in this ca,lmplc
redoing
‘1’1~ only
change
CillTy
back-
may require
resolution
Suppose
on the current
is
a contradiction
dcpendcnt
important
of A or H being
is d#icult.
slalc5
lo temporarily
of
All
if A
is cncountcrcd.
contradiction,
infcrenccs
will
that
B arc
that
A will
t.lctic.
it is still
contradiction).
StiIlc
guar:~n~c
is bclicvcd,
A discovery
in one
result
.SwiIcIIiug
the
The backtracking
rims.
computation.
one
the dcpcndency-directed
Eventually.
is discovcrcd
{II, D, B, G}
to dctcrminc
A and
Suppose
will
is that any infc:cncc
from A and B indcpcndcntly.
contradiction
‘I’MS
the best problcnl-solving
A and B indicntcs
A and 4 will
much
imny
contradiction
to compare
from
may have changed
was not discovcrcd
contradictory.
bctwccn
after
Unou/itr~:.
the best solution.
bclicvcd,
only
some assertion
suppose A, D, E, C and
It is impossible
thcsc states simultancousty.
which
difficult
For example,
solutions.
w<lnts to do in problem
but
which
contradictions.
bclicvcd)
a set of choices
the ‘I‘M!3 algorithms
at a time.
mechanism
limitations
can bc avoided,
The si~zglc slafe problem
considcrcd
they have certain
result
scnrch, and tic
in other
systems arc Lhc best gcncral-purpose
with choice.
in appropriate
cxtcnsivc
USING TMS
can
in rcstx~~~sc lo a contradiction.
tracking
a value
‘I’hus,
and <z +
and
the
y =
0, {B},),
then
is rcmo\cd
from
For cxamplc,
and <a: =
0, {B},>
O but this pro\,idcs
tlowc\cr.
thcsc
it would
Abstractly,
problLm
c~cry
possiblc3
problem
solver
set disco\rcrcd
discovers
the combined
on it or any
‘I’hcn
val~~cs with
sets is crascd
step
b) whcrc
f(n,
the
interaction
COIIIC known
schcrr~c
dots
cqui~alcnt
can
f
with
uhosc
have
noLion
assumplioll
only
r-cquirc
pcrforni
infcrcnccs
using
the
problem
OhlClll:~
and
the
discuss4
the
basic
oniy
two contr,ldictory
Snilching
irrclcvant.
is rcmoccd
should
cntrics
VUIllC
this
‘I&C
intcrcsting
VillUCS
SCt.
-
exploration
that ilIly
‘I’hc
assumptiotl-t~~lscd
is
supcrsct
it is not
a value
underlying
solutions
to coexist.
‘I’hus,
mechanism
mode
contain
dncs not tcrminatc
those assertions
schcmc,
Suppose
assertions.
no more,
slilles
no
This
is exactly
which
the result
carry
as a sllbsct
{E, G}
part
arc
of
knowlcdgc
dcpcnd
approach
that under
dcsircd
cxamplc.
from
<Z + y = 0, {El},>,
a
this situation
ICSS.
is cijicull.
A state is complctcly
Suppose
Changing
spccificd
state
is now
trivial
y =
contradictory.
or
but
-y : <.z =
y =
211ic
whcthcr
not ncces~ry
to rcmovc II. bccawc
unhkc
a convcntion;ll
logid
system
;\
contradiction
dots not ItIl;lly cvcrqlhlng.
I:or some !nsks. 3s polntcd out in (Martins
antI Shnpuo. 1983). thcrc IS Sony utility m dcrwng
further contradictory
V&YZS.
-1,
incficient.
only
82
is an inclcgant
carlicr
{E, G}
{G, H}
arc derivations
{E, G}.
from
1
a simplified
(Y : <z =
1, {A},>,
p :
0, {A, B},>.
In
not.
is discovcrcd
1, {C},>
This
fix to this problem
problem
techniques
which
assumptions
lntcr, <y =
has conscqucnce
unouting
or justification-based
and lhcir
z =
Consider
exists
arc used.
WC l~avc implicitly
in this discussion. * two values arc considcrcd
if both their assertion
an
from a and ,O as the set {A, B} is
1, {C},>
‘I‘hus. <z =
dots
(i.c.,
1 using {E, G}
of z =
solver dcduccd
if c : <z -
1, {A},>
assumption-based
Thcrc
adopted
the
1 and has conscqucntly
assumptions
thcrc
is not dcrivablc
Howcvcr,
but <Z =
part
(and
fails to address all
1, {A, B},>, and X : <Z =
---I, {C, B}, (A c)> IS
‘. d crivablc.
by a set of assumptions.
urdcr
not under
the problcnl
-1
ncvcr
the assumption
that z =
In addition
{G, H}
on the
avoided.
automatically
{B; D, G, G}
Not all conscqucnccs
to {G, II}.
MC
a
1 is also dcduccd
under
mcrcly
infcrcnccs
&&=2n3
derivation).
over
possible
i.c.. ilIly
process of dctcrmining
J0
of two con-
arc cxplorcd
for thnt matter).
has dctcrmincd
allows
moving
to i1 contradiction.
as if the contradiction
from
also
Consider
{B, C, E, G}
CCilSCS,
{B, C, E, C}
continues
arc
the difficult
z =
mark
while
all possibilities
.Z=t
and that
arc
unlcs~ it
rcsolvcd.
assertions
within
the nssllinption-based
the
it is simple
work on the ovcmll
arc rcmovcd
rcmovcd
to explicitly
is partially
of prcscrving
dcrivcd
problem.
solver
gone through
is
a contradiction
is ncvcr
of that StatC
{B, C, B, G}
the problem
indcpcndcnt
‘I’hc prcscncc
ncvcr
let alone dcpcndcncy-
ncccssary
a contradiction
hcncc
Unfort~~natcly,
bctwccn
schcmc
of the
underlying
underlying
problem
{B, D, E, G}
Assertions
cvcry
-
311~~1
cxtremcly
SC~Swhich
on state
contradictory
tllC
thus
implies
'I'llCll.WllCll
addrcsscs
it is easy to
the presence
or disbclicvcd.
Iicncc,
of
of
solution
The
once added
assulnption-bnscd
of the unouting
IiCgilrdlCSS
base.
Icast;
implies
of any kind -
‘I’hc assumptions
A \lalllc
silnl~ltancously.
involving
assumptions
sets of
it is easy to find
of b arc a subset
the justifications
to the ‘I-MS problem
ilSSLllnptil~llS
modes of intcmction
of an assertion
b if the assumptions
~>crlni~l~cntly,
In the simplest
a set of
occurred.
nssuniplions.
while
while exploring
not juslifkations
from StiltC {I?, C, E, G} lo (13, D, E, G} in rcsponsc
SpXC,
WllOSC
or the
iJtrurr/itrg. ‘I’hc unouting
Of tllC solution
th0SC ViIlllC$
assumptions
is no backtracking
as bclicvcd
the analog
two solutions.
tr;~tlic~~>ry assertions
contradiction
solving
Work
Overzealous cotllrarlicliott avoidmcc.
rather
backtracking.
‘I’hcrc
mode
;I pilIT
cxamplc,
The tttnchittery is cutt&mott~e.
idcntifiablc.
context.
transferred
it is easy to compare
For
assertions.
Also
directly
that
a set of
In either
is dcduccd
As assumptions,
mode
carlicr:
contradictory
many
to compare
of u).
A more sophisticntcd
assumption-based
The sittglr skr~c problm.
arbitrariiy
(a implies
dircctcd
SClCCtS illI tllOSC
set of
data
of another
assumptions
from
NOK
1, {E, G},>
1 will still bc prcscnt
the prcscnce
base.
add
(i.c.,
arc “automatically”
if <s =
the most
Z:
values
state
context
simultaneously.
change.
is done to the data base.
solver
01 inlcractic;n,
the
with
whcthcr
daL\
schcn~~ is just
set of intcrcsting
is discovcrcd,
bul nothing
only
of
set A,, IJ At, a supcrsct
of
assertion
simple.
problctn
base of
notion
to bc this cxtrcmc.
the
vaIlIC
and p : <b, A,,,>
any
it
assumptions,
the
assumptions.
‘I’hcsc arc just two of many possible
stiltc,
some
SCt Of ilSSlllllptiOl~S
wo\~ld IX to cxplorc
:I contradiction
from
one
rcprcscntational
underlying
dctcrminc
and cvcry
in
example,
{B, C, E, G}, then z =
assumptions
the the
set is a SubSCt Of tllC COntCxt’S ilSSul~lptiOn
arc iI subset of the current
chnngcd
set of
1 term
f<)rmt~liltctl
data
~~ssumption-based
it
implicitly,
of ilitcr‘lction
or
in the
It is not ncccss;\ry
pi
bc
takes
the
cy : <a, A,,,>
form
con\radictory
not
:ls5uniptions:
the
contt.adictr~ry
For
The dott~itzatzce
ofjustifcotiuns.
this
Whcncvcr
on this list,
obtained
values
arc the dominant
sysbans.
bctwccn
CXE,
is
A list is maintained
b), A,, U A,,, (cc, is),> unless the assumption
<f(a,
ix..
interaction
set is placed
of its super
li)r all \,,~lircs of
of
of
to bc contradictory.
problem-solving
u clad b dctcminc
work.
Iwo
assumption
S~upposc cvcry
bc:
mode
solver and the dntn base is as follows.
;\ssumptioll
b,iscd
not justifications
to irtst~~i.cItiot~-Dtr.~c(j ‘I’hlS
to a current
{B, D, G, G)
0, {A, B},>
As
can bc restricted
or all states can bc cxplorcd
cxploriiig
z =
set {A, n}
<Z -1. 4 =
solving
assumptions)
to another.
<S =
0 individw,d]y.
the assumption
based on assullll)~ions,
one
1 or 3 =
contained
both
1 contradicts
z =
z =
th;rt
Problem
the same
the set {A, El} is c(mtladiCt(~ry.
bccausc
is prim,lrily
SCllClTlC
imply
trs~rtttrptiorr-6~7sctl
;IS opposed
can contain
dilKculty.
about
if the dntabasc
bc rcmovcd?
where
of times, a value
assumptiw set is found to
if its
without
vnlucs
‘I’hus,
a ‘I‘MS
number
the database
no information
two
contradictory.
Unlike
in and out an arbitrary
the data base only
bc contradictory.
1, {A},>
{A,B},>.)
-1,
<y =
node can bc brought
the same
arc the same. ‘Illis
is
contrary
to the way TMS’s
their assertion
simply
is the same). Thus,
changing
produced
for both
proach.
1)cpcnding
produced
but unouting
justifications
to find more clcgant
approaches.
in the nssLllnption-based
results
by
(dc
is still with US.
solutions.
approach
than
which
inadequacy
After
ap-
problem
the
assumptions
altcrnatc
solver
will
If the
problem
arc cqunl
f:or
in
many
For
throw
muitiplc
for quantities
problem
away
derivations.
possible
out
all
values
of the asslunptions
solver should
throw
that
using arc logically
results
but
Mow
of some
Another
dcduccd:
should
the
goal
problem
For
throwing
is to discover
the
problem
all
set CM
bc nrrivcd
cxatnincs
that
arises if derivations
base contained
1, {A},>,
(a, p, p)>,
<y =
‘l’his
last vnluc
is incohcrcnt
a diffcrcnt
a : <CC+
three
2, {A},
derivation
for
(CY,7,~)).
in that
z each
explicit
of the assumption-based
simplest
its derivation
approach
consistent
state
dots
not
appear.
it
quickly
must
many
suggcstcd
global
globally
termination
consistent
sets inferprekdiorrs
the
in
this
paper
it is not
cvcn
consistent
of
state
the
states,
if
problctn-solving
is often
rcquircd.
any,
thcrc
effort
WC call
and the process of computing
arc.
some
I Icrc
I prcscnt
can bc
or bit-vectors).
difl’crcnt
‘f’hc same
cotnbiniltions
of
sets. and
(b) quickly
carlicr.
‘I‘hcsc goals
once a set of assumptions
its unique
structure
is
as
can bc marked
operations
1illtiCC
(this
of the assulnption-based
they
ci\n
Such
that subsct/supcrsct
is only
bc optirnircd
possible
record
is to maintain
whcncvcr
;I IICW set is crcillcd
dctcrminc
whclhcr
computed
and access the nogood
by
this operation
data-structure
As cvcry
the fact
by a simple
that
if the sets arc
assumption-based
sets.
‘l’hc
a list of all the contradictions
unioning
the new set is a supcrsct
cfflcicnt.
an
C0lTlplltiltiOI~S
of course
approi~chcs,
algorithms
by crc&ing
two
need only
set is cntcrcd
time
the lattice
of some
for ordcrcd
can be
structure
nogood
sets with
to
set.
once per
manipul;~tion
of the nogood
ti\kcs linear
nogood
bc pcrforrncd
into
it is a supcrsct
and
is chcckcd
of any known
contr;ldiction
in tcrscction
it
set is
the subsets
data structures).
the
when
a new
contradiction
is discovcrcd
it is a simple
known
to mark
all its supcrscts
as contradictory
and stop all problem
However,
notion
the global
them
itilplcinctitatiol1
for sc& and a hash table for thcsc
for cxnmplc.
sornchow
tcchniquc
matter
how
and
options.
many
form
thcrcforc
As sets ilrc uniquiscd
is that
With
which
to (a) uniquizc
f .ikc ~hc justilication-l,nscd
appronchcs
bc
‘I’hus
proceed
Izurthcrmorc,
at the
as
for some ilSSCITiOI1.
approaches.
lists, arrays
unioning
‘f‘hus,
Subsct/supcrsct
uniqui/cd).
and <y z‘
time.
sets.
arc set operations,
y, {},>,
would
to dctcrminc
to bc contradictory
of the new set (which
global
algorithm
incomp,llibility
the given set Ilas been crcatcd
set. G ivcn ;I lattice
One of the advantages
infcrcncc
an
or
all v,Ilucs
is the set and its rcprcscntation
ii canonical
‘I’hc most common
of tlt~
is that
z =
values
at by
with
as it is crcatcd.
of
to
It can bc viewed
such.
bc discarded.
notion
All
unchcckcd.
Its task is to construct
irnplcmcntation
as cdr-coded
whcthcr
dctcrrnincd
rules
is rcquircd
So it is important
canonic:\li/.cd
NT
dcrivntions
arc important
sets.
dctcrminc
dcrivntions.
of the scope
which
(c.g..
surprisingly
the
proceed
states.
algorithm.
r’cnlovcs
basic datil slructul’c
arc achicvcd
lhcrc
solver
identical
is outside
2, {A},
with
to
21second process is invoked
consistent
a contradiction
come possible
optimijcd
other
prublcm
in the infcrcncc
csscntially
solver
in
Unfortunately.
the
I<cdundancy
but
functioning.
assertions,
infcrcncc
and 7 : <CC=
(a,P,7)>.
uses z twice
of
indcpcndcncc
If the data
<y =
pcrmittcd
arc best for ;tssllmption-bnscd
‘l’hc
analyycs
can
l,(A),>,
use a very
1984)
of intcrprctations.
such that the .~dclilion of any assumption
assunIption
rcscnrch
tcchniqucs
?
problem
incohcrcncy.
p : <s =
if
possible
diffcrcnt
is one cvcry
dcvicc
;IS all
rules
carcflllly
be so cavalier
speaking,
indcpcndcnt.
of logical
must cope with
cannot
away nuy derivation.
the
in syntactically
problem
any
Brown,
of
W~IOSC
arc as important
reasoning
to dcrcrminc
as well
ncvcr
is no guarantee
causal
solver
Strictly
derivations
and
dcrivntions
the statuses
of the assertions
cxamplc,
tasks
2, {A},
should
to or a supcrsct
the derivations
of
goal
tasks ~hc stntuscs
the
globi~lly
sclccting
of
and cvaluatc
dcrivatiws.
‘I’MS,
discover
is to identify
solver
such
‘l’his
invariably
only
derivation.
as their
and is outside
INCOt1k:RE:NCY
assertions.
assertions.
construction
cohcrcncc
Klccr
arc
sets of assumptions.
rcrrloval
‘l‘hc
interpretation
the construction
infcrcnccs
,111 possible
results
for some
(de
to manage
a stl-~~iglit-li)l.w~~l~d set-munipulntion
hc can live
with.
.iNl)
of
global
~hc d;ltn bnsc rcachcs quicsccncc
construct
maximal
HEl)UNl)ANCY
1979) and
tcchniquc
non-contradictory
task, an
of problem-solving
must choose which
of the complexity
~hc goal of maintaining
Klccr,
simple
Unouting
in the justification
from
the scope of this paper.
problems
It just shows up in a dilfcrcnt
on the charrrctcristics
system implcmcntor
problem
avoided,
different
research is rcquircd
is a open problem
place
the unouting
significantly
cot~s~ruciiot~. Most
used (two values arc the same if
statuses is complctcly
by adding
Marc
are usually
solving
of
on them.
Howcvcr.
choice
thousands
in/erpretafion
of
outweigh
place.
that has worked in practice: A and l3 are two dcrivntions
for the same
4A solution
Suppose A is dcrivcd
under as>umption
set a and I3 is dcrivcd
under
asscrlion.
If a and b are
assumption set b If (L IS a proper subsc~ of b. Ii should bc dlscardcd
the stmc. compute all the asscrtlons I\ and 1%dcpcnd on. call these CI and p. If CY is
Othcrwisc,
both derivations should bc
a proper subset of p. l% should bc discarded.
kept and used.
the
costs
dots
cdr-coded
suficicntly).
83
the
of
In our cxpcricncc
data-structure
ordcrcd
unless
problem
assumptions
in
an
maintaining
is cxtrcmcly
I -M-2)
the
the extra ctrort
not turn
thcsc
da&structurcs
incurred
out to bc worth
lists or bit-vectors
large
(i.c.,
advantages
in
tens
not
the
first
in maintaining
the cost (storing
of
do
this
sets as
speeds up subset computations
(Martins
and Shapiro,
assertion
with
((Martins
and Shapiro,
and the assumption
it is cxtrcmcly
of its assumption-set
set the origin
these
an cxtcnsive
cquivalcnt
Although
Howcvcr,
to cntcring
the ordering
ncss it has significant
influcncc
work
‘f’hc ovcraff
to tflc
should
cficicncy
number
constructed
in this section.
assumptions.
which
pcrscdcd
by other
avoided
wily to achicvc
this cnsurcs
not
This
cllicicncy
‘I’hcrc
identical
with
arc two classes of in-
which
tend
cxampfc.
(dc Kfccr,
the function
is inherently
IHowcvcr,
assertions
fjotfl
different
choices
whcthcr
their
choices
sets first.
proposed
and
as fate as possible;
assumption
in cficicncy
of
recording
There
the
LOCAI,
circuits
dc Kfccr,
AND
arc many
which
will
same
For
(Muftipfc
reasoning
and
by marking
of.
1983).
can dctcr-
its schematic.
thus
Quafitativc
muftipfc
possible
solutions
arc
a device has only one
comparing
using
(McDermott,
diffcrcnt
assumption-based
1983)
enough
and
to formufntc
for many
by a general
choices
tasks,
(Ilarton,
schcmc
is formulated,
the schcmc
the compfcxitics
arc unncccssary.
it is important
problem-solving
work it is providing
f%zlicf flcasoncr)
(Martins
SAMI’LI;,
applications
other
1984).
to first
-
the topic
the architccturaf
based framework
proposal
for troubleshooting
in SOt’HIE
III
of constraintc
(fIrown,
0Llt
the origin
each restriction
bctwccn
is also used
and
a conscqucncc
ovcrhcad.
84
it
tficrc
marking
mechanism
agents
bcficfs
that
a very gcncrafizcd
Intcrcstingfy,
reasoning
instead
assumption
is no ncccssity
sets.
among
system,
As a conscqucncc
approach,
Xf<up’s
cquafity
syntactically
With
for contexts
uses
of the justification-
the
it has
e.g., easy
mechanism
classes of assumptions
to identify
and
satisfaction
contexts.
1982).
cquivalcncc
is possibfc
as-
possessing
unifies assumption-based
It uses constraint
(McAlfcster,
contexts.
multipfc
contradict
of the assumption-based
to construct
equivafcnt
in this paper,
set.
of fiup
may
It
account
individually
an equality-based
context
of the advantages
switching
cfcctronic
Burton
to make predictions
set from
1953),
simuftancously.
1983) has proposed
schcmc which
and the assumptions
(Barton.
contradic-
takes into
In this system
wcff
1983) is a
including
the data base.
tcchniqucs.
an assumption-based
cxpficitfy
base. each
that
into
(McDermott,
and Shapiro,
muftipfc,
wffs.
data
bcficfs
compficatcd
justifications
many
1976) is a program
but
justification-based
which
underlying
the same
bclicfs,
allows
to bc rcprcscntcd
logic
agents have cntcrcd
and rcfativcfy
set. This
and f1rown,
with
which
bcficfs
undcrfying
McDermott
choices
1MPL~:MICN’I’A’lIONS
for which
hc subtracts
unnecessary.
system
hypothcticaf,
interact
consistent
two
to see
‘f’wo
of the salnc choice
1979) and (dc Kfccr
each
Thus,
chcckcd
in a contradiction.
can
csscntiafly
but this is conceptually
and Rrown.
QUAI,
one by explicitly
Howcvcr,
making
the essential
gcncraf
{A, C} {B, C} and {A, B, C}.
set can be trivially
It usespropagation
~111his actual implcmcntation
in the data base.
is bcttcr.
(dc Klccr
siruarion
tic
i~ssl~lnptio~~-b;~scd ilnd justilication-based
introduced
how
Mf3R
contradictions
mechanism.
set it is a mcmbcr
results
was incorporated
1983).
Shapiro,
in this paper.
identify
is applicable.
(dc Kfccr,
prcscnt
approach
and
is only
to unify
incfllcicncics
XRup
of this paper
that
is based on a rcfcvancc
if they arc not mcmbcrs
WORK
ambiguous,
F,ach of thcsc is powcrfuf
No matter
sets and no
many
can bc obtained
tfic choice
is used in (de Klccr,
HbX,A’l-El)
and
all attempt
approaches.
arc
One
the new assumption
produces
sets {A, B}
combinations
arc cott~pn/ible
approach
nogood
with
that
muftiplc
from
for any particular
something
(Martins
whose assumptions
of thcsc infcrcnccs
assumption
subset
the contradiction
incrcasc
choice
rcquircs
F,NVfSfON
sofcfy
Quaf scfccts the correct
sumptions
individual
of a circuit
to make
the validity
and that
for device behavior.
-
1983)
AVBVC
A significant
1979) and
about
program
bc simultaneously
causal accounts
to a particular
available
for this task the assumption-based
function.
tory
the four
information
‘I‘his
are
some underlying
is focafizcd
bc cxpficitfy
solutions
arc su-
the choice
introduces
fault
components
that
of this paper.
between
to clutter
individual
does
will become
set). ‘I’hc best mcasurcmcnt
assumptions.
propagations
model
as
schcmcs.
subsets arc contradictory.
‘[‘he cxcfusivc-or
the
component
impfics
measure-
is not operating
values whose assumption
from
with
that
maximal
of an infcrcncc
produced.
rc-
hcncc
yet unvcrificd
analysis
motivation
arc
one that provides
and circuit
the predictions
A contradiction
next is tic
mint
the
is fincarfy
a strong
new assumptions
vafucs
witfl
as the correct
assumptions
is violated,
1984) product
a scparatc
and vafucs which
smaller
following
slowly
models
some component
component,
set (i.e., the nogood
QUAI,
of
faulty
component
Hcncc,
tcchniqucs
involves
provides
assumptions.
that any values
very
infcrencc
speaking.
this is to introduce
bc supcrscdcd
number
the
The
contradictory
the
component
at some point,
correctly.
assumptions
first.
proportional
dcgradcs
on values with
by working
cfficicncy,
assumptions
(i.e.,
to bc futifc:
vafucs with
For
to complcte-
from
is faulted,
the actual
assumption
(this is
is roughly
to bc contradictory
arc a subset of the original
is
of the
fcwcr
Thus,
functioning
to determine
solving
of infcrcnccs.
arc guaranteed
sets arc later discovcrcd
a contradiction
place
is irrcfcvant
with
each
of infcrcnccs.
the number
tic
infcrcnccs
pcrformancc
ing step. so, roughly
for reducing
not
wit11 the cornput;ltionaf
However,
fated to the nurnbcr
fcrcnccs
and
Fortunntcfy,
outfincd
inconsistent.
be consulted,
cfficicncy.
of the problcrn
number
problem-sol\
on
on vafucs
of assumptions
values).
set is
a set into a fatticc).
problem
sofvcr
intended.
not describe
crcatcd
behavior
As the circuit
that
must bc updated
of the inferences
dcvicc
has the advantage
take
sets of any assertion
about
ments.
sets
whcncvcr
must
each
arc nogood.
the restriction
a ncwfy
need
computation
the restriction
roughly
whcthcr
super-sets
set of contradictions.
whcthcr
set? ) This
to dctcrminc
as only
discovcrcd
of marking
which
1983) calls thcsc super-sets
simple
contradictory
cnrirc
1983) uses the technique
the super-sets
and as
diffcrem
but
schcmc
presented
and their
associated
The incfficicncics
of backtracking
lcms was rccogniled
dificulties
not
quite
and proposes
formulated
technique
in terms
cxplorcs
early.
for constraint
(Mackworth.
a number
techniques.
justifications,
space nearly
McAllcster
Intclligcncc
the
D.,
“An
Laboratory,
Outlook
on Truth
AIM-HI,
Maintenance,”
Cambridge:
M.I.T.,
Artificial
1980.
Although
assumptions,
as cficicntly
[ll]
prob-
1977) summarizes
of efficient
of assertions,
the solution
satisfaction
[12]
his
McAllcster
Artificial
as ‘I’MS-like
D.,
Intelligence
“Reasoning
Laboratory,
Utility
AIM-667,
Package
User’s
Cambridge:
Manual,”
M.I.T.,
1982.
schemes.
[13] McDermott
ACKNOWLEDGhWNTS
I thank
out
many
Daniel
of
the
Bobrow
technical
and
13rian Williams
issues and
forced
who
me
helped
to clean
sort
up
[14]
the
Iiulifson,
Procedural
implcmcntation.
Center,
RI t3t,tOGt<,IPHY
[15] Stcclc,
J.F.,
Calculus
‘I’cchnical
[I]
Barton,
GX.,
“A
Artificial
Multiple-Context
Intclligcncc
Equality-based
I .aboratory,
I .nboratory,
Reasoning
‘II<-7 15, Cambridge:
language
J.S..
1). Burton
and knowlcdgc
and
J. de Klccr,
cnginccring
Academic
[3] de Klecr,
J. and
to appear
nition,”
J.S. Brown,
J., “Causal
Artificial
natural
in SOPHIE
I, II and
by D.Slccmnn
and J.S.
Press, 1983.
Conflucnccs,”
[4] de Klccr.
“Pedagogical.
tcchniqucs
111,” in Itzfelligm( Tuforitlg S’ysletns, cditcd
Ijrown,
“A
Qualitative
f’hysics
Ijascd
on
in Arl/~cial Ittklligence.
and Tclcological
lntclligcncc
licasoning
Laboratory,
‘H-529,
in Circuit
Cambridge:
RccogM.I.T.,
1979.
[5] de Klccr,
to Circuit
[G] de
M.I.T.,
Klccr,
J., “A
12, No.
[8] Forbus,
Applied
Methods
of
Intclligcncc
Localizing
Laboratory,
Faults
AIM-394,
in
8, 1980.
Electronic
Cambridge:
Truth
K.D.,
“Qualitative
AIM-664,
A.K.,
It~rclligetzce,Vol.
Martins,
York,
System,”
“Consistency
J.P. and
Report
Process Theory,”
Cambridge:
8, No.
Spaces.” IJCAI-1983,
‘I’cchnical
Maintenance
Arffkial
Itr~elligmce,
Artificial
Intclligcnce
3, 1979.
[9] Mackworth,
New
of Constraints
1976.
Laboratory,
[lo]
“Propagation
Circuit Theory and Applications, Vol.
“Local
Artificial
[7] Doyle,
Vol.
J. and C.J. Sussman,
Synthesis,”
Circuits,”
and Data Dependencies:
A Synthesis,”
M.I.T.,
1982.
in Networks
of Relations,”
No.
Ar@ial
1, 1977.
S.C. Shapiro,
“Reasoning
1983 (see also: Dcpartmcnt
203,
l3ufil0,
New
York:
in Multiple
of Computer
State
for
Derkson,
Intuitive
73, Menlo
llcfinition
Language
based on
and
K.J.
Waldingcr,
Reasoning,”
Artificial
Park:
1972.
S.1I.I..
and lmplcmcntation
Constraints,”
‘1X-595,
Cambridge:
M. J.T., 1979.
[16) Williams,
B.C.,
“Qualitative
Analysis
AI I *aboratory
‘1’11-567, 1983.
“QA4:
Intclligcnce
of a Computer
Artificial
Intelligence
M.I.T.,
1983.
[2] Brown,
J.A.
Note
G., “‘l’hc
Programming
System,”
D., “Contexts
1983.
Ijclief
Science,
University
of
1983).
85
of MOS
Circuits,”
M.I.T.
A