未知多邊形遍歷問題不僅涉及算法設(shè)計(jì)與分析、計(jì)算幾何、路徑規(guī)劃等基礎(chǔ)理論問題,也是解決游戲產(chǎn)業(yè)、未知區(qū)域搜救等領(lǐng)域?qū)嶋H問題的基礎(chǔ)。因此,本課題的研究,兼具理論意義和實(shí)用價(jià)值。本文針對(duì)未知多邊形遍歷問題以及網(wǎng)格撤離問題進(jìn)行了研究,首先研究了與求解問題相關(guān)的基礎(chǔ)知識(shí),如點(diǎn)與多邊形位置關(guān)系的判定、求解給定兩點(diǎn)界定的圓弧、競爭比的分析方法等,然后分析了與課題相關(guān)的已有算法,如直線搜索問題的雙倍策略、√2倍巡邏員路徑近似算法、競爭比為26.5的未知多邊形遍歷算法,以及競爭比為21的網(wǎng)格單組撤離策略等,并指出部分算法的不足之處。在此基礎(chǔ)上,詳細(xì)研究了競爭比為6.7的未知多邊形遍歷算法并對(duì)其進(jìn)行了編程實(shí)現(xiàn),通過比較實(shí)驗(yàn)結(jié)果和理論結(jié)果,驗(yàn)證了算法的有效性。同時(shí),提出了解決單源點(diǎn)兩組撤離問題與多源點(diǎn)撤離問題的撤離算法,證明了單源點(diǎn)兩組撤離策略以及多源點(diǎn)撤離策略不僅適用于危險(xiǎn)區(qū)域是凸多邊形的情形,而且也適用于受災(zāi)區(qū)域是非凸多邊形的情形,并分別計(jì)算出了每個(gè)算法的競爭比。
【學(xué)位單位】：大連海事大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類】：TP301.6
【部分圖文】：

簡單多邊形（可看成是巡視員要巡視的區(qū)域）中，巡視員從起點(diǎn)ｓ出發(fā)，在多邊形中逡逑巡視一周后回到點(diǎn)＾要求在巡視過程中必須檢查到相應(yīng)簡單多邊形內(nèi)的任意一逡逑點(diǎn)，且所走的路徑長度最短。圖１．１給出該問題的一個(gè)示意圖，其中粗實(shí)線表示簡逡逑單多邊形的邊界，細(xì)實(shí)線是巡視員行走的路線，虛線是為保證巡視員能夠看到多逡逑邊形中任意一點(diǎn)的一個(gè)控制位置。顯然，由于要求巡視員所走的路徑長度最小化，逡逑所以巡視員的路徑應(yīng)該位于所有虛線以及部分多邊形邊界所圍成的區(qū)域內(nèi)，且不逡逑可能自交。另外，起點(diǎn)ｓ既可以在多邊形的內(nèi)部，也可以在其邊界上，但不能在多逡逑邊形的外部。巡視員路徑問題也稱為多邊形搜索問題。逡逑圖１．１巡視員路徑問題的示例逡逑Ｆｉｇ．邋１．１邋Ａｎ邋ｅｘａｍｐｌｅ邋ｏｆ邋ｔｈｅ邋ｗａｔｃｈｍａｎ邋ｒｏｕｔｅ邋ｐｒｏｂｌｅｍ逡逑計(jì)算幾何學(xué)領(lǐng)域的搜索問題通常包括在某搜索區(qū)域范圍內(nèi)搜索某一個(gè)點(diǎn)，或逡逑某條線段，或某未知區(qū)域的邊界等。根據(jù)搜索區(qū)域邊界信息是否己知，又將這類逡逑搜索問題分為兩種：當(dāng)搜索區(qū)域邊界信息己知時(shí)，稱其為多邊形搜索或ｏｆｆｌｉｎｅ搜逡逑索問題；否則

逑中，機(jī)器人的搜索能力是具有３６０°的視覺，或者具有“看見”搜索目標(biāo)或障礙物的逡逑能力。例如，在圖１．２（ａ）中，區(qū)域八圖中沒有給出具體邊界的幾何形狀）中有點(diǎn)ｓ逡逑和點(diǎn)／，陰影區(qū)域?yàn)槲挥冢兄械恼系K物，機(jī)器人以點(diǎn)？為搜索目標(biāo)，從ｓ出發(fā)進(jìn)行逡逑搜索。由于機(jī)器人在行動(dòng)前已經(jīng)掌握了邋Ｐ的幾何信息，如邊界、各障礙物以及目逡逑標(biāo)點(diǎn)／的位置等信息，所以機(jī)器人可計(jì)算出一條從ｓ到／的最優(yōu)路徑［４４］，并沿著最逡逑優(yōu)路徑找到目標(biāo)點(diǎn)〖，其中，實(shí)線表示路徑長度最短的搜索路徑，而虛線則表示拐逡逑彎最少的搜索路徑（同一個(gè)問題可能有不同的擇優(yōu)標(biāo)準(zhǔn)）。獲取這類路徑的策略稱為逡逑ｏｆｆｌｉｎｅ搜索算法。逡逑（i瞬汀㈠危蟆駑危掊義希�、广逦＼逦／辶x希印瑁苠澹恚椋殄濉埃睿螅穡幔簦楨危苠危洌瑁酰穡幔簦楨義希皺澹皺義希ǎ幔╁危ǎ猓╁義賢跡保插澹ǎ幔┳疃搪肪逗妥釕僮勐肪叮ǎ猓┳疃搪肪逗突魅寺肪跺義希疲椋紓澹保插澹ǎ幔╁澹裕瑁邋澹螅瑁錚潁簦澹螅翦澹穡幔簦楨澹幔睿溴澹恚椋睿椋恚酰礤澹簦酰潁睿椋睿玨澹穡幔簦楨澹ǎ猓╁澹裕瑁邋澹螅瑁錚潁簦澹螅翦澹穡幔簦楨澹幔睿溴澹錚睿歟椋睿邋澹穡幔簦楨義系牽北囈緇蛘習(xí)錛澳勘甑男畔⑽粗�，机器人要諛I(yè)階鈑怕肪鍛清義俠訓(xùn)模蠖嗍榭魷祿?dān)器冉z贍芴剿韉揭惶醣茸鈑怕肪兌安睢保ǔざ雀せ虺殺懼義細(xì)螅┑穆肪�。灾q飫轡侍庵

本文編號(hào)：2834977