孔國杰，馮時，于會龍，巨志揚，龔建偉

(1.北京理工大學 機械與車輛學院，北京 100081;2.32398 部隊，北京 100192)

0 引言

地面無人集群系統(tǒng)由多個同構或異構的無人車構成，是共同完成統(tǒng)一目標的協(xié)作系統(tǒng)，在軍事［1-3］、生產［4］、物流［5］、交通［6-7］等各個領域能夠發(fā)揮重要作用，其典型應用場景如圖1 所示。多車協(xié)同系統(tǒng)協(xié)同涉及交通流優(yōu)化［8-9］、智能任務調度分配［10-12］、多智能體協(xié)同定位［13-14］、協(xié)同規(guī)劃控制［15-24］等多個研究方向，目前，在智能車輛、智能交通、機器人等方向的研究及應用領域，已經取得了許多優(yōu)秀成果。隨著車與外界(V2X) 通信技術的發(fā)展［25-27］，無人車輛能夠通過網絡通訊與其他車輛、網絡設備、路面基礎設施等進行互聯(lián)，單無人車輛獲取信息的范圍逐漸擴大，并能夠基于交互信息進行分析決策，進一步促進了車車、車網、車路之間的信息交互，從而使得多車協(xié)同系統(tǒng)有了更廣泛的應用場景。

圖1 多車協(xié)同系統(tǒng)應用場景Fig.1 Applications of cooperative motion planning

多車協(xié)同系統(tǒng)能夠實現(xiàn)更合理的資源分配和任務分配，以及提高復雜任務的執(zhí)行容錯率和魯棒性，在執(zhí)行各類復雜任務，如大面積環(huán)境探索［12］、集群打擊［28-29］、倉儲物流［5］、協(xié)同施工作業(yè)時［30］，具有更大的優(yōu)勢。此外，多車協(xié)同系統(tǒng)有利于提升交通通行效率、改善擁堵狀況、減少污染排放與能源消耗，對系統(tǒng)整體效率提升及能耗降低有著重要的作用［31-33］。多車協(xié)同系統(tǒng)是多智能體系統(tǒng)的一個典型實例［34-38］，每輛無人車可看作一個智能體，在多個智能體協(xié)同行駛或作業(yè)時，會不可避免地產生運動軌跡沖突問題。僅依靠單一平臺的感知、決策和控制進行“孤島式”的相互避障策略，易受到環(huán)境及傳感器等因素的干擾，造成車輛避讓策略失誤，導致危險情況的發(fā)生，既無法滿足多車協(xié)同系統(tǒng)的安全性需求，亦不能充分發(fā)揮多車協(xié)同系統(tǒng)的優(yōu)勢，這就產生了協(xié)同決策規(guī)劃的需求。

本文針對多車協(xié)同系統(tǒng)的協(xié)同運動規(guī)劃技術展開調研，對現(xiàn)有方法進行總結和分類，并針對不同技術類型的特點進行詳細分析。

1 國內外發(fā)展現(xiàn)狀概述

1.1 國外多車協(xié)同技術及應用場景概述

國外多車協(xié)同系統(tǒng)研究起步較早。早期研究由于硬件限制，大部分針對于小規(guī)模的多車協(xié)同系統(tǒng)，更多利用單體智能，依靠簡單規(guī)則和交互完成多車協(xié)同。1996 年加拿大Alberta 大學Kube 等［15］研發(fā)了Collective Robotics 多車協(xié)同任務系統(tǒng)，實現(xiàn)了多個無人平臺的協(xié)作推箱任務;1994 年美國加州大學PATH 項目進行了高速環(huán)境下的多車協(xié)同行駛實驗，實現(xiàn)了多車編隊穩(wěn)定行駛、加速、跟隨車輛進入及離開編隊等［16］。近年來，隨著計算平臺算力的提升和通信技術的發(fā)展，多車協(xié)同系統(tǒng)向著大范圍作業(yè)、集群規(guī)?；?、協(xié)同智能化的方向快速發(fā)展，研究人員將單車路徑規(guī)劃、模型預測控制(MPC)［39-43］、博弈論［44-46］等理論引入多車協(xié)同系統(tǒng)中，在理論探索和實驗研究方面取得了大量進展。Gerdts 等［17］將多車協(xié)同問題表述為一個帶有反碰撞約束的順序規(guī)劃問題，并通過求解障礙物包圍下的車輛最快無碰撞軌跡實現(xiàn)多車協(xié)同;英國Bucharest 大學Gabriela 等［18］通過建立交通管制決策優(yōu)化目標，提出了一種4D 空間多車沖突檢測和沖突解決的優(yōu)化方法，通過調整速度及軌跡的中長期避讓策略和通過調整航向的短期避讓策略實現(xiàn)協(xié)同規(guī)劃;荷蘭代爾夫特理工大學Zhu 等［19］提出一種考慮運動不確定性的分布式多車協(xié)同規(guī)劃方法，將每個智能體與實體的碰撞概率約束構建為機會約束，通過假設不確定性符合高斯分布，將機會約束轉化為確定性線性約束，并基于分布式MPC 求解多智能體的無沖突路徑。

