5. Algorithm

1.  Overview

Our robot will explore and traverse an unknown area while avoiding obstacles. After that, it will find the shortest path from the start zone to the goal zone. We need a smart algorithm to guide it throughout the exploration and fastest run.

We design our algorithm and implemented as a PC program for the high computation power on PC and the ease of modification. It issues instructions and receives sensor feedback through Raspberry Pi using Wifi socket.

2.  Simulator

We also designed and implemented a robot simulator in Python which simulates the feedback from sensors according to the arena we designed. This would allow us to test our algorithms for any displacement of the arena without our physical robot. A screenshot of our simulator is shown in Figure 1 below.

Simulator GUI

Figure 1: Simulator GUI

We can visualise the map explored by our robot through program’s GUI. Map descriptor can be generated anytime according to the map it explored.

3. Exploration Algorithms

In this project, a wall follower algorithm is selected because the robot can not move quite accurate and needs a lot of auto-realignment according to the walls or consecutive obstacles.

Inside this follower algorithm, a right-hand rule is selected. The basic idea of this algorithm is to make sure that there is always an obstacle on the right side of the robot. Here is the pseudo-code.

while(not reach destination){

if(can go right){turn right and forward}

else if (can move forward){move forward}

else {turn left}

}

4. Auto-realignment of Robot Position

Because our robot may deviate from a straight line because the two motors would have speed difference and 0% error is impossible in real-life applications.  As a result,  an auto-realignment of robot position is strongly needed and would enhance robot’s performance a lot. This is a work both performed in hardware and software sides.

4.1 Implementation in Hardware

The auto-realignment function is implemented inside Arduino.

The first auto-realignement method is to make sure the robot is parallel with the wall. It compares the two front sensors’ readings and to rotate until they are nearly equal to each other. This Because sensor’s manufacturing difference, it is highly recommended to set an offset and a error tolerance limit so as to improve the realignment performance.

Another auto-realignment function is to make  sure the distance from robot to wall is just proper to avoid obstacles. It compares the front sensor’s reading with a preset target value. If the robot is deviate from its original position, it would recover back by driving the motors until the front sensor’s reading is equal to the preset value.

4.2 Triggered in Software

Even though the auto-realignment function is implemented inside hardware. It is inside the algorithm to decide whenever to trigger the auto-realignment condition. In our project, two calibration conditions are designed.

The first auto-realignmentcondition is whenever the robot is inside a corner made by two obstacles or walls, it would perform auto-realignment two times to come back to correct position.

The second auto-realignmentcondition is to keep an alarm counter. Whenever the counter exceeds a preset value and alarm flag is set, the robot would try to find a nearest three consecutive obstacles or wall to perform auto-realigment.  If it is impossible to find, the robot would take a risk to continue the right hand rule algorithm until it reaches a auto-realignment point. After coming back to correct position, the alarm counter would be set to 0.

5. Fastest Path Algorithms

In our project, the shortest path is defined as the path from the start point to the destination with the smallest number to turn. It is defined like this because we find out that one turning command would cause about around a 1 second whereas the robot’s maximum speed could travel 0.45 meters in a second. As a result, more turnings mean more time to require for completion of the shortest path.

Bread first search is used to search this fastest path. The basic idea is that there are 15*20 = 300 blocks inside the arena. In addition,  for one block, the robot could only have 4 possible directions to face. As a result, there are 1200 vertexes we could search. We could define an edge between two neighbour vertexes equals to 2 when a turning is required. As a result, the first path figured out by our BFS is the one with the smallest number of turnings.