Finite State Machines

Finite state machines/automatons (FSM) are used to control various parts of the robot. More...

Classes

struct  robo_fsm
 Structure describing FSM. More...

Defines

#define FSM_SIGNAL(fsm_id, event)   __fsm_signal(FSM_GET_BY_ID(fsm_id), __##fsm_id##_##event)
 Sends an event to another automaton (FSM), running in another thread.
#define FSM_GET_BY_ID(id)   (&robot.fsm[FSM_ID_##id])
 Returns pointer to struct fsm identified by the id.
#define DBG_PRINT_EVENT(msg)   DBG("%s: event: %s\n", msg, fsm_event_str(fsm->event))
 Prints current event in a human readable form.
#define FSM_STATE(name)
 Defines a state function for finite state machine.
#define FSM_STATE_DECL(name)   int fsm_state_##name(struct robo_fsm *fsm)
 Declares a prototype of state function defined later.
#define FSM_TIMEOUT(ms)   __fsm_timespec_add_ms(&fsm->timeout, &fsm->now, (ms))
 Sets FSM's timeout.
#define FSM_TIMER(ms)   __fsm_timespec_add_ms(&fsm->timer, &fsm->now, (ms))
 Sets FSM's one-shot timer.
#define FSM_TIMER_STOP()   __fsm_timespec_invalidate(&fsm->timer)
 Stops the timer.
#define FSM_EVENT   ((__FSM_EVENT_ENUM)(fsm->event))
 Value of current event in state functions.
#define FSM_TRANSITION(next)
 Sets current state to next.
#define SUBFSM_TRANSITION(substate)
 Invoke state transition to sub-FSM.
#define SUBFSM_RET()
 Return from sub-FSM.

Typedefs

typedef int fsm_event
 Type for FSM events.

Enumerations

enum  fsm_common_events {
  __COMMON_EV_NOEVENT = 0, __COMMON_EV_INIT, __COMMON_EV_EXIT, __COMMON_EV_STATE_ENTERED,
  __COMMON_EV_RETURN, __COMMON_EV_TIMEOUT, __COMMON_EV_TIMER
}
 FSM events. More...

Functions

void fsm_init (struct robo_fsm *fsm, char *debug_name)
 FSM initialization.
int fsm_start (struct robo_fsm *fsm, pthread_attr_t *attr)
 Starts previously initialized FSM.
int fsm_destroy (struct robo_fsm *fsm)
 Deallocates all resources allocated by fsm_init().
const char * fsm_event_str (fsm_event ev)
 Returns string with the name of event submitted as parameter.

Detailed Description

Finite state machines/automatons (FSM) are used to control various parts of the robot.

Content:

Introduction

The FSM is a thread that executes specially structured code (function) as a response to some events. The events can be generated internally (see fsm_common_events), by another FSM or by some other piece of code. Every FSM is defined by structure robo_fsm and a set of state functions. There is exactly one "current" state function at a time. The goal of the current state functions is to react to events. The reaction to the event can be represented by an arbitrary piece of code that does something useful. It is also possible to change the current state (function) of FSM (so called state transition). Having several state functions, it is possible to react differently on the same events depending on what is the current state. Structuring the code as a set of state functions can sometimes ease the programming of complicated control tasks.

State Functions

The state function is a function taking a pointer to FSM structure as an argument and returning an integer value. To make declaration of state function easier, there is a macro FSM_STATE(). This macro declares the state functions and also adds some code to conditionally print debugging messages. Thanks to this macro, programmer can concentrate on the real programming task and the complexity of declaration is hidden.

The usual structure of state function is one big switch statement. The switch condition is the FSM_EVENT macro, whose value is the event (see section Events) to be handled. In the handling code you can execute whatever you want. Additionally, FSM infrastructure provides some useful functions and macros. To work with time, you can use FSM_TIMER() and FSM_TIMEOUT(). To execute transition to another state, use FSM_TRANSITION() or SUBFSM_TRANSITION() (see Sub-Automatons). To send an event to another FSM, use FSM_SIGNAL().

An example state function, whose only function is to wait 1 second before entering another_state is shown here:

FSM_STATE(my_state) {
  switch (FSM_EVENT) {
    case EV_STATE_ENTERED:
      FSM_TIMER(1000);
      break;
    case EV_TIMER:
      FSM_TRANSITION(another_state);
      break;
  }
}

For the above to work, it is important to declare the macro FSM_<id> before including header with event definition and fsm.h. See Events.

Events

