Robust Reward Placement under Uncertainty

Petros Petsinis, Kaichen Zhang, Andreas Pavlogiannis, Jingbo Zhou, Panagiotis Karras

Abstract

Optimizing facility locations in a network is challenging when agent mobility is uncertain. This paper introduces the Robust Reward Placement (RRP) problem, which aims to maximize the worst-case performance ratio across multiple Markov Mobility Models. We prove RRP is NP-hard and propose $\Psi$-Saturate, a bicriteria approximation algorithm that balances performance guarantees with budget constraints. Extensive evaluations on synthetic and real-world Baidu Map data demonstrate the effectiveness and scalability of our approach.

Introduction

Optimizing facility locations in a network is a critical task for urban planning and marketing. While historical data provides a baseline for movement patterns, real-world mobility is dynamic, influenced by factors like weather, holidays, or construction. A placement optimized for a sunny day might perform poorly during a storm.

Mobility patterns change significantly under different conditions (e.g., sunny vs. rainy weather), requiring robust placement strategies.

The Robust Reward Placement (RRP) problem addresses this uncertainty by modeling movement as a set of possible Markov Mobility Models (MMMs). The goal is to find a set of locations that performs well regardless of which scenario occurs. Specifically, the objective is to maximize the minimum ratio of collected reward to the optimal reward possible for each specific scenario, ensuring robustness across diverse conditions.

Methodology

RRP is established as both NP-hard and inapproximable within a constant factor in polynomial time. To overcome this, the researchers propose $\Psi$-Saturate, a bicriteria approximation algorithm. It uses binary search on the target ratio combined with a greedy selection process. It guarantees a solution within $\epsilon$ of the optimal ratio, provided the budget can be slightly exceeded (by a factor logarithmic in the number of mobility models).

Several baseline heuristics are compared:

  • All Greedy: Solves the problem for each model individually and picks the best resulting set.
  • Myopic: A standard greedy approach based on marginal gain.
  • Best-Worst Search (BWS): Specifically targets the worst-performing scenario.
  • DP-RRP: A dynamic programming approach adapted from the Max-Min Knapsack problem.

Experimental Evaluation

The algorithms were tested on synthetic networks (Erdős-Rényi and Scale-Free graphs) and real-world movement records from Baidu Map in Nanjing, China. The real-world dataset featured over 51,000 nodes and 13 distinct mobility graphs representing different weekly periods.

Key Results and Discussion

The experimental results highlight the trade-offs between solution quality and computational efficiency across different network topologies.

Scalability and execution time of various algorithms on Erdős-Rényi and Scale-Free networks.

Key findings include:

  • Performance: $\Psi$-Saturate consistently outperforms simple heuristics on random graphs. DP-RRP often finds the highest quality solutions but suffers from quadratic scaling, making it less suitable for very large state spaces.
  • Scalability: Most proposed algorithms, including $\Psi$-Saturate, scale linearly with the graph size, proving practical for city-scale applications.
  • Robustness Trends: The achievable robustness score generally decreases as the number of possible mobility models increases, reflecting the increased difficulty of satisfying an "adversarial" range of scenarios.

Conclusion

This work provides a robust framework for facility placement under mobility uncertainty. By focusing on the performance ratio rather than absolute rewards, the RRP model ensures fair treatment across scenarios with different inherent activity levels. Future research will explore optimizing the content of rewards to further influence agent behavior in these uncertain environments.

Summary updated

BibTeX
@inproceedings{petsinis2024robust,
  author = {Petros Petsinis and Kaichen Zhang and Andreas Pavlogiannis and Jingbo Zhou and Panagiotis Karras},
  title = {{Robust Reward Placement under Uncertainty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure