ELEN90066 Embedded Systems Design

Project Report

1    Introduction

The purpose of this report is to detail the design process and methods used in completing the Kobuki Obstacle Course Project.  The report documents the design of a Finite State Machine (FSM) and its implementation on a Kobuki robot so that it can navigate an unknown obstacle course. Furthermore, the process used to test the system and the adaptions made leading into the final demonstration will be explained.  Finally, the report will detail the outcome of this demonstration and a discussion of shortcomings and analysis of how the system could be improved.

1.1    Background

Designing behaviour that allows a vehicle to traverse a complicated environment is an increasingly relevant problem. Finite State Machines provide a reliable method of achieving this, creating a way of representing the complicated behaviour in a readable format that the designer can follow.  This representation of an output of the system in distinct ”states” also permits a more robust analysis and validation of the system, such as demonstrating that given a particular input, the system will always enter the desired state. This feature becomes critical for safety when working with systems that impact the physical world.

The process and elements of the design outlined in this report could be applied to many real-world systems today.  For example, the online retailer Amazon uses similarly-sized autonomous vehicles to transport racks of goods around its warehouses and fulfillment centres  (E. Ackerman  2019). These vehicles would require similar (though far more complex) obstacle avoidance abilities as those developed in the Kobuki project. It is feasible to imagine an extension to the project that involves picking up an item at one end of the obstacle course and delivering it to the other. Moreover, full- size autonomous passenger vehicles use a similar process to operate on public roads today.  Their objective is much the same as in the Kobuki Project:  drive from point A to point B while avoiding obstacles in its path.  The primary diferences lie in the complexity of the system, requiring the use of many more sensors and actuators, and the incredibly tight performance tolerances needed in such a high-risk environment.

The Kobuki provided a platform for implementation and testing of our finite state machine.  It is a relatively low-cost piece of equipment, ideally suited for education and experimentation.  The hardware contains various sensors (discussed later), and was interfaced to the MyRio for processing.

1.2    Requirements

The design requirements, provided in the project brief, gave an outline of the behaviour required of the Kobuki, though the exact algorithm and its implementation were left to be designed.  The requirements for the Kobuki’s behaviour were:

• The robot should not move until the ’Play’ button is pressed

• The robot should maintain its initial orientation and drive forward in the absence of obstacles or a hill.

• The robot should avoid obstacles, not fall of clifs or edges, and should maintain both wheels on the ground.

•  Avoidance must always be satisfied, even if multiple obstacles are encountered at once or in rapid succession.

• After avoiding an obstacle the robot should return to initial orientation.

• The robot should detect an incline and orient itself to drive straight uphill.

• The robot should continue driving straight when the top of the incline is reached.

• The robot should detect a downhill slope and orient itself to drive straight downhill.

• The robot should detect level ground and stop within 40cm of the end of the descent.

• The robot should not rotate more than 180。.

• The robot should not exhibit 'hugging' or eratic behaviour.

• The robot should not terrminate operation unexpectedly.

• The course should be completed within the time limit.

A sample course layout was also provided (Figure 1) in the project guide, although the exact course specifications were not given in advance.  This obviously meant that a good level of robustness/ generality was required to ensure that our robot could complete any given course.  Not knowing the exact course specifications also made a more thorough testing procedure essential in order to catch behavioural quirks and problems in edge cases.

Figure 1: Sample course layout

Knowing a more about how the course would be structed, some assumptions were made in the creation of the state machine algorithm.   As the  Kobuki was not required to avoid/detect any obstacles during hill climb and descent, the obstacle avoidance would only need to occur in the first section of the course.  Similarly, there were no holes or drops in the obstacle avoidance section of the course, so wheel drop sensors were not necessary.  With this understanding, we proceeded to design our Finite State Machine and incrementally adjusted it until it performed as required.

2    Finite State Machine

From the understanding of the Kobuki’s behavioural requirements and the course structure, the design for our statechart was a hierarchical extended state machine, implemented using the Lab- VIEW statechart.  This seemed to be the most logical approach, allowing the broader segments of the course to be compartmentalised, allowing for easier design and testing. LabVIEW provided advantages in the many aspects of the design, implementation, testing and validation. The graphi- cal nature of the LabVIEW statechart made it easier to implement the algorithm structure for the design and state refinements were simple to add. Furthermore, LabVIEW was much better suited during implementation, as it could communicate with the myRIO, which controls the behaviour of the Kobuki, through a wifi network to provide feedback on the state it was in and the values of the sensors.

