Drücken Sie „Enter“, um den Inhalte zu überspringen

Python | Zustandsautomat

Wie häufig in der Informatik versuchen wir Dinge aus der Realität in Modell abzubilden, die innerhalb eines Computers laufen. Genau das soll auch mit einem endlichen Automaten oder Zustandsautomaten (engl. State Machine) erfolgen. Kennzeichnend für einen Zustandsautomaten sind ein oder mehrere Zustände, Zustandsübergänge zwischen Zuständen und Aktionen, die einen Zustandsübergang auslösen. Der Übergang von einem in einen anderen Zustand ist nur möglich (zulässig), wenn zwischen diesen beiden Zuständen ein Zustandsübergang und die dazugehörige Aktion definiert sind. Daraus folgt, dass Zustandsübergänge immer gerichtet sind, also nur in eine Richtung gehen. Es ist zulässig, dass es von einem Zustand Zustandsübergänge zu verschiedenen Zuständen geben kann.

Betrachten wir beispielsweise eine Lichtzeichenanlage (ugs. Ampel), wie sie in Deutschland üblich sind. Die Zustände einer (sehr) einfachen Anlage wäre hier: Rot, Rot-Gelb, Grün, Gelb, Gelb-Blinken. Ein typischer Zustandsübergang ist der Übergang von Rot nach Rot-Gelb. Einen Zustandsübergang von Rot nach Gelb, oder von Rot unmittelbar nach Grün ist ein unzulässiger Zustandsübergang. Ausgelöst werden die Zustandsübergänge beispielsweise durch einen zeitgesteuerten Taktgeber, oder durch das Drücken eines Tasters bei Fußgängerampeln.

Die folgende Implementierung stellt die Basisklasse für einen einfachen Zustandsautomaten dar. Der Zustandsautomat wird initialisiert mit einem Startzustand und einer Liste von Zuständen und deren Zustandsübergängen. Vor und nach jedem Zustandsübergang kann optional eine individuelle Methode aufgerufen werden. Zusätzlich verfügt der Zustandsautomat über optionale allgemeine Methoden, die vor und nach jedem Zustandsübergang aufgerufen werden, sowie einer optionalen Methode, die bei einem unzulässigen Zustandsübergang aufgerufen wird. Ein unzulässiger Zustandsübergang führt nicht zu einem Zustandswechsel.

Code

# Statemachine.py
from typing import TypeVar, Generic, Callable

TState = TypeVar('TState')
TCommand = TypeVar('TCommand')


class StateMachine(Generic[TState, TCommand]):

    class StateTransition:
        CurrentState: TState
        Command: TCommand

        OnBeforeTransition : Callable[[], None] = None
        OnAfterTransition : Callable[[], None] = None

        def __init__(self, current_state, command):
            self.CurrentState = current_state
            self.Command = command

        def __cmp__(self, other):
            if isinstance(other, self.StateTransition):
                return self.CurrentState == other.CurrentState and \
                       self.Command == other.Command

            return False

        def __hash__(self):
            return 17 + 31 * self.CurrentState.__hash__() + \
                   31 * self.Command.__hash__()

    transitions = {}
    CurrentState : TState
    OnInvalidTransition: Callable[[TState, TCommand], None] = None
    OnBeforeTransition: Callable[[TState, TCommand], None] = None
    OnAfterTransition: Callable[[TState, TCommand], None] = None

    def __init__(self, initial_state : TState):
        self.CurrentState = initial_state

    def move_next (self, command : TCommand) -> TState:
        transition = None
        for k in self.transitions.keys():
            if k.CurrentState == self.CurrentState and \
                    k.Command == command:
                transition = k
                break

        if transition is None:
            if callable(self.OnInvalidTransition):
                self.OnInvalidTransition(self.CurrentState, command)

            return self.CurrentState

        if callable(transition.OnBeforeTransition):
            transition.OnBeforeTransition()
        if callable(self.OnBeforeTransition):
            self.OnBeforeTransition(self.CurrentState, command)

        next_state = self.transitions.get(transition)
        self.CurrentState = next_state

        if callable(transition.OnAfterTransition):
            transition.OnAfterTransition()
        if callable(self.OnAfterTransition):
            self.OnAfterTransition(self.CurrentState, command)

        return self.CurrentState

    def add_transition (self, start_state : TState, \
                        end_state : TState, \
                        transition : TCommand, \
                        before_transition: Callable[[], None] = None, \
                        after_transition: Callable[[], None] = None):
        key = self.StateTransition(start_state, transition)
        key.OnBeforeTransition = before_transition
        key.OnAfterTransition = after_transition

        self.transitions.__setitem__(key, end_state)

