[發(fā)明專(zhuān)利]一種基于改進(jìn)D*lite算法的移動(dòng)機(jī)器人路徑規(guī)劃方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 202010010351.6
• 申請(qǐng)日: 2020-01-06
• 公開(kāi)（公告）號(hào): CN111176286B
• 公開(kāi)（公告）日: 2022-08-23
• 發(fā)明（設(shè)計(jì)）人: 張毅;施明瑞
• 申請(qǐng)（專(zhuān)利權(quán)）人: 重慶郵電大學(xué)
• 主分類(lèi)號(hào): G05D1/02
• 分類(lèi)號(hào): G05D1/02
• 代理公司: 重慶市恒信知識(shí)產(chǎn)權(quán)代理有限公司 50102
• 代理人: 劉小紅;陳棟梁

1.一種基于改進(jìn)D*lite算法的移動(dòng)機(jī)器人路徑規(guī)劃方法，其特征在于，包括以下步驟：

步驟S1，首先，根據(jù)機(jī)器人所在環(huán)境的柵格地圖，使用地圖分割算法將地圖分割為若干內(nèi)部沒(méi)有障礙物的有界單元；

步驟S2，根據(jù)S1中所得的若干有界單元之間的連通關(guān)系得到單元連接圖，計(jì)算得到各單元之間的原始距離代價(jià)值和鄰接矩陣；

步驟S3，根據(jù)S2中得到的鄰接矩陣，使用雙向圖搜索算法，計(jì)算得到從目標(biāo)單元到起始單元所經(jīng)過(guò)的單元順序；

步驟S4，根據(jù)S3得到的單元順序，依次按照核心網(wǎng)格設(shè)置方法在對(duì)應(yīng)單元中設(shè)置核心網(wǎng)格，按順序組成搜索鏈表；

步驟S5，根據(jù)S4得到的搜索鏈表，將D*lite算法多方向的搜索依照搜索鏈表的順序分為多段的朝著正確方向的搜索，用搜索鏈表引導(dǎo)D*lite算法完成路徑規(guī)劃；

所述步驟S4根據(jù)S3得到的單元順序，依次按照核心網(wǎng)格設(shè)置方法在對(duì)應(yīng)單元中設(shè)置核心網(wǎng)格，按順序組成搜索鏈表，具體步驟為：

S41：為每一個(gè)網(wǎng)格添加一個(gè)編號(hào)num，num等于網(wǎng)格所在單元的編號(hào)；

S42：根據(jù)S3中得到的單元順序，從第二個(gè)單元開(kāi)始，設(shè)當(dāng)前單元為u，前一單元為u′，找出u中與u′相鄰的網(wǎng)格作為核心區(qū)域core，記為：

core＝all(s_{s.num＝u.num}∈succ(s′_{s′.num＝u′.num}))

S_{s.num＝u.num}表示單元u中的網(wǎng)格，在當(dāng)前單元u中，所有與前一單元u′相鄰的網(wǎng)格共同組成了單元u的核心區(qū)域；按單元順序依次設(shè)置核心區(qū)域，直到在起始單元中完成設(shè)置；

S43：以X_max，X_min，Y_max，Y_min表示核心區(qū)域內(nèi)的網(wǎng)格中擁有的最大和最小橫縱坐標(biāo)，計(jì)算核心區(qū)域中心坐標(biāo)core_mid，具體公式為：

S44：設(shè)置目標(biāo)網(wǎng)格為第一個(gè)核心網(wǎng)格，起始網(wǎng)格為最后一個(gè)核心網(wǎng)格，設(shè)s為當(dāng)前核心區(qū)域內(nèi)的網(wǎng)格，cgrid為上一個(gè)核心網(wǎng)格，core_mid為下一個(gè)核心區(qū)域的中心坐標(biāo)，給每一個(gè)核心區(qū)域內(nèi)的網(wǎng)格設(shè)置一個(gè)kc值，由kc₁和kc₂組成，記為：

每個(gè)核心區(qū)域中選取kc值最小的網(wǎng)格作為核心網(wǎng)格，首先比較kc₁值，如果kc₁相同再比較kc₂值；

S45：用核心網(wǎng)格組成搜索鏈表，其中鏈表的頭是目標(biāo)網(wǎng)格，鏈表的尾是起始網(wǎng)格，其余核心網(wǎng)格按照單元順序插入鏈表中，即可得到搜索鏈表。

2.根據(jù)權(quán)利要求1所述的一種基于改進(jìn)D*lite算法的移動(dòng)機(jī)器人路徑規(guī)劃方法，其特征在于，步驟S1根據(jù)機(jī)器人所在環(huán)境的柵格地圖，使用地圖分割算法將地圖分割為若干內(nèi)部沒(méi)有障礙物的有界單元，具體步驟為：

S11：用一條垂直線從左至右掃描柵格地圖；

S12：當(dāng)掃描線掃入障礙空間時(shí)，掃描線的連通性增加，當(dāng)掃描線掃出障礙空間時(shí)，掃描線的連通性降低，當(dāng)掃描線的連通性增加時(shí)，一個(gè)舊單元結(jié)束，生成兩個(gè)新單元；當(dāng)掃描線的連通性降低時(shí)，兩個(gè)舊單元結(jié)束，生成一個(gè)新單元；當(dāng)掃描線的連通性不變但某段連通線長(zhǎng)度發(fā)生了階躍變化，若變化的大小超過(guò)當(dāng)前單元最大寬度的一半，則舊單元結(jié)束，新單元生成；

S13：掃描結(jié)束后，環(huán)境地圖被分割成若干獨(dú)立的有界單元，每個(gè)單元內(nèi)部都沒(méi)有障礙物。