除了理論方面的探索外，在實際應用方面，國外許多科研單位也對多車協(xié)同系統(tǒng)進行了一系列的探索，如美國航空航天局(NASA) 為實現(xiàn)外星球資源與環(huán)境探索目標，設立Swarmie 項目［20］，利用多個具有感知、定位與通信功能的無人車，實現(xiàn)協(xié)同大面積未知區(qū)域探索，如圖2(a) 所示。美國海軍研究辦公室對水陸兩棲小型無人戰(zhàn)車集群展開研究，實現(xiàn)了多車協(xié)同兩棲作戰(zhàn)能力的提升。歐盟設立Martha課題，開展多車協(xié)同搬運方面的研究，旨在提升多車協(xié)同系統(tǒng)的工作效率和能力。

圖2 國內外多車協(xié)同系統(tǒng)研究現(xiàn)狀Fig.2 Research status of cooperative multi-vehicle systems

1.2 國內多車協(xié)同技術及應用場景概述

與國外相比，國內對多車協(xié)同系統(tǒng)的研究開展相對較晚，然而，隨著近年來我國技術實力的快速提升與人工智能技術的快速突破，產生了許多有價值的理論研究成果與實際應用［47-50］。清華大學Xu 等［7］針對部分車聯(lián)網環(huán)境下的多車隊列協(xié)同避讓問題，提出了相對動能密度的概念，在車聯(lián)網環(huán)境下設計了總相對動能密度最小的多車協(xié)同控制算法。北京理工大學毛昱天等［38］針對初始通信網絡拓撲為強連通非平衡圖條件下的多車協(xié)同控制問題進行研究，在系統(tǒng)中存在和不存在領航者的條件下實現(xiàn)多車協(xié)同系統(tǒng)的分布式集群控制，實現(xiàn)了多車集群的編隊行駛，如圖2(b) 所示。

此外，國內許多研究機構與企業(yè)也紛紛開始探索多車協(xié)同系統(tǒng)的實際應用［51-53］。陸軍裝備部“跨越險阻2021 陸上無人系統(tǒng)挑戰(zhàn)賽”中加入無人車編組快速突擊組別、陸空無人系統(tǒng)集群偵查打擊組別等，將多無人系統(tǒng)集群作戰(zhàn)概念運用到復雜地形、復雜天候和復雜電磁環(huán)境下，有力提高了多車協(xié)同系統(tǒng)在軍用領域的實際應用水平，為占領未來智能化陸戰(zhàn)制高點提供技術儲備。京東物流將多車協(xié)同系統(tǒng)應用于倉儲物流領域，在其倉儲配送中心使用百余臺具備環(huán)境感知、自主定位、協(xié)同作業(yè)等功能的物流機器人對快遞進行快速分揀，如圖2(c) 所示。

2 多車協(xié)同系統(tǒng)協(xié)同運動規(guī)劃框架分類

多車協(xié)同規(guī)劃算法的整體框架類型主要分為集中式框架、分布式或分散式框架［54］，以及分層分布式或混合框架，如圖3 所示。

圖3 多車協(xié)同規(guī)劃算法框架Fig.3 Framework of multi-vehicle path planning

集中式框架［55］是指中央控制器計算所有被控車輛的運動軌跡，并發(fā)布給各車需執(zhí)行的控制量或控制參考量。由于各車需要與中央控制器直接進行有關控制量的信息傳輸，常常要求所有被控車輛是網聯(lián)式的，并且各車之間能相互通信或車輛與基站之間(V2I) 能相互通信［56］。集中式框架的優(yōu)點是能獲取所有車輛的確定性狀態(tài)信息，從而能采用多無人車整體優(yōu)化的方法實現(xiàn)規(guī)劃結果的全局最優(yōu)性。當計算規(guī)模小時，若采用高性能計算機作為中央控制器來實行并行計算，足夠滿足計算效率的要求。然而，當被控車輛數(shù)目增加時，由于僅在一個機器上求解，計算代價和通信負擔顯著增加。這也是限制集中式框架廣泛應用的主要原因。Li 等［54］將多車運動規(guī)劃問題統(tǒng)一為集中式框架下考慮避免碰撞約束的最優(yōu)控制問題，并提出一種基于初始化的計算框架——漸進約束動態(tài)優(yōu)化框架(PCDO) 以減少中央控制器的計算負擔，最終以多車協(xié)同停車任務驗證了軌跡規(guī)劃結果的最優(yōu)性。

