嵌入式控制系統設計/有限狀態機和Petri網
有限狀態機 (FSM) 和 Petri 網 (PN) 是用於表示系統中離散互動的概念模型。
- FSM 是一個概念模型，它表示一個單個活動如何隨著時間的推移改變其行為，對內部或外部觸發事件做出反應。
- PN 是一個概念表示，它表示多個活動是如何協調的。
FSM 和 Petri 網處於比實際軟體更高的層次。這意味著它解釋了行為，但沒有解釋如何實現它。它是一個理想的表示，它沒有考慮時間延遲。
不同複雜度的系統以不同的方式表示。FSM 或 UML 狀態圖（類似於 FSM，但具有更多可能性）只能表示集中式系統，因此不需要與其他相同型別的系統進行協調。此類系統的示例包括自動售貨機、電梯等。
具有分散式硬體和集中式軟體狀態的系統可以使用 Petri 網表示。集中式軟體協調不同硬體元件之間的相互作用方式。
具有分散式硬體和分散式軟體狀態的系統也可以使用 Petri 網表示，但在這種情況下，沒有中央控制單元。不同的硬體元件都有自己的軟體狀態，並且它們都知道 Petri 網。現在，不同的元件必須自己進行協調。
分散式系統的一個例子是機器人足球賽。這是一場由機器人進行的足球比賽。每個機器人都是一個系統。如果有一個控制塔協調機器人，那麼這就是集中式軟體狀態的案例。控制塔本身可以被視為一個獨立的系統，用狀態圖表示，該狀態圖包含“球由己方控制”、“球由對方控制”等狀態。在每種狀態下，機器人必須以不同的方式進行合作；這由不同的 Petri 網表示。
如果沒有控制塔，每個機器人必須控制自己，並且它們必須自己進行協調。然後，每個機器人都會“知道”Petri 網，並且必須做出自己的決定，這可能會帶來一些問題。這些問題將在“Petri 網”部分中進行處理。
有限狀態機是離散行為的模型，它由以下部分組成：有限數量的狀態、狀態之間的轉換以及動作。狀態表示某種行為。轉換指示狀態變化，並由條件控制。動作是對要執行的活動的描述。如果此動作取決於狀態，則稱為 Moore 機。如果動作在轉換髮生時執行，即狀態和條件滿足時，則稱為 Mealy 機。大多數機器同時是 Moore 機和 Mealy 機。
一些整合開發環境 (IDE) 允許設計人員在螢幕上繪製 FSM 圖，然後 IDE 自動將該圖轉換為軟體或 FPGA 或 ASIC 實現。這使設計人員能夠使用自然的方式來表示系統。
一個機器人正在高速工作。當有人開啟門進入房間時，機器人繼續工作，但速度降低以確保人員安全。當人員從門離開房間時，他/她必須在關門後按下按鈕。現在，機器人可以繼續高速工作。
請注意，這是一個 Moore 機，因為輸出（動作）是基於狀態的。
還要注意現實和現實模型之間的區別。在模型中，不需要任何時間來檢查條件。在現實中，檢查門感測器和檢查按鈕需要一些時間。
在火車專案中，當火車經過隧道時，燈必須亮起來。雖然，當火車在白天行駛時，燈應該調暗。根據行駛方向，白燈或紅燈應工作。
請注意，這是一個 Mealy 機，因為輸出（動作）是基於輸入的。
在火車專案中，火車在轉彎時必須減速。當火車行駛上坡時，電機必須更加努力地工作。狀態之間的轉換由信標控制。該影像顯示了從/到直線行駛的可能轉換，其他轉換也可能發生。
之前解釋的 FSM 在某種程度上是有限的。您不能同時啟用兩個狀態，彼此相鄰。UML 狀態圖試圖克服這種限制，同時保留其良好的特性。這只是 UML 中定義的許多系統圖形表示之一。UML（統一建模語言）旨在指定、視覺化、構建和記錄軟體密集型系統。有關更多資訊，請參閱 維基百科頁面。狀態圖的基本語法與 FSM 非常相似。在狀態圖中，可能存在狀態內的狀態，因此存在一種層次結構。它們被稱為子狀態和超狀態或父狀態。另一個可能性是併發狀態。透過使用分支，一個狀態可以由多個其他狀態跟隨。每個轉換都可以用自己的條件控制。當多個條件滿足時，兩個狀態可以同時處於活動狀態。
與 FSM 相比，使用子狀態和超狀態，嵌入式系統的設計可以更好地視覺化，並且不那麼複雜。您可以更好地瞭解系統的工作原理，並且設計人員更容易定位問題並調整系統。因為它是一種標準，因此可以使用大量模擬工具（StateMate、StateFlow、BetterState...）。這些模擬工具只是用來檢查理論系統，但您永遠無法確定嵌入式系統是否能正常工作。可用的“後端”將狀態圖轉換為 C 或 VHDL。這使得軟體或硬體實現成為可能。
一個很好的例子來說明狀態圖的用法是自動售貨機。使用者插入一個 25 美分的硬幣，機器會等待使用者插入第二個 25 美分的硬幣。在使用者選擇飲料後，飲料就會被分配。機器再次等待。您有兩個主要狀態：收集和分配。它們有子狀態，因為有不同的飲料，而且每次使用者插入硬幣時都會進入一個新的狀態。理論上，這似乎是一個很好的視覺化方法，但在實踐中還有許多其他因素。這些問題可以部分解決。瓶子可能會卡在機器中，因此我們在收集和分配部分旁邊建立一個新狀態，如以下圖所示。
Petri 網（PN）是一種抽象模型，用於展示非同步程序之間的互動。它只是表示這些互動的眾多方法之一。非同步意味著設計人員不知道程序何時啟動以及它們將按什麼順序執行。視覺化這些概念的一種常見方法是使用位置、令牌、轉換和弧。我們參考 Petri 網基礎 來初步介紹符號。需要指出的是，只有當每個輸入位置都有令牌時，轉換才能觸發。觸發時，從每個輸入位置取走一個令牌，轉換的每個輸出位置都會得到一個（額外的）令牌。
位置可以扮演以下角色
- 一種通訊媒介：RoboCup 中的無線連線；
- 緩衝區：所有機器人互相傳送訊息。當一個機器人檢查第一條訊息時，其他傳入的資訊會被放置到它的記憶體中；
- 地理位置：機器人的環境，它需要去的地方；
- 可能的狀態或狀態條件：機器的正常模式和安全模式（參見 FSM）；
令牌可以扮演以下角色
- 物理物件：機器人；
- 資訊物件：兩個機器人之間的訊息；
- 物件集合：人員搬運器；
- 狀態指示器：機器人所處的狀態：防守方/進攻方；
- 條件指示器：令牌指示某個條件是否滿足（例如，當裁判發出訊號時，足球比賽開始）。
轉換可以扮演以下角色
- 事件：啟動執行緒，機器從正常模式切換到安全模式；
- 物件的轉換：改變角色的機器人，參見進一步說明；
- 物件的傳輸：球在機器人之間傳球。
弧線只連線位置和轉換，並指示令牌移動的方向。
在 PN 中，可能會出現兩個或多個系統相互等待，直到某個操作才能執行的情況。這被稱為 死鎖。也可能出現單個系統在轉換開始時永遠等待，因為另一個程序始終具有更高的優先順序。這個問題被稱為 *餓死*。
在數學模型中，轉換不花費時間。在現實世界中，執行轉換需要一定時間，事件的順序或時間就變得很重要。這個問題與 *競爭條件* 或 *競爭危害* 有關。當 PN 很大時，這些問題很難找到。
將使用 RoboCup 示例來介紹可能出現的問題和解決方案。為了實現某個目的，機器人之間必須進行通訊。我們假設自主機器人是完美設計的，因此我們使用行為工程方法。
當機器人站在球場上時，它的行為包含多種選項。根據這些選項和傳入的資訊，它會決定要做什麼。
每個機器人都可以執行一些基本操作
- 原地不動
- 轉身
- 行走
- 走向球
- 抓取
- 傳球
- 踢球
- ...
兩個或多個機器人必須協同工作，因此它們的操作必須同步。設計人員使用 Petri 網作為虛擬模型來展示互動。
示例：雙人傳球場景
當一個機器人看到它面前有一個對手，並且它附近有一個隊友時，它可以設定一個雙人傳球動作。我們參考引言中的 Petri 網圖。透過這個模型，第一個機器人的軟體可以與第二個機器人的軟體進行通訊。有時，指令必須等待輸入訊號，該訊號指示另一個機器人已經完成了它的操作。
當以這種方式計劃雙人傳球時，可能會出現問題。當第二個機器人帶球突破並失去球權時，第一個機器人會永遠等待接球。更好的實現方法需要兩個機器人之間進行持續的通訊。第二個機器人可以告訴它已經失去了球權，或者它想把球傳給另一個球員。
示例：錯誤決策
機器人必須在比賽中做出決策。檢查多個條件需要一些時間，在這段時間內，先前的決策可能會從真變為假。因此，機器人會執行錯誤的操作。例如：一個機器人要球。擁有球權的機器人必須檢查兩個條件。如果隊友要球，並且我擁有球權，那麼傳球。當該機器人檢查完第一個條件時，可能會出現一個對手跳到要球的機器人面前，因此該機器人說它不再想要傳球。第一個機器人檢查第二個條件，然後它傳球，球被對手攔截了。這個簡單的例子可以擴充套件為第三個條件（如果沒有任何對手）。
示例：死鎖情況
- 互斥原則指出，資源只能分配給一個機器人。如果沒有分配，則資源是空閒的。當兩個機器人爭奪球（=資源）時，可能會出現 死鎖 情況，因為球被分配給了兩個不同的代理。這個問題也與迴圈等待條件有關，因為每個機器人都在等待另一個機器人釋放球權。
- 機器人必須在團隊中扮演角色（=資源）。角色分配如下：主要進攻手、進攻支持者、防守支持者和守門員。守門員的角色在整個比賽中都是固定的。其他三個角色更加靈活。機器人不斷地互相傳送訊號，廣播它們自己與球之間距離的估計值。根據各種估計值，距離球最近的機器人會扮演主要進攻手的角色，向球移動，並試圖將球踢向對方球門。進攻支持者也向球移動，但會在距離球太近之前停下來。防守支持者會等到球靠近它（然後切換到主要進攻手的模式）。在將這些角色分配給機器人時，可能會出現問題。將主要進攻手的角色視為只能分配給一個機器人的資源。如果沒有任何機器人分配此資源，則團隊會受到影響，因為沒有任何機器人會嘗試向球移動。如果多個機器人分配此資源，則團隊也會受到影響，因為它們會互相干擾，因為它們都在試圖搶球。另一個問題是，在兩個角色之間切換時會發生時間延遲。機器人必須首先釋放資源，然後另一個機器人才能獲取它。在此期間，機器人會凍結，無法執行任何操作。
- 在攻擊手機器人失去能量的緊急情況下，可能會出現死鎖情況。機器人無法釋放其攻擊手角色，因此沒有任何代理會朝著球移動，因為它們無法成為主要進攻手（資源未釋放）。可以透過機器人之間的通訊或在斷電時使用自動釋放功能來避免此問題。
之前的模型有很多擴充套件和變體。由於列表太詳細，這裡只討論一些模型。
在有色 PN 中，每個令牌都是一個具有某些屬性的物件。這些屬性在令牌遍歷結構時可能會發生變化。例如，透過這些屬性，某個物件可以優先於其他物件。每個物件都有一定的有限狀態機需要遵循，不同物件之間的協調由有色 Petri 網完成。因此，有色 PN 可以被認為是協調和計算的結合。
通訊順序程序 (CSP) 是一種語言，用於計算機科學中描述併發系統中的互動。由於這種併發性，通訊必不可少。每個“訊息”都是協調和通訊的結合。透過這種方式，可以對程序之間進行形式化驗證。
