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

有效

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

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

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

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

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

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

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

C、檢測步驟B中選出的節點是否包含目標點，若包含，將其放入關閉表，繼續步驟E；若不包含，比較節點F值與K的大小；若選出節點F值均大于K，將選出節點放入當前節點表，繼續步驟B；若存在節點F值小于K，將F值小于K的節點放入當前節點表，繼續步驟B，其余點入開放表；

D、將已包含目標點和一批較優節點的關閉表單獨提取出來，將起點放入最短節點集合，其余點入待測節點集合；

E、從待測節點集合中選出距離最短的節點N放入最短節點集合，并將N從待測節點集合中移除；

F、重新計算待測節點集合各個節點到起始點的距離，因為N已選取，則需要以N來更新各個節點的距離；

G、重復步驟E、F，當目標點送入最短距離集合時，即已選擇出一條起點到中間點1的最短路徑，記為路徑1；

H、以中間點1為起點，中間點2為終點，得出路徑2，直至以中間點i為起點，以此類推共搜尋出i+1條路徑，將這些路徑順序連接，即為農機作業時一條最短路徑。

2.根據權利要求1所述的基于Dijkstra算法的農用機械最短路徑規劃的方法，其特征是：所述初始表記錄未搜索節點；臨時表記錄已被擴展還未擇優的節點；開放表記錄擴展擇優后拋棄的節點；關閉表記錄所選取的一批較優節點。