While the Kobuki calculates the distance it has driven and the angle it has turned by comparing the encoder values on each drive wheel, this is difficult to represent in the FSMs. In the following diagrams, states that depend on a distance driven or angle turned will use a variable, dist  (mm) or angle (degrees), to store that current value with a default transition that increments the variable. This represents the behaviour of the Kobuki, though physical complications, such as the ramp angle or a high-friction surface, would change the rate that this increment actually occurs. Also note that while reading the FSMs, some of the transition actions had to be placed below the transition guard to condense the diagram so it could be read on an A4 page. Similarly, the true / guard was omitted from the default transitions to save room.

2.1    Hierarchical FSM Diagram

The implementation of the state machine was done using the conventions described in An Introduc- tory Lab in Embedded and Cyber-Physical Systems v.1.70.. The top level FSM, shown in Figure 2, was a relatively simple extension on the skeleton statechart provided in the workshop documents. Adding a RESET state made testing the system much faster, as it would not require redeployment to test the same behaviour in a diferent scenario. Initially, we had hoped not to need to use the clif sensors, as the Kobuki would orient itself to point up the hill once it detected that it was no longer on flat ground. However, the performance became much more robust with the addition of the clif sensors as a fail-safe, in case the Kobuki did not detect the hill in time, or started to drift from its alignment. Due to the critical nature of its operation, the transition into the DETECT CLIFF state preempts the behaviour in the refinement of RUN, preventing the Kobuki from performing an action or transition that might cause it to drive of the clif.

Figure 2: Top Level FSM

The behaviour in the refinement of the DETECT CLIFF state, displayed in Figure 3, was relatively simple.  When the sensors detected a clif, the Kobuki stopped and, depending on which sensor detected the clif, the opposite wheel reversed to turn away from the clif.  When the 20。turn was complete, it would signal that the process was complete, so that it could transition back to RUN in the top level FSM. In this implementation, the centre clif sensor is not used.  This is because the centre clif sensor does not provide information about the best way to turn to avoid the detected clif, as well as issues with it falsely detecting a clif when the Kobuki reaches the top of the ramp. Due to the location of the side clif sensors, one of them would always trigger before the Kobuki could drive of an edge, making the performance still robust without the centre sensor.

Figure 3: FSM CLIFF DETECT

The RUN state refinement, shown in Figure 4, handled almost all of the movement behaviour of the Kobuki. The Kobuki begins moving by entering the DRIVE state, where it simply moves directly forward until it detects an obstacle from a bump sensor or detects the ramp based on accelerometer values.  An APPROACH state was also added between DRIVE and HILL  CLIMB  where, after detecting a hill, the Kobuki would drive forward its width of 30cm before transitioning. This also served to safeguard the behaviour from falsely detecting a hill due to noisy accelerometer values and being unable to transition back. In its current implementation, the R UN state does not allow the Kobuki to return to drive after transitioning to  HILL  CLIMB.  This was decided based on assumptions about the course, knowing that the hill is the last obstacle.  However, this does have an impact on the robustness of the behaviour and its applicability to a more generalised task, where this assumption might not be accurate.

Figure 4: FSM RUN

When the right or centre bump sensors were triggered while in the DRIVE state, the refinement would transition to LEFT AVOID, meaning that it would turn left to avoid the obstacle that was either on the right or directly in front. The FSM for the refinement of LEFT AVOID is shown in Figure 5, with the behaviour of RIGHT AVOID turning the opposite directions, but otherwise being identical. The obstacle avoidance behaviour is a little complicated, but can be better understood by following the arrows of the same colour through the diagram.  Ideally, upon detecting an obstacle, the Kobuki would reverse, turn left, drive 30cm and turn right to face forward again, having avoided the obstacle.  If during this drive it encounters another obstacle, it transitions to the green path, where it reverses, turns 180。, drives 50cm and turns to face forward again.  If in this process, it again hits an object, the blue path will be taken and it will stop driving to immediately turn and face forward again.

Figure 5: FSM AVOID

