{"id":9837,"date":"2015-04-14T22:11:47","date_gmt":"2015-04-14T12:11:47","guid":{"rendered":"http:\/\/legoeng.local\/?p=9837"},"modified":"2019-06-27T12:29:24","modified_gmt":"2019-06-27T02:29:24","slug":"from-sequential-programming-to-state-machines","status":"publish","type":"post","link":"http:\/\/legoeng.local\/from-sequential-programming-to-state-machines\/","title":{"rendered":"From Sequential Programming to State Machines"},"content":{"rendered":"

\"BOGATECH\"<\/a>In this unit, we will explore some common algorithms for line following in a very systematic way, starting with well known “sequential” approaches, and then contrasting these with a “state machine” approach.<\/p>\n

We will see in detail how a four-step simple line follower with two Light (or Color) sensors works and how to systematize the design of its algorithm. We will analyze the similarity and fundamental difference with the three-step simple line follower typically used with one Light (or Color) sensor.<\/p>\n

We will see how to make the robot take decisions sequentially at each line intersection, and how to design data flow diagrams to express graphically the working process of a program.<\/p>\n

Finally, we will see how to program a state machine for this line follower and the advantages it brings over sequential programming.<\/p>\n

This unit is based on my \u201cTeachers Introduction Course to LEGO\u00ae Mindstorms NXT & EV3<\/a>\u201d at BOGATECH<\/a>\u2019s website. Here the programming examples are based on the LEGO MINDSTORMS EV3 Software, but at BOGATECH\u2019s website you can find the NXT version and the differences between the two platforms, if you are interested.<\/p>\n

Exercise 1. A\u00a0four-step simple line follower<\/h2>\n

We can start by asking the students how they think we should conceptually proceed. How should we design the algorithm? Note that the two Light sensors are located on each side of the black line that we want to follow, as shown in the images below.<\/p>\n

Note: Although we will refer to Color sensors throughout this article, we are using them as Light sensors. Of course, the approach described in this article applies equally well to an NXT robot with a Light sensor.<\/p>\n

\"2
Color sensors’ location detail<\/figcaption><\/figure>\n
\"Robot<\/a>
Line following robot with two Color sensors<\/figcaption><\/figure>\n

We can help the students by making a small drawing on the board and asking them:<\/p>\n

    \n
  1. What should the robot do when the two sensors detect (or \u201csee\u201d) the white color? By making the drawing it becomes obvious that robot has to go forward.<\/li>\n
  2. And when the left sensor detects black and the right one white? It has to turn left.<\/li>\n
  3. When the right sensor detects black and the left one white? It has to turn right.<\/li>\n
  4. Finally, and before drawing the intersection, we can ask in what situation the two Color sensors of the robot will detect black. The answer is: in an intersection.<\/li>\n<\/ol>\n

    Tip<\/strong>: If the\u00a0path has very tight angles the robot might detect them as intersections. This might even happen in right angles, depending on the width of the line or the distance between both sensors. For the purpose of this exercise, create a gentle and smooth path. In further units we will address more advanced challenges like how to make the robot negotiate tight angles without losing the line…\u00a0<\/span><\/p>\n

    \"Graphic
    Graphic algorithm to follow a line with 2 color sensors<\/figcaption><\/figure>\n

    Another more systematic, but less graphic, way to find all the combinations of the two Color sensors\u2019 readings is to build a table of values.<\/p>\n\n\n\n\n\n\n\n\n
    Sensor values<\/strong><\/td>\n<\/td>\nSensor 1<\/strong><\/td>\nSensor 2<\/strong><\/td>\nRobot action<\/strong><\/td>\n<\/tr>\n
    B = Black<\/td>\n<\/td>\nB<\/td>\nB<\/td>\nIntersection, stop the robot?<\/td>\n<\/tr>\n
    W = White<\/td>\n<\/td>\nB<\/td>\nW<\/td>\nLeft turn<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\nW<\/td>\nB<\/td>\nRight turn<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\nW<\/td>\nW<\/td>\nGo forward<\/td>\n<\/tr>\n
    <\/td>\n<\/td>\n(Left, port 2)<\/td>\n(Right, port 3)<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    We can ask the students how many combinations we would have with three Color sensors. The answer is eight which is equivalent to 23<\/sup>. In general we would have XY<\/sup> combinations, where X is the number of possible readings \u2013 in our case 2, that is, true if the reading is below the threshold between white and black and false if it is above \u2013 and Y is equivalent to the number of sensors, in this example 3 sensors.<\/p>\n

    Next we can ask how to program this line follower? We can help the students by asking them how many different options we have. The answer is four, thus we will need a switch with four branches. How can we obtain these four branches? Well, we need to nest three switches.<\/p>\n

    At the same time that we ask them these questions, it is important to represent this graphically on the board to help the students visualize the algorithm. An important point they need to understand is that the first switch needs to be associated to the first Color sensor and the other two to the second one, to obtain the four possible cases, as shown in the image below.<\/p>\n

    \"Pseudo\u00a0At this point the programming is trivial, we only need to implement the previous pseudocode.<\/p>\n

    Let’s say that the right-hand motor is connected to Port B, the left one is connected to Port C, the left Color sensor is connected to Port 2 and that the right Color sensor is connected to port 3. You will also need to check the right value of the light threshold between the white color of the field background and the black color of the line to follow (e.g. 25% in the following example), and that the Color sensor is configured to read the reflected light. Finally, you will also need to adjust the motors\u2019 power to be less than 40% to obtain a smooth robot behavior when following the line.<\/p>\n

    Create a new program, as shown in the following image.<\/p>\n

    \"4<\/a>
    A simple “four step” line follower with two Color sensors<\/figcaption><\/figure>\n

    Note that with the motor blocks located one after the other \u2013to start or to stop them at the same time, or to stop one and start the other one\u2013, the program execution is so fast that it is like the two are run at the same time.<\/p>\n

    In the EV3 Software, the \u201cMove Tank\u201d block is a useful way to control the two motors at the same time with only one block. The image below shows how to simplify the previous program using this block.<\/p>\n

    \"4<\/a>
    4 step simple line follower with 2 color sensors using the block \u201cMove Tank\u201d<\/figcaption><\/figure>\n

    Tip<\/strong>: When using the \u201cMove Tank\u201d block you need to carefully configure the block\u2019s motor ports, from left to right, in the same way the motors are setup in the robot looking towards the front (\u201cLeft Motor Port + Right Motor Port\u201d). In our example, we need to configure the motors as \u201cC + B\u201d (and not \u201cB + C\u201d) because port C corresponds to the motor on the left and port B to the one on the right. We can also see that to brake a motor you just need to configure its power to 0.<\/p>\n

    Finally, if the robot executes the program, what will be the robot\u2019s behavior? The answer is that the robot will follow the line until the first intersection and once there it will stop and it will never get out of the loop. That is, the program will execute indefinitely (until the batteries will run out or until we will stop it). To demonstrate this, we can raise the robot and place it a little bit further away from the intersection, just after it, and we will see how the robot will start again following the line until the next intersection, etc.<\/p>\n

    Next, we can compare the four step approach with the following three-step line follower that uses only one Color sensor, and ask the students what is the fundamental difference?<\/p>\n

    \"3<\/a>
    3 step simple line follower with one color sensor<\/figcaption><\/figure>\n

    As we can see, the three-step simple line follower with one Color sensor is an optimization of the two step simple line follower. To make it work properly, you need to make several tests to adjust the two thresholds with enough distant values (for the same Color sensor in EV3) to make the robot go forward in the straight segments and not to lose the line in the curves.<\/p>\n

    Observe that the behavior of these algorithms to follow the line with one or two Color sensors is almost identical (maybe it is a little bit more precise with two Color sensors) because both algorithms execute one of three options. In the case of the line follower with one Color sensor, the robot turns to one side or the other and goes forward whenever the reflected light detected by the Color sensor is close to the threshold between white and black (i.e. when the sensor \u201csees gray\u201d). In the case of the robot with two Color sensors, the robot goes forward when the two Color sensors detect white (i.e. when the black line is between the two Color sensors).<\/p>\n

    Thus, the fundamental difference is that the robot with two Color sensors is able to detect line intersections<\/strong>!<\/p>\n

    Coming back to the two sensor line follower, we can now ask what we need to do when the robot detects an intersection. With the current students\u2019 knowledge the correct answer is to get out of the loop<\/strong>!, so as to decide what to do at each intersection, that is, to go forward, to stop or to turn to one side or the other of the intersection. Some students might see that another solution will be to count intersections, but we will address this later\u2026<\/p>\n

    Then the question is: how can we get out of the loop? In general, when we use a loop the problem is always how to get out of it\u2026 One answer is to use a variable<\/em><\/strong>. For this, we need to convert the loop into a logic loop and use a logic variable to control the exit from the loop when finding a line intersection.<\/p>\n

    \"4<\/a>
    A simple “four step” line follower with 2 Color sensors and loop exit control when detecting a line intersection<\/figcaption><\/figure>\n

    In this example, notice that the logic variable initializes to false, that is, it is written to a false value before entering the loop, and it is only written to \u201cTrue\u201d when the Color sensors detect the black color to make the robot exit the loop. We can also see that the motors are stopped just after exiting the loop. We could have done this inside the switch, but as we will see later on, doing this outside the loop gives more flexibility.<\/p>\n

    Observe that initializing the variable before entering the loop saves having to insert the variable three more times in each one of the other three switches\u2019 branches, but with a false value. In addition, it makes it easier to read and understand the program.<\/p>\n

    A little bit of theory<\/h2>\n

    Some programming languages explicitly require initializing variables, but this is not the case with the EV3 Software. By default, a logic variable is initialized to false, a numeric variable to the 0, and a text variable to the empty string, \u201c\u201d.<\/p>\n

    Finally, the EV3 Software has a \u201cLoop Interrupt\u201d block that provides a way of getting out of a loop, without having to use a variable, as the following image shows. Observe that the \u201cLoop Interrupt\u201d block needs to have the same name as the loop you want to interrupt. By default, loops are numbered when you add them to the program and their number can be changed. In our example, the loop is named \u201c01\u201d.<\/p>\n

    \"4<\/a>
    4 step simple line follower with 2 color sensors with loop exit control using a \u201cLoop Interrupt\u201d block<\/figcaption><\/figure>\n

    Tip<\/strong>: It is a very good practice to always initialize the variables used, so as to make explicit their values and to make the code much more understandable. If you use a \u201cLoop Interrupt\u201d block, make sure that its name is the same as the loop you want to interrupt. In the case of long and complex programs it is very advisable to use descriptive names for loops, to better understand the code when you use the \u201cLoop Interrupt\u201d block.<\/p>\n

    You can now build a small circuit with intersections and you can ask the students to program the robot to go forward at the first intersection, to turn left at the second, to turn right at the third and to stop at the fourth one. Perhaps the most obvious approach is that you only need to copy the previous code and program what the robot needs to do at each intersection, just after each loop exit.<\/p>\n

    \"Circuit<\/a>
    Circuit with intersections program<\/figcaption><\/figure>\n

    After the first intersection the previous programs use a Move Tank block to make the robot go forward 70 degrees, just enough to pass the line. At the second intersection the robot makes a point turn, in this case over wheel C, to turn left. We can see that, with a stopped wheel, if the other motor turns an equivalent to one rotation, given my robot\u2019s geometry (yours might be different), this makes exactly one quarter turn, just what we need to continue following the line. At the third intersection, the robot turns over the other wheel to turn right, and at the fourth intersection the robot stops. At this point we see the usefulness of not putting the motor blocks to brake them and stop the robot inside the switch branch corresponding to the line intersection detection, this saves some code and allows concatenating the robot movements in a softer way without motor brakes.<\/p>\n

    But even if this solution works perfectly well, what is its disadvantage? The problem is that the program is too long. The line follower code is duplicated four times, or as many times as intersections to negotiate. This implies that if we need to make any changes to the line follower, we will need to repeat it four times. In addition, the program needs to compile the same code four times, making the program less efficient and using a lot of unnecessary space in the robot\u2019s memory.<\/p>\n

    The following step is to create a subprogram or user block \u201cLineFollower2s\u201d for the code corresponding to the line follower that is duplicated four times in the two previous examples.<\/p>\n

    \"Circuit<\/a>
    Circuit with intersections program with user blocks<\/figcaption><\/figure>\n

    Now the program is much more efficient and easy to understand, and the code corresponding to the line follower is only compiled or translated to the robot\u2019s language once. In addition, if we need to make a change in the subprogram or user block, we only need to do it in the original program and when saving the change, this will propagate to all the instances or its insertions inside the main program.<\/p>\n

    Finally, we can design a longer circuit to test the robot in taking decisions at each line intersection in a sequential way, following the flow or sequence of the robot path.<\/p>\n

    Acquired knowledge<\/h3>\n

    The students have learnt designing algorithms in a graphic way, with pseudocode and in a systematic manner by using tables of values for each sensor. They have also compared the algorithms of the line followers with one and two Color sensors, and they have seen a sequential strategy to program the line follower robot with two Color sensors to make decisions at each line intersection. In addition, the students have seen the usefulness and efficiency of subprograms or user blocks to make the code more compact and more understandable and efficient, and they have learnt to use variables to pass information between different blocks or program parts, especially to get out of a loop by using a \u201cLoop Interrupt\u201d block.<\/p>\n

    Challenge 1. Get to the end of the cage!<\/h2>\n
    \"Challenge
    Challenge exercise diagram<\/figcaption><\/figure>\n

    This image shows the circuit of the challenge exercise to reach the end of the cage, where the arrows show the robot\u2019s actions. The straight forward movements where the robot will have to follow the line are shown in black and the actions the robot will have to make in reaching the intersections are shown in red.<\/p>\n

    Before starting, if pay attention to the exercise, we will see that we need six instances of the line-follower user block and between each instance we need to turn left, go over the middle line of the field, turn right, turn right again, go over the middle line again, and stop.<\/p>\n

    Tip<\/strong>:\u00a0To make the robot easily detect intersections and even right angles, these need to have a cross shape (\u201c+\u201d) as shown in the above image. This might not be necessary, it will depend on the robot\u2019s geometry (distance of the sensors to the wheels turn axis and distance between wheels) and the speed of the motors when following the line.<\/p>\n

    A little bit of theory: State machines<\/h2>\n

    The previous programming style is perfectly correct, the blocks and decisions are programed in a sequential way following a specific order, for example, following the order in which the robot encounters the intersections, following a specific reading order of the different robot\u2019s sensors, and finally taking actions in a specific sequence of decisions. In the EV3 Sofware the sequence beam establishes the program blocks execution order. Sequential programming<\/em> is one of the most common and often more obvious programming styles, because if the program is not very complex, you can write it without any planning, but it is not always the most efficient, most flexible or most understandable style in the long run.<\/p>\n

    For example:<\/p>\n