分散式框架或分布式框架是指各車有自己獨立的控制器，承載各自軌跡規(guī)劃任務［57］。一方面，對于大規(guī)模的無人車環(huán)境，將原始的多無人車全局優(yōu)化問題分解為多個次優(yōu)的子問題，由各車分攤計算負擔，保證實時運行效率;另一方面，對于無人車覆蓋率小于100%的環(huán)境，車輛在無法通過直接通信獲取其他車輛狀態(tài)信息的情況下，需自行通過感知預測等模塊觀測其他交通參與者的狀態(tài)和行為，并以此進行規(guī)劃。Mirheli 等［58］提出了一種在無信號燈路口進行協(xié)調駕駛的分布式規(guī)劃控制邏輯DCSICL，與其此前提出集中式框架方法SICL［59］相比，能以更少的CPU 計算時間來生成接近最優(yōu)的車輛軌跡，并且分布式算法框架不會隨著被控車輛數(shù)目的增多而延長運行時間。整體而言，通常分布式框架犧牲解的全局最優(yōu)性以換取更高的計算效率。

分層分布式框架也稱混合框架，結合了集中式和分布式框架的優(yōu)點［60-62］。在此框架中，中央控制器可以通過與各被控車輛通信來進行集中式的規(guī)劃與控制，同時，各被控車輛之間又可以通過與相鄰車輛的通信來協(xié)同完成一定的任務。在此協(xié)同框架下，各車輛既受中央控制器的統(tǒng)一規(guī)劃任務控制，又保留了一定的車間協(xié)同自主性。分層分布式協(xié)同規(guī)劃框架既保留了集中式框架的全局最優(yōu)性，又保留了分布式框架的可擴展性及魯棒性的優(yōu)點，可以在求解質量和規(guī)劃的時間成本之間取得一個較好的平衡。

綜上所述，各類多車協(xié)同規(guī)劃算法框架都有其適用范圍，在求解規(guī)模不大且對解的質量要求高時，優(yōu)先考慮集中式框架;而對于系統(tǒng)規(guī)模較大或存在非網聯(lián)車輛的情況，需要保證車輛有一定的分布式計算能力。

3 多車協(xié)同系統(tǒng)協(xié)同運動規(guī)劃算法分類

在多車協(xié)同系統(tǒng)中，多車協(xié)同決策規(guī)劃模塊需要計算多個車輛在未來一段時間內的無沖突運動軌跡。需要在考慮多個車輛可能存在的運動沖突的同時，考慮環(huán)境因素、車輛自身結構和車輛動力學特性等因素對車輛運動軌跡帶來的限制，在較短時間內規(guī)劃出多車運動相互之間無沖突、安全且易于控制模塊進行軌跡跟蹤的運動軌跡。本節(jié)基于多車協(xié)同系統(tǒng)的框架分類，對不同框架下的算法進行整理，并分析其特點。

3.1 集中式框架下的多車協(xié)同規(guī)劃方法

集中式框架采用中心節(jié)點計算、車輛節(jié)點執(zhí)行的方案，由中央計算設備對所有車輛的軌跡進行實時規(guī)劃［54］，車輛負責跟蹤執(zhí)行所接收到的路徑結果?；诩惺娇蚣艿膮f(xié)同規(guī)劃方法通?？梢杂嬎愠鋈肿顑?yōu)軌跡，提升系統(tǒng)的執(zhí)行效率和協(xié)同效果，廣泛應用于倉儲物流、集群打擊等場景，然而，由于集中式框架對于通訊狀態(tài)和中心節(jié)點計算能力要求都十分高，在面對野外大面積探索、農業(yè)作業(yè)等作業(yè)區(qū)域較廣、通訊延時較大的非結構化道路場景任務時表現(xiàn)一般。目前集中式框架下的多車協(xié)同主要包括基于搜索算法和基于優(yōu)化控制的方法。

3.1.1 集中式框架下的多車協(xié)同規(guī)劃方法

在集中式的多車協(xié)同規(guī)劃中一類方法是在單車路徑搜索算法的基礎上進行改進而來［63］，此類方法中在單車搜索算法之上添加了對路徑沖突的處理機制，其中路徑沖突主要有兩種: 碰撞沖突和交換沖突［64］。此類方法中一類是基于A*搜索算法的方法［65-66］，例如局部修復A*算法(LRA*) 和分層合作A*算法(HCA*) 等。此類算法隨著車輛數(shù)量和環(huán)境復雜度增加，可擴展性差。為解決這個問題，目前基于路徑搜索的算法最常用的是沖突搜索(CBS)算法［67］。

基于沖突搜索的多車協(xié)同規(guī)劃方法從基于搜索的單車規(guī)劃方法基礎上發(fā)展而來，是近幾年提出的專門用于求解多車協(xié)同規(guī)劃問題的一類分層搜索算法。經典算法包括CBS 算法［68-69］、改進沖突搜索(ICBS) 算法［70］、增強沖突搜索(ECBS) 算法［71］等。

