發(fā)布時間：2018-01-08 14:33

  本文關(guān)鍵詞：未知區(qū)域中目標搜索的online算法研究　出處：《大連海事大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 計算幾何 目標搜索 online算法 機器人 競爭比

【摘要】：online搜索問題是計算幾何學(xué)、機器人學(xué)、算法學(xué)中的熱點研究問題,它不僅涉及動態(tài)搜索、最優(yōu)路徑規(guī)劃、算法設(shè)計與分析等基礎(chǔ)理論問題,還在危險區(qū)域撤離、機器人目標搜索、未知區(qū)域探索等領(lǐng)域有著廣泛的應(yīng)用。研究針對這類問題的簡潔、高效算法,不僅具有理論意義,而且還具有很大的實際應(yīng)用價值。盡管近年來online搜索問題的研究取得了一些優(yōu)秀的成果,但仍有很多經(jīng)典的開放性問題沒有解決,且一些成果還存在著效率沒達到最優(yōu)、限制條件多等問題。在此背景下,本文針對online搜索中三個具體問題,展開深入研究。首先是信息不完備的危險區(qū)域撤離問題。針對這一問題,本文分單人撤離和多人撤離兩種情況討論。在單人撤離情況中,提出了競爭比為13.812的對數(shù)螺線算法,且通過給出匹配的競爭比下界,證明了該算法是最優(yōu)的單調(diào)周期性算法。同時,將對數(shù)螺線單調(diào)周期性的性質(zhì)應(yīng)用在網(wǎng)格模型中,提出了競爭比為21的螺旋撤離算法。在多人撤離情況中,提出了一個新的等角撤離算法EES,給出了競爭比計算通式,并在分析算法競爭比的基礎(chǔ)上對分組方式做了進一步的優(yōu)化研究。其次,是最小感知能力機器人街道搜索問題。針對這一問題,本文提出了競爭比為9的最優(yōu)online搜索算法。該算法不僅在效率上有所提升,將競爭比從原有算法的11降低到現(xiàn)在的9,還去掉了機器人需要攜帶位置標記裝置及使用數(shù)據(jù)結(jié)構(gòu)S-GNT的限制。最后,是基于可視性的未知多邊形探索問題。針對這一問題,本文提出了一個競爭比為6.7的online探索算法。該算法通過將(?)倍的offline巡視員路徑近似算法online化,遞歸地探索多邊形中的兩類凹頂點,及合理地使用結(jié)構(gòu)角殼,將競爭比從原有算法的26.5降低到6.7,大幅提升了探索效率。本文提出的這些算法是相應(yīng)問題到目前為止的最優(yōu)解決方案。它們不僅解決了online搜索領(lǐng)域中的一些理論問題,還在危險區(qū)域撤離、機器人搜索、探索等領(lǐng)域中有著廣泛的應(yīng)用前景。
[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.
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP242

【相似文獻】

相關(guān)期刊論文 前3條

1 朱為;李國輝;;基于自動結(jié)構(gòu)延伸的圖像修補方法[J];自動化學(xué)報;2009年08期

2 ;娛樂在線[J];電腦技術(shù);2001年02期

3 ;[J];;年期

相關(guān)博士學(xué)位論文 前1條

1 魏琦;未知區(qū)域中目標搜索的online算法研究[D];大連海事大學(xué);2016年

相關(guān)碩士學(xué)位論文 前1條

1 楊仙魁;閉合型摳圖的研究與應(yīng)用[D];云南大學(xué);2013年

，

本文編號：1397514