赵新云 刘厚泉

（中国矿业大学计算机科学与技术学院，江苏 徐州 221116)

一种基于概念格的室内导航算法

赵新云 刘厚泉

（中国矿业大学计算机科学与技术学院，江苏 徐州 221116)

文章首先建立一个室内导航模型，提出了一种基于概念格的室内导航算法，该算法基于位置-出口模式和形式概念分析的理论，使用概念格表示室内环境，并使用最近邻居关系结合A*算法来查找两个实体之间的最优路径。

室内导航；概念格；A*算法

近年来，随着城市建设的突飞猛进，各种现代化的高楼大厦摩肩接踵，其内部的结构和功能更是错综复杂。而当人们身处这样一些陌生而复杂的环境中找寻特定的目标时，例如包括办公室、展览厅、校园、医院、博物馆等室内区域，此时，室内导航就显得尤为重要。它可以引导使用者在一定的时间内使用一系列的方向序列找到目的地。此外，导航系统不仅可以用于在不熟悉的地方引导使用者，而且可以将程序用于导航机器人引导视觉或身体上残疾的人通过某些环境中的安全通道。而导航算法是导航系统中不可或缺的一部分。本文提出了一种基于概念格的室内导航算法。该算法基于位置-出口模式和形式概念分析的理论，使用概念格表示室内环境，并利用最邻近关系结合A*算法来查找两个实体之间的最优路径。

本文的组织形式如下：

第二章介绍了概念格的相关知识，第三章提出了基于概念格的室内导航算法，并给出了利用该算法进行导航的实例。

（一）概念格的相关知识

概念格，又称为Galois格，由德国的Rudolf Wille提出，并已在众多的领域取得了广泛而成功的应用。在知识发现领域，概念格可以从关系数据中构造出来，然后从概念格上可以提取各种类型的知识，如蕴含规则、关联规则、分类规则等等；在软件工程领域，概念格可以从类库的规范说明上构造，从而对类库结构的可视化以及类库的重构和优化提供支持；在知识工程领域，概念格可以用于知识库的重新结构化；在信息检索方面，概念格可以实现对信息的有机组织。

在形式概念分析中，概念格的每个节点是一个形式概念，首先来介绍一下这些基础概念：

定义1：形式背景是一个三元组（G,M,I）,其中G是所有对象的集合，M是所有属性的集合，I⊆G×M表示G和M集合中元素之间的关系。对于元素g∈G，m∈M，（g，m）∈I表示“对象g具有属性m”。

定义2：设（G,M,I）为一形式背景，对于集合X⊆G，Y⊆M，我们定义

则X’是X中对象的通用属性集，Y’是Y中具有通用属性的对象集。

定义3：设（G,M,I）为一形式背景，当X⊆G，Y⊆M，X’=Y，Y’=X时，（G,M,I）的形式概念为（X，Y），其中X，Y分别是概念（X，Y）的外延和内涵。形式背景（G,M,I）的所有概念集记为C（G，M，I）。

定义4：设（G,M,I）为一形式背景，（Xa，Ya）和（Xb，Yb）是C（G，M，I）中的两个形式概念，当且仅当Xa⊆Xb或者Ya⊆Yb时，（Xa，Ya）≤（Xb，Yb）。此时，（Xa，Ya）是（Xb，Yb）的子概念，（Xb，Yb）是（Xa，Ya）的超概念。

由上述定义可知，关系≤是形式概念上的一个偏序，证明如下：对于C（G，M，I）下的三个形式概念（Xa，Ya），（Xb，Yb），（Xc，Yc），满足以下性质自反性：（Xa，Ya）≤（Xa，Ya）反对称性：（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）是其非空有限子集都有一个上确界（叫并）和一个下确界（叫交）的偏序集合（poset）。

由以上概念得出概念格，C（G，M，I）的形式概念（G，M）和偏序关系≤生成一个格，称为概念格，记为L（G，M，I）或者（C（G，M，I），≤）。概念格通过Hasse图生动而简洁的表示概念及概念之间的关系。

（二）启发式搜索A*算法

