• Home
  • News
  • Algorithm helps autonomous vehicles navigate...

News Story

Algorithm helps autonomous vehicles navigate common tricky traffic situations

news story image

Figure 2 from the paper: Demonstrating GAMEPLAN with Human Drivers: In the top row, the driver of the white vehicle is aggressive while the driver of the black vehicle is conservative. GAMEPLAN computes a turn-based ordering that determines the black agent should yield to the white vehicle, which would pass first. The bottom row illustrates a similar scenario without game-theoretic planning. Both drivers are unsure of who should move first. In this case, both the white and silver agents stop and after a delay of 8 seconds, the more aggressive driver in the white vehicle moves first, followed by the silver vehicle.

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 first, 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 traffic auction, each driver “bids” on whether to move or wait based on a specific strategy, meant to be acceptable to each driver. The auction most familiar to drivers is called “first-in-first-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 first 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 first.

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