Open Access. Powered by Scholars. Published by Universities.®
Operations Research, Systems Engineering and Industrial Engineering Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering
Direct: A Scalable Approach For Route Guidance In Selfish Orienteering Problems, Pradeep Varakantham, Hala Mostafa, Na Fu, Hoong Chuin Lau
Direct: A Scalable Approach For Route Guidance In Selfish Orienteering Problems, Pradeep Varakantham, Hala Mostafa, Na Fu, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
We address the problem of crowd congestion at venues like theme parks, museums and world expos by providing route guidance to multiple selfish users (with budget constraints) moving through the venue simultaneously. To represent these settings, we introduce the Selfish Orienteering Problem (SeOP) that combines two well studied problems from literature, namely Orienteering Problem (OP) and Selfish Routing (SR). OP is a single agent routing problem where the goal is to minimize latency (or maximize reward) in traversing a subset of nodes while respecting budget constraints. SR is a game between selfish agents looking for minimum latency routes from source …
Streets: Game-Theoretic Traffic Patrolling With Exploration And Exploitation, Matthew Brown, Sandhya Saisubramanian, Pradeep Varakantham, Milind Tambe
Streets: Game-Theoretic Traffic Patrolling With Exploration And Exploitation, Matthew Brown, Sandhya Saisubramanian, Pradeep Varakantham, Milind Tambe
Research Collection School Of Computing and Information Systems
To dissuade reckless driving and mitigate accidents, cities deploy resources to patrol roads. In this paper, we present STREETS, an application developed for the city of Singapore, which models the problem of computing randomized traffic patrol strategies as a defenderattacker Stackelberg game. Previous work on Stackelberg security games has focused extensively on counterterrorism settings. STREETS moves beyond counterterrorism and represents the first use of Stackelberg games for traffic patrolling, in the process providing a novel algorithm for solving such games that addresses three major challenges in modeling and scale-up. First, there exists a high degree of unpredictability in travel times …
Sampled Fictitious Play For Multi-Action Stochastic Dynamic Programs, Archis Ghate, Shih-Fen Cheng, Stephen Baumert, Daniel Reaume, Dushyant Sharma, Robert L. Smith
Sampled Fictitious Play For Multi-Action Stochastic Dynamic Programs, Archis Ghate, Shih-Fen Cheng, Stephen Baumert, Daniel Reaume, Dushyant Sharma, Robert L. Smith
Research Collection School Of Computing and Information Systems
We introduce a class of finite-horizon dynamic optimization problems that we call multi-action stochastic dynamic programs (DPs). Their distinguishing feature is that the decision in each state is a multi-dimensional vector. These problems can in principle be solved using Bellman's backward recursion. However, complexity of this procedure grows exponentially in the dimension of the decision vectors. This is called the curse of action-space dimensionality. To overcome this computational challenge, we propose an approximation algorithm rooted in the game theoretic paradigm of Sampled Fictitious Play (SFP). SFP solves a sequence of DPs with a one-dimensional action-space, which are exponentially smaller than …