Subject: Re: FSM Enhancement Goals and Thoughts
From: Alec Stanculescu (alec@fintronic.com)
Date: Thu Dec 13 2001 - 10:54:54 PST
Cliff,
I came up with the following example of state machines, which we can
use, to bounce ideas around:
In FutureTown driver-less taxis are dispatched by a robot when
customers place orders by phone, describing in ascii (computer
processable) the origin and destination addresses.
The dispatcher must:
===================
- accept orders
- ask for the list of free taxis, upon receipt of an order, and
wait for list_timeout or for the list to arrive.
- send and emergency signal to system_maintenance and stay
out_of_order, if list_timeout arrives.
- select the best taxi for the job and send the job description to the
selected taxi, and wait for acknowledgement or for taxi_timeout,
when the list of free taxis arrives.
- send a taxi_maintenance signal, upon receipt of
taxi_timeout, and ask again for the list of free taxis.
- upon receipt of the acknowledgement the order is considered under
processing until a signal is sent by the taxi that it is free again
or until a cancel_ack signal is received. In case cancel_ack is
received the dispatcher must ask for the list of free taxis again in
order to select the best one for the job.
We shall not worry about how to select the best taxi, nor with how the
taxi manages to follow directions. Let us focus on the state machine.
Hints
-----
Inputs: Order, Free_taxi_list_available, list_timeout, taxi_timeout,
ack, cancel_ack
Outputs: system_maintenance, taxi_maintenance, job_description,
States: wait_for_order, wait_for_list, send_job, out_of_order...
To consider: the dispatcher must accept multiple overlapping orders.
Therefore, it must be capable of spawning of a new fsm for each order
received, to be able to monitor its completion (and in case of
cancel_ack to start again to select the best taxi), while accepting
new orders.
Or, alternatively, the dispatcher must keep info about the status of
each taxi and in each state check if a cancel_ack has been received
from taxis that accepted jobs.
The two alternatives allow us to understand the advantages of the
hierarchical state machine over the flat state machine.
The robot of the taxi must:
==========================
- wait for job_description from dispatcher, while sending a taxi_free
signal to dispatcher.
- respond to a job_description with an acknowledgement and proceed to
process the job.
- send a cancel_ack upon receipt of accident
- consider that the order was processed, upon receipt of customer_done
and wait for a new job_description.
Inputs: job_description, accident, customer_done
Outputs: taxi_free, ack, cancel_ack.
States: Wait_for_job, Processing, Out_of_Order
Describe the Dispatcher/Taxis system as a "Dispatcher state machine"
that communicates with multiple instances of the "Taxi state machine".
Note: Assume different clocks for each taxi and the dispatcher.
Suppose now that we want to improve
the dispatcher so that when it receives a taxi_free and it determines
that the newly available taxi may satisfy better an order in progress,
it may give the job description to the newly available taxi and
interrupt the job previously given to the other taxi.
To achieve the improvement we will split the "processing" state of taxi
into two states: going_to_customer, and going_to_destination and we
will add a new signal from dispatcher to each taxi (cancel_job) as
well as one signal from each taxi to dispatcher (cancel_job_ack).
This will show the need for transferring a FSM into another state from
another FSM (i.e. the dispatcher will transfer the taxi from the state
going_to_customer to the state wait_for_job. This may imply a protocol
which may be hidden at a higher level of abstraction.
We can also extend this example if necessary. The problem will become
more complicated when FutureTown decides to share its taxi pool with
NextTown... Issues of fairness, etc.
Alec Stanculescu
This archive was generated by hypermail 2b28 : Thu Dec 13 2001 - 10:54:52 PST