The classic farmroad example

We use a classic example for a more complex state machine that originates from the book "Contemporary Logic Design" by Randy H. Katz:

A Traffic light controller

"A busy highway is intersected by a little-used farmroad [...]. Detectors are placed along the farmroad to raise the signal C as long as a vehicle is waiting to cross the highway. The traffic light controller should operate as follows. As long as no vehicle is detected on the farmroad, the lights should remain green in the highway direction. If a vehicle is detected on the farmroad, the highway lights should change from yellow to red, allowing the farmroad lights to become green. The farmroad lights stay green only as long as a vehicle is detected on the farmroad and never longer than a set interval to allow the traffic to flow along the highway. If these conditions are met, the farmroad lights change from green to yellow to red, allowing the highway lights to return to green. Even if vehicles are waiting to cross the highway, the highway should remain green for a set interval." [ Katz, Randy H.: Contemporary Logic Design. Redwood City, California 1994, p.421. ]

The following figure shows this scenario:

images/download/attachments/2523156/farmroad_figure.png

State machine diagram

The following state machine diagrams shows a solution to the problem. We replaced the U.S. traffic light switching scheme with a German one though.

The intersection

images/download/attachments/2523156/farmroad_state_machine.png

Highway open

The state machine starts with entering the ‘Highway open’ state. The state will change after receiving a detector signal, but not before the minimum time is elapsed.

In the beginning, the detector is checked too see If the 'Detector on' signal was already received. If it was, the minimum time for the highway to be open still has to elapse before the state is finished.

If a 'Detector on' signal wasn’t already received the minimum time has to pass and a 'Detector on' signal has to occur for the state to be finished.

Switching highway to farmroad

Switching from the highway to the farmroad happens in two steps. First the highway’s traffic light will be switched to yellow and farmroad’s traffic light will be switched to red-yellow. This phase will be finished after a certain fixed time has elapsed.

The second phase will switch the highway to red. This ensures that the intersection is completely blocked for all directions for a moment. This state is left as well after a certain time.

After the 2nd phase is finished the whole ‘Switching highway to farmroad’ state is finished.

Farmroad open

Then the state “Farmroad open” is entered. This will turn the farmroad traffic light to green.

After a fixed maximum period of time or when the detector goes off, the ‘Farmroad open’ state will be finished and the ‘Switching farmroad to highway’ state will be entered.

Switching farmroad to highway

The switch will be made in two steps (as in the first switch in the opposite direction). In the first phase, the highway traffic light will be turned to red-yellow and the farmroad will be turned to yellow. After a fixed waiting time has elapsed, phase two is entered. Now the farmroad’s traffic light becomes is switched to red. After a fixed time has elapsed, the switching is finished

Back to Highway open

Then the ‘Highway open’ state is entered once again. On enter, the highway’s traffic light will change to green.

The traffic light

images/download/attachments/2523156/traffic_light_state_machine.png

The traffic light state machine is simpler as the intersection’s state machine.

It has just four simple states that represent the phases of the traffic light in which different colors (or color combinations) show. The state machine reacts on ‘switch’ events. The flow of the state machine will be starting at the initial pseudostate and then switching to the ‘Red’ state. On receiving a ‘switch to red-yellow’ signal, the ‘Red’ state is finished and the state ‘Red-yellow’ will be executed. On receiving a ‘switch to green’ signal, the ‘Red-Yellow’ state is finished and the state ‘Green’ is entered and executed. On receiving a ‘switch to yellow’ signal, the state ‘Green’ is finished and the state ‘Yellow’ is entered and executed.

When the state machine will receive a ‘Switch to red‘, the state ‘Yellow’ will be finished and the next state, the ‘Red’ state will be active again.

Implementation with yasmine

As shown in the state machine diagrams above, the solution will contain multiple state machines with different elements. There will be different classes for the intersection itself, for the traffic light, and for the detector.

UML class diagram

images/download/attachments/2523156/farmroad_class_uml.png

The detector class

