Roboter werden immer ausgeklügelter und können komplexe Aufgaben in verschiedenen Umgebungen ausführen. Eine effektive Möglichkeit, ihr Verhalten zu programmieren, ist durch den Einsatz von Finite State Machines (FSMs). FSMs bieten einen strukturierten Ansatz, um verschiedene Zustände zu verwalten, in denen sich ein Roboter befinden kann und wie er zwischen ihnen übergeht. Sie sind ein grundlegendes Konzept in der Robotik, eingebetteten Systemen und der KI von Spielen, weil sie komplexe, reaktive Verhaltensweisen in ein klares, vorhersagbares Modell verwandeln. Dieser Artikel untersucht die Theorie hinter FSMs, praktische Implementierungstechniken, häufige Fallstricke, fortgeschrittene Varianten wie hierarchische Zustandsmaschinen und wie sie mit modernen Alternativen wie Verhaltensbäumen verglichen werden.

Was ist eine Finite State Machine?

Eine Finite-State-Maschine ist ein Rechenmodell, das aus einer endlichen Anzahl von Zuständen besteht. Der Roboter befindet sich immer in einem Zustand zu einem Zeitpunkt und wechselt in andere Zustände, basierend auf bestimmten Eingaben oder Bedingungen. Dies macht FSMs ideal für die Gestaltung vorhersehbarer und überschaubarer Roboterverhalten. Zu jedem Zeitpunkt wird die gesamte Geschichte des Systems durch seinen aktuellen Zustand erfasst. Die Zukunft hängt nur von diesem Zustand und dem eingehenden Eingang ab.

Diese Eigenschaft, bekannt als die Markov-Eigenschaft, gibt FSMs ihre Einfachheit und Überprüfbarkeit.

Die früheste formale Arbeit über endliche Automaten datiert bis in die Mitte des 20. Jahrhunderts, und FSMs werden seit den 1970er Jahren in der Robotik eingesetzt. Sie erscheinen in allem, von einfachen Linienfolgerobotern bis hin zu autonomen Unterwasserfahrzeugen. Die wichtigste Erkenntnis ist, dass viele Roboteraufgaben in eine Reihe von diskreten Modi zerlegt werden können, jeder mit seinem eigenen Kontrollgesetz, seiner eigenen Sensorstrategie und seinen eigenen Abbruchkriterien.

Kernkomponenten einer Finite State Machine

Staaten

Zustände repräsentieren die verschiedenen Modi oder Verhaltensweisen, die ein Roboter zeigen kann. Jeder Zustand kodiert eine bestimmte Reihe von Aktionen und Reaktionen. Idle, Vorwärtsbewegung, Drehen, Hindernisse vermeiden, Objekt aufnehmen, und Drop-Off-ObjektZustände werden typischerweise als Kreise oder gerundete Rechtecke in Zustandsdiagrammen gezeichnet. Ein Roboter kann sich nur in einem Zustand gleichzeitig befinden - dieser gegenseitige Ausschluss macht das Denken über das System praktikabel.

Übergänge

Übergänge definieren die Regeln, die den Roboter veranlassen, von einem Zustand in einen anderen zu wechseln. Sie werden durch Ereignisse ausgelöst - Sensorablesungen, Timerabläufe oder interne Bedingungen. Ein Übergang beinhaltet normalerweise eine Schutzbedingung (z. B. "wenn Abstand"). < 0.5 m") and an optional action that executes during the switch. In a deterministic FSM, given a current state and an input, there is exactly one possible next state. Nondeterministic FSMs exist but are less common in robotics because they require backtracking or parallel exploration.

Inputs

Inputs sind externe Signale oder Daten, die Zustandsübergänge beeinflussen. In der Robotik stammen die Inputs von Sensoren (Lidar, Kamera, Stoßfänger, IMU) oder von internen Softwaremodulen (Navigationsziele, Batteriepegel). Sie können diskret (binärer Stoßsensor) oder kontinuierlich (Entfernungsmessung) sein. Um kontinuierliche Werte mit einem FSM zu verwenden, müssen sie in diskrete Ereignisse quantisiert werden - zum Beispiel "Hindernis erkannt" bei Reichweite < 0.3 m, and "obstacle cleared" when range > 0,5 m. Diese Quantisierung ist ein kritischer Entwurfsschritt, der die Robustheit des FSM bewirken oder brechen kann.

Aktionen

