未知区域中目标搜索的online算法研究

发布时间：2018-01-08 14:33

本文关键词：未知区域中目标搜索的online算法研究　出处：《大连海事大学》2016年博士论文　论文类型：学位论文

【摘要】：online搜索问题是计算几何学、机器人学、算法学中的热点研究问题,它不仅涉及动态搜索、最优路径规划、算法设计与分析等基础理论问题,还在危险区域撤离、机器人目标搜索、未知区域探索等领域有着广泛的应用。研究针对这类问题的简洁、高效算法,不仅具有理论意义,而且还具有很大的实际应用价值。尽管近年来online搜索问题的研究取得了一些优秀的成果,但仍有很多经典的开放性问题没有解决,且一些成果还存在着效率没达到最优、限制条件多等问题。在此背景下,本文针对online搜索中三个具体问题,展开深入研究。首先是信息不完备的危险区域撤离问题。针对这一问题,本文分单人撤离和多人撤离两种情况讨论。在单人撤离情况中,提出了竞争比为13.812的对数螺线算法,且通过给出匹配的竞争比下界,证明了该算法是最优的单调周期性算法。同时,将对数螺线单调周期性的性质应用在网格模型中,提出了竞争比为21的螺旋撤离算法。在多人撤离情况中,提出了一个新的等角撤离算法EES,给出了竞争比计算通式,并在分析算法竞争比的基础上对分组方式做了进一步的优化研究。其次,是最小感知能力机器人街道搜索问题。针对这一问题,本文提出了竞争比为9的最优online搜索算法。该算法不仅在效率上有所提升,将竞争比从原有算法的11降低到现在的9,还去掉了机器人需要携带位置标记装置及使用数据结构S-GNT的限制。最后,是基于可视性的未知多边形探索问题。针对这一问题,本文提出了一个竞争比为6.7的online探索算法。该算法通过将(?)倍的offline巡视员路径近似算法online化,递归地探索多边形中的两类凹顶点,及合理地使用结构角壳,将竞争比从原有算法的26.5降低到6.7,大幅提升了探索效率。本文提出的这些算法是相应问题到目前为止的最优解决方案。它们不仅解决了online搜索领域中的一些理论问题,还在危险区域撤离、机器人搜索、探索等领域中有着广泛的应用前景。
[Abstract]:Online search problem is a hot research problem in computational geometry robotics and algorithmology. It not only involves dynamic search optimal path planning algorithm design and analysis and other basic theoretical issues. It is also widely used in dangerous area evacuation, robot target search, unknown area exploration and so on. It is not only of theoretical significance to study the concise and efficient algorithm for this kind of problems. Although the research of online search problem has made some outstanding achievements in recent years, there are still many classical open problems that have not been solved. And there are still some problems such as efficiency is not optimal and restrictions are many. Under this background, this paper aims at three specific problems in online search. The first is the problem of evacuation of dangerous areas with incomplete information. In view of this problem, this paper discusses the two situations of single evacuation and multi-person evacuation. In the case of single-person evacuation. A logarithmic spiral algorithm with a competition ratio of 13.812 is proposed, and the lower bound of matching competitive ratio is given to prove that the algorithm is an optimal monotone periodic algorithm. The monotonic periodicity of logarithmic spiral is applied to the grid model, and a spiral evacuation algorithm with competitive ratio of 21 is proposed. In the case of multi-person evacuation, a new isometric evacuation algorithm, EES, is proposed. In this paper, the general formula of competition ratio is given, and on the basis of analyzing the competition ratio of algorithm, further optimization of grouping is studied. Secondly, the street search problem of robot with minimum perceptual ability is discussed. In this paper, an optimal online search algorithm with a competition ratio of 9 is proposed. This algorithm not only improves the efficiency, but also reduces the competition ratio from 11 to 9. It also removes the restrictions on the robot's need to carry position marking devices and use the data structure S-GNT. Finally, the problem of exploring unknown polygons based on visibility is proposed. In this paper, we propose a online exploration algorithm with a competition ratio of 6.7. The offline inspector path approximation algorithm online, recursively explores two types of concave vertices in the polygon, and reasonably uses the structural angular shell. Reduce the competition ratio from 26.5 to 6.7. These algorithms proposed in this paper are the optimal solutions to the corresponding problems so far. They not only solve some theoretical problems in the field of online search. It also has a wide application prospect in dangerous area evacuation, robot search, exploration and other fields.
【学位授予单位】：大连海事大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP242

【相似文献】