Abstract
Our increasingly interconnected urban environments provide several opportunities to deploy intelligent agents—from self-driving cars and ships to aerial drones—that promise to radically improve productivity and safety. Achieving coordination among agents in such urban settings presents several algorithmic challenges: the ability to scale to thousands of agents, addressing uncertainty, and partial observability in the environment. In addition, accurate domain models need to be learned from data that is often noisy and available only at an aggregate level. In this paper, I will overview some of our recent contributions towards developing planning and reinforcement learning strategies to address several such challenges present in large-scale urban multiagent systems.
Introduction
As autonomous systems like drones, self-driving taxis, and automated maritime vessels become more prevalent, we face a massive coordination challenge. The standard mathematical framework for this, the Decentralized Partially Observable Markov Decision Process (Dec-POMDP), is notoriously difficult to solve. In fact, it is "NEXP-Hard," meaning even a system with just two agents can be computationally overwhelming.
In a real city, we don't have two agents; we have thousands. Furthermore, we rarely have perfect data on every single individual due to privacy concerns or sensing costs. Instead, we often only see aggregate data (e.g., "there are 50 cars on this road segment," rather than "Car A is at GPS coordinate X"). This research addresses the gap between theoretical multiagent models and the practical, large-scale, aggregate-data reality of urban systems.
Shifting to Collective Modeling
The core of this work is a shift from individual-based modeling to Collective Multiagent Decision Making. By focusing on aggregate population counts rather than individual agent identities—a concept called "partial exchangeability"—the complexity of the problem no longer grows exponentially with the number of agents. In many urban settings, the specific identity of an agent matters less than the total number of agents performing a certain action in a specific location.
Technical Framework
The proposed framework utilizes several key technical components:
- Collective Graphical Models (CGMs): These models describe the distribution of aggregate statistics. Instead of tracking every car, CGMs track "count tables"—how many entities moved from point A to point B.
- CDec-POMDP (Collective Dec-POMDP): A new framework that combines Dec-POMDPs with the principle of collective modeling. It treats count tables as "sufficient statistics" for planning, meaning no critical information is lost by ignoring individual IDs.
- Planning-as-Inference: Coordination is treated as a "likelihood maximization" problem. By using Expectation-Maximization (EM), the system can utilize message-passing algorithms that are highly scalable.
- Lifted Multiagent RL (MARL): Traditional Reinforcement Learning requires sampling individual trajectories, which is prohibitively expensive for thousands of agents. "Lifted" RL works directly with count-based representations, making the learning process independent of the actual population size.
Real-World Applications and Results
The research validates these models using historical data from various urban domains:
- Maritime Traffic: Using Electronic Navigation Charts (ENC) and vessel movement data from the Singapore Straits to model traffic separation schemes.
- Urban Road Traffic: Using vehicle counts from inductive-loop detectors to estimate turn probabilities.
- Taxi Fleet Data: Optimizing supply-demand matching in large cities.
Key results include massive scalability, with algorithms coordinating thousands of agents where previous solvers were limited to dozens. Furthermore, the aggregate models were shown to accurately replicate historical patterns, proving that collective modeling is sufficient for high-stakes urban management.
Conclusion and Future Work
While the collective approach is highly effective for homogeneous populations, future work will address challenges in systems with highly heterogeneous agents. Additionally, further research is needed to improve multiagent credit assignment in purely count-based environments and to develop RL strategies that can handle the high variance inherent in large-scale urban feedback loops.
Summary updated