一種基于概念格的室內(nèi)導(dǎo)航算法

趙新云 劉厚泉

（中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

一種基于概念格的室內(nèi)導(dǎo)航算法

趙新云 劉厚泉

（中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

文章首先建立一個(gè)室內(nèi)導(dǎo)航模型，提出了一種基于概念格的室內(nèi)導(dǎo)航算法，該算法基于位置-出口模式和形式概念分析的理論，使用概念格表示室內(nèi)環(huán)境，并使用最近鄰居關(guān)系結(jié)合A*算法來查找兩個(gè)實(shí)體之間的最優(yōu)路徑。

室內(nèi)導(dǎo)航；概念格；A*算法

近年來，隨著城市建設(shè)的突飛猛進(jìn)，各種現(xiàn)代化的高樓大廈摩肩接踵，其內(nèi)部的結(jié)構(gòu)和功能更是錯(cuò)綜復(fù)雜。而當(dāng)人們身處這樣一些陌生而復(fù)雜的環(huán)境中找尋特定的目標(biāo)時(shí)，例如包括辦公室、展覽廳、校園、醫(yī)院、博物館等室內(nèi)區(qū)域，此時(shí)，室內(nèi)導(dǎo)航就顯得尤為重要。它可以引導(dǎo)使用者在一定的時(shí)間內(nèi)使用一系列的方向序列找到目的地。此外，導(dǎo)航系統(tǒng)不僅可以用于在不熟悉的地方引導(dǎo)使用者，而且可以將程序用于導(dǎo)航機(jī)器人引導(dǎo)視覺或身體上殘疾的人通過某些環(huán)境中的安全通道。而導(dǎo)航算法是導(dǎo)航系統(tǒng)中不可或缺的一部分。本文提出了一種基于概念格的室內(nèi)導(dǎo)航算法。該算法基于位置-出口模式和形式概念分析的理論，使用概念格表示室內(nèi)環(huán)境，并利用最鄰近關(guān)系結(jié)合A*算法來查找兩個(gè)實(shí)體之間的最優(yōu)路徑。

本文的組織形式如下：

第二章介紹了概念格的相關(guān)知識(shí)，第三章提出了基于概念格的室內(nèi)導(dǎo)航算法，并給出了利用該算法進(jìn)行導(dǎo)航的實(shí)例。

（一）概念格的相關(guān)知識(shí)

概念格，又稱為Galois格，由德國的Rudolf Wille提出，并已在眾多的領(lǐng)域取得了廣泛而成功的應(yīng)用。在知識(shí)發(fā)現(xiàn)領(lǐng)域，概念格可以從關(guān)系數(shù)據(jù)中構(gòu)造出來，然后從概念格上可以提取各種類型的知識(shí)，如蘊(yùn)含規(guī)則、關(guān)聯(lián)規(guī)則、分類規(guī)則等等；在軟件工程領(lǐng)域，概念格可以從類庫的規(guī)范說明上構(gòu)造，從而對(duì)類庫結(jié)構(gòu)的可視化以及類庫的重構(gòu)和優(yōu)化提供支持；在知識(shí)工程領(lǐng)域，概念格可以用于知識(shí)庫的重新結(jié)構(gòu)化；在信息檢索方面，概念格可以實(shí)現(xiàn)對(duì)信息的有機(jī)組織。

在形式概念分析中，概念格的每個(gè)節(jié)點(diǎn)是一個(gè)形式概念，首先來介紹一下這些基礎(chǔ)概念：

定義1：形式背景是一個(gè)三元組（G,M,I）,其中G是所有對(duì)象的集合，M是所有屬性的集合，I?G×M表示G和M集合中元素之間的關(guān)系。對(duì)于元素g∈G，m∈M，（g，m）∈I表示“對(duì)象g具有屬性m”。

定義2：設(shè)（G,M,I）為一形式背景，對(duì)于集合X?G，Y?M，我們定義

則X’是X中對(duì)象的通用屬性集，Y’是Y中具有通用屬性的對(duì)象集。

定義3：設(shè)（G,M,I）為一形式背景，當(dāng)X?G，Y?M，X’=Y，Y’=X時(shí)，（G,M,I）的形式概念為（X，Y），其中X，Y分別是概念（X，Y）的外延和內(nèi)涵。形式背景（G,M,I）的所有概念集記為C（G，M，I）。

