path planning
In warehouses, hospitals and manufacturing facilities all around the world, autonomous mobile robots (AMR) are asked to perform dynamic and complex tasks — often alongside their human coworkers. In order to navigate ever-changing environments safely and efficiently, robots need to know how to get from point A to point B without bumping into walls, equipment or people. And that starts with path planning.
There are four main elements to a navigation system for AMRs: sensors, data processing, mapping and path planning. Sensors are used to measure the position and orientation of the robot relative to its surroundings. Data processing is used to convert the raw data from the sensors into usable information. Mapping is used to create a representation of the robot’s surroundings. And finally, path planning is used to calculate the best route for the robot to take.
In this blog, we’ll focus on path planning: what it is, how it works and the most common algorithms used to navigate robots through complex environments.
path planning
What Is Robot Path Planning?
Simply, robot path planning is the process of finding a safe, efficient way to get from one location to another. This process takes into account the environment that the robot will be operating in, as well as any obstacles that might be in the way.
Path planning is crucial for AMRs. Poor planning can lead to mistakes, damage to the robot, or harm to the people and objects around it. By using a planning algorithm, AMRs can safely and efficiently navigate unpredictable spaces.
How Does Robot Path Planning Work?
There are a number of different algorithms that can be used for robot path planning, but they all have a common goal: to find the shortest path from a robot’s starting position (or pose) to its goal position.
Mapping the space. In order to determine the most efficient path through a space, first a robot must be given or “implicitly build a mapped representation of their surrounding space.”
Simultaneous localization and mapping (SLAM) is one method used for AMRs that lets you build a map and localize your robot in that map at the same time.
path planning
Robotic path planning. Once the area has been mapped out in a grid or a graph, the robot needs to understand how to move from its beginning pose to its goal quickly and efficiently. That’s where path planning algorithms come into play. In its video tutorial on path planning, MATLAB describes it like this:
“Graph-based algorithms work by discretizing the environment. That is, breaking it up into discrete points or nodes and then finding the shortest distance to the goal considering only these nodes.”
Keep in mind, path planning only dictates where the robot moves (the path it takes from start to goal). AMRs use path planning combined with motion planning (how the robot moves) to navigate and avoid unpredictable obstacles.
Common Path Planning Algorithms
There are two common categories of graph-based path planning algorithms: Search-based and sampling-based.
Search-based algorithms. Search-based (or searching) algorithms work by gradually exploring potential paths and then choosing the one that offers the shortest and most efficient path between start and goal, taking into account any obstacles that may be in the way.
You can think of this searching method as a tree. The algorithm creates branches by adding nodes in an ordered pattern, computing the numerical cost of each edge (or straight line) between nodes. The path with the smallest number (or cost) is the one the robot will ultimately take to reach its goal.
Search-based algorithms are efficient and powerful but they do have drawbacks. They tend to be resource-intensive, meaning it takes “a large amount of space to store all possible paths and a lot of time to find them.”
For this reason, search-based algorithms are less efficient for use in large spaces with more complex landscapes.
A*, a popular and widely used search-based algorithm, was developed in 1968 for the world’s first mobile intelligent robot, Shakey.
Sampling-based algorithms. Sampling-based algorithms select (sample) nodes randomly and then connect them to the nearest node in the tree. The tree branches out, sampling the environment until it determines the optimum path to reach the goal.
Sampling-based algorithms can typically find a path even in large graphed environments. However, they may be slower and may not be able to come up with the most efficient path.
Rapidly-exploring random trees (RRT) is a sampling-based algorithm developed in 1998 to quickly grow the tree from the start point until it reaches the goal. RRT* starts with RTT but then attempts to improve the path by grafting new branches onto existing ones.
path planning
Recent Developments: Machine Learning
Both sampling and searching algorithms are graph-based, meaning they rely on graphing the area and solving the start to goal problem numerically.
Recent developments in path planning leverage the power of AI to figure out the best way to navigate through complex environments, especially those with unpredictable obstacles. Machine learning algorithms can analyze data to find patterns and trends in the environment and efficiently generate the optimal path between start and goal.
Through reinforcement learning algorithms and deep learning, robots can adapt their behavior as they receive feedback from the environment and make predictions about the best way to navigate. Machine learning has opened up new opportunities to teach robots how to avoid unpredictable obstacles and react in real time in ever-changing environments.
Final Thoughts
Today’s AMRs are asked to navigate larger, more complex environments — often with unpredictable obstacles. Without a clear path to follow, AMRs would be unable to safely, efficiently complete these tasks.
Path planning is an evolving science that — when combined with sensors, data processing and mapping — is a powerful tool that enables robots to work alongside humans in dynamic environments.
