UC San Diego
Design and Analysis of Distributed Algorithms with Applications to Networked Traffic Systems
- Author(s): Gravelle, Evan
- Advisor(s): Martinez, Sonia
- et al.
There are many benefits of solving problems in a decentralized manner. Distributed algorithms often do not require global information which can alleviate the curse of dimensionality in large networks, there is often robustness to failure of parts, and they are often more robust to failure of parts, and to dynamic changes to the environment that can occur while maintaining performance. This dissertation will focus on three problems involving networked systems in which distributed algorithms have significant benefits: constrained load balancing, traffic congestion minimization, and traffic intersection efficiency.
Many physical limitations of real systems are not considered in the literature of distributed load balancing algorithms. We address the specific problem of quantized distributed load balancing over a network of agents subject to upper-limit constraints. We then shift focus to traffic systems, where endowing traffic control systems with local information and communication can be exploited for further efficiency. Motivated by a desire to reduce congestion, we propose two distributed algorithms to reduce delays: a dynamic lane reversal algorithm and a rerouting algorithm. Finally, we present a novel intersection control algorithm based on an objective function that accounts for drivers' time preferences.
For each problem, a specific objective is formed mathematically. An algorithm is designed to achieve this objective, and stability and convergence of the algorithms are analyzed. Experiments are run through simulation to verify stability and convergence as well as to test performance.