定義4：設(shè)（G,M,I）為一形式背景，（Xa，Ya）和（Xb，Yb）是C（G，M，I）中的兩個(gè)形式概念，當(dāng)且僅當(dāng)Xa?Xb或者Ya?Yb時(shí)，（Xa，Ya）≤（Xb，Yb）。此時(shí)，（Xa，Ya）是（Xb，Yb）的子概念，（Xb，Yb）是（Xa，Ya）的超概念。

由上述定義可知，關(guān)系≤是形式概念上的一個(gè)偏序，證明如下：對(duì)于C（G，M，I）下的三個(gè)形式概念（Xa，Ya），（Xb，Yb），（Xc，Yc），滿足以下性質(zhì)自反性：（Xa，Ya）≤（Xa，Ya）反對(duì)稱性：（Xa，Ya）≤（Xb，Yb）且（Xb，Yb）≤（Xa，Ya）?（Xa，Ya）=（Xb，Yb）傳遞性：（Xa，Ya）≤（Xb，Yb）且（Xb，Yb）≤（Xc，Yc）?（Xa，Ya）≤（Xc，Yc）

定義5：格（Lattice）是其非空有限子集都有一個(gè)上確界（叫并）和一個(gè)下確界（叫交）的偏序集合（poset）。

由以上概念得出概念格，C（G，M，I）的形式概念（G，M）和偏序關(guān)系≤生成一個(gè)格，稱為概念格，記為L（G，M，I）或者（C（G，M，I），≤）。概念格通過Hasse圖生動(dòng)而簡潔的表示概念及概念之間的關(guān)系。

（二）啟發(fā)式搜索A*算法

A*算法是建立在典型的Dijkstra算法上的，是由Hart、Nilsson、Raphael等人首先提出的。該算法通過選擇下一個(gè)被檢查的節(jié)點(diǎn)時(shí)引入已知的全局信息，對(duì)當(dāng)前節(jié)點(diǎn)距終點(diǎn)的距離作出估計(jì)，作為評(píng)價(jià)該節(jié)點(diǎn)處于最優(yōu)路線上的可能性的量度，這樣就可以首先搜索可能性較大的節(jié)點(diǎn)，從而提高了搜索過程的效率。

啟發(fā)式搜索就是指在路徑規(guī)劃中引入啟發(fā)信息以提高搜索效率的方法。A*算法是目前廣為流行的路徑規(guī)劃啟發(fā)式算法，對(duì)實(shí)現(xiàn)最佳優(yōu)先搜索十分有效。通過選擇合適的估價(jià)函數(shù)，A*算法尋找最優(yōu)路徑所使用的搜索空間比經(jīng)典Dijkstra算法小。采用啟發(fā)信息的目的是提供一個(gè)頂點(diǎn)距離目標(biāo)有多遠(yuǎn)的估價(jià)，以使搜索算法優(yōu)先考慮最有希望的頂點(diǎn)。具體地說，A*算法引入了當(dāng)前節(jié)點(diǎn)j的估計(jì)函數(shù)f*(j)，當(dāng)前節(jié)點(diǎn)的估計(jì)函數(shù)定義為：f*(j)=g(j)+h*(j)。其中g(shù)(j)是從起點(diǎn)到當(dāng)前節(jié)點(diǎn)j的實(shí)際最短距離，h*(j)是從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的最短距離的估計(jì)。若h*(j)=0，即沒有利用任何全局信息，這時(shí)A*算法就變成了普通的Dijkstra算法，這說明該算法也可看作Dijkstra算法的特殊情形。

算法使用時(shí)根據(jù)實(shí)際情況選擇h*(j)的具體形式，h*(j)要滿足一個(gè)要求:即不能高于節(jié)點(diǎn)到終點(diǎn)j的實(shí)際最短距離。這一條件稱為相容性條件，可以證明，如果估計(jì)函數(shù)滿足相容性條件，且原問題存在最優(yōu)解，則A*算法一定能夠求出最優(yōu)路徑。

（三）基于概念格的室內(nèi)導(dǎo)航算法

基于位置-出口理論，將室內(nèi)環(huán)境主要分為兩種實(shí)體，即位置（location）和出口（exit）。位置是指邊界帶有一個(gè)或多個(gè)出口的幾何區(qū)域，出口是指用戶可以出入位置的邊界點(diǎn)。建立一個(gè)位置-出口矩陣A=[aij]，其中aij元素為1表示在i位置有j出口，為0表示在i位置沒有j出口。

