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

Injecting behavior into the system

Introduction

In the last issue of the magazine, we introduced the idea/method of injection system behavior of the finite automat system and defined three basic components which consist of: generic finite automat, state definition and transition matrix. In this issue, we continue with the topic, whereby we will be introduced to different aspects of application, principles, code portability and practical problems in implementation.

Principles and concepts

Programmable autonomous vehicles (in the text below PAV) are one section of of application, but the method can be used for different purposes. Let's return first to the high level of PAV architecture, the reason for this will be clear soon. PAV is made up of: control units (in our case 8051 microcontroller, although generally this can be any digital computer), power amplifier (device driver), actuator (DC motors in our case) and set of sensors that make feedback back to control unit (InfoElektronika No. 110 - PAV infrastructure).

Intel 8051 Development board by MikroElektronika

Question: Have you ever thought about the printer and the way it works, about its internal electronics? The printer is basically a robot and belongs to the motor control domain. In general, printers have several different types of motors. One is in charge of positioning the head of the printer with bidirectional motion, which means that it has a H-Bridge circuit or, for example, a ULN 2xxx serie of IC that control the motor with signal sequence by moving the head of the printer. The second set of motors is used for positioning the paper, using different sensor sets to identify the position, paper availability, etc. As you can see, the similarities are great. For example, the Rohm 574 sensor that was written in InfoElektronika magazine No. 111 was used from an old printer. In the case of a printer, the finite automat (hereinafter referred to as FA) can be used to implement a low level of management software. Now let's look at a few more examples. Let's omit the concrete implementation of the PAV and deal with functional aspects. We already know that PAV have the ability to move forward, backward (with speed control), brake or stop, etc. Does this look like to you that PAV and VCR are basically similar? ... Of course, because the VCR also has a H-Bridge circuit which is precisely used for the aforementioned rewinding of the tape with the possibility of speed regulation, BA6222 IC. Simply put, the VCR device partly belongs to the motor control domain because it owns the motor, but also the electronics for processing the image of the video, which is not interesting to us in this case.Let's take another example. We were all in mega-markets and almost everyone at the entrance/exit have automatic doors. Things are simple, we approach doors, a passive infrared sensor detects our movement, triggers an event that the microcontroller detects with an interrupt unit, starts the H-Bridge, the doors open and then closes after a predetermined time. All of the above mentioned is exactly identical to PAV in terms of electronics. Now let's ask a new question: are the printers, VCRs and automated door robots? It's a matter of definition and nothing more. The printer, VCR, automatic door and PAV are conceptually identical devices in terms of the similarity of motor electronics control. What is clear is that these devices can be modeled by FA, including the motor. Does it make sense to model electronics for video recorder FA, we will come to the answer through the next text.

Portability

At the moment when we begin the practical realization of a device, it is good practice to implement it so that components can be reused. Two key reasons for this are: time and testing. If the device works steadily, it means that it has been well tested and that we have spent the time, so it should be reused. We apply the same thing to FA. How to write FA so we can use it on several different platforms:Intel 8051, PIC, ARM, x86 etc.?It's clear to everyone that it is difficult to write a 100% portable program code, but there are methods that make portability a simpler task. The answer to this question lies in standards and compilers. You can also view the text from InfoElektronika No. 110 - Platform portability for 32bit microcontrollers. Compiler manufacturers sign their products basically with three things, and follow several examples. C compiler of X is: ANSI C compiler, with extensions for Intel 8051 microarchitecture, Intel 8051 standard platform. C compiler of Y's manufacturer: ANSI C compiler, with PIC microarchitecture extensions, PIC Microchip platform. C compiler of the Z manufacturer is: ANSI C compiler, with extensions for x86 microarchitecture, Intel x86 platform. What we can see from the examples listed are the standards. All these compilers are ANSI C standard. And now we come to the essence. To portability we come in the way that the program code is written with ANCI C standard and in no way different. This is true, but the processed data at a certain time should be set to the output ports of the microcontroller. Microcontroller peripherals are what we call extensions, and such things are not portable, as each platform carries some specificity with itself. The rule is simple: we write/solve the essence of the problem with the ANSI C standard in such a way that it is completely isolated as a whole. This is achieved by creating separate files (.c and .h) and defining the interfaces through which we perform those parts of the non-portable program code. An additional item, ANSI C compilers carry libraries with them because they are part of the standard. However, libraries are not portable because they are written according to the specifics of microarchitecture/set of instructions. The moment you need to use a method from a particular library, it must be separated into a separate file to make the program code more portable.

Consequently, the development of the program code is not directly related to the development environment of the embedded system. For example, I tested the FA code written ANSI C standard in the development environment of Microelectronics with a Microsoft Visual C ++ compiler because it is the same ANSI C compiler for the x86 platform.

