分層有限狀态機和無人車行為規劃
行為規劃又稱為行為決策，是無人車規劃子產品三層（任務，行為，動作）的中間層，本文将介紹行為規劃的基本概念，設計核心，同時介紹一種具體的無人車行為規劃方法——分層有限狀态機，
行為規劃（Behavior Planning）是無人車規劃子產品的一層，位于全局任務規劃和底層的動作規劃層之間，駕駛行為規劃也被稱為駕駛行為決策，這一層的作用主要是依據來自上層（任務規劃層）的全局最優行駛路線資訊，根據目前的交通場景和環境感覺的資訊的了解，來确定自身目前駕駛狀态，在交通規則的限制和駕駛經驗的指導下規劃出合理的駕駛行為。下圖是無人車行為決策層的資訊流：
無人車決策規劃系統設計準則
行為規劃部分幾乎直接關系到無人車的可靠性和安全性，要設計出完全符合人類駕駛員習慣和交通規則的行為規劃系統在目前來看仍然是一大挑戰，目前而言實作行為規劃子產品的方法很多，但是其設計理念大緻可以總結為兩點：
- 合理性：無人車駕駛的合理性建立在兩個基礎之上——交通法規和駕駛經驗，其中交通法規的優先級又要高于駕駛經驗，交通法規需要考慮的内容包括：靠右側車道行駛，不能超速，換到超車時應提前開啟轉向燈，對于感覺到的交通信号燈和交通标志，應按照其隻是内容行駛，出現任何危險情況，應當能夠果斷地執行緊急制動等等。駕駛經驗需要考慮的内容主要包括：盡量保持在原車道，不應随意變道；城市路段行駛時，不應随意加速，確定駕駛的平順性；對于前車行駛緩慢而條件運作的情況應當果斷超車等等。
- 實時性：任何無人車系統中的行為規劃都是實時的，行為規劃應當能夠處理複雜的動态交通場景，并且能夠根據環境的變化快速的調整駕駛行為以避免危險的發生。
有限狀态機
目前在無人車行為規劃上并沒有一個“最佳解決方案”，目前普遍認可和采用的方法是分層有限狀态機（Hierarchical Finite-State Machine ，HFSM），分層有限狀态機也是早期DARPA挑戰賽中被許多隊伍采用的行為規劃方法。而有限狀态機是分層有限狀态機的基礎。
相信很多讀者都認為計算機（Computer）就是我們的筆記本，PC或者是伺服器，實際上我們生活中的所有計算裝置都是計算機，包括我們手裡的手機，這些計算裝置可以被統稱為反應系統（Reactive System），因為它們都是根據來自外部世界的輸入信号工作的。
而有限狀态機就是一個非常簡單的抽象反應系統，它之是以非常簡單是因為它隻對特定的外界輸入産生數量有限的響應，在有限狀态機中，我們隻能構造有限數量的狀态，外界的輸入隻能讓狀态機在有限的狀态中從一個狀态跳到另一個狀态。下圖是一個簡單的FSM：
一個有限狀态機通常包含如下幾部分：
1. 輸入集合：通常也叫刺激集合，包含我們考慮到的狀态機可能收到的所有輸入。通常我們使用符号 Σ Σ 表示這個集合。一個簡單的例子，假設我們的無人車上有啟動，停止兩個按鈕（我們以a，b代替，不能同時被按下），那麼以這兩個按鈕為輸入的FSM的輸入集合 Σ={a,b} Σ = { a , b } 。
2. 輸出集合：即FSM能夠作出的響應的集合，這個集合也是有限的，我們通常使用符号 Λ Λ 來表示輸出集合，很多情況下FSM并不一定有輸出，即 Λ Λ 為空集。
3. 我們通常使用有向圖來描述FSM内部的狀态和轉移邏輯，我們使用符号 S S 來表示有向圖中狀态的集合。
4. FSM通常有一個固定的初始狀态（不需要任何輸入，狀态機預設處于的狀态），我們使用符号 s0s0 表示。
5. 結束狀态集合，是狀态機 S S 的子集，也有可能為空集（即整個狀态機沒有結束狀态），通常使用符号 FF 表示。
6. 轉移邏輯：即狀态機從一個狀态轉移到另一個狀态的條件（通常是目前狀态和輸入的共同作用），比如說我們要從上圖的 Python 狀态轉移到 Error 狀态，需要的條件是： 1）狀态機處于 Python 狀态；2）輸入不是 “is”。我們通常使用狀态轉移函數來描述轉移邏輯： δ:S×Σ→S δ : S × Σ → S
接收器（Acceptors）和變換器(Transducers):根據是否有輸出可以将感覺機分為兩類：接收器和變換器，其中接收器是指沒有輸出但是有結束狀态，而變換器則有輸出集合。
FSM可進一步區分為确定型（Deterministic）和非确定型（Non-Deterministic）自動機。在确定型自動機中，每個狀态對每個可能輸入隻有精确的一個轉移。在非确定型自動機中，給定狀态對給定可能輸入可以沒有或有多于一個轉移。
分層有限狀态機
當狀态很多的時候，有限狀态機就有可能變得非常龐大，假設有限轉态機有N中狀态，那麼其可能的狀态轉換就有 N×N N × N 種，當 N N <script type="math/tex" id="MathJax-Element-11">N</script> 的數量很大的時候，狀态機的結構也會變得更加複雜，此外，有限狀态機還存在如下幾個問題：
- 可維護性差：當新增或者删除一個狀态的時候，需要改變所有與之相關聯的狀态，是以對狀态機的大幅度的修改很容易出錯；
- 可擴充性差：當FSM包含大量狀态時，有向圖可讀性很差，不友善擴充；
- 複用性差：幾乎不可能在多個項目中使用相同的FSM
這時候就可以使用分層狀态機(Hierarchical Finite-State Machine)了，把那些同一類型的狀态機做為一個狀态機，然後再做一個大的狀态機，來維護這些子狀态機，如下圖所示：
相比于FSM，HFSM新增了一個超級狀态（Super-state）：本質上也就是将性質同一類型的一組狀态何為一個集合（即上圖中的大方框），超級狀态之間也有轉移邏輯。這也就意味着HFSM不需要為每一個狀态和其他所有狀态建立轉移邏輯，由于狀态被歸類，類和類之間存在轉移邏輯，那麼類和類之間的狀态轉移可以通過繼承這個轉移邏輯來實作，這裡的轉換繼承就像面向對象程式設計中通過多态性讓子類繼承超類一樣。
感覺機在行為規劃中的使用
那麼我們為什麼在無人車行為規劃層使用感覺機呢？無人車的行為規劃層從某種程度上來說也是一種反應系統——無人車的決策（也就是無人車一個時間段以後的狀态）是基于無人車目前所處的狀态以及來自感覺子產品的資訊（輸入）共同決定的。我們以一個實際的應用案例來分析：
“Junior”是斯坦福大學在2007年參加DARPA城市挑戰賽時的無人車，它是第二名完成該比賽的無人車，Junior的行為規劃系統就是通過分層有限狀态機實作的，他們将頂層的駕駛行為分成了13個超級狀态（也就是我們上圖中的大方框），每個駕駛行為又對應一些子狀态來完成這一行為。頂層行為由一個FSM管理，如下圖所示：
我們簡單的分析一下這個狀态機：
- LOCATE_VEHICLE: 這是Junior的初始狀态，即在無人車出發之前确定其在地圖中的位置。
- FORWARD_DRIVE: 這個超級狀态實際上包含了直行，車道保持和障礙物規避，當不是在停車場（即無道路開放區域）時，這是狀态機首選的狀态。
- STOP_SIGN_WAIT: 當無人車在停車标志處等待時，進入此狀态。（停車标志是美國十字路口的常見标志）
- CROSS_INTERSECTION：在這個狀态下無人車處理十字路口通過這一場景，無人車會等待直到确認能夠安全通過。
- UTURN_DRIVE: 在U型掉頭時調用的狀态
- UTURN_STOP: 在U型掉頭前的停車狀态
- CROSS_DIVIDER: 跨過黃線行駛
- PARKING_NAVIGATE：停車場内的普通駕駛模式
- TRAFFIC_JAM和ESCAPE：處理交通阻塞時的兩個狀态
- BAD_RNDF: 如果目前道路和預先做的路網圖不同的時候，即進入該狀态，在這個狀态下，無人車會采用混合A*算法完成車輛的路徑規劃。
- MISSION_COMPLETE: 當挑戰賽（DARPA）結束，無人車進入該狀态，即整個狀态機的結束狀态。
在無人車正常行駛中這個狀态機幾乎處在普通駕駛模式（即FORWARD_DRIVE和PARKING_NAVIGATE這兩個狀态），系統通過stuckness detectors（膠着檢測器）來确定是否從普通駕駛狀态轉移至底層的其他狀态，在完成了相應的動作以後行為子產品又會回到原來的普通駕駛模式。這樣的狀态機能夠讓無人車處理一下複雜情況：
- 當目前車道阻塞的時候，車輛會考慮駛入對面車道（即CROSS_DIVIDER）, 如果對面車道也被阻塞了，則會啟動U形轉彎（UTURN_STOP/UTURN_DRIVE），此時内部RNDF（Route Network Definition File，即全局路網圖）也會相應修改，并執行dynamic programming以重新生成RNDF值函數。
- 對于十字路口的交通阻塞問題，在等待時間結束以後，會調用混合A*算法找出最近出口制動車輛離開阻塞區域。
- 在單向通道阻塞的時候，如果規劃失敗也會調用混合A*算法規劃至下一個GPS路點。
- 某些路點在循環多次以後仍然無法到達，那麼跳過這個路點（這是為了防止車輛為了抵達規劃中某個路點而進入死循環）
- 如果無人車長時間沒有取得任何的進展（指比賽的進展），車輛将會調用混合A*規劃出通往附近的GPS航點的路徑，這個規劃是無視交通規則的。
雖然Junior的政策有些是針對DRAPA挑戰賽設計的（即為了盡可能赢得比賽），但是其設計的理念仍然具有參考價值。在實際的無人駕駛應用中，需要實作的狀态機将更為複雜。雖然HFSM比傳統的FSM更為子產品化，但它仍然繼承了FSM大多數缺點，例如有限的可重用性。在後面的文章中，我們将介紹行為樹（Behavior Tree），行為樹這種方法将各種狀态子產品化，以便邏輯的不同部分能夠更輕松地重用它們。