平面網格多邊形的探索問題是典型的online探索問題。本文主要對平面區(qū)域中邊界幾何信息未知的網格多邊形探索問題進行研究。關于該問題的研究,不僅涉及到計算幾何、數(shù)學等領域的相關理論知識,而且涉及到未知危險區(qū)域撤離、搜救、游戲產業(yè)、機器人路徑規(guī)劃等實際應用問題的求解,所以具有理論和實際兩方面的研究價值。網格多邊形的探索問題可描述為:給定平面上一個網格區(qū)域和一個邊界信息未知的多邊形P以及與邊界相鄰的起始位置s,機器人從s出發(fā),探索P內所有單元格后返回到s,完成對整個網格多邊形的探索。研究的目標是要找到一個探索策略以優(yōu)化機器人的探索路徑,縮短探索時間。本文基于以下假設進行研究:一是機器人在初始狀態(tài)不了解探索區(qū)域的幾何信息;二是機器人具有一定的記憶功能,且能夠跟隨探索過程存儲相關信息。本文在論述網格多邊形中內部單元格、外部單元格、分割單元格、探索策略的競爭比等相關概念的基礎上,分析了網格探索問題的深度優(yōu)先搜索算法和改進的深度優(yōu)先搜索算法,針對探索路徑過長導致探索效率較低的問題,提出了本文的改進方法,設計出了 optDFS探索算法并分析了該算法的競爭比。最后,使用Python語言實現(xiàn)了 optDF... 

【文章來源】：大連海事大學遼寧省 211工程院校

【文章頁數(shù)】：66 頁

【學位級別】：碩士

【部分圖文】：

圖１．１藝術畫廊問題的示例??Ｆｉｇ．?１．１?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ａｒｔ?ｇａｌｌｅｒｙ?ｐｒｏｂｌｅｍ??

?平面網格的高效探索策略研宄???圖１．２巡視員路徑問題的示例??Ｆｉｇ．?１．２?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ｗａｔｃｈｍａｎ?ｒｏｕｔｅ?ｐｒｏｂｌｅｍ??Ｏｎｌｉｎｅ問題［２］是指在邊界信息未知的區(qū)域中進行的目標搜索或區(qū)域探索，因此該問??題可分為搜索問題和探索問題。探索任務一般都交由智能機器人完成，并假設機器人具??有３６０°的視角。搜索問題是指在區(qū)域中對一個或多個幾何元素例如點、線、多邊形等進??行搜索；探索問題一般是指對整個區(qū)域進行的探索，即對區(qū)域內的每個點進行遍歷。搜??索問題可在邊界信息己知的區(qū)域中進行，通常稱之為ｏｆｆｌｉｎｅ搜索問題，也可在邊界信息??未知的區(qū)域中進行，通常則稱之為ｏｎｌｉｎｅ搜索問題。??Ｏｆｆｌｉｎｅ搜索問題是指機器人在己知搜索區(qū)域的完備幾何信息的前提下對目標進行??的搜索，即機器人在搜索開始前，對起始點、搜索目標點、區(qū)域中間有無障礙物等幾何??信息完全了解，是一種行為目標十分明確的搜索。Ｏｆｆｌｉｎｅ搜索問題的一個示例如圖１．３??所示。??Ｓｈｏｒｔｅｓｔ?ｐａｄｉｌ??Ｍｍｉｒｍｉｍ?ｆｅｉｋ?ｐａｔｈ、＇漢１??ｓ??圖１．３?Ｏｆｆｌｉｎｅ搜索問題的示例??Ｆｉｇ．?１．３?Ａｎ?ｅｘａｍｐｌｅ?ｏｆ?ｔｈｅ?ｏｆｆｌｉｎｅ?ｓｅａｒｃｈ?ｐｒｏｂｌｅｍ??－２?－??

?大連海事大學專業(yè)學位碩士學位論文???在平面區(qū)域ｉ？中，給定起始點和目標點／，陰影部分表示障礙物，且己知該區(qū)域??的邊界幾何信息。機器人從起始點Ｓ出發(fā)，尋找到一條從Ｓ到ｆ的最短路徑。由于機器??人事先完全掌握了該多邊形區(qū)域的邊界幾何信息，所以機器人會從所有路徑中選擇一條??最短的遍歷路徑［３］，即圖１．３中的實線路徑，并沿這條最短路徑搜索到目標點／。若要求??尋找一條從ｓ到／的路徑，并要求路徑具有最少的拐點，則機器人會選擇圖１．３中的虛??線路徑，并沿這條路徑對目標點／進行搜索。針對ｏｆｆｌｉｎｅ搜索問題所設計的搜索算法通??常稱為ｏｆｆｌｉｎｅ搜索算法＋６］。??Ｏｎｌｉｎｅ搜索問題［７＿９］是指待搜索區(qū)域的幾何信息未知，即機器人在搜索該區(qū)域之前，??只知道起始點、目標點、以及一些局部信息，對區(qū)域中間是否存在障礙物、搜索區(qū)域的??邊界在哪里等幾何信息完全不了解，在這種情形下所進行的搜索。Ｏｎｌｉｎｅ搜索問題的一??個示例如圖１．４所示，在平面區(qū)域７？中，給定起始點５和目標點？，陰影部分表示障礙物，??但機器人只知道起始點ｘ和目標點〖等局部信息，為了搜索給定區(qū)域，機器人需要安裝??感知系統(tǒng)，在收集搜索區(qū)域的局部幾何信息的同時探索前進，動態(tài)地搜索目標點〖，最??終形成一條搜索路徑，如圖１．４中虛線所表示的路徑。在圖１．４中，實線表示機器人知??道該區(qū)域幾何信息的前提下對目標點／進行搜索所走的最短路徑。從圖１．４可以看出，??在事先不知道搜索區(qū)域的幾何信息時，要想找到問題所對應的一條最短路徑是非常困難??的。機器人每前進一步，會獲得一些局部信息，根據(jù)所獲得的局部信息判斷下一步的移??動方向。由于信息不完備，所以很難

【參考文獻】：
期刊論文
[1]基于八區(qū)域的簡單多邊形頂點凸凹性識別算法[J]. 薛理,楊樹文,王中輝,張珊,馬吉晶.  計算機應用與軟件. 2018(01)
[2]判斷點與多邊形拓撲關系的改進算法[J]. 向俊,王靜,夏幼明.  計算機工程與設計. 2014(05)
[3]利用極點順序的多邊形頂點凹凸性判別算法[J]. 趙軍,張桂梅,曲仕茹.  工程圖學學報. 2007(01)

碩士論文
[1]求圖中受限制的所有最短路徑算法的分析與研究[D]. 鄧禮禮.華東師范大學 2009



本文編號：3510946