Defining the state

Every state of the system must be implemented in such a way that the generic FA "knows" to execute it. In practice, such things are realized by defining the interface.The interface is a set of methods and properties that the state implements because it is also used for the implementation of a generic FA. Defining the interface is the first step in realization. As the purpose of this text is not to explain each method of the interface (because there is no space for it), we will deal with one essential method. The interface defines the default method called DefaultMethod. As the generic FA uses an interface, each state of the system must implement the default method. Let's take for example the state of moving forward PAV. This state is implemented by the DefaultMethod method. The responsibility of the method is to manage the H-Bridge according to the rules of moving forward. From the moment it is done the method is completed, where the PAV is still in the moving forward state, and therefore FA also. Now let's take an example of the state of moving backward. From the moment it is done the method is completed, where the PAV is still in the moving backward state, and therefore FA also. The same thing is with braking, or stopping the vehicle. Here's the whole picture. PAV is in idle state, therefore generic FA is in idle state. If an event occurs, the FA from the idle state goes to the moving forward state, it automatically means that it starts running the DefaultMethod state to which it has passed. What DefaultMethod really does is not the FA's responsibility, its only responsibility is to start its execution - in this case the H-Bridge is setted according to rules of moving forward.

How FA calculates the next state of the system is the responsibility of the transitional matrix.

 

Figure #1. State machine - Transition Matrix

Transitional matrix

In the previous issues of the magazine, FA is represented exclusively in one way, graphically. We used circles to present the state and arrows to present the transition. There is another way of defining FA and we deliberately kept it for this text, so that things become clear. It is about a tabular/matrix definition of FA which makes a transitional matrix (hereinafter referred to as TM). Columns of the table/matrix are states, while the rows of the table/matrix are events that affect the transition. Figure 1. shows mapping between two different ways of defining FA. FA from picture 1.a. is mapped to the table/matrix from picture 1.b. FA from picture 1.c. is mapped to the table/matrix of picture 1.d. As you can see, the table/matrix display carries with itself all the information of FA's behavior and not only that, they are completely different in the transitions for identical set of states and events, pictures 1.b and 1.d - which gave us the basis for developing the method of injecting behavior into the FA system! There are three types of transition between states: direct, conditional, and external. Direct transition cites generic FA to after executing the default method - DefaultMethod, automatically switch to the next state of the FA system. The conditional transition cites generic FA to, after executing default method, check the previously executed state, and if the condition is fulfilled, it automatically switches to the next state. External transition belongs to the domain of external events. Each of these transitions is suitable for solving various problems. For example, direct transitions are suitable for generating PWM and control signals. On the other hand, external transitions allow us to operate the system depending on the events gathered by the sensors.

Now let's ask a series of questions. What type of transition has the highest priority? Is it a direct, conditional or external transition? There are no answers because it depends on the problems we are addressing, but what we can do is to configure the transition priorities. It is logical that external transitions have a higher priority than others in the case of PAV, because vehicles change their position in space and need to provide quick response to external factors. But this case can not be transferred to other cases, and the ability to configure the priority of transition is an adequate solution to the problem. There are several ways for practical implementation of TM. In this case, a number of bytes (stream) was used, which allows it to be easily injected into the FA system or RAM memory of the microcontroller. We determine the dimension of the series or the number of bytes by multiplying the number of columns and rows. However, from the enclosed program code (link to the InfoElektronika website) you can see that TM is not the only one that injects into the system. In addition to TM we also inject information about the initial state of the FA system. Accordingly, a number of bytes has been expanded by one. TM can be a problem because it requires a lot of memory. The more states and events we define, the more memory you need to store it. Consequently, there are certain optimization methods based on mod arithmetic that allow one byte to be used to define more states / events. You can also find the method of calculation in the enclosed program code.

Figure 2. Stepper motor modeled with the finite automat.

Encoding of states and types of transition

As we already mentioned in the TM case, the lack of memory problem can become large, especially in the case of small memory models, whereby TM can occupy up to 80% of memory leaving little space for other things - keeping the code state/type of transition. This problem is solved in such a way that the state/event is actually the position/index TM. In this way, additional storage space for saving the code state/event is not required. To encode external transitions or events, we use the priority encoder (hereinafter referred to as PE) - CD4532 IC. At the input of the PE, we push the keys to simulate pressing on the same different external events. In concrete implementations, we input signals from different types of sensors to the PE input - for the needs of testing and prototype development, the keys are good enough. I decided for PE because it gives opportunity to prioritize external events. Some external events need to be reacted before others, and PE is an adequate choice.

Stepper motor modeled with the finite automat

