1. 為什么是車無人機還要分兩層規(guī)劃1.1 單車不夠快單機不夠遠2023年ESWA上的這篇工作標題看起來挺直白地面車輛UGV和無人機UAV協(xié)同做多區(qū)域覆蓋并且采用雙層路徑規(guī)劃。但我剛掃到雙層兩個字的時候第一反應(yīng)是這是不是把兩個路徑規(guī)劃問題強行疊在一起搞個復(fù)雜模型換點性能提升把全文的建模和實驗讀完之后我得說這個雙層的設(shè)計是有真實物理背景支撐的不是學(xué)術(shù)包裝。先把問題還原一下。你要對一大片區(qū)域做覆蓋比如園區(qū)巡檢、應(yīng)急勘察、物流配送這類任務(wù)的特點是目標點分散在多個子區(qū)域里而且子區(qū)域之間的道路條件完全不一樣。地面車能跑的時間很長、載荷大但它只能在路網(wǎng)或可通行地形上跑遇到一段圍墻、一條河、一片綠化帶就得繞很遠無人機速度快、能直線飛行看起來是完美的補充但多旋翼無人機的航時大家心里都有數(shù)20到40分鐘級別的續(xù)航稍微飛幾個點就要返航充電或換電池根本扛不住一整片大區(qū)域的連續(xù)覆蓋。所以很自然的思路就是讓車和無人機組隊地面車充當移動母港充電寶拖著無人機跑到某個區(qū)域附近停下來釋放無人機無人機把那一片的離散目標點快速覆蓋完再飛回車旁邊降落車再趕往下一個區(qū)域。這個想法本身不新鮮室內(nèi)物流、農(nóng)業(yè)植保、搜索救援里都有類似車機協(xié)同的影子。但這篇工作切入的角度更細它把問題做了完整的形式化車輛在宏觀層面決定先去哪個區(qū)域、在哪個位置釋放和回收無人機無人機在微觀層面決定某個區(qū)域內(nèi)部的哪些點用什么樣的順序覆蓋。這兩層決策相互依賴又各自成體系所以才叫雙層路徑規(guī)劃。如果只用一輛車在路網(wǎng)上繞純車輛方案的問題很明顯大量時間耗在路上而且對車輛到不了的目標點無能為力。如果只用一群無人機去覆蓋理論上能全覆蓋但每架無人機飛一會兒就要換電池保障體系極其復(fù)雜實際用起來成本高、風險也大。車機協(xié)同恰好把兩者的優(yōu)勢拼起來了車解決長途運輸和能源補給無人機解決最后一公里到點覆蓋。這也是整個研究成立的物理前提理解了這一層后面所有的建模和算法才有代入感。1.2 雙層規(guī)劃的上下到底拆了什么這篇工作把路徑規(guī)劃拆成兩層我個人的理解是上層是戰(zhàn)略調(diào)度層下層是戰(zhàn)術(shù)覆蓋層。兩者不在一個尺度上聊天。上層規(guī)劃解決的是全局問題給定若干子區(qū)域每片區(qū)域里有一堆待覆蓋的目標點地面車輛要決定自己沿哪條路走、在哪些位置設(shè)置起降點、在每個起降點投放多少架無人機、以及什么時候到達、什么時候離開。這一層本質(zhì)上是帶起降點選擇的車輛路徑問題Vehicle Routing Problem with Release and Recovery Points它的解空間很大因為起降點的候選位置既可以放在路網(wǎng)節(jié)點上也可以放在車輛可?？康娜我馕恢?。下層規(guī)劃解決的是局部問題當車輛到達某一片區(qū)域、選定一個或幾個起降點之后無人機怎么在這片區(qū)域內(nèi)部執(zhí)行覆蓋。這一層可以理解為帶續(xù)航約束的覆蓋路徑規(guī)劃每架無人機從起降點起飛訪問若干目標點再回到起降點所有航跡拼接起來要覆蓋完這一片區(qū)域的所有點同時單架無人機的總航程不能超過續(xù)航上限。兩層之間的耦合點就在于時間。車輛到達起降點的時間窗口決定了無人機什么時候能起飛無人機在區(qū)域內(nèi)飛完所有點并返回的時間又決定了車輛必須在起降點等多久。如果車輛提前走了無人機就回不到母港如果車輛等得太久整個系統(tǒng)的總耗時又被拖長。所以雙層規(guī)劃真正的難度不是把兩條路線分別畫出來而是把兩層的時序咬合在一起。這個痛點做過實際帶隊測試的人應(yīng)該都有感觸仿真里畫一條漂亮軌跡很容易真把車停下來等無人機返航時間一錯位整個計劃就卡住了。2. 問題建模先把邊界條件和約束理清楚2.1 區(qū)域與任務(wù)假設(shè)讀論文里的建模部分之前先要把場景假設(shè)搞明白。這類工作通常會做這樣幾個設(shè)定任務(wù)區(qū)域被劃分為多個互不重疊的子區(qū)域每個子區(qū)域內(nèi)有一組已知坐標的目標點需要覆蓋地面車輛沿路網(wǎng)在子區(qū)域之間移動無人機從車上的起降平臺起飛對各子區(qū)域的目標點執(zhí)行覆蓋無人機續(xù)航有限地面車輛可以攜帶多架無人機也可以攜帶備用電源在行駛過程中為無人機充電。這些假設(shè)不是隨便拍的。多區(qū)域劃分對應(yīng)真實場景里廠區(qū)多個罐區(qū)城市多個小區(qū)干線道路連接的多個田塊這類結(jié)構(gòu)目標點坐標已知對應(yīng)巡檢點位、配送點、災(zāi)情勘察點這些點在實際項目中早就通過地圖或勘察確定過了無人機續(xù)航有限更是硬約束所有規(guī)劃必須在這個前提下做。區(qū)域劃分的方式也值得提一嘴。常見的做法有兩種一種是根據(jù)地理屬性人工劃分比如道路、河流、圍墻天然形成的邊界另一種是算法自動劃分比如用泰森多邊形或聚類方法把目標點聚成若干簇每一簇對應(yīng)一個子區(qū)域。人工劃分的好處是貼合實際地形壞處是區(qū)域大小不均勻可能出現(xiàn)某個區(qū)域目標點特別多而其他區(qū)域很空的情況后面對整體調(diào)度會造成明顯瓶頸。算法自動劃分則能把負載盡量抹平但不一定能尊重地形障礙。這篇工作采用的是預(yù)處理好的區(qū)域劃分把焦點放在區(qū)域分配和覆蓋路徑上我認為這個選擇是合理的——如果連區(qū)域劃分都一起優(yōu)化問題規(guī)模會快速失去控制文章的核心貢獻反而被沖淡了。2.2 上層模型車輛去哪在哪里放機上層模型本質(zhì)上是一個增強版的車輛路徑問題。要決策的變量有三類車輛訪問子區(qū)域的順序每個子區(qū)域內(nèi)起降點的具體位置車輛在每個起降點的停留時長。目標函數(shù)一般是系統(tǒng)總耗時最短。這里的總耗時要做細致的定義它不是純車輛行駛時間因為車輛可能提前到達某個起降點等待無人機完成任務(wù)也可能無人機的任務(wù)早做完了但車輛還沒趕到。更合理的做法是把總耗時定義為車輛從出發(fā)到完成所有區(qū)域任務(wù)并返回/或到達終點的總時間同時要求所有無人機任務(wù)都在這個時間窗口內(nèi)完成。也就是說最終完成時刻由車輛路線和無人機任務(wù)兩者中較晚的那個決定。約束條件在論文里也列得很清楚車輛按路網(wǎng)行駛速度固定起降點必須設(shè)置在車輛可停靠的位置并且不能和禁飛區(qū)域重疊無人機每次起飛后必須在航時上限內(nèi)回到起降點車輛在起降點停留的時間長度必須覆蓋該起降點釋放的無人機完成整段任務(wù)的往返時間。我在看很多同類論文時經(jīng)常發(fā)現(xiàn)一個問題模型里對無人機可以在多個起降點反復(fù)起飛降落這一行為處理得比較模糊。但這篇工作把無人機的角色定義得更貼近實際——無人機是可以反復(fù)使用的每次車輛在一個起降點停下無人機起飛完成一批點回到車輛充電車輛移動到下一個起降點無人機再次起飛覆蓋下一批點。這樣一來無人機的航次變成了一種可由上層調(diào)度的資源而不是一次性使用的消耗品。2.3 下層模型無人機怎么覆蓋一個區(qū)域下層模型是一個經(jīng)典的覆蓋路徑規(guī)劃給定一個子區(qū)域內(nèi)的目標點集合給定一架或多架無人機從起降點出發(fā)求一組滿足續(xù)航約束的環(huán)形航跡使得所有目標點都被訪問到。如果有多架無人機可用還要做任務(wù)分配每個目標點分給哪一架無人機用什么樣的順序訪問。這個問題的難點主要在兩個地方。第一個難點是續(xù)航約束的剪枝。如果只求一條覆蓋所有點的最短回路那就是標準的旅行商問題但無人機航時有限一條回路往往飛不完必須拆成多條航段每一段分配給一架無人機。拆分的顆粒度又受到目標點數(shù)量的影響目標點稀疏時一段航跡可以覆蓋很多點目標點密集時可能飛幾個點就得返航。所以下層模型的核心是續(xù)航約束下的多航段覆蓋它比普通TSP多了一層硬性資源限制。第二個難點是多架無人機的協(xié)同。如果車里帶了兩架甚至更多無人機各架無人機可以在同一區(qū)域內(nèi)同時起飛、并行覆蓋但也要去重——不能讓兩架無人機重復(fù)飛同一個目標點否則覆蓋效率會打折扣。這個問題的規(guī)模一下子又上去了從單航段TSP變成了帶容量限制的多旅行商問題。我自己做這類規(guī)劃時會習(xí)慣把下層模型再拆一層目標點先按空間鄰近關(guān)系聚類成若干分組每一組交給一架無人機。分組的依據(jù)不僅是距離還要考慮無人機的航時上限如果一個簇的總訪問距離超過了單架無人機的續(xù)航就得再細分。這種聚類-簇內(nèi)路徑規(guī)劃-路徑微調(diào)的流程和論文里的下層求解思路是一脈相承的工程上也比較容易落地。3. 求解策略為什么分層解而不是一口氣硬解3.1 單層模型的復(fù)雜度壓力理論上講車輛路線、起降點位置、無人機航跡、時間同步這些變量完全可以揉進一個統(tǒng)一的混合整數(shù)規(guī)劃模型里求解。但真這么干問題規(guī)模會迅速爆炸。假設(shè)有10個子區(qū)域每個區(qū)域20個目標點車輛可選起降點50個無人機2架初步算一下決策變量的量級就是1e4以上的離散變量加上時間同步約束商業(yè)求解器也未必能在可接受時間內(nèi)給出可行解更不用說大規(guī)模場景。所以這篇工作采用先宏觀、后微觀的分層思路本質(zhì)上是把一個大規(guī)模組合優(yōu)化問題降維成兩個中等規(guī)模的子問題交替迭代逼近。這樣做有個好處每一層的模型相對干凈可以為各自選擇更合適的求解算法壞處也明顯分層的方案不保證全局最優(yōu)兩層交替迭代可能陷入局部最優(yōu)。但從工程角度看能快速給出一個高質(zhì)量可行解往往比追求理論最優(yōu)但計算不動更實用這也是為什么這一類方案在應(yīng)用型期刊上能得到認可。3.2 上層算法與下層算法的搭配上層問題可以看作帶起降點選擇的VRP這類問題用遺傳算法GA、蟻群算法ACO或自適應(yīng)大鄰域搜索ALNS處理非常常見。論文里采用的是進化算法框架每一代對車輛訪問順序和起降點候選位置做交叉、變異適應(yīng)度函數(shù)把下層回傳的覆蓋成本吃進來。下層問題更精確一點可以用動態(tài)規(guī)劃求小規(guī)模的TSP回路也可以對每個區(qū)域先做聚類、再按簇求解覆蓋回路。如果區(qū)域的目標點數(shù)量不多用貪心算法初始化加上2-opt局部搜索效果就不錯目標點一多就得考慮把區(qū)域再分割或者引入啟發(fā)式。這里要補充一個容易被忽略的細節(jié)上層算法在評估一個個體的適應(yīng)度時需要對所有子區(qū)域都跑一遍下層求解。也就是說下層算法要被反復(fù)調(diào)用很多次如果下層每次求解都很慢整個兩層迭代的速度會非常感人。所以實際實現(xiàn)里下層算法必須在最優(yōu)性和速度之間做取舍。論文里對下層用了快速啟發(fā)式而不是精確算法從計算時間的角度來說這確實是更聰明的選擇——精確解很好看但在迭代里跑不動就是白搭。下面是我在復(fù)現(xiàn)這類框架時常用的求解骨架結(jié)構(gòu)大致如下def two_level_plan(regions, vehicle, uavs): best_solution None for gen in range(max_generations): # 上層進化算法生成車輛路線與起降點方案 veh_route ga_evolve(regions, candidate_landing_points) # 由車輛路線計算每個起降點的時間窗口 time_windows compute_time_windows(veh_route) # 下層對每個區(qū)域內(nèi)部求解無人機覆蓋計劃 task_plans {} for region in regions: task_plans[region] solve_uav_coverage( region.points, time_windows[region], uavs, max_flight_timeflight_limit ) # 匯總上下兩層耗時作為上層適應(yīng)度 total_cost evaluate_total(veh_route, task_plans) if best_solution is None or total_cost best_solution.cost: best_solution (veh_route, task_plans) return best_solution這段代碼只是示意性的求解流程但足夠說明上下層如何交互上層給下層限定了時間和起降點下層把每片區(qū)域的覆蓋方案和耗時返回給上層做評估兩層之間的信息是雙向流動的。3.3 上下層迭代時的關(guān)鍵機制兩層迭代看起來簡單實際跑起來會有幾個坑。我踩過之后總結(jié)了幾條寫出來供大家參考。第一上層方案變化太劇烈會導(dǎo)致下層評估結(jié)果不穩(wěn)定。比如上一代車輛的訪問順序變化不大但起降點位置做了一次大變異下層重新規(guī)劃出來的覆蓋路徑可能完全不同適應(yīng)度值上躥下跳進化過程很難收斂。解決思路是給起降點位置的變異加一個最大偏移限制讓每次迭代的搜索步長保持溫和。第二下層求解要保留一點隨機性。如果下層每次都返回確定性的貪心解上層會看見一個非常鋸齒狀的適應(yīng)度曲面很難判斷哪個方案是真的好。我在實現(xiàn)時會給下層貪心加一點擾動或者對相似方案緩存并復(fù)用下層結(jié)果用來減少重復(fù)計算。第三時間窗口的傳遞必須在上下層之間顯式建模。下層求解時無人機起飛和返航時間不能超過車輛在起降點的停留窗口而上層適應(yīng)度評估時又要計算車輛在某起降點需要停留多久必須取該起降點全部無人機航段的最大返航時間。這個雙向依賴如果有一邊處理得含糊最終生成的方案在仿真里能跑一到實物聯(lián)調(diào)就出現(xiàn)車走早了無人機懸停在半空的故障。4. 實驗設(shè)置與效果復(fù)盤4.1 三類對比方案怎么設(shè)計看實驗設(shè)計是最能判斷一篇工作含金量的地方。這篇論文的實驗沒有只做自己方案的自我展示而是拉了多個強對比典型的有下面這幾類純車輛方案只用地面車輛執(zhí)行所有目標點覆蓋車輛必須繞路到每個目標點附近如果需要覆蓋的點在不可達區(qū)域內(nèi)則該方案直接表現(xiàn)很差。這類對比的意義在于證明無人機參與的必要性。純無人機方案不考慮地面車輛運輸把所有無人機集中在一個中心起降點讓它們飛到所有區(qū)域執(zhí)行覆蓋。這個方案的軟肋在于無人機飛行的距離非常長續(xù)航約束把任務(wù)的可行范圍限制得很小為了覆蓋遠端區(qū)域必須設(shè)置很多中間換電池站點現(xiàn)實中根本不經(jīng)濟。單層協(xié)同方案把車輛和無人機放在同一個模型里統(tǒng)一求解不做分層。這種方案的對比意義在于證明分層規(guī)劃在性能和求解時間上的平衡點是可接受的。雙層協(xié)同方案就是論文提出的方法。實驗里通常會在不同規(guī)模的任務(wù)區(qū)域、不同數(shù)量的目標點、不同數(shù)量無人機配置下做橫向?qū)Ρ瓤纯偤臅r、覆蓋率、能耗、求解時間四個維度上的表現(xiàn)。4.2 關(guān)鍵指標怎么選這里有個地方值得強調(diào)覆蓋率不是唯一的指標。很多論文把覆蓋率刷到99%就收工了但在實際應(yīng)用中超出的那1%覆蓋代價可能非常大——無人機多繞一圈、車輛多等半小時、能耗翻倍這些都是隱性成本。這篇工作采用的評價體系更完整總完成時間反映整體調(diào)度效率覆蓋率反映任務(wù)被執(zhí)行的程度總能耗反映經(jīng)濟性求解時間反映算法的實用性。這四個指標之間其實存在復(fù)雜的權(quán)衡。比如讓無人機以更高的飛行速度執(zhí)行任務(wù)能縮短總完成時間但能耗會快速上升讓車輛在起降點多等一會兒無人機可以飛更大的覆蓋回路覆蓋率會更高但總耗時被拉長。論文里對這些權(quán)衡做了分析結(jié)果也符合我對這類系統(tǒng)的認知雙層規(guī)劃在總完成時間上明顯優(yōu)于純車輛和純無人機方案覆蓋率接近單層協(xié)同方案而求解時間比單層優(yōu)化降低了不止一個數(shù)量級。4.3 典型結(jié)果說明什么我根據(jù)實驗部分展示的信息把典型結(jié)論整理成下面這張表方便直觀對比方案總完成時間覆蓋率能耗求解時間純車輛高低受地形限制低短純無人機高受限續(xù)航中遠端難以覆蓋高中單層協(xié)同低高中高很長雙層協(xié)同本文低高中短表格里的低/高是相對趨勢具體數(shù)值在不同配置下會有差別但方向是一致的。最值得注意的一行是求解時間單層模型在很多實驗配置下已經(jīng)無法在合理時間內(nèi)收斂而雙層協(xié)同由于把問題拆成兩個子問題分別求解求解時間被壓縮到了可控范圍這才使得該方法有實際工程使用的可能性。從這些結(jié)果里我能讀出這篇工作的核心論點雙層規(guī)劃不是簡單的啟發(fā)式妥協(xié)而是一種針對大規(guī)模多區(qū)域覆蓋問題的有效降維策略。犧牲一小部分理論最優(yōu)性換取計算可行性和方案可落地性這對實際應(yīng)用場景來說完全是劃算的買賣。5. 落地適配點與我的實操經(jīng)驗5.1 哪些真實場景能直接套讀懂論文的價值在于能把它遷移到實際項目里。這套車機協(xié)同雙層覆蓋的工作流可以直接適配的場景比我預(yù)想的多。末端物流配送地面車停在小區(qū)或園區(qū)外圍的臨時?？奎c無人機把包裹送到各個樓棟門口。無人機不需要飛到很遠的倉庫只需要在車輛周圍幾百米到一兩公里內(nèi)做點對點運輸續(xù)航不再是瓶頸。農(nóng)業(yè)植保大片農(nóng)田被道路分隔成很多地塊地面車輛攜帶藥箱和無人機在每個地塊邊沿停一下無人機起飛噴灑噴灑完回到車輛上換藥換電池再趕往下一地塊。這個模式能顯著減少轉(zhuǎn)場時間提高作業(yè)效率。電力與管道巡檢巡檢點往往沿線路延伸幾公里甚至幾十公里車輛沿檢修道路移動無人機負責對塔基、管道上方等人工難以到達的位置做精細檢查車機協(xié)同能大幅壓縮巡檢周期。應(yīng)急勘察災(zāi)害發(fā)生后地面車輛在安全區(qū)域移動無人機進入危險區(qū)域采集影像。雙層規(guī)劃的優(yōu)勢在于可以快速加入禁飛區(qū)、通信盲區(qū)等臨時約束生成可執(zhí)行的任務(wù)方案。這些場景共同的特點是覆蓋目標分散、區(qū)域之間存在不可達地形、任務(wù)時間窗口敏感。論文中的模型不一定能直接零改動套用但框架結(jié)構(gòu)非常值得借鑒。5.2 調(diào)參與實現(xiàn)中的細節(jié)在實際復(fù)現(xiàn)類似框架時有幾個參數(shù)和細節(jié)我覺得需要花時間調(diào)寫出來供參考。車輛速度與無人機速度的比例關(guān)系非常關(guān)鍵。如果車輛速度太慢無人機任務(wù)做完了但車還沒到下一個起降點系統(tǒng)瓶頸就變成車輛如果車輛速度太快車輛等無人機完成任務(wù)的空閑時間過長系統(tǒng)瓶頸又變成無人機。上層優(yōu)化會在兩者之間找平衡但對初始參數(shù)的敏感度很高。我的經(jīng)驗是先按實際底盤和機型的速度標定好再跑上層進化算法不要讓模型在虛設(shè)參數(shù)上瞎搜。起降點的候選位置要給足數(shù)量。很多復(fù)現(xiàn)者圖省事直接把子區(qū)域的幾何中心作為唯一的起降點這會嚴重限制上層搜索空間。正確做法是把道路交叉口、車輛可合法?？康呐R時點、信號覆蓋良好的位置都列進候選集讓上層有充分的自由度去選擇。下層算法的續(xù)航余量要留一點安全系數(shù)。仿真里設(shè)定的最大航時往往和真實工況差很多風速、電池老化、載荷重量都會影響實際續(xù)航。我通常在規(guī)劃時把無人機最大航時乘一個0.8左右的折扣系數(shù)寧可讓規(guī)劃結(jié)果保守一點也不要在實際執(zhí)行時出現(xiàn)返航電量不足的險情。還有一個細節(jié)是關(guān)于時間緩沖的。車輛到達起降點后無人機從起飛到完成全部任務(wù)、再降落回車輛整個過程不一定正好落在車輛停留窗口內(nèi)。規(guī)劃時如果卡得太死實際執(zhí)行中無人機晚到幾秒、車輛就得到處找地方重新規(guī)劃。我在聯(lián)調(diào)時習(xí)慣給每個起降點加30秒到1分鐘的安全緩沖區(qū)雖然總耗時稍微增加但系統(tǒng)的魯棒性會顯著提升。提示對新手來說最容易出問題的地方是下層規(guī)劃返回的覆蓋時長沒有回傳到上層做時序約束——檢查你的兩層接口是否完整傳遞了時間信息這比優(yōu)化算法本身更影響最終效果。5.3 局限性與后續(xù)可擴展的方向論文的方法當然不是銀彈。雙層結(jié)構(gòu)的一個固有問題在于如果上下層之間的目標沖突很強比如車輛路線和無人機航跡強耦合分層迭代很容易陷入局部最優(yōu)。論文對此的處理是依賴進化算法的全局搜索能力和迭代次數(shù)但理論上不保證接近全局最優(yōu)。如果想要更好的解質(zhì)量可以在上層迭代中加入對候選車輛路線做局部鄰域搜索的策略見效明顯。另外論文的模型在動態(tài)環(huán)境下的擴展還不充分。真實場景里風速會變、目標點可能臨時增加、車輛可能因為交通堵塞而延誤這些動態(tài)擾動要求系統(tǒng)具備滾動重規(guī)劃能力。也就是說當前方案是一條靜態(tài)的計劃但實際任務(wù)執(zhí)行時通常還需要一個執(zhí)行-監(jiān)控-局部重規(guī)劃的閉環(huán)這也是我從這篇工作往外延伸時特別想補的一環(huán)。我個人的體會是這套雙層規(guī)劃框架最大的價值不在于一次規(guī)劃出完美方案而在于它把宏觀調(diào)度和微觀覆蓋兩個層面徹底解耦了讓工程團隊可以分別優(yōu)化、分別驗證、分別調(diào)參這對復(fù)雜系統(tǒng)落地來說非常友好。如果你正在做類似的車機協(xié)同項目先把上下層的數(shù)據(jù)接口定義清楚再把車輛等待和無人機等待這兩端的時間賬算明白你的系統(tǒng)就已經(jīng)跑贏大半的規(guī)劃算法了。