A*算法是建立在典型的Dijkstra算法上的，是由Hart、Nilsson、Raphael等人首先提出的。该算法通过选择下一个被检查的节点时引入已知的全局信息，对当前节点距终点的距离作出估计，作为评价该节点处于最优路线上的可能性的量度，这样就可以首先搜索可能性较大的节点，从而提高了搜索过程的效率。

启发式搜索就是指在路径规划中引入启发信息以提高搜索效率的方法。A*算法是目前广为流行的路径规划启发式算法，对实现最佳优先搜索十分有效。通过选择合适的估价函数，A*算法寻找最优路径所使用的搜索空间比经典Dijkstra算法小。采用启发信息的目的是提供一个顶点距离目标有多远的估价，以使搜索算法优先考虑最有希望的顶点。具体地说，A*算法引入了当前节点j的估计函数f*(j)，当前节点的估计函数定义为：f*(j)=g(j)+h*(j)。其中g(j)是从起点到当前节点j的实际最短距离，h*(j)是从当前节点到终点的最短距离的估计。若h*(j)=0，即没有利用任何全局信息，这时A*算法就变成了普通的Dijkstra算法，这说明该算法也可看作Dijkstra算法的特殊情形。

算法使用时根据实际情况选择h*(j)的具体形式，h*(j)要满足一个要求:即不能高于节点到终点j的实际最短距离。这一条件称为相容性条件，可以证明，如果估计函数满足相容性条件，且原问题存在最优解，则A*算法一定能够求出最优路径。

（三）基于概念格的室内导航算法

基于位置-出口理论，将室内环境主要分为两种实体，即位置（location）和出口（exit）。位置是指边界带有一个或多个出口的几何区域，出口是指用户可以出入位置的边界点。建立一个位置-出口矩阵A=[aij]，其中aij元素为1表示在i位置有j出口，为0表示在i位置没有j出口。

基于第一节的基础概念，位置、出口以及它们之间的二元关系构成了一个形式背景。如图1为一建筑中的部分区域的示意图，其中L1,L2,L3,L4,L5,L6,L7,C为位置，e1,e2,e3,e4,e5,e6,e7,e8,e9,e10为出口，根据图1建立8*10的位置-出口矩阵，其中位置为对象集，出口为属性集。

图1 一建筑中的部分区域

对于位置L4有两个出口e4和e7,且对于同时具有出口e4和e7的位置只有L4，则根据定义3，（{L4},{e4,e7}）为形式概念；对于位置L4和L5有共同的出口e7，而出口e7仅为位置L4和L5所共有，则（{L4,L5},{e7}）也为形式概念。

根据定义4，由{L4}⊆{L4，L5}可得，（{L4},{e4,e6}）≤（{L4,L5},{e6}）。同理可得其他形式概念，根据定义5可以将它们表示为Hasse图，如图2所示。图中，节点均为形式概念，边表示形式概念之间的泛化和特化的关系，Hasse图展示了概念格中的层次结构关系。

图2 图1的Hasse图

由图2可以得出下面这个定理，它描述了基于概念格的模型是如何来表示位置之间的关系的。定理1：设（L，E，I）为一形式背景，其中L为位置集，E为出口集，设({l1},E1),({ l2},E2)为形式概念，其中l1∈L，l2∈L，E1⊆E，E2⊆E，如果E1∩E2不为空，则（{l1，l2}，E1∩E2）为形式概念。

证明：一个出口连接着两个位置，也就是说，两个以上的位置不能共享同一个出口。因此，每个概念的外延中位置的个数最多为两个（除概念格的顶层概念以外）。E1∩E2不为空，l1，l2为概念的外延，且不超过两个，因此，（{l1，l2}，E1∩E2）为形式概念。

概念格上存在一种语义关系称为最邻近关系，这种关系协助在概念格上找到最优导航路径。

定义6：设（C（G，M，I），≤）是形式背景（G，M，I），≤）的概念格，（X1，Y1）和（X2，Y2）是形式概念，（X1，Y1）和（X2，Y2）是最邻近关系，当且仅当不存在（X3，Y3）使得（X1，Y1）≤（X3，Y3）≤（X2，Y2）或者（X2，Y2）≤（X3，Y3）≤（X1，Y1）。