Aktionen sind die Verhaltensweisen, die ausgeführt werden, während sich der Roboter in einem bestimmten Zustand befindet. Diese können kontinuierlich sein (mit konstanter Geschwindigkeit fahren) oder One-Shot (einen Befehl an den Greifer senden). In Moore-Maschinen hängen Aktionen nur vom aktuellen Zustand ab. In Mealy-Maschinen können Aktionen auch von der Eingabe abhängen, die den Übergang verursacht hat. Die meisten Roboterimplementierungen sind Hybride - sie führen kontinuierliche Aktionen innerhalb von Zuständen aus und diskrete Aktionen bei Übergängen.

Mealy gegen Moore Machines

Zwei klassische Architekturstile existieren für FSMs. Moore-MaschineOutputs (Aktionen) sind ausschließlich mit dem Zustand verbunden. Messmaschine, Outputs werden mit den Übergängen selbst assoziiert. Betrachten wir zum Beispiel einen Roboter, der einen Sound abspielen muss, wenn er ein Hindernis erkennt. Bei einem Mealy-Ansatz wird der Sound während des Übergangs von "Moving" zu "Avoiding" emittiert.

Bei einem Moore-Ansatz würde der Sound kontinuierlich abgespielt, während er sich im Zustand "Avoiding" befindet. Mealy-Maschinen benötigen oft weniger Zustände, weil Aktionen durch Ereignisse ausgelöst werden können, anstatt zu verweilen, aber sie können während des Debuggens schwieriger zu verfolgen sein. Die meisten praktischen Roboter-FSMs nehmen einen Moore-Stil mit expliziten "on entry"-Aktionen an.

Implementierung von FSMs in Robot Software

Um einen Roboter mithilfe eines FSM zu programmieren, definieren Entwickler typischerweise jeden Zustand und die damit verbundenen Verhaltensweisen. Sie geben dann die Bedingungen an, unter denen der Roboter von einem Zustand zum anderen übergeht. Dieser Ansatz vereinfacht komplexe Verhaltenslogik und erleichtert das Debuggen. In der Software dominieren drei Implementierungsmuster:

1. Switch-Case (Nested Conditions)

Auf der einfachsten Ebene liest eine einzelne Schleife den Sensoreingang und verwendet eine FLT:0-Anweisung über die aktuelle Zustandsvariable. Jeder Fall enthält die zustandsspezifische Logik und die Bedingungen für Übergänge. Obwohl es einfach zu prototypisieren ist, wird dieses Muster für mehr als eine Handvoll Zustände unhandlich, da alle Übergangslogiken in einer monolithischen Funktion leben.

2. Zustandstabelle (Lookup Table)

Eine Zustandstabelle kodiert Übergänge in einer Matrix: Zeilen repräsentieren aktuelle Zustände, Spalten repräsentieren Ereignisse und Zellen enthalten den nächsten Zustand und optionale Aktion. Dieser Ansatz trennt die Übergangslogik vom Verhaltenscode und macht es einfach, sie zu ändern, ohne sie neu zu kompilieren (wenn sie aus der Konfiguration geladen werden). Es ist das Rückgrat vieler industrieller Robotersteuerungen.

3. Zustandsmuster (objektorientiert)

Im Zustandsentwurfsmuster wird jeder Zustand als eine separate Klasse implementiert, die von einer gemeinsamen Schnittstelle abgeleitet wird. Der Kontext des Roboters hält einen Zeiger auf das aktuelle Zustandsobjekt. Wenn die Eingabe eintrifft, delegiert der Kontext die Methode des Staates , die den aktuellen Zustand durch Austausch des Zeigers ändern kann. Dieses Muster ist sauber, erweiterbar und eignet sich gut für komplexe Roboter mit vielen Verhaltensweisen. Es wird im Roboterbetriebssystem (Robot Operating System, ROS) über Frameworks wie SMACH weit verbreitet.

Beispiel: Hindernisvermeidung mit Pseudocode

Betrachten wir einen Roboter, der durch einen Raum navigiert und Hindernisse vermeiden muss. Umzug und VermeidungWenn ein Hindernis erkannt wird (Reichweite) < threshold), the robot transitions to the Avoiding state, executes a turn, and then returns to Moving. Below is a simplified C++-like pseudocode using the State pattern:

In diesem Beispiel wird ein Timer im Zustand Ausweichen verwendet, um sicherzustellen, dass sich der Roboter eine Sekunde lang dreht, bevor er die Vorwärtsbewegung wieder aufnimmt. In einer echten Implementierung können Sie die Segelfreigabe überprüfen, bevor Sie zurückgehen.

Praktische Roboteranwendungen von FSMs

Linie nach

