(19)國(guó)家知識(shí)產(chǎn)權(quán)局(12)發(fā)明專利(65)同一申請(qǐng)的已公布的文獻(xiàn)號(hào)(73)專利權(quán)人南京信息工程大學(xué)地址210044江蘇省南京市江北新區(qū)寧六路219號(hào)(72)發(fā)明人朱琪豪劉云平翟馬浩顧潤(rùn)曾凡響卓若水付景枝龔毅光臧強(qiáng)徐梁(74)專利代理機(jī)構(gòu)南京蘇高專利商標(biāo)事務(wù)所(普通合伙)32204專利代理師周雅審查員郭鴻旭(54)發(fā)明名稱基于批處理先驗(yàn)知識(shí)樹的無人機(jī)路徑規(guī)劃方法本發(fā)明公開了一種基于批處理先驗(yàn)知識(shí)樹的無人機(jī)路徑規(guī)劃方法，通過在人工勢(shì)場(chǎng)法的合勢(shì)力函數(shù)中加入采樣點(diǎn)范圍控制參數(shù)，根據(jù)障礙物的密集程度動(dòng)態(tài)調(diào)整采樣點(diǎn)的生成范圍，并定義閾值，當(dāng)采樣點(diǎn)的合勢(shì)力函數(shù)小于閾值時(shí)，則保留該點(diǎn)，否則剔除。該過程大大減少隨機(jī)生成采樣點(diǎn)策略導(dǎo)致的冗余采樣及計(jì)算資源的浪費(fèi)；本發(fā)明在路徑優(yōu)化過程中，將一個(gè)橢圓采樣集合轉(zhuǎn)化為兩個(gè)局部子集橢圓采樣集合，減少采樣面積，提高采樣效率；并通過更新起始點(diǎn)到信標(biāo)點(diǎn)的路徑代價(jià)，增加第二個(gè)橢圓面積，從而增大障礙物間可通行區(qū)域在橢圓內(nèi)部的概率；同時(shí)引入障礙物密集程度因子，增加信標(biāo)點(diǎn)生成在障礙物查否2待擴(kuò)展邊優(yōu)先隊(duì)列Q;將起始點(diǎn)置入樹節(jié)點(diǎn)集合和樹節(jié)點(diǎn)優(yōu)先隊(duì)列中，目標(biāo)點(diǎn)置入采樣新采樣點(diǎn)集合；(4)以初始路徑的起始點(diǎn)和目標(biāo)點(diǎn)作為焦點(diǎn)，根據(jù)最優(yōu)路徑長(zhǎng)度和起始點(diǎn)和目標(biāo)點(diǎn)的(6)將目標(biāo)點(diǎn)從樹節(jié)點(diǎn)集合中拿出再次放入采樣點(diǎn)集合中，置空Qv和QE,將起始點(diǎn)路徑代價(jià)減去起始點(diǎn)到信標(biāo)點(diǎn)的路徑代價(jià)值(7)再次置空Qv和QE,并將起始點(diǎn)放入圓批次采樣中；(9)對(duì)第一子橢圓和第二子橢圓中進(jìn)行剪枝優(yōu)化，并在兩個(gè)子橢圓中批次采樣；置空Qv和QB將路徑上的采樣點(diǎn)放入Q,根據(jù)Qv和Qg的最小估計(jì)成本，確定最優(yōu)待擴(kuò)展34 標(biāo)b的獎(jiǎng)勵(lì)r?(t)為5歸一化獎(jiǎng)勵(lì)r(t)為10.根據(jù)權(quán)利要求1所述基于批處理先驗(yàn)知識(shí)樹的無人機(jī)路徑規(guī)劃方法，其特征在于，6基于批處理先驗(yàn)知識(shí)樹的無人機(jī)路徑規(guī)劃方法背景技術(shù)任務(wù)起著決定性作用。傳統(tǒng)的路徑規(guī)劃算法主要包括基于圖搜索的算法和基于采樣的算[0010](6)將目標(biāo)點(diǎn)從樹節(jié)點(diǎn)集合中拿出再次放入采樣點(diǎn)集合中，置空Qv和Q,將起7d?d?和d?為閾值常量,P(q,Qg8[0034](52)計(jì)算去時(shí)刻第I個(gè)節(jié)點(diǎn)作為信標(biāo)的選擇概率p(t);9[0055]將采樣點(diǎn)(x,y")依次進(jìn)行逆旋轉(zhuǎn)和逆平移操作，得到采樣點(diǎn)在原始坐標(biāo)系下的坐標(biāo)。[0056]進(jìn)一步的，步驟(11)中，三階B樣條曲線為[0059]有益效果：本發(fā)明與現(xiàn)有技術(shù)相比，其顯著優(yōu)點(diǎn)是：1、本發(fā)明在人工勢(shì)場(chǎng)法的合勢(shì)力函數(shù)中加入了采樣點(diǎn)范圍控制參數(shù)，能夠根據(jù)障礙物的密集程度動(dòng)態(tài)調(diào)整采樣點(diǎn)的生成范圍，并定義閾值θ,當(dāng)采樣點(diǎn)的合勢(shì)力函數(shù)小于閾值時(shí)，則保留該點(diǎn)，否則剔除。該過程大大減少了隨機(jī)生成采樣點(diǎn)策略導(dǎo)致的冗余采樣及計(jì)算資源的浪費(fèi)；2、本發(fā)明將一個(gè)橢圓采樣集合轉(zhuǎn)化為兩個(gè)局部子集橢圓采樣集合，減少采樣面積，提高了采樣效率；并通過更新起始點(diǎn)到信標(biāo)點(diǎn)的路徑代價(jià)，增加第二個(gè)橢圓面積，從而增大障礙物間可通行區(qū)域在橢圓內(nèi)部的概率；同時(shí)引入障礙物密集程度因子，使得信標(biāo)點(diǎn)生成在障礙物旁邊的概率更大，增加了路徑通過復(fù)雜障礙物的可能性，從而優(yōu)化路徑；3、本發(fā)明在橢圓內(nèi)部進(jìn)行批次采樣時(shí)，本發(fā)明采用基于橢圓參數(shù)方程的采樣法，引入縮放因子，通過簡(jiǎn)單的三角函數(shù)能夠隨機(jī)得到橢圓內(nèi)的采樣點(diǎn)坐標(biāo)，相比于隨機(jī)采樣再進(jìn)行判斷點(diǎn)是否在橢圓內(nèi)部的方法來說計(jì)算開銷附圖說明[0060]圖1為本發(fā)明的流程圖；[0061]圖2為本發(fā)明的橢圓的空間示意圖；[0062]圖3是本發(fā)明的第一和第二子橢圓的空間示意圖；[0063]圖4至圖7為本發(fā)明步驟(4)至步驟(9)的示意圖；[0064]圖8是本發(fā)明步驟(9)剪枝的示意圖；[0065]圖9是本發(fā)明的樹節(jié)點(diǎn)擴(kuò)展示意圖。具體實(shí)施方式[0066]下面結(jié)合附圖對(duì)本發(fā)明作進(jìn)一步說明。[0067]本發(fā)明所述基于批處理先驗(yàn)知識(shí)樹的無人機(jī)路徑規(guī)劃方法，包括以下步驟：[0068](1)初始化集合，集合包括樹邊集合、樹節(jié)點(diǎn)集合、采樣點(diǎn)集合、樹節(jié)點(diǎn)優(yōu)先隊(duì)列Qv和待擴(kuò)展邊優(yōu)先隊(duì)列Q;將起始點(diǎn)置入樹節(jié)點(diǎn)集合和樹節(jié)點(diǎn)優(yōu)先隊(duì)列中，目標(biāo)點(diǎn)置入采樣點(diǎn)集合。[0069](2)引入采樣點(diǎn)范圍控制函數(shù)和合勢(shì)力絕對(duì)值的閾值，結(jié)合人工勢(shì)場(chǎng)法生成采樣點(diǎn)，更新采樣點(diǎn)集合。具體步驟如下：[0070](21)采用批處理操作在區(qū)域內(nèi)進(jìn)行隨機(jī)采樣。[0071](22)采用改進(jìn)的人工勢(shì)場(chǎng)法引導(dǎo)生成采樣點(diǎn)。依據(jù)障礙物的密集程度動(dòng)態(tài)調(diào)整采樣點(diǎn)的生成范圍，障礙物數(shù)量較多時(shí)，采樣點(diǎn)的生成范圍也會(huì)更大，障礙物數(shù)量較少時(shí)，采樣點(diǎn)的生成范圍也會(huì)更小。假設(shè)在地圖中隨機(jī)采樣出一個(gè)點(diǎn)9,改進(jìn)的人工勢(shì)場(chǎng)法會(huì)根據(jù)公式如下：4越小，人工勢(shì)場(chǎng)法影響采樣點(diǎn)生成的能力就越弱，采樣點(diǎn)就越趨于在全局地圖中生成；4越大，人工勢(shì)場(chǎng)法影響采樣點(diǎn)生成的能力就越強(qiáng)，采樣點(diǎn)就越趨于在起點(diǎn)和目標(biāo)點(diǎn)之間[0078]式中，d?和d?為定義的閾值常量，p(q,qgoai)為采樣點(diǎn)q到目標(biāo)點(diǎn)9goal的歐與傳統(tǒng)人工勢(shì)場(chǎng)法的引力勢(shì)場(chǎng)函數(shù)一致；當(dāng)p(q,qgoat)在d?和d?之間時(shí)，加入α作為新的引力增益系數(shù)，其中α<8;當(dāng)p(q,ggoal)大于定義的閾值常量d?時(shí)，引力勢(shì)場(chǎng)函數(shù)Uau(q)是一個(gè)定值。通過定義d?和d?,可以實(shí)現(xiàn)動(dòng)態(tài)調(diào)整引力勢(shì)場(chǎng)函數(shù)Uau(q)。標(biāo)點(diǎn)與智能體之間的距離因子p(q,qgoal),在智能體靠[0082]本發(fā)明設(shè)定一個(gè)閾值θ,θ根據(jù)當(dāng)前已生成采樣點(diǎn)的合勢(shì)力絕對(duì)值分布情況來值θ的公式如下：[0086](31)若當(dāng)前樹節(jié)點(diǎn)優(yōu)先隊(duì)列Q的最小估計(jì)成本小于或等于待擴(kuò)展邊優(yōu)先隊(duì)列[0091](4)以初始路徑的起始點(diǎn)和目標(biāo)點(diǎn)作為焦點(diǎn)，根據(jù)最優(yōu)路徑長(zhǎng)度和起始點(diǎn)和目標(biāo)和為長(zhǎng)軸的長(zhǎng)度，所以如果采樣點(diǎn)在橢圓的外面，則它到兩個(gè)焦點(diǎn)的距離肯定大于目前的初始路徑，不能夠改善當(dāng)前的路徑，所以將其剔除。并且任意一條邊的其中一點(diǎn)在橢圓外也無法改善當(dāng)前路徑代價(jià)，也需要將其剔除。具體步驟如下：[0094](42)計(jì)算橢圓的短軸，其長(zhǎng)度為,C..為起點(diǎn)和終點(diǎn)的直線路徑長(zhǎng)度。如下：[0097](44)剔除橢圓外的采樣點(diǎn)。由于橢圓中心點(diǎn)不在原點(diǎn)且其長(zhǎng)軸與x軸可能存在角度，因此采用坐標(biāo)變換的方法建立橢圓坐標(biāo)系，在橢圓坐標(biāo)系下橢圓的中心點(diǎn)在原點(diǎn)且其長(zhǎng)軸為x軸。對(duì)于原始坐標(biāo)系下的采樣點(diǎn)(x,y),首先需要將其平移到以橢圓中心為參考點(diǎn)[0099]接著設(shè)橢圓旋轉(zhuǎn)的角度為9(以逆時(shí)針為正方向)。經(jīng)過平移后的點(diǎn)(x,y)繞原點(diǎn)旋轉(zhuǎn)后的坐標(biāo)(x,y")的計(jì)算公式為[0101]對(duì)于一個(gè)經(jīng)過坐標(biāo)變換后的采樣點(diǎn)(x,y");,如果其滿足方程[0112](51)步驟(4)得到的更新后采樣點(diǎn)集合為V={q?,q?,…,qN},對(duì)節(jié)點(diǎn)集合中的每個(gè)節(jié)點(diǎn)初始化權(quán)重為1;為信標(biāo)b,并引入障礙物密集程度因子計(jì)算信標(biāo)b的獎(jiǎng)勵(lì)r(t),接著進(jìn)行歸一化處理，得到歸一化獎(jiǎng)勵(lì)r(t);[0121]其中，從和σ為權(quán)重參數(shù)，C(b,goal)為從信標(biāo)b到目標(biāo)點(diǎn)Sgoal的潛在路徑代[0130](7)再次置空Qv和Qg,并將起始點(diǎn)放入Qv,再根據(jù)第一子橢圓和第二子橢圓[0137]接著在(0,2π),范圍內(nèi)均勻采樣φ的值，計(jì)算得出x"和y",得到采樣點(diǎn)[0138]將采樣點(diǎn)(x",y")經(jīng)過逆旋轉(zhuǎn)操作轉(zhuǎn)換為平移后的坐標(biāo)系下的坐標(biāo)逆旋轉(zhuǎn)公式如下：[0140]再將(x,y)通過逆平移操作轉(zhuǎn)換為原始坐標(biāo)系下的坐標(biāo)(x,y),逆平移公式如[0142]最終得到在原始坐標(biāo)系下子橢圓內(nèi)部的采樣點(diǎn)。[0143](10)判斷是否完成迭代，若完成則輸出路徑，未完成則返回步驟(9)的批次采樣否否