Algorithm helps autonomous vehicles navigate common tricky traffic situations
As autonomous vehicle (AV) development accelerates, artificial intelligence (AI) is evolving to deal with common situations on the road. Many considerations involving traffic safety need to be addressed for AVs to be incorporated into real-life driving. Some of the most ubiquitous of these involve decision making in traffic merging, at unsignaled intersections, and in roundabouts.
Navigating these dangerous scenarios is challenging—for both humans and AVs. Bad decisions at intersections are responsible for 40% of all crashes, 50% of serious collisions, and 20% of driving-related fatalities. Because drivers do not know what other drivers are going to choose, it is hard to coordinate actions. Picture the common scenario of two drivers arriving together at a four-way, unsignaled intersection. Sometimes both drivers decide to take the initiative to move ﬁrst, potentially resulting in a collision. Or both drivers may sit and wait for the other to make the first move.
ISR-affiliated Distinguished University Professor Dinesh Manocha (ECE/CS/UMIACS) and his Ph.D. student Rohan Chandra have developed a new AI framework, GamePlan: Game-Theoretic Multi-Agent Planning with Human Drivers at Intersections, Roundabouts, and Merging, that can help AVs address these situations. GAMEPLAN models the real-life challenge of predicting the actions both of other AVs and especially of human drivers, whose intentions are unknown.
How GAMEPLAN works
Within AI, the field of game theory uses a mechanism called “auctions” for these scenarios. In a trafﬁc auction, each driver “bids” on whether to move or wait based on a speciﬁc strategy, meant to be acceptable to each driver. The auction most familiar to drivers is called “ﬁrst-in-ﬁrst-out,” in which the bidding strategy is based who arrived at the intersection first. Auctions can produce collision- and deadlock-free navigation policies without requiring a lot of data. But auctions don’t work so well when aggressive drivers ignore the convention, move first regardless, and put themselves and other drivers in jeopardy. AVs need to be able to navigate safely in these situations.
In GAMEPLAN, the authors provide the ﬁrst formal analysis of how navigation works in these challenging scenarios. They then develop a robotics-based algorithmic auction framework for AVs. The framework uses data obtained from GPS, depth cameras, LIDAR and other sensors to understand the trajectories and velocities of other vehicles in the situation. It then infers driver behaviors like aggressiveness and impatience.
GAMEPLAN next uses these assumptions to directly determine a driver’s likely strategy in a traffic auction. Finally, GAMEPLAN instructs the AV to follow an optimal turn-based ordering in which more aggressive or impatient drivers move ﬁrst.
Although counter-intuitive, this approach is game-theoretically optimal and successfully prevents collisions and deadlocks with human drivers in the real world. In four-way intersections, GAMEPLAN is shown to reduce the number of collisions and deadlocks by up to 30% over prior methods. The paper also includes demonstrations of GAMEPLAN’s usefulness in merging scenarios that involve real human drivers.
Published September 21, 2021