Ein Linienfolgeroboter kann drei Zustände haben: Folgen Sie der Linie, Suche nach Line, und SchnittpunktumschlagWenn die Linie verloren geht, geht der Roboter zu Search über, wo er ein geschwungenes Muster ausführt. Sobald die Linie wiedererlangt ist, kehrt sie zu Follow zurück. An einer Kreuzung geht sie in einen speziellen Zustand über, der eine Markierung liest oder eine vorprogrammierte Wendung ausführt.

Pick-and-Place-Betrieb

Industrielle Manipulatoren verwenden oft ein FSM, um ein Griff zu sequenzieren: Weiter zu Approach Pose, Umzug nach Grasp Pose, Schließen Greifer, Rücknahme, Umzug zum Place Approach, Offener Greifer. Jeder Zustand hat klare Ein- und Ausstiegsbedingungen. Sensoren (Kraftmoment, Nähe) lösen Übergänge zwischen diesen Zuständen aus, wodurch die Gesamtaufgabe robust für die Variation der Teilposition wird.

Autonome Exploration

In der mobilen Roboter-Exploration, Zustände wie Erforschen, Zurück zum Ziel, Aufladung, und Wiedereinziehung Die Roboter übergehen von Explore zu Recharge, wenn die Batterie leer ist. Wenn sie stecken bleibt, führt ein Recovery-Zustand eine Abfolge von Umkehrungen und Drehungen aus, bevor er zu Explore zurückkehrt. FSMs bieten eine natürliche Möglichkeit, diese Fehlerarten explizit zu behandeln.

Vorteile und Grenzen von FSMs

Vorteile

  • Vorhersagbarkeit: Verhalten ist klar definiert und leicht zu verstehen. Mit einem Zustandsdiagramm kann jedes Teammitglied genau sehen, was der Roboter in jeder Situation tun wird.
  • Modularität: Neue Verhaltensweisen können durch die Einführung neuer Zustände und Übergänge hinzugefügt werden, ohne bestehende Logik neu zu schreiben - insbesondere bei Verwendung des Zustandsmusters oder der Zustandstabellen.
  • Debugging: Das Isolieren von Problemen ist einfacher, wenn Verhaltensweisen in Zuständen organisiert sind. Sie können den aktuellen Zustand und die Ereignisse, die Übergänge ausgelöst haben, protokollieren, so dass es einfach ist, Fehler zu wiederholen und zu verfolgen.
  • Überprüfbarkeit: Da FSMs endlich sind, können formale Methoden angewendet werden, um Eigenschaften wie Lebendigkeit (der Roboter wird nie stecken bleiben) und Sicherheit (er tritt nie in einen verbotenen Zustand ein) zu überprüfen.

Beschränkungen

  • Explosionszustand: Wenn die Anzahl der Verhaltensweisen und Ereignisse wächst, kann die Anzahl der Zustände und Übergänge kombinatorisch explodieren.Ein Roboter mit 10 unabhängigen binären Eingängen könnte theoretisch 2^10 Zustände benötigen, um alle Kombinationen abzudecken - obwohl in der Praxis Zustände nach Relevanz gruppiert sind.
  • Skalierbarkeit: Klassische flache FSMs sind schwer über 20-30 Zustände hinaus zu halten.
  • Mangelnde Währung: Standard-FSMs behandeln nur jeweils einen Zustand. Roboter müssen häufig gleichzeitige Aufgaben ausführen (z. B. beim Navigieren nach Landmarken), wobei sich gleichzeitige Zustandsmaschinen oder hierarchische FSMs damit befassen.

Fortgeschrittene FSM-Varianten

Hierarchische Finite State Machines (HFSMs)

HFSMs, auch als Statecharts bekannt, erlauben es einem Zustand, einen oder mehrere Unterzustände zu enthalten. Navigieren Staat kann selbst eine FSM mit Unterstaaten sein Vorwärtsbewegung, Drehen, und VermeidungWenn der Roboter in einen Niedrige Batterie Situation während in jedem navigierenden Unterstaat, ein Übergang von den Eltern Navigieren Staat Andocken HFSMs reduzieren die Zustandsexplosion, indem sie gemeinsame Übergänge und Standardverhalten erlauben. Der Formalismus wurde 1987 von David Harel eingeführt und wird in UML-Zustandsmaschinen weit verbreitet eingesetzt.

Fuzzy Finite State Machines

