《基于Dijkstra算法的清掃機(jī)器人最短路徑規(guī)劃及仿真實(shí)現(xiàn)》8600字（論文）

基于Dijkstra算法的清掃機(jī)器人最短路徑規(guī)劃及仿真實(shí)現(xiàn)摘要隨著如今時(shí)代的快速發(fā)展，信息時(shí)代的來(lái)臨，電能和機(jī)械已經(jīng)離不開(kāi)我們的日常，無(wú)論是哪種行業(yè)，都已經(jīng)離不開(kāi)機(jī)械的輔助。清掃機(jī)器人是能夠代替人力進(jìn)行人們?nèi)粘Ｋ璧沫h(huán)境清理的一種機(jī)器，只需消耗一定的電能，就能代替人力完成煩雜的清掃任務(wù)。清掃機(jī)器人的路徑規(guī)劃是清掃機(jī)器人要求解的核心問(wèn)題，其目的在于尋求無(wú)碰撞最優(yōu)路徑。Dijkstra算法是一種經(jīng)典的求解最優(yōu)路徑的算法，計(jì)算一個(gè)頂點(diǎn)到其余各個(gè)頂點(diǎn)的最小移動(dòng)代價(jià)，可解決清掃機(jī)器人運(yùn)行路徑的問(wèn)題。本文設(shè)計(jì)實(shí)現(xiàn)了基于Dijkstra算法的清掃機(jī)器人的最短路徑規(guī)劃，計(jì)算較為復(fù)雜的地形，規(guī)劃其最佳路徑，并進(jìn)行仿真實(shí)現(xiàn)。關(guān)鍵詞：清掃機(jī)器人；路徑規(guī)劃；最優(yōu)路徑；Dijkstra算法 目錄 TOC\o"1-3"\h\u1緒論 51.1課題研究背景及意義 51.2國(guó)內(nèi)外研究現(xiàn)狀 61.3課題研究的主要內(nèi)容及組織結(jié)構(gòu) 72開(kāi)發(fā)軟件簡(jiǎn)述 82.1python 82.2PythonIDLE 82.3Pycharm 93Dijkstra算法 103.1Dijkstra算法的基本原理 103.2Dijkstra算法原理的圖解 103.3Dijkstra算法的優(yōu)缺點(diǎn) 134基于Dijkstra算法的清掃機(jī)器人最短路徑規(guī)劃的設(shè)計(jì) 144.1搜尋路徑的目標(biāo)效果 144.2開(kāi)始位置、目標(biāo)位置、地圖創(chuàng)建 154.3地圖的初始化和障礙物的設(shè)置 164.4機(jī)器人的運(yùn)動(dòng)方式以及柵格編號(hào) 174.4.1機(jī)器人運(yùn)動(dòng)方式 174.4.2柵格編號(hào) 184.5搜尋路徑 194.5.1搜尋流程 194.5.2判斷邊界、障礙物 204.6獲得最短路徑 205仿真實(shí)現(xiàn) 226總結(jié)與展望 24參考文獻(xiàn) 251緒論1.1課題研究背景及意義用于生產(chǎn)的第一臺(tái)機(jī)器人是在1959年由恩格爾伯格發(fā)明的，機(jī)器人這一新事物就逐漸成為科研人員研究的焦點(diǎn)[1]。尤其是隨著科學(xué)的逐漸發(fā)展，人工智能行業(yè)的不斷更新，機(jī)器人的重要性早已經(jīng)發(fā)展成為人們生活中必不可少的一部分。世界上逐漸涌現(xiàn)出許多不同類型的機(jī)器人，比如應(yīng)用于AI的機(jī)器人，服務(wù)于清潔機(jī)器人，工業(yè)領(lǐng)域的機(jī)器人，可以進(jìn)行運(yùn)輸?shù)臋C(jī)器人，在水下作業(yè)的機(jī)器人，目前，人們研究機(jī)器人的方向被分為三個(gè)部分：構(gòu)建機(jī)器人周圍環(huán)境的地圖、規(guī)劃?rùn)C(jī)器人最短路徑、搜索和導(dǎo)航機(jī)器人行動(dòng)軌跡。1960年代后期，斯坦福的研究所開(kāi)發(fā)出了能自己移動(dòng)的機(jī)器人[1]。研究所表明，機(jī)器人的最短移動(dòng)路徑問(wèn)題，是機(jī)器人最為核心的問(wèn)題關(guān)鍵所在。在機(jī)器人的工作系統(tǒng)中，尋找從開(kāi)始位置到目的地位置的最佳無(wú)碰撞行動(dòng)路線。到了現(xiàn)代，清掃機(jī)器人的路徑規(guī)劃問(wèn)題可以說(shuō)是如今研究機(jī)器人的領(lǐng)域之中，最為核心的一個(gè)研究方向。路徑的規(guī)劃問(wèn)題，它的本質(zhì)就是對(duì)計(jì)算出清掃機(jī)器人最短路徑的算法的一個(gè)研究問(wèn)題。尤其是近幾年來(lái)，隨著互聯(lián)網(wǎng)+的時(shí)代來(lái)臨，國(guó)內(nèi)外大量的學(xué)者專家對(duì)于機(jī)器的能源消耗最佳化的要求頗為急切。對(duì)于清掃機(jī)器人的最短路徑的規(guī)劃，也是最為直接的減少能源消耗的途徑之一。有很多可以應(yīng)用的規(guī)劃路徑，因?yàn)樗麄兊膬?yōu)缺點(diǎn)的原因應(yīng)用的領(lǐng)域范圍也不同。根據(jù)不同領(lǐng)域的通路規(guī)劃運(yùn)算法則研究，按照不同的運(yùn)算法則和運(yùn)算法則的基本原理，運(yùn)算法則大致可分為四大類:現(xiàn)有的運(yùn)算法則、圖形方法、智能生物工程運(yùn)算法則和其他運(yùn)算法則[2]。Dijkstra算法應(yīng)用研究，將它應(yīng)用到我們?nèi)粘Ｉ畹母鱾€(gè)部分，包括機(jī)器人的移動(dòng)路徑、農(nóng)產(chǎn)品流通和城市運(yùn)輸系統(tǒng)等。如果是給定的乳腺圖示，則應(yīng)該用傳統(tǒng)的Dijkstra算法適當(dāng)?shù)匦薷囊粋€(gè)決定起點(diǎn)和終點(diǎn)之間最短路徑的問(wèn)題，讓終點(diǎn)立即顯示出來(lái)，并使之達(dá)到最短距離并輸出各種存在的最短路徑對(duì)于給定了一個(gè)有向圖,確定起始點(diǎn)和結(jié)束點(diǎn)的最短路徑問(wèn)題，必須對(duì)Dijkstra算法做出適當(dāng)?shù)母淖?當(dāng)他搜尋的路徑一旦到達(dá)最終標(biāo)記的地點(diǎn)，就立即結(jié)束尋找,然后計(jì)算出開(kāi)始點(diǎn)和最終點(diǎn)之間的最佳距離，并且輸出。1.2國(guó)內(nèi)外研究現(xiàn)狀清掃機(jī)器人是一種家庭服務(wù)機(jī)器人，目前清掃機(jī)器人是使用最廣泛的服務(wù)機(jī)器人類型。機(jī)器人多用于清潔室內(nèi)地板，特別是在住宅、酒店、辦公樓和其他地方。人們想要除去重復(fù)的、乏味的清潔工作，所以利用這個(gè)機(jī)器人就會(huì)達(dá)到人們的理想。清掃機(jī)器人的研究始于20世紀(jì)80年代。經(jīng)過(guò)30多年的開(kāi)發(fā)，國(guó)內(nèi)外開(kāi)發(fā)出了很多產(chǎn)品，在市場(chǎng)上取得了巨大成功。從技術(shù)角度來(lái)說(shuō)，清掃機(jī)器人包含人工智能、電子技術(shù)、數(shù)學(xué)和機(jī)械設(shè)計(jì)等主題。它具有很強(qiáng)的實(shí)用性和自主性，集成了知識(shí)的各個(gè)方面。清掃機(jī)器人的工作環(huán)境通常是一個(gè)封閉的內(nèi)部房間，需要足夠的智能來(lái)檢測(cè)周圍的環(huán)境，并獨(dú)立進(jìn)行路徑規(guī)劃和完成清潔。有必要以較低的重復(fù)率完成整個(gè)區(qū)域的清理工作。因此需要一種能夠?qū)崟r(shí)的計(jì)算出最短路徑的計(jì)算機(jī)算法，而Dijkstra算法就是其中一種可以滿足這些需求的算法，當(dāng)室內(nèi)出現(xiàn)了需要清潔的污垢，系統(tǒng)可以自主的計(jì)算出最短的最佳路徑，然后控制清掃機(jī)器人來(lái)到目標(biāo)地區(qū)進(jìn)行清潔。Dijkstra算法是E.W.Dijkstra在1959年提出的，也被稱為Dijkstra算法[11]。他使用了一個(gè)貪心算法，現(xiàn)在被認(rèn)為是最快的方法。最短路徑的計(jì)算方法分為最短路徑的靜態(tài)計(jì)算和最短路徑的動(dòng)態(tài)計(jì)算。靜態(tài)最短路徑算法被設(shè)計(jì)成在不改變外部環(huán)境的情況下計(jì)算最短路徑。它主要是迪杰斯特拉算法和A*(AStar)算法。動(dòng)態(tài)路徑的最短途徑是指，持續(xù)變化的外部環(huán)境如果預(yù)測(cè)不能如期進(jìn)行，則計(jì)算出最短途徑。例如當(dāng)敵人或障礙物持續(xù)運(yùn)動(dòng)的時(shí)候。Dijkstra的算法解決了從一個(gè)來(lái)源到另一個(gè)頂點(diǎn)的最短路徑問(wèn)題。它的主要特征是從一開(kāi)始就使用貪心的算法，每次它轉(zhuǎn)向接近起點(diǎn)的鄰近節(jié)點(diǎn)時(shí)，最接近起點(diǎn)的節(jié)點(diǎn)直到到達(dá)終點(diǎn)才被訪問(wèn)。迪杰斯特拉算法基本應(yīng)用于最短路徑方向研究的。在許多工作流程中，具體的內(nèi)容他以簡(jiǎn)明概要，主要是關(guān)于數(shù)據(jù)的結(jié)構(gòu)、圖表方面的理論、運(yùn)行過(guò)程中數(shù)據(jù)的研究。特別值得令人注意的是此算法不需要對(duì)圖形的負(fù)加權(quán)邊不做特別的研究規(guī)劃。經(jīng)過(guò)這么多年來(lái)國(guó)內(nèi)外學(xué)者的研究發(fā)現(xiàn)，最短路徑的算法除了Dijkstra算法之外，還產(chǎn)生出了許多不同的算法，簡(jiǎn)單的列舉出幾種類型：Floyd運(yùn)算法則(亦稱擴(kuò)散)是一種運(yùn)用動(dòng)態(tài)程序設(shè)計(jì)的運(yùn)算法則，以在給定的權(quán)重圖表中找到各源之間的最佳路徑。使用動(dòng)態(tài)編程算法來(lái)查找給定的最佳路徑它的名字取自它的創(chuàng)始人之一RobertFreud[12],他是在1978年TuringAward獲獎(jiǎng)?wù)吆蚐tanfordUniversity計(jì)算機(jī)科學(xué)學(xué)院的教授級(jí)別大師。動(dòng)態(tài)的編程算法是描述Floyd算法的重要特征。與Dijkstra的算法相似核心的想法是在兩個(gè)頂點(diǎn)之間插入一個(gè)或多個(gè)通過(guò)點(diǎn)，通過(guò)更短的通過(guò)點(diǎn)和不通過(guò)的距離進(jìn)行比較。同時(shí)，相鄰方陣中必須有兩個(gè)D字行，利用已知條件計(jì)算相鄰點(diǎn)之間的距離就是通過(guò)它來(lái)完成的，第二矩陣P是被稱之為中間節(jié)點(diǎn)k的數(shù)值。Bellman-Ford算法通過(guò)反復(fù)迭代，反復(fù)調(diào)整邊緣設(shè)備E的各個(gè)位置，使從調(diào)試點(diǎn)到彼此頂點(diǎn)u∈V的最短路徑推定數(shù)逐漸接近最短距離。Bellman-Ford算法并不超過(guò)n-1。每一個(gè)步驟都需要在圖表的邊緣進(jìn)行改進(jìn)。完成第一個(gè)等級(jí)k后，從起點(diǎn)到最邊緣查找最短的路徑。n-1階段結(jié)束后，最短的路線是從起點(diǎn)到終點(diǎn)。不包含循環(huán)葫蘆的直接前往。因此通過(guò)n-1個(gè)邊緣獲得的最短途徑是源代碼。從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的最短路徑的特定值。SPFA算法是解決單源代碼最短路徑問(wèn)題的算法?？梢栽趫D表中使用V-1放松，以便獲得所有可能的最佳路勁方案。和迪杰斯特拉的算法相比，優(yōu)點(diǎn)是邊的權(quán)重值可能是負(fù)數(shù)，并且很容易體現(xiàn)出來(lái)。他的缺點(diǎn)更復(fù)雜，時(shí)間復(fù)雜性更高。但算法可以通過(guò)各種方式優(yōu)化來(lái)提高效率。算法的思路：使用dis圖來(lái)記錄每個(gè)節(jié)點(diǎn)的給定值，并使用相鄰列表或相鄰行列保存圖表G。實(shí)時(shí)動(dòng)態(tài)近似模擬法是本算法主要運(yùn)用的方法:規(guī)則規(guī)定為“先進(jìn)先出”。為了支持優(yōu)化節(jié)點(diǎn)，第一個(gè)u節(jié)點(diǎn)每次都從隊(duì)列中移除，預(yù)留的工作使用當(dāng)前規(guī)劃值，在最短的路徑點(diǎn)優(yōu)化。當(dāng)啟動(dòng)過(guò)程中最短端口改變時(shí)，v端口現(xiàn)在不在隊(duì)列中。就會(huì)指定u節(jié)點(diǎn)v。就會(huì)安排點(diǎn)v在隊(duì)列后面。因此節(jié)點(diǎn)不斷從隊(duì)列中移除，所以一直到隊(duì)列空為止都會(huì)一直執(zhí)行松弛操作。1.3專題研究的主要內(nèi)容和組織架構(gòu)本論文主要是以Dijkstra算法為核心，著重研究清掃機(jī)器人的最短路徑的規(guī)劃和仿真實(shí)現(xiàn)。將Dijkstra算法的基本原理，與清掃機(jī)器人的最短路徑問(wèn)題相結(jié)合，先模擬出清掃機(jī)器人工作地區(qū)的地圖、障礙物和目標(biāo)地點(diǎn)，再逐步將搜尋路徑仿真出來(lái)，最終計(jì)算出清掃機(jī)器人的最佳最短路徑。第一章緒論，這一章概述了Dijkstra算法和清掃機(jī)器人的背景以及意義，簡(jiǎn)單的介紹了除了Dijkstra算法以外的其他最短路徑算法的相關(guān)知識(shí)。第二章開(kāi)發(fā)軟件簡(jiǎn)述，這一章講述了編寫基于Dijkstra算法的清掃機(jī)器人最短路徑程序的編程程序語(yǔ)言、運(yùn)行軟件和運(yùn)行環(huán)境。第三章Dijkstra算法，這一章主要講述了運(yùn)用圖形、圖表和文字詳細(xì)的剖析了Dijkstra經(jīng)典算法的基本原理和運(yùn)算最短路徑的過(guò)程，最后還分析了Dijjkstra算法的優(yōu)缺點(diǎn)。第四章基于Dijkstra算法的清掃機(jī)器人最短路徑規(guī)劃的設(shè)計(jì)，這一章主要是通過(guò)流程圖、程序還有圖表講述了清掃機(jī)器人最短路徑程序設(shè)計(jì)方法和設(shè)計(jì)過(guò)程。第五章仿真實(shí)現(xiàn)，這一章主要是對(duì)清掃機(jī)器人最短路徑程序的仿真測(cè)試。最后總結(jié)了本篇論文的主要研究方向，還有對(duì)清掃機(jī)器人最短路徑計(jì)算程序的一些優(yōu)缺點(diǎn)的總結(jié)和對(duì)于此程序未來(lái)的發(fā)展期望。2開(kāi)發(fā)軟件簡(jiǎn)述2.1pythonPython是ABC語(yǔ)言的替代品，它設(shè)計(jì)于90年代初由荷蘭數(shù)學(xué)與計(jì)算機(jī)科學(xué)研究協(xié)會(huì)GuidovanRossum研發(fā)[13]。有效的數(shù)據(jù)結(jié)構(gòu)不僅通過(guò)Python提供，面向?qū)ο蟮木幊桃脖灰?。由于?dòng)態(tài)輸入語(yǔ)言的特性和Python的句法分析，它成為了應(yīng)用語(yǔ)言，他讓更多的軟件平臺(tái)和應(yīng)用他的企業(yè)可以快速地開(kāi)發(fā)腳本和程序。版本的不斷更新和新的語(yǔ)言功能正在被逐步使用于一個(gè)獨(dú)立的大應(yīng)用程序開(kāi)發(fā)項(xiàng)目。Python是一個(gè)容易擴(kuò)展的機(jī)器語(yǔ)言，新的函數(shù)和數(shù)據(jù)類型可以通過(guò)c或c++開(kāi)發(fā)和擴(kuò)展。Python也可以用作可調(diào)軟件中的擴(kuò)展編程語(yǔ)言。豐富的Python標(biāo)準(zhǔn)庫(kù)為每個(gè)基本系統(tǒng)平臺(tái)提供源代碼或機(jī)器代碼。自上世紀(jì)90年代初Python出現(xiàn)以來(lái)，它逐漸被廣泛用于系統(tǒng)管理和網(wǎng)頁(yè)設(shè)計(jì)。與其他語(yǔ)言相比，被開(kāi)發(fā)成這種語(yǔ)言的讀寫輸入和解釋能力和功能都很優(yōu)秀，有關(guān)它本身的標(biāo)點(diǎn)符號(hào)語(yǔ)言比其他語(yǔ)言更加特別。Python是一種解釋型語(yǔ)言：說(shuō)明編譯的步驟在研發(fā)階段被取締。類似于PHP和Perl語(yǔ)言。Python是交互式語(yǔ)言:說(shuō)明了，通過(guò)在Python的符號(hào)“>>>”的后方可以直接運(yùn)行代碼Python是面向?qū)ο笳Z(yǔ)言:說(shuō)明了python代碼的封裝程度已經(jīng)很成熟了和python是標(biāo)準(zhǔn)面向?qū)ο蟮恼Z(yǔ)言。Python是初學(xué)者的語(yǔ)言:Python代碼小白而言，是易上手易開(kāi)發(fā)的語(yǔ)言，大部分的應(yīng)用程序都可以通過(guò)此語(yǔ)言進(jìn)行開(kāi)發(fā)，無(wú)論是前端后端還是游戲開(kāi)發(fā)都能使用此語(yǔ)言。2.2PythonIDLEIDLE是Python的集成開(kāi)發(fā)環(huán)境。這是通過(guò)代碼包裝的可選部分組成的Python，很多版本的Linux都包含在內(nèi)。它完全用Python和TkinterGUI工具包編寫（Tcl/Tk的包裝函數(shù)）。通過(guò)基本的IDE進(jìn)行基于Python軟件開(kāi)發(fā)的。常規(guī)的IDE功能他都具備，是Python非營(yíng)利開(kāi)發(fā)的一個(gè)優(yōu)質(zhì)的選擇。一旦安裝了python,就會(huì)自動(dòng)配置IDLE，所以沒(méi)有必要單獨(dú)下載安裝它。與此同時(shí)，使用IDLE框架Eclipse也可以很方便地調(diào)整Python軟件。主要功能:句法分離，段落分離，文本編輯，表鍵控制，程序調(diào)試。Idle是GuidovanRossum制作的標(biāo)準(zhǔn)Python發(fā)布版[14]?？梢栽谌魏吻闆r下都運(yùn)行Python和TK在閑置的狀態(tài)環(huán)境。打開(kāi)Idle會(huì)顯示已提升的對(duì)話框命令行接口窗口(這是比刪除和粘貼基本對(duì)話框命令前端更好的功能)。它還有Python的編輯器(雖然沒(méi)有整合代碼，但具有自動(dòng)輸入代碼的功能)，類瀏覽器和調(diào)試器。點(diǎn)擊下面菜單的虛線，菜單將會(huì)更新到永久窗口。值得注意的是編輯”菜單在基礎(chǔ)畫面邊緣的邊角處傾斜是很有用的。中斷點(diǎn)可由IDLE提供變量檢測(cè)功能但沒(méi)有存儲(chǔ)內(nèi)存地址和可變內(nèi)容的存儲(chǔ)或同步等分析功能。2.3PycharmPyCharm是很成熟的應(yīng)用于python的軟件平臺(tái)，Python的開(kāi)發(fā)失效率和速度都有很大的提升。除了調(diào)試、報(bào)告語(yǔ)句錯(cuò)誤、項(xiàng)目管理、代碼提示、自動(dòng)操作、代碼測(cè)試、單一控制等IDE，還特別提供支持網(wǎng)絡(luò)開(kāi)發(fā)的Django構(gòu)件各高級(jí)功能。是JetBrains制作的PyCharmIDE軟件,同時(shí)VS2010的重疊插件Resharper也是由JetBrains研發(fā)出來(lái)的[16]。同時(shí)我們支持GoogleAppEngine來(lái)y應(yīng)用于高級(jí)代碼相關(guān)的分析程序。這個(gè)功能是PyCharm轉(zhuǎn)換為Python項(xiàng)目的開(kāi)發(fā)者和初學(xué)者的強(qiáng)有力的研發(fā)工具。一般IDE擁有的功能PyCharm應(yīng)有盡有，即調(diào)試、加亮詞組、管理項(xiàng)目、代碼報(bào)錯(cuò)、自動(dòng)操作、代碼測(cè)試、智能控制等。同時(shí)Django的開(kāi)發(fā)引擎的功能還受PyCharm所提供，來(lái)支持GoogleAppEngine。IronPython由PyCharm開(kāi)發(fā)的是很具有優(yōu)勢(shì)性的。3Dijkstra算法3.1Dijkstra算法的基本原理3.2Dijkstra算法原理的圖解首先，closelist與openlist集合有我們提出：1、閉集closelist：記錄已求出最短路徑的節(jié)點(diǎn)。2、開(kāi)集openlist：記錄找不到最短路徑的節(jié)點(diǎn)。。3、集合1：記錄源節(jié)點(diǎn)到各節(jié)點(diǎn)的距離。4、集合2：記錄節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn)。算法操作步驟：最后，我們重復(fù)上面兩個(gè)步驟，直到遍歷所有的節(jié)點(diǎn)。首先，源點(diǎn)被添加到closelist集合中，其他節(jié)點(diǎn)被添加到openlist中，分析從A到另外剩余節(jié)點(diǎn)的距離。不能通過(guò)源節(jié)點(diǎn)直接到達(dá)的距離將被記錄為∞。接著從開(kāi)放列表中選擇“最短距離的頂部N”，并將頂部N添加到禁用列表中，同時(shí)將頂部N從禁用列表中移除。然后計(jì)算從開(kāi)源列表中的每個(gè)節(jié)點(diǎn)到a的距離(從開(kāi)源列表中的每個(gè)節(jié)點(diǎn)的距離)的距離因?yàn)榍懊娴牟襟E確定了N是最短路徑的頂點(diǎn)，因此N可以用來(lái)更新到其他頂點(diǎn)的距離。例如，從A到B到C的距離可能小于A到C的距離，從A到C的距離必須在此期間改變，父點(diǎn)C也會(huì)隨之變換。)最后需要反復(fù)進(jìn)行以上步驟，直到我們通過(guò)所有的節(jié)點(diǎn)。舉個(gè)例子，尋找到A到G點(diǎn)的最短距離：圖:3-1示例有向圖圖首先，我們將起點(diǎn)A存入在封閉集合列表中，將未完成的節(jié)點(diǎn)放在開(kāi)放集合中，如下所示:圖:3-2示例表格圖圖:3-3起點(diǎn)A變化圖選擇最小距離的節(jié)點(diǎn)。很明顯可以獲取點(diǎn)B，把B從一個(gè)開(kāi)放的集合中移除，然后把它添加到一個(gè)封閉的集合中。圖:3-4搜尋節(jié)點(diǎn)表格圖圖:3-5搜尋節(jié)點(diǎn)B圖圖:3-6更新距離表格圖圖:3-7更新節(jié)點(diǎn)圖根據(jù)上述方法的類比，直到所有節(jié)點(diǎn)都被發(fā)現(xiàn)，終點(diǎn)出現(xiàn)在封閉的集合中:圖:3-8計(jì)算路徑表格圖最終得到最短路徑：G—>F—>E—>C—>B—>A。3.3Dijkstra算法的優(yōu)缺點(diǎn)4基于Dijkstra算法的清掃機(jī)器人最短路徑規(guī)劃的設(shè)計(jì)4.1搜尋路徑的目標(biāo)效果假定有如下的地圖：圖:4-1目標(biāo)地圖圖左下角為清掃機(jī)器人目前的所在位置，而右上角的位置為檢測(cè)到的需要清理的地區(qū)。當(dāng)我們用Dijkstra算法來(lái)尋找最佳路徑，最終的效果為：圖:4-2目標(biāo)仿真效果圖程序會(huì)以我們定義的機(jī)器人起點(diǎn)，逐漸向四周進(jìn)行擴(kuò)展，直到搜尋到我們定義的需要清掃的目標(biāo)地點(diǎn)。4.2初始位置，終點(diǎn)位置，繪制地圖我們需要?jiǎng)?chuàng)建一個(gè)房間地形的模擬圖形，包括障礙物的創(chuàng)建，還有清掃機(jī)器人的初始點(diǎn)和清掃目標(biāo)地區(qū)：圖:4-3地圖定義程序圖以上程序段主要是對(duì)模擬地圖的創(chuàng)建，首先用定義了機(jī)器人的起點(diǎn)、終點(diǎn)、柵格的大小、還有機(jī)器人的半徑。然后需要設(shè)置地圖中障礙物的位置，前面的四個(gè)For循環(huán)用來(lái)設(shè)置四周的障礙物，用來(lái)模擬房間的四面墻。后面兩個(gè)For循環(huán)用來(lái)設(shè)置地圖內(nèi)的障礙物，模擬房間中的物品。最終通過(guò)plt.plot()指令在格柵地圖中畫出地圖的形狀。圖:4-4地圖描繪程序圖以上都只是柵格地圖之上模擬地圖的創(chuàng)建，最重要的還是對(duì)柵格地圖的創(chuàng)建，程序段如下：圖:4-5格柵地圖創(chuàng)建程序圖在之前的程序中，我們已經(jīng)定義了地圖的大小，通過(guò)提取障礙物的邊界值來(lái)設(shè)置柵格地圖的最大值和最小值。接著我們需要得出柵格具體的個(gè)數(shù)，例如通過(guò)（x的最大值-x的最小值）/柵格的大小就能得出x方向上的柵格具體數(shù)量。Y方向通過(guò)相同方式得出。4.3地圖的初始化和障礙物的設(shè)置上文只是對(duì)障礙物的具體位置和形狀進(jìn)行了描述，但并沒(méi)有將其設(shè)置成障礙物，以此需要以下程序：圖:4-6地圖初始、障礙物設(shè)置程序圖先是遍歷每個(gè)柵格，將其初始化為False，這就是地圖的初始化。接著通過(guò)前面兩個(gè)For循環(huán)來(lái)遍歷每個(gè)柵格，尋找到障礙物，然后通過(guò)另一個(gè)For循環(huán)遍歷每個(gè)障礙物，并且膨脹每個(gè)障礙物，將其設(shè)置為Ture：圖:4-7地圖假象模型圖格柵地圖的構(gòu)建如上所示，R就是格柵地圖中機(jī)器人的所在位置，o則是膨脹后的障礙物，機(jī)器人的半徑小于障礙物時(shí)，則判定為無(wú)法通行。4.4機(jī)器人的運(yùn)動(dòng)方式以及柵格編號(hào)4.4.1機(jī)器人運(yùn)動(dòng)方式創(chuàng)建好地圖之后就是對(duì)機(jī)器人運(yùn)動(dòng)方式的定義了，程序如下：圖:4-8機(jī)器人運(yùn)動(dòng)方式程序圖這里定義了機(jī)器人向周圍八個(gè)方向運(yùn)動(dòng)的軌跡，以及運(yùn)動(dòng)后的花費(fèi)。4.4.2柵格編號(hào)為了能夠更快的搜尋到最短路徑，我們要對(duì)每個(gè)柵格進(jìn)行特定的標(biāo)號(hào)，方便能夠最快速的尋找到我們需要的柵格:圖:4-9格柵Key的構(gòu)建程序圖這里采用哈希表的方式：Key-Value，將每個(gè)柵格進(jìn)行不同的編號(hào)，產(chǎn)生不同的Key，在后面方便將其放入到開(kāi)集合和閉集合中。效果如下所示：圖:4-10格柵Key的效果圖4.5搜尋路徑4.5.1搜尋流程搜尋路徑的流程為將起點(diǎn)放在openlist中，然后進(jìn)入循環(huán)中，把openlist里路徑花費(fèi)g（n）最小的節(jié)點(diǎn)加入到closedlist中，然后判斷這個(gè)路徑是否為終點(diǎn)，如果不是就以從這個(gè)節(jié)點(diǎn)開(kāi)始，遍歷它周圍沒(méi)在closedlist中的鄰接節(jié)點(diǎn)，然后計(jì)算每個(gè)鄰接節(jié)點(diǎn)的路徑花費(fèi)(n)，接著再進(jìn)入下一個(gè)循環(huán)，直到搜尋到終點(diǎn)后，循環(huán)停止。其流程圖如下圖4-11所示。圖:4-11搜尋流程圖4.5.2判斷邊界、障礙物查看每個(gè)節(jié)點(diǎn)的搜索過(guò)程中，需判別是否有機(jī)器人觸及了地圖邊界和障礙物。程序部分代碼如下。圖:4-12碰撞判定程序圖px、py為機(jī)器人當(dāng)前所在的具體位置，前面四個(gè)判斷的是查看機(jī)器人撞到邊界，接觸到會(huì)返回False。后面一個(gè)判斷是查看機(jī)器人是否碰撞到障礙物接觸到會(huì)返回False，反之會(huì)生成一個(gè)true。4.6獲得最短路徑通過(guò)上文對(duì)路徑的搜尋，我們找到了目標(biāo)點(diǎn)。圖:4-13最短路徑搜尋程序圖這段代碼可以用圖文來(lái)解釋：圖:4-14最短路徑搜尋示意圖從起點(diǎn)v1一直到終點(diǎn)v6。在獲取最終路徑時(shí)，我們需要從終點(diǎn)出發(fā)尋找。在搜尋完路徑后，代碼中會(huì)記錄最短的路徑來(lái)自于那個(gè)節(jié)點(diǎn)，比如v6的最短節(jié)點(diǎn)來(lái)自于v7，v7來(lái)自于v4，一直搜尋到起點(diǎn)v1。而v1我們記錄的是一個(gè)-1的數(shù)據(jù)，當(dāng)程序獲取的數(shù)據(jù)為-1時(shí)，就判斷這段路徑已經(jīng)獲取完畢，程序就會(huì)停止，最后就能計(jì)算出最短路徑。5仿真實(shí)現(xiàn)這是創(chuàng)建的初始地圖：圖:5-1地圖仿真圖如上圖5-1中，左下角的點(diǎn)是清掃機(jī)器人所在的初始點(diǎn)，而右上角是我們定義的被檢測(cè)到的需要清掃的目標(biāo)地點(diǎn)。四周的邊框是我們定義的模擬墻面，中間豎著的兩條線這是我們定義的模擬障礙物。這是運(yùn)行程序后的結(jié)果：圖:5-2結(jié)果仿真圖如上圖5-2所示，圖中布滿的X，表示的是機(jī)器人從起點(diǎn)開(kāi)始搜尋目標(biāo)終點(diǎn)的搜尋路徑，當(dāng)尋找到目標(biāo)終點(diǎn)后，程序就會(huì)算出最短路徑，然后通過(guò)線段顯示出來(lái)。6總結(jié)與展望以上便是對(duì)于Dijkstra算法實(shí)現(xiàn)清掃機(jī)器人路徑規(guī)劃的全部?jī)?nèi)容。本文主要講述的就是基于Dijkstra算法的清掃機(jī)器人的路徑規(guī)劃以及仿真的實(shí)現(xiàn)，首先就是對(duì)于Dijkstra經(jīng)典算法的原理的仔細(xì)剖析，再了解了基本原理的基礎(chǔ)上，將這種運(yùn)算最短路徑的算法進(jìn)一步結(jié)合到現(xiàn)實(shí)生活的問(wèn)題中來(lái)。進(jìn)一步解決了清掃機(jī)器人最短路徑搜尋的問(wèn)題，能減少清掃機(jī)器人能量的損耗，節(jié)省能源的使用率。Dijkstra算法是目前所熟知的最為方便的一種機(jī)器人最短路徑的算法，其可以搜尋到地圖的每一個(gè)角落，直到搜尋到目標(biāo)位置之后才會(huì)停止，因此是一種搜索范圍很廣的算法。也正是因?yàn)镈ijkstra算法搜尋范圍較廣，會(huì)將地圖的每個(gè)點(diǎn)都搜尋一遍，因此可能會(huì)造成較大的計(jì)算量，會(huì)降低機(jī)器的運(yùn)行效率。本文程序里的地圖是事先編程給出的，因此，希望在未來(lái)能夠?qū)崿F(xiàn)清掃機(jī)器人運(yùn)作和實(shí)時(shí)地圖探測(cè)的結(jié)合，能夠?qū)崟r(shí)的反映出地圖上清掃機(jī)器人自身的位置和需要清掃的目標(biāo)地點(diǎn)位置，隨時(shí)的更新以便隨時(shí)進(jìn)行清掃。當(dāng)然，本文使用的程序只針對(duì)出現(xiàn)一個(gè)目標(biāo)地點(diǎn)的情況，希望未來(lái)能發(fā)展出對(duì)多個(gè)目標(biāo)地點(diǎn)進(jìn)行搜尋計(jì)算，能更加貼近生活中的問(wèn)題然后去解決。參考文獻(xiàn)陳智康1,劉佳1,2,王丹丹3,張運(yùn)喜1,2.改進(jìn)Dijkstra機(jī)器人路徑規(guī)劃算法研究[A].（1.天津職業(yè)技術(shù)師范大學(xué)天津市信息傳感與智能控制重點(diǎn)實(shí)驗(yàn)室，天津;2.天津職業(yè)技術(shù)師范大學(xué)自動(dòng)化與電氣工程學(xué)院,天津;3.青島市技師學(xué)院，青島），2020梁波,楊新民.一種基于改進(jìn)型Dijkstra算法的路線規(guī)劃方法研究[A].南京:中國(guó)電子科技集團(tuán)公司第28研究所，2020耿振余,陳治湘,黃路煒,李德龍,劉思彤，周宏升，王立華編著．軟計(jì)算方法及其軍事應(yīng)用[M].國(guó)防工業(yè)出版社，2015.12秦麗園.簡(jiǎn)析BP神經(jīng)網(wǎng)絡(luò)算法[A].四川成都:成都理工大學(xué)，2016丁艷,管燕明.粒子群算法優(yōu)化研究[A].廣東廣州，2018鄭樹(shù)泉.工業(yè)智能技術(shù)與應(yīng)用[M].上海:上?？茖W(xué)技術(shù)出版社，2019張海濤,程蔭杭.基于A*算法的全局路徑搜索[A].《CNKI;WanFang》，2007夏正東,卜天明,張居陽(yáng).SPFA算法的分析及改進(jìn)[A].上海;華東師范大學(xué)上海市可信重點(diǎn)實(shí)驗(yàn)室，2014.王超,高武奇.基于AHP與Bellman-Ford算法的停車規(guī)劃方法[A].陜西西安：西安工業(yè)大學(xué)電子信息工程學(xué)院,2017郭志軍.Floyd-Warshall算法的C語(yǔ)言實(shí)現(xiàn)[A].遼寧:遼寧對(duì)外經(jīng)貿(mào)學(xué)院信息技術(shù)系，2008劉小玲,李輝,郭治國(guó).基于狄克斯特拉算法的車間動(dòng)態(tài)生產(chǎn)能力評(píng)估與實(shí)現(xiàn)[J].微計(jì)算機(jī)信息，2006(12):96-98郝自軍,何尚錄.最短路問(wèn)題的Floyd算法的若干討論[J].重慶工學(xué)院學(xué)報(bào)(自然科學(xué)版),2008,(05):156-159.[2017-09-02].黃海濤.Python3破冰人工智能從入門到實(shí)戰(zhàn).北京:人民郵電出版社，2019KennethReitz,TanyaSchlusser著.Python漫游指南影印版英文版:東南大學(xué)出版社，2017.10：第35頁(yè)百度百科.Pycharm.[EB/OL].[2014