Sequential Decision Making for Improving Efficiency in Urban Environments

Pradeep VarakanthamIJCAI 2016 · OpenReview

Abstract

Rapid "urbanization" (more than 50% of world's population now resides in cities) coupled with the natural lack of coordination in usage of common resources (ex: bikes, ambulances, taxis, traffic personnel, attractions) has a detrimental effect on a wide variety of response (ex: waiting times, response time for emergency needs) and coverage metrics (ex: predictability of traffic/security patrols) in cities of today. Motivated by the need to improve response and coverage metrics in urban environments, my research group is focussed on building intelligent agent systems that make sequential decisions to continuously match available supply of resources to an uncertain demand for resources. Our broad approach to generating these sequential decision strategies is through a combination of data analytics (to obtain a model) and multistage optimization (planning/scheduling) under uncertainty (to solve the model). While we perform data analytics, our contributions are focussed on multi-stage optimization under uncertainty. We exploit key properties of urban environments, namely homogeneity and anonymity, limited influence of individual entities, abstraction and near decomposability to solve "multi-stage optimization under uncertainty" effectively and efficiently.

Introduction

As the world rapidly urbanizes, cities struggle with a "lack of coordination" in common resources. Whether it’s a shortage of bikes at a specific station or long wait times for an ambulance, the core challenge is a mismatch between limited supply and unpredictable, dynamic demand. Traditional AI research in resource allocation often falls into categories that are insufficient for the complexity of modern metropolises—typically focusing on small-scale, deterministic, or purely cooperative/competitive environments.

Taxonomy of Urban Decision Making

Real cities are characterized as large-scale, stochastic (uncertain), and dynamic. Traditional models break down when trying to coordinate thousands of taxis or predict emergency calls across a metropolis. The research aims to bridge this gap by creating "intelligent agent systems" that make sequential decisions to match supply and demand in real-time.

Taxonomy of decision-making models in urban environments.

As illustrated in Figure 1, urban environments represent a unique challenge at the intersection of large-scale systems and stochastic, dynamic environments. While previous work has addressed deterministic or small-scale problems, the "Sequential Decision Making in Urban Environments" framework targets the high-complexity quadrant involving multi-stage matching, dynamic redeployment, and hybrid game-theoretic models.

Methodology

The framework utilizes a combination of data analytics to build predictive models and multi-stage optimization under uncertainty to solve them. The scalability of these solutions is achieved by exploiting four key properties of urban environments:

  1. Homogeneity and Anonymity: In a city, one taxi or bike is often functionally identical to another. By focusing on the number of resources in a zone rather than the identity of each individual agent, the complexity of the mathematical model is drastically reduced.
  2. Limited Influence: The actions of a single agent (e.g., a taxi driver) have a negligible impact on the overall city system, allowing for simplified modeling of individual behavior.
  3. Abstraction: Resources are grouped into abstract "supply components" to solve high-level problems before refining the operational details.
  4. Decomposability: Massive problems, such as city-wide bike sharing, are broken into nearly independent sub-problems, such as separating bike repositioning from the routing of the trucks that move them.

Technically, the system employs frameworks like Decentralized Markov Decision Processes (Dec-MDPs) for cooperative tasks and a hybrid of Stochastic Games and Congestion Games for competitive scenarios, such as selfish taxi drivers seeking fares.

Experimental Results

The research is grounded in extensive real-world datasets, including two years of taxi data from Singapore (~10,000 taxis), bike-sharing data, and emergency response records from major Asian cities. The proposed methods showed significant improvements over current industry practices:

  • Taxis: Sequential strategies yielded up to 90% of optimal solutions, compared to 60% for standard greedy approaches. Furthermore, selfish drivers saw an expected revenue increase of 40 SGD per day.
  • Emergency Response: The 80th percentile response time was reduced by at least 2 minutes across two different cities.
  • Bike Sharing: "Lost demand" (users unable to find a bike) was reduced by 22% to 45% compared to current repositioning practices.
  • Scalability: The speed of solving decentralized power restoration problems improved 30-fold.

Discussion and Future Work

While the results are promising, several challenges remain. The current models assume that human agents (like taxi drivers) will follow "equilibrium strategies" if they benefit individually, but real-world behavior can be more erratic. Additionally, while the methods are scalable, the computational complexity of multi-stage optimization remains high. Future work should also address cross-domain interaction, exploring how different urban systems (e.g., bike repositioning and ambulance routing) interact through shared infrastructure like traffic networks.

Summary updated

Abstract

Rapid "urbanization" (more than 50% of world's population now resides in cities) coupled with the natural lack of coordination in usage of common resources (ex: bikes, ambulances, taxis, traffic personnel, attractions) has a detrimental effect on a wide variety of response (ex: waiting times, response time for emergency needs) and coverage metrics (ex: predictability of traffic/security patrols) in cities of today. Motivated by the need to improve response and coverage metrics in urban environments, my research group is focussed on building intelligent agent systems that make sequential decisions to continuously match available supply of resources to an uncertain demand for resources. Our broad approach to generating these sequential decision strategies is through a combination of data analytics (to obtain a model) and multistage optimization (planning/scheduling) under uncertainty (to solve the model). While we perform data analytics, our contributions are focussed on multi-stage optimization under uncertainty. We exploit key properties of urban environments, namely homogeneity and anonymity, limited influence of individual entities, abstraction and near decomposability to solve "multi-stage optimization under uncertainty" effectively and efficiently.
BibTeX
@inproceedings{varakantham2016sequential,
  author = {Pradeep Varakantham},
  title = {{Sequential Decision Making for Improving Efficiency in Urban Environments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=ryWWg4z_Zr},
}
Figure