本文是一篇计算机论文范文,本文针对多机器人在未知多边形区域的撤离问题展开研究,机器人的搜索目标为区域边界上的未知出口,最终目的是使所有机器人从出口撤离该区域。在线撤离问题的研究,不仅可以丰富计算几何,理论算法等领域的理论知识,还在危险区域撤离、灾难搜救等实际场景中有着广泛的应用。
1绪论
1.1研究背景与意义
计算几何学从二十世纪七十年代兴起,作为计算机理论科学的一个重要分支,受到国内外研究人员的广泛关注[1]。近年来,随着社会科学技术的发展,机器代替人工的现象变得越来越普遍。人们习惯把危险性高,机械性强的工作都交给机器人来实现。但是机器人在面对复杂的工作环境时,研究人员往往不能直接为其设计出高效算法。而计算几何是将复杂的问题抽象成简单的几何模型,通过对几何模型特性的分析,从而快速的求解算法[2,3]。因此,计算几何学在机器人领域具有广泛应用。
搜索问题[4-6]作为计算几何学和机器人学中的基本问题,是指通过单个或多个机器人对某个特定的区域进行搜索,搜索目标可以为区域中的某个点、线或者边界等。根据对搜索区域几何信息的掌握情况,将搜索问题分为:离线搜索问题和在线搜索问题。如果机器人在执行搜索任务时,事先已经掌握搜索区域的全部信息,包括起始点、目标点、区域中有无障碍物及障碍物位置点等,机器人可以根据已知信息,选择一条最优路径到达目标位置,这类问题被称为离线搜索问题。
1.2国内外研究现状
近年来,地震、城市火灾、交通事故等突发性灾害频繁发生,对人类的生命安全造成巨大威胁。当灾难发生后,如何快速地将被困人员撤离危险区域是人们普遍关心的问题。由于灾难的突发性和未知性,搜救过程中对危险区域信息的掌握往往是不全面的,甚至是完全未知的,因此该问题引起了计算几何学和机器人领域的广泛研究关注[23,24]。
撤离问题在研究学者不断地探索中也取得了诸多成果。2002年,Hamacher[25]等人对宏观和微观撤离模型的差异进行描述,并说明了撤离研究的实际应用价值。在早期的研究中,从构建集中式撤离计划的角度,研究了网格多边形的撤离问题,2008年,Chen[26]等人采用系统仿真方法比较了三种不同网格的撤离效率,为后续研究提供思路。2010年,Fekete[27]等人将问题具体化,研究了从直线网格多边形环境中尽可能快的撤离问题。2013年,Xu[28]等人提出了多组机器人从平面凸区域撤离算法,在此算法中,机器人到达边界就代表撤离成功,并给出了下界为3。随后,Tan和Wei[29]又对该问题做出新的优化和改进,将“双倍策略”引用到二维平面的撤离问题上,提出半圆撤离算法。2014年,Czyzowicz[30]等人首次提出机器人在圆盘上搜索未知出口并撤离的问题,将出口设置在圆盘边界,通过机器人之间的协作,搜索出口并撤离。同时提出将机器人的通信类型分为两类:无线通信类型和面对面通信类型。在无线通信模式下,机器人可以在任何时间点进行通信,一旦其中一个机器人发现出口,可以立即将出口的位置通知给其它机器人;
2相关基础知识
2.1计算几何概述
计算几何学[48-50]自二十世纪七十年代末从算法设计与分析中独立出来,就受到了各领域研究学者的广泛关注。1972年,计算几何学被正式定义为研究几何模型和数据处理的学科,其主要研究内容是探讨几何形体的计算机表示、分析和综合,研究的重点在于“渐进且快速的精准求解算法”。
计算几何学不仅属于数学分支,同时也作为计算机理论科学的一个重要分支,研究怎样灵活、有效地建立几何形体的数学模型以及在计算机中更好地储存和管理这些模型数据。随着计算机的出现,许多繁琐的问题得到解决,但是还有一些看似容易的问题,在计算机的处理上却需要设计出一套十分复杂的解决方案,如几何问题。而计算几何的特点在于将实际生活中难以解决的问题,通过几何建模的方式,从而分析研究出高效的解决办法。因此,计算几何产生的一系列重要研究成果,在众多实际领域中也具有广泛应用。例如,计算机图形学、机器人学、地理信息系统、模式识别、统计分析、CAD/CAM、计算机流体动力学、图像处理、计算机视觉等。
计算几何学的目标之一就是提供在应用领域建立解决方案时所需要的几何要素。计算几何学呈现出几何化、图形化、代数化的发展趋势,涉及的内容也十分广泛,如点、线、集合、多边形等基础知识,还包含了几何算法(如线性规划、画廊看守、三角剖分),几何结构(如区域树、区间树、排列),其次还有数据结构中最短路径查找等[51]。计算几何可以帮助人们解决存在的问题,未来依然会不断发展与进步,在实际生活中具有广阔的应用和发展空间。
2.2基本定义与性质
为了方便描述,本节给出了所涉及的计算几何相关概念和基本性质。
定义2.2.1:平面上若存在三条或三条以上的线段,使得线段间的首尾相连形成一个闭合区域,则称该区域为一个多边形。
定义2.2.2:多边形若满足封闭不自交的条件,则称为简单多边形。其中,首尾相接的线段称为简单多边形的边界。
定义2.2.3:在二维平面内各边相等,各角也相等的简单多边形,称为正多边形。
定义2.2.4:连接正多边形位于两条不同边界上的任意两点的线段称为弦。
如图2.1所示,图2.1(a)为简单多边形,图2.1(b)为非简单多边形,图2.1(c)为正多边形。简单多边形的区域是封闭的,若一个多边形内包含另一个多边形,则被包含的多边形称为“洞”且称该多边形为带“洞”多边形,本研究中不考虑带“洞”多边形。在后续研究中提到的多边形指的是具有对称性的正多边形。平面区域指的是被多边形边界包围,具有可测量性的内部区域。在多边形中弦长的计算使用余弦定理。
3 无线通信机器人从正六边形区域在线撤离算法 ..................... 18
3.1 模型描述 ..................... 18
3.2 两个机器人从正六边形区域在线撤离算法 ........... 19
3 无线通信机器人从正六边形区域在线撤离算法 .............................. 18
3.1 模型描述 ................................... 18
3.2 两个机器人从正六边形区域在线撤离算法 ....................... 19
5 总结与展望............................... 57
5.1 总结 ............................. 57
5.2 展望 ......................... 57
4速度可变机器人从圆形区域在线撤离算法
4.1模型描述
将机器人的搜索区域抽象为一个封闭的圆形,记为P,半径为1。出口位于其边界上的未知位置,记为e。机器人被圆形搜索区域的边界包围,只能从位于其边界上的出口离开。
在搜索区域中,机器人可以随时移动、停止、转弯和切换方向,同时还可以处理信息和执行算法,但是只有在到达边界上的未知出口点时,才能识别出口位置。机器人可以向区域中的任何选定点移动,可达到的最大速度为1。如前所述,机器人的基本搜索能力与第3章相同,区别在于本章为机器人新增加一个被动的辅助工具,在后续的研究中被称为自行车。自行车的作用是帮助机器人提升移动速度,使用自行车的机器人可以将最大移动速度达到v(v>1)。自行车可以随时被放置在区域内的任何位置,但不具备自主移动、搜索、定位和识别能力,只能辅助机器人加速,并且一辆自行车不能同时被多个机器人使用,只有当驾驶自行车的机器人释放自行车后,另一个机器人才可以继续使用。因此,机器人在工作中会有两种状态:驾驶状态和行走状态。驾驶状态下,机器人的最大速度为v(v>1);行走状态下,机器人的最大速度为1。机器人只有在到达自行车的停放点时,才能识别自行车的存在。机器人可以计算和定位自身位置,同时识别出口和自行车。由于机器人速度发生变化,在撤离问题研究中机器人的情况会更加复杂多变,即使是小基数的机器人数量,仍然存在着极大挑战。
5总结与展望
5.1总结
本文针对多机器人从简单多边形区域在线撤离问题展开研究。主要的研究工作包括如下几个方面:
(1)论述了与本文研究相关的计算几何基础知识,通过分析国内外的研究现状,总结了撤离问题的研究特点。并在现有研究问题的基础上,提出了本文的研究内容,阐述了在线撤离问题理论和实际应用的意义和价值。
(2)针对机器人撤离区域的问题。在原有撤离模型(圆形、三角形、正方形)的基础上,提出正六边形区域的撤离模型,在无线通信模式下,将机器人数量划分为两个和2k(k>1)个分别展开研究。
(3)针对速度可变机器人的撤离问题。在撤离过程中,机器人借助变速辅助工具改变自身速度。在机器人速度可交换的前提下,将撤离区域设定为圆形,分别设计了机器人在两种通信模式下的撤离算法。在无线通信模式下,给出了两个机器人从未知出口撤离的多项式结果并分析下界。通过算法效率分析发现,算法中慢速机器人先发现出口的实例与下界相匹配,进而证明了该算法的高效性。在面对面通信模式下,阐述了机器人之间的相遇规则,设计相应的撤离算法,分情况对算法效率进行具体分析。结合实际情况,骑车和步行之间的实际速度差距大概在三倍到七倍之间,假设将机器人的速度比设置为1:7,在无线通信模式下撤离开销约为1.5630,而面对面通信模式下撤离开销则近似为1.8081。
参考文献(略)