An event is identified by an Event ID. This is a string usually starting with EV_ prefix. Every FSM can handle so called common events (e.g. EV_STATE_ENTERED) and also some additional events specific to the FSM. Those additional events are declared only for one FSM and can be sent to FSM from another place by the FSM_SIGNAL() macro. To avid programming errors we have three requirements for working with events.

  1. It is not possible to send an event to FSM, which didn't declare it. This situation should produce compile-time error.
  2. In a state function, an attempt to handle an event declared for another FSM should also produce compile-time error.
  3. If some event, which can be handled by the FSM, is omited in switch command, we want to be warned.

These requirements are hard to achieve in plain C. Therefore, additional events for FSMs are declared as a data structure in Python and there is a Python script, which converts this definition to .h a .c files.

The event definition (for example see roboevent.py) is a Python dictionary (associative array) called events. Keys to this dictionary are the lowercase identifiers of FSM. The value is another dictionary, which defined the events for that FSM. The key is the event ID and value is a comment.

The script, which generates .c and .h source code is called eventgen.py. In .h, there is one enum for each FSM with all events this FSM can handle. The members of enums are not directly event IDs, but some internal identifiers starting with double underscore (__). You should never use these identifiers directly in your application. Then, there are macros, which translates the event identifiers to internal event identifiers. Thanks to this, the above requirements 1. and 2. are fulfilled. Requirement no. 3 is also fulfilled because recent versions of GCC warns if some enum member is not handled in switch statement.

Note:
You have to always include the generated header file before fsm.h.

In the source, where you define your state function, you have to define macro FSM_<id>, whre <id> is uppercase identifier of FSM as defined in event definition.

Sub-Automatons

Sometimes, it may be useful to enter a state of sub-automaton and return back to current state after this sub-automaton finishes its task. You can enter the sub-automaton state by calling SUBFSM_TRANSITION(). When the sub-automaton is done, call from some of its state functions SUBFSM_RET(). Then the original state function will be called with EV_RETURN.

Sub-automaton calling can be nested up to the level of 10.

Define Documentation

#define FSM_GET_BY_ID ( id   )     (&robot.fsm[FSM_ID_##id])

Returns pointer to struct fsm identified by the id.

This macro should be defined by the application, which uses fsm.h.

Parameters:
fsm_id FSM indentifier. This is the uppercase variant of the string, which defines the FSM in definition of events in python source.

Definition at line 43 of file robot.h.

