Stanford AA274A Principles of Robotic Autonomy | Autumn 2019 | State Machines

斯坦福大学 AA274A 机器人自主原理 | 2019年秋季 | 状态机 Marco Pavone 教授开启了本课程的决策模块，详细讲解了有限状态机的数学公式化表述、优势以及理论边界，并通过自动停车场道闸和二进制序列检测器等实例阐释相关概念。他展示了划分细化算法如何精简冗余的状态表示，并解释了用于复杂自主系统的分层与模块化设计模式。随后，博士生 Benoit Landry 将理论与实际应用相结合，探讨了 PX4 自动驾驶仪软件栈中的真实飞行模式，并演示了如何将单体式 Python 导航脚本重构为模块化的 ROS SMACH 架构。讲座最后介绍了利用 SMACH Viewer 进行运行时检查，并预告了包括马尔可夫决策过程和强化学习在内的不确定性决策后续主题。 有限状态机（FSM）是机器人决策和行为编排的核心基础框架，它通过紧凑的状态空间抽象运行，取代了计算上难以处理的输入历史记录。 (0:05) 状态最小化算法利用划分细化技术，将行为状态机缩减为最小等效形式，其运行时间相对于状态数量呈多项式级。 (18:52) 机器人操作系统（ROS）生态系统利用 SMACH 库来构建模块化、分层的状态机，并配合 smach_viewer 对活动状态进行实时可视化自省。 (40:08) 包括开源 PX4 自动驾驶仪飞行栈在内的现实世界自主系统，严重依赖 FSM 架构来管理模式切换和安全关键型执行逻辑。 (36:37)

In Stanford's AA274A course, Professor Marco Pavone and Ph.D. student Benoit Landry present finite state machines as an indispensable modeling framework for robotic autonomy, showing how formal state reduction and structured software libraries prevent critical operational failures. State Abstraction and Theoretical Boundaries (2:04) State machines resolve the computational intractability of evaluating full input histories by summarizing past events into a compact state variable. Defined formally by states, input and output vocabularies, a transition function, and an output function, they serve as modeling frameworks for control synthesis, system analysis, and behavior simulation. Pavone notes that while deep learning continues to advance, finite state machines remain central to production robotics, even as modern research explores hybrid architectures such as Christopher Manning's work combining state machines with machine learning. Systematic Design and State Reduction (18:52) Because ad hoc state machines quickly grow unwieldy, systematic architectural techniques are necessary to prevent logic bugs and state explosion. Pavone illustrates that intuitive models, such as binary tree structures designed to detect sequences like 010 and 110, often generate redundant states that perform identical operations. To streamline these models, engineers rely on polynomial-time equivalence partitioning algorithms that iteratively group states by equivalent outputs and compatible transitions, collapsing bloated systems into minimal behavioral representations. Production Realities and Failure Modes (13:58) Real-world robotic deployments frequently fail when state machines overlook sensor dropouts, conflicting data, or edge cases like vehicle tailgating at an automated parking gate. Production systems like the open-source PX4 drone autopilot illustrate the complexity of managing operational modes—including loitering, return-to-land, and acrobatic maneuvers—across dedicated loop files like commander.cpp, where architectural debates regularly involve dozens of developer comments. Furthermore, finite state machines cannot manage tasks requiring unbounded counting, such as validating arbitrarily long strings of balanced parentheses, placing them near the lower tiers of computational expressiveness. Modular Robotics Implementation via ROS SMACH (40:08) To transition beyond fragile if-elif scripts like the baseline TurtleBot navigator.py, Benoit Landry demonstrates the ROS SMACH framework. SMACH formalizes modular development by encapsulating behaviors into individual state classes and structural containers that support composition patterns like cascading, parallel execution, and feedback loops. Paired with introspection tools like smach_viewer, this architecture dynamically highlights active states during runtime, enabling engineering teams to rapidly diagnose path-planning failures, tracking timeouts, and state divergence without digging through monolithic codebases. Pavone cautions that while conceptualizing state machines appears straightforward, engineering disciplined, bug-free implementations under hardware constraints remains exceptionally difficult. Looking ahead, the curriculum transitions from deterministic state logic toward decision-making under uncertainty, introducing Markov Decision Processes, dynamic programming, and reinforcement learning.

斯坦福大学教授 Marco Pavone 与助教 Benoit Landry 指出，有限状态机是机器人实现离散推理与决策的基础建模框架；通过规范的形式化定义、状态化简与模块化工程实现，工程师能够有效控制自主系统的行为逻辑并应对异常故障。 状态机的形式化建模与计算局限 (2:04) 状态机并不是具体算法，而是一种克服历史输入爆炸的离散建模框架。标准数学映射无法保留历史记忆，而直接穷举全部历史输入序列在计算上是不可行的。有限状态机通过紧凑的状态变量 $s_t$ 概括过去的输入历史，由状态转移函数 $T(s_t, i_t)$ 与输出函数 $O(s_t, i_t)$ 共同决定下一状态和即时动作，广泛应用于控制合成、系统交互分析与多智能体仿真验证。自动化车库道闸等现实系统便通过离散状态与传感器输入的映射实现周期性动作。然而，有限状态机在计算能力上处于较低层级，无法处理需要无界计数的任务，例如识别任意长度括号字符串是否配对平衡即需要无限状态，这要求工程师明确其与图灵机等更高阶计算模型的理论边界。 边缘异常处理与状态最小化方法 (13:58) 在物理机器人中部署状态机极易受到传感器丢包、矛盾读数或环境异常行为的干扰，例如跟车闯关未被检测可能导致道闸直接砸向车辆，这促使系统设计演化为不断引入异常状态的迭代过程。为了防止系统复杂度无序膨胀，工程师依赖严格的状态化简算法去除冗余逻辑。以检测二进制序列 010 与 110 的检测器为例，直观的树状构造会产生包含 7 个状态的结构，但通过划分精炼算法，首先按照输出行为分组，再依据输入转移的兼容性进行多轮分割，该系统最终可在多项式时间内被严格简化为等效的 4 状态模型。此外，分层超状态、级联串联、并行组合以及反馈闭环等架构模式，也为维持大规模状态系统的可解释性与形式化验证提供了结构支撑。 工业规范与开源飞行控制系统的状态机实践 (35:06) 在工业机器人与自动驾驶企业的实际开发中，工程师往往直接利用面向对象设计将当前状态维护为内部成员变量，并在固定频率的控制循环中轮询输入并触发转移。PX4 开源无人机飞控系统正是这一范式的典型工业案例，其在 commander.cpp 等核心模块中明确维护了返航（RTL）、悬停（Loiter）、着陆（Landing）与特技模式（Acro mode）等离散航行模式，以防误触发高风险特技动作。开源社区围绕 PX4 状态机架构的边界划分与数据流经常产生激烈的工程争议与多轮工单讨论，这表明生产级系统的状态设计并非纯理论推导，而是需要权衡软硬件交互与安全约束的复杂系统工程。 ROS SMACH 框架与导航异常安全恢复 (40:08) 为了避免在庞大的单体 Python 脚本中堆砌易碎的 if-elif 嵌套逻辑，ROS 生态提供了 SMACH 框架。SMACH 规范了 smach.State 节点规范及其 execute 方法所返回的结果字符串，并借助上下文管理器实现容器化封装。在 TurtleBot 导航架构重构中，系统被清晰拆解为等待、规划与跟踪三个核心状态。过往学生项目中因 EKF 滤波器发散或传感器异常导致小车陷入死角的故障，在 SMACH 结构下可通过捕获规划失败或跟踪超时结果，显式触发后退或重置定位等安全恢复分支。配合 smach_viewer 提供的动态内省可视化，开发团队能够实时监视运行中的状态转移，显著降低排查逻辑悬挂和系统盲跑的时间成本。 课程后续将从确定性的离散状态机转向不确定环境下的自主决策，系统探讨马尔可夫决策过程（MDP）、动态规划及其近似算法，并最终衔接强化学习以处理带噪感知与动作执行。

[0:05] Prof. Marco Pavone: When you go to industry, most likely a lot of your time will be spent debugging state machines.

