嵌入式控制系统设计/有限状态机和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) 是一种语言，用于计算机科学中描述并发系统中的交互。由于这种并发性，通信必不可少。每个“消息”都是协调和通信的结合。通过这种方式，可以对进程之间进行形式化验证。