CBS 算法把多車路徑規(guī)劃問題視為多個單車路徑規(guī)劃問題，上層算法找到多車路徑之間的沖突，并通過分裂結點的方式在下層搜索中添加多車路徑約束條件，下層算法解決多個單車路徑規(guī)劃問題，在基于搜索的路徑規(guī)劃算法基礎上滿足多車路徑約束，從而解算多車無沖突路徑［72-73］。在CBS 算法中，下層算法的單車路徑搜索過程與普通的路徑規(guī)劃方法類似，不同之處在于搜索過程中需要額外考慮由上層算法添加的沖突約束以及在搜索過程中需要考慮原地等待等情況。CBS 算法流程如圖4［74］所示，其中圓點代表車輛的初始位置，星號代表各車輛的目標位置，連接初始點和目標點的實線代表相應車輛從初始位置到目標位置的路徑;填充顏色的方塊代表兩車路徑的沖突結點。兩輛車在初始時刻分別由下層算法規(guī)劃各自的路徑，二者在黃色結點處產生路徑沖突，因此需要生成新的分支。為消解沖突，在第2 層左側節(jié)點處添加沖突約束為藍色車輛不能通過沖突結點，右側節(jié)點處添加沖突約束為紅色車輛不能通過沖突結點。在相應的沖突約束下，下層規(guī)劃算法重新對兩輛車進行路徑規(guī)劃，并重復以上步驟，直至生成無沖突路徑。相較于基于A*算法的協(xié)同規(guī)劃方法，用A*整體規(guī)劃求解多車協(xié)同問題需要在擴展同時考慮各車之間的沖突，生成大量無意義的節(jié)點，CBS 算法通過添加約束解決沖突，求解效率更高。然而，在車輛數(shù)量較多的高度競爭圖中，CBS 由于不能檢測到獨立的子問題，其性能會迅速下降，因此出現(xiàn)了眾多基于CBS 的改進和優(yōu)化算法。

圖4 CBS 算法示意圖［74］Fig.4 Illustration of CBS algorithm［74］

ICBS 算法在原始算法的基礎上，提出了元智能體的概念，將兩個沖突的車輛合并為一個元智能體，從而減少上層分裂結點的次數(shù)［71，75-76］;此外，CBS算法并不對沖突進行分類，并任選沖突進行拆分，性能受沖突選擇影響大，ICBS 算法將運動沖突進行劃分，并提取出主要沖突、半主要沖突以及非主要沖突，通過優(yōu)先對主要沖突和半主要沖突進行解決，從而提高算法的實時性。Barer 等［71］基于CBS 算法，在上下層搜索中將最優(yōu)搜索改為聚焦搜索，得到增強型CBS 算法，可以求得具有可控近似比的多車協(xié)同規(guī)劃問題的近似解。聚焦搜索充分利用了上層解之間的沖突信息，使下層搜索更容易避免沖突。Cohen 等［77］在多車協(xié)同規(guī)劃問題的原始圖內引入了高速路，在高速路上的車輛只能單向行駛，改進后的算法下層搜索類似加權A*算法，該算法也可以求得多車協(xié)同規(guī)劃問題的近似最優(yōu)解。Cohen 等［78］將高速路方法加入到ICBS 算法、ECBS 算法中測試，發(fā)現(xiàn)算法求解性能都得到了提高，并且提出了兩種針對物流倉儲這種場景下的高速路生成算法，使得高速路生成得以自動化。

總的來說，基于沖突搜索的多車協(xié)同規(guī)劃方法具有算法完備性，能夠在大面積、多車路徑耦合度高的場景下具有良好的表現(xiàn)，然而其算法框架對中心計算節(jié)點的計算能力要求高，且算法實時性一般，難以滿足車輛速度較快的多車協(xié)同場景需求。

3.1.2 基于優(yōu)化控制的集中式多車協(xié)同規(guī)劃方法

基于優(yōu)化的多車協(xié)同規(guī)劃方法在集中式和分布式框架下都有著廣泛的應用，集中式框架下的優(yōu)化方法將所有被控車輛的運動軌跡作為優(yōu)化對象，相比于單車中基于優(yōu)化的路徑規(guī)劃算法，多車協(xié)同規(guī)劃的優(yōu)化問題需要考慮被控對象之間避免運動軌跡沖突的約束?；趦?yōu)化的算法核心在于優(yōu)化目標的選擇和約束條件的構建，其中最典型的算法為預構建碰撞檢測算法。

預構建碰撞檢測算法根據(jù)車輛特性和車輛約束生成一系列候選軌跡簇［79-82］，構成車輛運動基元庫，并分析多車運動基元庫之間兩兩時空三維坐標系下的碰撞可能性，從而預構建碰撞矩陣或碰撞判別準則。作為優(yōu)化模型的約束，各車基于車輛運動基元庫選擇候選軌跡，并滿足與其他車輛的軌跡之間無碰撞約束，從而實現(xiàn)多車協(xié)同規(guī)劃，在小規(guī)模場景下具有良好的應用效果，如車道并線［79］、匝道匯入［80］等，如圖5 所示。算法具有全局最優(yōu)性，保證了協(xié)同效率。然而由于預構建碰撞檢測算法需要將多車軌跡離散為一系列碰撞矩陣，當車輛數(shù)目和交互區(qū)域較大時，難以保證離散后求解空間內算法的完備性和實時性。

