A Topological-Based Me hod o Alloca ing
Senso s by Using CSP Techniques
R. Ceballos, V. Cejudo, R. M. Gasca, and C. Del Valle
Depa amen o de Lenguajes y Sis emas In o m´a icos,
Uni e sidad de Se illa (Spain)
{ceballos, cejudo, gasca, ca melo}@lsi.us.es
Abs ac . Model-based diagnosis enables isola ion o aul s o a sys em.
The diagnosis p ocess uses a se o senso s (obse a ions) and a model
o he sys em in o de o explain a w ong beha iou . In his wo k, a
new app oach is p oposed wi h he aim o imp o ing he compu a ional
complexi y o isola ing aul s in a sys em. The key idea is he addi ion o
a se o new senso s which allows he imp o emen o he diagnosabili y
o he sys em. The me hodology is based on cons ain p og amming
and a g eedy me hod o imp o ing he compu a ional complexi y o he
CSP esolu ion. Ou app oach main ains he equi emen s o he use
(de ec abili y, diagnosabili y,...).
1 In oduc ion
Model-based diagnosis (MBD)[1][2] allows o de e mine why a co ec ly designed
sys em does no wo k as expec ed. In MBD, he beha iou o componen s is sim-
ula ed by using cons ain s. Inpu s and ou pu s o componen s a e ep esen ed
as a iables o cons ain s. These a iables can be obse able and non-obse able
depending on he senso s alloca ion. The objec i e o he diagnosis p ocess is o
de ec and iden i y he eason o any unexpec ed beha iou , and o isola e he
pa s which ail in a sys em.
The diagnosabili y o sys ems is a e y ac i e esea ch a ea in he diagnosis
communi y. A oolbox in eg a ing model-based diagnosabili y analysis and au-
oma ed gene a ion o diagnos ics is p oposed in [3]. The p oposed oolbox sup-
po s he au oma ed selec ion o senso s based on he analysis o de ec abili y
and disc iminabili y o aul s. In his line, a me hodology o ob ain he diagnos-
abili y analysis using he analy ical edundancy ela ions (ARR) was p oposed
in [4]. This app oach is based on an exhaus i e analysis o he s uc u al in o ma-
ion. The objec i e is he addi ion o new senso s o inc ease he diagnosabili y.
In a p e ious wo k [5] a me hodology o analyze he diagnosabili y o a sys em
based in a p ocess algeb as was p oposed. A amewo k o es ing he diagnos-
abili y o a sys em is defined by using he a ailable senso s, a model abs ac ion,
and some snapsho s o senso eadings.
In his wo k, a new app oach is p oposed in o de o imp o e he compu a-
ional complexi y o isola ing aul s in a sys em. Ou app oach is based on he
addi ion o new senso s. A cons ain sa is ac ion p oblem (CSP) is ob ained in
o de o selec he necessa y senso s o gua an ee he p oblem specifica ion. We
p opose an algo i hm o de e mining he bo leneck senso s o he sys em in o -
de o imp o e he compu a ional complexi y o he CSP. A CSP is a amewo k
o modeling and sol ing eal p oblems as a se o cons ain s among a iables. A
CSP is defined by a se o a iables X={X1,X2,..., Xn}associa ed wi h a se o
disc e e- alued, D={D1,D2,..., Dn}(whe e e e y elemen o Diis ep esen ed
by se o i), and a se o cons ain s C={C1,C2,..., Cm}. Each cons ain Ci
is a pai (Wi,Ri), whe e Riis a ela ion Ri⊆Di1·...·Dik defined in a subse o
a iables Wi⊆X.
The emainde o he pape is o ganized as ollows. Sec ion 2 p o ides he
defini ions and no a ion in o de o cla i y MBD concep s. Sec ion 3 in oduces
he basis o ou app oach. Sec ion 4 desc ibes he CSP gene a ion. Sec ions 5
shows he g eedy me hod o imp o ing he CSP esolu ion. Finally, conclusions
a e d awn and u u e wo k is ou lined.
2 No a ion and De ini ions
In o de o explain ou me hodology, i is necessa y o es ablish some concep s
and defini ions om he model-based diagnosis heo ies.
De ini ion 1. ASys em Model is a fini e se o equali y cons ain s which de-
e mine he sys em beha iou . This is done by means o he ela ions be ween
he non-obse able and obse able a iables (senso s) o he sys em.
De ini ion 2. ADiagnosis is a pa icula hypo hesis ha shows he sys em
diffe s om i s model. Any componen could be wo king o aul y, hus he
diagnosis space o he sys em ini ially consis s o 2nComp - 1 diagnoses [2],
whe e nComp is he numbe o componen s o he sys em. The goal o diagnosis
is o iden i y and efine he se o diagnoses.
De ini ion 3. The Disc iminabili y Analysis [3] de e mines whe he and unde
which ci cums ances he conside ed (classes o ) aul s can be dis inguished.
De ini ion 4. The Diagnosabili y le el is he quo ien o he numbe o he
(classes o ) aul s which can be dis inguished each o he , and he numbe o all
he possible aul s. The size o he possible aul s is ini ially 2comp -1.
De ini ion 5. A se o componen s Tis a Clus e o componen s [6], (i) i i
does no exis a common non-obse able a iable o any componen o he clus e
wi h any componen ou side he clus e , and (ii) i o all Q⊂T hen Qis no
a clus e o componen s.
All common non-obse able a iables be ween componen s o he same clus e be-
long o he clus e , he e o e, all he connec ions wi h componen s which a e ou -
side he clus e a e moni o ed. A clus e o componen s is comple ely moni o ed,
and o his eason he de ec ion o aul s inside he clus e is possible wi hou any
in o ma ion om o he componen s which do no belong o he clus e . A mo e
de ailed explana ion and he clus e de ec ion algo i hm appea s in [6].
3 The Basis o he Algo i hm
Ou app oach is based on he gene a ion o new clus e s o componen s by al-
loca ing senso s in some o he non-obse able a iables. These new clus e s
educe he compu a ional complexi y o he diagnosis p ocess since i enables
he gene a ion o he diagnosis o he whole sys em based on he diagnosis o
he subsys ems. Le Cbe a se o ncomponen s o a sys em, and C1and C2be
clus e s o n-mandmcomponen s such as C1∪C2=C; hen he compu a-
ional complexi y o de ec ing conflic s in C1and C2sepa a ely is lowe han in
he whole sys em C, since he numbe o possible diagnoses o he wo clus e s
is (2n-m)+(2
m)-2≤2n-m ·2m-2whichisless han2
n-1.
The clus e ing p ocess enables isola ing he aul s o he o iginal sys em, since
he mul iple aul s which include componen s o diffe en clus e s a e elimina ed.
These kind o aul s a e ans o med in o single o mul iple aul s which belong
o only one clus e . The compu a ional complexi y o de ec ing conflic s and
disc imina ing aul s in a sys em is always highe han o an equi alen sys em
di ided in o clus e s.
4 The CSP P oblem Speci ica ion
The objec i e is o ob ain he bes alloca ion o senso s in o de o gene a e new
clus e s. The alloca ion o he senso s will be o mula ed as a Cons ain Sa is-
ac ion P oblem (CSP). A CSP is a way o modeling and sol ing eal p oblems
as a se o cons ain s among a iables.
The me hodology was applied o he 74181 4-Bi ALU. I is one o he ISCAS-
85 benchma ks [7]. I includes 61 componen s, 14 inpu s and 8 ou pu s. Table 1
shows he se o a iables and cons ain s o de e mining he numbe and loca-
ion o senso s o his example. The ollowing a iables a e included:
–nNonObsVa : This cons an - a iable holds he numbe o non-obse able
a iables.
Table 1. CSP o he 74181 ALU senso s alloca ion
Va iable (= ini ial alue) Domain
(1) nSenso s = { ee}D={1, . . . , nNonObsVa }
(2) clus e O Compi={ ee}D={1, . . . , nComp}
(3) clus e Dis ={ ee}D={1, . . . , nComp}
(4) senso k={ ee}D={ ue, alse}
Cons ain s
(5) i (senso E01 = alse)⇒clus e O CompM11 = clus e O CompM32
(6) i (senso E02 = alse)⇒clus e O CompM19 = clus e O CompM32
...
Fig. 1. 74181 ALU
–nSenso s: This a iable holds he numbe o new senso s. I mus be smalle
han he numbe o non-obse able a iables.
–senso k: This se o a iables ep esen s he possible new senso s o he
sys em. They hold a boolean alue in he in e al { ue, alse},whe e ue
implies ha he e mus be a senso , and alse he opposi e.
–clus e O Compi: This se o a iables ep esen s he clus e associa ed o
each componen i.
–clus e Dis : This se o a iables holds he numbe o componen s included
in each clus e .
Fo each common non-obse able a iable be ween wo componen s a con-
s ain is gene a ed which gua an ies ha i he e is no a senso , he wo com-
ponen s mus belong o he same clus e . Table 1 shows he cons ain s (5),(6),...
ha hold his kind o in o ma ion, and i is based on Figu e 1. The final senso s
alloca ion is s o ed in senso k, and he dis ibu ion o he clus e s is s o ed in
clus e Dis i. The op imiza ion p oblem can ha e diffe en objec i es, depending
on he use and he p oblem equi emen s. Two ypical goals can be:
–To minimize he numbe o senso s (i he numbe o clus e s is fixed).
–To minimize he maximal numbe o componen s in each clus e (i he
maximal numbe o senso s is fixed).
I is possible o add o he cons ain s in o de o gua an ee some p ope ies
o he solu ion. Fo example, in o de o gua an ee p ices, o espec equi e-
men s o he cus ome s, o s o e incompa ibili ies, o speci y p oblems, ... We
ha e applied he limi ed disc epancy sea ch (LDS) [8] algo i hm in o de o
sea ch he solu ion. This algo i hm is based on he limi a ion o he numbe o
disc epancies.
5 Imp o ing he Algo i hm: A G eedy Me hod
The compu a ional complexi y o a CSP is exponen ial in gene al. We p opose a
me hod o ob ain he mos impo an alloca ion o he new senso s in o de o
gene a e mo e clus e s; ha is, he bo lenecks o he sys em. Ou me hod has
wo phases:
1. The calcula ion o he minimal pa hs: A g aph whe e he nodes ep esen he
componen s o he sys em, and he edges ep esen he connec ions be ween
each wo componen s (non-obse able a iables). Each edge has a weigh
calcula ed as he numbe o common non-obse able a iables be ween wo
componen s. By applying he Floyd’s algo i hm (dynamic p og amming), all
he sho es pa hs be ween all pai s o nodes is s o ed.
2. In o de o de e mine which a e bo lenecks o he sys em, each minimal pa h
will o e which senso s a e mo e impo an . Figu e 2 shows his algo i hm.
senso sO de (P)
componen Vo es[nComp][nNonObsVa ]
senso Vo es[nNonObsVa ]
// All he componen s (1..nComp) o es he a iables (senso s)
// associa ed o he minimal pa hs
o Each jbe ween 1 o nComp
o Each Pk om componen i o componen j
o Each qbe ween 1 o leng h(Pk)
= ( o eValue / (leng h(Pk,i,j)·leng h(Pk))
o Each includes in pa h[q]
componen Vo es[i][Pk,i,j,q]+=
endFo Each
endFo Each
endFo Each
endFo Each
// Recoun ing o o es o each senso
o Each senso jbe ween 1 o nSenso s
senso Vo es[j] = 0
o Each ibe ween 1 o nComp
senso Vo es[j] += componen Vo es[i][j] / ( ·nComp )
endFo Each
endFo Each
e u n so (senso Vo es)
Fig. 2. Algo i hm o ob aining he bo leneck senso s o he sys em ( O(n2·m2),
whe e nis he numbe o componen s and mis he numbe o non obse able a iables)

Each minimal pa h will o e o he included non-obse able a iables o
he minimal pa h. The numbe o o es a e scaled in o de o gua an ee ha
each componen gene a es he same o al numbe o o es. These o es allow
o gene a e a so ed lis o non-obse able a iables. This lis is composed o
he mos ele an senso s wi h he aim o gene a ing new clus e s.
The bo lenecks o he sys em ep esen he bes senso s in o de o isola e
componen s and aul s. The so ed lis o senso s enables c ea ing a CSP wi h
less a iables o find he solu ion o he p oblem in a limi ed ime. Only he so-
lu ions included in he combina ions o he mbo leneck senso s will be es ed,
and he e o e, he numbe o possible solu ions will be lowe han 2m.Theop i-
mal solu ion is no gua an eed, bu he educ ion o compu a ional complexi y
enables finding a solu ion in a limi ed ime.
Example: In he Alu74181 example he mos impo an senso s a e (based
on he numbe o o es): E02(930), E03(878), X28(773), E01(737), E00(583),
D00(514), D01(463), D02(326), D03(301),... The o he senso s ha e less han 166
o es. The fi s 9 senso s a e ep esen ed by shaded ci cles in Figu e 1. The pos-
sible diagnoses in he sys em a e 261 - 1. By using he fi s 9 selec ed senso s,
he numbe o clus e s is 17 (all wi h less han 6 componen s) and he compu-
a ional complexi y is educed because o he educ ion o possible diagnosis o
less han 29.
6 Conclusions and Fu u e Wo k
The objec i e o ou app oach is he alloca ion o a se o new senso s in o -
de o imp o e he compu a ional complexi y and diagnosabili y o a sys em.
The me hodology was applied o an s anda d example, and he esul s a e e y
p omising. I is based only on opological p ope ies. This enables applying his
app oach o diffe en kinds o sys ems. As a u u e wo k, we a e wo king on new
g eedy me hods o imp o e he o es coun ing.
Acknowledgemen s
This wo k has been unded by he Spanish Minis y o Science and Technology
(DPI2003-07146-C02-01) and he Eu opean Regional De elopmen Fund.
Re e ences
1. Rei e , R.: A heo y o diagnosis om i s p inciples. A i icial In elligence 32 1
(1987) 57–96
2. de Klee , J., Mackwo h, A., Rei e , R.: Cha ac e izing diagnoses and sys ems.
A i icial In elligence 2-3(56) (1992) 197–222
3. D essle , O., S uss, P.: A oolbox in eg a ing model-based diagnosabili y analysis
and au oma ed gene a ion o diagnos ics. In: DX03, 14 h In e na ional Wo kshop
on P inciples o Diagnosis, Washing on, D.C., USA (2003) 99–104
4. T a ´e-Massuy´es, L., Escobe , T., Spanache, S.: Diagnosabili y analysis based on
componen suppo ed analy ical edundancy ela ions. In: 5 h IFAC Symposium on
Faul De ec ion, EEUU (2003)
5. Console, L., Pica di, C., Ribaudo, M.: Diagnosis and diagnosabili y analysis using
PEPA. In: ECAI 2000, P oceedings o he 14 h Eu opean Con e ence on A i icial
In elligence, Be lin, Ge many, IOS P ess (2000) 20–25
6. Ceballos, R., G´omez-L´opez, M.T., Gasca, R., Pozo, S.: De e mina ion o Possible
Minimal Con lic Se s using Componen s Clus e s and G obne Bases. In: DX04,
15 h In e na ional Wo kshop on P inciples o Diagnosis, Ca cassonne, F ance (2004)
21–26
7. Hansen, M.C., Yalcin, H., Hayes, J.P.: Un eiling he ISCAS-85 Benchma ks: A Case
S udy in Re e se Enginee ing. IEEE Design and Tes o Compu e s 16(3) (1999)
72–80
8. Ha ey, W.D., Ginsbe g, M.L.: Limi ed disc epancy sea ch. In: Fou een h IJCAI,
Mon eal, Canada, IOS P ess (1995)