Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2015

Abstract

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 to destination along edges of a network available to all agents. Thus, SeOP is a multi-agent planning problem where agents have selfish interests and individual budget constraints. As with Selfish Routing, we employ Nash Equilibrium as the solution concept in solving SeOP. A direct mathematical program formulation to find a Nash equilibrium in SeOP cannot scale because the number of constraints is quadratic in the number of paths, which itself is an exponential quantity. To address scalability issues, we make two key contributions. First, we provide a compact non-pairwise formulation with linear number of constraints in the number of paths to enforce the equilibrium condition. Second, we introduce DIRECT, an incremental and iterative master-slave decomposition approach to compute an approximate equilibrium solution. Similar to existing flow based approaches, DIRECT is scale invariant in the number of agents. We also provide a theoretical discussion of our approximation quality and present extensive empirical results on synthetic and real-world graphs demonstrating the scalability of combining DIRECT with our non-pairwise formulation.

Keywords

Leisure and Entertainment, Decision Support, game theory

Discipline

Artificial Intelligence and Robotics | Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering

Publication

AAMAS '15: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems: 4-8 May, Istanbul

First Page

483

Last Page

491

Publisher

AAMAS

City or Country

Richland, SC

Additional URL

http://dl.acm.org/citation.cfm?id=2772942

Download

Share

COinS