Figure 6: FSM HILL CLIMB

Finally, the last state refinement of RUN  is the HILL  CLIMB  state, in Figure 6, showing the behaviour of the Kobuki on a hill and how it reaches the final STOP  state.  HILL  CLIMB  is centred around the orientation procedure, which is the intial state and is reachable from both CLIMB  and DESCEND. This works by comparing the accelerometer value in the y-axis to the guards to determine which way the Kobuki should turn, which it does until the y-axis value is near zero. A value of zero indicates that the Kobuki is driving parallel with the slope of the hill. When the Kobuki detects the flat hilltop using the x-axis accelerometer values, it transitions to FLAT and again to DESCEND when it starts downhill. In that transition, it also asserts descending, causing the Kobuki to transition to STOP in Figure 4 when it again reaches flat ground.

2.2    Sensor Data

The primary sensors utilised in our implementation were the 3-axis accelerometer, three bump sensors (left, right, and centre) and three clif sensors.

An accelerometer outputs the acceleration along each axis of its reference frame. Using this infor- mation we can determine if the robot is oriented up the hill or not. If there is any acceleration in the y-axis as shown in Figure 9, clearly the Kobuki is oriented at an angle and hence a correction needs to be applied.  In much the same manner, this system is used to detect the flat top of the course as well as the descent.  During the design and testing phase, a low-pass filter was added to reduce noise in the accelerometer signals.

The three bump sensors are the means by which the Kobuki can avoid obstacles.  On physical impact, the bump sensor asserts its respective signal. Therefore the bump sensors (and further the clif sensors) are pure signals. When a bump sensor signal is present, the Kobuki will turn to avoid the obstacle. The clif sensor signals are used in the same way. The Kobuki passes the sensor signals to the MyRio using a serial connection. Command signals are passed to the Kobuki actuators the same way.

Figure 7: Diagram of the Kobuki platform.

Figure 7 shows the Kobuki hardware. The various sensors, ports, and buttons are labelled, as well as some unused functionality such as the LEDS.

Figure 8: Orientation of the accelerometer axes in the MyRio

The orientation of the 3-axis accelerometer in the MyRio is shown in Figure 8.  The MyRio was mounted on the top of the Kobuki, attached with velcro and the serial connector attached.  The forward direction of the Kobuki corresponded to the positive x-axis of the accelerometer (Figure 9, with z-axis not shown).

Figure 9: Mounting of the MyRio on the Kobuki, with the x and y orientation shown

3    Design Procedure

The design procedure followed several steps.  Due to the nature of the requirements, we could develop the obstacle avoidance algorithm and the hill climbing algorithm in parallel.  Once the algorithms were behaving predictably, we implemented a transition linking the two regions.

3.1    Obstacle Avoidance

Naturally the first problem to solve is the obstacle avoidance. As seen in the state diagram, this is the first region the Kobuki enters. Major parameters that were adjusted here include:

●  Distance to reverse upon making a collision.

●  Angle to adjust after reversing.

●  Distance to travel in the new heading.

These parameters contribute to the behaviour of the robot and the obstacles that it can avoid.

3.2    Hill Climbing

The hill climb solution required use of the accelerometer data.  It was not necessary to compute the tilt of the Kobuki as the raw accelerometer values were enough to determine if it was facing uphill. When facing uphill there should be no observable acceleration in the y-axis, hence this was a trigger to make the Kobuki reorient itself.

These triggers were defined using a threshold, hence noisy measurements could sometimes trigger these thresholds prematurely. Therefore a low-pass filter was introduced to smooth these measure- ments.  This was only introduced after testing our simulated design on the actual platform.  We found that there were a few key diferences in the simulation and reality that required adjustment. These are discussed later.

3.3    Transition Events

Another key aspect to success of the Kobuki is the transitions between hill climb and avoidance functionalities. The importance of these cannot be overstated - many groups failed due to transitions not behaving as expected. The main transitions are described below.

●  Transitioning from obstacle avoidance to hill climb at the base of the hill.

●  Transitioning from hill climb to the flat peak of the climb.

●  Transitioning from the flat peak to the descent of the hill.

●  Transitioning from hill descent to stopping at the bottom of the hill.

Table 1: Transition guards

