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

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