Ultrafast Motion-Planning Chip Could Make Autonomous Cars Safer
Realtime Robotics’ motion-planning processor helps autonomous cars make better decisions
About two years ago, we covered a research project from Duke University that sped up motion planning for a tabletop robot arm by several orders of magnitude. The robot relied on a custom processor to do in milliseconds what normally takes seconds. The Duke researchers formed a company based on this tech called Realtime Robotics, and recently they’ve been focused on applying it to autonomous vehicles.
The reason that you should care about fast motion planning for autonomous vehicles is because motion planning encompasses the process by which the vehicle decides what it’s going to do next. Making this process faster doesn’t just mean that the vehicle can make decisions more quickly, but that it can make much better decisions as well—keeping you, and everyone around you, as safe as possible.
Here’s the problem: Navigating through an inherently unpredictable world involves a substantial amount of computers trying to guess what humans are going to do next. Computers are pretty good at this, especially in semi-structured environments like on roads. Most of them use what are called probabilistic models to predict what nondeterministic objects (things that have some independent agency) will do. For example, most models would probably agree that a car that’s in front of you on the highway has a high probability of continuing to drive at about the same speed while staying in its lane. It has a somewhat lower probability of changing lanes without signalling, and an even lower probability of suddenly braking.
Most autonomous driving systems plan motions based on their model’s most probable scenario for what the objects around them will do. These models can provide a confidence level and the system can slow the vehicle down if it’s not sure what’s going to happen, but it’s still planning just for one scenario at a time, as opposed to considering all possible actions that a vehicle could take (even the improbable ones) and making a motion plan that keeps the vehicle in the optimal position to handle even the things that only might happen. Unlike most autonomous driving systems that can only manage a single motion plan at a time at a rate of between 3 Hz and 10 Hz, Realtime Robotics can run through tens or even hundreds of motion plans while spending less than 1 millisecond computing each—a rate of 1,000 Hz. This allows the system to consider far more potential outcomes in far less time to arrive at the best decision possible.
Realtime Robotics’ motion-planning system for vehicles begins with a lattice—an enormous precomputed graph consisting of all the different trajectories that the vehicle could take in an obstacle-free environment. It does that for a time horizon of between 5 and 10 seconds. The lattice consists of nodes and edges: Nodes are specific vehicle configurations (position, velocity, heading), while edges connect nodes and represent the trajectory between those configurations over about 1 second’s worth of travel time for the vehicle. There are tens of millions of edges in the lattice, reflecting all the different possible transitions between configuration states through the entire time horizon that the lattice covers. Each edge comes with a cost that represents things like fuel usage or passenger comfort, and the lowest cost edges imply more efficient, gentle motion.
Example of a lattice, with the blue boxes representing the vehicle as it traverses the lattice edges.
The motion plan that you get out of Realtime Robotics’ system is just about as good as the motion plan you’d get out of any other system. The difference is that it has delivered the plan between one and two orders of magnitude faster, meaning it can circle back and run the whole planning again to generate better decisions.
[Originally posted by IEEE SPECTRUM — May 16, 2019]