The detector class will asynchronously and randomly generate timed events for 'Detector on' and 'Detector off' simulating vehicles approaching and crossing the intersection. The generator will do this in its own thread. So, the detector will need to be started at the beginning and stopped after it is not used any more. It has a public method for checking if the detector is on or off.

The detector class constructor takes a parameter that is a detector callback interface. This interface will be inherited and implemented by the intersection class. When an event is generated, the intersection will receive the event via this callback interface.

start()

void detector::start()
{
run_ = true;
generate_random_detector_events_ =
SX_MAKE_UNIQUE< sxe::thread >( sxe::bind( &detector::generate_detector_events, this ) );
}

The start method will create and start a new thread that will generate detector events.

stop()

void detector::stop()
{
{
sxe::unique_lock< sxe::mutex > lock( mutex_ );
run_ = false;
}
condition_variable_.notify_all();
SX_ASSERT( generate_random_detector_events_->joinable(), "Event generator thread is not joinable!" );
generate_random_detector_events_->join();
generate_random_detector_events_.reset();
}

The stop method will turn the flag for running to false and through this will notify the generating thread to stop. The thread is then joined.

is_on()

bool detector::is_on()
{
sxe::unique_lock< sxe::mutex > lock( mutex_ );
return( is_on_ );
}

The method is_on will return a bool value that tells if the detector is on (true) or if the detector is off (false) at the very moment.

generate_detector_events

This function will generate detector events ('Detector on' and 'Detector off') randomly and asynchronously. The succession of 'Detector off' and 'Detector on' will be always off-on-off-on... This happens in a loop until the detector is stopped. The events are generated randomly after a duration (in a given time interval).

For each event that is generated, the detector callback will be called to notify the intersection about the event (via detector_off() or detector_on()).

The traffic light class

The traffic light class has a state machine as a member. The state machine needs to be started and stopped (the state machine will process events - changing the colours - asynchronously in a separate thread).

First, in the constructor of the class, the method that builds the state machine is called: build_traffic_light_state_machine. The class has start() and stop() methods, and methods for switching the traffic light (which internally fire different switch events).

build_traffic_light_state_machine

void traffic_light::build_traffic_light_state_machine()
{
composite_state& root = traffic_light_state_machine_.get_root_state();
region& main_region = root.add_region( "main_region" );
initial_pseudostate& initial_pseudostate = main_region.add_initial_pseudostate( "initial" );
 
// states
sxy::simple_state& red_state = main_region.add_simple_state( "Red",
Y_BEHAVIOR_METHOD2( this, &traffic_light::on_traffic_light_red ) );
sxy::simple_state& red_yellow_state = main_region.add_simple_state( "Red-Yellow",
Y_BEHAVIOR_METHOD2( this, &traffic_light::on_traffic_light_red_yellow ) );
sxy::simple_state& green_state = main_region.add_simple_state( "Green",
Y_BEHAVIOR_METHOD2( this, &traffic_light::on_traffic_light_green ) );
sxy::simple_state& yellow_state = main_region.add_simple_state( "Yellow",
Y_BEHAVIOR_METHOD2( this, &traffic_light::on_traffic_light_yellow ) );
// transitions
traffic_light_state_machine_.add_transition( sxy::Y_COMPLETION_EVENT_ID, initial_pseudostate, red_state );
traffic_light_state_machine_.add_transition( EVENT_SWITCH_TO_RED_YELLOW::get_event_id(), red_state,
red_yellow_state );
traffic_light_state_machine_.add_transition( EVENT_SWITCH_TO_GREEN::get_event_id(), red_yellow_state, green_state );
traffic_light_state_machine_.add_transition( EVENT_SWITCH_TO_YELLOW::get_event_id(), green_state, yellow_state );
traffic_light_state_machine_.add_transition( EVENT_SWITCH_TO_RED::get_event_id(), yellow_state, red_state );
}

Each state will have a do behavior assigned that will call a specific method which is responsible for controlling the lights of the traffic light (in this example by writing the color name to the console).

The transitions will be triggered by different events IDs. The events are created using the the macro Y_EVENT_CREATE and they are defined in an anonymous namespace:

