（计算机应用技术专业论文）楼宇三维路径的生成、规划及表达.pdf

摘要 摘要 寻路是人们日常生活中必不可少的基本问题。通常根据应用环境的不同，可 以将寻路问题分为两大类：室外和室内。室外寻路问题的一个典型应用就是交通 寻路。用于交通寻路的例子有基于w e b 的电子地图和车载g p s 导航等。室外的寻 路问题得到了人们很大的关注。然而，室内的路径查找则常常被忽视。事实上很 多人在高层的建筑物中进行寻路时是非常低效的。尤其是在一个陌生的建筑物环 境当中，人们的室内寻路会更加低效。因此，高效的室内寻路问题成为目前的一 个研究热点。如何帮助人们有效地在室内寻路尤其是高层建筑物内寻路是本文的 研究重点。论文的主要内容如下： l _ ) 路径模型的自动生成。详细介绍了路径模型的生成过程：首先，使用基于 数学形态学的细化算法、特征点提取算法等建立一层楼的楼道路径，并将 房间等楼层实体作为结点连接到楼道路径上。房间内部结构可以单独考 虑，从而建立好一层楼的路径图；然后利用楼梯结点和电梯结点将相邻的 楼层路径图相互连接起来，从而生成整个建筑的三维路径模型。该路径模 型是由弧和结点结构组成的带权图结构。根据弧上赋予的权值不同，路径 模型可以应用到很多的领域。例如在火灾发生的建筑物环境当中，权值可 以代表通过路径的代价，该代价由火势，温度，烟雾浓度等定义。 2 ) 路径规划。首先提出了路径权值的更新方法，这些权值是由安装在建筑物 各个部位的真实传感器数据进行综合而得到的。这样的权值信息能够符合 建筑物内部的实时环境。然后介绍了启发式搜索，并利用启发式的a 幸算 法在路径模型中实现了最佳路径检索。最后提出了一个根据生成的路径模 型制定人员疏散计划的数学模型。该数学模型利用时间展开网络和最小费 用流的线性规划方法求得最佳疏散计划。 3 ) 路径表达。路径表达分为图形化表达和自然语言表达。图形化的路径表达 是将检索到的最佳路径显示在三维建筑场景当中。在三维的显示中，提供 了基本的交互界面，即：选择起始实体( 结点) 和目标实体( 结点) 。在这一 交互的过程中主要用n - 维屏幕坐标到三维空间坐标的变换和三维对象 拾取。最后，讨论了如何将这些由结点和弧组成的最佳路径通过自然语言 进行表达。 关键词：三维路径模型；路径自动生成；路径规划；路径表达 分类号：t p 7 5 1 北京交通大学硕士学位论文 a bs t r a c t w a y f i n d i n gi s an e c e s s a r i l yb a s i ci s s u ei np e o p l e sd a i l yl i f e t h ep r o b l e mo f w a y f i n d i n g c a nb ed i v i e d e di n t ot w ok i n d s a c c o r d i n gt o d i f f e r e n ta p p l i c a t i o n e n v i r o n m e n t s ：i n d o o r sa n do u t d o o r s at y p i c a la p p l i c a t i o no fo u t d o o rw a y f i n d i n gi st o f i n dp a t h si nat r a f f i cs y s t e m ，i e e l e c t r o n i cm a p sb a s e do nw e ba n dg p s n a v i g a t i o nf o r c a r s o u t d o o rw a y f i n d i n gp r o b l e mh a da t t r a c t e dm o r ep e o p l e sa t t e n t i o n h o w e v e r , i n d o o rw a y f i n d i n gp r o b l e m sa reo f t e ni g n o r e db yp e o p l e i nf a c t ，t h ee f f i c i e n to f f i n d i n g ap a t hi nab u i l d i n gi sv e r yl o wf o rm a n yp e o p l e ，e s p e c i a l l yf o rt h e s ep e o p l ew h oa r ei n a nu n f a m i l i a rb u i l d i n ge n v i r o n m e n t a sar e s u l t ，h i g he f f i c i e n ti n d o o r w a y f i n d i n g b e c a m e sar e s e a r c hf o c u sn o w t h ee m p h a s i so ft h i sp a p e ri sj u s tt of i n dam e t h o do f h o wt oh e l pp e o p l ee f f i c i e n t l yf i n dap a t hi ni n d o o re n v i r o n m e n te s p e c i a l l yi nat a l l b u i l d i n g t h em a i nc o n t e n t so ft h i sp a p e ra r e 1 ) a u t o m a t i c a l l yg e n e r a t i n gr o u t em o d e l ( 黟a p h ) i nt h i ss e c t i o n ，t h ep r o c e s so f h o wt oa u t o m a t i c a l l yg e n e r a t i n gr o u t em o d e li si n t r o d u c e d f i r s t ，h a l l w a y so f o n ef l o o r a r ec o n s t r u c t e db yu t i l i z i n gi m a g et h i n n i n ga l g o r i t h mb a s eo n m a t h e m a t i c a lm o r p h o l o g ya n dc h a r a c t e r i s t i cp o i n td e t e c t i n ga l g o r i t h m t h e n w ec a nc o n n e c te n t i t i e sn o d e st ot h e s eh a l l w a y s ar o u t em o d e lo fo n ef l o o r c a nb ec o n s t r u c t e db yt h i sm e t h o d a tl a s tw el i n ke v e r yt w on e i g h b o r i n g f l o o r sb yc o n n e c t i n gt h ep o r t a ln o d e sl i k es t a i r sn o d e sa n de l e v a t o rn o d e s c o n s e q u e n t l y , at h r e e d i m e n s i o n a lr o u t em o d e lh a sb e e n e v e n t u a l l y c o n s t r c t e d t h er o u t em o d e li saw e i g h t e dg r a p hw h i c hi sc o m p o s e do fn o d e s a n da r c s t h er o u t eg r a p hc a i lb ea p p l i e di nm a n yd o m a i n sa c c o r d i n gt o d i f f e r e n tw e i g h td e f i n a t i o n s f o re x a m p l e ，i tc a nb ea p p l i e di nf i r e f i g h t i n g s y s t e m s t h ew e i g h t sa r ea b l et or e p r e s e n tt h ec o s to fp a s s i n gs o m ea r c s i n t h ec a s e ，t h ew e i g h ti sd e c i e d e db yf i r ec o n d i t i o n s ，t e m p e r a t u r e ，a n ds m o k e d e n s i t y 2 ) r o u t ep l a n n i n g f i r s t ，am e t h o do fu p d a t i n gw e i g h t si sp r o p o s e di nt h i s s e c t i o n t h e s ew e i g h t s v a l u e sc a nb ef i g u r e do u tb ys y n t h e s i z i n gt h es e n s o r d a t aw h i c ha r ed e r i v e df r o mr e a ls e n s o rd e v i c e s t h e s ew e i g h t sc a nw e l l r e f l e c tt h er u n t i m ee n v i r o n m e n to fb u i l d i n g t h e nw ei n t r o d u c e dh e u r i s t i c s e a r c ha n di m p l e m e n t e dt h eh e u r i s t i ca 木a l g o r i t h mt of i n dt h eo p t i m a lp a t h a tl a s t ，am a t h e m a t i c a lm o d e lo f m a k i n ga ne v a c u a t i o np l a ni sp r o p o s e d t h e m a t h e m a t i c a lm o d e lu s et i m e - e x p a n d e dn e t w o r ka n dl i n e a rp r o g r a m m i n go f m i n c o s tf l o wt oc a l c u l a t et h ee v a c u a t i o np l a n 3 ) r o u t ee x p r e s s i o n r o u t ee x p r e s s i o ni n c l u d e sg r a p h i cr o u t ee x p r e s s i o na n d n a t u r a ll a n g u a g er o u t ee x p r e s s i o n g r a p h i cr o u t ee x p r e s s i o ni st od i s p l a yt h e r e t r i e v e do p t i m a lp a t hi n3 db u i l d i n gs c e n e i n3 db u i l d i n gs c e n e ，a n i n t e r a c t i v ei n t e r f a c ew h i c hp r o v i d e st h ef u n c t i o no fs e l e c t i n gas t a r te n t i t y ( n o d e ) a n dad e s t i n a t i o ne n t i t y ( n o d e ) i sp r o v i d e d w em a i n l yu s ea t r a n s f o r i l l a t i o nf r o mt w o d i m e n s i o n a ls c r e e nc o o r d i n a t et ot h r e e d i m e n s i o n a l s p a c ec o o r d i n a t ea n dp i c ku pat h r e e - d i m e n s i o n a lo b j e c ti na l li n t e r a c t i v e s y s t e m a tl a s t ，w et r a n s f o r mt h eo p t i m a lp a t hw h i c hi sc o m p o s e do f n o d e a n da r c si n t on a t u r a ll a n g u a g er o u t ed e s c r i p t i o n k e y w o r d s ：t h r e e - d i m e n s i o n a lr o u t em o d e l ；a u t o m a t i c a l l yg e n e r a t i n gr o u t e ；r o u t e p l a n n i n g ；r o u t ee x p r e s s i o n c l a s s n o ：t p 7 5 1 v 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：准交k 签字日期：裾年莎月6 日 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：市奂欠 签字日期： 矽。8 年易月日 北京交通大学硕士学位论文 致谢 本论文的工作是在我的导师黄雅平副教授的悉心指导下完成的，黄雅平副教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢二 年来黄雅平老师对我的关心和指导。 黄雅平副教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都 给予了我很大的关心和帮助，在此向黄雅平老师表示衷心的谢意。 黄雅平副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示 衷心的感谢。 在实验室工作及撰写论文期间，向为、王玲等同学对我论文中的可见图部分 的研究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 北京交通大学硕士学位论文 序 本文提出了一种应用于建筑物模型的路径模型。首先概括介绍了课题的研究 背景和意义，并讨论和本课题关系密切的相关研究现状。然后在第二部分介绍了 建筑物模型和现有的路径模型。第三部分重点讨论了如何根据建筑楼层图自动生 成一个三维的路径模型，该部分自动生成三维路径模型的方法已经发表到一篇论 文中，有望被e i 检索。第四部分讨论在生成好的路径模型基础上进行路径规划， 包括路径权值的更新，最短路径的计算和疏散计划的制定。第五部分则讨论了将 搜索的最短路径三维显示在建筑物场景当中，以及如何将最短路径转换为自然语 言的表达。 拓扑图结构的路径模型有着很大的应用空间，它是路径规划和导航应用的基 础。机器人导航和最短路径的计算都离不开路径模型，此外建筑物内部的路径模 型还可以用于制定在紧急情况下的人员疏散计划。本文详细地讨论了路径的生成， 规划和表达，并结合图表，实验结果和框架图，以及数学模型等对所用到的技术 和原理进行了阐述。在系统的设计和实现过程中，除了参考国内外前人的研究成 果外，也遇到了很多的新的技术和挑战。 概论 1 1 课题的研究背景 1 概论 建筑信息模型( b u i l d i n gi n f o r m a t i o nm o d e l i n g ，b i m l ) 是一项新技术，正引领着 建筑业信息技术走向更高的层次。b i m 是指通过数字信息仿真模拟建筑物所具有 的真实信息，在这里，信息的内涵不仅仅是几何形状描述的视觉信息，还包含大 量的非几何信息，如材料的耐火等级、材料的传热系数、构件的造价、采购信息 等。实际上，b i m 就是通过数字化技术，在计算机中建立一座虚拟建筑，一个建 筑信息模型就是提供了一个单一的、完整一致的、逻辑的建筑信息库。它对于过 去2 0 年来由c a d 主导的二维电子建筑工程制图带来了第二次的革命，即从二维 图纸到三维设计和建造的革命，第一次的革命是由手绘工程图纸到电子二维图纸 的革命。建筑信息模型( b i m ) 的技术核心是一个由计算机三维模型所形成的数据 库，不仅包含了建筑师的设计信息，而且可以容纳从设计到建成使用，甚至是使 用周期终结的全过程信息，并且各种信息始终是建立在一个三维模型数据库中。 美国标准化委员会( n i s t 2 ) 提出了初始的b i m 工程标准，来解决建筑物信息建模的 问题。本论文提出的三维路径正是用于服务建筑信息模型，从而完善模型系统。 路径规划的一个典型应用是导航。导航是一个技术门类的总称，它是引导飞 机、船舶、车辆以及个人( 总称作运载体) 安全、准确地沿着选定的路线，准时到达 目的地的一种手段。我们每天的行动实质上都是一种广义范围的导航，即我们会 选择一条代价最小的路径到达目的地。今天，随着人类活动的发展，对导航的要 求越来越高。现在很成熟的一个导航应用即为交通系统中普遍使用的车载g p s 导 航，借助于g p s 的导航信息提示，司机可以高效地驾驶，尤其是在一个司机不太 熟悉的城市交通环境中。机器人等智能设备的导航则是导航领域的前沿研究，吸 引了大批的学者和科学家投身其中，如专门用于室内导航研究的不来梅室内机器 人r o l l a n d 3 1 】， 2 】，另外近年来虚拟环境的导航如电脑游戏的导航和路径规划也引 起了人们的关注【3 】。 本论文的室内路径模型，是根据基于建筑信息模型生成的建筑物楼层平面图 h t t p ：e n w i k i p e d i a o r g w i k i b u i l d i n g _ i n f o r m a t i o n _ m o d e l i n g ；h t t p ：u s a a u t o d e s k c o m a d s k 2 n a t i o n a li n s t i t u t eo fs t a n d a r d sa n d t e c h n o l o g y 3 h t t p ：w w w i n f o r m a t i l u n i - b r c m c n d e r o l l a n d i n d c x _ e h u n 北京交通大学硕士学位论文 自动生成的。该路径模型可以作为楼宇智能化和人性化的功能完善。路径的规划 既可以是楼宇内的最优路径导航，也可以是楼字发生紧急情况的人员疏散计划的 制定。其中路径导航可以是在终端设备上的显示，又可以是导航路径自然语言的 描述在移动设备上的应用，描述的形式不一定局限于文本，还可以是语音，图像 和带有指示箭头的路径提示，也可以是这些形式的混合。 1 2 课题的研究意义 当今的许多应用领域，例如消防系统，交通导航，紧急情况的人员疏散，楼 宇安全等，路径模型提取和导航是必不可少的一部分。车载g p s 在交通领域的定 位和导航作用已经得到了实践的证实。本文的提出了楼宇三维路径模型的自动生 成系统，并在该路径模型的帮助下制定和用户要求的应用领域相关的路径规划。 例如，在建筑物发生火灾的紧急情况下，路径模型是制定合理人员疏散计划的基 础。火灾逃生计划可以是一条几何最短逃生路径，也可以是一条根据目前的楼内 火势和烟雾等实际情况相关的代价最小路径。紧急情况下的疏散计划则依赖于楼 内的火势和人员的真实分布。合理的逃生路径和符合实际情况的疏散计划都能够 有效减小人员伤亡。 鉴于现有g p s 导航系统在室内导航能力不足的缺点，本文的三维路径模型可 以用于完成室内的路径导航。根据来访者给出的起始位置和目标位置，该模型可 以生成最短路径并显示在三维场景下，从而起到室内导航的作用。实际情况下， 乘客的导航是室外交通导航和车站室内导航的结合，尤其是需要在大型复杂的换 乘站，如大型国际机场更需要站内导航。在室外的情况下，乘客可以根据现有的 g p s 导航系统选择合理的乘车线路到达中转站，而站内的导航则可以依据本文提 出的室内导航模型，这样即把乘客的行程完全做到了全程导航。该路径模型还可 以用于虚拟环境，如在三维游戏中的寻径任务，当然用于游戏场景寻径时路径的 生成过程就和应用于建筑物内的情况有所不同，因为游戏寻径更多的时候是从整 个场景寻径，可能包括室外和室内，但是路径模型同样可以适用。和游戏导航相 似，机器人导航同样也可以使用本路径模型作为先验的全局路径，但是在大多数 情形下，机器人三维路径模型的生成是根据安装在室内各个角落的传感器而生成 的。j a no l i v e rw a l l g r u n 4 在他的论文中提出的路径图就是基于安装在屋顶和墙角 等处的传感器而建立的，这些传感器可以为机器人感知，从而帮助其完成路径导 航，实际上这种服务于机器人导航的路径建立过程，传感器的分布情况最终决定 了路径模型的生成。 本文提出的路径生成，最大特点即为路径模型是根据各楼层的建筑平面图自 2 概论 动生成的，这样自动生成的路径模型极大地节省了手动生成路径的时间和成本。 自动的生成模型不需要用户的干预，从而增强了系统的可使用性。对于不同的建 筑物，用户只要输入完整的楼层平面图就可以，然后系统自动建立好路径模型， 从而加强了系统的适应能力。 1 3 课题的相关研究 1 3 1 室内机器人导航 室内移动机器人导航作为当今最前沿的科技之一，吸引了大批的专家和学者 投身其中，并且成为每年一届的在不来梅举行的国际空间感知会议( i c s c 4 ) 的一个 重要议题而提出。室内机器人导航的基本内容有基于环境理解的全局定位，目标 识别和障碍物检测，安全保护三个方面： 1 ) 基于环境理解的全局定位，即通过对环境中景物的理解，识别人为的目标 或具体的实物，以完成对机器人的定位，为路径的规划提供素材； 2 ) 目标识别和障碍物检测，即实时对地面上的障碍物进行检测或对于特定目 标进行检测和识别，提高控制系统的稳定性； 3 ) 安全保护，即能够对于地面上出现的凹陷和移动的物体进行分析，以避免 对机器人造成损伤。 定位系统这里不再详细的描述，因为这不是本文要研究的重点。j o a n ah o i s 5 等利 用和应用领域相关联的本体论作为机器可处理的元数据进行描述，实现了基于对 话交互模式的三维图像物体识别原型系统。该系统实质上是将机器人视觉和图像 处理结合起来的一种应用，借助于应用环境的本体数据模型，该机器人可以将识 别到的物体分类，然后再利用用户的提示给出精确的识别结果。安全保护，实际 上也是机器人视觉的一种应用，只是在机器人识别障碍环境的基础上，进行路径 分析从而避免机器人碰撞到这些障碍物。 移动机器人的路径规划明确规定的定义为：寻找一条从出发点到目的地的一 条无碰撞的最优或者次优路径，这和本文提到的路径规划概念有着区别和联系。 本文的路径规划包含了机器人导航的含义。机器人的路径规划方式可以分为两类： 基于环境先验信息的全局路径规划和基于传感器信息的局部路径规划。全局路径 规划也可以称为全局的路径模型的表示，这也是和本文关联最为紧密之处，这里 的路径模型要包含机器人能够理解的数据表达。因此从某种程度上来说，机器人 4i n t e r n a t i o n a lc o n f c j r c n c e o ns p a t i a lc o g n i t i o n , h t t p ：c o n f c r c n c e s p a t i a l - c o g n i t i o n d e 3 北京交通大学硕士学位论文 导航是路径模型表述和人机交互的结合。在机器人层面，路径数据的描述要足够 详细和规范，以满足机器人可以理解的要求；而在用户端的层面，则需要更加的 抽象和自然化，从而达到自然语言可交互的目的。 全局路径规划主要包含可见图( v i s i b i l i t yg r a p h ) 法，环境栅格( 鲥d ) 法、和自由 空间法。可视图法是将机器人视为一点，将机器人、目标点和多边形障碍物的各 项点进行组合连接，要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之 间以及各障碍物顶点与顶点之间的连线，均不能穿越障碍物，即直线是可视的。 搜索最优路径的问题变为求这些可视直线的最短距离问题，可运用优化算法，简 化可视图，缩短搜索时间。栅格法将机器人工作环境分解成一系列具有二值信息 的网格单元，多采用基于位置码的四叉树或八叉树建模方法，并通过优化算法完 成路径搜索，目前游戏中( 如a g eo fe m p i r e s ) 的寻径算法一般是基于这种方式的路 径规划。自由空间法是采用预先定义的如广义锥形和凸多边形等基本形状构造自 由空间，并将自由空间表示为连通图，通过搜索连通图来进行路径规划，其算法 的复杂程度往往与障碍物的个数成正比。该法比较灵活，机器人起始点和目标点 的改变不会造成连通图的重构，但不是任何情况下都能获得最短路径。本文中采 用的路径模型生成即是基于自由空间法( 本文称为拓扑图法) 建立的，对于这三种全 局规划法论文后面会详细的介绍。 局部路径规划实际上是不依赖于完整的环境路径模型，机器人在行动的过程 中根据实时的环境来作出行动，局部路径规划主要方法有：人工势场法、遗传算 法和模糊逻辑算法等。人工势场法的基本思想是将机器人的工作空间视为一种虚 拟力场，障碍物产生斥力，目标点产生引力，引力和斥力的合力作为机器人的加 速力，来控制机器人的运动方向和计算机器人的位置。该法结构简单，便于低层 的实时控制，在进行实时避障和平滑的轨迹控制方面，得到了广泛的应用，但这 种方法存在局部最优解的问题，因而可能使机器人在到达目标点之前就停留在局 部最优点。遗传算法是一种借鉴生物界自然选择和遗传机制的搜索算法，由于它 具有简单、健壮、隐含并行性和全局优化等优点，对于传统搜索方法难以解决的 复杂和非线性问题具有良好的适用性。应用遗传算法解决自主移动机器人动态环 境中路径规划问题，可以避免困难的理论推导，直接获得问题的最优解。模糊控 制算法模拟驾驶员的驾驶思想，将模糊控制本身所具有的鲁棒性和基于生理学上 的“感知一动作”行为结合起来，适用于时变未知环境下的路径规划，实时性较 好。局部路径规划可以看作为机器人行动智能化的体现，这综合了环境目标的识 别和分析，机器人实时的推理判断，然而我们的路径规划是要在路径模型生成的 基础上去完成的。 4 概论 1 3 2 室内g p s 导航 在九十年代，g p s 向世界展示了全球定位设备的强大力量并为三维测量设立 了新的标准。通过把及时三维坐标提供给一个系列传感器，g p s 给三维坐标信息 的使用方法进行了一场革命。然而直至今天，依靠卫星定位的g p s 信号依然很弱 以致于不足以穿越建筑物的墙壁，这样就造成了其在室内导航的局限。在上世纪 九十年代，美国a r cs e c o n d 5 公司在g p s 启发下开发了室内g p s ，并且公司成为室 内g p s 的专利持有者。该系统使用红外脉冲激光发射器代替卫星的作用，接收器 根据发射器投射来的光线时间特征参数，计算接收器所在点的角度和位置，并将 模拟信号转换成数字脉冲信号，通过无线网络发送给中央控制室的服务器，最后 通过室内g p s 自行开发的软件或第三方测量软件( 如s a 、m e t r o l o gi i 、m a y a 等 等) 处理数据获得高精度的信息，并供远端的多用户共享。室内g p s 主要应用于飞 机制造、卫星制造等航空航天领域，汽车、造船以及工业测量等领域。它的主要 功能体现在：实时监控、移动导航、在线检测、大部件的空间尺寸三维测量以及 逆向工程等等。即实时监控被测物体在生产、安装和维修过程中的位置和状态； 跟踪和导航工作区域内的起重机、机器人或其它移动设备及工具；实时在线检测 生产装配线或实验室研究的质量控制。现有的室内g p s 导航和室外的g p s 导航不 同，室内的g p s 导航并不依赖于卫星，之所以都以g p s 命名，是因为室内g p s 的定位原理和室外的g p s 定位原理模型是相同的。在工作区域的室内空间安装几 个固定的红外发射器，每个发射器都通过红外波段发出类似与g p s 卫星的定位信 号。在需要测量的加工点只需要安装一个接收器，就可以通过模拟的室内卫星信 号精确实时定位。虽然室内的g p s 定位技术可以实现室内环境定位精度在0 2 m m ， 但是这样的定位系统依赖于大量的硬件设备支持，如传感器，信号接受器等，并 且服务的对象主要为工业领域的工业生产，自动控制和设备检测。以美国a r c s e c o n d 公司的室内g p s 为例，就需要激光发射器、圆柱型感应器、扁平型感应器、 v - b a r 测量探测器、调制解调器等硬件的支持。路径的自然语言描述加上精确的定 位系统，可以很好的完成室内导航的功能，这样室内的路径导航便可以帮助弱势 群体如残疾人，老人等在室内的行动。荷兰阿姆斯特丹大学的一个发明家就将室 内g p s 导航应用到服务于老人行动的实际中去。考虑到老年人的身体条件，他们 外出活动有一定的困难。现在借助于室内g p s 导航，他们可以更加随意的在室内 走动。这是室内g p s 首次针对某一特定功能而设计，之前的工业领域的室内g p s 都太过一般化，没有像车载g p s 那样融入到人们的日常生活中。现有的室内g p s 5 h t t p ：w w w a r c s e c o n d c o m 5 北京交通火学硕+ 学位论文 不需要生成路径模型表述，这里的精确的定位系统可以为本文将要提出的导航路 径描述起到很好的作用，但是这对于制定紧急情况的人员疏散计划制定不能起到 有效的技术支持，路径模型的生成对于制定疏散计划极为重要。 1 3 3 建筑物人员疏散 密集场所的人员疏散一直是建筑物火灾发生时的一个重要话题，由于人们在 发生火灾的时候，受到内部自身心理，包括恐惧、惊慌、冲动、侥幸、个体孤独 和从众心理等【6 】和外部环境条件，包括烟雾浓度，火势蔓延和环境温度等的内外 因素影响，人们很可能作出错误的逃生行为，如跳楼，选择电梯逃生等。随着经 济的高速发展，大型的高楼如购物商场，写字楼等人员非常密集，一旦发生火灾， 人员的有效疏散显得极为重要。火灾踩踏事件成为不合理疏散的一个典型，可以 说火灾踩踏是由于人们不遵守疏散行动或根本没有疏散计划的情形下发生的悲 剧。去年( 2 0 0 7 年) ，以色列一家科技公司就发明了一套新型的高楼室外逃生装置， 帮助人们在危险发生时，迅速有效地逃离现场，从而可以避免踩踏的发生。这套 装置的操作十分简单，当火灾、地震警报响起时，这套事先被安装在房间内的逃 生装置就会自动启动，遇难者只需穿上救生衣，扣好安全扣，从窗户或阳台顺着 绳索滑下去，就可以成功逃生了。这套逃生装置的一个显著特点就是利用户外通 道逃生，从而避免了在火灾发生时，慌忙逃离的居民因争抢楼梯而发生堵塞和踩 踏事故，也减小了居民长时间滞留火场吸入浓烟而窒息的危险。 逃生器材对于人员疏散是必不可少的，然而从宏观上建立起一种疏散模型， 进而制定出疏散计划对于整体的疏散任务非常重要。建筑物火灾疏散中人的行为 研究，是一个复杂的涉及多学科的系统课题。对于疏散模型，目前有两方面：一种 是从建筑物本身的自然、物理属性出发，结合疏散人员特征，不考虑或不全面考虑 个体的行为个性特点，对建筑物的疏散空间和疏散路径进行模化，建立预测安全 疏散所需时间的模型，评价疏散系统的可靠性；另一种是从研究人在火灾中的个性 行为入手，研究火灾事故及其疏散中人员的生理和心理状态，个体行为和群体行 为的特殊规律。建筑物火灾疏散中人的行为研究，是一个复杂的涉及多学科的系统 课题。h o r s tw h a n m a e h e r 和s t e v a n u s a t j a n d r a 【7 】指出宏观模型是基于最优化的 方法而不考虑个体之间的差异。如把个体看作是拥有相同性质的集合体，个体间 的不同特征被忽略掉。由于时间在疏散过程中是一个决定性的参数，大多数的宏 观疏散模型都是基于动态网络流模型，这旱的动态网络可以看作是动态路径模型， 人员疏散可以看作是网络流。动态的网络是和静态网络相对应存在的，静态的网 络中路径信息不随着时间而改变。微观的模型则把重点放在个体运动的模拟上， 6 概论 考虑个体的参数( 例如行进速度，反应时间和身体能力) 和疏散行动过程中人与人之 间的相：豆作用。现在，越来越多的人对于胞自动在行人和交通活动中的模拟感兴 趣。吕春杉 8 等提出了一种基于运动模式和元胞自动机的人员疏散模型。该模型 借助智能移动机器人的运动模式，并考虑了火灾环境对人员的疏散行为的影响， 即火灾环境对人员造成的生理心理影响从而导致低效的疏散行为。引入一个健康 度的概念，在疏散过程中，人员的健康度会受到其周围的烟气浓度、温度，氧气、 二氧化碳和一氧化碳浓度的影响而不断下降，从而导致人员的疏散方f 相的错位和 疏散速度的下降。格林威治大学( u n i v e r s i t yo fg r e e n w i c h ) 的e x o d u s 开发团队 f s e g 6 ，开发的商业计算机疏散模型建模软件工具b u i l d i n g e x o d u s7 ，专门用于疏 散模型的模拟。该工具是由c + + 语言丌发，并且包含5 个子模型：人员，运动， 行为，毒性和危险品子模型。一个疏散模型演示图如图1 1 所示。b r a u n 9 等则将 研究重点放在个人在拥挤环境模拟的行为建模，文中用h e l b i n g 模型 1 0 作为模拟， 图1 1b u i l d i n g e x o d u s 模拟演示 f i g u r e1 1d e m oo f b u i l d i n g e x o d u s 并将其一般化来考察个体行为特性和集体行为特性的差别。如果只是将个人的逃 生作为首选，而不考虑其他人的疏散，人往往是受利己主义( i n d i v i d u a l i s m ) 思想的 影响。而将人们自然分组疏散，人们会更多的考虑同组其他人的安全，从而利他 主义( a l t r u i s m ) 成为团队的主导。文中最后将这两种模拟在二维和三维效果可视化 表现出来。 6 f i r es a f e t ye n g i n e e r i n gg r o u p 7 h t t p ：f s e g g r e a c u k e x o d u s i n d e x h t m l 北京交通大学硕士学位论文 1 4 课题的主要研究内容 1 4 1 路径模型的自动生成 本文的路径模型( r o u t eg r a p h ) 是一种楼层信息的拓扑图，也就是全局路径规划 中的自由空间模型。路径模型实质上是由可以通过的路径所组成的图。论文中的 路径图是图论在计算机建模中的数据模型，这样的图由结点和边组成的，为了表 达建筑楼层的动态信息，边上被赋以权值来记录实时的环境变化。我们将建筑楼 层平面图中的房间、楼梯、电梯等抽象为结点，而将楼道，走廊等可以通行的区 域通过边表达出来。我们最终的目标是根据楼层平面图，自动地生成与该楼层相 关的路径拓扑图，这一过程将会用到图像处理中的基于数学形态学的图像细化和 图像特征点提取等算法来生成楼道路径， 中。以此方法可以生成所有层的路径图， 然后将房间、楼梯结点加入到路径图当 这里各层路径图还没有连接，最后通过 连接楼梯电梯等楼层连接点，从而完成各层间的连通图，这样就将一个完整的三 维建筑路径模型建立好了。为建筑信息模型( b i m ) 自动地生成路径模型是系统的首 要工作，也为接下来的路径规划及表达提供了基础。 1 4 2 路径规划 借助于前面的三维路径模型，路径规划才可以实现。路径规划可以分为静态 的路径规划和动态的路径规划。最短路径或者代价最小路径属于静态路径规划的 范畴，生成最短路径的过程，路径图的信息不会随时间发生变化，因此这样的最 短路径往往比较简单，但却不符合实际情况。机器人导航过程中的障碍物位置的 改变和室内环境中其他机器人的行动，都说明静态的最短路径应用的局限性。论 文中生成的最短路径可以看作是动态的，因为路径信息可以根据建筑物的实际环 境情况进行实时的更新。例如在火灾发生的情况下，烟雾浓度，火势大小和温度 高低等因素可以影响路径图中边的权值大小，这些权值代表了通过该路径的代价 大小，这样便可以制定符合实际情况的最优路径。本论文使用启发式的搜索算法 来完成最短路径的计算，这被证明为目前最好的路径计算方法。通过启发式的a 毒 搜索算法，完成最短路径的规划。随后提出了一个用于计算紧急情况下制定人员 疏散计划的数学模型。 1 4 3 路径的表达 概论 在路径规划中搜索到的最优路径，可以作为一种导航信息应用到实际中去。 事实证明图示形式和自然语言是人们常用的两种表达路径信息的方式，并且偏好 于用自然语言的人数和偏好于图示的人数大体相当。我们可以将这条最短路径在 b i m 中三维显示出来，但是这就需要用户拥有一套功能强大的显示设备，显示出 b i m 三维模型和模型中的最优路径，因为路径的显示依赖于b i m 模型。b a r b a r a t v e r s k y 和p a u lu l e e 11 1 从心理学角度阐述和证明了用语言描述和组织空间信息 是合适的，利用语言的特性把空间信息的某些方面作为重点抽象出来而忽略其他 细节的信息是可以有效地组织空间信息的。自然语言描述的信息和三维图形显示 相比，缺乏了形象性，却对于硬件设备的要求很低，目前大多数的设备都能够支 持文本格式的显示。在这一部分我们将把由结点和边构成的路径信息转化成为和 环境信息相关联的，由一系列转弯动作描述的自然语言路径表达。当然其他形式 的路径信息表达，例如车载g p s 上实现的语音导航，也具有很大的实际意义，不 久的将来，本文会将路径导航信息在移动设备上应用，包含文本和语音导航。 1 5 论文的内容组织 论文共分为6 章，首先详细介绍了路径自动建立的过程，然后在该路径模型 基础之上，介绍了的路径规划，紧接着我们更进一步将得到的最佳路径以三维图 形和自然语言两种形式表达出来，文章的最后给出了结论和展望。具体的章节安 排如下： 第一章，简单介绍了课题的背景，意义和相关的研究，概括性地介绍了论文 的研究内容。 第二章，介绍了建筑模型和路径模型。在建筑模型部分主要讨论了i f c 标准 和建筑信息模型；在路径模型部分，则结合建筑模型生成的楼层平面图的结构特 点，比较三种路径模型的优缺点，说明本文采用拓扑图来描述楼层路径信息是非 常有效的。 第三章，详细地介绍了如何通过基于数学形态学的图像细化，及图像交叉点 和拐点的提取算法，最终自动生成路径模型的过程，这是本文的重点。 第四章，在生成路径模型的基础上，首先介绍了路径权值的更新，然后利用 启发示搜索的a 宰算法搜索到最佳路径，最后介绍基于路径模型的人员疏散计划的 生成算法。 第五章，首先介绍了将路径规划中得到的最佳路径，三维地显示到建筑物场 景当中，在显示系统中提供一个可供用户选择起始结点和目标结点的交互界面， 然后探讨将搜索到的最优路径转换为自然语言描述的路径这一过程的相关技术， 9 北京交通大学硕士学位论文 分析自然语言描述的路径特征包括参考系选择，方位信息和冗余信息的分析综合 在盘悬盘 守守0 第六章，最后给出全文的总结和对于将来工作的展望。 1 0 建筑物模型和路径模型 2 1 建筑物模型 2 建筑物模型和路径模型 随着计算机和数字技术的发展，建筑的设计过程发生了巨大的变化，出最先 的手绘图纸发展到计算机辅助设计( c a d ) ，从传统的二维设计发展到三维、多维设 计，到现在涵盖产品生命周期全部信息的信息模型的转变。最初建筑物的模型就 是真正的实体建筑物的缩微版，论文这里提到的建筑物是由建筑物辅助设计软件 而生成的。这一生成模型的过程是用计算机技术和图形学方法将建筑物中实体的 形状，位置，大小，姿态三维生成和可视化的过程。一张由计算机辅助设计软件 生成的平面布局图如图2 1 所示。目前常见的c a d 三维建筑建模的工具及其格式 幽2 1c a d 平面布局幽 f i g u r e2 1c a d f l o o rp l a n 如下： 1 )a u t o c a d d w g ，d w f 格式； 2 ) 3 d sm a x m a x 格式； 3 ) 3 ds t u d i o 3 d s 格式； 4 ) s k e t c h u p s k p 格式； 5 ) g o o g l ee a r t h k m l 、k m z 格式； 6 ) p k p m t 格式。 山于存在如此之多的文件格式，对于生成的三维建筑模型，用，、往往会