Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/64295D36-40C7-4CBA-AE96-99C14C3CD25C | ||
| Year | 2021 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Stergios Plataniotis, "Tackling multi-agent routing in an orienteering problem setting", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2021 https://doi.org/10.26233/heallink.tuc.88952 | ||
| Appears in Collections |
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.
Copyright © DIAS 2013
