基于Dubins路徑的A*算法的多無人機(jī)路徑規(guī)劃

宋雪倩， 胡士強(qiáng)

(上海交通大學(xué)，上海 200240)

0 引言

無人機(jī)(Unmanned Aerial Vehicle,UAV)已經(jīng)被廣泛運(yùn)用于民用和軍用領(lǐng)域。為了達(dá)到真正的“無人”和“智能”，在環(huán)境已知并給定起始位置和航向角之后，無人機(jī)應(yīng)能夠自主規(guī)劃一條滿足任務(wù)需求的避障路徑，通常要求這條路徑最短；而當(dāng)空中有兩架無人機(jī)在同一高度執(zhí)行任務(wù)時，必須考慮防撞，同時還要滿足飛行性能約束。對于固定翼無人機(jī)，它們不能像旋翼機(jī)一樣懸停，必須保持最小速度，且轉(zhuǎn)彎受到最小轉(zhuǎn)彎半徑的限制。

A*算法[1]是路徑規(guī)劃中最著名的離散搜索算法之一。通常先將二維平面進(jìn)行柵格化，再使用A*算法或改進(jìn)A*算法進(jìn)行最短路徑搜索[2-3]。這在規(guī)劃時沒有考慮飛行器的始末航向要求，得到的路徑不能滿足飛行性能約束且會對一些不必要節(jié)點(diǎn)進(jìn)行搜索。文獻(xiàn)[4-5]都使用了A*算法進(jìn)行移動機(jī)器人的路徑規(guī)劃，都是在規(guī)劃完成之后，對路徑進(jìn)行光滑處理，其中涉及較大計(jì)算量且無法保證光滑之后的路徑依舊安全；文獻(xiàn)[6]考慮了飛行性能限制，利用可視圖法與 Dijkstra算法，但仍需要較長計(jì)算時間；而Dubins路徑[7]是給定始末方向以及在轉(zhuǎn)彎半徑有約束的情況下、兩點(diǎn)之間的最短曲線，被廣泛用于自主機(jī)器人的路徑規(guī)劃當(dāng)中[8-10]。本文提出的基于Dubins路徑的A*算法的路徑規(guī)劃方法，考慮了固定翼無人機(jī)的最小轉(zhuǎn)彎半徑，利用Dubins路徑進(jìn)行可飛路徑建模，以Dubins曲線與障礙圓切入點(diǎn)，即無人機(jī)的位姿為節(jié)點(diǎn)，邊搜索下一步的有效節(jié)點(diǎn)，邊利用A*算法進(jìn)行尋優(yōu)，由于剔除了不必要節(jié)點(diǎn)，提升了搜索效率?！?br>