圖5 基于預構建碰撞檢測法的多車協(xié)同規(guī)劃算法［79］Fig.5 Multi-vehicle cooperative planning algorithms based on pre-constructed collision detection［79］

3.2 分布式框架下的多車協(xié)同規(guī)劃方法

分布式框架是一種去中心化方案，去除了中心計算節(jié)點，將一個全局運動軌跡規(guī)劃問題拆解成各車運動規(guī)劃子問題，由車輛自身計算平臺獨立承載各自軌跡規(guī)劃任務［83-84］。由于分布式框架僅計算單車自身的運動軌跡，對于硬件設備計算能力的需求大大降低，而且不會隨著被控車輛數(shù)目的增多而延長運行時間，提升了系統(tǒng)的實時性，且具有不依賴中心計算節(jié)點的優(yōu)點，防止因為中心計算節(jié)點的故障導致整個系統(tǒng)的癱瘓，增強了系統(tǒng)的靈活性和魯棒性。然而由于分布式系統(tǒng)僅處理與自己相關的信息，并不對全局運動軌跡進行整體處理，每個車輛的規(guī)劃結果可收斂到納什均衡，但非帕累托最優(yōu)解，即每個無人車都能達到自己期望的最優(yōu)解，但無法收斂至全局最優(yōu)［85-86］。此類方法在難以布設中心計算節(jié)點的非結構化道路下具有更加靈活的優(yōu)勢，但在城市十字路口交通調度一類需要最大化通行效率的場景下表現(xiàn)一般，目前主要有以下4 種方法。

3.2.1 基于優(yōu)化的分布式多車協(xié)同規(guī)劃方法

在分布式框架中，優(yōu)化方法將各車通行順序或自車運動軌跡作為優(yōu)化對象，目前主要方法有人工勢場法、安全走廊法、點對點安全距離或安全時距法等。

人工勢場法的基本思想是在目標處設計一個吸引勢［87-93］，在障礙物處構造一個排斥勢，在車輛運動過程中，車輛會遵循勢的梯度，計算出被目標吸引，被障礙物排斥的路徑［94］。Lienke 等［87］將協(xié)同規(guī)劃問題簡化為靜態(tài)障礙物或短時動態(tài)障礙物避障，各個車輛基于通信系統(tǒng)或預測信息獲取其他車輛的運動軌跡并進行風險評估，從而構建勢場地圖實現(xiàn)多車協(xié)同規(guī)劃，如圖6(a) 所示，其中上圖縱軸代表人工勢場勢能大小，下圖為勢場的可視化圖，顏色越深代表勢場值越大。基于人工勢場法的規(guī)劃方法由于其簡單高效、生成路徑平滑的優(yōu)勢，在近20 年來得到了廣泛的關注。然而，人工勢場法的性能依靠勢場函數(shù)的設計，容易導致局部極小值問題，車輛路徑受到目標點附近障礙物的排斥后始終在終點附近振蕩，無法收斂到終點值，此外，人工勢場法將障礙物描述為斥力，本質上是一種軟約束，在道路環(huán)境復雜的非結構化場景下易產生危險，難以保證絕對的安全性。

安全走廊法將當前時刻其他車輛的運動軌跡在本車的三維時空地圖下進行投影占據(jù)［95-106］，并在可通行區(qū)域上提取對應的安全走廊，在安全走廊下獲取優(yōu)化變量對應的邊界，從而構建帶有約束的優(yōu)化問題，快速求解自身運動軌跡。Klischat 等［96］將可通行區(qū)域進行提取并構建一個有向圖來存儲，從而表示可在對應單元格通行的時間，如圖6(b) 所示。由于其他車輛軌跡、動靜態(tài)障礙物在本車三維時空地圖下的占據(jù)往往表現(xiàn)為非凸形式，需要將其建模為非凸優(yōu)化問題，Liu 等［98］在非凸空間障礙物占據(jù)下提取對應優(yōu)化變量的凸可通行區(qū)域，從而將非凸優(yōu)化問題轉換為凸優(yōu)化問題，提升了優(yōu)化求解的效率，如圖6(c) 所示，其中Convex Feasible Set(CFS) 代表凸可行集合，New Reference Point 表示新參考點，Optimal Solution in the CFS 表示凸可行集合中的最優(yōu)解。基于安全走廊法的多車協(xié)同規(guī)劃方法在大部分場景下具有良好的表現(xiàn)，當優(yōu)化模型的目標函數(shù)和約束建立合理時，具有良好的求解效率。基于凸可行集的協(xié)同規(guī)劃方法具有普適性，能應對一般交互場景［96，100-101］，在車輛與車輛交互場景［102-103］、車輛與行人交互場景［104-105］均有應用。然而，與基于安全距離的方法類似，上述方法僅能在單個時間周期內進行優(yōu)化，沒有利用到預測軌跡的動態(tài)信息。Ding 等［106］將安全走廊擴展到時空三維構型空間里，規(guī)劃出避開動態(tài)障礙物的協(xié)調軌跡。