#define FSM_SIGNAL ( fsm_id,
event   )     __fsm_signal(FSM_GET_BY_ID(fsm_id), __##fsm_id##_##event)

Sends an event to another automaton (FSM), running in another thread.

Event sending is asynchronous, but each thread a buffer for only one event. If this buffer is occupied, the calling thread waits until the previous event is noticed by the receiving thread. Therefore it is not a good idea for FSM to signal itself (possible deadlock).

Note:
This macro ensures that it is not possible to send an event to other FSM than the one for which it was declared. If you get compilation error, that __<FSM_ID>_<EVENT_ID> is not declared, it means the recipient doesn't handle this event.
Parameters:
fsm_id Event recipient's ID.
event Event to send.

Definition at line 262 of file fsm.h.

Referenced by FSM_STATE(), new_goal(), new_trajectory(), notify_fsm(), robot_goto(), robot_trajectory_add_final_point(), and trajctory_recalc().

#define FSM_STATE ( name   ) 

Value:

static inline void fsm_state_##name##_impl(struct robo_fsm *fsm, int *__ret); \
        int fsm_state_##name(struct robo_fsm *fsm) {                    \
                int ret=RC_WAIT;                                        \
                DBG_FSM_STATE(#name);                                   \
                fsm_state_##name##_impl(fsm, &ret);                     \
                return ret;                                             \
        }                                                               \
        static inline void fsm_state_##name##_impl(struct robo_fsm *fsm, int *__ret)
Defines a state function for finite state machine.

This function is called by FSM framework whenever some event occurs. The event can be read by using FSM_EVENT macro. In the function body, other FSM_xxx macros can be used to invoke state transition or set timeout or timer. When no state transition is invoked, FSM waits for the next event, after the function returns. Then, after another event occurs, this state function is called again with that event.

Note:
The body of state function is declared as void inline function. This function is called from state function stub, which contains debugging macros.
The actual name of the function stub is fsm_state_<name> and the name of inline implementation is fsm_state_<name>_impl.

Parameters:
name Name of the state.

Definition at line 312 of file fsm.h.

#define FSM_STATE_DECL ( name   )     int fsm_state_##name(struct robo_fsm *fsm)

Declares a prototype of state function defined later.

Parameters:
name Name of state function.

Definition at line 327 of file fsm.h.

#define FSM_TIMEOUT ( ms   )     __fsm_timespec_add_ms(&fsm->timeout, &fsm->now, (ms))

Sets FSM's timeout.

If no event arrives within the specified number of milliseconds, EV_TIMEOUT is generated. Before the state function is called, the timeout is always reset (to infinity).

Parameters:
ms The length of timeout in milliseconds.

Definition at line 338 of file fsm.h.

#define FSM_TIMER ( ms   )     __fsm_timespec_add_ms(&fsm->timer, &fsm->now, (ms))

Sets FSM's one-shot timer.

After the specified number of milliseconds elapses, EV_TIMER is generated. The difference from FSM_TIMEOUT() is that timer expiration is not reset automatically before a state function is entered. This means that the timer is not reset by arrival of any event.

Todo:
Shall we invalidate timer on state transition?
Parameters:
ms Time to timer expiration in milliseconds.

Definition at line 352 of file fsm.h.

Referenced by FSM_STATE().

#define FSM_TRANSITION ( next   ) 

Value:

do {                                                            \
                FSM_TIMER_STOP();                                       \
                fsm->last_state = fsm->state;                           \
                fsm->state = &fsm_state_##next;                         \
                fsm->event = EV_STATE_ENTERED;                          \
                *__ret=RC_PROC;                                         \
        } while(0)
Sets current state to next.

The state is not changed immediately. The rest of current state function finishes its execution and then, a call to the new state function is executed with EV_STATE_ENTERED as event.

Parameters:
next Next state.

Definition at line 383 of file fsm.h.

Referenced by FSM_STATE().

 
#define SUBFSM_RET (  ) 

Value:

do {                                                            \
                fsm->last_state = fsm->state;                           \
                fsm->state = *(--fsm->fnc_sp);                          \
                fsm->event = EV_RETURN;                                 \
                *__ret = RC_PROC;                                       \
        } while(0)
Return from sub-FSM.

Definition at line 416 of file fsm.h.

#define SUBFSM_TRANSITION ( substate   ) 

Value:

do {                                                            \
                FSM_TIMER_STOP();                                       \
                *(fsm->fnc_sp++) = fsm->state;                          \
                fsm->last_state = fsm->state;                           \
                fsm->state = &fsm_state_##substate;                     \
                fsm->event = EV_STATE_ENTERED;                          \
                *__ret = RC_PROC;                                       \
                return;                                                 \
 } while(0)
Invoke state transition to sub-FSM.

The behaviour is almost the same as of FSM_TRANSITION(), but whenever the sub-FSM returns (see SUBFSM_RET), the current state function is executed with EV_RETURN as event.

Parameters:
substate Initial state of sub-FSM.

Definition at line 401 of file fsm.h.

Enumeration Type Documentation

enum fsm_common_events

FSM events.

Enumerator:
__COMMON_EV_NOEVENT  Never happens.
__COMMON_EV_INIT  The FSM was just initialized.

This event is sent only once and it is the first event delivered to FSM.

__COMMON_EV_EXIT  Sent as last event before FSM exits the event loop.

__COMMON_EV_STATE_ENTERED  A transition to this state was just executed.

__COMMON_EV_RETURN  Previously called sub-automaton reached its final state.

__COMMON_EV_TIMEOUT  No event occurred within the time interval specified by FSM_TIMEOUT().
__COMMON_EV_TIMER  The timer previously set by FSM_TIMER() expired.

The difference from timeout is that timeout is "canceled" by reception of any event whereas timer is not.

Definition at line 7 of file fsm_common_events.h.

Function Documentation

int fsm_destroy ( struct robo_fsm *  fsm  ) 

Deallocates all resources allocated by fsm_init().

Parameters:
fsm FSM to destroy.
Returns:
Zero in case of success, non-zero otherwise.

Definition at line 262 of file fsm.c.

Referenced by robot_destroy().

Here is the caller graph for this function:

const char* fsm_event_str ( fsm_event  ev  ) 

Returns string with the name of event submitted as parameter.

Parameters:
ev Indetifier of the event
Returns:
The name of event or "undefined event!!!" if the ev doesn't refer to a valid event.

Definition at line 9 of file roboevent.c.

void fsm_init ( struct robo_fsm *  fsm,
char *  debug_name 
)

FSM initialization.

Prepares EV_INIT to be sent as the first event.

Parameters:
fsm FSM to initialize
debug_name A string used to identify the FSM in debugging massages.

Definition at line 212 of file fsm.c.

Referenced by robot_init().

Here is the caller graph for this function:

int fsm_start ( struct robo_fsm *  fsm,
pthread_attr_t *  attr 
)

Starts previously initialized FSM.

A thread is created, which executes fsm_thread_routine().

Parameters:
fsm FSM to start.
attr Attributes for thread creation.
Returns:
Return value of pthread_create().

Definition at line 245 of file fsm.c.

Referenced by robot_start().

Here is the caller graph for this function:

Generated on Thu Sep 13 11:28:29 2007 for DCE-Eurobot by  doxygen 1.5.3