A finite state automat - Injecting behavior into the system, Part I

Injecting behavior into the system

Introduction

A finite state automat as a general model for describing the behavior of the system has wide application. One of the fields of application is shown in the last issue of the magazine (# 112) and refers to the description of the behavior of a programmable autonomous vehicle. However, the presented software solutions have certain drawbacks - each new task entails reprogramming. Injection System Behavior is the method/idea to describe the behavior of the system at an abstract level using the generic structure of the finite automat, eliminating reprogramming. 

Injecting behavior into the system

In the previous two issue of the magazines (InfoElektronika # 111 and # 112) are displayed two different tasks, two different software solutions, executed by a programmable autonomous vehicle (hereinafter referred to as PAV): avoiding the obstacle and defined movement of the black path. Both tasks are modeled by a automat with a finite state number (hereinafter FA). However, what is the problem of software solutions for both defined tasks? The problem is reprogramming. Each new defined task entails reprogramming - write a program from the beginning. This is followed by a simple set of logical questions. Why to reprogram? How to circumvent the reprogramming? Is there a simpler way? Yes, reprogramming is circumvented by the injection of behavior into the FA system.

Figure 1. Finite state machine #1.

What is it really about?

The basic building elements of FA are: states, transition functions and initiatives. The transition functions based on the current state and initiative define the next state of the system. In Figure 1., FA is presented with four states (circles) and transition functions (arrows) with the tag of the initiative describing the behavior of the system. The initial state of the system is A. If the Cmd1 initiative is brought to the FA input, the system namely FA goes to the state C. At the moment when Cmd4 initiate is brought at the input of FA, FA switches to state D, etc. As we see, the transition functions define the behavior of the system. Let us now look at the example of FA from Figure 2.

The initial state of the system is C. If the Cmd1 initiative is brought to the input of the FA, the system goes into state A. If the Cmd2 initiative is brought to the input of the FA, the system goes into state B, etc.

What can we notice from the previous two examples of FA? We see that both FA have identical states and initiatives and the only difference is in the transition functions. Different linking of the states (circles) by transition functions (arrows), we get different behaviors for the same system, which follows the basis of the idea of ​​injection system behavior. As we can see, states and initiatives are constant (unchangeable) building components of FA, while transition functions make a variable component, one that is injected into the system. It is sufficient to define states and initiatives only once, the moment when the system begins to model FA. The transition functions must be defined (by matrix transition) for each task separately and then injecting them into the FA system, Figure 3.

Figure 2. Finite state machine #2.

Application to PAV (Programmable Autonomous Vehicle)

Let's apply the method now to PAV. PAV states are: moving forward, backward, wheel rotation to the left, right, inaction, braking, etc. All the above states constitute the finite set of all possible states of system S and is defined only once. What are the PAV initiatives? Initiatives are sensors: Infrared, passive infrared, mechanical, temperature sensors, ultrasonic sensors, etc. All of the above system initiatives constitute the finite set of all possible initiatives of system P and is defined only once (InfoElektronika # 112). The S and P sets form an alterable (existent) component of the FA. The alterable component of the system consists of the transition functions. The task "Avoiding an obstacle" through the transition functions defines certain connections between the state of moving forward, backward, wheel rotation etc. But these connections are not constant, they can be changed, which also changes the way the system behaves.The "movement defined by the black path" task describes completely different transition functions between the states of the PAV.

Generic finite automat - Injection infrastructure

Realizing such a method/idea requires the implementation of the generic FA infrastructure. The generic structure of FA must satisfy the following:

1. the ability to define and store all possible system states

2. the ability to define and store all possible system initiatives

3. the ability to easily add and remove state and system initiatives

4. the ability to inject transition functions and

5. generic algorithm for transition between states

Figure 3. Model of the generic finite automat

With the generic FA structure, we eliminated the need for reprogramming, the only thing we need to do is to "describe" what we require from system to do, and then we inject into the generic FA.

Also, the method of injecting behavior into the system can be used for the program implementation of a microprocessor microsequencer (example nothing else).

Author: Vladimir Savić
Translator: Nera Marković
nera.markovic(at)zilsel-invent.com

Publication: InfoElektronika magazine number 115