[0:05] All right. [0:06] So, today we're going to move on [0:09] to the fourth module of this class that [0:12] deals with [0:14] reasoning and decision-making. [0:17] And in particular today we're going to [0:19] cover one of the most basic tools in [0:22] order to endow a robot with [0:25] basic reasoning capabilities referred to [0:28] as a state machines. [0:30] In one way or another you have already [0:32] encountered state machines at least [0:34] implicitly in the past. Today we're [0:37] going to [0:38] discuss them [0:40] a little bit more in detail. [0:43] The topic of state machines is [0:45] fairly simple. [0:47] On the other hand, when you go to [0:49] industry, most likely a lot of your time [0:53] will be spent debugging state machines. [0:55] Turns out the state machines can get [0:57] extremely tricky [0:58] and give rise to undesired behaviors [1:01] that you will try to [1:03] discover and correct, but the process [1:05] will be will be very time-consuming. [1:09] Fortunately, there are some [1:11] basic techniques and a design [1:15] patterns that you can use in order to [1:18] engineer state machines that are less [1:21] prone to errors. This is somewhat the [1:23] objective of this lecture. [1:26] So, the key concept simple, making them [1:28] work on practical robots quite [1:30] complicated. [1:32] In particular the [1:33] objectives of today's lecture are to [1:35] introduce the notion of a state [1:37] machines, [1:38] discuss their relevance in terms of [1:40] strengths and their limitations, and [1:42] finally introduce some tools that you [1:43] can use in order to properly set them up [1:47] set them up. [1:49] Most of this lecture is taken from a [1:52] lecture at MIT [1:54] from Leslie Cabling and the co-authors [1:56] and uh colleagues [1:58] um in a busy classroom in the EECS [2:01] department at MIT. [2:04] Now, [2:06] um a function in general is uh a map [2:10] between an input and an output. [2:13] A state machine instead is uh a [2:17] methodology in order to model [2:20] uh system [2:22] whose output depends on the entire [2:24] history of the input. [2:27] Okay? So, in a map, you have an input, [2:29] that input gets transformed, perhaps [2:31] very non-linearly, into an output, but [2:34] there's no notion of a history of the [2:35] input. [2:36] While in a state machine, the notion of [2:38] a history of the input is the defining [2:41] uh concept. [2:42] So, we can basically define a state [2:44] machine as a computational model for [2:46] systems whose output depends on the [2:48] entire history on their inputs at a very [2:51] high level. [2:52] Now, a state machine per se is not an [2:56] algorithm. It's just a modeling [2:57] framework. The same way you would use uh [3:00] Markov decision processes or probability [3:02] densities in order to model a problem. [3:05] We look at uh [3:06] uh [3:08] probability formulations of filtering as [3:10] a modeling tool, but then you we had to [3:11] divide algorithms. [3:13] We use at the Markov decision processes [3:15] as a modeling tool for uh [3:17] decision-making. Actually, we'll see [3:18] that in the next lecture, but then you [3:20] have to design algorithms. Similarly, [3:22] for finite state machines, they are a [3:23] modeling tool, but then you have to [3:25] design algorithms in order to manipulate [3:27] them. [3:29] Now, state machines can be used in a [3:32] variety of ways and for a variety of [3:35] tasks. First of all, and this is the [3:38] most basic application of a state [3:40] machines, you can use them uh [3:42] synthetically in order to specify a [3:45] program for uh a robot. [3:48] Like, for example, a simple robot could [3:50] be an ATM [3:52] Behind the hood in the ATM machine, [3:55] there is a state machine that says if a [3:57] sensor a card in the card reader, I [4:00] should ingest a card, then I should read [4:02] the numbers, then I should some other [4:04] operations. All of that is encoded into [4:07] a state machine. [4:08] But another way of using state machine [4:10] is [4:12] in terms of [4:13] analysis. Like for example, you can use [4:16] a state machine to model the interaction [4:18] between an autonomous agent and some [4:22] other agents [4:23] in the environment, say self-driving car [4:25] and some pedestrian. And trying to [4:28] reason about the possible failure modes [4:31] that your control algorithm for the [4:33] autonomous agent could give rise to. [4:36] So this is more for analysis as opposed [4:37] to control synthesis. [4:39] Finally, you can use a state machine in [4:42] order to predict the behavior of other [4:44] agents in order to simulate, for [4:46] example, the safety deficiency of the [4:49] autonomous stack of a robot. For [4:51] example, it's very typical to model [4:53] pedestrians in simulation by using a [4:56] finite state machine. And then test in [4:58] simulation and the behavior of your [5:00] autonomous car when interacts with a [5:02] pedestrian, where the pedestrian is [5:04] going to interact with your autonomous [5:06] car according to some state machine. [5:10] So there are many different ways you can [5:12] use a state machine. All of them quite [5:15] important to the point that uh [5:17] if you stick with the robotics field, [5:19] you'll be working with state machines [5:20] for the rest of your life. [5:23] Most likely, unless uh [5:25] uh deep learning takes over everything [5:27] and state machine becomes obsolete. [5:30] Now, state machines uh [5:33] are useful [5:35] quite a big deal to the practitioner for [5:37] all the reasons that I've just discussed [5:39] in order to synthesize a controller, in [5:41] order to analyze a controller, in order [5:43] to predict the behavior of other agents [5:45] on the roads. [5:47] But, [5:48] it is also of interest to researchers. [5:50] There is still quite a bit of work on [5:53] developing new tools for state machines. [5:55] For example, in order to prove their [5:57] correctness, in order to learn them from [6:01] data, and so on and so forth. For [6:03] example, here we just pulled up a paper [6:06] from Chris Manning, who is a professor [6:07] here in computer science from 2019, [6:10] doing some work blending the field of [6:13] learning with the field of state [6:15] machines. [6:16] So, it's still, even though it's [6:18] very old topic, probably one of the [6:20] oldest topic in the field of robotics, [6:22] it's still an active field of research. [6:26] Now, [6:27] what is a state machine from a [6:29] mathematical standpoint? [6:31] To specify a system whose [6:34] output depends on the history of an [6:37] input, in principle, we could have a [6:39] very complicated function that for each [6:42] possible history of an input [6:45] it maps a given output. [6:47] But, that function would be very [6:48] difficult to specify because the space [6:51] of possible histories grows [6:54] exponentially. [6:55] So, you would need to specify the [6:57] behavior of that function for an [6:59] exponentially large number of possible [7:01] inputs. That from a practical standpoint [7:03] would be horrible. [7:05] So, the approach of a state machine, [7:06] which is, by the way, the approach that [7:08] we already seen in most of this class uh [7:12] uh this quarter, is to introduce the [7:15] notion of a state that in a compact way [7:18] captures whatever it matters in order to [7:22] um [7:23] uh predict an input based on a his [7:25] predict an output, well, output and [7:27] information based on an input sequence. [7:30] In particular, a state machine comprises [7:32] a set of uh [7:34] states, [7:36] a set of inputs, called the input [7:38] vocabulary, and a set of outputs, called [7:41] the output vocabulary. [7:43] And then [7:45] comprises two key maps. One is the state [7:48] transition function. Very very similar [7:51] conceptually to the state transition [7:52] model that we use in order to specify [7:54] the dynamics of a robot. This is a map [7:56] that maps the current input and the [7:59] current state into a new state. [8:02] And then an output function. [8:04] A a map that maps the current input and [8:07] the current state into an output level. [8:12] Note that here there is no dependency on [8:14] entire history of the inputs because the [8:16] idea is that all that dependency is [8:18] encapsulated into the notion of a state [8:21] as of t. [8:24] And this is in general [8:26] uh um [8:28] this uh [8:30] a key theme in modeling and control. You [8:32] have a two different approaches. One is [8:34] a purely input-output and another one is [8:37] a state space approach whereby you [8:39] introduce notion of a state in order to [8:41] simplify the map from the input to the [8:43] output through the notion of the state. [8:48] And of course you also have to specify [8:49] an initial state as of zero. [8:51] So the very abstract level then the way [8:53] that the state machine would look like [8:55] is that we have a bunch of states. In [8:58] this case we have a three states. [9:00] We have an input vocabulary. In this [9:02] case we have three possible inputs. And [9:05] then we have the space of outputs. [9:07] That's the output vocabulary. And then [9:09] we have to specify the two maps, the [9:11] input map and the output map. The input [9:13] map from a graphical perspective is [9:16] represented via arcs. [9:18] So an arc means that if you are in state [9:21] as of zero and you apply input i1 [9:25] then you transition to state as of one. [9:27] If instead you apply input i0 then you [9:30] transition to state as of two. [9:34] So again here conceptually nothing new. [9:37] In a way this is the very same model we [9:39] use in order to model the state [9:41] evolution of a robot. [9:43] Point here is that uh this same model [9:46] can be used much more generally to [9:48] specify the uh high-level behavior of a [9:51] robot or any automated machine for what [9:54] matters. Like, for example, an ATM [9:56] machine. [9:59] As I said, we have a second map, which [10:00] is the output map that specify [10:03] uh [10:04] the uh [10:06] output that the state machine would [10:09] provide [10:10] when from a given state [10:13] you transition to another state on a [10:15] given input. So, for example, if you're [10:16] at state S of zero, and you apply input [10:19] I1, then the state machine outputs a [10:22] label O1. [10:25] We'll see some example later on that [10:27] will clarify this concept. And actually, [10:29] let's see an example right away. [10:31] So, [10:32] this is a fairly simple example, but [10:34] actually with a real example. Let us [10:36] assume that [10:37] you are at a gate and that the gate has [10:40] a bar that can be in a three possible [10:43] positions. Either at the top, meaning [10:45] that the bar has been raised, at the [10:47] bottom, or somewhat in the middle, [10:50] meaning that the bar is either raising [10:52] or lowering. [10:54] Now, there is a sensor that tell that [10:56] tells us if the car is in front of the [10:59] bar [11:00] or if the car has just passed through [11:03] the bar. [11:05] And the gate can take uh the following [11:07] actions. It can uh [11:09] uh raise the bar, lower the bar, or do [11:12] nothing. [11:13] Waiting, for example, for the next car. [11:16] Now, as you can imagine, if we want a [11:18] behavior that looks something like uh if [11:21] a car wants to enter, then the bar [11:23] should go up. [11:25] In reality, it would be a bit more [11:26] complicated. Most likely, you would need [11:28] to enter a ticket or something. But, [11:30] let's assume that uh this is uh a uh [11:33] free parking. The only thing is that you [11:34] want to regulate the rate at which new [11:36] vehicles enter the parking. [11:39] The gate has to stay open until the car [11:41] has gone through the gate. And finally, [11:43] the gate the gate has to lower the bar [11:46] once the car has gone through the gate. [11:49] So, how do we model this behavior by [11:52] using a state machine? [11:54] Well, first of all, we have to introduce [11:55] the notion of states. [11:58] And here there is some [11:59] freedom. I mean, we can specify a state [12:02] machine in many different ways. [12:04] Obviously, you would like to have a [12:06] state machine where the number of states [12:07] is as small as possible. [12:09] It occupies less memory, but most [12:12] importantly, is easy easier to [12:14] understand and easier to verify its [12:16] correctness. [12:18] But, having said that, sometimes there [12:20] is some flexibility, so coming up with [12:22] good state machines is actually an art. [12:26] So, in this case, it's quite simple. So, [12:29] the states, we can think of them as [12:31] being waiting for the next car, raising [12:34] the bar, the bar has been raised, or [12:36] we're lowering the bar. So, four states. [12:39] Inputs are a little bit more [12:40] complicated. And again, here you can see [12:42] how there is some freedom. [12:44] The a key question in state machines is [12:47] trying to find a minimal representation [12:48] in terms of states and inputs that [12:50] produce the desired behavior. More on [12:52] this later. But in this case, we choose [12:54] to use as inputs [12:56] the no car at gate, car at gate, gate at [12:59] top, not gate at top, gate at bottom, no [13:02] gate at bottom, car just exited, no car [13:04] just exited. [13:05] And then the output, see, let's think of [13:08] this as a sort of a display that the [13:10] gate is given to the driver or any [13:13] bystander, is whether the gate is [13:15] raised, lowered, or not. Not means no [13:19] operation. [13:20] So, we're just waiting for the next car. [13:28] So, there is no car at [13:32] um [13:33] gate. [13:38] No, you get the So, in in a given state, [13:40] you have uh one input only that allows [13:43] you to go to the next state. [13:45] Yeah. So, when the gate is at top, [13:48] the car has to be there, otherwise [13:52] uh the gate will be not at top. And [13:53] that's exactly what the state machine [13:57] Yeah. Yeah, that's actually a good [13:58] point. [13:59] So, when you analyze the state machines, [14:03] usually you also have to introduce [14:05] additional [14:07] uh states that encapsulate a notion that [14:10] there is some anomaly. [14:12] Like, for example, [14:14] um here the idea as we will see in the [14:16] state machine is that we're constantly [14:18] polling the sensor to check whether [14:20] there is a car. What if the sensor is [14:23] not returning any value? We're not [14:24] capturing that here, but in principle we [14:26] should capture that. And that would lead [14:28] us into another state that we don't have [14:31] here for simplicity, which is we have an [14:33] anomaly. Or what What if we have some [14:37] inconsistency in [14:40] the states that we observe? [14:42] Absolutely. But for simplicity here, I [14:44] just want to convey the notion of what [14:46] the basic state machine looks like. [14:48] So, the state machine then, as I said, [14:50] is represented as a graph where nodes [14:52] are the states, [14:53] and then the arcs are labeled by the [14:56] input that triggers a transition from a [14:59] given state to the next one, and the [15:01] corresponding label. [15:02] Like, for example, [15:04] if you're waiting, [15:05] we constantly poll the sensor. [15:07] If the input [15:10] is a not car at gate, then we do [15:13] nothing, and the label is no operation. [15:15] If it said that there is a car at gate, [15:17] then the label is raise, and we go into [15:21] the state where we are in raising mode. [15:24] Then [15:25] uh we constantly pull the sensor that [15:27] measure the angle of the gate. [15:30] If the [15:33] gate is not at top, [15:35] keep raising it. Basically, I do [15:36] nothing. Keep [15:38] uh [15:38] well, actually keep raising it. [15:40] And once we are at top, we transition [15:42] into the state that says raised. [15:45] Say that we pull the sensor every I [15:47] don't know, a second or so. [15:49] And then again, we have these loops [15:51] waiting for the car to go through. Or [15:54] once a car goes through, then we go into [15:56] the lowering. Then it takes some time to [15:58] go into lowering, and then we go back to [16:00] the waiting. [16:01] What are the tricky thing that can [16:02] happen? Like for example, maybe there is [16:05] a car that is tailgating, and the sensor [16:08] has not detected that. So, we might have [16:10] a car [16:11] that is going through while the bar is [16:13] lowering, and the state machine we have [16:15] no provision to handle that case. So, [16:17] you can see how immediately state [16:19] machines can become quite complicated, [16:22] and you might find the failure modes [16:24] that [16:24] maybe you do not uh [16:27] uh consider when you first design a [16:29] state machine. So, state machine is [16:30] actually architecting a state machine is [16:32] a bit of an iterative process. [16:34] You state machine, you test uh what [16:36] happens. [16:37] Most likely you [16:39] forgot to account for some failure mode. [16:41] You add the new states, new inputs, new [16:43] outputs, and then you keep iterating. [16:46] And we'll see a case um even though [16:48] again, state machines are not the [16:50] sexiest and most popular topic in [16:52] robotics, you'll see that [16:55] when there are like open source [16:56] projects, [16:57] many of the complaints or open tickets [17:00] are about the behavior of the underlying [17:02] state machine. And then we'll give an [17:03] example later on. [17:07] Now, [17:08] state machines allow us to specify the [17:10] behavior for a very broad class of uh [17:13] uh tasks uh we're interested in, [17:16] but not for everything. Like for [17:17] example, let's assume that you want to [17:19] devise a state machine [17:22] that tells us whether a given string of [17:25] arbitrary length [17:28] has a number of parentheses that is [17:30] balanced, meaning that you have an equal [17:32] number of opening parentheses and equal [17:34] number of closing parentheses. [17:36] Simple task, right? [17:38] No. [17:40] The problem is that we're saying here [17:43] that the string can be of equal length. [17:46] And so you might have a cases whereby [17:49] you keep counting and you have a [17:52] a certain number of parentheses and a [17:54] bigger number of that are opening bigger [17:56] number of parentheses that are closing. [17:58] The problem is that as you may try to [18:00] convince yourselves is that devising a [18:03] state machine for this task will require [18:05] an infinite number of states. [18:07] Which is in contrast to our assumption [18:09] of a finite state machine where we have [18:10] a finite number of states. [18:13] And in reality, it turns out and here I [18:16] will be quite brief [18:17] that the state machine are [18:20] a computational method in order to [18:21] specify behaviors, but in terms of [18:25] its modeling power, they are quite low [18:27] in the [18:29] um [18:30] a stack of a possible tools that you [18:33] will be using. [18:34] Turing machine, if you're aware of it, [18:36] is basically at the top in terms of a [18:39] um [18:41] a modeling computational power. Finite [18:43] state machines are more or less at the [18:44] bottom of the ladder. [18:46] Having said that, they're still very [18:48] useful and widely used. [18:52] All right. So, [18:54] the concept of a state machine is [18:56] relatively simple, but as I already [18:59] mentioned [19:00] a key challenge is how to architect them [19:04] in a way that they are not overly [19:06] complex [19:07] and second of all, they are correct. [19:10] One of the most basic tasks that [19:14] one has to deal with when architecting a [19:16] state machine is try to reduce [19:20] the number of states in your state [19:22] machine without losing [19:25] any behavior that you'd like your state [19:26] machine to generate. [19:29] Now, there are different ways of [19:31] architecting a state machine in a [19:33] principal way. [19:35] The first way that deals with the [19:37] problem of [19:38] reducing the number of states [19:41] encompasses a set of algorithms that [19:43] take as an input a state machine and as [19:46] an output produces a state machine that [19:48] produces the state behavior, but with a [19:50] number of states that is minimized. [19:51] Basically, the idea is to remove [19:54] redundant states and we'll see an [19:56] example in a second. [19:58] A second approach for architecting a [20:01] state machine in a principal way is to [20:03] use [20:04] architec- hierarchical decompositions [20:07] whereby you put together some states [20:08] into super states. [20:10] And this hierarchical composition allows [20:12] you to better understand the behavior of [20:15] the whole system without losing any [20:18] information. [20:19] And finally, using some common design [20:22] patterns in order to architect state [20:24] machines in a way that is as modular as [20:26] possible. [20:27] First of all, in order to have [20:28] interpretability. Second of all, in [20:30] order to possibly swap different modules [20:32] if you want to update some part of your [20:34] autonomous stack. [20:36] So, let's look first at the notion of [20:39] reducing the number of states of a state [20:42] machine. [20:43] So, the idea of and there are different [20:46] ways to do it. But, the idea is to [20:49] identify combined states that have an [20:51] equivalent behavior in an effort to [20:52] reduce the size of a state machine. [20:55] Equivalent states, broadly speaking, are [20:57] those states that produce [21:00] the same outputs and for all input [21:03] combinations, they transition to the [21:04] same states or equivalent states. [21:08] So, basically the idea is if by mistake [21:11] and that happens when state machines [21:13] become very complex, you have redundant [21:15] states, you duplicate states, you try to [21:17] remove them. [21:19] So, there are different algorithms to do [21:20] that, but one of the most one of the [21:22] simplest ones [21:24] proceeds by [21:26] first placing all states into [21:29] an equivalent class of states. This is [21:31] of course a course simplification. It [21:33] means that [21:35] uh you start with a hypothesis that your [21:36] state machine can be modeled with a [21:37] single state, [21:39] which in general is not true. [21:41] And then you start a partitioning this [21:43] course state by dividing into sub [21:47] partitions of states that are not [21:51] equivalent to each other. [21:52] In particular, the way to do it is first [21:54] to partition this initial set based on [21:57] how to be behavior, meaning states that [22:00] produce different outputs should be [22:02] belong to different classes. They're not [22:04] duplicates. [22:05] And second, you continue partitioning [22:09] the super set by [22:12] forming subsets that transition to [22:14] different states. [22:16] So, the idea is that you have a big [22:18] state machine, [22:19] collapse everything to one state that in [22:21] general is too coarse, and then you [22:23] start partitioning. [22:25] We're going to see an example. [22:26] Uh [22:27] the good news is that these algorithms [22:29] are relatively fast. [22:32] Let's see an example. So, here the task [22:34] is to [22:36] detect a given sequence. [22:38] Basically, you are given as an input [22:42] sequence of [22:44] 01 numbers. [22:45] We want for the state machine to output [22:48] after it has seen the third number, [22:50] whether one of those two sequences have [22:53] been detected. So, if you give as an [22:57] input sequence to the state machine 010, [23:00] it should output a true. [23:02] I've recognized it. [23:03] And we uh uh symbolize that with a one. [23:06] If we see instead 110, [23:10] we should also output one. If we see any [23:13] other three [23:15] number three-digit sequence, we should [23:17] output the false. We have not recognized [23:19] that sequence. [23:21] So, how would you design a state machine [23:23] for this problem? [23:24] Well, the most [23:26] obvious way [23:27] is to consider [23:29] a a tree structure, whereby you start at [23:32] a state S of zero. [23:35] That's the initial state. [23:37] At this initial state, you can see two [23:39] possible input, either the digit zero or [23:42] the digit one. This will be the first [23:44] digit in the sequence. [23:46] So, if you see [23:48] zero, then you're going to a new state. [23:52] And if you see [23:54] one, then you're going into the other [23:56] state S2. [23:58] Then you get to serve the second digit. [24:01] So, again, you split into two possible [24:03] states. [24:05] S3 [24:07] S4 [24:10] S5 [24:12] S6 [24:14] So, this is if you get as an input zero, [24:17] this is if you get as an input one, [24:18] input zero, input one. [24:21] Now, we want to detect [24:23] >> [snorts] [24:23] >> uh input sequences uh 010 or 110. [24:31] So, in the third [24:33] we consider further the third digit. [24:39] So, this will be zero, this will be one, [24:40] this will be zero, this will be one, [24:42] this will be zero, this will be one, [24:44] this will be zero, this will be These [24:45] numbers are the inputs that I observe. [24:49] And then finally, [24:51] we reset the state machine to [24:55] again, the initial state at zero. After [24:57] seen three digits, either way we [24:59] recognize that the sequence or not, [25:01] whatever we go through the initial [25:03] state. [25:04] Now, here we have just to specify the [25:07] behavior in terms of uh [25:09] uh state input next state mapping. What [25:11] about the outputs? [25:13] Well, we want to detect uh sequence [25:15] either 010 110. Let's consider 010. The [25:19] sequence 010 will be detected if we are [25:22] in this following path. [25:24] So, if we have this transition, then we [25:26] output one, which means that we have [25:28] seen uh the sequence. But, all the other [25:31] transitions should output zero. [25:37] While for 110, it means that we are [25:40] here. So, here we output one, but here [25:42] we output zero. [25:44] Zero and zero. [25:46] Does it make sense? [25:49] So, this is a state machine that would [25:51] uh uh detect a sequence 010 110. [25:55] I put, say that uh the sequence is a 000 [25:59] as an input. So, I start here, first [26:02] digit brings me to S1, second digit [26:04] brings me to S3, second digit brings me [26:07] to um [26:09] the um [26:11] initial state, and it outputs a zero, [26:13] which means that this sequence was not [26:15] recognized. Yeah. [26:17] >> Wouldn't it be better to go instead from [26:19] S1 down to the S3 S4 just to go to S2 [26:24] because that's also the you think the [26:25] state one? [26:27] But, like [26:28] >> If you If you go from S0 to S1, [26:31] that's where it's taking a zero. And you [26:32] know that state S [26:33] >> That's exactly right. And that's the [26:35] point of this example. [26:36] >> Okay. [26:37] >> That this is the most trivial way of [26:39] setting up the state machine, [26:40] but it uses a number of states that is [26:43] not minimal. Actually, we can find a [26:44] state machine that produces the same [26:46] exact behavior [26:47] with a lower number of states. And as [26:50] you correctly mentioned, [26:53] notionally, S1 and S2 do not need it to [26:57] be split [26:59] because they capture the same notion. [27:01] So, they could be actually put together [27:03] as equivalent [27:04] um [27:05] states. And this is exactly what the [27:06] algorithm does. The [27:08] The what the algorithm does is to start [27:12] by putting all states [27:14] into an equivalent class of state. [27:17] So, essentially we're saying, let's try [27:19] to see if actually we can run this state [27:21] machine with the same input-output [27:23] behavior with only one state. [27:25] Well, in general, this is not true. And [27:27] in particular, the first way to split [27:29] this uh partitioning is to note that uh [27:32] states S6 and X4 [27:36] produces produces an output [27:38] something that is different from the [27:39] other states. So, obviously, we needed [27:42] to split this partition into two [27:46] uh [27:47] equivalent classes. [27:49] Now, the question is can and then use [27:52] these two states in order to craft the [27:55] state machine or I needed to keep [27:57] splitting? Well, we have to see again if [28:00] indeed all these states are here belong [28:03] to the same equivalent class or actually [28:05] they model different behavior. [28:07] Well, let's go let's first see [28:11] um [28:11] the um next state behavior. [28:15] So, in case of [28:17] uh S0, [28:19] S0 goes to S1 and S2. So, this same [28:22] partition. [28:23] Okay, so that's fine. [28:25] S3 [28:26] goes to S0, that belongs to this [28:28] partition, and S6 S5 goes to this [28:31] partition. So, these are compatible with [28:33] this partition. [28:35] But S1 [28:36] goes through goes to either S3 or S4. [28:40] But S4 belongs to the other partition. [28:42] So, actually [28:43] does not belong to this partition, I [28:45] have to introduce a new class. [28:47] And then I keep going. [28:49] And as a result, if I do this algorithm, [28:50] and one should have proof that actually [28:52] this algorithm produces the right uh [28:54] uh results, I find the four [28:58] states that allow me to specify the [29:01] state machine. In particular, the state [29:03] machine in terms of those four states [29:05] looks like this, which is basically what [29:07] you were saying. [29:08] So, we go from S0. [29:12] No matter what output, I say X. X means [29:15] that the output is no matter what input. [29:17] X means that the input can be either [29:20] zero or one. [29:22] We go to S 1 prime. [29:26] This would be the set [29:29] the model's equivalent class S1 S2. [29:31] Exactly what you were saying. [29:33] Then from uh S1 prime, [29:36] we can go to S3 prime or [29:43] S4 prime. [29:47] Then from S3 prime, [29:49] we go [29:51] uh no matter what the input [29:54] to S0. So, there is that. [29:59] Well, from S4 prime, [30:02] in the case of uh [30:05] the input one and zero, we also go to [30:07] the reset. But in the case of input one, [30:13] uh oh, sorry. In the case of input zero, [30:15] we output uh uh one. [30:19] Otherwise, we output zero. [30:22] So, let's see if this reduced state [30:24] machine produces the same behavior. [30:26] Like, for example, let's assume that uh [30:29] we want to detect 010. [30:32] So, whatever the first digit, we go to [30:34] S1 prime. Exactly what you were saying. [30:36] Also, this is zero, this is one. [30:38] If we get one, we're going to this state [30:40] here. [30:41] And then if we get a zero, we output [30:43] one. We have recognized the sequence. [30:46] So, let's look at 110. [30:51] We go to S1, we go to here. Again, we [30:54] see a zero, so we output a one. So, we [30:55] have recognized the sequence. Everything [30:57] else will be recognized as a [31:00] another sequence, so not recognized. [31:02] Yeah. [31:04] >> I thought in the previous slide we were [31:05] saying that this algorithm would take [31:07] polynomial time. But if you have to [31:09] generate the tree and then kind of like [31:12] split from from from that [31:15] from the tree up upwards, wouldn't that [31:18] take polynomial exponential [31:20] >> Yeah, I mean it's polynomial in the [31:21] number of [31:23] states. [31:24] So, and the polynomiality is referred to [31:26] the number of splittings. [31:29] Yeah. [31:30] No. No, no. The generation of the tree [31:31] is something that you have done, but [31:33] it's not part of the algorithm. [31:35] So, now there should be a proof to show [31:36] that actually this algorithm is correct. [31:38] Turns out that it's correct and there [31:39] are tools out there that take a state [31:41] machine as an input and produce a one [31:44] with a minimal dimensionality. So, which [31:46] is pretty cool. [31:48] Another way, and here we'll be quite [31:50] brief, [31:51] uh, um, [31:52] properly architecting a state machine is [31:55] to introduce a hierarchical [31:57] decomposition, whereby basically you [32:00] aggregate states into super states [32:04] and then you have transition in between [32:06] super states. This is basically to have [32:08] more [32:10] interpretability for your system. Again, [32:12] there are tools out there, [32:14] but I won't go into further details. [32:16] And finally, [32:17] a principal way of architecting a large [32:20] state machine is try to modularize it. [32:23] So, to have like a [32:25] small state machines that take care of [32:27] individual behaviors and then you [32:29] compose them according to some basic [32:32] operations. The three basic operations [32:35] entail sequential decomposition, whereby [32:38] the output of one of the state machines [32:40] become the input for the next one. [32:41] Of course, here we're assuming that the [32:44] output vocabulary for the first state [32:46] machine correspond to the input [32:47] vocabulary for the second state machine. [32:52] This is the so-called cascade [32:54] combination. You can also do a parallel [32:56] combination [32:57] whereby the assumption is that the input [32:59] vocabulary for the two state machines is [33:01] the same and then the output is simply [33:04] the concatenation of the two outputs. [33:09] And again, here is not much magic. It's [33:11] more like a design pattern. Try to think [33:13] in a modularized way in order to ease [33:16] the [33:18] correctness [33:19] correctness certification process. And [33:21] finally, the feedback construction [33:23] whereby the output is fed back as an [33:27] input. [33:28] This is, for example, used in order to [33:31] have a counters or this kind of state [33:33] machines. [33:35] All right. So, [33:37] um [33:40] state machines, as [33:42] as already said, [33:43] are relatively easy to grasp, but [33:46] designing good state machines is [33:48] remarkably hard. [33:50] So, now one of my PhD student, Benoit, [33:52] is going to give you some hands-on [33:55] uh [33:56] guidelines about how to properly design [33:59] a state machine, in particular, as it is [34:02] in the spirit of this class, we're going [34:04] to introduce a tool that is available [34:07] within the ROS environment that allows [34:09] you to design state machines in ROS. [34:12] Okay? [34:17] So, [34:19] you had this right, right? [34:20] >> Sorry? [34:20] >> You had this right? [34:21] >> Yeah, yeah, I know. [34:23] I should probably get to this. [34:25] I have the mic. [34:26] >> Wait. [34:31] >> All right. [34:32] Okay, so just bear with me for a second. [34:37] Sweet. Okay. [34:38] Um [34:39] so thank you Marco for the intro. So [34:40] yeah, so the for those who don't know [34:41] me, I'm Benoit. Um one of Professor [34:44] Pavone's [34:45] uh PhD student. And so yeah, we'll talk [34:47] a little bit about implementing [34:48] [clears throat] these state machines and [34:49] we'll look at code which I think is [34:51] exciting. So we'll look a little bit at [34:53] kind of practically speaking how we can [34:56] leverage some of these tools [34:58] um [34:59] and yeah, so [35:00] um so first basically a common strategy [35:03] uh so yeah, um [35:05] let's just backtrack a little bit for 1 [35:06] second. Uh [35:08] basically what I'm going to try to [35:09] convey in this section is a couple of [35:11] things. So first make it clear that all [35:14] the tools that I'm presenting here are [35:16] optional. So unlike a lot of things [35:19] when you're designing your robot, you [35:20] don't have to actually use a tool for [35:23] like you know an existing tool to design [35:25] your state machine. It's just it's but [35:27] it is nice to know that there are both [35:29] existing tools out there to help you and [35:31] there's also not only existing tools but [35:33] very very common ways of implementing it [35:35] that you should get kind of more [35:37] familiar with. Mostly because chances [35:40] are if you join like Zoox or Waymo, [35:43] the one of the first thing you'll have [35:44] to do is just look at their ginormous [35:46] code base and then try to navigate your [35:48] way around and find where their basic [35:49] state machine is. [35:50] And so there's a lot of kind of a lot of [35:52] this that you'll probably have to do. As [35:54] a recognizing the kind of like usual [35:55] patterns is is a good is a good thing. [35:58] So yeah, so one of the the thing that [36:00] most people do for is to leverage [36:02] basically object-oriented programming. I [36:03] mean everyone does this nowadays. [36:06] So you basically will build like a class [36:08] that will kind of abstract your state [36:09] machine [36:10] and that that class is going to keep [36:12] track for example, I mean a common way [36:14] is to keep track of kind of your state [36:15] and for example like a variable [36:18] that that stays that stays in that class [36:21] or and then have some sort of fixed rate [36:23] that will [36:24] you'll have some sort of method that [36:25] will be run at some fixed rate that will [36:27] update your state, update your [36:28] transition, get your inputs, uh do all [36:31] the kind of transitions that uh that you [36:33] need to to actually run your state [36:35] machine. [36:36] Um [36:37] we'll [clears throat] look at at things [36:38] a little bit more concrete uh just to [36:40] give you a sense. So, this is uh the [36:43] state machine for the flight mode [36:45] of uh PX4. So, for those who don't know [36:48] what PX4 is, it's basically one of the [36:50] most popular, probably [36:52] the most popular open-source uh [36:54] flight software for drones. Uh so, it [36:57] can do quadrotors, fixed wings, uh a lot [36:59] of things. So, if you ever have to fly a [37:01] robot, you probably [37:04] uh will find out about PX4. Uh and so, [37:06] one of the things that they have in the [37:07] documentation to just kind of convince [37:09] you that this is, you know, these these [37:11] ideas of finite state machines actually [37:12] being relevant is that basically that [37:14] their transition diagram for their [37:16] flight modes. Um and there's a lot of [37:18] care that goes into this and making sure [37:20] that uh it's simple sure that it also [37:22] reflects the code properly uh or that [37:25] the code that you're implementing [37:26] reflects in the state machine properly. [37:27] Uh but yeah, it just gives you a sense, [37:29] for example, in this like they have [37:30] their different flight mode that they [37:31] describe as, you know, for example, RTL [37:33] is return to land. Uh then it tells you [37:35] that, you know, you have a state that [37:36] corresponds to uh being [clears throat] [37:38] landed or to landing. [37:40] Um [37:41] and then you have a state that uh [37:43] corresponds to loitering, which is just [37:45] like kind of staying in the air. Uh so, [37:48] if you go look at kind of any existing [37:50] robotics uh stack that runs on real [37:53] robot, chances are you will be able to [37:55] find uh a finite state machine diagram [37:58] like this. [37:59] Uh [38:00] >> [clears throat] [38:00] >> and we'll look a little bit so and then [38:01] if you go look into actual code, so I [38:03] dug around a little bit and tried to [38:04] find a little bit find a little bit kind [38:06] of this the specific lines of what I'm [38:08] talking about. [38:10] Uh so, in in if you look in the PX4 [38:12] flight stack, they'll have a file, for [38:13] example, commander.cpp um [38:16] that's just like a C++ file that [38:17] essentially has this for loop that I'm [38:19] talking about. So, in that class, you [38:21] have a for loop that gets executed and [38:23] you can think of this as like the main [38:25] loop of the robot of the drone that's [38:26] flying. It's just going to execute that [38:28] at some fixed rate and then do inside [38:30] that loop do all these state transition [38:32] among the different state that you need. [38:34] And [38:35] it's the state machine abstraction is [38:37] helpful enough was it helpful enough to [38:39] like the hundreds of developers on PX4 [38:41] that they, you know, they have [38:43] abstracted that as a kind of a helper [38:45] function. So they even if you just go [38:48] and and kind of try to track how they're [38:50] actually implementing the state machine [38:51] they have like their dedicated tools to [38:53] just do that. And so you go look at for [38:55] example in their state machine [38:57] implementation they'll have something [38:58] that will check like [39:00] you know, for a given state [39:02] >> [clears throat] [39:03] >> if like the a given input was in that [39:05] case it's asking it to change the [39:08] navigation mode into acro mode [39:10] then it will try to update this the [39:13] vehicle status to say that you're in [39:15] acro mode. So this is obviously like [39:16] very simple. Usually you do like I mean [39:18] this imply this actually triggers a [39:19] whole bunch of other things but this is [39:21] like the simplest version you can think [39:22] of a transition. [39:24] For those that are curious acro mode is [39:26] the ones that people used to do [39:27] backflips and things so you might not [39:29] want to trigger it by accident. If you [39:32] go look so something that Professor [39:34] Pavone mentioned I was kind of curious [39:36] to see how mature their state machine [39:38] was [39:39] and on PX4 and see if you just go look [39:41] at like the issues on the state machine [39:43] for [39:45] for PX4 there's a lot of them that are [39:48] still open. There's about like 14 or 15 [39:51] with very intense discussions and back [39:55] and forth with 24 comments and people [39:57] screaming at each other about how the [39:59] right way of doing this. So it's very [40:01] interesting and it's open source so if [40:03] you're curious and if you want to help [40:05] out designing this [40:06] feel free to jump in. There's another [40:08] implementation of the state machine of a [40:10] state machine that [40:12] you probably have seen. Have you guys [40:14] looked at navigator.py yet? In the [40:16] homework? You have? Okay, sweet. So, [40:18] that's your state machine, right? [40:20] Um and that's like the simplest probably [40:21] state machine you could possibly come up [40:23] with for a robot that does something [40:24] interesting. Um but if you go look at [40:26] just how it's implemented, you basically [40:28] have, right, uh you have this uh run [40:30] function. Uh and then in that your run [40:32] function, you have a bunch of uh LF [40:34] statements, [40:36] uh which gives you uh tells you [40:37] basically, you know, given that you're a [40:39] certain mode, so our mode in our case it [40:41] probably corresponds to a state, right, [40:43] of our state machine. Uh it will check [40:45] different things, uh whether, for [40:46] example, you're aligned or whether [40:48] you're near your goal, and then it will [40:49] switch your your mode in the right [40:51] uh [40:51] to the right mode. [40:53] Um [40:55] Okay, let's talk a little bit more about [40:57] ROS, [40:58] uh like ROS tools specifically for state [41:01] machines. So, something that [41:04] uh you might not know is that ROS [41:05] actually [41:07] uh comes with, yeah, a tool that allows [41:08] you to do that. So, [41:10] uh that's also one of the reason why we [41:12] teach, I guess, like the concept of [41:14] state machine is uh because, you know, [41:17] at at the beginning of the class, we [41:18] basically explained that ROS comes with [41:19] all these tools that do all these magic [41:21] things that you can leverage. Uh that's [41:22] only true if you can cast your problem [41:25] to the format that those tools [41:28] uh want, right? Uh and so if you can [41:30] think of your problem in terms of like [41:32] designing a formal state machine, uh [41:34] then Dial actually allows you to use [41:36] some of these tools. So, it's important [41:37] that you understand kind of like the [41:38] first part of that lecture so you can [41:39] think of your problem, okay, you [41:40] recognize it that this is I'm designing [41:42] a finite state machine right now, uh and [41:43] then maybe it's like worth for me to [41:45] think about like the transitions and the [41:46] actual like formalism of it so that then [41:48] you can use tools like uh Smack, which [41:50] stands for uh state machine. Uh [41:53] uh And then and then, yeah, kind of have [41:56] like a whole bunch of tools with that. [41:57] So, not only does it allow you to kind [41:59] of implement this in like a very clean [42:01] way, in a abstract way, but if you [42:03] actually use Smack, then it also comes [42:05] with visualization tools so you can [42:06] monitor your state machines so that you [42:08] can, [42:09] um you know, share your state machine [42:10] amongst each other or even like include [42:12] it in a report on that final report, for [42:14] example. [42:15] Uh so we'll go a little bit into like [42:17] well how smack works, the basic syntax, [42:19] and we'll look at code as I promised. Um [42:21] so [42:22] for so the smack uh like framework [42:26] um [42:27] is uh basically comes with uh like these [42:29] two main components [42:31] uh which are basically state and [42:33] containers. So a container you can think [42:36] So a state is a state. I mean exactly [42:38] what you'd expect it to be. [42:40] Uh a container is for example a finite [42:42] state machine. So they have a slightly [42:44] more generic version of what a state [42:46] machine is just because they do kind of [42:48] fancy things with it. But uh you can [42:50] think of uh yeah a container as a state [42:52] machine and and I'll explain how you can [42:54] use that later. [42:55] Uh so the state um basically yeah, so [42:58] the state corresponds one-on-one with [43:00] the state that we described earlier. [43:02] Uh you basically when you implement [43:04] state and we'll I'll show you example [43:05] code of this, uh you'll inherit inherit [43:08] from uh smack.state which basically only [43:11] uh requires you So Python has no way of [43:13] actually enforcing you to do that, but [43:15] uh you should implement two functions [43:16] which is the constructor uh and then the [43:18] execute function [43:20] uh which will basically execute the [43:22] state. [43:23] Uh [43:24] and then [clears throat] the only [43:25] requirement is that your execute returns [43:26] outcomes. [43:29] Uh let's Yeah, okay. [43:31] So this basic syntax uh [43:33] literally, you know, taken from the [43:34] documentation. A lot of this is online, [43:36] so we're just going to walk through some [43:37] of this so that we can [43:39] uh you know, if you have questions, you [43:40] can just ask. [43:41] Uh so as I said uh basically you have [43:43] the constructor. Uh you can do kind of [43:46] arbitrary initialization. Which you'll [43:48] have The important thing is that when [43:49] you when you're constructor, you'll want [43:50] to define what the potential outcome of [43:52] your um of your state is. You'll see [43:54] where the outcome come in. Basically, [43:55] you can think of outcome uh they like a [43:57] common outcome would be like success or [43:59] failure. So let's say you're running a [44:01] state and you have like a success [44:02] successful outcome or an [44:04] uh uh, like failure outcome, uh then [44:07] that could map to for example a [44:08] different transition. Uh And then your [44:10] execute basically just does what it [44:12] needs to do. So, do a backflip and then [44:15] outcome success or failure, for example. [44:18] So, pretty simple. [44:20] Uh, [44:21] >> [cough and clears throat] [44:22] >> So, now the container is basically the [44:23] state the state machine the state [44:25] machine abstraction. And then what we're [44:27] going to do is you're going to [44:28] instantiate a container and then you can [44:30] add state to it and then add basically [44:32] the transition [44:34] to that. So, [44:36] if you go look at basically the basic [44:38] example also. So, if you create a state [44:40] machine [44:41] which just is that container, [44:43] essentially what you want to do is then [44:44] create So, foo in that case is for [44:46] example the state that I just showed [44:48] you. So, that'd be like one of the state [44:49] implementation and bar would be a [44:51] different state. [44:52] After you've created a state machine, [44:53] you would basically add two different [44:56] the two different state foo and bar and [44:57] then you could you'd say, "Okay, outcome [45:00] one." which could be for example [45:01] success. The what what you're going to [45:03] want to do is transition back to bar. [45:05] And then, you know, failure could be a [45:07] different outcome. You can also map to [45:09] outcomes of the state machine. It might [45:11] be clearer in the in this diagram [45:12] actually. There you go. So, [45:14] >> [clears throat] [45:14] >> what you just saw basically corresponds [45:16] to this state machine. So, they have the [45:18] two state where the outcome one [45:20] basically means that you're going to go [45:21] to [45:22] bar. So, you can think of outcome a [45:23] little bit as corresponding to like the [45:25] input formalism that we had before in [45:27] the state machines. And then outcome two [45:29] will do the other transition. And some [45:31] of the outcomes are basically like [45:32] outcome of the container, not of the [45:34] state, [45:36] but you don't really need to worry about [45:37] this. [45:39] Uh, [45:41] >> [clears throat] [45:41] >> let's maybe [45:43] look at the actual [45:46] code [45:47] of this and then [45:49] let's look at composition and then we'll [45:50] we'll look at code. So, two things. [45:53] So, you all these things that we talked [45:55] about so the composition the one we [45:57] talked about sequence [45:58] cascade parallel and feedback. Sorry. [46:00] They actually have basically one-to-one [46:02] correspondence with SMAC uh, basically [46:07] a container. So, what you can do is you [46:09] can create basically containers that can [46:11] sequence container, which is basically [46:13] you're going to give it like two state [46:14] machine and you're going to basically [46:15] that state machine the resulting state [46:16] machine is not like the cascaded version [46:18] of the state machines. [46:19] Uh and you can look up in the I won't [46:22] you know, we're not going to go into too [46:23] much of details of the syntax of this, [46:25] but just suffice to know that you know, [46:26] if you can break down your state machine [46:28] and kind of that with these different [46:31] patterns, then it makes it super easy to [46:32] use SMAC. Uh and and design the overall [46:35] state machine. [46:36] Uh and the other thing we'll look at [46:37] visualization a little bit, but SMAC [46:38] allows you to visualize [46:40] very easily. So, let's look at code cuz [46:42] that's more fun. [46:44] Uh okay, let's look at like the simple [46:46] example the foobar, right that we just [46:49] looked at just so that you see [46:51] basically what this would look like this [46:52] would look like. Does Can everyone see [46:53] this? [46:55] Is it like big enough? [46:58] Okay, so this is literally just like the [46:59] example that we had earlier. Uh [47:01] this is a state. Um maybe I'll I'll [47:03] [clears throat] start with the the [47:04] section here. [47:05] Uh so, in our main function, right? What [47:07] we're going to do is we're going to [47:08] initialize our node as we always do. [47:10] Then we will create a state machine [47:12] container [47:13] and we'll specify, you know, those are [47:15] the outcomes that are basically the the [47:17] outcomes of the state machine. [47:18] Uh and then [47:20] is [clears throat] if everyone familiar [47:21] with the with [47:22] syntax? [47:25] Probably not, right? It's like like [47:26] weird syntax. Okay, so all this does [47:29] so you have to use this for SMAC, but it [47:30] basically defines a block that sets [47:33] like a context essentially. So, it's [47:36] very it's really just a fancy way to for [47:40] to tell Python to basically go look at [47:42] this class and then this class basically [47:44] has a couple of functions that will set [47:46] up things in the background for you. And [47:48] then even if your code here fails, [47:51] uh it will tear it down. So, like a [47:54] classic example for this is like a file. [47:56] So, you could think of like you could [47:58] say, "Okay, with like this file opened, [48:00] go write this code in the file." And [48:03] then maybe your writing code fails, and [48:05] you want to make sure that the file gets [48:06] closed basically, so it doesn't stay [48:08] open and your your crashed program is [48:10] like holding on to open resources on [48:12] your computer. Uh then Dahl will allow [48:14] you to do that. Uh but [48:16] that's kind of you kind of don't really [48:17] need to understand any of this to just [48:19] use it. Uh [48:20] you just suffice to just like remember [48:22] that this is how you make sure that you [48:24] uh spit basically say that like that [48:26] state machine is the state machine that [48:28] all these states are being added to. So, [48:30] you're basically saying with the state [48:32] machine, I'm going to call add, so I'm [48:34] going to add those two states, uh foo [48:36] and bar, and then I'm going to execute [48:38] the state machine. So, executing will [48:42] uh basically start in initial state uh [48:44] and then will the first state that you [48:46] added, and then will uh [48:49] will do the transition until it exits [48:51] until there's basically no more [48:52] transitions to do. Uh [48:54] and we can run this code very easily, [48:56] and feel free to run it yourself, too. [48:59] Uh so, we're just going to start a [49:00] little raw score. [49:03] And it will give us a bunch of very [49:06] little useful info here that just [49:08] telling us basically the different [49:10] transition um [49:12] that uh we implemented. Uh so, it's [49:16] basically telling us, you know, just the [49:17] setup code. Essentially, all of this is [49:18] just telling us what like what you've [49:20] just built. Uh and then this is telling [49:22] you like the state, so it's executing [49:24] the first state foo, and then basically [49:26] it's saying that foo uh gave the outcome [49:28] outcome one, which it the state machine [49:31] knows that it needs it needs to [49:32] transition to state bar, and then as [49:33] expected, you're executing the state bar [49:35] after. [49:36] Um okay, I know this is not interesting, [49:38] but I will just show you something now [49:40] that is uh [49:42] probably way more interesting because [49:44] it's relevant to your final project uh [49:45] that you will need to implement. So, [49:48] um [49:48] that is this is interesting, but maybe [49:50] not an interesting example. Uh so, so [49:52] the [49:53] uh [49:55] something that we can do, right? So, as [49:57] you like I said, the basic navigator of [49:59] Pi is a state machine. [50:00] Um and [50:02] uh [50:02] I was curious to see if, you know, would [50:04] it be possible to rewrite uh basic our [50:07] navigator in the SMAC framework and what [50:09] that would kind of look like. So, um [50:12] just having a kind of a crack at it, uh [50:14] and this is not like the only [50:15] implementation, obviously, you can do, [50:16] but uh I'm going to show you a little [50:18] bit what, you know, you could do for [50:20] your own, for example, final project, if [50:22] you're trying to do something that's [50:23] more complicated. Uh so, I didn't [50:25] include all the states, but I included [50:26] some of them. Uh but, if you were [50:28] trying, for example, to implement [50:29] something that that does way more [50:31] complicated um uh states. So, one thing [50:33] that happened a lot in the previous [50:35] years is people would have things like [50:37] uh they would get stuck in a corner and [50:39] their state machine was not was [50:41] basically just stuck there. They had [50:42] like no kind of detection of the fact [50:44] that, you know, their EKF was going [50:46] haywire or uh that their sensors were [50:48] all bad. Um well, really, all they [50:50] should have done is just, you know, [50:51] reset all their localization, get to a [50:53] state that just resets everything, [50:55] potentially like moves backwards a [50:56] little bit, uh and then keep going. So, [50:58] you know, implementing these sort of [50:59] like fail-safe state can get you very, [51:01] very far for the final project. Uh and [51:04] SMAC can help you do that more [51:05] effectively. So, if you look at just [51:07] kind of what uh we implemented for the [51:09] kind of navigation, um [51:11] there's basically just kind of three [51:13] states, right? So, waiting state, that's [51:15] just like your TurtleBot. Your TurtleBot [51:16] is going to be waiting [51:18] uh and kind of not doing [51:20] like anything other than just waiting [51:21] for commands. Um [51:23] and so, you know, executing that state [51:25] essentially means that all you're doing [51:27] is, you know, you're sending zero [51:28] velocity uh to any to to your actuator. [51:32] Uh and then [51:32] >> [clears throat] [51:33] >> there's going to be another state, which [51:34] is going to be the planning state. [51:37] Uh so, the planning state [51:39] will basically define a couple of [51:41] outcomes, right? So, we've successfully, [51:43] which corresponds to basically what the [51:44] planner has been what what the planner [51:46] thinks just happened. Uh so [51:48] the outcomes could be a success, so [51:50] you've successfully computed a plan for [51:52] your tool bot, failure, [51:54] uh you've received a new command that is [51:56] basically giving you like a new goal, [51:57] right? Or you've received a new map, [51:59] which probably means you should replan, [52:02] uh or you you have an error, like you [52:04] when you computed it. Uh so if you look [52:06] at like the code inside, this looks a [52:08] lot I mean this basically you know what [52:09] your like replan function in navigator [52:11] is doing. Uh [52:13] >> [clears throat] [52:13] >> and then we're going to have a third [52:14] state, which is a tracking state. Uh and [52:16] the tracking state is going to be [52:18] uh basically your your you have an [52:20] existing plan, and all you're doing is [52:21] just kind of following it until uh you [52:24] until you reach the end. Um [52:26] and I think so the state in Jureli, [52:28] there's a lot of like little like [52:29] syntactic details here, which I think [52:31] are not super interesting, uh but [52:34] what's interesting is this, I think. So, [52:36] if you take time to actually write your [52:39] state of your tool bot in kind of this [52:41] nice abstracted framework, then when [52:43] you're designing your transition, they [52:45] could basically just boils down to these [52:46] couple of lines, and it's super clean, [52:48] it's super simple, it's easy to change, [52:50] modify, [52:51] uh to do whatever you want, to test. Uh [52:53] so for example, right? All I'm doing, [52:55] creating a state machine, I'm saying if [52:58] you're in the waiting state, and uh [53:01] you know, the output is like [53:03] nothing happened, then stay in the [53:05] waiting state, right? Uh but if you have [53:08] a new command if you're in the waiting [53:09] state and you're getting a new command [53:11] from someone on Arviz, for example, then [53:14] uh you should probably switch to mode [53:15] planning, something. [53:17] Uh for example, or planning, uh if you [53:20] know, you're if you're planning and you [53:22] have a success, then you should start [53:23] tracking it. Or if you have a failure, [53:25] then you should probably just stop and [53:27] wait, cuz you don't really have any good [53:29] plan, so you should probably just hang [53:30] tight. Uh and so you can like define all [53:32] these or for example, we have it that's [53:34] like a nice little makes it easy for you [53:36] to define like this transition without [53:38] having to like think about too much of [53:40] the details. It's like, okay, I will [53:42] make sure that like that state when it [53:44] detects like like the plan is old, [53:47] or the tracking state, so when I the [53:49] state that's tracking controller, that's [53:50] tracking the existing path, all right? [53:52] If it detects that it's old for whatever [53:54] reason, like maybe you're far from your [53:55] start or you the timer has expired, [53:59] then I'll just say that the plan has [54:00] expired, and then like whoever is [54:01] defining the state machine is going to [54:03] decide what to do. Maybe you re-plan, [54:05] right? Or maybe when the plan has [54:06] expired, you just like stop and you [54:07] wait. Um so yeah, so super easy to like [54:10] abstract and kind of think about this in [54:13] in like very much like the same [54:14] framework, like the same like very like [54:16] theoretically grounded framework that we [54:17] just talked about. Uh so I'm going to [54:19] run this and just show you something [54:21] else that you can do that I think is is [54:24] useful. [54:31] So uh I basically just have this launch [54:33] file that's running this like modified [54:36] uh navigator along with like all the [54:38] simulation stuff. [54:40] Um [54:42] and then so I have RViz, and then what [54:45] what I'm also going to finish with is [54:47] basically [54:48] uh just talk about this other tool now [54:49] that this allows you to do [54:51] to use, which is a a visualizer, which [54:54] is uh it's called Smach viewer. [54:58] And so if you run this So if you install [55:00] this tool, it's called Smach [55:01] {underscore} viewer, [55:03] uh [55:03] and then you can run it. Basically, what [55:05] it allows you to do is without like any [55:08] additional work on your part, because [55:10] you use the right formalism of state [55:12] machine and because you use the right [55:14] tool, you basically get this like nice [55:16] little visualization of what your state [55:18] is [55:20] >> [clears throat] [55:27] >> and [55:30] Sorry, that track was horrible. [55:33] Uh and now [55:35] not [clears throat] only does it gives [55:36] you a visualization to like make sure [55:37] that you know now you can inspect your [55:39] state machine and you can argue for [55:42] hours with your teammate whether [55:45] whether you know the error after waiting [55:46] should transition to tracking or should [55:48] transition to planning but when you're [55:50] executing your state machine for example [55:52] by giving your robot a new plan [55:55] you can actually see the state evolve on [55:57] your state machine right so it went to [55:59] tracking so it went very quickly to [56:01] planning and then because it's super [56:02] easy plan [56:03] it went [56:04] to tracking almost immediately but then [56:07] and then you knew the entire time that I [56:09] was in that state and as soon as it [56:10] transitioned back to the waiting state [56:12] then you know so that's I think it's a [56:15] super powerful tool when you're instead [56:17] of sitting there and just kind of [56:18] wondering what is my turtlebot doing [56:20] just kind of trying to running over that [56:22] fence and I have no idea what's going on [56:24] having something like smack viewer [56:25] running and just telling you oh you're [56:26] in this state looks like this transition [56:28] is not being triggered that can give you [56:30] a lot of insight and I can you give save [56:32] you a lot of time it's also just like a [56:34] nice way to document for other people [56:35] jumping in and just kind of trying to [56:37] figure out what they implemented over [56:38] the weekend so so yeah that's it [56:41] you smack is good there's obviously open [56:44] source software is always little quirks [56:45] here and there [56:46] but I think generally it's like [56:48] basically there we're happy to help you [56:50] guys kind of figuring out how to set it [56:51] up for your project if that's needed and [56:53] then smack viewer just like basically [56:55] comes for free right gives you awesome [56:57] visualization and just like good [56:59] monitoring so [57:00] that's it if you guys have questions I'm [57:02] happy to [57:03] to answer anything [57:11] >> So yeah so I recommend you to use smack [57:14] so traditionally what happens in the [57:16] final project is that the state machine [57:19] that the students architected were [57:21] fairly simplistic not accounting for [57:24] failure modes and so on and then in the [57:30] Um, [57:31] in the rush and in the under pressure, [57:34] it was very difficult for them to debug [57:36] errors. They had this monolithic [57:38] humongous [57:39] navigator.py file. Very difficult to [57:42] understand what was going wrong, what [57:43] type of transition was creating issues, [57:45] and so on. So, having said that, I [57:47] encourage you to be a little bit more [57:48] disciplined in programming. That is one [57:51] of the [57:52] key [57:53] learning objectives of this class. And [57:55] in particular, I believe that SMAC is [57:58] a relatively easy tool to use, but also [58:00] quite powerful. So, you could try if you [58:02] have time. So, what we're going to do [58:05] next time is then to move to the topic [58:08] of decision making under uncertainty. [58:10] So, for now, we have been talking about [58:13] uncertainty [58:15] only from the perspective of [58:16] localization and mapping. We're going to [58:18] talk about how uncertainty can be [58:21] accounted for in order to compute [58:24] decisions. [58:26] That will lead to the topic of Markov [58:29] decision processing, and in particular, [58:31] dynamic programming and approximate [58:32] dynamic programming. [58:34] Based on that, we'll have a final [58:35] lecture [58:37] after the Thanksgiving on reinforcement [58:40] learning. Of course, it's just a preview [58:42] of what you will see if you enroll in [58:45] 274B [58:48] about the topic of learning-based [58:50] perception and control. [58:52] All right, so I'll see you next time.