In klassischen FSMs sind Übergänge klar – eine Bedingung ist entweder wahr oder falsch. Fuzzy-FSMs ersetzen die boolesche Logik durch Zugehörigkeitsgrade. Anstelle von "Hindernis erkannt = ja/nein" könnte die Eingabe beispielsweise "Hindernisnähe = 0,7" sein. Der Roboter könnte teilweise in den Ausweichen-Zustand übergehen, während er teilweise in Bewegung bleibt. Dies führt zu einem glatteren Verhalten, verliert aber die strenge Vorhersagbarkeit von knackigen FSMs.

Fuzzy-FSMs werden in der Roboternavigation verwendet, wo eine reibungslose Vermischung von Verhaltensweisen gewünscht ist.

Wahrscheinlichkeitsbezogene FSM

Probabilistische FSMs (auch Markov-Ketten genannt) weisen Übergängen Wahrscheinlichkeiten zu. Bei einer Roboteraufgabe können Sie die Wahrscheinlichkeit einer erfolgreichen Auswahl eines Objekts im aktuellen Zustand modellieren. Dies ermöglicht es dem Roboter, Aktionen zu wählen, die die erwartete Belohnung maximieren - ein Thema im Zentrum des verstärkenden Lernens. Obwohl probabilistische FSMs im deterministischen Produktionscode nicht so häufig sind, sind probabilistische FSMs eine wichtige theoretische Brücke.

Vergleich von FSMs mit Verhaltensbäumen

Verhaltensbäume (BTs) sind in der Robotik und der KI als Alternative zu FSMs populär geworden. In einem BT steuern zusammengesetzte Knoten (Selector, Sequence), wie Kinderknoten ausführen. Im Gegensatz zu FSMs haben BTs keinen einzigen "aktuellen Zustand", sondern durchqueren stattdessen einen Baum von der Wurzel an jedem Tick. Dies macht BTs modularer und wiederverwendbarer; Unterbäume können leicht kombiniert werden. BTs können jedoch aufgrund ihres impliziten Kontrollflusses schwerer zu debuggen sein und sind weniger zugänglich für formale Überprüfungen.

Für viele Aufgaben bieten FSMs ein einfacheres, intuitiveres Modell. Viele moderne Robotersysteme verwenden einen hybriden Ansatz: ein High-Level-FSM, das zwischen BT-gesteuerten Verhaltensweisen wechselt.

Mehr zu diesem Vergleich finden Sie unter Wikipedia Artikel über Verhaltensbäume.

Tools und Frameworks für Roboter-FSMs

Mehrere Motoren vereinfachen das Erstellen und Ausführen von FSMs auf Robotern:

  • ROS-SCHWERZ - Eine Python-Bibliothek, die ein State Machine Framework mit integrierter ROS-Themen, Aktionen und Dienste bereitstellt, das hierarchische Zustände und Introspektion unterstützt (Ansicht des aktuellen Zustands über die ROS-Konsole). SMACH-Dokumentation.
  • Pyro - Ein Python-Paket für Robotik, das eine leichte FSM-Implementierung für kleine bis mittlere Roboter enthält.
  • QP/C++ Ein eingebettetes Echtzeit-Framework (von Quantum Leaps), das ereignisgesteuerte aktive Objekte mit hierarchischen Zustandsmaschinen zur Verfügung stellt.
  • State Machine Compiler Tools wie Ragel und FLT:3 können Zustandsdiagramme in C-, C++- oder Java-Code kompilieren. Sie erzeugen effiziente, tabellengesteuerte FSMs ohne Laufzeit-Overhead.

Schlussfolgerung

Finite State Machines sind ein mächtiges Werkzeug in der Roboterprogrammierung, das es Entwicklern ermöglicht, zuverlässige und wartbare Verhaltenslogik zu erstellen. Mit fortschreitender Robotik-Technologie sind FSMs weiterhin eine grundlegende Technik für das Management komplexer autonomer Verhaltensweisen. Ihre Transparenz macht sie ideal für sicherheitskritische Systeme, in denen das Verhalten überprüft und verifiziert werden muss. Während neuere Paradigmen wie Verhaltensbäume Vorteile in Bezug auf Modularität und Skalierbarkeit bieten, bleiben FSMs die ideale Methode für Systeme mit klar definierten Modi und klaren ereignisgesteuerten Übergängen. Durch die Beherrschung der Kernkonzepte - Zustände, Übergänge, Eingaben und Aktionen - und das Lernen, sie mit hierarchischen und unscharfen Varianten zu erweitern, können Sie robuste Robotersoftware erstellen, die sich in der unvorhersehbaren realen Welt vorhersehbar verhält.