At the International Conference on Robotics and Automation, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) have presented a new lane-change algorithm that splits the difference. It allows for more aggressive lane changes than the simple models do but relies only on immediate information about other vehicles’ directions and velocities to make decisions.
One standard way for autonomous vehicles to avoid collisions is to calculate buffer zones around the other vehicles in the environment. The buffer zones describe not only the vehicles’ current positions but their likely future positions within some time frame. Planning lane changes then becomes a matter of simply staying out of other vehicles’ buffer zones.
For any given method of computing buffer zones, algorithm designers must prove that it guarantees collision avoidance, within the context of the mathematical model used to describe traffic patterns. That proof can be complex, so the optimal buffer zones are usually computed in advance. During operation, the autonomous vehicle then calls up the precomputed buffer zones that correspond to its situation.
The problem is that if traffic is fast enough and dense enough, precomputed buffer zones may be too restrictive. An autonomous vehicle will fail to change lanes at all, whereas a human driver would cheerfully zip around the roadway.
With the MIT researchers’ system, if the default buffer zones are leading to performance that’s far worse than a human driver’s, the system will compute new buffer zones on the fly — complete with proof of collision avoidance.
That approach depends on a mathematically efficient method of describing buffer zones, so that the collision-avoidance proof can be executed quickly. And that’s what the MIT researchers developed. They begin with a so-called Gaussian distribution — the familiar bell-curve probability distribution. That distribution represents the current position of the car, factoring in both its length and the uncertainty of its location estimation.
Then, based on estimates of the car’s direction and velocity, the researchers’ system constructs a so-called logistic function. Multiplying the logistic function by the Gaussian distribution skews the distribution in the direction of the car’s movement, with higher speeds increasing the skew.
The skewed distribution defines the vehicle’s new buffer zone. But its mathematical description is so simple — using only a few equation variables — that the system can evaluate it on the fly.
The researchers tested their algorithm in a simulation including up to 16 autonomous cars driving in an environment with several hundred other vehicles.
This project was supported, in part, by the Toyota Research Institute and the Office of Naval Research.