圖6 基于優(yōu)化的分布式多車協(xié)同規(guī)劃算法Fig.6 Distributed multi-vehicle cooperative planning based on optimization

基于安全距離或安全時距的約束條件直接考慮同一時刻各車的空間位置關系，能方便地嵌入到多車協(xié)同優(yōu)化問題中。由于安全距離僅考察各車在二維空間上的沖突問題，因此大部分的優(yōu)化問題采用MPC 的滾動優(yōu)化思想［107］在每個時間采樣步內構建安全時距約束，要求車輛i 與車輛j 之間的距離或時間差大于閾值，這類約束條件在高速匝道并道［108-110］、換道［111-113］等場景中十分常見。同時，在車輛隊列［114-116］或編隊行駛［117］時，各車間距能作為功能性約束進行隊形的引導和保證?；诎踩嚯x或安全時距的約束條件構建簡單方便，但由于只能在單個時間采樣周期進行優(yōu)化，難以直接用于軌跡規(guī)劃，更常用于控制策略的設計。

3.2.2 基于速度障礙的多車協(xié)同規(guī)劃方法

基于速度障礙(VO) 的多車協(xié)同規(guī)劃方法［93，118-120］的基本思想是計算兩車相對速度，若相對速度的方向在寬度為二者半徑之和的扇區(qū)內，則兩車在未來某個時間點必然會發(fā)生碰撞，故將障礙扇區(qū)相對于另一車輛的速度進行平移，即為本車的絕對速度障礙區(qū)，車輛求取在障礙區(qū)范圍之外使得當前速度抖動最小的相對速度，從而避免碰撞發(fā)生［121］，如圖7(a) 所示。基于速度障礙的方法易導致車輛速度抖動問題，由于車輛之間僅交互速度信息，當其他的車輛也采取同樣的回避措施時，兩車會不斷進行相互避讓，造成車輛運動的抖動?；セ菟俣日系K(RVO) 算法［122］假設其他車輛會分擔一半的避讓責任，減小對自身當前扇形障礙區(qū)的偏移程度，從而解決抖動問題，如圖7(b) 所示。此類方法由于分布式特性、算法實時性高、僅需交互車輛速度信息的優(yōu)點，在仿真、游戲等領域有著十分廣泛的應用。然而，由于此類方法僅依據(jù)其他車輛當前速度信息進行避讓，在車輛速度較高的場景下并不具有良好的適應性，且由于此類算法將車輛上一幀的速度作為當前幀的預期速度，在轉彎及避讓其他車輛時易出現(xiàn)異常的預期，造成急轉現(xiàn)象的發(fā)生，不利于車輛的穩(wěn)定行駛。

圖7 速度障礙法［120］Fig.7 Velocity obstacle-based methods［120］

3.2.3 基于博弈論的多車協(xié)同規(guī)劃方法

基于博弈論的協(xié)同規(guī)劃方法［123-125］試圖將所有智能車當作獨立的具有自私性質的理性決策者，并在構建多車之間沖突和協(xié)作交互行為的數(shù)學模型后，各車基于此模型理解與其他交通參與者和環(huán)境的相互作用產生的效益或代價，并最大化主觀效益［126-127］，基于博弈多車協(xié)同規(guī)劃方法更傾向于生成行為決策結果(行為或目標點) 而非確定的運動軌跡［128］，如圖8 所示。

圖8 基于博弈論的多車協(xié)同規(guī)劃方法［127］Fig.8 Game theory-based multi-vehicle cooperative planning

完整的數(shù)學模型需要定義博弈對象、博弈者能獲取的信息(觀察函數(shù)) 和能執(zhí)行的操作(轉移函數(shù))，以及操作帶來的相應收益或損失(回報或收益函數(shù))［129-130］?；诓┺恼摰膮f(xié)同規(guī)劃方法又可分為合作型博弈和非合作型博弈兩類，前者表示一些交通參與者以外部強制約束方式(或稱合同) 構成利益共同體并以此為博弈最小單位，而后者僅以本車作為受益者。Lin 等［131］基于合作型博弈方法構建多車協(xié)同換道模型，各車能以統(tǒng)一的付費方式換取車道通行權，因此能公平地分配合作利益共同體內部各車的收益或損失，保證變道車輛和讓行車輛的雙贏與合作。合作型博弈方法還常用于在車輛隊列行駛場景［132-135］、出租車調度場景［136］等存在典型的利益共同體的場景。然而，由于實際道路中的其他交通參與者，如有人駕駛車輛等不參與合作而僅根據(jù)自己的利益進行運動，非合作型博弈方法也具有必要的應用價值［137］，并且已經在換道場景［138-140］交叉路口［141-142］和環(huán)島［143］等場景中進行了驗證。劉陽［144］結合兩類方法的特點提出一種基于分層運動協(xié)同控制方法，在針對車輛隊列運動協(xié)同規(guī)劃問題中，將隊列內外的路權沖突問題抽象為“隊列內合作，隊列外競爭”的交互問題，從而利用合作型博弈方法和非合作型博弈方法的特點實現(xiàn)各車隊的整體效益最大化。綜上，合作型博弈方法需在存在利益共同體的場景下使用，并且要考慮內部的公平效益分配;同時，兩類博弈方法更傾向于生成規(guī)劃參考量而非確定的規(guī)劃軌跡，如車輛隊列間距、道路通行權等。

