（通信与信息系统专业论文）虚拟逃生系统中路径规划技术的研究与应用.pdf

武汉理工大学硕士学位论文 摘要 随着社会的不断进步 我国城市化建设的不断推进 各种大型公共设施随 处可见 对于这些高密度人群聚集的场所 由于其在紧急情况下人群疏散工作 存在很大的不安全性和不确定性 一旦疏散工作安排不合理 就会造成不可预 计的生命和财产损失 因此做好人员的安全疏散工作显得尤为重要 近年来 人群疏散工作已经成为安全领域的一个研究重点 然而 在紧急情况下 逃生 人群的行为是一个相当复杂的现象 它不但被外界环境所影响 而且与人的心 情 身体素质等也有很大的关系 因此仅仅用一组数学公式来描述疏散过程是 不够严谨的 也是不太现实的 但是 组织大量人员进行现实的疏散演练 又 费力耗时 难以实现 所以 目前对于人群疏散的研究工作主要是基于虚拟场 景下的计算机仿真 虚拟逃生系统的仿真中 最为重要的部分是逃生系统的路径规划部分 这 也是本文的主要研究内容 本文通过对已有算法的研究 尤其是现有经典算法 a 算法的研究之后 提出了三种路径规划改进措施 来提高算法的运行效率 在标准a 算法的基础上 采用二叉堆的方法来对a 算法开启列表进行快速排 序 从而提升算法在开启列表中查找和删除节点的效率 将单个物体的寻径过 程和a 算法相结合 加快虚拟环境下的路径搜索速度 在路径规划中运用分层 寻路的思想 先根据虚拟环境的信息进行全局规划 把整个虚拟环境划分为几 个小区域 然后在各个小区域内进行局部搜索以完成局部路径规划 来减少路 径搜索过程中系统搜索的节点数 加快路径搜索速度 本文通过仿真实验验证了算法的优化特性 实验结果表明 改进后的算法 相比改进前搜索效率提高1 4 7 最后本文将改进后的算法成功的应用于实例中 在v s 环境下 结合m f c m i c r o s o f tf o u n d a t i o nc l a s s e s 框架结构和o g r e o b j e c t o r i e n t e dg r a p h i c s r e n d e r i n ge n g i n e 3 d 渲染引擎开发出一套虚拟现实的疏散仿真系统 由疏散结 果可知 本文建立的路径规划算法针对虚拟场景下的紧急疏散达到了很好的模 拟效果 关键字 虚拟场景 路径规划 a 算法 导航图 武汉理工大学硕士学位论文 a b s t r a c t w i t ht h es o c i a lp r o g r e s sa n dc o n t i n u o u sa d v a n c eo fc h i n a su r b a n i z a t i o n m a n y k i n d so fl a r g ep u b l i cf a c i l i t i e sc o n t i n u et oe m e r g e f o rt h ep l a c eo fh i 曲 d e n s i t y c r o w d i nc a s eo fe m e r g e n c y t h e r ea r ei n s e c u r i t y a n du n c e r t a i n t yd u et ot h e e v a c u a t i o nw o r k o n c et h ee v a c u a t i o na r r a n g e m e n t si su n r e a s o n a b l e w i l lr e s u l ti n l o s so fl i f ea n dp r o p e r t yw h i c hc a n tb ea n t i c i p a t e d t h e r e f o r e t h ee v a c u a t i o no ft h e p u b l i cp l a c e si n d e p t hs t u d y h a sv e r yi m p o r t a n ts i g n i f i c a n c e i nr e c e n ty e a r s e v a c u a t i o nh a sb e c o m ear e s e a r c hp r i o r i t yo ft h es e c u r i t yf i e l d t h ee v a c u a t i o no f c r o w db e h a v i o ri sav e r yc o m p l e xp h e n o m e n o n a n di tn o to n l yb ei n f l u e n c e db yt h e e x t e r n a le n v i r o n m e n t b u ta l s oh a v eag r e a tr e l a t i o n s h i pw i t ht h ep e r s o n sm o o d p h y s i c a l j u s tu s eas e to fm a t h e m a t i c a lf o r m u l a st od e s c r i b et h ee v a c u a t i o np r o c e s s i s n o tr i g o r o u se n o u g h h o w e v e r o r g a n i z a t i o n sl a r g en u m b e r so fp e o p l et ot a k ep a r ti n r e a l i t yo fe v a c u a t i o nd r i l l c o n s u m i n gt i m e c o n s u m i n g a n dd i f f i c u l tt oa c h i e v e t h u s t h ep r e s e n tr e s e a r c hw o r df o rt h ee v a c u a t i o ni st h ec o m p u t e rs i m u l a t i o nb a s e do nt h e v i r t u a ls c e n e i i lt l l ev i r t u a ls i m u l a t i o no ft h ee s c a p es y s t e m t h em o s ti m p o r t a n tp a r ti st h ep a t h p l a n n i n go ft h ee s c a p es y s t e m t h i si sa l s ot h em a i nc o n t e n t so ft h i sa r t i c l e i nt h i s p a p e r w es t u d yt h ee x i s t i n ga l g o r i t h m s e s p e c i a l l y s t u d yt h ee x i s t i n ga a l g o r i t h m w ea d v a n c et h r e ei m p r o v e dm e a s u r e st oi m p r o v et h eo p e r a t i n ge f f i c i e n c yo ft h e a l g o r i t h m o nt h eb a s i so ft h es t a n d a r da a l g o r i t h m u s i n gab i n a r yh e a pm e t h o dt o o p e nt h el i s to fa a l g o r i t h ma n dm a k e aq u i c ks o r t s oa st oe n h a n c et h ea l g o r i t h mt o f i n da n dd e l e t et h ee f f i c i e n c yo ft h en o d e si nt l l el i s to fo p e n c o m b i n et h er o u t i n go f as i n g l eo b j e c tw h i tt h ea a l g o r i t h m a c c e l e r a t et h es p e e do ft h ep a t hs e a r c hi na v i r t u a le n v i r o n m e n t t h i sa r t i c l eu s eo fh i e r a r c h i c a lp a t h f i n d i n gt h i n k i n gi nt h ep a t h p l a n n i n g a c c o r d i n gt h ei n f o r m a t i o no fv i r t u a le n v i r o n m e n tt oc o m p l e t et h eg l o b a l p l a n n i n g a n dt h e n d i v i d e dt h ev i r t u a le n v i r o n m e n ti n t o s e v e r a ls m a l l e ra r e a s t o c o m p l e t et h el o c a lp a t hp l a n n i n gi nt h el o c a ls e a r c ho fe a c hs m a l la r e a r e d u c et h e n u m b e ro fn o d e si nt h es e a r c ho fp a t h t oa c c e l e r a t et h es p e e do ft h ep a t hs e a r c h i nt h i sp a p e r t h es i m u l a t i o nr e s u l t sh a v ev e r i f i e dt h ee f f i c i e n c yo ft h i sa l g o r i t h m 武汉理工大学硕士学位论文 a n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h es e a r c he f f i c i e n c yo ft h ei m p r o v e d a l g o r i t h mh a si m p r o v e d14 7 f i n a l l y t h ei m p r o v e da l g o r i t h ms u c c e s s f u l l ya p p l i e dt ot h ei n s t a n c ei nt h ev s e n v i r o n m e n t c o m b i n e dw i t ht h es t r u c t u r e o ft h em f c m i c r o s o f tf o u n d a t i o n c l a s s e s f r a m e w o r ka n do g r e o b j e c t o r i e n t e dg r a p h i c sr e n d e r i n ge n g i n e 3 d r e n d e rh o s p i t a l i t yt od e v e l o pt h ee v a c u a t i o no fav i r t u a lr e a l i t ys i m u l a t i o ns y s t e m t h ee v a c u a t i o no ft h er e s u l t ss h o w st h a tt h ee s t a b l i s h e dp a t hp l a n n i n ga l g o r i t h mf o r t h ee m e r g e n c ye v a c u a t i o no ft h ev i r t u a ls c e n et oa c h i e v eag o o ds i m u l a t i o nr e s u l t s k e y w o r d s v i r t u a lr e a l i t y p a t hp l a n n i n g t h ea a l g o r i t h m n a v i g a t i o nm a p 武汉理工大学硕士学位论文 1 1 研究目的和意义 第1 章绪论 公共安全的完善是稳定社会和保障国家安全的基础 中国每年由公共安全 所造成的国内生产总值损失高达6 人口损失超过二十万i 公共安全危机有 很多种 例如毒气泄漏 核污染 地震 火灾 海啸 传染疾病等突发事件 全球范围内公共安全事故在近几年频频出现 各地爆发的海啸 禽流感 地震 台风等都给人民的生命和财产带来了巨大的损失 2 同时也对世界各国的公共安 全管理部门敲响了警钟 对于信息中心 通信基站等信息通信系统是一种严格 的考验 但对诸如交通 医疗 卫生的信息化资源调度体系同样也是一个巨大 的挑战 随着经济的持续发展 社会的稳定进步 我国城市化建设不断加快 大型 建筑物日益增多 作为商业文化中心的一线城市承担着日益增多的体育 娱乐 政治 商业 宗教等活动 所面临的安全问题也随之变得更加严重1 3 在诸如商 场 剧院 体育馆等大型公共设施内 发生煤气泄漏 爆炸 恐怖袭击等涉及 公共安全的紧急情况下 会引发人群恐慌 从而导致拥挤踩踏等事件 快速而 安全的将场馆内的人员成功的疏散到安全区域就显得尤为重要 虽然在建筑法中对保障出口安全的条例中有明确的规定 但是在实际情况 下很难对建筑的疏散合理性做出评估 突发的紧急情况下 生活中已经有很多 关于因为人群没能得到合理的疏散而引发的大量伤亡的报道 除了造成严重的 生命和财产损失外 大量幸存者及其家属在心理方面更会留下永久的阴影 由 于突发的公共危机导致的紧急疏散情况下所造成的人员伤亡实例随处可见 其 中最近十年以来的真实事件举例如下 1 2 0 0 1 0 5 0 9 加纳首都阿克拉 足球场内球迷骚乱 导致1 2 6 人死亡 2 2 0 0 2 0 6 1 6 北京市海淀区某网吧发生特大火灾 2 5 人死亡 3 2 0 0 2 1 2 0 5 委内瑞拉其大都市 歌舞厅内发生特大火灾 因为出口 设计不合理 导致4 7 人死亡 8 人受重伤 4 2 0 0 3 1 2 1 3 重庆开县 川东北气矿场发生特大井喷事故 因为对周 武汉理工大学硕士学位论文 边区域居民疏散不及时 导致2 3 4 人死亡 5 2 0 0 4 0 8 o l 巴拉圭首都亚松 超市引发大火 造成约3 6 0 人死亡 5 0 0 人受伤 4 1 以上种种案例告诉我们 在突发紧急事故下 如何处理这些突发性事故 保障人民生命财产安全 如何有效的应急与救助来降低人员伤亡和财产损失 已经成为世界各地需要研究解决的一个重大课题 对紧急状况下的大规模人群疏散过程做出合理规划 除了需要详细分析以 往发生过的重大安全事故中的人群疏散过程外 还需要系统的研究城市应急管 理知识和方法 来得到这个复杂过程中正确的疏散规划策略 紧急情况下的人群疏散工作不同于其他的救援工作 其主要因素体现为以 下几点 1 诱因不定 公共安全事故频发的原因是多种多样的 但是他们的起因往往是由于人们 对于事故前表现出的细微征兆的忽略 最后演变成巨大的安全灾难 然而紧急 状况下人群本身所造成的混乱和恐慌才是导致踩踏事件的原因 2 场所不定 公共安全事故可能发生在楼道或者楼梯 地铁 火车站 建筑物出口等任 何地点 在露天型开放类场所也可能出现危机 这类开放场所周围大多会有树 栏杆等各种设施 危急情况下 人群密度过大 此类障碍物就会阻碍人群的疏 散 导致拥挤 3 时间不定 公共安全事故的重要特征是 毫无警示的情况下 突发的 而且短时间内就 能造成不可估计的人员伤亡和经济损失 所以时间无疑是这类事故中首先要争 取的重要资源 4 连锁反应 因为安全事故导致的各种连锁反应在生活中也是时常出现的 例如火灾导 致的爆炸 拥挤导致的踩踏事故 交通事故引发的交通堵塞等1 5 大量研究显示 拥挤情况下会产生造成某种严重后果的难以抗拒的力量 紧急情况下 高密度的拥挤人群所产生的力量足够推倒墙壁甚至折断钢筋 通 过对紧急情况下人群的运动规律和人群逃生动态等方面的研究 可以有效的预 防由于这类公共安全事故造成的潜在威胁 进而避免灾难的发生 6 1 由于这方面 武汉理工大学硕士学位论文 的研究有很大的研究前景和应用价值 近几十年来学术界对人群疏散问题的研 究越来越关注 很多国家的政府部门和安全机构都对这一应用展开了一系列的 研究并且开发出相应的系统 通过对大量聚集人群的运动规律和疏散特征的了 解 能够使得建筑物内部结构得到优化 从而达到人群疏散速度的提升 进而 大幅减少人员伤亡和财产损失 此外 这方面的研究能够指导人们在组织大规 模人群集会时 设计出相对安全的管理措施 从而保障大型公共活动的顺利开 展 刀 大规模的实际人群疏散演练是研究人群疏散过程最直观的方法 但是这种 疏散演习不但无法模拟出灾难情况下的疏散情况 而且组织难度也相当大 耗 资耗时 而且本身也存在着安全隐患 因此不宜采用这种方法 结合社会学 心理学等相关领域的知识 进行人群疏散的计算机仿真技术研究是当前最为流 行的方法 也是较为合适的研究方法 8 l 通过对该课题的研究 将为大型公共设施安全问题的解决提供全新的技术 理论 工具和方法 研究成果可以广泛应用于大型公共设施安全危机处置预案 的设计 评估和优化 大型公共安全危机事件的可视化交互分析 重要公众建 筑设计方案的公共安全风险评估 分析与改进 公共设施安全危机事件决策的指 挥人员培训 1 2 国内外研究现状 现在 人们的日常生活中充斥着各种虚拟现实技术 这种现实需求对虚拟 现实技术相关方面的研究起着很大的推动作用 这也使得虚拟现实技术在近年 的发展中 逐步成为计算机仿真领域又一重点研究课题 通过技术的不断发展 创新 许多优秀的团队研究出大量的理论成果 应用于各个领域的仿真平台也 不断出现 1 2 1 虚拟逃生系统研究现状 对于人群应急疏散仿真的研究现状 世界范围内举办过多次有影响力的学 术型国际会议 也相应的在理论方面出版了很多会议论文 在这些国际会议中 拥挤安全工程国际会议 i n t e r n a t i o n a lc o n f e r e n c eo ne n g i n e e r i n gf o rc r o w d s a f e t y 于伦敦1 9 9 3 年举办 该会议在世界范围内产生了很大影响 9 1 其次 武汉理工大学硕士学位论文 2 0 0 1 年在德国杜伊斯堡举行的第一届 行人及疏散动态学大会 c o n f e r e n c eo n p e d e s t r i a na n de v a c u a t i o nd y n a m i c s p e d 重新把密集人群安全疏散问题推到社 会的焦点 另外 2 0 0 3 年8 月 第二届p e d 大会在伦敦成功召开 会议表明对 人群疏散动态的研究将正式作为一门独立的学科出现 l o l 人群疏散仿真系统模型可以划分为两类 微观模型和宏观模型 早期仿真 模型技术发展还不够成熟 宏观模型被广泛使用 但是微观模型在许多方面都 具备明显优势 因此近些年来对微观模型的研究成为逃生仿真系统的重要研究 方向 其中 微观模型又可以分为连续型模型和离散型模型 由于智能体被大 量引入虚拟逃生系统仿真中 所以目前人群疏散仿真模型的研究主要集中于离 散型模型 在国外 相关方面学者的主要研究方向是人员的行为模型和安全疏散模型 据有关文献统计 随着计算机的不断发展 在2 0 世纪8 0 年代以来 国外学者 开发出了很多用来描述建筑物应急人群疏散特性的模型 其中正在研究开发的 模型和完成开发工作的模型就有2 2 种 1 1 1 总体上 这些模型都可以归纳为 网 络节点模型 即建筑物的各部分的空间布局用网络来表示 近年来 国外许多优秀的研究机构开发出各种人群疏散仿真系统 这些仿 真模型被许多事故安全工程师用来分析建筑的安全系数 对建筑的紧急疏散工 作做出高水平的疏散评估 并且取得了较好的指导效梨1 2 l 下面列举了国外一些优秀的紧急疏散仿真系统 1 美国 f r a n c i s 开发的预测最小理论疏散时间的网络模型e v a c n e t 由s t a h l 开 发的火灾行为模型b f i r e s 一1 1 由a l v o r d 开发的疏散与救援模型 还有 e g r e s s e s c a p e b g r a f c s p d o n e g a n s e n t r o p y m o d e l e x i t t s l m u l e x n o r i t a k a l l a s h i 5 m o d e l v e g a s m m a g n e t m o d e l e v a c s i m d r a g e r e t a l 19 9 2 e x i t 8 9 f a h y 19 9 3 等网络模型及e x o d u s a s e r i v o l k e r s c h n e i d e r a e a e g r e s s s g e m 等能够描述建筑物内人的运动的 虚拟现实模型i l 川 2 英国 在对环境阻塞情况下人员心理状态进行研究的基础上 s e r t 中心的s i m e 等部分人提出了o r s e t 模型的概念 该系统能够把建筑学 心理学 管理学以 及火灾报警和疏散规划放在一起 进行统一研究分析来生成最优的指导人群疏 4 武汉理工大学硕士学位论文 散的仿真系统 于此同时 英国研究人员研发出较多能够真实反映紧急情况下 人群疏散的仿真系统 来模拟人群逃生路线 帮助指导安全疏散路径的规划 如b u i l d i n ge x o d u s s i m u l e x e g r e s s 等 3 日本 日本学者较注重把火灾人员行为统计 人员疏散安全评估方法 火灾危险 性评估和性能化设计结合起来进行研究 提出了t o g a w a 经验公式计算疏散时间 并开发出粗糙网络模型 水力模型1 1 4 4 匈牙利 交通专家h e l b i n g 把人员的行为反应量化为作用力 即社会力 添加到人员 疏散模型中 取得了重大进展 成功地再现了群体效应等经典的人员疏散行为 1 5 1 o 与发达国家相比 我国的存在很多条件方面的不足 在虚拟人群疏散仿真 方面的的研究还不能达到欧美等国家的水平 但是我国也有大量优秀的研究人 员从事着安全疏散方面的工作 并且在人群疏散系统方面也都取得了不错的成 绩 东北大学方正等人对人群疏散做了大量的研究 并且建立了人群疏散的 网 格模型 武汉大学在与香港城市大学合作的过程中 创建了一个过程模拟模型 s g m e 1 6 1 2 2 路径规划算法的研究现状 路径规划技术在人工智能领域是一个经典问题 它被应用于各种现实生活 环境中 比如车辆导航 医学手术 机器人移动 航空航天 货物装配分析等 不仅如此 在虚拟环境中的仿真培训 游戏寻路方案设计 虚拟战场 导航漫 游等各种领域都有应用 路径规划问题在a i 中的应用问题是指在障碍物环境下 找到一条从给定起始点到目标终止点的合理路线 该路线应该能满足车辆 装 配物 医疗设备 机器人等的无碰撞情况下安全到达目的地或者完成所有操作 此类为题被归纳为获得一条点到点的无碰撞合理路径 虚拟现实的仿真过程往 往需要路径规划的合理运用 随着社会对虚拟现实技术的需求以及计算机仿真 技术的不断发展 路径规划课题的研究已经成为虚拟现实技术的一个重要研究 方向 计算几何学传统研究课题是路径规划技术的起源 智能机器人的飞速发展 使得路径规划技术在七十年代中期成为移动机器人的又一重要研究方向 随机 武汉理工大学硕士学位论文 路径规划 r a n d o m i z e d p a t hp l a n n e r r p p 是一种相当重要的实际应用方法 该方 法在1 9 9 1 年由j b a r r a q u a n d j c l a t o m b e 提出 1 7 1 路径最短算法包括很多种 其中比较典型的有 启发式搜索算法 神经网络方法 图论基本法 动态规划 法等 这些最短路径法都是路径规划的核心算法 传统的最短路径算法有矩阵 算法 迪杰斯特拉 d i j k s t r a 算法 f l o y d 算法等 路径规划问题被描述为在已知初始位置 目标位置和特定的环境信息中 寻找一条从起始点到目标点的距离最短或者代价最小路径 路径规划案范围划 分可分为局部规划和全局规划 全局规划 在环境信息已知的情况下 搜索出 一条从起始节点到目标节点的最优路径 又叫做离线或者静态路径规划 部分 未知或者全部未知的环境信息下 在全局路径规划的基础上 对路径段更为精 细的规划叫做局部路径规划 又叫在线或者动态路径规划 在国内 游戏领域与机器人领域的开发中运用路径规划研究的方法是最多 的 许多院校和相关的实验室 浙江大学c a d c g 国家重点实验室 清华大学 计算机科学和技术系 北京航空航天大学 哈尔滨工业大学等 也对路径规划 技术在不同环境中的应用进行了相关研究并得出了许多有益的结论 l 引 例如 把蚁群算法运用于路径规划中 基于人工势能的路径规划 a 算法的优化改进 等 但是随着路径规划技术研究的不断深入发展 搜索效率方面的问题也不断 显现 在路径规划技术不断的发展中 科研人员的研究重点也逐渐转向算法复 杂程度的降低和与高新技术的结合方面 开拓更加广阔的发展空间 大部分关于路径规划问题的研究都主要集中在机器人领域 随着近几年虚 拟场景应用范围越来越广 计算机的软硬件设施不断发展 路径规划在虚拟场 景中的应用也逐渐成为热门的研究对象 尤其是在仿真培训和游戏中 路径规 划体现出了更高的利用率 它既要和人一样具有智能性 又要具备真实的行走 能力 所规划的最优目标也不仅仅是最短的距离 而是需要有更多的其他因素 其中有一项很重要的内容就是平衡路径保证最小代价与提高搜索的效率来确保 它的实时性 这样才能保证即使不能获得最优路径 但是考虑到其他的多方面 的因素 得出的最终路径可以达到既直观合理并且不对3 d 虚拟空间显示造成影 响 完成定位 路径搜索 避障等一系列问题 是一个要求从全局到局部运用 相应策略来解决的过程 需要综合运用人工智能 计算机图形理论 虚拟现实 模型构建等多学科知识内容 合理真是的表达出环境特征 并结合地形结构存 6 武汉理工大学硕士学位论文 储模式智能的进行搜索的过程 所以虚拟场景中的路径规划技术是一个颇具挑 战的课题 当前国内对于路径规划技术的发展还处于一个初期的阶段 有很多 不足之处 路径规划在很多情况下主要是考虑两点间路径的连通性 很少考虑 实际底面的构造情况 例如底面的粗糙度 坡度 植物的覆盖度等因素 在野 外的路径规划中 这些问题是影响智能体移动的关键因素 在具体的路径搜索 算法中 如何减少算法搜索的节点数 提高算法的收缩效率上也存在很大的改 进空间 因此在虚拟现实场景中的路径规划问题上还存在着很大的挖掘空间 1 9 j 2 0 1 3 研究内容及组织结构 1 3 1 研究内容 本文的工作主要包括以下内容 1 对虚拟场景下大规模人群疏散的研究现状进行了研究 主要分析了虚拟 逃生系统中路径规划的现有算法 并指出了当前路径规划算法的不足 2 提出了一种基于a 算法的改进算法 该算法通过改进a 算法的o p e n 列表的查找速度 并将a 算法和单个物体的寻径过程相结合 很大程度上提高 了路径搜索的效率 3 对改进后的算法进行仿真 与改进前的算法进行实验数据对比 通过实 验数据来判定算法的优化性能 将改进后的算法运用于实际中 实现虚拟环境下人群疏散的仿真系统 1 3 2 论文组织结构 本文结构安排如下 第一章 绪论部分 主要对虚拟逃生系统及其路径规划算法的国内外研究 现状进行了详细介绍 另外简单阐述了本课题研究的目的和意义 最后对本文 的研究内容和组织结构做了讲解 第二章 对现有的路径规划算法做了深入研究 分析了各种路径规划算法 的优缺点 并提出了一种适合虚拟场景的路径规划算法 第三章 本文的核心部分 详细介绍了一种基于a 算法的改进算法 对改 进后的算法性能做了深入分析 武汉理工大学硕士学位论文 第四章 将改进后的算法进行仿真实验分析 通过与标准a 算法的实验结 果对比 分析改进算法在路径规划的搜索效率方面的性能提升 并将算法运用 到实际 搭建虚拟场景下大规模人群的逃生系统 第五章 对本文的研究工作进行了总结 同时对课题未来的研究方向进行 了展望 武汉理工大学硕士学位论文 第2 章常用路径规划算法分析 随着对机器人的深入研究 对路径规划问题的认识也越来越深刻 现在比 较经典的移动机器人路径规划问题是 按照一定的评价准则 在一个有障碍物 的环境内 如何找到一条从起始状态到目标状态的无碰撞路径 路径是一系列 空间点的轨迹 是在固定的空间中由机器人所经过留下的轨迹 比如 耗费时 间最短 路径最短 安全性能最好 消耗能量最少等都是比较常用的评价标准 一般情况下机器人的相关路径规划实验都是通过计算机仿真出来 即机器人路 径规划思想在一定程度上被虚拟场景中的路径规划技术借鉴了 2 1 路径规划技术研究 路径规划问题的研究一般包括路径执行 规划方法和环境表示 其中路径 执行与底层控制机构相关 控制机器人或虚拟人按照设定的路径行走 其中路 径执行与底层控制机构有一定的联系 操控机器人或虚拟人按照设定好的路径 前进 规划方法研究在环境表达的基础上 采用哪种有效的方法来规划和优化 路径 最后环境表示具体涵盖怎么样将环境信息有效地表达出来以及怎么样有 效地获取环境信息 以下两类工作领域与路径规划相关 第一类是虚拟世界领域 r e y n o l d s 1 于1 9 8 7 年第一次成功地模拟了鸟群的飞行过程 并开始对虚拟现实系统的路径 规划进行系统的研究 第二类是机器人领域 根据机器人的行为规范进行相应 的路径规划2 l j 在机器范畴这个问题是一个十分重要的研究课题 并且已经很好 地研究设计和实现了许多非常实用的算法 其中在机器人导航模块中至关重要 的任务之一就是路径规划技术 控制机器人使得其按照事先给定的路径移动至 目的地 这就是机器人导航的定义 通过传感器获得地图信息并予以记录 根 据此事先掌握的地图信息实时的调整机器人的位置 做出相应的正确决策 完 成机器人的自动导航 路径跟踪的过程 最终完成路径的规划 安全到达目的 地 可以根据路径规划方法的发展过程和其所体现的智能程度将路径规划方法 分为两大类 智能型路径规划方法和传统型路径规划方法 其中智能型路径规划 9 武汉理工大学硕士学位论文 方法有 神经网络 模糊逻辑 遗传算法等 这几种方法都可以加快规划速度 并且提高智能体路径规划的精确度 传统型路径规划的方法如下 人工势能法 图搜索法 动态规划法 自由空间法等等 传统型路径规划的这些方法在机器 人的路径规划方面应用非常多 根据虚拟个体对环境的探知程度可以将路径规划算法分为两个类型 第一 种是已知环境具体信息的全局路径规划 第二种是未知环境信息的局部路径规 划 未知地图具体情况时 可以利用传感器对虚拟人周边的地形 建筑等环境 信息进行探测来获取具体的障碍物位置信息 全局路径规划是知道智能体环境信息的情况下完成的算法 它无法根据临 时反馈得到的障碍物信息作出具体的动作 局部路径规划可以通过传感器返回 的智能体周围的障碍物信息作出具体反映 安全的绕过障碍物 因此局部路径 规划相对全局路径规划而言更能够高效 准确的进行路径规划 综合上述归纳 可以将两种算法综合利用 先对虚拟场景进行全局规划 然后利用局部路径规 划具体到每一个小模块进行具体的高效寻径 2 2 经典算法对比分析 由于不少方法在机器人研究领域得到广泛应用 因此叙述时将侧重机器人 但这些方法同样适用于虚拟环境 除了局部路径规划和全局路径规划外 路径规划的花费方式还有多种 例 如环境适应性 是否具有智能性 环境表示等 一种方法可能会属于几种划分 方式 甚至与其他方法相结合来使用 对机器人的研究是使用路径规划方法最 多的领域 但是所有方法一样适用于虚拟对虚拟场景的研究 栅格法 拓扑法 可视图法和自由空间法被称作环境建模法 这四种路径规划法经常会与其他路 径搜索算法使用 模糊逻辑 遗传算法 启发式搜索算法 人工蚁群法 神经 网络方法 这五种方法称为智能规划法 具有一定的智能性 2 2 1 由于虚拟场景 中的路径规划需要在计算机中生成并显示图像 所以对算法的各方面性能要求 更高 由于启发式搜索算法收缩效率高 实时性强 所以更加适合于虚拟场景 下的路径规划 d i j k s t r a 算法和a 算法分别是最短路径搜索和最具前景的启发式搜索算法 他们不仅在网络路由算法 游戏设计 交通路径导航等领域应用非常广泛 而 且在人工智能 虚拟场景的路径规划方面都有十分广泛的应用 下面将对这两 武汉理工大学硕士学位论文 种经典算法进行详细的分析和比较 2 2 1d i j k s t r a 算法分析 荷兰计算机科学家狄克斯特拉 d i j k s t r a 于1 9 5 9 年提出了一种基于有向图走 索最短路径的典型算法 该算法可以计算图中一个节点到其它所有节点的最短 路径 i 1 1 d i j k s t r a 算法 该经典算法的搜索过程是以初始点为中心开始 逐层向 外扩展搜索 当到达目标点时算法结束 矧 d i j k s t r a 算法在牺牲了搜索效率的基 础上获得了最短路径的最优解 由于算法搜索过程是一层一层向外铺开的 所 有搜索的节点非常多 这是算法效率偏低的主要原因 d i j k s t r a 算法是最具代表性的求解最短路径的算法之一 它的路径求解基本 思想如下 首先用一个集合表示带权有向图的所有点和边 g v e 有向 图中所有点的集合用v 表示 所有边的集合用e 表示 v 中所有节点的集合可以 分为两类 一类是已经求出最短路径的节点集合 称之为集合s 另一类是还没 有求出最短路径的节点的集合u 算法刚开始时集合s 中只有初始节点v 在算法 进行的过程中 集合u 中的节点一次按照到初始节点v 最短路径长度的递增次序 加入到集合s 中去 在这一集合u 中节点转移到集合s 的过程中 总是要求从初始 节点v n 集合u 中任意一个节点的最短路径距离大于或者等于到集合s 中所有节 点的最短路径距离 s 和u 中所有节点都对应一个到起始点的最短距离 s 中的节 点距离即为从起始点v n 该节点的最短路径长度 u 中节点的距离即为v n 该节点 最短路径长度 刚路径所包括的节点只能是属于s 中的节点 d i j k s t r a 算法的基本描述如下 1 初始情况下 集合u 中包含出其实节点v 以外的所有节点 而集合s 中只有源点v 其中v 的距离为0 图中节点距离值的计算规定如下 如果图中 存在弧 则顶点v j 的距离值即为此弧的权值 否则定义为无穷大 例 如源点v 与节点u 存在一条边 该边的权值就是u 中定点u 的距离 如果v 到t l 的边不存在 那么集合u 中节点u 的距离为无穷大 2 将集合u 中距离起始点v 距离最小的点k 插入到集合s 中 选定距离 被认为是顶点k 到起始节点v 的最短路径长度 3 在顶点k 作为新的中间点的基础上 对集合u 中所有节点的距离加以 修正 如果集合u 中的点u 经过新的中间点k 到达源点v 的距离比修改前未经 过顶点k 的距离要短 就对顶点u 的距离值进行修改 点u 修改后的距离值应 武汉理工大学硕士学位论文 该是顶点k 的距离值加边的权值得到 修改完后 将u 中距离最小的点加入到 集合s 中 4 重复 2 3 步骤 直到目标节点被插入集合s 2 4 1 m 2 1 可以更清晰的描述s i j k s t r a 算法 图中节点5 为初始节点 节点3 为目标 节点 图2 1d i j k s t m 算法示例图 最短路径树1 3 9 的形成过程 1 先将顶点5 插入最短路径树 然后将由顶点5 发起的边 设置为搜索边界 2 检测算法边界边所指向的节点 这里是节点2 和节点6 同时把比较 后得到的距离起始节点5 更短的节点加入最短路径树 然后把边 也加入 收缩边界 3 再次检测搜索边界的边所指向顶点 起始节点5 到达顶点3 的带价值 是5 但是到达顶点6 的代价是3 所以节点6 发起的边 4 被加入搜索边界 并且将节点6 插入最短路径树 4 重复以上过程 从节点5 出发经过节点6 n 达节点4 的路径代价是5 所 以把节点4 插入最短路径树 同时将边 作为搜索边界 路径5 2 3 和路径 5 6 4 3 分别为两条不同的到达目标节点的路线 通过比较得知 路径5 2 3 较短 所以后续的路径搜索过程中将不再考虑5 643 最后成功获取最短路径 从上面的描述可以得出这样的结论 d i j k s t r a 算法的实现是一个不断比较的 循环过程 如果不使用热河方法或者技术 所有未经标记的点会以一个无序的 状态被存储在数组或链表中 毫无疑问 在这种无需存储的状态下 每次要获 得权值最小的边时 都要对所有节点一一遍历 算法的执行效率也因此变得很 低 当地图数据量很大时 把未经标记的节点按照其对应边的权值予以顺序排 列是一种很有效的做法 采取这种做法的有优点是每次循环都可以获得想要的 武汉理工大学硕士学位论文 点 从而大幅度的提高了算法的搜索效率 2 2 2a 寻径算法分析 a 算法和d i j k s t r a 算法都能用于计算最短路径 其中a 算法是启发式搜索算 法的一种 即在虚拟环境中进行搜索时 以代价评估函数为基准来搜索每一个 位置 最终得到一条最优路径 2 5 1 一般使用a 幸算法进行路径搜索能够获得路径 的较优解 但是不是最优解 因为a 算法在搜索路径时效率很高 而且尤为适 合于点到点的最优路径搜索 所以在人工智能 虚拟现实以及实时系统等领域 的应用是相当普遍的 a 算法通过估价函数来计算从当前位置到目标位置的代价距离 并根据最 小代价来决定后续的搜索方向 如果当前代价评估失败 则返回上一步对新的 节点进行评估 a 算法的估价函数如公式2 1 所示 坟n h n g n 2 1 式中 f n 表示从初始节点到当前节点n 的代价花费 h n 表示从当前节点n 到达目标节点的代价估计 g n 和h n 之和即为估价函数h n h n 代表了从起始 节点经过当前节点1 1 通往目标节点的代价值 其中 g n 为已知 所以h n 是启发 信息的主要来源 算法对路径的评估结果直接受到h n 函数选择好坏的影响 在a 算法的思想过程中 有两个数据表很重要 1 o p e n 表 用来存放待检验节点的列表 这些节点可能是路径要覆盖的 也可能不是 2 c l o s e d 表 该表用来存放已经访问过的节点 这些节点在后续过程中 是无需再考虑的 具体算法步骤如下 第一步 将起始节点插入o p e n 表中 第二步 如果o p e n 表不是空表 并且当前节点不是目标节点 则 1 将当前节点n 插入o p e n 歹t j 表 在第一步中初始节点即为当前节点 2 将当前节点n 相邻的所有有效 被障碍物覆盖等无法通过或者已经在 c l o s e d 表的节点为无效节点 节点插入o p e n 表 3 通过估价函数f n 计算o p e n 表中当前节点n 所有子节点的f 值 4 把节点n 从o p e n 表中删除 插入c l o s e d 表 并将节点n 所有相邻 子节点中f 值最小的节点设置为当前节点 5 重复以上操作 武汉理工大学硕士学位论文 第三步 当前节点即为目标节点时 依次向上寻找当前节点的父近点 即 可输出最终路径 2 6 1 2 7 通过以上分析可知 虚拟环境中一条路径的是不是最优和高效主要取决于 估价函数的选择 一个高效的启发式估计函数在理论上可以快速高效的获得最 优路径 但是由于路径的搜索是收到多方面因素影响的 尤其在环境复杂的大 规模人群中 想要得到一个完全正确的最优估计函数是很困难的 只能通过当 前的虚拟环境对比的选择更为合适的估价函数 当然算法可以通过搜索更多的 节点来获得更为合适的路径 但是这样就必须牺牲算法搜索速度这一重要指标 使用a 幸算法进行路径搜索过程中 如何产生当前节点对应的相邻节点来作 为下一步代价评估的节点是一个很重要的问题 通常为了节省内存资源和计算 时间 可以直接根据需求在当前节点的8 个相邻方向上获取有效节点作为子节 点 而非虚拟环境中事先选取好的一切出口节点 2 2 3d i j k s t r a 算法和a 算法的对比分析 通过前两节的算法分析可以知道 d i j k s t r a 算法是在一种没有考虑目标点具 体位置的情况下盲目的进行搜索过程 可以将其看作是一种以起始节点为圆心 向外逐层搜索同心圆的过程 是一种同概率搜索 而a 算法这是从分考虑目标 节点的位置进行的一种启发式搜索 每次搜索的过程都会考虑当前节点到目标 节点的代价估计 是一种有目的的搜索 d i j k s t r a 算法在搜索两点间的最优路径时 会从起始节点开始 向外逐层搜 索每一个节点 知道目标节点出现 这样能够确定两点间的最优路径 但是搜 索的节点数量非常多 在计算小规模地图时能够在短时间内得到路径最优解 当地图很大是 该算法搜索的节点数量呈几何级增长 搜索效率相比a 算法是 非常低的 考虑到这些因素 本为选择对a 算法进行改进 2 3 本章小结 本章首先对路径规划技术进行了介绍 并介绍了其几种不同的分类方式 然后分别对两种常用路径规划算法a 算法和d i j k s t r a 算法进行了研究 并结合虚 拟场景的路径规划的特点对这两种路径规划方法进行了对比分析 选择更适合 于本文的路径规划方法来进行改进 1 4 武汉理工大学硕士学位论文 第3 章虚拟环境下基于a 六算法的改进算法设计 在人工智能领域中 对路径规划算法的研究是一个重要的部分 其中 人 工智能的自动寻径部分都是较为复杂的 由于智能体移动时采用的是智能技术 因此 构建导航图和设计群体路径规划算法是紧急情况下的大规模人群疏散系 统中最为核心的模块 例