Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Algorithm Design for Safe and Efficient Societal-Scale Navigation

Abstract

In modern urban centers, traffic networks increasingly experience higher densities of both human-operated and self-driving vehicles. Unfortunately, high traffic loads can increase the likelihood of accidents and gridlock at individual intersections and roads, and produce societal-scale externalities in the form of pollution and excessive commute times. To address these issues, modern navigation and transportation technologies increasingly leverage machine learning-enabled components to safely and efficiently guide commuters towards their desired destinations. Examples range from learning-enabled perception and motion planning algorithms deployed on self-driving vehicles, to recommendation systems for route planning in large-scale transportation networks. Unfortunately, learning-based algorithms can exhibit unexpected and alarming behavior when deployed in real-world environments. For instance, computer vision modules in self-driving vehicles frequently fail to correctly identify traffic signs and predict pedestrian motion, with fatal consequences. Meanwhile, route recommendation platforms can induce high congestion levels, by directing self-interested travelers to overcrowd paths of least perceived latency. These phenomena highlight that, despite their promise, modern ML algorithms for localized and societal-scale navigation remain unable to operate robustly in real-world traffic scenarios.

To overcome these challenges, this thesis draws from tools in control theory, estimation theory, numerical optimization, game theory, and mechanism design to design algorithms that ensure safe and efficient navigation in modern transportation systems. In particular, the thesis consists of the following parts, each of which targets a different facet of decision making in traffic navigation: (I) A unified optimization-based state estimation algorithm for autonomous agents; (II) Game-theoretic motion planners that characterize multi-agent interactions in local traffic scenarios; (III) A dynamic tolling scheme and learning updates for large traffic networks. We conclude by describing promising avenues of future work.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View