Week 6: Architecting Modules of the Path Finding Algorithm in Verilog

Welcome back, everyone! Last week, I explored different aspects of Verilog and how to model basic modules that describe sequential and combinational digital logic.

This week, I want to utilize those Verilog skills and embark on the complex task of architecting modules in Verilog to describe the intricate robot path-finding algorithm. At a higher abstract level, the user would provide the grid map in terms of a two-dimensional array. Each grid location, identified by a specific row # and column #, serves as the position that the robot would occupy if there’s no obstacle in that grid location. The presence of an obstacle is identified by marking each area in this two-dimensional matrix (map), with “0” for no obstacle and “1” for an obstacle.

Thus, I am using a two-dimensional array for a grid map. I plan to write a behavioral code to create tests in Verilog (called a test bench). The grid map would be initialized at the start of the simulation through the test bench. I would use internal memory to initialize the grid map for FPGA implementation. I will have another two-dimensional array, ‘visitMap,’ for keeping track of all the grid locations (row #, column #) that the robot visits. The initial part of the algorithm does not allow the robot to visit the same nodes already visited to make the path optimal. I may change this part of the algorithm conditionally if I find my test cases, which would test different starting and destination locations and grid maps for other places for obstacle locations. I plan to initialize the starting and destination locations from the test bench using “task.” The same task can initiate the robot’s path exploration by setting the “start_path_finding” signal.

The path exploration RTL saves each grid location (row #, column #) the robot visits to get to the destination location into a single-dimensional array called “return_array.” I chose a single-dimensional array because it’s a more manageable pass-through task.

After I defined the central data structures and building blocks of the main RTL code, I focused on the initial algorithmic implementation. Based on the path-finding algorithm I devised, the robot starts at the starting location (starting row #, column #) given by the test bench (user). It moves between rows or columns (one grid location at a time) until the destination location (destination row #, column #) is reached. I plan to implement this logic part with a “while” loop. The algorithm does two exploration paths simultaneously: 1) Row # first algorithm: Change the row # location first to move towards destination row # until there is an obstacle or the destination row # location is reached. If the robot is blocked due to an obstacle, then the robot moves in the following column # location to reach the column # location of the destination. The robot repeats this sequence until it reaches the destination location. This part is called ‘row first.’ The robot does not move into a location that it already visited based on the “visit map” array to avoid the infinite loop. 2) Column # first algorithm: Change the column # location first to move the robot towards the destination # column unless blocked by obstacles or the destination column # is reached. If the robot is blocked due to an obstacle, the robot moves to the following row # location to reach the row # location of the destination. The robot repeats this sequence until it reaches the destination location. The robot does not move into a location that it has already visited based on the ‘visitMap’ array to avoid an infinite loop.

The robot adds “1” to the cost every time it moves. The equal weight of “1” is because the distance between two consecutive grid locations is the same. Finally, the algorithm chooses either going through the row # first or column # first algorithm’s suggested path based on which outputs a lesser cost. Since the distance between each grid location is exact and is reflected in the cost, knowing the starting location automatically determines the precise location of the robot at any given time. Thus, it eliminates the need for a GPS to determine the robot’s location.

Next week, I plan to rigorously test my implementation using my test bench and a series of carefully designed tests. If the testing reveals any weaknesses in the algorithm, I am prepared to modify the algorithm step by step until the majority of the test conditions are verified, ensuring the reliability and robustness of the final product. Come back next week to find out more!