Each of these transitions depend on accelerometer values and the state of the Kobuki when these values are measured.  A summary is shown (Table 1).  These transitions are very important, as if one is triggers prematurely, the Kobuki will believe it is further through the course than it is.

4    Testing Procedure

The testing procedure was a mix between simulation and controlled testing on the actual Kobuki. The computer simulation proved valuable in the initial testing of the avoidance algorithm. It was much faster to run a simulation than to deploy onto the hardware and run a physical test, however simulations were soon phased out as there were key diferences between simulation and physical testing. A main contributor was the coordinate system between the simulation and actual platform were diferent (the y and x axis were switched) which became tedious to switch on each test. This meant that every transition guard using accelerometer values had to be adjusted to reflect the coor- dinate system between the simulation and physical system. The next was the introduction of noise - noisy measurements from the real system tended to cause the Kobuki to behave unpredictably, so testing in the simulation was less useful to rectify these problems. This meant the simulation was less useful for testing the hill climb section. The simulation did still provide value in developing the general approach to climbing the hill.  Fine-tuning to develop precise accelerometer guards could only be done on the Kobuki hardware.

While addition of the low pass filter solved some issues, the Kobuki motion itself occasionally caused peaks in the signal that were not filtered enough. It was found that when switching states involved a wheel speed alteration, high accelerations would occur, creating unpredictable results.  Further, when the Kobuki collided with obstacles accelerometer peaks were also observed.  This led us to introducing a delay between states which in turn allowed accelerometer signal transients to settle before the state diagram began making decisions again.

This delay was made to be significant due to the importance of these transitions, outlined in the previous section. For the purposes of simplicity and readability, these delays were not represented in the FSM diagrams shown previously.

Utilisation of the wifi feature on the MyRio was immensely valuable during testing. This allowed a real-time view of the sensor data provided by the Kobuki (displayed on the PC in LabView), as well as the current state.The real-time sensor data was instrumental in discovering the source of many unwanted transitions. It was possible to see which sensors were activated, and exact accelerometer output.  Debugging time was thus vastly reduced, as when a problem occurred it was simple to identify the state the system was in and which transition should or should not be taking place. The easy debugging was especially useful in solving the accelerometer issue mentioned above, as when the physical Kobuki displayed unintended behaviour it was quick to find out that it was entering the HILL  CLIMB state when it was not on a hill.

The addition of the button B1 as a reset button was particularly useful in testing.  This allowed the Kobuki to reset from its initial state after a test, without needing the code redeployed.  Once again, this improved debugging time, allowing multiple variables to be examined in a single test.

When the intended design was implemented and performed as would be expected, more rigorous testing of the system in scenarios similar to the course was undertaken. Whereas previously small tests were run to check the performance of one part of the statechart, such as avoiding a single obstacle or being able to orient up the hill, it was important to check how these behaviours worked together. This was intended to test our assumptions in the design of our algorithm, rather than to see if it had been implemented correctly. We had limited access to the actual obstacles and ramp that would be used in the final assessment.  This meant that our system needed to be sufficiently general in order to cope with a variety of obstacles, and perform as expected on slopes of varying inclines, width, and surface texture.  However, using the equipment available small sections of the course were set up to see if the Kobuki could reach the ramp after a few obstacles.  The obstacle avoidance had trouble passing multiple obstacles, as if it became caught in a corner it would be trapped.  Thus, additions were made to the avoidance algorithm to account for running into an obstacle while already avoiding another one, by turning around and attempting to pass in a diferent section.

With these more extended tests, other issues were also noticed.  Some Kobukis had a noticeable drift to them, and while intending to drive straight they would veer to one side.  While it would be possible to correct for this by adjusting wheel speeds slightly, the error was diferent in each physical Kobuki so this adjustment would be largely pointless. Furthermore, each collision with an obstacle caused the Kobuki to lose its sense of the forward direction slightly, as the impact would create some deflection. This could not be entirely eliminated, but reducing the speed of the system when in DRIVE helped somewhat, which was helped by having more time to complete the course.

The testing procedure involved repeated trial and error, particularly in determining the ideal ac- celerometer thresholds. This seemed to be the most efficient way to find robust thresholds, although at times proved tedious.

5    Validation Procedure

