Exploration Algorithm

There are several exploration algorithms implemented in the simulator. All of them were created based on either Greedy Algorithm or Wall Following Algorithm.

Before the exploration, if the Map entity changes, a graph of vertices based on the explored arena and obstacles will be built. The graph’s vertices represent the different positions on the arena where the robot can be at. The edges represent the path where the robot can move from one vertex to another.

Explored 100% Explored 40%

Greedy Algorithm

The greedy algorithm’s objective is to explore as many unexplored blocks as possible. The following figures show the different number of cells it could explore, assuming there are no obstacles in the unexplored region.

 Scenario 1 Scenario 2 Scenario 3
 18 grids to explore 27 grids to explore 9 grids to explore

In the greedy algorithm, it will choose Scenario 2’s position. The exploration algorithm will look at all the different scenarios using Breadth First Search (BFS) from the current location and get the best next position to stop at; for the robot to explore that position.  To move to the next position, Dijkstra Algorithm is used.

Heuristic Algorithm – Improved from Greedy Exploration Algorithm

To denote the best location to explore next, calculation of score is performed for each position and then compared. The calculation involves the distance it is away from the current location, distance away from start position, distance away from the end position and the number of grids that it could explore. The weightage is adjusted accordingly to the scenario of the Map. For example, when the endpoint has been found, the endLocationWeightage will be set to 0. Or when the user initiates “terminate exploration”, startWeightage will be set to 100000, so that it will go to the nearest position near the start position.

Wall Follower 1 (Left wall)

In the algorithm implementation, Wall Follower is also implemented as one of the exploration algorithms. It follows the left wall and moves until the next stopping location is its starting point. Then it will switch to the Heuristic algorithm to explore unexplored grids in the centre of the arena (if there are any). Finally, it returns to the starting point.

Pseudocode:

if (turnedleft previously and forward no wall)
     go forward;
else if (no wall at left)
     turn 90 deg left;
else if (no wall forward)
     go forward;
else
     turn 90 deg right;

Wall Follower 2 – Improved (Left wall)

To improve the performance of wall follower algorithm,  the algorithm will do a recursive search along the left wall until there are unexplored grids are found. Then the robot will move to the location using the Dijkstra algorithm. Before this implementation is made, the previous Wall Follower algorithm will follow the wall strictly even when all the grids are explored around the area. The following figures show the difference between the improved and the previous one.

1st Version Improved Version Video

Optimize Sensor reading and Movement

  

 

 

The diagram on the left shows two different scenarios. If there are unexplored rows of blocks on the right side, the robot can only move one grid at a time (shown in the left figure). Otherwise, it will move 3 grids ahead (shown in the right figure), saving the number of messages passed between PC and Arduino.

Exploration Termination Condition

In the leaderboard challenge, the exploration must be complete within 6min. However, due to the flow of our network structure, during the 1st week of leaderboard challenge, it took our robot 4min to explored the endpoint. Thus, we implemented the terminating condition, such that when it reaches the endpoint, it will head back to start point when a specified time limit is reached.