Week 4: Developing the Algorithm

Welcome back, everyone! Last week, I explored the Webots simulation environment to visualize a robot’s movement from its starting location to its destination location. This week, I will discuss the first refinement level in my grid-based pathfinding algorithm. There are three parts to the pathfinding algorithm:

1.The map for navigation is divided into equally spaced grids with marks identifying whether a specific grid is occupied by an obstacle (marked as “1”) or not occupied with an obstacle and available for the robot to move into (marked as “0”).

2. Because two consecutive grids are equal distances apart, the algorithm calculates the cost of the overall path by adding the number of grid location that it visits until it reaches its destination.

3. After determining all possible destination paths, the algorithm chooses the route with the least cost.

Here’s a little more depth into the first layer of the actual algorithm:

1. I assume that the robot has only four sensors to sense obstacles. So, the robot moves in the north, west, east, and south directions.

2. There are two major methods: move in the x direction (x-traversal up or down) and move in the y direction (y-traversal left or right). The x coordinate represents the row number, and the y coordinate represents the column number.

3.The reference origin point for the grid map (0,0) is in the top left corner of the grid. Let’s say the destination x coordinate (row#) is more than the current grid point’s x coordinate. In that case, the robot moves down by one location if there is no obstacle in that location and if the robot never visited that grid point before. Similarly, if the destination x coordinate is less than the current grid point’s x coordinate, then the robot moves up by one location if there is no obstacle in that location and if the robot has not visited that grid point, until the destination x coordinate is reached. So, for the robot to reach the intended x coordinate (row#), it must move either up or down.

4. Now, let’s say the robot’s movement in the vertical direction is blocked due to obstacles. In that case, the robot moves in the y direction (column#), left or right, until the desired destination y coordinate (column#) is reached or until the robot move is blocked due to obstacles or the boundaries of the grid map. Now, suppose the destination y coordinate (column#) is greater than the current grid point’s y coordinate. In that case, the robot moves right by one location if there is no obstacle in that location and if the robot has never visited that grid point. Likewise, if the destination y coordinate is less than the current grid point’s y coordinate, then the robot moves left by one location if there is no obstacle in that location and if the robot as never visited that grid point, until the destination y coordinate is reached.

The goal is to find the most optimal path. So, I am writing the algorithm in such a way where the robot tracks the final destination location relative to its current location. Most existing algorithms for robot path navigation use all possible paths, including the ones that may not directly go to the destination location. Thus, these algorithms, including Dijstrka’s algorithm, would take much longer to find the optimal path. My approach is unique and optimized for grid-based map navigation.

Come back next week to find out how I have explored the HDL, Verilog to implement and simulate this algorithm!