寫帖子

最近搜索

    暫無相關數據

  • 個人賬號

  • 企業賬號

注冊 登錄
登錄

無人駕駛中用到的規劃算法

說兩句

圈子: 2019-01-09 17:16:29

無人駕駛中用到的規劃算法

對無人駕駛軟件架構進行分層,大致分成三層:感知層、決策層與控制層。

感知是指無人駕駛系統從環境中收集信息并從中提取相關知識的能力。其中,環境感知(Environmental Perception)特指對于環境的場景理解能力,例如障礙物的位置,道路標志/標記的檢測,行人車輛的檢測等數據的語義分類。 一般來說,定位(Localization)也是感知的一部分,定位是無人車確定其相對于環境的位置的能力。

規劃是無人車為了某一目標而作出一些有目的性的決策的過程,對于無人駕駛車輛而言,這個目標通常是指從出發地到達目的地,同時避免障礙物,并且不斷優化駕駛軌跡和行為以保證乘客的安全舒適。規劃層通常又被細分為任務規劃(Mission Planning),行為規劃(Behavioral Planning)和動作規劃(Motion Planning)三層。

最后,控制則是無人車精準地執行規劃好的動作的能力,這些動作來源于更高的層。

規劃

任務規劃

無人駕駛規劃系統的分層結構設計源于2007年舉辦的DAPRA城市挑戰賽,在比賽中多數參賽隊都將無人車的規劃模塊分為三層設計:任務規劃,行為規劃動作規劃,其中,任務規劃通常也被稱為路徑規劃或者路由規劃(Route Planning),其負責相對頂層的路徑規劃,例如起點到終點的路徑選擇。 

我們可以把我們當前的道路系統處理成有向網絡圖(Directed Graph Network),這個有向網絡圖能夠表示道路和道路之間的連接情況,通行規則,道路的路寬等各種信息,其本質上就是我們前面的定位小節中提到的高精度地圖的“語義”部分。


這樣的路網圖中的每一個有向邊都是帶權重的,那么,無人車的路徑規劃問題,就變成了在路網圖中,為了讓車輛達到某個目標(通常來說是從A地到B地),基于某種方法選取最優(即損失最?。┑穆窂降倪^程,那么問題就變成了一個有向圖搜索問題,傳統的算法如迪科斯徹算法(Dijkstra’s Algorithm)和A*算法(A* Algorithm)主要用于計算離散圖的最優路徑搜索,被用于搜索路網圖中損失最小的路徑。

行為規劃

行為規劃有時也被稱為決策制定(Decision Maker),主要的任務是按照任務規劃的目標和當前的局部情況(其他的車輛和行人的位置和行為,當前的交通規則等),作出下一步無人車應該執行的決策,可以把這一層理解為車輛的副駕駛,他依據目標和當前的交通情況指揮駕駛員是跟車還是超車,是停車等行人通過還是繞過行人等等。

行為規劃的一種方法是使用包含大量動作短語的復雜有限狀態機(Finite State Machine,FSM)來實現,有限狀態機從一個基礎狀態出發,將根據不同的駕駛場景跳轉到不同的動作狀態,將動作短語傳遞給下層的動作規劃層。


如上圖所示,每個狀態都是對車輛動作的決策,狀態和狀態之間存在一定的跳轉條件,某些狀態可以自循環(比如上圖中的循跡狀態和等待狀態)。雖然是目前無人車上采用的主流行為決策方法,有限狀態機仍然存在著很大的局限性:首先,要實現復雜的行為決策,需要人工設計大量的狀態;車輛有可能陷入有限狀態機沒有考慮過的狀態;如果有限狀態機沒有設計死鎖保護,車輛甚至可能陷入某種死鎖。

動作規劃

通過規劃一系列的動作以達到某種目的(比如說規避障礙物)的處理過程被稱為動作規劃。通常來說,考量動作規劃算法的性能通常使用兩個指標:計算效率(Computational Efficiency)和完整性(Completeness),所謂計算效率,即完成一次動作規劃的處理效率,動作規劃算法的計算效率在很大程度上取決于配置空間(Configuration Space),如果一個動作規劃算法能夠在問題有解的情況下在有限時間內返回一個解,并且能夠在無解的情況下返回無解,那么我們稱該動作規劃算法是完整的。

配置空間:一個定義了機器人所有可能配置的集合,它定義了機器人所能夠運動的維度,最簡單的二維離散問題,那么配置空間就是[x, y],無人車的配置空間可以非常復雜,這取決于所使用的運動規劃算法。

在引入了配置空間的概念以后,那么無人車的動作規劃就變成了:在給定一個初始配置(Start Configuration),一個目標配置(Goal Configuration)以及若干的約束條件(Constraint)的情況下,在配置空間中找出一系列的動作到達目標配置,這些動作的執行結果就是將無人車從初始配置轉移至目標配置,同時滿足約束條件。

在無人車這個應用場景中,初始配置通常是無人車的當前狀態(當前的位置,速度和角速度等),目標配置則來源于動作規劃的上一層——行為規劃層,而約束條件則是車輛的運動限制(最大轉角幅度,最大加速度等)。

顯然,在高維度的配置空間來動作規劃的計算量是非常巨大的,為了確保規劃算法的完整性,我們不得不搜索幾乎所有的可能路徑,這就形成了連續動作規劃中的“維度災難”問題。目前動作規劃中解決該問題的核心理念是將連續空間模型轉換成離散模型,具體的方法可以歸納為兩類:組合規劃方法(Combinatorial Planning)和基于采樣的規劃方法(Sampling-Based Planning)。

運動規劃的組合方法通過連續的配置空間找到路徑,而無需借助近似值。由于這個屬性,它們可以被稱為精確算法。組合方法通過對規劃問題建立離散表示來找到完整的解,如在Darpa城市挑戰賽(Darpa Urban Challenge)中,CMU的無人車BOSS所使用的動作規劃算法,他們首先使用路徑規劃器生成備選的路徑和目標點(這些路徑和目標點事融合動力學可達的),然后通過優化算法選擇最優的路徑。

另一種離散化的方法是網格分解方法(Grid Decomposition Approaches),在將配置空間網格化以后我們通常能夠使用離散圖搜索算法(如A*)找到一條優化路徑。

基于采樣的方法由于其概率完整性而被廣泛使用,最常見的算法如PRM(Probabilistic Roadmaps),RRT(Rapidly-Exploring Random Tree),FMT(Fast-Marching Trees),在無人車的應用中,狀態采樣方法需要考慮兩個狀態的控制約束,同時還需要一個能夠有效地查詢采樣狀態和父狀態是否可達的方法。后文我們將詳細介紹State-Lattice Planners,一種基于采樣的運動規劃算法。


來源:http://www.vgyfnc.tw

顯示全部

0個評論

    數據加載中...

歡迎來到汽車學堂!

請及時完善個人信息,增加就業推薦機會

歡迎來到汽車學堂!

請及時完善個人信息,為您提供更好的服務

下線通知

您的帳號在其它地方登錄,您已被迫下線,如果不 是您本人操作,請及時修改密碼。

吉林11选五助手走势