ѧ
JOURNAL OF SOFTWARE 
1999 10 5 Vol.10 No.5 1999



һֲַݽ׵Ķ
ʿСʯһ
ժҪеĶԱʾ㷨ڵ,һµķ.,˻ڸṹĶԱʾ.Ȼ,˲ͬȲ˹ϵϱļ㷽.,Ƶóֲݽ׵㷨.¸ķнϸߵ֪,㷨ɸѡʵıʾ,㷨,Ըĺ,һ㶨овοֵ.
ؼʡ,ṹ,ϱ,ֲݽ,Կռ.
ͼšTP18
A Hierarchical Method for Qualitative Topological Inference 
LIAO Shi-zhong1SHI Chun-yi2
1Department of Computer ScienceLiaoning Normal Un iversityDalian116029
2Department of Computer Science and TechnologyTsinghua UniversityBei jing100084
AbstractA new method is proposed to solve the problems in existing qualitative represent ation methods and topological inference algorithms. First, a qualitative represe ntation mechanism based on conceptual neighborhood is described. Then, a computa tion procedure for composition tables in different topological relation levels i s put forward. Finally, a hierarchical topological inference algorithm is demons trated. The algorithm can select a suitable representation and inference level f or a given problem, and can work out a reasonable solution when other algorithms fail to give answers. The hierarchical method proposed in this paper is cogniti vely valid, and is helpful for general qualitative reasoning research.
Key wordsTopological inference, conceptual neighb orhood, composition table, hierarchy, qualitative spatial reasoning.
ǶԿռоĻ,һô,ӦԼ㷨ʹԼﵽ·ԣ13.ȻڵϢϵͳռݿͶԿռõӦã1,2,еԹ̶Ȼʾ˹ϵ.Smithֻ˻˹ϵ1.HernandezȻ˲ͬ˹ϵıʾʹ,˵ҪԺͿ,ûнһʵ㷨2.GrigniܽĹʱ,˱ʾ˹ϵһֲϵ˹ϵĸϱ,ûиϱļ㷽,Ҳûиϵе㷨3.
ıʾ,ԲͬڶϽ,ǶҪص2.еĶԱʾ,ף4иķ,ֻǴʽϰѶֵΪӼ,ûнһֵ̻Ӽڽṹ,ʵЧĶԱʾ.,ʶ֪ʶе˹ϵ,ǲȷȻʾ.,Ҫϵͳܹ˹ϵڲͬȻϵıʾ,Ҫʱ,ܹԼ,ȷʵıʾ,Ľ.,˹ϵڲͬȻϵıʾ֯о,ԼʺϾıʾѡ񷽷о,ҪĹ.
йдڵ,ף5,6ݵĹ,һֻڸṹ˹ϵԱʾ,оڲͬȻ˹ϵϱļ㷽,һֲݽ׵㷨.
1 ˹ϵĶԱʾ
˹ϵǻĿռϵ.ڶԿռ,˹ϵΪǿռϵһֶԱʾ,4-ģʽ2.ף5˹ϵıģ,ڱģͿֱƵ˹ϵ걸͸ṹ.о˹ϵһֻڸṹĶԱʾ.
1. Cǿռϵ޷ǿռ,Ʀ,աCǹCڵ,,նӦƿɲ3CеĹϵ໥ת2,6,7.
ԦաC,յĸHC()={סC,ڵ}.
CĸṹCиԪصĸ,ɸͼʾ.,˹ϵĸṹͼ1ʾ5.

ƹĸڹϵṹ¶.
A,BC,A,Bǹڵ,ڵ,aA,bB,a,bǹCڵ.Ӧ,D2C,AD,HD(A)={BDA,Bǹڵ}.
2. TǱʾһռϵķǿ޼,TĶԱʾΪ
Q(T)=HT,T,T,LT.
 (1) HT:T2TTĸṹ.
(2) Tݪ2T,

