Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
5-2016
Abstract
We study the problem of optimizing the trajectories of agents moving over a network given their preferences over which nodes to visit subject to operational constraints on the network. In our running example, a theme park manager optimizes which attractions to include in a day-pass to maximize the pass’s appeal to visitors while keeping operational costs within budget. The first challenge in this combinatorial optimization problem is that it involves quantities (expected visit frequencies of each attraction) that cannot be expressed analytically, for which we use the Sample Average Approximation. The second challenge is that while sampling is typically done prior to optimization, the dependence of our sampling distribution on decision variables couples optimization and sampling. Our main contribution is a mathematical program that simultaneously optimizes decision variables and implements inverse transform sampling from the distribution they induce. The third challenge is the limited scalability of the monolithic mathematical program. We present a dual decomposition approach that exploits independence among samples and demonstrate better scalability compared to the monolithic formulation in different settings.
Keywords
Budget control, Combinatorial optimization, Decision making, Inverse transforms, Mathematical transformations, Multi agent systems, Optimization, Sampling, Scalability
Discipline
Artificial Intelligence and Robotics | Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Intelligent Systems and Optimization
Publication
Autonomous agents and multiagent systems: AAMAS 2016 Workshops, visionary papers, Singapore, May 9-10
First Page
50
Last Page
66
ISBN
9783319468396
Identifier
10.1007/978-3-319-46840-2_4
Publisher
Springer Verlag
City or Country
Cham
Citation
MOSTAFA, Hala; Akshat KUMAR; and LAU, Hoong Chuin.
Simultaneous optimization and sampling of agent trajectories over a network. (2016). Autonomous agents and multiagent systems: AAMAS 2016 Workshops, visionary papers, Singapore, May 9-10. 50-66.
Available at: https://ink.library.smu.edu.sg/sis_research/3367
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1007/978-3-319-46840-2_4
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons