CMU Researchers Develop Algorithm to Help Autonomous Vehicles Navigate Busy Streets

It is a scenario familiar to anyone who has driven down a crowded, narrow street. Parked cars line both sides, and there isn't enough space for vehicles traveling in both directions to pass each other. One has to duck into a gap in the parked cars or slow and pull over as far as possible for the other to squeeze by.

Drivers find a way to negotiate this, but not without close calls and frustration. Programming an autonomous vehicle (AV) to do the same — without a human behind the wheel or knowledge of what the other driver might do — presented a unique challenge for researchers at the Carnegie Mellon University Argo AI Center for Autonomous Vehicle Research.

"It's the unwritten rules of the road, that's pretty much what we're dealing with here," said Christoph Killing, a former visiting research scholar in the School of Computer Science's Robotics Institute and now part of the Autonomous Aerial Systems Lab at the Technical University of Munich. "It's a difficult bit. You have to learn to negotiate this scenario without knowing if the other vehicle is going to stop or go."

While at CMU, Killing teamed up with research scientist John Dolan and Ph.D. student Adam Villaflor to crack this problem. The team presented its research, "Learning To Robustly Negotiate Bi-Directional Lane Usage in High-Conflict Driving Scenarios," at the International Conference on Robotics and Automation (ICRA).

CMU algorithm anticipates others' behavior

The team said it believes its research is the first into this specific driving scenario. It requires drivers — human or not — to collaborate to make it past each other safely without knowing what the other is thinking.

Drivers must balance aggression with cooperation. An overly aggressive driver, one that just goes without regard for other vehicles, could put itself and others at risk. An overly cooperative driver, one that always pulls over in the face of oncoming traffic, may never make it down the street.

"I have always found this to be an interesting and sometimes difficult aspect of driving in Pittsburgh," Dolan said.

Autonomous vehicles have been heralded as a potential solution to the last-mile challenges of delivery and transportation. But for an AV or robot to deliver a pizza, package or person to their destination, they have to be able to navigate tight spaces and unknown driver intentions.

The team developed a method to model different levels of driver cooperativeness — how likely a driver was to pull over to let the other driver pass — and used those models to train an algorithm that could assist an autonomous vehicle to safely and efficiently navigate this situation. The algorithm has only been used in simulation and not on a vehicle in the real world, but the results are promising. The team found that their algorithm performed better than current models.

Driving is full of complex scenarios like this one. As the autonomous driving researchers tackle them, they look for ways to make the algorithms and models developed for one scenario, say merging onto a highway, work for other scenarios, like changing lanes or making a left turn against traffic at an intersection.

"Extensive testing is bringing to light the last percent of touch cases," Dolan said. "We keep finding these corner cases and keep coming up with ways to handle them."

About the author

Aaron Aupperlee is senior director of media relations at Carnegie Mellon University's School of Computer Science.