(b) p,qʣT,pq,pq=,
(c) qʣT,tq,ʹqHT(t).
(3) T:TݡLTΪ,ǣTݵLTһһӦ.
(4) LTǶԸƵļ.
HT,TLTȷ,Q(T)ɼΪT.һ,ǣT0=T,Tn=ۣTn-1,ڹڹϵ͸ṹĻ,ɵõTķֲݽ׵ĶԱʾʽ.Ϊͷ,õĲϵĵײټһչϵ,ڶټһ㷺ϵ6.
1:T=T(n,n)={d,t,o,c,c@b,i,i@b,=}ʵ˹ϵ걸5,Tһֲַݽױʾʾ:
(1) Q(T)=HT,T,T,LT.,
HTͼ1ʾ;
T={{d},{=},{t,o},{i,i@b},{c,c@b}};
LT={d,=,o,i,c};
T1ʾ.
(2) Q(T)=HT,T2,УT,LTݡ.,
HTݿHTƵ,ͼ2HTݵһּıʾʽ,
ͼеĽǶԸ;
T2={{{d}},{{t,o},{i,i@b},{c,c@b},{=}}};
УT({{d}})=dҦУT({{t,o},{i,i@b},{c,c@b},{=}})=o;
LT={d,o}.
1TĶ

TLT
{d}d
{=}=
{t,o}o
{i,i@b}i
{c,c@b}c


γɵĲϵĵײһ㲻Ŀչϵ,ڶһƽķϵ,˹ϵһֲַݽ׵ıʾʽͼ3ʾ.

ʶ֪ʶͶ֪ʶĻص,ͬһƵĸڲͬоֲͬĶ2.еĶԱʾ,ף4иķ,Ȼǿ˶붨,ָ˶ԱʾĲ,ЩֻǴʽϰѶֵΪӼ,ûнһֵ̻ӼĽṹ,˲ͬεĸɾͬһһ,ܷӳʶ֪ʶͶ֪ʶһص.1пԿ,ڸĶԱʾԸṹΪ,ѶԸƼΪԱʾĻɷ,Ӷ̻˲ͬȻֲͬͬڻ,ɽϺõرʾʶ֪ʶͶ֪ʶһص.,ĶԱʾжԱʾķչ,еķиõ֪.
2ϱļ㷽
˹ϵĸϱĻ.е˹ϵռϵĸϱ˵ֱͨԵõ.ʶ,ϱԶǶԿռٵս֮һ8.ף5и˻˹ϵϱʽƵ.ڴ˻,ڽһо˹ϵϱļ㷽.
ǣTn-1еĸΪ,TnеĸΪ*,ǦУTn-1Ϊ,RS=rR,sSrs.֪Tn-1еĸϱ,r,sʣTn-1,rsж,Tnеĸϱɰ·:u,vLTn-1,

ɼ,˻˹ϵĸϱ,,Ϳɼ˹ϵĸϱ.ף5ݿ֪,÷ȷ.2ǻ˹ϵĸϱ,3ͱ4ǻڱ1ͼ3ʾ˹ϵĸϱ.ף3иĽһµ.
2˹ϵĸϱ

*dtoi@bic@bc=
dT{d,t,o,i@b,i}{d,t,o,i@b,i}{d,t,o,i@b,i}{d,t,o,i@b,i}{d}{d}{d}
t{d,t,o,c@b,c}{d,t,o,i@b,c@b,=}{d,t,o,i@b,i}{t,o,i@b,i}{o,i@b,i}{d,t}{d}{t}
o{d,t,o,c@b,c}{d,t,o,c@b,c}T{o,i@b,i}{o,i@b,i}{d,t,o,c@b,c}{d,t,o,c@b,c}{o}
c@b{d,t,o,c@b,c}{t,o,c@b,c}{o,c@b,c}{o,i@b,c@b,=}{o,i@b,i}{c@b,c}{c}{c@b}
c{d,t,o,c@b,c}{o,c@b,c}{o,c@b,c}{o,c@b,c}{o,i@b,i,c@b,c,=}{c}{c}{c}
i@b{d}{d,t}{d,t,o,i@b,i}{i@b,i}{i}{d,t,o,i@b,c@b,=}{d,t,o,c@b,c}{i@b}
i{d}{d}{d,t,o,i@b,i}{i}{i}{d,t,o,i@b,i}T{i}
={d}{t}{o}{i@b}{i}{c@b}{c}{=}

