Multi-agent orienteering problem with time-dependent capacity constraints

Article type: Research Article

Authors: Chen, Cen | Cheng, Shih-Fen^; | Lau, Hoong Chuin

Affiliations: School of Information Systems, Singapore Management University, Singapore. E-mail: {cenchen.2012,sfcheng,hclau}@smu.edu.sg

Note: [] Corresponding author.

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 the 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 and interacting agents. All agents in MOPTCC are assumed to be self-interested, and they interact with each other when arrive at the same 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 collectively 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 this is 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

DOI: 10.3233/WIA-140304

Journal: Web Intelligence and Agent Systems: An International Journal, vol. 12, no. 4, pp. 347-358, 2014