Publication Type

Journal Article

Version

acceptedVersion

Publication Date

10-2014

Abstract

In this paper, we formulate and study the Multi-agent Orienteering Problem with Time-dependent Capacity Constraints (MOPTCC). MOPTCC is similar to the classical orienteering problem at single-agent level: given a limited time budget, an agent travels around the network and collects rewards by visiting different nodes, with the objective of maximizing the sum of his collected rewards. The most important feature we introduce in MOPTCC is the inclusion of multiple competing agents. All agents in MOPTCC are assumed to be self-interested, and they interact with each other when arrive at certain nodes simultaneously. As all nodes are capacitated, if a particular node receives more agents than its capacity, all agents at that node will be made to wait and agents suffer as a result (in terms of extra time needed for queueing). Due to the decentralized nature of the problem, MOPTCC cannot be solved in a centralized manner, instead, we need to seek out equilibrium solutions, and if not possible, at least approximated equilibrium solutions. The major contribution of this paper is the formulation of the problem, and our first attempt in identifying an efficient and effective equilibrium-seeking procedure for MOPTCC.

Keywords

Multi-agent orienteering problem, sampled fictitious play

Discipline

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

Research Areas

Intelligent Systems and Optimization

Publication

Web Intelligence and Agent Systems

Volume

12

Issue

4

First Page

347

Last Page

358

ISSN

1570-1263

Identifier

10.3233/WIA-140304

Publisher

IOS Press

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.3233/WIA-140304

Download

Share

COinS