Before embarking on the modeling of the FA stepper motor, it is necessary to look at the functional aspects. We will be guided by simple examples to make the injection method easy to understand. We have already written about unipolar stepper motors, InfoElektronika No. 110, but let's repeat the basics. Stepper motors are recognizable by a bigger number of excerpts where one of them is common (example: link it to +12V) and multiple control excerpts that serve for controlled rotation in one of two possible directions. Rotation takes place in steps, with the minimum degree of rotation declared by the manufacturer. By generating a signal sequence in time, we generate a sequence of discrete steps that make the rotation of the motor. By inputting the time delay between the generated signals, we input a time delay between the steps, which regulates the speed of the rotation of the motor. Analyzing the functional aspects of the stepper motor follows a series of conclusions in order to define the state of the FA. Conclusion: As the rotation progresses stepwise in two possible directions, two rotational states are required: a step in the clockwise direction (Step CW) and a reverse clockwise step (Step CCW).Conclusion: the time delay between the steps introduces an additional state - timer. The last state is the idle state - in this state FA is waiting for an external event. The last situation is simply imposed by itself, because at the moment when it is initialized, FA is waiting for external events - for example: coffee machines, because they are the same as FA. As we see, I have a total of four states on the basis of which we can describe the behavior of the stepper motor in different ways:

1. Step CW - one step of the clockwise rotation.

2. Step CCW - one step of rotation in reverse clockwise direction.

3. Timer - a time interval between the steps

4. Idle - state of waiting for external events, initial state

After defining the state, the step of defining the different tasks/behaviors of the stepper motor is followed. Figure 2.a shows the starting point. As you can see, only the states are shown, there are no transitions. First Behavior: Switch to an external event from the standby state to the state of continuous rotation clockwise, Figure 2.b. Second behavior: the same as first, with the additional possibility of regulating the speed to the specified external events, Figure 2.c. Third behavior: the same as the second with the additional possibility of regulating the direction of rotation to the specified external events, Figure 2.d. As we see from Figure 2.b, the first behavior defines a transition between the three states of FA: Step CW, Timer, and Idle. This is exactly what we wrote in InfoElektronika No. 112 - all of the above states, altogether four, constitute the set S - set of all possible states of the system, but only three are necessary for the realization of the first behavior (the task set St). Other behavior also eliminates Step CCW, Figure 2.c, whereby it is introduced only in the third behavior, because we also require rotation in the opposite direction, Figure 2.d. Note that first behavior uses one external transition and then follows a series of infinite direct transitions between the two states of Step CW and Timer, making the FA automaton with infinitely many transitions between states - InfoElektronika No. 112. Second and third behaviors enter additional external transitions to regulate speed and change direction of rotation respectively. After defining the transitions between states, the next step is mapping the state diagram in the TM by the rule shown in Figure 1. The next step is the implementation of the states where each implements an interface that defines the default method - DefaultMethod. From the enclosed program code, please note that there is a lot of similarities between the Step CW and Step CCW, with the shift bit direction difference by shift bitwise ANSI C programming language operator. The last step is to pack TM into separate files with a bin extension. In this case, there are a total of three bin files. The first bin file contains TM of the first behavior, the second contains TM of second behavior and third contains TM of third behavior. Files with bin extension are injected into the FA system, or in RAM memory of the microcontroller via RS232 communication - the way of injection is your choice.

Conclusion

Each method carries with it the advantages and disadvantages, and accordingly the method of injecting behavior into the FA system. There is always a famous saying: "What you get on the bridge will be lost on the brim". By injection, we eliminate reprogramming, which reduces the time of modification of the behavior of the system. On the other hand, unnecessary conditions unnecessarily occupy memory and we lose valuable resources. At the beginning of the text there are several examples of systems that can be modeled by KA. However, does it make sense to use the generic FA for the automatic doors of mega-markets? In my opinion, no, because it is a system that suffers a little changes after it is made. On the other hand, the method is suitable for PAV. Why? The moment you practically realize PAV you will surely have the desire to do as many different things as possible with it. In that case, the injection method seems to be a great choice because it allows a rapid change in the behavior of the robot. The only thing left to do is describe what are you expecting from the PAV to do. The complete program code of the generic finite automat can be downloaded from the InfoElektronika magazine website. The enclosed program code includes testing the generic FA in the development environment MS Visual C ++ for the x86 platform. Note: the names of the states are not 1: 1 with the names of the states in the enclosed program code. How does this look in practice look at the attached YouTube video links.

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

Publication: InfoElektronika magazine number 115

YouTube links:
http://www.youtube.com/watch?v=4ZGx8zq_t6k&feature=player_embedded
http://www.youtube.com/watch?v=Ei9KdeeKOBI&feature=player_embedded
http://www.youtube.com/watch?v=UL981FDDahA&feature=player_embedded