3.2.4 基于共識的多車協(xié)同規(guī)劃方法

基于共識的協(xié)同規(guī)劃方法將所有交通參與者納入考慮范圍，各車作為參與者接收他車的意見規(guī)劃和調整本車軌跡，同時對其他網聯(lián)車輛軌跡結果提出要求，最終所有車輛達成共識，實現(xiàn)整體協(xié)調合作［145］。Mirheli 等［146］和Molinari［147］提出一種基于共識的分布式軌跡規(guī)劃算法，該算法針對無信號燈交叉路口的多車軌跡規(guī)劃問題，收集沖突區(qū)域內各車車輛級別的軌跡規(guī)劃結果以更新各車預測軌跡信息，在多次迭代求解后各車規(guī)劃軌跡實現(xiàn)收斂，從而達成共識，將軌跡結果質量推廣到全局最優(yōu)性。此外，基于共識的協(xié)同規(guī)劃方法可以用于設計車輛隊列行駛算法，以促進隊列的弦穩(wěn)定性［148-150］?；诠沧R的協(xié)同規(guī)劃方法應用于分布式框架，盡管能通過迭代方式實現(xiàn)漸進最優(yōu)，但難以直接表征全局目標。

3.3 分層分布式框架下的多車協(xié)同規(guī)劃方法

分層分布式框架中，中心計算平臺通常計算出離散規(guī)劃參考量，并發(fā)布給各車，再由各車以此生成考慮復雜動態(tài)環(huán)境約束和車輛自身運動學等約束的軌跡，既保證了全局結果的質量，也有效降低了算法的復雜度，提升了系統(tǒng)的實時性和實際應用效果。常用的離散規(guī)劃參考量有通行順序［151］、任務點列表［152］以及基準點抵達時間列表［153］等。Ye 等［151］針對高速匝道并道場景提出了一個雙層優(yōu)化邊緣計算模型BOEC 以同時優(yōu)化并道時間和車輛軌跡，其中，最優(yōu)并道時間是由道路單元(RSU) 根據(jù)其收集的V2I 通信范圍內的所有車輛狀態(tài)信息規(guī)劃求解保證，車輛實際執(zhí)行軌跡是由各車在接收RSU 發(fā)布的通行順序后自行生成。此類框架通常采用上述集中式和分布式下的算法進行混合搭配，具有其共同的特點。

4 現(xiàn)有研究的不足與挑戰(zhàn)

本文對目前多車協(xié)同規(guī)劃主流算法的現(xiàn)狀進行剖析，總結出多車規(guī)劃問題仍存在的主要不足:

1) 在算法的多場景適應性方面，目前關于多無人車協(xié)同運動規(guī)劃算法的研究通常僅是對某一特定場景的分析和應用，難以用通用、統(tǒng)一的多車協(xié)同規(guī)劃框架合理地協(xié)調軌跡層約束信息與多車行為層約束信息，其中前者包括軌跡平滑度、與環(huán)境交互安全性等，后者包括整體通行效率、與多無人車之間的交互安全性等。本文將此問題的原因分解為兩個主要的挑戰(zhàn)——實現(xiàn)多車運動規(guī)劃結果全局最優(yōu)性和提高求解效率的權衡挑戰(zhàn)、時空三維避免碰撞約束的高維復雜度挑戰(zhàn)，具體分析如下:

實現(xiàn)多車運動規(guī)劃結果全局最優(yōu)性和提高求解效率的權衡挑戰(zhàn)。目前多車規(guī)劃算法中能實現(xiàn)規(guī)劃結果全局最優(yōu)性的包括有基于博弈論的方法、基于優(yōu)化的方法等，然而，前者僅能求解出離散的規(guī)劃參考量而非完整的軌跡，如道路通行權等，后者在直接將各車軌跡作為優(yōu)化變量求解時，求解耗時隨無人車數(shù)目的增長而急劇增大。而其他多車規(guī)劃算法為了提高求解效率，僅能求解出次優(yōu)結果，如基于共識方法在分布式框架下實現(xiàn)漸進最優(yōu)結果。目前研究針對此挑戰(zhàn)，通常將多車協(xié)同運動規(guī)劃問題限定在固定的場景中，以便利用道路結構特征、行為特征等降低求解復雜度，如為了協(xié)調全局最優(yōu)性和求解效率，十字交叉路口場景中算法根據(jù)道路結構特征為所有車輛分配道路段和通行順序、換道場景中根據(jù)行為特征決策出變換車道行為的合適時機，盡管算法在規(guī)定場景中表現(xiàn)良好，然而，與場景強相關的多車協(xié)同運動規(guī)劃算法難以泛化到其他場景中應用。

