Motion Planning vs Path Planning
Imagine you’re building the next big autonomous vehicle. During the phase when testing the car’s ability to travel from one point to another, the car scans its environment and maps out the best way to get its dummy passenger from the starting position to the desired destination. Is this the process of motion planning? Or path planning?
At first glance the two terms can be mistaken to mean the same thing. They are sometimes even used interchangeably in robotics. This misconception may be partially due to the fact that they both answer some aspect of the question ‘how does my robot get from point A to point B?’ In the autonomous car scenario, we were dealing with path planning because the car was planning the path it would take, and not planning how it would execute on that path, which would be motion planning.
Path planning and motion planning are two separate processes in robotics and both must be tackled on the way to achieving a fully functioning robot. Let’s examine each of them separately and then consider how they interact.
Path Planning
By its robotics definition, path planning is the process you use to construct a path from a starting point to an ending point given a full, partial, or dynamic map. Essentially, you are calculating out a path on a particular terrain that is the shortest or fastest for a robot to navigate while also avoiding obstacles.
When you think of path planning you are answering questions like ‘which direction is your robot moving in?’, ‘where is the next step?’, and ‘how can I reach the destination with this barrier in my way?’
To present you with a simple example, the path planning process for these humanoid robots that are capable of navigating a rough terrain of cinder blocks is as follows: the robots have a defined starting and ending point between which they map out all possible paths, footstep by footstep, then evaluate the cost of each and finally determine the best one to take.
There are some important considerations that go into planning out a path, namely
- is the environment that we’re working with dynamic? (do we have unknown or moving obstacles?)
- how will we map out and model the environment? does the robot have SLAM (simultaneous localization and mapping) capabilities?
- can we compute a path on the fly if necessary?
- do we need our path to optimize certain factors such as time, energy, or safety?
Once we have an idea of our environment and constraints for a path, there are various algorithms we can choose from to help us determine how a robot will navigate through a space with either known or unknown obstacles while avoiding collisions. Sampling Based Planning is a probabilistically complete method which uses randomization to construct a graph or tree (roadmap) in C-space (configuration space in which each point represents a particular configuration/placement of the robot) on which queries may be solved. Algorithms like Dijkstra’s and A* can also be applied to these roadmaps to find the most efficient paths, and each has its own variations, benefits, and drawbacks depending on the heuristics set by the programmer. Accordingly, each algorithm and set of constraints may give you a different outcome. But whichever algorithm you end up using, the final product in your path planning process is the same: a well-defined path along a map that your robot will eventually follow… but not before you plan its motion along that path.
Motion Planning
When we have a path for a robot to take we need to determine how to execute on that path. Motion planning is the process by which you define the set of actions that you need to execute to follow the path you planned. During this process you enable your robot to move by answering questions like ‘how do I make the motors move forward?’, ‘what type of sensors do I use?’, and ‘what type of wheel do I need?’ among many others.
The considerations for motion planning can start out simple when working with less complex robots, like TurtleBot, in less complex environments, like flat surfaces with minimal obstacles. We consider things such as the speed at which we want the robot to move, if we need to speed up or slow down, how to approach a change in direction, etc.
As we increase the complexity of the robot we also increase its potential capabilities. This can be observed in the increasingly popular humanoid robots which can jump, flip, navigate more complex terrains, etc. But with these added capabilities motion planning needs to consider more than just speed. We factor in discussions about whether our robot might jump over an obstacle instead of turning to avoid it, what the most efficient ways are to execute these motions, whether our robot is designed well enough and can move in a way that it remains balanced in less stable environments where perhaps we have a lot of wind or pressure or a narrow, suspended path. These never-ending considerations all factor into our robots’ integral motion plan.
There are even more fundamental things to consider as motion planning is something that is inherently dynamic meaning it is always changing depending on certain factors such as
- the current location of the robot
- how much the robot has already moved
- whether the environment has changed
A motion plan might change several times throughout the course of a robots’ path and motion in order to adjust to any of these factors.
Additionally, motion planning is not strictly related to a robots’ movement along a path. It also means figuring out how to make a robot grab and even manipulate objects. This connects to another process called grasp planning which involves its own elements of motion. Things become complicated in stationary robots like robotic arms whose job it is to grab and manipulate objects. Here, the motion and grasp planning involves an understanding of the mechanics of contact with an object. For example, in planning how to grab an object, the robot needs to know how many fingers to place around it and exactly where to place those fingers in order to successfully grab and move it. In planning how to push an object, the robot needs to be able to predict whether the object will slide smoothly or fall over in order to exert the correct force for the desired motion of the object. As you can see, the list of considerations in motion planning just keeps growing.
So how is motion planning actually executed? Similar to path planning there are various algorithms and schemes we use to generate a motion plan for a robot. The typical motion planning process includes activating a robots’ controller which continuously reads from sensors like motor encoders, force sensors, vision sensors, or depth sensors, and updates the actuator commands to achieve a robots’ desired behavior. Model Predictive Control is a common motion planning scheme which uses a model to predict the future behavior of a system, anticipating future disturbances while considering constraints, and incorporates this information into the control problem to improve performance. Beyond this, there are some widely used open-source packages for motion planning such as PickNik’s MoveIt which supports development in motion planning, manipulation, 3D perception, kinematics, control, and navigation mainly for robotic arms, and DexNet which focuses on grasp planning using various techniques.
Environment
To further illustrate the differences between these two processes let’s consider a humanoid robot in two vastly different environments. The first is a tall hedge maze and the second is a thin tightrope suspended hundreds of feet in the air.
In the maze, motion planning is relatively simple. We know the robot must move forward, turn to change direction, and keeping moving forward to progress through the maze whether that be on wheels or feet. However, path planning in the maze is difficult if the robot is not supplied with a map detailing every turn and dead end. The robot can’t see the entire maze to compute a most efficient path or even just past the path that lies directly ahead of it. The robot cannot plan its path before it starts the maze. Instead, it will have to compute on the fly, similar to these pasta shaped soft robots which harvest their energy from heat and change direction instantly when they come in contact with an obstacle, actually requiring no human input to escape maze-like environments.
Conversely, on the tightrope it is the motion planning that is more difficult. The robot is on an unbalanced surface with many factors affecting its motion. Each “step” the robot takes is subject to a wobble and potentially a lethal fall. So do you make the robot execute a motion different than a human-like walk? Do you make it somehow crawl? Or hang on like Tarzan and hope for the best? Luckily in this case the path planning is simple as we are just navigating a straight line.
As you can see, path planning and motion planning are not one and the same. Each process undertakes the planning of different parts of a robots journey and each plan can be wildly different depending on the robots’ design and environment.
Another, more relatable example is found in cars. In a car the GPS takes care of the path planning by taking in a starting point and a destination and mapping out the fastest route between the two, then delivering commands to the controller, whether that be a driver or the car itself, such as when to turn. The motion planning is the actual driving. The user examines and follows the planned route while observing traffic signals and obstacles like pedestrians, controls the speed of the car to obey traffic laws, and changes lanes and adjusts speed to avoid hitting obstacles which all results in the motion of the car.
Interplay
Though path planning and motion planning are decidedly different processes, they do involve some overlap. We began this article by mentioning that both path and motion planning answer some aspect of ‘how is my robot getting from point A to point B?’ We now can break that question down and say that path planning addresses the spatial aspect of this inquiry while motion planning addresses the mechanical components. Combined, they give us a complete procedure for getting a robot from one point in space to another.
Further, when these processes interact they can influence each other. Normally in robotics we solve the navigation problem using path planning then apply motion planning on top. In this way path planning expands into motion planning because the path factors into trajectories for all the robots’ joints which are then expanded into commands for the robots’ motors. This doesn’t mean path planning happens once and never again after motion commences. In fact, a robots’ current motion can influence the path planning and the path might have to be adjusted on the fly. For example if a car was driving at a high speed and suddenly needed to turn, it might not be feasible to initiate a sudden change in velocity even if that was necessary to stay on the shortest or fastest path. Instead we might adjust to take the next best path.
Complex Computation: Engaging the Cloud
As modern robots address real-world problems in dynamic environments, computation for path and motion planning becomes much more complex. Along with innovation come challenges related to increased needs for flexibility and autonomy in motion and task execution. For example, take an autonomous car: when mapping its dynamic environment we need to determine if objects are moving (like other cars driving), whether we need to know exactly what a specific object is (human vs. inanimate object), and whether an abject can change from inanimate to dynamic (like a previously parked car that is leaving its parking spot). Today, an adequate algorithm must handle these complex requirements with high-level mapping and motion strategies which demand higher-level computation and require more energy, storage, hardware, etc. and accordingly come at a much higher cost.
This is where the cloud comes in to save the day. By offloading the execution of these computationally intensive algorithms to the cloud we can achieve a better quality robot while simultaneously reducing infrastructure costs. Computation offloading tackles limitations of robots such as limited processing capabilities and limited storage capacity by offloading the execution and workload to other rich systems with better performance and resources.
Computation offloading tackles limitations of robot hardware such as limited processing capabilities and limited storage capacity by offloading the execution and workload to other rich systems with better performance and resources. With the growing 5G network and sustainable connections, streaming data to the cloud is becoming more feasible and advantageous. Moving the likes of path and motion planning computation to the cloud enables us to minimize the hardware requirements that drive up costs in robotics.
What Have You Learned Today?
Path planning and motion planning are two distinct robotics processes. Though often used interchangeably because they deal with the overarching process of a robots’ journey through space, the two terms have their own meanings.
Path planning helps robots map out a path as straight as possible from point A to B while avoiding obstacles instead of leaving it meandering in circles. Motion planning establishes the exact actions a robot must execute to follow a predetermined path and reach its goal. When properly implemented, the two processes contribute to an accurate, quality robot.