To validate our algorithm we can notice that all states are reachable and no contradictions are possible. We are exclusively in hill climb or obstacle avoid and the transitions are very explicit.

Examples that ensure correctness of the algorithm include:

● We only enter clif avoid when a clif sensor is activated.

●  The pause state is only entered when button B0 is pressed.

●  In the run state we exclusively avoid obstacles until an accelerometer event is triggered.

To further validate the algorithm we can consider some potential unsafe states and prove that it is impossible to enter these states. To do this we need to define what an unsafe state in this context is. We use the following definition:

If the Kobuki enters a state in which it is possible for the device to fall of a  clif, or enters a loop in which it is impossible for the state machine to halt in the final Stop state, then the state machine is unsafe.

The implemented state machine is not a composed state machine - it does not operate at the same time as another while occupying two states.  Hence the Kobuki algorithm only occupies a single state at a time, greatly reducing the risk of dangerous states.

An obvious unsafe state would be to be in  OBSTACLE AVOID  state when the Kobuki is on a hill, as we do not expect there to be clifs to avoid during the obstacle avoid section.  However, this contingency was covered by CLIFF AVOID being a top level state.  Meaning regardless of the state, we will always avoid a clif.

With this feature the only remaining unsafe state will be if we cannot finally halt the state machine. Due to the linear nature of the state machine we are guaranteed to reach this state eventually assuming the appropriate string of accelerometer events.  Hence we can conclude that the given state machine is safe.

The design is restricted to this exact use case as it assumes the progression of the obstacle course. We assume the Kobuki first needs to avoid obstacles, and then climb a hill. It can be noticed that when the Kobuki has entered the hill climb state, obstacle avoid becomes unreachable.  Further, once the robot completes the obstacle course and stops, it will never leave the stopped state (unless the reset button is used).  While this achieves the specifications of the project, if the system needed to be generalised the state diagram will have to be updated.

6    Demonstration Outcome

6.1    Attempt One

We were fortunate to have two attempts at the course, as our first one failed due to an anomaly in the course design.  While the right hand side of the path was largely trivial, the left hand side presented a challenge in a small, diagonal pathway through which the robot barely fit.  Figure 10 shows the small space that caused the Kobuki to fail.

Figure 10: The Kobuki unable to pass through too small a gap

Upon colliding with the obstacle, the Kobuki was then largely stuck as the avoidance algorithm first caused the Kobuki to reverse away from the obstacle.  The Kobuki would then reverse into the wall immediately behind it, and as there are no collision sensors on the back of the robot, begin to lose it’s heading and fail the task.  The robot was unable to manoeuvre successfully when the obstacles were too close together.

6.2    Attempt Two

Our second attempt almost fell to the same issue.  This time the Kobuki traversed the right hand side, but unluckily just clipped an obstacle, causing it to run into a wall.  After colliding with the obstacle and the nearby wall repeatedly for some time, while making little progress, the Kobuki regained its heading and made it to the hill climb section. This section worked without fault, even displaying its clif sensing ability.  The Kobuki climbed the hill while re-orienting to maintain a straight uphill heading, travelled along the plateau, and descended without issue. The overall time taken to complete the task was slightly beyond the time limit.  The time constraint would have easily been met if not for the repeated collision issue earlier in the test.  Figure 11 shows the Kobuki upon completing the descent and coming to a stop.

Figure 11: Kobuki at the end zone

Of the initial requirements, the following were satisfied:

 The robot should not move until the ’Play’ button is pressed

 The robot should maintain its initial orientation and drive forward in the absence of obstacles or a hill.

 The robot should avoid obstacles, not fall of clifs or edges, and should maintain both wheels on the ground.

 Avoidance must always be satisfied, even if multiple obstacles are encountered at once or in rapid succession.

 After avoiding an obstacle the robot should return to initial orientation.

 The robot should detect an incline and orient itself to drive straight uphill.

 The robot should continue driving straight when the top of the incline is reached.

 The robot should detect a downhill slope and orient itself to drive straight downhill.

 The robot should detect level ground and stop within 40cm of the end of the descent.

 The robot should not rotate more than 180◦ .

 The robot should not exhibit ’hugging’ or eratic behaviour.

 The robot should not terrminate operation unexpectedly.

 The course should be completed within the time limit.