應用改進APF-Informed-RRT*算法的配送無人機航跡規(guī)劃

摘 要： 為加快末端物流配送的效率，提出一種配送無人機的航跡規(guī)劃問題。針對傳統(tǒng)快速搜索隨機樹（rapidlysearchrandom tree， RRT） 算法在航跡規(guī)劃中存在的盲目性和路徑不平滑等問題，將人工勢場法（artificial potentialfield， APF） 與Informed-RRT*算法融合，提出一種自適應步長增長策略的改進APF-Informed-RRT*算法。首先在選擇新節(jié)點時，考慮到障礙物和目標點的影響，提出一種自適應步長增長策略來解決采樣的盲目性；其次采用三次B樣條對拐點處進行平滑處理；最后分別采用RRT*算法、Informed-RRT*算法和改進APF-Informed-RRT*算法在兩種環(huán)境中進行仿真實驗。結(jié)果表明，改進APF-Informed-RRT*算法相較于RRT*算法和Informed-RRT*算法，在運行時間、迭代次數(shù)以及路徑平滑上都得到提升。

關(guān)鍵詞： 末端物流配送; 航跡規(guī)劃; 人工勢場法; Informed-RRT*算法

中圖分類號： TB9; TH242 文獻標志碼： A 文章編號： 1674–5124（2025）01–0173–08

0 引 言

隨著新興信息技術(shù)的發(fā)展，網(wǎng)絡購物已經(jīng)與人們的生活緊密相關(guān)，客戶體驗也成為關(guān)注的重點。而物流配送，特別是末端物流配送是影響客戶滿意度的重要環(huán)節(jié)。末端物流配送是指從下游配送中心到最終客戶的運輸過程。然而在大部分的實際環(huán)境中，因為繁雜的交通規(guī)則以及多變的地形導致末端物流配送的時效性較低，客戶的體驗感較差，從而制約了網(wǎng)絡購物的發(fā)展[1]。為了提升末端物流配送的效率，無人機引起了國內(nèi)外物流公司和網(wǎng)購平臺的廣泛關(guān)注。配送無人機可以自主避障，不限于地面交通，選擇最優(yōu)的配送的路徑，可以大大減少人力成本，提升配送的效率，已成為末端物流配送的新選擇[2]。

航跡規(guī)劃是確保配送無人機完成任務的前提，其根據(jù)環(huán)境、時間、路程等性能指標，規(guī)劃出一條從起始位置到目標位置的無碰撞的最優(yōu)航跡[3]。航跡規(guī)劃的方法大致分為傳統(tǒng)算法和智能優(yōu)化算法。傳統(tǒng)算法主要有人工勢場法[4]、RRT 算法[5] 等。智能算法主要有蟻群算法[6]、灰狼算法[7] 等。

1986 年，Khatib 提出了人工勢場法[8]，它是一種局部路徑規(guī)劃算法。該算法模型簡單、實時性較強，得到了廣泛應用，但容易出現(xiàn)目標不可達和陷入凹型障礙物區(qū)域的問題[9]。RRT 算法是由Lavalle[10] 提出的一種快速搜索算法，它適用于全局規(guī)劃。該算法計算量小，且不需要構(gòu)建柵格地圖，但其較強的隨機性，會導致搜索時間較長。因此將這兩種算法結(jié)合，可以解決彼此的缺點，達到最優(yōu)的航跡規(guī)劃效果。

很多研究者對這兩種算法的結(jié)合進行了研究。劉成菊等[11] 是在雙向擴展隨機樹的基礎(chǔ)上加入了APF 引力的思想，解決了智能體面對動態(tài)障礙物的路徑規(guī)劃問題，但沒有考慮斥力的影響。陳俠等[12]是在目標偏置RRT 基礎(chǔ)上結(jié)合了APF 和遺傳算法，得到無人機飛行的最優(yōu)航跡。盛春紅等[13] 將Informed-RRT*和APF 結(jié)合，解決了無人機的局部最小值問題但是該方法的適用環(huán)境較簡單。劉文倩等[14] 提出了改進Informed-RRT*算法，解決了無人機狹窄空間中易陷入局部約束導致的航跡規(guī)劃失敗的問題。趙超力等[15] 采用引力引導的RRTconnect算法提高了對狹窄通道環(huán)境的適應性，但可能會存在前期引力過大問題。王楊斌等[16] 在Informed-RRT*基礎(chǔ)上加入了自適應步長策略提高了尋找可行全局路徑的穩(wěn)定性和效率，但步長的自適應函數(shù)設置太過于籠統(tǒng)。雖然上述文獻都基于RRT 和APF 算法的結(jié)合進行了一定的改進，但在復雜障礙環(huán)境中，還會存在航跡不平滑且隨機性強、前期引力過大、搜索時間長等問題。

針對以上問題， 本文提出了一種改進APFInformed-RRT*算法對配送無人機進行航跡規(guī)劃。首先在采樣過程中加入了Informed 采樣策略和改進的APF，減少了采樣的隨機性；然后在確定新節(jié)點時，引入了自適應步長找尋高質(zhì)量節(jié)點，減少迭代次數(shù)；最后采用三次B 樣條對拐點處進行優(yōu)化。仿真結(jié)果表明，本文算法在不同的環(huán)境中都能大大提高搜索效率。

1 Informed-RRT*算法

Informed-RRT*算法是一種概率采樣的搜索方式，它將初始位置作為根節(jié)點，通過隨機采樣向四周生長，直到目標點在隨機樹很近時，便找到了從初始位置到目標位置的航跡。它是在RRT 算法的基礎(chǔ)上加入了重新選擇父節(jié)點的過程、重新布線的過程以及約束采樣空間。

2 改進的APF-Informed-RRT*算法

2.1 改進的APF 算法

Informed-RRT*算法在航跡規(guī)劃時仍然缺乏對復雜環(huán)境的處理能力，在采樣過程中盲目搜索，存在很大的隨機性，因此在采樣過程中引入APF 對采樣范圍加以約束。其思想是在生成新節(jié)點時考慮障礙物以及目標點對新節(jié)點產(chǎn)生方向的影響。