平面网格的高效探索策略研究
发布时间：2021-11-22 04:33
平面网格多边形的探索问题是典型的online探索问题。本文主要对平面区域中边界几何信息未知的网格多边形探索问题进行研究。关于该问题的研究,不仅涉及到计算几何、数学等领域的相关理论知识,而且涉及到未知危险区域撤离、搜救、游戏产业、机器人路径规划等实际应用问题的求解,所以具有理论和实际两方面的研究价值。网格多边形的探索问题可描述为:给定平面上一个网格区域和一个边界信息未知的多边形P以及与边界相邻的起始位置s,机器人从s出发,探索P内所有单元格后返回到s,完成对整个网格多边形的探索。研究的目标是要找到一个探索策略以优化机器人的探索路径,缩短探索时间。本文基于以下假设进行研究:一是机器人在初始状态不了解探索区域的几何信息;二是机器人具有一定的记忆功能,且能够跟随探索过程存储相关信息。本文在论述网格多边形中内部单元格、外部单元格、分割单元格、探索策略的竞争比等相关概念的基础上,分析了网格探索问题的深度优先搜索算法和改进的深度优先搜索算法,针对探索路径过长导致探索效率较低的问题,提出了本文的改进方法,设计出了 optDFS探索算法并分析了该算法的竞争比。最后,使用Python语言实现了 optDF...
【文章来源】：大连海事大学辽宁省 211工程院校
【文章页数】：66 页
【学位级别】：硕士
【部分图文】：
图１．１艺术画廊问题的示例??Ｆｉｇ．?１．１?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ａｒｔ?ｇａｌｌｅｒｙ?ｐｒｏｂｌｅｍ??
?平面网格的高效探索策略研宄???图１．２巡视员路径问题的示例??Ｆｉｇ．?１．２?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ｗａｔｃｈｍａｎ?ｒｏｕｔｅ?ｐｒｏｂｌｅｍ??Ｏｎｌｉｎｅ问题［２］是指在边界信息未知的区域中进行的目标搜索或区域探索，因此该问??题可分为搜索问题和探索问题。探索任务一般都交由智能机器人完成，并假设机器人具??有３６０°的视角。搜索问题是指在区域中对一个或多个几何元素例如点、线、多边形等进??行搜索；探索问题一般是指对整个区域进行的探索，即对区域内的每个点进行遍历。搜??索问题可在边界信息己知的区域中进行，通常称之为ｏｆｆｌｉｎｅ搜索问题，也可在边界信息??未知的区域中进行，通常则称之为ｏｎｌｉｎｅ搜索问题。??Ｏｆｆｌｉｎｅ搜索问题是指机器人在己知搜索区域的完备几何信息的前提下对目标进行??的搜索，即机器人在搜索开始前，对起始点、搜索目标点、区域中间有无障碍物等几何??信息完全了解，是一种行为目标十分明确的搜索。Ｏｆｆｌｉｎｅ搜索问题的一个示例如图１．３??所示。??Ｓｈｏｒｔｅｓｔ?ｐａｄｉｌ??Ｍｍｉｒｍｉｍ?ｆｅｉｋ?ｐａｔｈ、＇汉１??ｓ??图１．３?Ｏｆｆｌｉｎｅ搜索问题的示例??Ｆｉｇ．?１．３?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ｔｈｅ?ｏｆｆｌｉｎｅ?ｓｅａｒｃｈ?ｐｒｏｂｌｅｍ??－２?－??
?大连海事大学专业学位硕士学位论文???在平面区域ｉ？中，给定起始点和目标点／，阴影部分表示障碍物，且己知该区域??的边界几何信息。机器人从起始点Ｓ出发，寻找到一条从Ｓ到ｆ的最短路径。由于机器??人事先完全掌握了该多边形区域的边界几何信息，所以机器人会从所有路径中选择一条??最短的遍历路径［３］，即图１．３中的实线路径，并沿这条最短路径搜索到目标点／。若要求??寻找一条从ｓ到／的路径，并要求路径具有最少的拐点，则机器人会选择图１．３中的虚??线路径，并沿这条路径对目标点／进行搜索。针对ｏｆｆｌｉｎｅ搜索问题所设计的搜索算法通??常称为ｏｆｆｌｉｎｅ搜索算法＋６］。??Ｏｎｌｉｎｅ搜索问题［７＿９］是指待搜索区域的几何信息未知，即机器人在搜索该区域之前，??只知道起始点、目标点、以及一些局部信息，对区域中间是否存在障碍物、搜索区域的??边界在哪里等几何信息完全不了解，在这种情形下所进行的搜索。Ｏｎｌｉｎｅ搜索问题的一??个示例如图１．４所示，在平面区域７？中，给定起始点５和目标点？，阴影部分表示障碍物，??但机器人只知道起始点ｘ和目标点〖等局部信息，为了搜索给定区域，机器人需要安装??感知系统，在收集搜索区域的局部几何信息的同时探索前进，动态地搜索目标点〖，最??终形成一条搜索路径，如图１．４中虚线所表示的路径。在图１．４中，实线表示机器人知??道该区域几何信息的前提下对目标点／进行搜索所走的最短路径。从图１．４可以看出，??在事先不知道搜索区域的几何信息时，要想找到问题所对应的一条最短路径是非常困难??的。机器人每前进一步，会获得一些局部信息，根据所获得的局部信息判断下一步的移??动方向。由于信息不完备，所以很难
【参考文献】：
期刊论文
[1]基于八区域的简单多边形顶点凸凹性识别算法[J]. 薛理,杨树文,王中辉,张珊,马吉晶. 计算机应用与软件. 2018(01)
[2]判断点与多边形拓扑关系的改进算法[J]. 向俊,王静,夏幼明. 计算机工程与设计. 2014(05)
[3]利用极点顺序的多边形顶点凹凸性判别算法[J]. 赵军,张桂梅,曲仕茹. 工程图学学报. 2007(01)
硕士论文
[1]求图中受限制的所有最短路径算法的分析与研究[D]. 邓礼礼.华东师范大学 2009
本文编号：3510946
【文章来源】：大连海事大学辽宁省 211工程院校
【文章页数】：66 页
【学位级别】：硕士
【部分图文】：
图１．１艺术画廊问题的示例??Ｆｉｇ．?１．１?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ａｒｔ?ｇａｌｌｅｒｙ?ｐｒｏｂｌｅｍ??
?平面网格的高效探索策略研宄???图１．２巡视员路径问题的示例??Ｆｉｇ．?１．２?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ｗａｔｃｈｍａｎ?ｒｏｕｔｅ?ｐｒｏｂｌｅｍ??Ｏｎｌｉｎｅ问题［２］是指在边界信息未知的区域中进行的目标搜索或区域探索，因此该问??题可分为搜索问题和探索问题。探索任务一般都交由智能机器人完成，并假设机器人具??有３６０°的视角。搜索问题是指在区域中对一个或多个几何元素例如点、线、多边形等进??行搜索；探索问题一般是指对整个区域进行的探索，即对区域内的每个点进行遍历。搜??索问题可在边界信息己知的区域中进行，通常称之为ｏｆｆｌｉｎｅ搜索问题，也可在边界信息??未知的区域中进行，通常则称之为ｏｎｌｉｎｅ搜索问题。??Ｏｆｆｌｉｎｅ搜索问题是指机器人在己知搜索区域的完备几何信息的前提下对目标进行??的搜索，即机器人在搜索开始前，对起始点、搜索目标点、区域中间有无障碍物等几何??信息完全了解，是一种行为目标十分明确的搜索。Ｏｆｆｌｉｎｅ搜索问题的一个示例如图１．３??所示。??Ｓｈｏｒｔｅｓｔ?ｐａｄｉｌ??Ｍｍｉｒｍｉｍ?ｆｅｉｋ?ｐａｔｈ、＇汉１??ｓ??图１．３?Ｏｆｆｌｉｎｅ搜索问题的示例??Ｆｉｇ．?１．３?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ｔｈｅ?ｏｆｆｌｉｎｅ?ｓｅａｒｃｈ?ｐｒｏｂｌｅｍ??－２?－??
?大连海事大学专业学位硕士学位论文???在平面区域ｉ？中，给定起始点和目标点／，阴影部分表示障碍物，且己知该区域??的边界几何信息。机器人从起始点Ｓ出发，寻找到一条从Ｓ到ｆ的最短路径。由于机器??人事先完全掌握了该多边形区域的边界几何信息，所以机器人会从所有路径中选择一条??最短的遍历路径［３］，即图１．３中的实线路径，并沿这条最短路径搜索到目标点／。若要求??寻找一条从ｓ到／的路径，并要求路径具有最少的拐点，则机器人会选择图１．３中的虚??线路径，并沿这条路径对目标点／进行搜索。针对ｏｆｆｌｉｎｅ搜索问题所设计的搜索算法通??常称为ｏｆｆｌｉｎｅ搜索算法＋６］。??Ｏｎｌｉｎｅ搜索问题［７＿９］是指待搜索区域的几何信息未知，即机器人在搜索该区域之前，??只知道起始点、目标点、以及一些局部信息，对区域中间是否存在障碍物、搜索区域的??边界在哪里等几何信息完全不了解，在这种情形下所进行的搜索。Ｏｎｌｉｎｅ搜索问题的一??个示例如图１．４所示，在平面区域７？中，给定起始点５和目标点？，阴影部分表示障碍物，??但机器人只知道起始点ｘ和目标点〖等局部信息，为了搜索给定区域，机器人需要安装??感知系统，在收集搜索区域的局部几何信息的同时探索前进，动态地搜索目标点〖，最??终形成一条搜索路径，如图１．４中虚线所表示的路径。在图１．４中，实线表示机器人知??道该区域几何信息的前提下对目标点／进行搜索所走的最短路径。从图１．４可以看出，??在事先不知道搜索区域的几何信息时，要想找到问题所对应的一条最短路径是非常困难??的。机器人每前进一步，会获得一些局部信息，根据所获得的局部信息判断下一步的移??动方向。由于信息不完备，所以很难
【参考文献】：
期刊论文
[1]基于八区域的简单多边形顶点凸凹性识别算法[J]. 薛理,杨树文,王中辉,张珊,马吉晶. 计算机应用与软件. 2018(01)
[2]判断点与多边形拓扑关系的改进算法[J]. 向俊,王静,夏幼明. 计算机工程与设计. 2014(05)
[3]利用极点顺序的多边形顶点凹凸性判别算法[J]. 赵军,张桂梅,曲仕茹. 工程图学学报. 2007(01)
硕士论文
[1]求图中受限制的所有最短路径算法的分析与研究[D]. 邓礼礼.华东师范大学 2009
本文编号：3510946
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3510946.html
