Fastest Path’s Algorithm

Dijkstra’s Shortest Path Dijkstra’s algorithm is used for our fastest path algorithm because it can find the shortest path between vertices in the graph. The coordinates on the arena are considered as the vertices in the graph.

Shortest Path Algorithm by (Grid count)

The vertex of the centre of the robot position is used as the starting vertex and the next point stopping grid as the end vertex. Using Dijkstra algorithm, the robot has to move along the edge of the graphs and reach the goal position. Making the shortest path the fastest path However, just by checking the shortest path will not give us the best performance because we have to take into account of the cost when the robot is turning. A 90-degree turn requires the robot to move its wheel approximately 15cm which is more than the width of a grid. Not only that, braking at every turn will slow down the robot.

Worst Case: 6 turning	Best Case: 1 turning

Implementation to minimize turning In order to make the shortest path (i.e the path where the robot moves minimum blocks), we have to ensure that the robot turn as less as possible. For this, the algorithm prefers a straight path rather than a path that requires turning. This can be implemented by reducing the cost required to move to next vertex, if the previous vertex, current vertex and the next vertex is in a straight line.

Shortest Path Algorithm by (Distance)

To implement this solution, a new graph is built using the obstacles, start and end point. We used the padded obstacles corners (red grids), start point, waypoint and endpoint as the vertices. For each vertex, it is checked against all the other vertices, to see if there is a clear path in between the 2 vertexes. If there is, an edge will be added between the 2 vertices. Using the algorithm, the robot can turn to any degree and move towards the goal. It does not have to necessarily go along the blocks.

Pseudo Code: 
1. Compute all vertices from padded obstacles corners, start and end points.
2. Connect all vertices with edges such that each edge does not intersect any padded obstacle.
3. Find the shortest path from the start vertex to the end vertex using Dijkstra Algorithm.

Making the shortest path the fastest path

Similarly to the previous Fastest path algorithm, it is not necessarily the fastest, if it requires a lot of turning. Thus, turning cost is added for each vertex added to the shortest path.

Weight = (Cost of start to the current node) + (Cost of current node to the next node) + Turning cost