Verwendung

Die Verwendung dieser Implementierung soll am Beispiel der schon zuvor genannten Lichtzeichenanlage erfolgen. Hierzu zunächst die Modellierung der Entität Ampel:

# Ampel.py
class Ampel:
    Rot: bool = False
    Gelb: bool = False
    Gruen: bool = False

    def __init__(self):
        self.Rot = True

    def __str__(self):
        return "Rot: {} | Gelb: {} | Grün: {}".format(self.Rot, self.Gelb, self.Gruen)

Weiter geht es mit den Zuständen und den Aktionen:

# AmpelStatesAndCommands.py
from enum import Enum


class AmpelState(Enum):
    AutoRot = 0
    AutoRotGelb = 1
    AutoGruen = 2
    AutoGelb = 3


class AmpelCommand(Enum):
    Tick = 0

Die Zustände und Aktionen werden als Auflistung (engl Enumeration) implementiert. Hierzu ist in Python das Modul enum notwendig. Kommen wir nun zum eigentlichen, konkreten Zustandsautomaten:

# AmpelStatemachine.py
import Statemachine


class AmpelStateMachine(Statemachine.StateMachine[AmpelState, AmpelCommand]):
    ampel : Ampel = None

    def __init__(self, ampel : Ampel):
        super(AmpelStateMachine, self).__init__(AmpelState.AutoRot)
        self.ampel = ampel
        self.OnInvalidTransition = self.Fehler

        self.add_transition(AmpelState.AutoRot, \
                            AmpelState.AutoRotGelb, \
                            AmpelCommand.Tick, \
                            None, self.Rot_nach_RotGelb)
        self.add_transition(AmpelState.AutoRotGelb, \
                            AmpelState.AutoGruen, \
                            AmpelCommand.Tick, \
                            None, self.RotGelb_nach_Gruen)
        self.add_transition(AmpelState.AutoGruen, \
                            AmpelState.AutoGelb, \
                            AmpelCommand.Tick, \
                            None, self.Gruen_nach_Gelb)
        self.add_transition(AmpelState.AutoGelb, \
                            AmpelState.AutoRot, \
                            AmpelCommand.Tick, \
                            None, self.Gelb_nach_Rot)

    def Rot_nach_RotGelb(self):
        self.ampel.Rot = True
        self.ampel.Gelb = True
        self.ampel.Gruen = False
        print(self.ampel)

    def RotGelb_nach_Gruen(self):
        self.ampel.Rot = False
        self.ampel.Gelb = False
        self.ampel.Gruen = True
        print(self.ampel)

    def Gruen_nach_Gelb(self):
        self.ampel.Rot = False
        self.ampel.Gelb = True
        self.ampel.Gruen = False
        print(self.ampel)

    def Gelb_nach_Rot(self):
        self.ampel.Rot = True
        self.ampel.Gelb = False
        self.ampel.Gruen = False
        print(self.ampel)

    def Fehler(self, state: AmpelState, command: AmpelCommand):
        print("BLINKEN!!")

Die Klasse AmpelStateMachine wird abgeleitet von der oben gezeigten Basisklasse StateMachine, wobei die Zustände und Aktionen als generische Parameter der Klasse übergeben werden: Statemachine.StateMachine[AmpelState, AmpelCommand].

Die möglichen Zustandsübergänge werden über die Methode add_transition festgelegt. Der erste Parameter kennzeichnet hier den Ausgangszustand, der zweite Parameter den Zielzustand. Dann folgt als dritter Parameter die auslösende Aktion. die letzten beiden Parameter sind optional. Hier kann auf Methoden verwiesen werden, die vor, bzw. nach einem Zustandsübergang auszuführen sind. In unserem Beispiel gibt es nur Methoden, die nach einem Zustandsübergang ausgeführt werden.

Der Ampelzustandsautomat kann nun im Programm verwendet werden:

# Irgendwo im Quellcode...

ampel = Ampel()
statemachine = AmpelStateMachine(ampel)

print (statemachine.CurrentState)

Ein Zustandsübergang wird ausgelöst durch:

# [...]

statemachine.move_next(AmpelCommand.Tick)
print (statemachine.CurrentState)
Share This

Share This

Share this post with your friends!