基于第一節(jié)的基礎(chǔ)概念，位置、出口以及它們之間的二元關(guān)系構(gòu)成了一個(gè)形式背景。如圖1為一建筑中的部分區(qū)域的示意圖，其中L1,L2,L3,L4,L5,L6,L7,C為位置，e1,e2,e3,e4,e5,e6,e7,e8,e9,e10為出口，根據(jù)圖1建立8*10的位置-出口矩陣，其中位置為對(duì)象集，出口為屬性集。

圖1 一建筑中的部分區(qū)域

對(duì)于位置L4有兩個(gè)出口e4和e7,且對(duì)于同時(shí)具有出口e4和e7的位置只有L4，則根據(jù)定義3，（{L4},{e4,e7}）為形式概念；對(duì)于位置L4和L5有共同的出口e7，而出口e7僅為位置L4和L5所共有，則（{L4,L5},{e7}）也為形式概念。

根據(jù)定義4，由{L4}?{L4，L5}可得，（{L4},{e4,e6}）≤（{L4,L5},{e6}）。同理可得其他形式概念，根據(jù)定義5可以將它們表示為Hasse圖，如圖2所示。圖中，節(jié)點(diǎn)均為形式概念，邊表示形式概念之間的泛化和特化的關(guān)系，Hasse圖展示了概念格中的層次結(jié)構(gòu)關(guān)系。

圖2 圖1的Hasse圖

由圖2可以得出下面這個(gè)定理，它描述了基于概念格的模型是如何來表示位置之間的關(guān)系的。定理1：設(shè)（L，E，I）為一形式背景，其中L為位置集，E為出口集，設(shè)({l1},E1),({ l2},E2)為形式概念，其中l(wèi)1∈L，l2∈L，E1?E，E2?E，如果E1∩E2不為空，則（{l1，l2}，E1∩E2）為形式概念。

證明：一個(gè)出口連接著兩個(gè)位置，也就是說，兩個(gè)以上的位置不能共享同一個(gè)出口。因此，每個(gè)概念的外延中位置的個(gè)數(shù)最多為兩個(gè)（除概念格的頂層概念以外）。E1∩E2不為空，l1，l2為概念的外延，且不超過兩個(gè)，因此，（{l1，l2}，E1∩E2）為形式概念。

概念格上存在一種語義關(guān)系稱為最鄰近關(guān)系，這種關(guān)系協(xié)助在概念格上找到最優(yōu)導(dǎo)航路徑。

定義6：設(shè)（C（G，M，I），≤）是形式背景（G，M，I），≤）的概念格，（X1，Y1）和（X2，Y2）是形式概念，（X1，Y1）和（X2，Y2）是最鄰近關(guān)系，當(dāng)且僅當(dāng)不存在（X3，Y3）使得（X1，Y1）≤（X3，Y3）≤（X2，Y2）或者（X2，Y2）≤（X3，Y3）≤（X1，Y1）。

基于最鄰近關(guān)系，下面定義了概念格上兩個(gè)形式概念的連接長度和連接強(qiáng)度。

定義7：設(shè)（C（G，M，I），≤）是形式背景（G，M，I），≤）的概念格，（Xa，Ya）和（Xb，Yb）是形式概念，如果存在概念格的形式概念序列

其中（X1，Y1）=（Xa，Ya），（Xj，Yj）=（Xb，Yb），（Xi，Yi）是（Xi+1，Yi+1）最鄰近的，1≤i≤j-1，則（Xa，Ya）（Xb，Yb）是相連的，兩概念的連接長度為（j-1），兩概念外延的連接強(qiáng)度為max（{|Xr∩Xr+1|，r=2，…，j-2}），兩概念內(nèi)涵的連接強(qiáng)度為max（{|Yr∩Yr+1|，r=2，…，j-2}）。

通過上述概念，結(jié)合A*算法，本文提出了基于概念格的導(dǎo)航算法，具體如下：

1.Hasse圖分為四層，將中間兩層的節(jié)點(diǎn)作為搜索節(jié)點(diǎn)，并初始化路徑長度作為權(quán)值；

2.找到初始位置的形式概念，在圖中表示為開始節(jié)點(diǎn)，添加該開始節(jié)點(diǎn)到開放列表；

3.重復(fù)下面的過程：

a.查找開放列表中具有最小f值的結(jié)點(diǎn)，把它作為當(dāng)前結(jié)點(diǎn);

b.將它放入封閉列表;

c.對(duì)當(dāng)前結(jié)點(diǎn)的相連結(jié)點(diǎn)的每一個(gè)，

1)如果它不可達(dá)，或者存在于封閉列表，忽略它。否則執(zhí)行下面操作；

