带“洞”多边形的Online探索策略研究

论文摘要

基于巡视员路径问题(WRP)、局部最短路径等问题求解思路,以及多边形探索领域已有成果,本文对平面上带洞多边形的Online探索问题进行了研究,目标是设计一个online探索策略,使机器人能够在带洞多边形中从给定起点出发,找到一条闭合路径,能够看到多边形内部的所有区域。Online探索问题的研究,涉及动态搜索、最优路径规划、算法设计与分析等基础理论知识,是计算几何学领域的理论课题,具有很高的理论研究价值。同时,Online探索问题在机器人目标搜索、未知区域探索等实际应用领域,也有着广泛的应用前景。本文首先论述了与Online探索问题相关的基础知识和基本算法,分析了多边形探索问题的现有研究成果,如关键映像点、关键切线访问方法等,在此基础上,结合带洞多边形的几何信息分析,提出了将带洞多边形的Online探索问题转化为多个简单多边形后再分别进行探索的求解方案。为此,本文首先研究了不带洞的简单多边形探索算法,然后分析了带洞多边形探索问题中“洞”的状态属性,通过对状态属性的划分,选取合适的构造方法,将其转化为简单多边形,并对转化后的简单多边形,调用简单多边形探索算法完成探索,最后综合各简单多边形的探索算法,设计出带洞多边形的Online探索算法,分析所设计的算法,并给出了算法可视化运行结果。实验结果表明,本文提出的带洞多边形online探索策略,是平面上带洞多边形探索问题的一个有效算法。

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 研究背景与意义
•   1.2 国内外研究现状
•   1.3 主要研究内容
•   1.4 论文章节安排
•   1.5 本章小结
• 2 基础知识及相关算法
•   2.1 基本概念
•   2.2 基本问题及算法
•   2.3 本章小结
• 3 带“洞”未知多边形探索问题的求解策略
•   3.1 未知多边形探索问题描述
•   3.2 未知多边形探索的特性
•     3.2.1 （?）倍巡视员路径问题的近似算法
•     3.2.2 角壳及其基于角壳的求解算法
•   3.3 右多边形探索
•     3.3.1 可视切线的访问方法
•     3.3.2 右多边形探索算法
•   3.4 简单多边形探索
•   3.5 寻找一条包围洞的最短路径
•   3.6 混合方法
•   3.7 本章小结
• 4 算法设计及其性能分析
•   4.1 算法流程设计
•   4.2 算法竞争比分析
•   4.3 本章小结
• 5 算法实现及其结果分析
•   5.1 带“洞”多边形的构造
•   5.2 运行结果及分析
•   5.3 本章小结
• 6 总结与展望
•   6.1 论文工作总结
•   6.2 进一步研究工作
• 参考文献
• 致谢
• 作者简历及攻读硕士学位期间的科研成果

文章来源

类型: 硕士论文

作者: 王方非

导师: 蒋波,杨毅军

关键词: 计算几何,机器人,探索算法,目标搜索,竞争比

来源: 大连海事大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 大连海事大学

分类号: O221;TP242

DOI: 10.26989/d.cnki.gdlhu.2019.001391

总页数: 57

文件大小: 3538K

下载量: 9