T={d,t,o,c@b,c,i@b,i,=}
3˹ϵĸϱ

*d=ico
d{d,=,i,c,o}d{d,i,o}d{d,i,o}
=d=ico
idii{d,=,i,c,o}{d,i,o}
c{d,c,o}c{c,=,i,o}c{c,o}
o{d,c,o}o{o,i}{d,c,o}{d,=,i,c,o}

4˹ϵĸϱ

*do
d{d,o}{d,o}
o{d,o}{d,o}

3㷨
ף6о˲ϵе㷨,ûпԼ廯.ڽһ һ,ֲݽ׵㷨.
ͼ3ʾĲϵN,()/(()/())Ϊ0,͡Ϊ4,MAXLEVEL=4.Parent(node)Ϊnod eĸ,Children(node)Ϊnodeӽ㼯,R1,R2,R3ֱΪ23ͱ4 ʾ ϱƵ,TCNǿռ˹ϵԼ,rel(Ni)Nеi˹ϵļ,rel(TCN)TCNгֵ˹ϵļ,G Ŀռ򼯺,G.level˵Gе˹ϵNlevelеĹϵ,NETSET ϵԼ,head(NETSET)NETSETеĵ1,tail(NETSET)NETSETгh ead(NETSET)֮ɵ,ֲݽ׵㷨.
㷨TRH. ֲݽ׵㷨.
:TCN,N,G.
:·ݵTCN,ݽ.
:
1. ʼ.NETSET{G}.
2. ȷĳʼ.:
ҳNеĳһlevel,
rel(G)rel(Nlevel)ҡrel(G) rel(Nlevel-1).
3. ѭ.
NETSET=,򷵻.
RELAXfalseSPECIFYfalse
Khead(NETSET);
NETSETtail(NETSET).
4. K.levelж.
levelΪ()/(()/()), ء޽⡱
levelΪ͡,򷵻ءƽ⡱
levelѱ,򷵻ءμ̫,⡱.
5. Լ.
K簴RlevelƵԼ
AKԼɵķϵ;
K.level.
6. жϼ.
KеĹϵǷϵ:Լ廯TS(K),ת3
Kݵ:
(A= SPECIFYlevel=MAXLEVEL-1RELAX,level=1),
򷵻ݽ⣻
,ÿһaA,KҳĻ,γһGa,þ廯T S(Ga),ת3.
Kǲݵ:Լɳ۹TR(K),ת3.
ӹTSTRĶ.
TS(G):Լ廯.
:G,level.
:Gľ廯缯NETSET,µlevel.
:
{
A,BG,ATB,Trel(Nlevel),µG,ATB,
T=ȦաTChildren().
NETSETNETSET{G}.
levellevel+1.
SPECIFYtrue.
}.
TR(G):Լɳ۹.
:G,level.
:Gɳ缯NETSET,µlevel.
:
{
A,BG,ATB,Trel(Nlevel),µG,ATB,
T={Parent()|աT}.
NETSETNETSET{G}.
levellevel-1.
RELAXtrue.
}.
2:һλҪһС.С3:סլ(R) ҵ(B)ͳվ(S).Ҫ:
(1) סլҵֿ;
(2) סլӦһվ;
(3) ҵӦһվ.
Ӧһֺ.
TRH㷨ⲽ:
(I) ȷĳʼΪ3.
(II) Ӧò3ĸϱ,ԼG=(R,B,S},֪ǲݵ,ͼ4( a)ʾ.
(III) TR(G),µԼ,ͼ4(b)ʾ,Ϊ2.
(IV) Ӧò2ĸϱ,Լ.