Y_EVENT_CREATE( EVENT_SWITCH_TO_RED_YELLOW, 1 )
Y_EVENT_CREATE( EVENT_SWITCH_TO_GREEN, 2 )
Y_EVENT_CREATE( EVENT_SWITCH_TO_YELLOW, 3 )
Y_EVENT_CREATE( EVENT_SWITCH_TO_RED, 4 )

switch_to_red_yellow/switch_to_green/switch_to_yellow/switch_to_red

These public methods will be called from the intersection and will fire different events in the state machine.

For example, the switch_to_green looks like:

void traffic_light::switch_to_green()
{
traffic_light_state_machine_.fire_event( EVENT_SWITCH_TO_GREEN::create() );
}

The intersection class

The intersection class contains an asynchronous state machine (async_state_machine) for the implementation of the intersection state machine. It owns two traffic lights: one for the farmroad and one for the highway. Also, it has a detector for generating the 'Detector on' and 'Detector off' events.

The intersection uses the class timed_event_creator for generating the time-based events like the maximum time that the farmroad can remain open, the minimum time that highway must stay open, or for the timings of the intermediate stages when switching from one direction to the other.

Finally intersection class has a start and a stop method.

start()

bool started = false;
sxy::state_machine_defects defects;
intersection_state_machine_.check( defects );
if( defects.empty() )
{
farmroad_traffic_light_.start();
highway_traffic_light_.start();
timed_event_creator_.run();
intersection_state_machine_.run();
detector_.start();
started = true;
}
else
{
std::cout << "The state machine is defect." << std::endl;
write_defects_to_log( defects );
}
return( started );

The start() method checks the state machine for defects and if there is no defect, it will start the state machine. Also the time event creator will be started just after the two traffic lights (one for the highway and one for the farmroad). Finally the detector is started as well.

If one or more defects are found, the method will log the defects.

stop()

void intersection::stop()
{
detector_.stop();
intersection_state_machine_.halt_and_join();
timed_event_creator_.halt_and_join();
highway_traffic_light_.stop();
farmroad_traffic_light_.stop();
}

The stop method will reverse the process of stopping and thus stop the detector, the traffic lights and the time event creator. After that, the intersection state machine will be stopped.

build_intersection_state_machine()

In this method the intersection's state machine is created and assembled. Each element of the state machine is created using the specific add member function of the parent element. For example:

sxy::composite_state& l_highway_open = main_region.add_composite_state( "highway open",
Y_BEHAVIOR_METHOD2( this, &intersection::highway_open_entry ),
Y_BEHAVIOR_METHOD2( this, &intersection::highway_open_exit ) );

For the highway open state, we create the entry and the exit functors in which we use two private functions of the intersection class: highway_open_entry and highway_open_exit. This functors will be the behaviors of the state.

intersection_state_machine_.add_transition( EVENTS_EXIT_FARMROAD_OPEN, farmroad_open, switching_to_highway,
sxy::transition_kind::EXTERNAL, Y_EMPTY_GUARD,
Y_BEHAVIOR_METHOD2( this, &intersection::cancel_timer_event_on_detector_off ) );

For the transition that is triggered on 'Detector off' event, we build also a functor (lambda function) using the macro Y_BEHAVIOR_METHOD2 in which the private function cancel_timer_event_on_detector_off is called.

highway_open_entry()

void intersection::highway_open_entry()
{
SX_LOG( hermes::log_level::LL_INFO, "Highway open." );
highway_traffic_light_.switch_to_green();
fire_timed_event( TIMER_HIGHWAY_MINIMUM_TIME_DURATION, timer_highway_minimum_time_event::create() );
}

In the highway_open_entry method the traffic light of the highway is turned to green and an event creation request for the elapsing of the minimum time for the highway to stay opened is enqueued. The request is done by calling the fire_timed_event method.

farmroad_open_entry()

