Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/64295D36-40C7-4CBA-AE96-99C14C3CD25C | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.88952 | - |
| Language | en | - |
| Extent | 4.9 megabytes | en |
| Extent | 85 pages | en |
| Title | Tackling multi-agent routing in an orienteering problem setting | en |
| Title | Αντιμετώπιση πολυπρακτορικής δρομολόγησης σε προβλήματα καθοδηγούμενου προσανατολισμού | el |
| Creator | Plataniotis Stergios | en |
| Creator | Πλατανιωτης Στεργιος | el |
| Contributor [Thesis Supervisor] | Chalkiadakis Georgios | en |
| Contributor [Thesis Supervisor] | Χαλκιαδακης Γεωργιος | el |
| Contributor [Committee Member] | Lagoudakis Michail | en |
| Contributor [Committee Member] | Λαγουδακης Μιχαηλ | el |
| Contributor [Committee Member] | Deligiannakis Antonios | en |
| Contributor [Committee Member] | Δεληγιαννακης Αντωνιος | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content 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. | en |
| Content Summary | Tο Πρόβλημα του Προσανατολισμού είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης, και αποτελεί γενίκευση του προβλήματος του πλανώδιου πωλητή. Μπορεί να αναπαρασταθεί σαν πρόβλημα εύρεσης μονοπατιού πάνω σε έναν γράφο, στον οποίο κάθε κόμβος συνδέεται με μία αμοιβή, ενώ η διάσχιση κάποιας ακμής με κάποιο κόστος. Γνωρίζοντας τον αρχικό και τον τελικό κόμβο, το ζητούμενο είναι η εύρεση ενός μονοπατιού που να τα συνδέει το οποίο μεγιστοποιεί τις συνολικές απολαβές (το "σκορ"), χωρίς την υπέρβαση ενός αρχικού προϋπολογισμού. Μπορεί να υπάρχουν και επιπλέον περιορισμοί, όπως κάποιο περαιτέρω κόστος για την επίσκεψη σε κάθε κόμβο, ή περιορισμοί σακιδίου. Καθώς το πρόβλημα είναι NP-hard, οι διάφορες παραλλαγές του αντιμετωπίζονται συνήθως με χρήση προσαρμοσμένων σε αυτές ευρετικών μεθόδων. Στην παρούσα εργασία, επεκτείνουμε αυτό το μοντέλο μετατρέποντάς το σε ένα πολυπρακτορικό πρόβλημα εύρεσης μονοπατιών, με την προσθήκη μιας "έκπτωσης αξίας" στη σχετιζόμενη με κάθε κόμβο αμοιβή, ανάλογα με τη συμφόρηση του εν λόγω κόμβου. Κατόπιν, αντιμετωπίζουμε το νέο αυτό πρόβλημα εφαρμόζοντας μεθόδους Τεχνητής Νοημοσύνης. Συγκεκριμένα, μοντελοποιούμε το πρόβλημα ως πολυπρακτορική Διαδικασία Αποφάσεων Markov καθώς και ως Μερικώς Παρατηρήσιμη Διαδικασία Αποφάσεων Markov, και το αντιμετωπίζουμε με τη χρήση μεθόδων πολυπρακτορικής ενισχυτικής μάθησης (multiagent reinforcement learning - MARL) και σχεδιασμού Monte-Carlo (με τον αλγόριθμο Partially Observable Monte Carlo Planning - POMCP) αντίστοιχα. Οι μέθοδοι MARL που χρησιμοποιούμε αξιοποιούν τον αλγόριθμο Sparse Cooperative Q-learning πάνω σε Συνεργατικούς Γράφους. Για τη λειτουργία του POMCP αλγορίθμου μας, μοντελοποιούμε τη συμφόρηση σε κάθε κόμβο ως αβεβαιότητα, και την αντιμετωπίζουμε με "φιλτράρισμα σωματιδίων". Συνολικά προτείνουμε έξι διαφορετικές αλγοριθμικές τεχνικές για την αντιμετώπιση του προβλήματος, και αξιολογούμε την απόδοσή τους πειραματικά με χρήση κατάλληλων προσομοιώσεων. | el |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2021-04-20 | - |
| Date of Publication | 2021 | - |
| Subject | Orienteering problem | en |
| Subject | Reinforcement learning | en |
| Subject | Artificial intelligence | en |
| 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 | en |
| Bibliographic Citation | Στέργιος Πλατανιώτης, "Αντιμετώπιση πολυπρακτορικής δρομολόγησης σε προβλήματα καθοδηγούμενου προσανατολισμού", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021 | el |
Copyright © DIAS 2013