時空三維避免碰撞約束的高維復雜度挑戰(zhàn)?，F(xiàn)階段多車規(guī)劃算法在三維時空構型空間里避免碰撞的思路主要有:①通過碰撞檢測篩選出安全的候選軌跡;②通過提取出與其他車輛、障礙物無碰撞的三維可通行空間，并基于該空間邊界生成安全軌跡。前者的代表方法有基于軌跡三維碰撞檢測的方法［80］，但由于目前的三維碰撞檢測方法并不成熟，以及將多車軌跡按照每個時刻進行切片以按照靜態(tài)障礙物碰撞檢測方法進行安全性判斷的方法存在時間消耗過多的問題，因此，實際應用場景有限，僅適用于場景不太復雜、無人車數(shù)目不多的情況。后者的代表方法有基于凸可行集的方法，但目前的方法中在生成安全區(qū)域過程中較少地考慮車輛的可通行能力和由于航向角等變化而引起幾何外形占據(jù)范圍的變化情況。因此，存在軌跡規(guī)劃模塊與安全區(qū)域生成模塊沒有合理協(xié)調的情況，從而導致在給定安全區(qū)域內難以求解出合理的軌跡結果的問題。

2) 在多車軌跡結果的質量方面，目前關于多無人車協(xié)同運動規(guī)劃算法的研究仍存在符合車輛運動特性的多車軌跡縱橫向耦合求解的挑戰(zhàn)，即沒有解決路徑規(guī)劃與速度規(guī)劃耦合問題。多數(shù)運動規(guī)劃算法在處理車輛運動學模型的非完整性約束時，采取的是縱橫向解耦思路或者耦合模型簡化思路。縱橫向解耦思路常用于傳統(tǒng)單車規(guī)劃算法的改進多車算法，如優(yōu)先級分配方式和運動協(xié)調方式分別從路徑層面和速度層面著手。一方面，盡管將三維時空構型空間的問題通過解耦的方式降維處理能降低問題復雜度，但也縮減了實際的解空間，損失了最優(yōu)性;另一方面，解耦方式下路徑規(guī)劃和速度規(guī)劃串聯(lián)運行，有可能導致路徑規(guī)劃結果和速度規(guī)劃結果無法合理協(xié)調的問題產生，如僅在路徑層面選擇較大曲率的路徑繞開其他車輛時，速度規(guī)劃可能仍規(guī)劃出較大的速度而導致車輛失穩(wěn)，或僅在速度層面選擇加減速的方式避讓其他車輛時，路徑層面無法對應修改已經規(guī)劃出的結果，從而導致三維時空空間下軌跡變化明顯而降低舒適性。耦合模型簡化思路是由于直接對三維時空軌跡進行優(yōu)化時，時空邊界獲取難度較高，因此多采用簡單的質點模型或曲線模型，如基于軌跡三維碰撞檢測的方法［80］、基于凸可行集的方法［106］等。這類方法盡管同時對路徑層面和速度層面進行耦合規(guī)劃，但簡化的模型不滿足車輛非完整性約束和動力學特性要求，因此，規(guī)劃的結果存在不利于控制模塊進行跟蹤執(zhí)行的風險。

5 總結

本文針對地面無人集群系統(tǒng)的運動規(guī)劃問題，介紹了問題的背景及應用場景，對無人集群系統(tǒng)中多平臺協(xié)同運動規(guī)劃的各類方法進行了歸納總結和分析。將現(xiàn)有研究中無人集群系統(tǒng)的協(xié)同運動規(guī)劃架構分為三類框架，分別為集中式、分布式及分層分布式框架?；诳蚣芊诸?，在各類框架下對國內外地面無人集群系統(tǒng)中多平臺協(xié)同運動規(guī)劃的各類方法進行了總結，分析了多平臺協(xié)同規(guī)劃技術的研究現(xiàn)狀，總結了各類框架下多車協(xié)同規(guī)劃領域的主流算法，并對每種算法的優(yōu)缺點進行歸納。進而分析了當前地面無人集群系統(tǒng)中多車協(xié)同規(guī)劃技術的發(fā)展現(xiàn)狀及不足之處，提出當前多車協(xié)同規(guī)劃中仍存在的挑戰(zhàn)性問題和未來的研究方向。