Week 7: Implementing Modules of the Path Finding Algorithm in Verilog

Welcome back, everyone! Last week, I explored the top-level architecture of the pathfinding algorithm in Verilog.

This week, I wrote a Verilog test bench. This test bench consists of different tasks that would provide necessary inputs to the RTL module in which the robot can start at a given starting location (starting row#, starting column#) on a given grid map, which is a single dimensional array acting as input to the RTL module consisting of all the rows of two-dimensional matrix of grid map arranged in sequential order to form a single dimensional array because Verilog does not accept two-dimensional array as input port. The output is also a single-dimensional array from RTL, which lists the grid point coordinates arranged in row# and column# for each grid point visited by a robot in its pathfinding exploration.

I am currently using a 100 Mhz clock as a system clock for my RTL module. The RTL module uses the “always” block to module a state machine. A state machine models the sequential behavior of the algorithm. For example, the default state of the state machine would indicate the starting row# and starting column #. For the x-first movement (row-first movement), the state machine in its initial first state will compare the destination column # to the starting column #.

If the destination column # exceeds the starting column #, the state machine will check if the grid point located at the next column # (column# + 1) has no obstacle based on the provided grid map (provided by the test bench). If there is no obstacle in the following grid point, the state machine will move into the next state, incrementing the robot location to the same row # but with column # assigned to column # + 1.

However, the destination column # is less than the starting column #. In that case, the state machine will check if the grid point located at the next column # (column# – 1) does not have any obstacle based on the provided grid map (provided by the test bench). If there is no obstacle in the following grid point, the state machine will move into the next state, incrementing the robot location to the same row # but with column # assigned to column# – 1.

However, if there is an obstacle at the next grid point, the state machine will move into the next state, where it will compare its current row # to destination row #.

If the destination row # exceeds the starting row #, the state machine will check if the grid point located at the next row # (row# + 1) has no obstacle based on the provided grid map (provided by the test bench). If there is no obstacle in the following grid point, the state machine will move into the next state, where it would increment the robot location to the same column # but with column # assigned to row# + 1.

However, if the destination row # is less than the starting row#, the state machine will check if the grid point located at the next row # (row# – 1) has no obstacle based on the provided grid map (provided by the test bench). If there is no obstacle in the following grid point, the state machine will move into the next state, where it would increment the robot location to the same column # but with row # assigned to row# – 1.

As a limiting condition, the state machine will continuously look for the new row # or column# location that is less than or equal to the maximum row # or column # supported by the given grid map. Each state will also mark the visit map array for that location as “1” once the robot moves to that grid point.

Thus, the entire algorithm can be explored in a maximum of 36 clock cycles since I assumed that the maximum row and column numbers are 6 (6 x 6 grid map). Thus, by implementing the algorithm in hardware, the speed increases dramatically. Maximum time (worst case) would be equal to 36 * 10ns = 360ns. If I increase the clock frequency, the robot can finish the pathfinding in less than 360 ns in the worst case.

Next week, I will explore the findings of the places where the algorithm failed and the fixes that I incorporated.