[發明專利]一種基于Dijkstra算法的農用機械最短路徑規劃的方法

有效

• 申請號: 201710966489.1
• 申請日: 2017-10-17
• 公開（公告）號: CN107860386B
• 公開（公告）日: 2020-09-04
• 發明（設計）人: 萬忠政;張盈綸;祝晨旭
• 申請（專利權）人: 洛陽中科龍網創新科技有限公司
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 洛陽市凱旋專利事務所 41112
• 代理人: 陸君

一種基于Dijkstra算法的農用機械最短路徑規劃的方法，涉及一種最短路徑規劃的方法，具體操作步驟如下：將農機的作業區域構建柵格地圖，柵格寬度依據車身寬幅劃分；根據精度要求和實際需要，令車身寬度為柵格寬度奇數倍的（2i+1）倍；根據無人機航測及傳感器反饋的障礙分布情況，將柵格地圖劃分為可通與不可通兩種狀態；為了將優化節點的擴散控制在合理范圍，引入一個最大估計值K；本發明通過選取出一批較優節點，并引入最大估值K來限制這批節點的擴散程度，以這批較優節點作為Dijkstra算法的頂點集，在減少了搜索時間的同時，保證了找到的路徑為最優路徑而非較優路徑。

技術領域

本發明涉及一種最短路徑規劃的方法，尤其是涉及一種基于Dijkstra算法的農用機械最短路徑規劃的方法。

背景技術

公知的，隨著人工智能的發展，無人化一詞逐漸進入了人們的視野，農業的無人化研究是減輕農民負擔，提高生產效率的重要研究方向；農用車輛的自動導航則是無人化研究最為關鍵的一部分，而在研究自動導航相關聯的項目時，往往要面對最短路徑規劃這個問題。最短路徑問題當下是熱門問題之一，被各類學科研究并廣泛應用于各個領域，比如：城市規劃、交通運輸、機器人路徑規劃、車輛路由等；對于我們所研究的農業機械來說，以最短路徑完成工作要求，就意味著以最低的油耗，最短的工作時間，最高的工作效率來完成農業活動，這就在很大程度上提高了生產效率和經濟效益，改善了農民的工作狀態。農機最短路徑規劃對于農機導航，農業現代化建設都有著重要的意義。

目前用于最短路徑規劃的比較經典的算法有Dijkstra算法和A*算法。這兩種算法一般都建立在模擬柵格地圖的基礎上。其中Dijkstra算法是基于圖論理論的遍歷算法，它需要檢測地圖中所有的節點，逐步選取最短路徑；其優勢在于，總能在一定時間內找到最短路徑，也就是能夠100％的找到最短路徑。但是它的搜索速度受到地圖大小和節點數數量的限制。在節點數較多的情況下，Dijkstra算法會耗費較多的搜索時間。這一特性讓Dijkstra算法在面對農機導航所應用的農田區域時顯得力不從心。而A*算法是一種啟發式算法，采用啟發式搜索，啟發式搜索就是在狀態空間中的對每一個搜索位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣就不需要搜索所有的節點，而是利用選擇的啟發函數評估優勢節點，每一步都能自動選出估計代價最小，即最接近目標的節點，這樣就在很大程度上提升了搜索效率；但是算法存在局部最優的問題，它最終所確定下來的路徑往往是較優路徑而非最優路徑。

發明內容

為了克服背景技術中的不足，本發明公開了一種基于Dijkstra算法的農用機械最短路徑規劃的方法。

為了實現所述發明目的，本發明采用如下技術方案：

一種基于Dijkstra算法的農用機械最短路徑規劃的方法，具體操作步驟如下：

（1）、將農機的作業區域構建柵格地圖，柵格寬度依據車身寬幅劃分；根據精度要求和實際需要，令車身寬度為柵格寬度奇數倍的（2i+1）倍，i為非負整數；

（2）、根據無人機航測及傳感器反饋的障礙分布情況，將柵格地圖劃分為可通與不可通兩種狀態；將障礙柵格垂直和水平方向相鄰的i+1個柵格也設置為不可通柵格；矩形最左端最靠上的可通柵格設置為起點，最右端最靠下的柵格設置為目標點，在中間設置若干個中間點，編號為1、2、3…i，上下同側中間點的選取間隔2i個柵格；

（3）、為了將優化節點的擴散控制在合理范圍，引入一個最大估計值K，具體操作步驟如下：

A、根據獲取柵格地圖的信息，記錄每個區域的可通或不可通狀態，并將柵格地圖初始化，即所有區域記錄均為未搜索區域，以起點為初始點，以中間點1作為目標點；

B、搜索本批起始點相鄰的八個節點，根據與目標點之間的距離關系，記作特征值F，從每個當前節點的可擴展節點中選取F值最小的兩個可通節點；