基于最邻近关系，下面定义了概念格上两个形式概念的连接长度和连接强度。

定义7：设（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），两概念外延的连接强度为max（{|Xr∩Xr+1|，r=2，…，j-2}），两概念内涵的连接强度为max（{|Yr∩Yr+1|，r=2，…，j-2}）。

通过上述概念，结合A*算法，本文提出了基于概念格的导航算法，具体如下：

1.Hasse图分为四层，将中间两层的节点作为搜索节点，并初始化路径长度作为权值；

2.找到初始位置的形式概念，在图中表示为开始节点，添加该开始节点到开放列表；

3.重复下面的过程：

a.查找开放列表中具有最小f值的结点，把它作为当前结点;

b.将它放入封闭列表;

c.对当前结点的相连结点的每一个，

1)如果它不可达，或者存在于封闭列表，忽略它。否则执行下面操作；

2)如果它不在开放列表，将它添加进去。以当前结点作为其父亲。记录这个结点的f，g和h值；

3)如果它已经在开放列表了，检查到达那个结点的路径是否更优，以g值为测量值。更低的g值意味着更好的路径。如果找到，这个结点的父亲改为当前结点，并重新计算这个结点的g和f值。为了保持开放列表按f值排序，需要重新排序来解决这个变化；

d.结束循环，当

1)将目标结点加入到开放列表，此时路径已经找到

2)没有找到目标结点，并且开放列表是空的。此时，没有路径

4.保存路径。从目标结点回走，从每个结点走到它的父亲结点，直到抵达开始结点，即为路径。

5.对路径进行处理，形成简单的路径序列。

根据以上算法，上例中从位置L4到位置L6的搜索路径可以由以下步骤来完成，首先，L4的形式概念为（{L4},{e4,e7}），L6的形式概念为（{L6}，{e5,e6,e9}）， 查找从L4到L6的路径就是要找到形式概念序列，通过算法可以找到序列如下：

简化后路径序列如下：

其中，序列（2）的长度为4，外延的连接强度为1，内涵的连接强度为1；序列（3）的长度为4，外延的连接强度为1，内涵的连接强度为2。

序列（2）列出了L4到L6的行走路径如下：通过e7从L4进入L5，再通过e9从L5进入L6。而序列（3）列出的行走路径如下：通过e4从L4进入走廊C，再通过e5或者e6进入L6。

由上可知，序列的长度表示了该路径的行走复杂度，内涵的连接强度表示出现意外情况时是否有备选路径以及备选路径的多少。其中序列（3）有可选路径L4-＞e4-＞C-＞e5-＞L6和L4-＞e4-＞ C-＞e6-＞L6，当出口e5和e6其中一个关闭时，可以选择另外一条路径。

（四）总结

本文提出了一种基于概念格的室内导航算法，该算法基于位置-出口模式和形式概念分析的理论，使用概念格表示室内环境，对于Hasse图使用最近邻居关系结合A*算法来查找两个位置之间的最优路径。该算法可以结合语义本体来进行上下文导航，根据用户的需求和周围的环境来进行选路，这将作为我下一步的研究方向。

[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*算法在基于电子地图的动态路径诱导中的应用[J].武汉理工大学学报(交通科学与工程版),2006.10,30(5):885-888.

[4] 张海涛,程荫杭.基于A*算法的全局路径搜索[J].机器人技术,2007,23(6):238、240.

[5] 吕太之,赵春霞.基于插值A*算法的路径规划[J].机器人技术,2006,22(ll):250、252.

TP29

A

1008-1151(2010)04-0040-03

2010-01-12

赵新云（1985－），女，江苏如皋人，中国矿业大学计算机科学与技术学院硕士，研究方向为地理信息系统和本体；刘厚泉（1963－），男，江苏徐州人，中国矿业大学计算机科学与技术学院副教授，博士，研究方向为因特网信息集成、GIS及虚拟现实。