（计算机软件与理论专业论文）三维高程地形中的多对象协同寻路.pdf

兰州大学研究生学位论文三维高程地形中的多对象协同寻路 摘要 路径规划、寻路问题是当前计算机科学领域中具有较高研究价值的一类问题，在计 算机网络路由算法设计、机器人探路、交通路线导航、人工智能、交互虚拟现实等系统 中有着广泛的应用。但传统的寻路研究多集中在对二维平面路网空间中单个寻路个体的 寻路研究上，随着计算机硬件处理能力以及应用环境的不断提高与发展，在具有高程信 息的三维地形中如何通过协同交互来发现多个寻路个体之间的最优路径成为了寻路问 题的一个新研究热点。 本文在认真分析寻路过程中个体的选择和状态转换过程的基础上，通过对传统寻路 算法及模型进行改造和重构提出了一种在三维高程地形中多对象协同交互寻路的方法， 所做的主要工作和取得的创新成果主要体现在以下几个方面。 首先，在研究一维分形布朗运动的基础上，扩展并提出了二维分形布朗运动的数学 模型，并且证明了模型理论的正确性。构造出了三维高程分形随机地形的生成方法。该 方法具有生成速度快、生成的地形精度高的特点，生成的地形满足真实地形所具有的随 机性和自相似性。 其次，在寻路路网构造完成之后，本文设计一种基于特征保持的网格简化算法，该 算法克服了随意性、难操作的缺陷，保持了原始地形的基本形态和高程信息，完成了路 网网格的简化，能够大幅度提高寻路算法的性能和效率。 再次，为了解决寻路过程中多对象协同交互问题，本文通过研究构造了一个正反馈 协同交互系统模型。在该模型中系统通过决策信息索来保证正反馈协同寻路过程，为多 对象间的协同交互提供了稳定、快速的互操作模型，并给出了协同交互系统的收敛性分 析，经过理论证明本文提出的协同交互系统是可以在一定时间范围内收敛到最优解。 最后，在3 d 交互虚拟现实引擎设计中对文中所提出的三维高程地形中多对象协同 寻路方法如何应用进行了讨论。 关键词：正反馈协同寻路二维分形布朗运动决策信息素特征网格化简 兰州大学研究生学位论文三维高程地形中的多对蒙协同寻路 a b s t r a c t p a t hp l a n n i n g f i n d i n gp r o b l e m sa r ev e r yv a l u a b l yt ob er e s e a r c h e di nc o m p u t e r s c i e n c e i nal o to ff i e l d s ，s u c ha sn e t w o r kr o u t i n ga l g o r i t h md e s i g n ，r o b o t sr o u t e s e x p l o r i n g t h en a v i g a t i o no ft r a f f i cp a t h ，a r t i f i c i a li n t e l l i g e n c ea n dr e a c t i v ev i r t u a lr e a l i t ys y s t e md e s i g n ， i tc o s t sal o to fa p p l i c a t i o n b u tc o n v e n t i o n a ls o l u t i o n sm a i n l yf o c u so n2 dp l a n a rp a t h n e t s t r u c t u r ea n di n d i v i d u a lp a t h - f i n d i n gu n i t a l o n gw i 廿1t h ei n c r e a s e m e n to f c o m p u t e rh a r d w a r e a n dd e v e l o p m e n to fa p p l i e de n v i r o n m e n t ，i nt h e3 dt e r r a i nw i t hh e i g h ti n f o r m a t i o n ，w eh a v e t op r o m o t eas o l u t i o nt ot h ep r o b l e mt h a tm u l t i u n i t sh o wf i n dt h eb e s tp a t hw i t ht h eh e l po f c o o p e r a t ec o m m u n i o n d t t r i n g al o to fr e s e a r c ho nu n i ts t a t u sc o n v e r s i o np r o c e s s ，b yr e b u i l d i n ga n d r e c o n s t r u c t i n gc o n v e n t i o n a lp a t h f i n d i n ga l g o r i t h ma n dm o d e l ，w ep r o m o t et h em e t h o dt o g u i d em u l t i u n i t sh o wt of i n dp a t hi n3 dt e r r a i nw i t hc o o p e r a t i o n t h em a i nw o r ki ss h o w e d i r k t h ef o l l o w i n g f i r s t ，o nr e s e a r c ho fc o n v e n t i o n a lf r a c t a lb r o w nm o v e m e n t ，t h i sp a p e re x p a n dt h e m a t h e m a t i c a lm o d e lo fp l a n a rf b m ，a n dp r o v ei t sc o r r e c t n e s s t h e r ef o r , w eh a v ep u tf o r w a r d am e t h o dt oc r e a t e3 dh e i g h tf r a c t a ls t o c h a s t i c t h i sm e t h o di sv e r yf a s t ，a n dw ec a l lc r e a t e h i g ha c c u r a t et e r r a i n t h et e r r a i nh a sc h a r a c t e r i s t i co f r a n d o ma n ds e l f - c o m p a r a b i l i t y s e c o n d l y , i no r d e rt om a k et h ep a t h - f i n d i n gc o r r e c t ，t h e n ，w ec o n s t r u c tp a t h - n e t so nt h e t e r r a i n ，f o r ms e a r c h a b l es t a t e s p a c e sm a r s h a l t oi m p r o v et h ep a t h f i n d i n ge f f i c i e n c ya n d p e r f o r m a n c e ，w ec o m p l e t et h ep r e d i g e s t i o no fp a t h - n e tg r i d s t h i r d l y , i no r d e rt os e t t l et h er e a c t i o np r o b l e mo fm u l t i - u n i t s ，t h i s t e x tc o n s t r u c t sa r e a c t i v es y s t e mb yr e s e a r c h t h i ss y s t e mg u a r a n t e e st h ep r o c e s so f c o m m u n i o no f m u l t i u n i t s b yp h e r o m o n ea n dr e a c t i v ec o m m u n i o nm e c h a n i s m ，p r o v i d i n gs t e a d ya n df a s ti n t e r 。o p e r a t e m o d e l ，f o l l o w i n gt h i sp r i n c i p l e ，m u l t i u n i t sa r ea b l et of i n dt h eb e s tp a t hb ys h a r i n gt h e i n f o r m a t i o na n dc o o p e r a t i n gr e f l e c t i o n a l s o ，w eg i v et h ea t t e s to ft h ec o m m u n i o na s t r i n g e n c y i l l u m i n a t et h a tw em u s tg e tt h eb e s ts o l u t i o nd u r i n gs o m et i m e f i n a l l y , w eh a v ed e s i g n e dam u l t i - u n i t sp a t h f i n d i n gs y s t e m i n3 dr e a c t i v ev i r t u a l r e a l i t y ( v r ) e n g i n ed i c u s st h ea p p l i c a t i o no f m u l t i u n i t sp a t h - f i n d i n gm e t h o d k e y w o r d s ：p o s i t i v er e a c t i o nc o o p e r a t ep a t hf i n d i n g 2 - d i m e n s i o nf b m d e c i s i o np h e r o m o n e e a r m a r kg r i d sp r e d i g e s t i o n 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行 研究所取得的成果学位论文中凡引用他人已经发表或未发表的成果、 数据、观点等，均己明确注明出处。除文中已经注明引用的内容外，不 包含任何其他个人或集体已经发表或撰写过的科研成果对本文的研究成 果做出重要贡献的个人和集体，均已在文中以明确方式标明 本声明的法律责任由本人承担 论文作者签名：过丝 日期：竺：! ：生 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产 权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论 文的规定，同意学校保存或向国家有关部门或机构送交论文的纸 质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以 采用任何复制手段保存和汇编本学位论文。本人离校后发表、使 用学位论文或与该论文直接相关的学术论文或成果时，第一署名 单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：釜缝导师签名： 缘冬日期：业 兰卅i 大学研究生学位论文 三维高程地形中的多对象协同寻路 第一章引论 1 1 问题的提出与研究现状 路径规划、寻路问题( p a t hp l a n n i n g f i n d i n gp r o b l e m ，p p p p f p ) ，主要是指在给定的原始 地图路网中寻找出一条从起始点到目标点之间的最优路径”“。此类问题具有非常重要的实际意义， 可以应用于计算机网络路由算法的设计“、机器人探路、交通路线导航”1 、人工智能“、游戏 a i 系统的设计与开发“”等很多方面，越来越受到计算机研究人员的重视。 从上个世纪末开始很多科学家都至力于这方面的研究，到目前为止已经产生了一些成果这些 研究成果主耍表现在两个方面：静态寻路方法和动态寻路方法”。 静态寻路方法主要是指在外界环境( 寻路地形信息) 不变的情况下，计算最优路径。其中比较 有代表性的如：d i j k s t r a 算法和a 木算法”。d i j k s t r a 算法是最经典的最短路径算法，也是最初被 公认的最好的寻路算法”。用于计算一个节点到其他所有节点的最短路径”。d i j k s t r a 算法虽然原 理简单易于实现，且一定可以在寻路路网中得到最优解。但是也存在着很大的缺陷：首先，此算 法盲目性较大，寻路过程中没有指导方向，所咀对于范围比较大的路网，计算量很大。其次，此算 法需要计算从一个节点到其他所有节点的晟短路径，计算了很多无用的和冗余的信息，浪费了大量 的时间，效率很低1 。a 丰( a s t a r ) 算法是一种静态路网中求解最短路径比较有效的方法。4 ”1 。斛 算法在人工智能学术界中是一种历久弥新的算法。自1 9 8 6 年以来已用于解决各类问题。并且此算法 对于静态路径规划也是非常有效的。“。虽然a 算法是静态路网中较好的一种寻路方法，但是也存在 着如下一些缺陷：首先，a 丰算法对估价函数要求比较严格，只有估价函数小于实际值，才能保证找 到最优答案。其次，a 丰算法的使用环境约束条件较多，非常适用于方形网格构造的路网，对使用其 他方式构造的路网并不适用。再次，a 算法无法在动态地形环境中使用，所以对于地形状态实时改 变的情况，无法作出正确的判断。而且在一张大范围的路网中，a 丰算法可能需要遍历数百甚至上千 个节点”“这样就花费了太多c p u 时间并且占据大量的存储空间。 动态寻路方法是指外界环境( 寻路的地形信息和寻路条件) 不断发生变化，在不能预估计的情 况下计算最短路径。主要用于机器人探路的研究。比较有代表性的方法如d 算法。d 是动态a 术( d s t a r d y n a m i ca 丰) 算法其首次在卡内及梅隆机器人中心的s t e n t z 在1 9 9 4 和1 9 9 5 年两篇论文 中提出的”“，主要用于机器人探路。d 算法已经对a 术算法做了一定的改进，所以d 算法最大的优 点是可以在动态路网上进行路径规划。但是d 算法对于我们的问题环境来说仍然存在着很大的缺陷 口7 1 ：首先，d 算法在指导寻路个体遇到障碍物的行动方面过于单一，仅仅是寻找绕过障碍物的最优 路径。然而这样找到的路径并不能保证是全局最优的。其次，d 算法虽然可以工作在简单的具有 三维高程信息的地形模型上，但对于多个寻路对象从源点向目标点出发进行寻路这种协同交互合作 兰州大学研究生学位论文 三维高程地形中的多对象协同寻路 晌情况，d 算法无能为力。 1 2 主要工作及工作成果 基于以上分析，无论是静态寻路模型中的d i j k s t r a 算法，斛算法还是动态寻路模型中的d 算 法。都存在着无法在具有高程信息的三维地形上进行寻路的缺陷。其次，缺少对多对象寻路中对象 问协同、交互机制的研究，无法发挥群体的优势寻找出最优路径。 由此，本文提出了在三维高程寻路路网中，多个寻路个体从同一目标地点出发经过交互、影 响、协作最终找到全局最优路径的方法。 本文的研究内容主要包括： 在对一维分形布朗运动研究的基础上，提出了二维分形布朗运动的数学模型，以此为基础， 计算三维地形高程信息中的随机地形偏移量d ，并证明其迭代计算过程是符合二维分形布 朗运动的，并通过线性插值的方法，生成三维高程随机分形地形。 为了使寻路过程更加快速、高效率的进行。我们必须对构造的寻路路网进行网格简化，本文 提出了一种基于特征保持的t i n 网格简化算法。通过此算法，我们可以在牺牲很小的高程信 息的情况下对寻路路网做出很大程度的简化从而提高寻路的效率。 为了解决寻路的多个个体之间的协同、交互。真正做到个体和个体之间共同思考，交互决策 来求得全局最优解。本文提出了正反馈协同交互系统，此系统通过决策信息素和正反馈协 同机制，给出了多寻路个体之间在寻路过程中的交互过程，从而保证了多对象协同寻路的成 功。 最后，对文中所提出的三维高程地形中多对象协同寻路方法，在3 d 交互虚拟现实引擎中 如何应用进行了讨论。 2 兰州大学研究生学位论文 三维高程地形中的多对象协同寻路 第二章相关理论与技术 2 1 三维高程地形的生成及简化的主要原理及相关技术 2 i 1 三维高程地形及寻路 三维高程地形是指在传统的二维平面栅格地形表示中，加入第三维高度维。使得每一个在计算 机中存储和表示的坐标点，除了具有在x o y 平面中的相对位置之外，还具有高度z 的信息。这样， 我们形成的地形不再只具有二维平面空间上的位置信息，通过第三维高度维的表述，得到了形如同 自然界中高低起伏的真实地形的存储、显示以及计算的方法。 三维高程地形中的寻路：在三维高程地形中，路径规划问题仍然是找到一条从起始点到中止点 的最优路径。但是寻路环境的变化对寻路方法提出了很大的挑战。代价估算，状态转移，路径决策等等 问题都要重新考虑和研究。 下面是一些比较成熟的三维地形生成算法和基本理论： 2 1 2 方形一方形细分算法 根据“新生正方形的面积是已存在正方形面积的一半”这一原则，产生插值点的位置坐标，其高 程值由权重l l 9 ：3 ：3 ：1 决定，距离最近点具有最大的权系数，这种插值方法构成了一个双二次曲面 的效果，它的一个重要优点是地景表面的法线是连续的，所以消除了三角形细分法中的“折痕现象” 。1 ，此外由于双二次曲面的效果影响，因此，用这个算法构造的地景轮廓比较柔和，但是如果需要，也 可以通过减小h 使表面更粗糙，另外，还可以通过放大y 值，使表面更粗糙，使山峰更突出，从而可以得 到陡峻的地景效果“1 。 虽然中点位移法简单，快速，但通常难以预测生成结果的大致形状，针对这个问题，提出了新的真 实感地形的分形生成方法 2 1 _ 3 分形布朗运动 它可以分解成一系列相互独立的高斯随机变量的累加，即在某一连续时间范围内，若干个高斯 分布的随机事件的积累可以形成布朗运动，从而建立了布朗运动盼数学模型。 布朗运动是1 8 2 7 年英国植物学家r b r o w n 在研究花粉时发现的。1 。它是一种随机运动，花粉微粒 的运动方向是随时改变的，其运动轨迹是一条无规则的折线，不受什么约束和支配。1 9 2 3 年，德国 数学家n w i _ e n e r 通过统计学规律分析，他认为布朗运动是一个随机过程， 研究表明”1 ，布朗运动的样本轨道具有统计自相似性，其数学描述如下： 3 兰型查兰堕! ! 皇兰垡笙苎 三堡壹堡丝翌! 塑兰翌墨塑旦量堕 若设x ( t ) 为一维空间上的随机过程，对于任意自变量t l ，t 2 ，该过程的增量： x ( t ) = x ( tz ) 一x ( t z ) 。具有高斯分布，而且其方差与自变量的差成比例，即有式2 一l 成立： e ( a x ( i ) ) = e i x ( f - ) 一x ( fz ) | 】i t2 一t - i ( 2 1 ) 此时对于任意的t o 和r ( r 0 ) ，以下两个变量： x ( t o + f ) 一x ( t o ) 和下1 ( x ( f 。+ ，f ) 一x ( f 。) ) 具有相同的有限维分布函数因而他们具有相同的统计特性，故认为该随机过程具有统计白相 似性。 2 0 世纪6 0 年代，m a n d e l b r o t ：和n e s s 通过对布朗运动的扩展，提出了分形布朗运动的概念和模型 引，一维f b m 是定义在某个概率空间上的一个随机过程v ： 0 ，。 一 r ，且满足如下条件： ( 1 ) 以概率lv ( t ) 连续且v ( 0 ) = 0 二 ( 2 ) 对于任何t 0 和h 0 ，v ( t + h ) 一v ( t ) 服从如下分布： 州哪圳圳嘞 班南唧( 斋卜湫聪， 显然，f b m 具有如下6 个性质： 1 ) 服从正态分布：v ( t ) n ( 0 ，t 2 “) 。 2 ) v ( t ) 是非平稳过程。 3 ) 增量平稳。 4 ) 具有统计自相似。 s ，平方变差为川“，绝对变差异为( 纭r 6 ) f b m 曲面的h a u s d o r f 维数和盒维数以概率i 等于( 3 - h ) 。 设v = v ( t 2 一t 1 ) ， at = t 2 一t l ，则f b m 可写为v o c t h ，对于x y 平面上的f b m 可表示为v 一r “， 其中r 2 = x 2 + 6y 2 。随机过程v ( t ) 可采用它的谱密度( ，) 刻画，若v ( t ) 是通过频率为，且具 有厂带宽低通滤波器的输入则s = 1 y ( ，_ ) | 2 矿，当岛( 厂) 在低频，处急剧增加时v ( t ) 的 变化会变得缓慢，对于f b m 而言( ，) = f ，其中p 为f b m 谱密度的幂次。对于f b m 的分形维数d 、 欧拉维数e 、分形参数h 和口存在以下关系： d ：e + 1 一日：e + 半 ( 2 - 2 ) 在式2 2 中，0 h i ，e d e + i ，z g ( n ) 时， 可以省略g ( n ) 。启发式搜索其实有很多的算法，那么我们在三维高程路网中的寻路算法又是一种什 么样的算法呢? 其实这种算法也是一种最好优先的算法。只不过要加上一些约束条件。由于在一些 问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题， 定义3 - 6 如果一个估价函数可以找出最短路径，我们称之为可采纳性。 定理3 1 在三维高程寻路路网中寻路算法是一个可采纳的最好优先算法。 证明：根据以上论述： 设算法的估价函数可表示为：f ( n ) = g ( i 1 ) + h ( n ) f ( n ) 是估价函数，g ( n ) 是起点到终点的最短路径值，h ( 1 1 ) 是r l 到目标的最短路经的启 2 兰州大学研究生学位论立三维高程地形中的多对象协同寻路 发值。其“( n ) 为去+ g ( f ，m 州n ) 为砌) 。由于训) 肯定，j 、于从被选择网格到 目标网格的实际路径耗费( 由式3 。2 可知) 。则可以证明应用这样的估价函数是可以找到最 短路径的，也就是可采纳的。 证毕。 由此，我们提出的寻路算法中路径估价和判断的计算函数是成立的，经过证明是可以找到最优 解的。 3 3 寻路过程的构造和描述 3 3 1 寻路过程的简单描述 为了解决多对象协同寻路的问题，在初步描述问题域的基础上，给出了简单的多对象正反馈协 同交互寻路的基本流程，为后面的研究和设计工作给出一个指导方针。初始工作流程图如图3 一l 所 示。 图3 - l真实地形正反馈协同交互寻路初始模型 在图3 - 1 中，椭圆代表原操作。箭头代表数据流向和原操作的执行顺序。长方形表示产生和传 输的数据。做为原操作相互交流的媒体。两个重要的辅助过程在图中使用单向箭头表示其作用。通 过这两个辅助过程的处理，使产生的数据变化为我们寻路需要的数据，在辅助过程的帮助下，也使 1 3 兰十i , i 大学研究生学位论文三维高程地形中的多对象协同寻路 原操作能够支持寻路工作。 3 ，3 2 寻路方法的基本框架及功能结构关系 3 3 2 i 寻路方法的结构框架 以上我们定义了在设计真实地形正反馈协同交互寻路模型的原形系统时用到的一些定义及概 念，以此来保证我们的原形系统可以正确的构建。下面我们给出寻路模型原形系统的框架图，展示 模型中各个部分的功能结构关系。 如图3 2 所示，表达了系统内部的交互和工作过程。 图3 - 2 寻路模型的基本结构框架 在系统框架图中。s 1 ，s 2 表示两个外部输入数据。a ，b 表示两个预处理过程。 p 卜p 7 表示模型框架中的主要处理过程，空心箭头表示重要的数据交互过程。 下面，我们来分析模型框架中的功能结构关系。 4 兰州大学研究生学位论文三维高程地形中的多对蒙协同寻路 3 3 2 2 框架的结构及功能结构关系 ( 1 ) 框架图的结构 在模型框架结构图中。 s i ，s 2 表示两个外部输入数据集合。其中s l 表示原始的地形资料数据集合，它向预处理过程a 输入原始地形资料信息。s 2 表示存储寻路各个信息的数据集台，一方面从处理功能p 7 中读取寻路 判断信息一方面负责寻路个体的出发时刻的控制。 预处理过程a 进行可控的具有自相似特性随机分形地形的生成过程。预处理过程b 进行寻跆路 网网格的生成及简化。 p l ：负责寻路信息的接收，初始化以及更新。 p 2 ：计算相临网格的地形行进代价g ( i 。j ) 。 p 3 ：计算寻路个体的估价值。 p 4 ：计算并更新相应网格上的决策信息量的强度r ，( f ) 。 p 5 ：完成路径选择过程。 p 6 ：判断单个寻路个体是否找到最优路径。 p 7 ：进行全局决策信息素的更新。 ( 2 ) 功能结构关系 、 初始状态下，模型首先输入地形资料信息，经过预处理过程a ，b 得到简化完成的寻路路网信息。 从s 2 读入一个寻路个体的信息。根据处理功能p l 的执行，进行寻路信息的初始化和更新。经过 p 2 ，p 3 ，p 4 的计算，得到路径决策所需的所需信息，根据这些输入信息，由p 5 进行选择，决定寻路个体 下一步的寻路方向。p 6 判断寻路个体是否到达终点。如果已经到达终点，则通过p 7 来进行比较，按 比例加强所有得到的路径中代价最短的那条路径上的所有网格的决策信息素。如果没有达到终点则 返回p l 处继续进行寻路。 综上所述，真实地形正反馈协同交互寻路模型是很多过程和处理模块共同协调，分工合作来共同 完成寻路过程的。我们已经看到了各个部分之问的功能结构关系。下面，我们需要对寻路模型原形的 工作流程进行详细的描述。 3 4 寻路过程中需要解决的关键问题 通过分析寻路模型框架结构图我们可以归纳出来。要完成在三维高程地形中多对象正反馈协同 寻路过程。我们需要解决好几个问题。 3 4 i 三维高程地形路网的生成和构造问题 在图3 2 中所表示的方法模型中，标号a 表示的预处理过程在正确完成之后，我们需要得到带 有高程信息的三维路网网格，而且要具有可控和随机自相似的特点。 1 5 兰州大学词f 究生学位论文 三维高程地形中的多对象协同寻路 生成高度真实感地形，一直是计算机图形学的重要的研究课题。经过多年的研究和积累，对于 较为规则的欧几里德形体( 即能够用欧几里德方法准确描述的几何形体) ，人们已经给出了较为成熟 的真实感图形生成理论和方法。而对于诸如山脉、云彩、树木等自然对象，由于无法写出相应的精 确的描述方程，通常只是用一些简单的规则形体来近似地拟合其效果往往不能完全令人满意，而 且计算效率也有待提高”。分形几何为解决这类自然对象的真实感图形生成问题提供了新的思路和 方法。 虽然分形几何的方法给我们生成真实地形提供了很大的帮助，但是分形几何在构造自相似真实 地形时会有较多的问题。分形地形的生成太过于“自动化”，虽然可以生成严格符台自相似性的地形， 但是外界环境无法控制地形地貌。也就是说传统的分形地形生成方法无法满足用户的实时要求， 更无法对地形做实时的修改。我们寻路路网的构造需要在用户环境信息交互参与的情况下实现生成 地形。我们需要解决这个问题，来生成具有可控性的自相似三维高程分形地形。 3 4 2 寻路路网网格的简化问题 预处理过程b 需要解决路网网格简化问题。在得到了三维高程地形路网初始空间后由于寻路 算法是基于搜索的一种洪泛算法，搜索范围的大小以及速度的快慢大大影响了寻路算法的效率。为 了使寻路算法更加稳定和高效。需要解决路网空间中地形网格的简化问题。 存在一些成熟的网格简化算法“1 。但是由于寻路环境的限制，传统算法存在着很多缺陷。解 决这个问题是要提出一个路网空间的网格简化算法，进行有差别检查和筛选，对于地形信息和地理 特征比较重要的地形网格，进行重点考虑，在保证一定的地形特征和保真度的前提下进行网格的简 化。通过解决此问题，既得到了优化的路网空间，为快速执行寻路算法奠定了良好的基础，又使原 始的地形地貌特征得到了保持，使得寻路算法更加健康和稳定。 3 4 3 正反馈协同交互系统 处理过程p 4 ，p 7 解决各个寻路个体之间如何进行交互影响，实现正反馈的决策信息素的交互和 影响。协同交互正反馈子系统是多对象协同寻路问题的重点问题。也是多对象寻路和单独个体寻路 问题相互区别的根本所在。 多对象协同寻路不同于个体单独寻路。多对象协同寻路着眼于多对象的群策群力，个体在多对 象寻路中发挥积极的正反馈的作用，共同协作以达到全局最优。而不是简单的对多个寻路个体多次 调用传统的寻路算法来简单和原始的模拟多对象寻路。 基于以上描述，在多对象协同寻路模型中，多个寻路个体如何相互影响、相互交换正反馈信息， 又是如何进行个体决策，来达到全局最优问题就是我们需要真正解决的。 6 兰卅l 大学研究生学位论文 三维高程地形中的多对象协同寻路 第四章三维高程地形路网网格的生成及简化方法 三维高程随机分形地形的生成是我们首先要解决的一个问题，只有组织良好的寻路环境，寻路算 法才能健康，快速，高效的发挥作用。 本章在研究一维分形布朗运动的基础上，扩展并提t 丑t - - 维分形布朗运动的数学模型。并且证明 了模型理论的正确性。构造出了三维高程分形随机地形的生成方法。该方法具有生成速度快、生成 的地形精度高的特点。并且生成的地形具有随机性和自相似性。 4 1 三维高程随机分形地形的生成 三维高程随机分形地形的生成需要一定的理论基础，我们首先完成地形生成中公式，概念的定义 然后给出了公式及定理的证明过程。以此来验证理论的正确性。 4 1 1 随机地形偏移量 为了使我们生成的高程三维地形具有自然界中真实地形的统计自相似性和随机性。我们需要附 加一个可以随生成地形迭代次数不断增加而逐渐变化的随机偏移量d ( 第i 次迭代时使用的随机偏 移量为d ) 。为了保证我们构造的地形的自相似性，这些随机偏移量必须符合均值为0 ，方差为玎2 的 r 7 1 高斯分布。随着算法中迭代过程的不断深入。基平面上的正方形网格会不断细化，求取中点的网 格尺度也随之减少，相应地，在每次迭代过程中相应的随机偏移量的扰动幅度也要成比例减少，它 是与随机变量的方差直接相关的。 下面，我们说明生成以上这些随机偏移量的生成过程8 ( u ) 是符合二维分形布朗运动的。 4 1 2 二维分形布朗运动的数学描述 由于生成的随机地形是具有三维属性和特点的高程地形。所以前面所描述的基于一维的分形布 朗运动是不适用于三维欧氏空间中的。我们需要得n - - 维分形布朗运动的数学模型。以次来证明生 成随机偏移量的随机过程b ( u ) 为二维f b m 。 将一维分形布朗运动”3 ，推广到二维： 设有多维随机函数( 过程) x ( t ，t z ) ，其中tz ，t 2 为自变量。若x ( t ，t z ) 具有如下性质： ( 1 )任意随机增量x = x ( t ，t 。) 一x ( s 。s 。) ( 其中t ，s ( i ，j = l ，2 ) 均为自变量) ，是均值为 o ，方差为盯2 的高斯随机变量； ( 2 ) 而且随机变量x 的方差只依赖于如下的距离d ： 7 兰州大学研究生学位论文 三维高程地形中的多对象协同寻路 d= 具体地说就是增量x 的方差与距离d 的2 h 次幂成比例，即有： v a r 峭：e ( i x ( t l , t 2 ) ( s 。，s ：) n ( 2x ，( 卉一j ，) ：) “( 4 1 ) 式中，t 。8 j 均为同一定义域上的自变量值，且具有各向同性，参数肺女足0 1 。 则满足上述( 1 ) ( 2 ) 两点的随机增量x 构成的随机过程，即为二维分形布朗运动，它同样具有 在多维空间中的统计白相似性。 4 1 _ 3 随机过程的证明 定理4 - 1 生成随机偏移量地随机过程b ( u ) 是二维分形布朗运动。 证明：设b ( 驴) 为一随机过程，盯表示某点的位置向量( u ，u ) 。 bh ( f i - ) = b 片( “，“，) 2 ；南 。l ， - - r l “。1 7 2 一i r l “一。2 ) d 占( f ) + 。，i f i - - f - i n - t 1 2 d b ( f ) 5 志 ( 瓜习丽广啦卜可广啦y ) d x d y + rr ( 瓜二阿万万) 肛”2 ) w ( x ，y ) d x d y 可以得到b ( 口) 的相关函数为： r 。一( r ) = e b 一( 犷) b 一( 矿) 】= c ( i 矿1 2 ”+ i 矿1 2 “一i 矿一矿1 2 “) 其中，h 为h u r s t 指数，c 为h 的函数，w ( x ，y ) 为二维高斯白噪。 不难推得研，( 玎) 具有如下性质： 增量z 精( 瓦) = b 日( 瓦一历) 一b ( 瓦) 是一个平稳的零值高斯过程。 带八上式可得出增量的舶( 万) 方差仅仅依赖于距离“= “；+ “；。则命题条件( 1 ) 得怔。 对b 一( 万) 取平均数学期望，得 e i b ( 矿) j 2 】= 2 c ( 矿) 片说明随机过程的变化的期望与自变量的变化成正比 则条件( 2 ) 得证。 在条件( 1 ) ( 2 ) 都得到证明的前提下，可知随机过程( 函数) b ( 万) 为二维分形布朗运动。 证毕。 一 兰州大学研究生学位论文 三维高程地形中的多对象协同寻路 4 2 地形生成方法及过程 4 2 1 地形数据的输入和表示 初始条件是一系列具有几何信息的数据集，其中最重要的就是地表高程信息，这是生成具有真 实感的地形所必须的。 数据集中，每一项数据由一个四元组来唯一的表示。称之为高程四元组。 对于初始地形数据，如果地形数据非常详细。则表明生成的地形具有非常高的细节表现。必然 会导致数据集合中四元组的数目比较多，我们应该尽量节省存储空间，使用空间利用律比较高的链 式方法来存储数据集合中的四元组。 4 2 2 高程综合控制系数的确定 高程综合控制系数用来综合考虑输入的地形数据对生成的最终地形的影响。由于高程综合控制 系数有给定地形数据的高程值来插值得到，此系数可以实现对待生成的地形的可控性。可以使生成 的地形符合我们的要求。 高程综合控制系数的确定如下面的公式所示： ：望! 兰! 里! 兰! 旦! 兰! = = = ：望竺空 胛 ( 4 - 2 ) 在式4 4 中，。2 石7 二= 可i 1 石二了万，即。t 为第i 个地形控制点到中点的距离平方的倒数。距离 越远d ，越小。则d z 越小z 为第i 个地形控制点的高程值。这说明距离中点越远的地形控制点 对高程综合控制系数的影响越小。这符合我们对地形的控制要求。 4 2 3 基于随机地形偏移量的地形迭代细分法 为迭代生成三维高程随机地形，需耍建立三维的空间直角坐标系。如图4 1 ，在三维o x y z 坐标 系中选择x o y 平面上的正方形o a b c 为地形的初始基平面，起始范围由数据集中的初始地形大小决定。 设空间点p ( x ，y ，z ) 的水平投影点在基本平面内，其高度坐标为z 。 9 兰州大学研究生学位论文三维高程地形中的多对象西同寻路 x z 图4 一l 三维坐标系 在二维的分形布朗运动中，自相似性依然存在没，只是此时函数的定义域是在平面上，高度坐 标z 是x ，y 两坐标的函数，即z = z ( x ，y ) 。迭代细分过程中，高度坐标z 的生成过程总伴随着基平 面上网格的不断细化，如图4 2 所示： 图4 2地形迭代生成细化过程 设在第i 次迭代细分过程中的某个正方形四个角点处的高度值已知，其值按顺时针方向排列分别 为z l j ，z ；，z ；，z ；，则此正方形中心m 处的高度值z ：可以由四个角点处高度值的平均值与给定的中 点坐标的高度值的线形差值再加上随机偏移量d ，。即有： 互i = - , h o 生警+ h ( 1 - h ) + d f ( 4 _ 3 ) 在式4 3 中，z , i ，为正方形基平面中心处的高度值：z l f ，z ；，z ；，z ；分别为被细化正方形基平 面四个角点处的高度值；h 为给定的相关地形控制点高程综合评价系数：为权重值，表示各部分对 高程z ：的影响程度。d ，是中心点处的随机偏移量，它是一个均值为o ，方差为盯的高斯随机变量。 这样，原来的正方形基平面被等分成四个更小的正方形如图4 2 所示，初始情况下地形的四个角 2 0 兰州大学研究生学位论文三维高程地形中的多对象协同寻路 点的地形的高程信息就是已知的。也就是说，通过从原始地形的迭代细分过程，生成了我们需要的 符合分形布郎运动的地形中间控制点。这些控制点细化了基平面，也增加了空间中三维属性位置点 的密度。对每一个新生成的小正方形迭代的细分下去，就可以生成我们所需要的三维高程随机地形。 没初始的网格尺度为占，且其四个角点处的高度值已知。在求出方格中心点及四条边中点处的 c 高度值的同时，网格也完成了第一次细化，新网格的网格尺寸减小为原来的, 1 e ，即网格尺度为 鱼2 6 。按此方法对网格进行细化时，每个迭代周期中网格的缩小比例保持不变，恒为拿，我们 称之为扰动细化因子r 。 幽4 3 嘲格迭代细化过崔 如前所述，为了保证我们生成的地形具有自相似的特点，当基平面的网格扰动细化因子r 不断减 少时，随机偏移量的方差也作相应的调整。我们推导出在中点置换法中，在第n 次迭代所对应随机偏 移量的