{d}.{c}={d},{d}{c}=,
ǲݵ.
(V) TR(G),µԼ,ͼ4(c)ʾ,Ϊ1.

(VI) Ӧò1ĸϱ,Լ,֪ݵ,Ҹϵ ϵ,ʷݽ

R{d}B,R{o}S,B{o}S.

ĺͼ5ʾ.

3:X,Y,Z3ʵ,Ի㷨TRH,ҳ˹ ϵr,
XrY,YrZ,ZrX.
XuY,YvZ,ZwX,w-1=u*vw=v*u.,Ӧ㷨TRHǿе.
X,Y,Z˹ϵû֪Լ,ʾΪ{d,o}.ɴȷʼΪ1.Ӧ 㷨TRH,ע⵽rǵϵXrY,YrZZrX,ɵõ3ݽ
d,=,o,t.
X,Y,Zʵ,Ľr=dr=t.
23ɼ,㷨TRH,ɼظĽ⣻HernandezSmith 㷨ȴ.
4
¼˸ĶԱʾûпֵ̻ϵڽṹ4.SmithHernand ezֻ˹̶Ȳϵ㷨1,2.Щ,о һֲַݽ׵,Ҫ:(1) һֻڸṹ˹ϵ ʾ;(2) ˶˹ϵϱԶ㷽.(3) о˹ϵԱʾ Ĳϵ,ʱʾεѡ񷽷,һֲݽ׵㷨. 
иʾͷ֪,ķչй, ľԼԵظĽ,ܹϺõرʾһĶ֪ʶ, ֪ʶıʾʹ,ҲһĲοֵ.
һĹ:(1) ԼɳۺԼ廯ǿռԼļо;(2) ֲݽ ռϵĶԱʾʹӦо.

оõ廪ѧܼϵͳصʵҿſ.
ʿ,1964,ʿ,,ҪоΪ,ռ,˹Ӧû.
     ʯһ,1935,,ʿʦ,ҪоΪ˹Ӧû,֪ʶ.
ͨѶϵ:ʿ, 116029,ʦѧѧϵ
ߵλʿУʦѧѧϵ116029
ʯһ廪ѧѧ뼼ϵ100084
ο
[1]Smith T R, Park K K. Algebraic approach to spatial reasoning. Interna tional Journal of Geographical Information Systems, 1992,6(3):177192
[2]Hernandez D. Qualitative Representation of Spatial Knowledge. Berlin: Sprin ger-Verlag, 1994
[3]Grigni M, Papadias D, Papadimitriou C. Topological inference. In: Mellish S S ed. Proceedings of the IJCAI'95. San Meteo: Morgan Kaufmann Publishers, Inc., 1995. 901906
[4]¼,ʯһ.ԴʽFAQA.ѧ,1995,18(6):417423
(Chen Jian, Shi Chun-yi. FAQA: a formal frame of qualitative algebra. Chinese J ournal of Computers, 1995,18(6):417423)
[5]ʿ,ʯһ.˹ϵıģͼϱƵ.ѧ,1997,8(12):894 900
(Liao Shi-zhong, Shi Chun-yi. Closed ball model and composition table derivati on for topological relations. Journal of Software, 1997,8(12):894900)
[6]ʿ.Կռֲƽо۲ʿѧλģ.:廪ѧ,1997 
(Liao Shi-zhong. The research on the hierarchical approximation method for qual itative spatial reasoning Ph.D. Thesis. Beijing: Tsinghua University, 1997) 
[7]Freksa C. Temporal reasoning based on semi-internals. Artificial I ntelligence, 1992,54(1-2):199227
[8]Cohn A G. The challenge of qualitative spatial reasoning. ACM Computing Sur veys, 1995,27(3):323325 
1998-02-10յԭ,1998-05-25յ޸ĸ
