Finite State Machine using Akka (1): modeling multiple elevators in a hotel

Background

That the Finite State Machine (more popularly known and referred to as FSM) is a fantastic tool to conceptualize and model the behaviour of a software component, is well-known. The principles of a Finite State Machine (FSM) help capture the possible inputs and outputs of the component as unambiguously as one wants. The rigour of mapping every input to every output (and associated changes internal to the component) can be quite demanding and at times, mind-twisting. In fact, it usually is so, for any non-trivial situation. However, the result is a piece of software which can be reasoned about confidently; its behaviour is always traceable and predictable. That, in itself, is a huge benefit.

This article is not about Finite State Machine (FSM) as such. From time to time, I refer to articles like the one by David Right for a thorough understanding. For a start, this WikiBook section is quite handy too. Many academicians and practitioners have written excellent books, papers and articles, not to forget the section on Wikipedia.
This is a chronicle (a few of them in series, which I plan to bring out in coming weeks) of my attempt to use the features and facilities of Akka ( http://akka.io ), the Actor-based message-driven runtime from Lightbend (https://www.lightbend.com/company). I assume here that you are generally aware of Akka’s Finite State Machine (FSM) type-support and APIs, provided in association with Actors’ philosophy and APIs.

Use Case to model

OK, to cut a long story short, here’s the use-case that I am trying to model:

In a hotel, more than one lift (elevators, if you like) are available for the guests. The lifts - lift carriages, to be a bit more precise - can stop at any floor, if a guest requests. Every floor as a lift-bay having as many doors as the number of lifts: a guest asks for the lift by pressing a button on any of the lift-doors. The key is this: a guest presses the button (intending to go up or down) on any of the multiple doors; but, which particular lift will serve her depends on some controlling logic. So, standing in a lift-bay, I may ask Lift[1] to serve me, but I may find that Lift[3] has come to take me in. The hotel has put in such a structure to serve the guests better: I choose any of the lifts, but the lift that can reach me the quickest, will move to where I am.  I am referring to this structure, as the Controller.

OK, so the Controller brings a lift to where I am. The lift lets me in.  I push a button on a panel mounted inside the carriage, to indicate where I wan to go to. The carriage then moves to my destination and lets me out. Straightforward, I suppose.

Our aim is to model this controlled movement of a carriage. So, we are not trying to simply explain a carriage’s operation as a Finite State Machine: we are trying to model  the interaction between the Controller and multiple carriages, so that the passenger is served in the quickest possible manner. And, We want to do that using Akka and its FSM facilities.

A basic elevator/lift

A lift’s behaviour is best modeled and understood by treating it as a Finite State Machine. It is easy and intuitive. Pictorially speaking:

Controller and Carriages

We are assuming that the Controller is responsible for operating the carriages: it switches a carriage on, instructs it to move around and finally switches it off. All the interactions between the Controller and the carriages are asynchronous: so, each of the carriages is modeled as an Actor, as well as the Controller.

As I have explained earlier, in the hotel, the Controller receives the button-press by a guest (or the passenger) and instructs one (may be, more: we will visit that possibility later) of the lifts to move to where she is. Our model follows this arrangement and lets the button-press reach the Controller and not the carriages.

There is an obvious case of a carriage waiting exactly at the floor that passenger is in (we assume that the door of the carriage remains open). In that case, she doesn’t press a button and walks in. Please note that the Controller is unaware of the passenger’s presence in this case.

Source and Destination Floor

The above arrangement tells us how  the Controller determines the the Source Floor. But how does the passenger indicate where does it want to go? Once inside the carriage, she presses a button on the mounted panel to indicate which floor is her destination.  Then, the carriage transports her to the destination, dutifully.

Thus, the carriage has two reasons to move:

1. When the Controller instructs it to move to a floor where a passenger is waiting  
2. When a passenger (already having stepped in) instructs it to move to a particular floor (buttons on the panel). Importantly, this input is received by the carriage itself, not the controller.

Therefore, the FSM that models a carriage has to respond to the same 'MoveTo' instructions, coming from different sources and for different purposes. Our  model should deal with this distinction.

Asynchronous instructions

These two instructions are disjoint and asynchronous. Two passengers can press buttons outside and inside the carriage at the same time, but the carriage can serve only one of them at a time. Furthermore - and this is important - one of the instructions can be given while the carriage is responding to the other. This means that a carriage can be in a Moving state while any/either of these two instructions can arrive. If and when will these arrive is unknown though. The temporal nature of their arrivals is the key. The FSM has to deal with this situation too.

In order to depict the FSM correctly, we do the following:

• We introduce a new state named ‘Moving’
• We introduce corresponding transitions between ‘Moving’ and ‘Stopped’ states.

This seems quite intuitive: when it is not moving, the carriage is stationary (‘Stopped’) and vice versa. It keeps moving until reaches a floor and then it stops. It moves again, when asked to go to another floor.

Modeling arrival of asynchronous events

We are designing a Finite State Machine (FSM) where inputs can arrive when the FSM is in the middle of a transition. One can draw a parallel with the asynchronous FSMs (here and here)  that are used in design of electronic circuits. We cannot stop the transition midway because we want the machine (carriage in this case) to be in a known state after every transition. Equally importantly, we cannot afford to lose the request which arrives while the transition continues, because its arrival confirms that the 'Event' of placing the request has already happened. Once the transition is complete, the FSM reacts to the first of events that have arrived.

Fortunately, Akka’s Actors are completely event-driven: every request to a carriage is treated as an event, is enqueued and is processed by the Actor at some point in time. Because our carriages are modeled as Akka Actors, it is guaranteed that the transition happens uninterrupted, while further inputs or events line up for their turns (I am not going into the details of Dispatchers and Mailboxes here, but I hope that the point is clear).

We are ignoring the time taken for opening the door, for the passenger to walk in/out and for closing the door. All this while, the carriage remains Stopped. A passenger can get in or out of the carriage only when it is in Stopped state. It moves again, if a passenger inside wants to go somewhere or a passenger somewhere else wants the carriage to go up/down to her.

The following table describes the events in a little more detail:

Event	Indicates
PassengerIsWaitingAt(floorID)	A passenger has pressed the up/down button at some floor
PassengerRequestsATransportTo(floorID)	A passenger has pressed a button on the panel inside the carriage
ReachedFloor(currentFloor)	The carriage has reached the floor where a passenger  has been waiting

Just to elaborate once more.

1. Both the events PassengerRequestedATransportTo(floorID) ,and PassengerIsWaitingAt(floorID), are temporally random. They can arrive at the carriage at any point in time, whether it is in Stopped or Moving state.   
2. It is important to understand that the carriage is eventually going to stop at some floor; that is its most common state. In fact, when a carriage is powered on, it is in a Ready state, which is its first Stopped state, if we consider.
3. In the real world, the button-panel inside the carriage is an electronic device, which generates a signal for the carriage. In order to cater - relatively easily - for the asynchronicity of the inputs it generates, it is modeled as an Actor in our case.
4. The carriage makes no distinction between the reason why it has come to a floor: to pick up a passenger or to drop one.  In our implementation we are distinguishing between these purposes, because we want to demonstrate that our carriage’s FSM is capable of doing so.
5. The carriage consumes time to come to a floor and the arrival is signaled by an associated electronic circuitry/device. This signal is the ReachedFloor(currentFloor) event above and it marks the completion of the transition from Moving state to Stopped state.

Here’s is a block diagram showing components that our model is using.

The code is here.

In the next post, I will explain the current design in a little more details.

Modeling software systems using FSMs is something that I enjoy very much. I try to experiment with approaches. So, I would love to hear your views about my approach. Point out gaps in my concept or mistakes in implementation, or both, if any.