PB*: Preference-Based Path-Planning for Autonomous Robots
Ayden Shankman (EE '23), Gavri Kepets (EE '23), and Netanel Fiorino (ME '23)
aydenshankman1@gmail.com, gkepets@gmail.com, netanelmf@gmail.com
Senior Capstone Project Advised by Professor Carl Sable, Professor Michelle Rosen, and Mike Giglia
Winner of The Best Interdisciplinary Project prize!
Project Abstract
Efficient travel for an autonomous robot requires a path-planning algorithm to determine the optimal path to take based on certain criteria. The most common criteria are speed, safety, and energy, as most autonomous robots are designed to operate in remote and/or difficult terrain where recharging, repair, or replacement is difficult or impossible. Most path-planning algorithms are catered toward specific robots, environments, or tasks, so the algorithms prioritize a static set of criteria, typically one or more of the three criteria previously listed. Many robots would benefit from having a path-planning algorithm that can dynamically prioritize a combination of the three criteria while also being generalizable to any type of autonomous robot. We present a novel path-planning algorithm, called PB*, that accounts for a robot's specifications, including its mass, dimensions, energy usage, and climbing abilities, and allows the user to set preferences for how much to prioritize speed, safety, and energy when calculating paths on any type of terrain. After running various tests, we demonstrated that PB* can provide accurate paths that respond appropriately to user inputs within a reasonable run-time.
What is Preference-Based Path-Planning for Autonomous Robots?
Autonomous robotics is a field of study that focuses on the development of robots that are able to operate independently of human control. Today, autonomous robots are used for a variety of applications, including industry, search and rescue, surveillance, and military operations. These robots require algorithms and systems that enable them to perceive their environment and make decisions based on gathered information. One of the most important tasks for a functional autonomous robot is path-planning. Path-planning is the task of finding the optimal path for a robot to follow between points in a defined space (often a physical space). Paths are considered optimal based on specific criteria; the most common path criteria for autonomous robots are speed, safety, and energy. Speed relates to how much time it takes for a robot to reach a destination, safety relates to how risk-averse or traversable a path is, and energy relates to the energy efficiency of the path.
However, the vast majority of path-planning algorithms are catered to very specific robots, environments, and tasks, so they are designed to only optimize for a static set of one or two of the three criteria mentioned. An example of such a path-planning algorithm is the one deployed on the Mars rovers known as Spirit, Opportunity, and Perseverance, which strictly prioritize safety when generating paths. Additionally, most path-planning algorithms are designed to account for the exact specifications and capabilities of a particular robot, such as its dimensions and battery capacity. However, if a robot's objective or specifications change, it is possible that the criteria or decision-making for its path-planning algorithm would need to change as well. For example, if a robot that usually prioritizes only safety when calculating paths suddenly becomes low on power, it may want to switch to prioritizing energy conservation when calculating new paths. To the best of our knowledge, there is currently no path-planning algorithm that allows for adjustable levels of prioritization of the three main criteria of speed, safety, and energy, and that is also generalizable to any type of autonomous robot.
We present a novel path-planning algorithm, called PB*, that addresses this issue. A user inputs various specifications of a robot, such as its mass, dimensions, energy usage, and climbing abilities. A function then converts point cloud data collected by a 3D LiDAR (also provided by the user) and converts it to a 2.5D height map, which is a 2D grid that represents a 3D surface or terrain by mapping the height and normals information to the surface to the grid (Figure. A probabilistic road map (PRM), which is a graph comprised of a set of randomly sampled points that are each connected to a fixed amount of their nearest neighbors, is then generated on top of the height map. The path-planning algorithm A* is then applied to calculate the optimal path from one point on the PRM to another, where the cost of each edge between two points is calculated based on the data from the underlying height map and the robot's specifications. Separate costs are calculated for speed, safety, and energy and individually weighted based on the user's specified preference. Finally, a check is done to determine if the edge is impossible for the robot to traverse, and if it is, a relatively high cost, denoted as the limitation cost, is added to the edge to ensure it is heavily avoided in the path-planning process.
To demonstrate PB*, we have created a program with a user interface (UI) that allows a user to input the various specifications of a robot mentioned previously, along with point cloud data from a 3D LiDAR. Following the user input, the program displays a 2.5D height map representing the surrounding terrain of the robot, which can be randomly generated for demonstration purposes or based on LiDAR data inputted by the user. The user can then input a start and goal location for the robot to navigate, as well as their preferences for speed, safety, and energy. The program then uses PB* to calculate the optimal path from the start point to the goal point and displays it on the height map for the user to see. Using the same height map, the user is able to change their speed, safety, and energy preferences, robot specifications, or start and goal locations to generate new paths, to see how each of these metrics may affect the generated path. PB* was also tested on terrain generated by readings from a physical 3D LiDAR to be evaluated within real-world environments.
Web UI
Below are images of our web UI. On the left is the map the user can test on, and on the right are options exposed to the user.
The user can specify their map preferences, graph preferences, optimization preferences, and robot configuration.
In order to evaluate the algorithm, various test cases were implemented in the web UI. The user can run tests with random maps, random robots, random preferences, and get the test results as a csv file.
Project Poster
