Fast, Smooth, and Reliable: How Robots are Becoming More Efficient with Motion Planning
Imagine you have a robot that bags your groceries at the supermarket. Let’s say it wants to load your favorite box of peanut butter cups from the grocery belt into your shopping bag. It needs to decide how to grasp the box and quickly put it into the bag while making sure to avoid hitting the cash register or anyone else nearby! This is exactly what motion planning is - the process of finding an optimal path from an initial robot configuration (e.g., the current pose or state of the robot) to a goal robot configuration while avoiding obstacles.
In robotics today, two common approaches to motion planning are: sampling-based and optimization-based.
Sampling-based approaches generate random samples of robot configurations and only retain the ones that are not in collision with obstacles. This includes methods such as Probabilistic Roadmap (PRM), Rapidly-exploring Random Graph (RRG) and Rapidly-exploring Random Tree (RRT). In the supermarket robot example, we would remove any configurations colliding with a person or item from the set of valid configurations. Then, the motion planner connects neighboring configurations with collision-free segments and searches for a path from the initial configuration to the goal. The robot would then typically select the path with the shortest length and compute the motion time along the path (i.e., time parameterization), determined by the robot’s capabilities. Sampling-based methods can find a solution quickly and are often probabilistically complete (given enough time, they are guaranteed to find a solution if it exists), which are the main reasons they are used by many of the existing motion planning frameworks. However, the shortest length path doesn’t always correspond to the fastest path.
In contrast, optimization-based methods, such as TrajOpt, STOMP and CHOMP, leverage prior information about the environment and the robot as constraints to compute a fast and collision-free path. This approach has been proven very effective for solving complex problems such as finding a fast, collision-free path while limiting the jerk in the motions. Jerk is the time derivative of acceleration and a lower jerk means the robot moves more smoothly, reliably, and efficiently. High jerk, on the other hand, can cause wear and tear on the robot, and reduce its overall working life. The downside of these fast, low-jerk optimization-based approaches though, is that they can take much longer to find trajectories, and may get stuck in a local optimum.
To summarize, sampling-based methods require less compute time but can output more time-consuming paths, while optimization-based methods find faster trajectories but can require longer compute times.
That leads us to the question - can we develop algorithms that minimize both execution and compute time?
It turns out it is possible! This paper for example, published in Science Robotics, presents a method to compute a time-optimized trajectory within just ~80 milliseconds. It uses a Sequential Quadratic Program (SQP) to compute a time-optimized, jerk-limited, and collision-free trajectory. To address the high compute times, a neural network computes an approximated solution to warmstart the SQP optimizer. The warmstart allows the SQP to start from a solution much closer to the final solution, reducing the number of optimization iterations. Since the final solution is outputted from the SQP, this guarantees that the trajectory meets the jerk and robot constraints, which the neural network on its own cannot guarantee.
This rapid computation of smooth, fast robot trajectories is particularly important for applications such as robot picking in e-commerce warehouses.
The Jacobi platform took this approach a step further. With a combination of optimization, deep learning, and motion-planning tools, it computes faster motions within less than 1 millisecond on average. You just choose your robot from the robot library, load your collision environment, train the motion planner, and you’re ready to use time-optimized, jerk-limited, and collision-free trajectories.
Mallika Parulekar is an undergraduate student at the AUTOLab, in the University of California, Berkeley, and is interested in robotics, algorithms, machine learning and game theory.
Blog overview