void intersection::farmroad_open_entry()
{
SX_LOG( hermes::log_level::LL_INFO, "Farmroad open." );
farmroad_traffic_light_.switch_to_green();
farmroad_maximum_time_event_handle_ = fire_timed_event( TIMER_FARMROAD_MAXIMUM_TIME_DURATION,
timer_farmroad_maximum_time_event::create() );
}

In this method, the traffic light of the farmroad is turned to green. An event creation request for the elapsing of the maximum time for the farmroad to stay open is made. The handle of the enqueued event creation request is kept in the member farmroad_maximum_time_event_handle_ because the request will be possibly cancelled if the 'Detector off' event is triggered before the timer elapses.

cancel_timer_event_on_detector_off()

void intersection::cancel_timer_event_on_detector_off( const sxy::event& _event )
{
if( _event.get_id() == detector_off_event::get_event_id() )
{
if( farmroad_maximum_time_event_handle_ > 0 )
{
SX_LOG( hermes::log_level::LL_INFO, "Try to cancel event with handle %.", farmroad_maximum_time_event_handle_ );
if( timed_event_creator_.cancel( farmroad_maximum_time_event_handle_ ) )
{
SX_LOG( hermes::log_level::LL_INFO, "Event with handle % was cancelled.", farmroad_maximum_time_event_handle_ );
}
else
{
SX_LOG( hermes::log_level::LL_INFO, "Event with handle % could not be cancelled.", farmroad_maximum_time_event_handle_ );
}
farmroad_maximum_time_event_handle_ = 0;
}
else
{
SX_LOG( hermes::log_level::LL_INFO, "There is no event to be cancelled on detector off." );
}
}
}

The cancellation of the event creation is handled here. The state 'Farmroad open' can be possibly exited in two ways: when maximum time has elapsed or when the detector is off. When the detector is off before the maximum time has elapsed, we cancel the request for the maximum time event to be fired. To achieve this, the handle for the maximum time for the farmroad to stay open creation request is checked in order to make sure that the timer was started and an event creation request was enqueued. If a request was enqueued, we try to cancel by calling the cancel method of the timed event creator.

We log the results and then set the member farmroad_maximum_time_event_handle_ (this member will keep the handle that was generated enqueuing of the event creation request) to zero.

detector_on()

void intersection::detector_on()
{
std::cout << "Detector is on." << std::endl;
intersection_state_machine_.fire_event( detector_on_event::create() );
}

The detector_on() method is inherited from the interface detector_callback and it is overridden. It fires the 'Detector on' event.

detector_off()

void intersection::detector_off()
{
std::cout << "Detector is off." << std::endl;
intersection_state_machine_.fire_event( detector_off_event::create() );
}

The detector_off() method is inherited from the interface detector_callback as well and it is overridden. In here, the 'Detector off' event is fired.

fire_timed_event ()

int intersection::fire_timed_event( const sxy::milliseconds _milliseconds, const event_sptr _event )
{
handle_type event_handle =
timed_event_creator_.create_event_creation_request( sxe::milliseconds( _milliseconds ), _event );
return( event_handle );
}

The fire_timed_event helper takes a duration after which an event should be fired (duration in milliseconds) and the event (an event with ID _event_id is created) that should be fired as parameters. This method will enqueue the event creation request and will return the handle of the request. The handle will be forwarded to the caller by the fire_timed_event method.

main()

try
{
examples::intersection intersection_of_roads;
if( intersection_of_roads.start() )
{
std::cout << "To quit press 'q'." << std::endl;
wait_for_quit_input();
intersection_of_roads.stop();
}
else
{
SX_LOG( hermes::log_level::LL_FATAL, "The intersection could not be started." );
error_code = 1;
}
}
catch ( const std::exception& _exception )
{
SX_LOG( hermes::log_level::LL_FATAL, "Unhandled exception: '%'.", _exception.what() );
error_code = 2;
}
catch ( ... )
{
SX_LOG( hermes::log_level::LL_FATAL, "Unknown exception!" );
error_code = 3;
}
log_manager.halt_and_join();

In the main function, an intersection object is created and started. After a 'q' key is pressed on the keyboard, the intersection is stopped.

Also exception handling is done here and the log manager is configured.