学位论文 > 优秀研究生学位论文题录展示

受限环境下基于空间拓扑关系推理的三维路径规划研究

作　者: 牛磊
导　师: 朱国宾
学　校: 武汉大学
专　业: 摄影测量与遥感
关键词: 受限环境三维空间拓扑关系定量空间推理多层次路径规划
分类号: P208
类　型: 博士论文
年　份: 2010年
下　载: 48次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机人工智能的发展以及城市化进程对人工智能支持的需求扩大,路径规划已被广泛应用于导航、规划、城市应急事件处理等各个方面。鉴于三维环境下的路径规划尤其是城市建筑物等受限环境由于引入了各种限制条件而更趋复杂,已经不适合再沿用传统的二维路径规划方案。为满足城市建筑物等受限环境的路径规划需求,本文尝试提出了一套应用于三维受限环境的路径规划方案。当前使用的路径规划解决方案存在着若干不足：首先传统路径规划没有使用空间拓扑关系；其次传统路径规划的基本移动规则没有适时改进；再次传统路径规划的数据组织方式存在效率问题。可见传统路径规划的最优路径结果衡量准则已无法满足现代需求。通过综合对现有搜索算法、空间拓扑关系和定量空间推理研究内容的分析,可以得出当前的路径规划研究重点应该是建立一套能够在受限环境下使用的基于空间拓扑关系推理的三维路径规划方案。为了建立该方案需要进行以下的研究：三维空间数据的拓扑关系引入、三维多层次式路径表达和基于能量最优的路径规划模式的实现。这中间的关键技术包括多层次的数据组织方式及路径规划、空间拓扑关系及定量空间推理的应用以及A*算法的三维改进。三维空间拓扑关系与定量空间推理的融合是本文数据结构和路径规划的基础。因为空间物体的拓扑关系对路径规划起到重要的辅助作用,比如路径规划方案可以利用空间拓扑关系来优化搜索范围。现有的有效获得空间物体的拓扑关系的方法是利用定量空间推理的相关技术来将已有的空间物体之间的定量关系转化为对应的空间物体的拓扑关系。为了达到此目的,需要引入一套能够适用于受限环境的改进空间物体拓扑关系与定量空间描述的对照体系。该体系中的每种拓扑关系包含了若干对应空间物体定量约束条件的集合,以及特定空间物体定量描述与对应空间物体拓扑关系的映射。在建立了空间物体拓扑定量推理的转化体系之后,就可以利用该体系对于路径规划环境进行分析处理,从而得到一套完整的有关路径规划环境的空间物体拓扑关系描述。由于路径规划往往涉及较大量的数据,因此必须探讨海量数据在路径规划方案中的存储与表达方式。因为空间物体拓扑关系都是以空间物体为单位进行描述的,所以路径规划方案的数据组织架构体系适合采用基于R-Tree的空间数据对象关系体系。此外数据组织在三维复杂情况下的具体实现方式和数据压缩的方法引入也是路径规划方案的重要组成部分。新路径规划方案的最优路径组织表达方式也和传统方案有明显区别。本文对于最优路径的表达引入了由用户决定主要范围和相关尺度的模式,利用该模式可以确定对于最优路径结果在何处采用精细路径表达以及何处采用粗略路径表达。这种表达模式需要空间拓扑关系和多层次式数据组织结构提供底层支持。除了这套表达模式,本文还提出了路径表达需要关注用户和系统的交互结果等在之前的研究中被忽视的因素,同时还建立了一套能量耗费最优的移动衡量准则用于满足用户相关需求。本文的路径规划方案的实现包括了三个部分,即路径规划环境的预处理、路径规划环境的构建以及多层次三维A*路径规划方案的实施。路径规划环境的预处理包括路径规划基本单元设置以及路径规划过程中基本移动规则的确立。路径规划环境的构建则包括了针对特定路径规环境采用特定方式来分析构建路径规划方案所需的多层次数据结构和空间物体拓扑关系。多层次A*路径规划方案的实施则介绍了改进三维A*算法利用空间物体拓扑关系推理技术和多层次的数据结构的特点来满足用户的多种路径规划需求的实现方式。为探讨本文路径规划方案的可推广性,专门设计了特定的实验。实验包括新路径规划方案中的算法性能分析和新路径规划方案的仿真应用。在新路径规划方案和传统径规划方案进行对比的过程中,展示出了新径规划方案具有占用较低的存储空间、使用较少运算时间等良好性能表现。除了具有性能优势外,新路径规划方案还能够根据用户的不同需求提供不同层次和不同范围的特定最优路径结果,这是传统路径规划方案所无法比拟的。但是新路径规划方案所给出的最优路径结果和传统的路径规划方案相比仍然存在着一定不足。在应用展示中,通过规划实验区域的逃生路线充分展示了新路径规划方案所具有的较好的应急反应能力。而仿真结果表明新路径规划方案能够为受限区域的大范围动态空间分析和应用提供有力的底层技术支持。通过以上研究,本文将空间拓扑关系和空间推理技术相融合应用于路径规划,并构建了将其实现的三维路径规划方案。在构建路径规划方案的过程中,建立了完整的空间数据结构体系和多层次路径规划模式,并攻克了相关的关键技术。论文通过仿真进行了系统验证,取得了一定研究成果,为将空间关系应用于路径规划提出了一种可行的应用模式。除此之外,本文还总结了受限环境下路径规划未来的发展趋势：即受限环境路径规划的多层次组织和表达研究；受限环境的基本构成单位研究;受限环境下三维空间物体拓扑关系深入研究；路径规划的能量最优模式研究。本文的创新点如下：1)空间拓扑关系在路径规划过程中的引入。2)多层次最优路径无缝融合表达。3)改进的三维空间寻路模式。

