Programmable autonomous vehicles – Fundamentals, Part III

June 19, 2018

Automat with a finite number of states

Introduction

After all practically implemented electronic components, the last step leads us to implementation of "intelligence" - control software - which is realized by automat with a finite number of states. Robotic intelligence is exactly that, an automat, a machine which, when initiated, goes from state to state to complete the task.

Figure 1. (a) FA with infinite transitions between states. (b) FA with finite transitions between states, State C is the output.

Automat with finite number of states (in the text below FA) is a mathematical model for defining a system behavior. It is defined by a trio FA (S, I, T) where: S - is the finite set of all possible system states, I - the finite set of all possible system initiatives, T - the set of all possible system tasks. Each task of a system is defined by regulated quadruple T = (St, St0, It, ft) where St - is a set of states necessary for the realization of a task, where each state belongs to the set S; St0 - the initial state also belongs to the set S; It - a set of task initiatives where each initiative belongs to the finite set I; and ft - task transition function. The principle of operation is simple, FA for the given task T, based on task transition function ft, depending on the current state and the input initiative, decides on the new state of the system. As such, FA can be used for realization of control software or "intelligence" of a programmable autonomous vehicle (in the text below PAV - the mobile robot). Inaction, moving forward, moving backward, wheel rotation, and all possible PAV states make a set of S. Mechanical sensors, infrared sensors (in the text below IC), DC motor sensors etc. (InfoElectronika No. 111 - practical realization of sensors) make the finite set of initiatives I. Example: The PAV is in the forward state, the IC sensor (the initiative) detects the object in front, the transition function ft based on the current state and the type of initiative determines a new state, lets say, stop the vehicle. As already mentioned in the first part of the PAV (InfoElectronika No. 110) the tasks are the starting point. Based on the same, we use the above showed mathematical model to describe the behavior of the system and practical realization of the control software. Regarding the number of transitions between the states, we distinguish two types of FA: with a finite number of transitions between states and infinite number of transitions between states.

Figure 2. FA with finite number of states. Describes the movement of a programmable autonomous vehicle that follows a black strip on a white background. End/Stop is the final state, and therefore FA is with a lot of finite transitions between states.

The finite automat with infinitely many transitions between states

In Figure 1.a is shown the FA system with an infinite number of transitions. States are shown by a circle, while transitions between states are shown by the arrow. States A and B constitute the finite set of possible states of the system S. I1 and I2 constitute the finite set of possible initiatives of the system I. The initial state of the system S0 is state A. In case of initiative I1, FA goes to state B. In case of initiative I2, FA goes to state A. As in both cases we have a transition to some of the system state, we consider the automat to be infinite. Since the system consists of two possible states: A and B, the only possible infinite sequence of transitions between the states is: A, B, A, B, A, B, A, B, A, B...