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!