Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Tackling multi-agent routing in an orienteering problem setting

Plataniotis Stergios

Full record

---

Summary

The Orienteering Problem is a combinatorial optimization problem which constitutes a generalization of the Travelling Salesman Problem. It can be presented as a graph, in which each node is associated with a reward, while each edge is associated with a cost. With the starting and ending nodes fixed, one has to find a path that maximizes the cumulative reward (or "score"), while maintaining a budget. There may also be more limitations, such as an extra cost of visiting each node or knapsack constraints. Such problems are usually solved via heuristics because of their NP-hard complexity. To this end, we extend this competitive setting to a multi-agent routing problem with the addition of congestion-related discounts, and take advantage of Artificial Intelligence methods to address it. Specifically, we model our extended problem in two different ways—i.e., as a multi-agent Markov Decision Process (MDP), and as Partially Observable MDP (POMDP); and employ multi-agent Reinforcement Learning (MARL) and Partially Observable Monte Carlo Planning (POMCP), respectively, to find good solutions. Our MARL solution employs a Coordination Graph communication format and the Sparse Cooperative Q-learning algorithm. For our POMCP algorithm, we model congestion as uncertainty countered by belief-particle filtering. Overall, we put forward six different algorithmic variants to tackle this problem, and provide an analysis of their performance via experimental simulations.

Available Files

Services