Robot Path Determination Using Landmark Optimization
Advisor: Kevyn Adams
Internship Location: Online, External Advisor: Dr. Vijay Kamble - Professor of Information and Decision Sciences at University of Illinois, Chicago
Onsite Mentor: Dr. Vijay Kamble
I will be conducting both library and internet research. I will be gaining more knowledge from books related to robot path finding using a landmark map. I will also be reading through several research papers on this topic. My findings will also be based on observations and experimentation of the algorithm and its implementation on hardware.
As a result of the research, I will be implementing an algorithm on FPGA such that given the home coordinates of the robot, the coordinates of the obstacles, and the coordinates of the final destination, the robot will be able to find the optimal path from the source (home) to the final destination with a given speed.
The new perspective that my research is bringing is that my project explores building an autonomous robot, which does not require GPS signaling or communication with base camp in order to do path-finding. This feature of the robot is unlike the abilities of most of the robots in the industry.
With the advent of artificial intelligence, teaching robots to learn the shortest path and avoid obstacles is an important research topic in robot learning because it helps produce robots that can help in industrialized and military tasks that are riskier for human beings to operate. In the studies, it has been shown that an industrial robot increases productivity by 80%.
My project could be of use in many settings, for example in the homes of seniors to assist them in their daily life. It could also be used in industrial environments where GPS signals cannot be detected properly. These robots could also be used in war zones in underground tunnels where GPS signaling cannot reach.
Project Blog
Week 1: Introduction
Hi Everyone, and Welcome to my Senior Project! During these next few months, I will be writing and implementing a path-finding algorithm for an autonomous robot to find the most optimal path from a certain starting point (source location) to a destination location. In this post, I will talk about my motivation behind this project, some background, and what I hope to achieve by the end of my project.
Most of you are probably familiar with self-driving cars. These self-driving vehicles are also known as autonomous cars, which are driverless vehicles that use a system of sensors, cameras, and other remote sensing devices like Light Detection and Ranging Sensor (LIDAR) to construct a map of the surrounding environment that facilitates the ability of the vehicle to navigate effectively and efficiently while avoiding both static and dynamic obstacles. These vehicles will drive from a starting location to some final destination with the assistance of Global Positioning System (GPS) signaling to find the location of the vehicle. Almost all autonomous vehicles currently require GPS beginning or RF signaling to operate.
This brings me to my next point of contention. Will GPS signaling always be available? What if humans want to enter, move through, and investigate environments in which it is actually difficult for them to operate? This is where autonomous vehicles, or rather more specifically, autonomous robots, become incredibly useful. Delving further into this idea of autonomous robots, what if these robots are placed in environments where GPS and Radio Frequency (RF) signaling are not available? Considering these arising problems, in my project, I want to explore how to write and execute an algorithm that an autonomous robot can use to navigate through an environment in which humans cannot operate or where GPS/RF signaling is not reliably available and go from a source location to a destination location with the most optimal path.
In implementing this algorithm, I will be striving for maximal efficiency for the robot to find the most optimal path from source to destination while reacting to static obstacles in real time. This means that immediately after the obstacle is found, the robot should change its path as opposed to facing a delay after meeting the obstacle. Making a hardware efficient algorithm would allow for a robot to achieve this efficiency in avoiding obstacles and finding the optimal path much better than would the pure software implementation of this algorithm. Therefore, I will be implementing this algorithm in hardware since it has lower latency compared to software.
Now, I’ll dive a little bit into what “hardware implementation” means. This means that I will not be using the traditional software encoded languages like Java and Python to write this algorithm. Instead, I will be using a hardware description language (HDL) called Verilog to write the code for the algorithm and implement it by using a Field Programmable Gate Array (FPGA), which is an integrated circuit. This integrated circuit has logic components like logic gates, memory elements(flip-flops), digital signal processors, and clock infrastructure that are all internal to the physical FPGA chip and that can be programmed by the user. I will code the hardware logic in Verilog to configure the FPGA. The synthesis tool will convert code into the logic components within FPGA, which will allow me to implement my Verilog algorithm in hardware. That was a lot of technical background knowledge! But it is very good to have some understanding of it before venturing into the rest of my project.
Through my research and writing of this algorithm, I hope to answer a few main questions. Does implementation of this algorithm in FPGA truly improve the efficiency of the robot’s path-finding abilities? Is the robot able to find the most optimal path from a starting point to a final point while avoiding the obstacles? How would this algorithm be physically helpful in real life applications for autonomous robots in industry?
As I begin to engage more deeply with the technical problem-solving and details behind this path-finding algorithm and the technical complexities of the FPGA, Verilog code, and software simulation tool set, I hope to find that the FPGA did improve the efficiency of the path-finding algorithm, and that this robot, which will be able to find the most optimal path, will also be especially beneficial in applications like war zones. As I mentioned before, most autonomous vehicles require these type of sensor systems to go from go from a source to destination. Hence, by the end of this project, I certainly aspire to have created a relatively unique and applicable tool for autonomous robots to use in environments where GPS and RF signaling are not available. Come back next week to learn about my initial steps of the project!
Week 2: Initial Research and Basic Ideas for Algorithm Implementation
Welcome back, everyone! I'm excited to present my research in robotic path planning. This research builds upon my previous work and introduces novel steps and ideas for implementing an innovative algorithm that could be vital in the robotics field.
Before beginning the technical part of my project, this week, I wanted to do further research on three main topics that would be significant to my project execution. I want to discuss the vast amount of information available about existing pathfinding algorithms and how these pathfinding algorithms have evolved. I will also dig deeper into the Field Programmable Gate Array (FPGA) hardware, how it will be helpful in my project, and possible options for robotic path exploration in a landmark map combined with FPGA implementation using hardware-efficient algorithms. This research is about understanding the field's current state and pushing the boundaries of what is possible in robotic path planning.
The navigation of mobile robots has been the subject of extensive study. It involves two main aspects: map modeling of landmarks the robot must navigate through and path planning, which encompasses the current robot algorithms to plan paths and navigate. There are currently four different types of map models: scale, topological, semantic, and behavioral maps. Each serves a specific purpose, depending on the robot's use for navigating a particular setting. Under the path planning section, there are two types of scenarios in which path planning is done: Single-Agent Path Planning (SAPF) and Multi-Agent Path Planning (MAPF). Three SAPF algorithms exist Classical, intelligent optimization, and artificial intelligence. There are also two types of MAPF algorithms: Centralized and Distributed Technology. Several path-planning algorithms fall under each of these categories. Furthermore, the current autonomous robots use LIDAR-based (Light Detection & Ranging) signaling that helps the robot create a map of its surroundings and GPS signaling for assistance.
Now, I'll expand upon the research I did this week regarding the hardware part of this project, specifically FPGA. Hardware description languages (HDLs) generate digital hardware's behavioral and structural description. In real life, hardware blocks work simultaneously as soon as they are powered. So, the hardware description incorporates this parallelism by adding constructs such as "always" and "assign." There are two main hardware description languages, Verilog and VHDL (Very High-Speed Hardware Description Language). System Verilog is an extension of the existing Verilog language. The portion of HDL behavioral code that can be represented directly in hardware is called RTL (Register Transfer Level). The RTL code can be run through the "Synthesis" tool, which generates a netlist of digital hardware components representing the RTL description. This netlist is generated using FPGA (Field Programmable Gate Array) or ASIC (Application Specific Integrated Circuit) libraries of digital hardware components. Since hardware works in parallel, it is generally faster than equivalent software code describing the same algorithm but running on a particular operating system. Hardware implementation can reduce the latency significantly, making it most suitable for applications that require real-time response. Among the FPGA and ASIC platforms available for implementing digital hardware, I chose the FPGA platform because I can reconfigure FPGA hardware by making changes in RTL code and resynthesizing the design. Since my path exploration algorithm requires an accurate time response for the robot to act quickly enough to avoid exceptionally dynamic obstacles, I chose hardware implementation using FPGA. I aim to simulate my design to demonstrate the pathfinding algorithm I choose.
Imagine a robot navigating through a complex environment with only partial information about its surroundings. It's like trying to find your way in a dark room with a flickering flashlight! Current research uses the Dijkstra algorithm in most implementations, but it's only sometimes efficient. For successful traversal of the autonomous robot, the robot's control block needs to know two things at any given time: 1) What is the path for the next node based on the map, starting location, and destination location provided? 2) Where exactly is the robot currently located on that path such that it can use that certain part of the map to move to next node? My research aims to tackle these challenges and develop a more effective path-planning algorithm for autonomous robots.
My proposed algorithm introduces a groundbreaking approach to meet the two essential requirements for a successful path-planning algorithm for autonomous robots. It involves using an Equidistant grid-based landmark map of the surroundings and directed pathfinding from the starting to the destination location. The key innovation of this approach is that the consecutive grid nodes are located at equal distances, enabling the entire map to be configured in grid nodes with their X and Y locations. This design allows the robot's movement to be traversed through these grid locations, eliminating the need for GPS or any other RF signaling. This innovative algorithm can potentially revolutionize the robotic path planning field, inspiring a new era of efficient and autonomous navigation. Come back next week to keep up with my progress!
Week 3: Exploring the Simulation Environment
Welcome back, everyone! After the extensive research that I discussed in last week’s blog post, this week, I started looking into a particular software that I can use to display the results of the pathfinding algorithm. This will make more sense after I talk about the output I actually want to see from the algorithm.
The pathfinding algorithm is intended find the optimal path on a given grid map. I will define certain locations in the grid with obstacles that the robot would not be able to enter in its path. I will also define a starting location and a final destination location on the grid. The robot would have to navigate through this landmark map from that given starting location to that given destination location while avoiding obstacles in certain grid locations. The final optimal path with the least cost (shortest possible path) that is found by the algorithm will be made up of different grid locations. When I implement the algorithm in Verilog, I want it to output a list of all the grid locations as x and y coordinates (format: (x,y) = (row # of the grid, column # of the grid)) that make up the optimal path, including the starting and final grid locations and the path’s cost. But, this output of the robot’s optimal path is not very communicative to users, so I realized that a true visual display of a robot executing the algorithm on a grid would be far more appealing and communicative to users. So, here comes the use for the simulation environment!
The simulation software I have decided to use to visually display the algorithm’s output as a robot moving along the optimal path through the landmark map is called Webot. Webot is a free open-source software that simulates the movement of robots. This week, I enjoyed exploring Webot in depth, understanding all of the features it offers, experimenting with different settings, robots, motors, and robotic movements, and determining how I could use it specifically for the purpose of my project’s output. After downloading Webot, I first imported the 69 environments available in the software. Each environment had a unique robot and surrounding, including an uneven desert terrain, a checkerboard, a house, and a city where an autonomous car drives itself. Each simulation environment is paired with C code that contains specific commands that control the movement of the robot or vehicle. I experimented with some of the sample code, changing values and changing the order of certain commands to see how it would affect the robot in the simulation. I also found out that different physical items can be imported into any chosen environment, like cardboard boxes and oil barrels. I could use these items to simulate an obstacle in the grid map in the simulation environment that must be avoided by the robot. In fact, there is also a feature that allows you to import motors and different actuators to customize a robot. In the corresponding code, the acceleration of a motor, energy efficiency of a motor, and several other functions can be altered, giving the robot more flexibility to move in the given environment the way I would want it too. After exploring Webot, my future goal is to find out how to use this software to create a 6 by 6 grid, place obstacles at certain coordinates, set starting and destination coordinates on the grid, and make a robot move from one square to the next specified square based on the Verilog output from the pathfinding algorithm. Since I cannot directly connect the Verilog output to Webot, I plan to separately configure the simulation in Webot, and I will manually input the Verilog output into the Webot code.
Stay tuned for next week’s blog post where I’ll discuss my work on the algorithm in more detail!
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!
Week 5: Exploring Verilog, Hardware Description Language
Welcome back, everyone! Last week, I explored the initial development of the robot path-finding algorithm. As I mentioned in my earlier blogs, I plan to implement this algorithm on FPGA.
This week, I will discuss my learning of Verilog, the hardware description language, and I’ll explain further detail about HDLs. A Hardware description language describes how digital hardware behaves in circuits. Digital hardware consists of combinational and sequential elements. A combinational circuit consists of digital elements whose output solely depends on its inputs. So, combinational circuits do not require memory, for example, AND, OR, NOT, NAND, NOR gates, multiplexers, encoders, decoders, etc. On the other hand, the output of a sequential circuit depends on its inputs and the previous state of its output. Sequential circuits must retain the last state of the output, meaning they implement some memory.
I explored how to model combinational and sequential circuits using Verilog. Overall, the robot path-finding algorithm can be divided into different states of the robot, its position at a given time, and the actions the robot would take in each of these states.
Verilog supports various behavioral modeling blocks. There are two main procedural blocks called "always" and "initial." All statements in the "always" block execute until the inputs used in the blocks and listed in the sensitivity list have a change. In contrast, the "initial" block is executed only once in the simulation. Clearly, anything that works only once after the power is on has no equivalent digital circuit representation, and thus, the "initial" block is not synthesizable. But the "always" block represents the true behavior of the digital circuit and therefore is synthesizable to the netlist of digital elements. Both blocks can be modeled with a "begin-end" or a "fork-join" construct. All the statements within the "begin-end" construct execute sequentially unless there is a "non-blocking" assignment within those statements. "Non-blocking" assignments happen simultaneously, simulating the actual behavior of the typical digital circuit.
On the other hand, assignments in blocking statements happened sequentially. All the statements within the "fork-join" block execute simultaneously, irrespective of blocking or non-blocking assignments. "Fork-join" blocks are not synthesizable. Synthesized HDL code can generate a netlist of realizable digital elements called RTL (Register Transfer Level) code.
I learned that Verilog is a versatile language that can actually be used to create a wide range of circuits! For instance, 'Case' and 'if' statements can be used to design multiplexers, encoders, decoders, and priority encoders, among other combinational circuits. 'Always' blocks, when combined with a sensitivity list that includes 'posedge' (rising edge) or 'negedge' (falling edge) of the clock, can model flip flops or synchronous memory. Verilog also offers a variety of operators, including binary, unary, reduction, ternary, equality, concatenation, logical, and bitwise, which can be used to create complex circuit logic.
In fact, Verilog also supports a variety of loop control logic for behavioral modeling. "For" loops can model shift registers. "While" and "repeat" loops can effectively model the behavior of repetitive parts of the logic. "For" loops can be synthesizable if they have a known constant number of iterations.
That was a significant amount of technical background, which will help me implement my path-finding algorithm using a Finite State Machine and some combinational logic circuit logic. The Finite State Machine, a practical application of Verilog, uses the clocked version of the next state as the current state. The combination portion of the Finite State Machine is modeled using a 'case' statement, demonstrating the real-world application of Verilog in robotics.
Come back next week to find out how I have used these Verilog constructs to model the robot path-finding algorithm!
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!
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.
Week 8: Initial Results of Path Finding Algorithm in Verilog
Welcome back, everyone! Last week, I explored the detailed architecture and implementation of the pathfinding algorithm in Verilog. I also wrote RTL and a testbench in Verilog and ran simulations.
While testing the design, I realized that sending the results (row #, column # coordinates of the nodes visited by the robot along with cost) all placed in a one-dimensional array requires a lot of processing in the test bench to get meaningful results for each node visited. I had to read the first two numbers and assign them to the row# and column#, respectively, of the node visited by the robot. I had to repeat the process until I get all the information on the nodes visited. So, instead, I modified the RTL port definition to include providing the x (column #) and y (row #) of each node visited separately with the valid signal. By doing so, my interface and its processing within the test bench became relatively simple.
Initially, in my first test case, I provided the grid map the x, y (column #, row #) coordinates of the obstacles as (1,2), (2,2), (1,3), (2,3) and the starting location as (0,1) and destination location as (5,3). According to my algorithm, the destination column # 5 was more than the starting column # 0. So, the state machine moved to a related state and incremented column # to 1 with the new coordinates of the node visited by the robot, such as (1,1). Then the state machine looked at the current starting coordinates (1,1) to the destination coordinates (5,3). Since the destination column # is still more than the current starting column #, the state machine remained in the same state and incremented the column # to 2 with new coordinates to (2,1). Since the destination column # is still more than the current starting column #, the state machine remained in the same state and incremented the column # to 3 with new coordinates as (3,1). Since the destination column# is still more than the current starting column #, the state machine remained in the same state and incremented the column # to 4 with new coordinates as (4,1). Since the destination column # is still more than the current starting column #, the state machine remained in the same state and incremented the column # to 5 with the new coordinates as (5,1). The destination column # became the same as the current starting column #. The state machine moved to a state where it would move in the y direction by changing the row #.
According to my algorithm, the destination row # 3 was more than starting row # 1. So, the state machine moved to the related state and incremented row# to 2 with new coordinates of the node visited by the robot as (5,2). Then, the state machine looked at the current starting coordinates (5,2) to the destination coordinates of (5,3). Since the destination row # is still more than the current starting row #, the state machine remained in the same state and incremented the row # to 3 with new coordinates to (5,3). Now the destination coordinates (5,3) are exactly the same as the new coordinates visited by the state machine/robot; the state machine exits to the original 0. It helped prove that my algorithm worked in my first test case.
So, I wanted to test the pathfinding algorithm further and came up with the following test case that changed the obstacle coordinates by adding two more nodes with obstacles: (3,1) and (4,1). So the test case was with all the following coordinates (column #, row #) as (1,2), (2,2), (1,3), (2,3), (3,1), (4,1).
During the simulation, I discovered that according to my algorithm, the destination column # 5 was more than starting column # 0. So, the state machine moved to a related state and incremented column # 1 with new coordinates of the node visited by the robot, such as (1,1). Then the state machine looked at the current starting coordinates (1,1) to the destination coordinates (5,3). Since the destination column # is still more than the current starting column #, the state machine remained in the same state and incremented the column # to 2 with new coordinates to (2,1). Since the destination column # is still more than the current starting column # but the following incremented column location (3,1) had obstacles, the state machine could not increment the column #. Instead, it went to the state where row # will be changed. Since the destination row # 3 is more than the current row # 1, the state machine wanted to go to a state where it would increment row # to 2 with new coordinates as (2,2), but there was an obstacle in that location. Thus, the state machine/robot was stalled without action. There, I found a mistake in my pathfinding algorithm.
Combe back next week to find out how I fixed this bug in the algorithm and re-simulated the design.
Week 9: Improving the Path Finding Algorithm based on the Verilog Simulation
Welcome back, everyone! Last week, I spent time debugging the Verilog simulation that encountered issues with specific obstacle positions. These positions, with coordinates (column #, row #) at (1,2), (2,2), (1,3), (2,3), (3,1), (4,1), proved a significant challenge, but I'm happy to share that I successfully resolved them.
The starting location, initialized at (0,1), represents the initial state of the system, while the destination coordinates, at (5,3), represent the desired final state. The state machine implementing the path-finding algorithm compares destination column 5 with starting location column 0. Since destination column # is more than the starting column and the next column position is not occupied by the obstacle based on the grid map, the state machine moved to a state where it incremented the column to 1. Since the current column 1 is still less than destination column # 5 and the next column position is free from obstacles based on the grid map, the state machine remained in the same state and incremented column # to 2. Then, the state machine compared the current column position 2 with the destination column 5. Still, the next column position occupied the obstacle, so the state machine moved to a state where it would change the row position.
The current position was at (2,1), and the state machine wanted to change the row position. The current row 1 was less than destination row 3, but position (2,2) had an obstacle. In the previous state, the state machine encountered position (3,1) and an obstacle. So, the state machine was stuck. In such a situation, if the next column and next row both have obstacles, the state machine would move to a different state, which indicates a 'move blocked' status. In this state, the machine would make the opposite decision, meaning if the destination row is more than the current row, instead of incrementing the row, the state will decrease the row. With this fix in the state machine, the machine moved to a state where it would decrement the row to 1 and move to location (2,0). With the current row to be 0, the state machine could not decrement the row further due to grid size limitation; it moved to a state where it would increment the column.
With the current column being 2 and the destination column being 5, the next column position is free of obstacles. The state machine incremented the column to 3 and moved to location (3,0). Since the destination column 5 is still more than the current column of 3, and the next column position did not have an obstacle, the state machine incremented to column 4 and moved to location (4, 0). Since the destination column 5 is still more than the current column of 4, and the next column position did not have an obstacle, the state machine incremented to column 5 and moved to location (5, 0). With the current column at 5, the destination column, the state machine moved to a state where it could change the row. This summary of the state machine's movement demonstrates its successful navigation to the destination location in the presence of a new set of obstacles.
With the current row being 0 and the destination row being 3, the next row position is free of obstacles. The state machine incremented the row to 1 and moved to location (5,1). Since the destination row, 3 is still more than the current row of 1, and the next row position did not have an obstacle, the state machine incremented to row 2 and moved to location (5,2). Since the destination row, 3 is still more than the current row of 2, and the next row position did not have an obstacle, the state machine incremented to row 2 and moved to location (5, 3). Thus, the state machine successfully moved to the destination location in the presence of a new set of obstacles.
In the next blog, I will explain the further testing of my algorithm, which will involve more complex obstacle configurations and performance evaluations.
Week 10: New obstacle configuration and Improving the Path Finding Algorithm based on Verilog Simulation
Welcome back, everyone! Last week, I debugged one of the bugs in my algorithm. I continued creating different maps of obstacle positions and start and destination locations. I added the obstacle at location (column #, row #): (1,4) and (2,4). So, the overall obstacle positions were at (3,1), (4,1), (1,2), (2,2), (1,3), (2,3), (1,4), (2,4), (3,4), (4,4). I changed my start location to (0,2) and kept my destination location as (5,3).
The starting location, initialized at (0,2), represents the system's initial state, while the destination coordinates, at (5,3), represent the desired final state. The state machine implementing the path-finding algorithm compares destination column 5 with starting location column 0. Since the destination column is more than the starting column and the next column position is occupied by the obstacle (1,2) based on the grid map, the state machine could not move into a column incrementing state. Instead, due to an obstacle in the following column location, the state machine moved to a state where the start row is compared to the destination row. Since the start row is 2 and the destination row is 3, the state machine moved to a state where the row is incremented. Then, the state machine compared the current row 3 to destination row 3 and realized it reached the destination row. However, the current column 0 still does not equal destination column 5, so the state machine moved to a state where the column can be incremented. Still, again, the location (1,3) has an obstacle. This is a critical scenario because the state machine arrived at the destination row but not the destination column. It cannot move to a state where it could increment the column because an obstacle is located at (1,3). So, the state machine goes to an exception-handling state where it increments a row even though it already reached the destination row. In the current location (0,3), the state machine still cannot move to a column incrementing state because even the following location (1,3) is also an obstacle. So, the state machine remains in an exception handling state and increments the row to 4. The current location is (0,4). Then, the state machine looks at the destination row and cannot decrease the row because the robot has already visited the previous row. So, now the state machine compares the destination column 5 with current column 0 and tries to increment the column, and the next column location (1,4) does not have an obstacle, and hence, the state machine goes to a state where it increments the column. The current location is (1,4). Then, the state machine again compares the current column 1 to destination column 5 and checks if the following column location (2,4) does not have an obstacle, and since it does not have an obstacle, the state machine increments to column 2. Then, the state machine still compares current column 2 with destination column 5; it checks if the following column location (3,4) has an obstacle, and since it has an obstacle. So, the state machine can't increment the column, nor can it decrement the row to go to the destination row. So, it again goes to the exception handling state, increments the row to 5, and goes to (2,5). Then, the state machine compares the current column 2 with destination column 5 and checks if the following column location (3,5) has an obstacle. Since there is no obstacle at (3,5), the state machine increments the column and goes to (3,5). Then, the state machine compares the current column 3 with the destination column 5 and checks if the next column position (4,5) has an obstacle. Since no obstacle exists at (4,5), the state machine increments the column to 4 and goes to location (4,5). Then, the state machine compares the current column 4 with destination column 5 and checks if the following column location (5,5) has an obstacle. Since there is no obstacle at (5,5), the state machine increments the column to 5 and goes to location (5,5). Since the state machine has already reached the destination column, it now compares the current row 5 with destination row 3 and checks if the following row location (5,4) has an obstacle. Since no obstacle exists at (5,4), the row is decremented to 4 and moves to the (5,4) location. Then, the state machine again compares the destination row 3 with current row 4, decrements the row to 3, and moves to (5,3), the destination location.
In my next blog, I will delve into the synthesis of the RTL Verilog code I've written, discussing the challenges I've encountered and how I've resolved them.
Week 11: Working with the Synthesis of the Verilog Code
Welcome back, everyone! Last week, I focused on synthesizing the Verilog code and generating a netlist that maps the logic elements/cells within FPGA, such as LUT (lookup table) and SLE (Sequential Logic Element or Flip Flop).
The synthesis tool, a crucial component in the Verilog code implementation process, takes the Verilog code (also known as the RTL code: Register Transfer Level code) for my path-finding algorithm as an input. It then produces the netlist, a digital circuit that connects various digital logic elements of an FPGA. In essence, the synthesis tool transforms the behavioral RTL code into a digital circuit that can be realized on an FPGA.
I set the target device as Microchip's PolarFire FPGA. I provided a clock constraint as 100MHz. The synthesis tool first gave me the an error: that my code had portions of logic within the "always" block, where I used both non-blocking and blocking statements. I intended to create the sequential logic. So, I converted all the blocking statements within the clocked "always" block into non-blocking statements. Going further, the synthesis tool gave an error that the "visitmap" array was updated in two different always blocks. I knew those were nonoverlapping statements because I was only initializing the "visitmap" in one "always" block and updating it in another "always" block where the state machine was coded. However, to resolve the issue indicated by the synthesis tool, I removed the initialization code of the "visitmap" from one "always" block and moved it to another "always" block where the state machine was coded. After making all these changes, I could synthesize the code successfully.
The tool generated the netlist with 126 SLE (sequential logic elements or Flip Flops) and 564 LUTs (Lookup tables). Each lookup table implements four input combinational functions. FPGAs do not have combinational gates such as AND, OR, NOT, NAND, or NOR. Instead, all the combinational logic is implemented in the LUTs (Lookup tables).
The timing analysis engine within the synthesis tool reported that the design could run at 110.7 MHz, faster than my original constraint. Within the 6x6 grid map that I took, for example, purposes, the algorithm can find the optimal path in 36 clock cycles in the worst case scenario. With a 110 MHz clock, it will take only 327 ns to find the optimal path. This demonstrates the clear advantage of hardware implementation, which is more deterministic and reliable than software implementation that relies on the operating system and system resource usage.
From the start of this project, my aim was to demonstrate the speed and suitability of the hardware implementation of the path-finding algorithm for a robot's real-time application. Now, this goal has been successfully achieved! Hope that my project was informative and interesting to engage with!