原文鏈接：進階課程?丨Apollo規劃技術詳解——Basic Motion Planning and Overview

運動規劃（Motion Planning）就是在給定的位置A與位置B之間為機器人找到一條符合約束條件的路徑。這個約束可以是無碰撞、路徑最短、機械功最小等。具體的案例可以是為移動機器人規劃出到達指定地點的最短距離，或者是為機械臂規劃出一條無碰撞的運動軌跡，從而實現物體抓取等。

基本的運動規劃就是在起始構型與目標構型之間找到一條連續運動軌跡，同時避開環境中的障礙物。

上周阿波君為大家詳細介紹了「進階課程?Apollo感知之旅——機器學習與感知的未來」。

通過介紹了感知中的機器學習、未來以及課后思考，其中詳細的介紹了感知里的機器學習問題，如何應對corner case，除深度學習外、還有其他算法，深度學習+仿真數據+車載Al芯片成為一種趨勢，智能交通設施、V2X的普及等知識，還思考了延時是如何來影響自動駕駛安全的，ACC自適應巡航的功能是如何實現的等問題。

本周阿波君將與大家分享Apollo規劃技術詳解——Basic Motion Planning and Overview。下面，我們一起進入進階課程第21期。

---

1.什么叫做運動規劃

規劃問題本質上是一個搜索問題，即對一個給定的函數，尋找最優解。相對于無人車而言，規劃問題就是給定現在的狀態，找到無人車移動的最優解。通常最優解目標函數F(x)定義。

從內容考慮，規劃問題涉及三個領域，機器人領域，控制領域和人工智能。不同的領域對問題的理解不同。

• robotic fields，規劃就是如何產生軌跡以完成目標，涉及RRT， A*，D* lite等。
• 控制領域，規劃理解為到達目標狀態的動態系統，涉及MPC， LQR等。
• artificial intellegence（AI），是生成狀態到動作的映射，涉及reinforcement ?learning，end-to-end imitation learning等。

---

2.如何構建汽車的運動規劃問題

從最簡單問題出發，把運動規劃抽象成一個path finding problem（路徑查找問題），只關心無人車怎樣走，周圍環境是不變的。如圖1所示，我們將其抽象成無數的網格，從綠色的點到紅色的點的路徑規劃就是一個path finding problem 。如圖想尋找最短路徑，可通過廣度優先的方法，也可以使用深度優先方法。但是對于最短路徑優化問題，深度優先方法的效率太低。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖1 路徑查找問題

另外，可以通過啟發式方式對搜索問題進行優化。前面的廣度優先方法沒有利用起點和終點之間的信息，breadth first search（BFS）和 depth first search（DFS）都屬于non-information search，問題就在于不知道目標在哪里。A-star算法是大概知道紅點在右邊，定義一個啟發式函數，該函數猜測距離目標還有多遠，通過這種方法先搜索一些比較近的點，然后從這個點出發逐漸擴大搜索圈。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖2?A-star算法

A-star花費時間比廣度優先算法時間更短，因為它有信息支持，現在的一些路徑搜索算法本質上都是從A-star算法出發，需要知道目標函數的樣子。

目前，A-star算法還不能直接用在規劃模塊上，因為A-star算法本身要求對整個環境全知。而自動駕駛對周圍環境是部分觀察的，如圖3所示。紅色的點是小車，紅色和綠色塊是障礙物，對于無人車來說是看不見的，無人車的傳感器（雷達、激光雷達、攝像機）系統能部分觀察環境。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖3 無人車部分可見動態環境

對于部分觀察我們可以使用貪心算法，其實就是一個增量搜索，就是在看見的情況下盡量走好。如圖4所示，利用D-star算法對部分觀察的數據進行控制規劃。它利用當前能夠看到的信息進行增量規劃，D-star的特點是處理在看到的有限范圍的條件下，如何到達預定地點的搜索問題方法。這種增量搜索很難通過一步步的迭代達到全局最優解。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖4 D-star算法

在現實生活中，人類開車是很少做90度直角轉彎的，這樣的折線并沒有考慮無人車運動過程中的運動模型和動力學模型。更進一步，可以通過平滑性曲線的方式來優化折線，換成一些較為平滑的曲線來完成，如圖5所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖5 曲線平滑

那么，上述介紹的搜索技術離自動駕駛運動規劃還差多少？首先是在部分觀察空間的動態障礙物，規劃模塊怎么處理動態障礙物是關鍵并且是有難度的。其次是自動駕駛汽車能否按照規劃的行駛，可能需要一個動態模型。第三還缺少了遵守交通規則，它是道路安全的基本保證，將交通規則融入規劃也是一個難點。第四是實時計算，目前來說百度要求規劃模塊運轉周期是100毫秒。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖6 實現自動駕駛還缺什么

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖7 自動駕駛運動規劃

運動規劃問題就是讓自動駕駛車輛能夠安全平穩到達終點，本質是一個三維規劃問題，即 XY 坐標加上時間維度，叫做 3D Trajectory Optimization Problem（軌跡優化問題）。從車輛動力學模型來說，維度需要進一步上升，因為涉及到車頭的方向，車的轉向角、加速度等問題。

---

3.無人駕駛硬件系統

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖8?自動駕駛汽車硬件系統

無人車硬件系統除了汽車之外，還涉及很多傳感器，傳感器感知汽車周圍環境，即使是這樣也只是部分搜索環境。還有 GPS 接收器可以做定位，以及 IMU 慣性導航系統，如上圖所示。

---

4.無人駕駛系統軟件

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖9 自動駕駛汽車系統軟件

如上圖所示，運動規劃可以獲得兩部分信息，一部分是動態信息，包括從認知獲得的信息，就是從感知模塊和定位模塊獲得信息，另一部分是靜態信息，就是高精地圖。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????圖10 無人駕駛系統軟件的組成

無人駕駛系統軟件包括定位、感知、預測、運動規劃和控制等。定位就是知道汽車在哪里。感知即是對周圍環境信息的獲取。預測就是感知到的障礙物的行進意圖，例如旁邊有無人超車。運動規劃是在知道這些信息后，告知汽車如何運動。控制模塊就是得到指令之后如何控制汽車。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????圖11 規劃模塊的工作原理

車輛狀態、交通燈信息、障礙以及障礙軌跡、導航、高精地圖都是規劃模塊能獲得的信息。規劃就是在這樣的部分可見信息中給無人車找到一條軌跡。它不僅是一條路徑，而是隨著時間推移路徑該怎么走，它包含兩方面，一是路徑信息，二是速度配置文件，需要保證速度和路徑變化都是平滑的。

---

5.課程概述

如圖所示，整個規劃模塊將會介紹以下內容。包括使用的方法、環境認知、所解決的問題、構建運動規劃以及如何構建一個通用生態系統。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????圖12 規劃模塊的組成

總結

以上是生活随笔為你收集整理的Apollo进阶课程㉑丨Apollo规划技术详解——Basic Motion Planning and Overview的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。