全文目录

摘要  5-8
ABSTRACT  8-12
第1章绪论  12-39
  1.1 路径规划的起源和发展  12-13
  1.2 三维路径规划研究意义  13-15
  1.3 路径规划相关研究现状  15-33
    1.1.1 路径规划算法  15-22
    1.1.2 空间拓扑关系及模型  22-28
    1.1.3 定量空间推理  28-32
    1.1.4 命题演算  32-33
  1.4 基于空间拓扑关系推理的三维路径规划研究目标  33-34
  1.5 基于空间拓扑关系推理的三维路径规划研究内容  34-36
  1.6 基于空间拓扑关系推理的三维路径规划的关键技术  36-39
第2章受限环境下三维空间拓扑关系推理  39-59
  2.1 空间拓扑关系基础  39-41
  2.2 受限环境内基本三维空间拓扑关系  41-46
  2.3 三维空间拓扑关系解析  46-54
  2.4 定量空间描述与三维空间拓扑关系的映射  54-59
第3章融合空间拓扑关系的层次式三维数据结构  59-68
  3.1 基于多层次技术的数据组织架构  59-62
  3.2 基于R-TREE的三维空间数据对象关系体系  62-65
  3.3 三维数据组织方式实现  65-68
第4章多层次路径规划构成  68-85
  4.1 多种路径规划方式的融合  68-72
  4.2 路径构成方式的改进  72-74
    4.2.1 基于空间拓扑的多层次最优路径  72-74
  4.3 路径规划方案的其它改进  74-85
    4.3.1 焦点与最优路径构成的融合  78-79
    4.3.2 用户和系统的交互  79-81
    4.3.3 基本移动耗费的最优模式改进  81-85
第5章基于受限环境的三维路径规划解决方案  85-104
  5.1 路径规划环境的预处理  85-92
    5.1.1 路径规划环境基本单元的确定  85-87
    5.1.2 路径规划基本移动规则的制定  87-92
  5.2 路径规划环境的构建  92-96
    5.2.1 空间域构成基本算法  93-94
    5.2.2 空间域增长算法  94
    5.2.3 空间域融合算法  94-95
    5.2.4 关键区域和关键节点的生成  95-96
  5.3 多层次路径规划方案的实施  96-104
    5.3.1 传统A~*算法改进  96-98
    5.3.2 空间域层次寻路算法  98-100
    5.3.3 空间域层次寻路方案最优证明  100-101
    5.3.4 空间域内三维A~*路径搜索算法  101-104
第6章路径规划实验  104-137
  6.1 实验区域设置  104-107
    6.1.1 实验环境的空间域划分  105-106
    6.1.2 路径搜索的关键参数设置  106-107
  6.2 新路径规划方案性能分析  107-127
    6.2.1 路径起始点设置  108
    6.2.2 路径搜索模式设置  108-109
    6.2.3 算法对比实验结果  109-126
    6.2.4 新旧路径规划方案的对比分析  126-127
  6.3 新路径规划方案应用案例  127-137
    6.3.1 疏散路径规划  127-130
    6.3.2 人群疏散仿真  130-137
第7章总结和展望  137-140
  7.1 受限环境下路径规划研究的总结  137-138
  7.2 路径规划研究未来发展趋势  138-140
参考文献  140-145
附录1:论文图表索引目录  145-147
附录2:攻读博士期间发表的学术论文  147-148
附录3:攻读博士期间参加的科研项目  148-149
致谢  149

受限环境下基于空间拓扑关系推理的三维路径规划研究

内容摘要

全文目录

相似论文