2)如果它不在開放列表，將它添加進(jìn)去。以當(dāng)前結(jié)點(diǎn)作為其父親。記錄這個(gè)結(jié)點(diǎn)的f，g和h值；

3)如果它已經(jīng)在開放列表了，檢查到達(dá)那個(gè)結(jié)點(diǎn)的路徑是否更優(yōu)，以g值為測(cè)量值。更低的g值意味著更好的路徑。如果找到，這個(gè)結(jié)點(diǎn)的父親改為當(dāng)前結(jié)點(diǎn)，并重新計(jì)算這個(gè)結(jié)點(diǎn)的g和f值。為了保持開放列表按f值排序，需要重新排序來解決這個(gè)變化；

d.結(jié)束循環(huán)，當(dāng)

1)將目標(biāo)結(jié)點(diǎn)加入到開放列表，此時(shí)路徑已經(jīng)找到

2)沒有找到目標(biāo)結(jié)點(diǎn)，并且開放列表是空的。此時(shí)，沒有路徑

4.保存路徑。從目標(biāo)結(jié)點(diǎn)回走，從每個(gè)結(jié)點(diǎn)走到它的父親結(jié)點(diǎn)，直到抵達(dá)開始結(jié)點(diǎn)，即為路徑。

5.對(duì)路徑進(jìn)行處理，形成簡單的路徑序列。

根據(jù)以上算法，上例中從位置L4到位置L6的搜索路徑可以由以下步驟來完成，首先，L4的形式概念為（{L4},{e4,e7}），L6的形式概念為（{L6}，{e5,e6,e9}）， 查找從L4到L6的路徑就是要找到形式概念序列，通過算法可以找到序列如下：

簡化后路徑序列如下：

其中，序列（2）的長度為4，外延的連接強(qiáng)度為1，內(nèi)涵的連接強(qiáng)度為1；序列（3）的長度為4，外延的連接強(qiáng)度為1，內(nèi)涵的連接強(qiáng)度為2。

序列（2）列出了L4到L6的行走路徑如下：通過e7從L4進(jìn)入L5，再通過e9從L5進(jìn)入L6。而序列（3）列出的行走路徑如下：通過e4從L4進(jìn)入走廊C，再通過e5或者e6進(jìn)入L6。

由上可知，序列的長度表示了該路徑的行走復(fù)雜度，內(nèi)涵的連接強(qiáng)度表示出現(xiàn)意外情況時(shí)是否有備選路徑以及備選路徑的多少。其中序列（3）有可選路徑L4-＞e4-＞C-＞e5-＞L6和L4-＞e4-＞ C-＞e6-＞L6，當(dāng)出口e5和e6其中一個(gè)關(guān)閉時(shí)，可以選擇另外一條路徑。

（四）總結(jié)

本文提出了一種基于概念格的室內(nèi)導(dǎo)航算法，該算法基于位置-出口模式和形式概念分析的理論，使用概念格表示室內(nèi)環(huán)境，對(duì)于Hasse圖使用最近鄰居關(guān)系結(jié)合A*算法來查找兩個(gè)位置之間的最優(yōu)路徑。該算法可以結(jié)合語義本體來進(jìn)行上下文導(dǎo)航，根據(jù)用戶的需求和周圍的環(huán)境來進(jìn)行選路，這將作為我下一步的研究方向。

[1] Wille,R. Restructuring lattice theory: an approach based on hierarchies of concepts[A]. Proceedings of the 7th International Conference on Formal Concept Analysis[C],Darmstadt, Germany:ACM Press,2009. 314-339.

[2] Gander B, Wille R. Formal Concept Analysis[M].Mathematical Foundations. Berlin:Springer,1999.

[3] 鄒亮,徐建閩,朱玲湘.A*算法在基于電子地圖的動(dòng)態(tài)路徑誘導(dǎo)中的應(yīng)用[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2006.10,30(5):885-888.

[4] 張海濤,程蔭杭.基于A*算法的全局路徑搜索[J].機(jī)器人技術(shù),2007,23(6):238、240.

[5] 呂太之,趙春霞.基于插值A(chǔ)*算法的路徑規(guī)劃[J].機(jī)器人技術(shù),2006,22(ll):250、252.

TP29

A

1008-1151(2010)04-0040-03

2010-01-12

趙新云（1985－），女，江蘇如皋人，中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士，研究方向?yàn)榈乩硇畔⑾到y(tǒng)和本體；劉厚泉（1963－），男，江蘇徐州人，中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院副教授，博士，研究方向?yàn)橐蛱鼐W(wǎng)信息集成、GIS及虛擬現(xiàn)實(shí)。