Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/64295D36-40C7-4CBA-AE96-99C14C3CD25C | ||
| Έτος | 2021 | ||
| Τύπος | Διπλωματική Εργασία | ||
| Άδεια Χρήσης |
|
||
| Βιβλιογραφική Αναφορά | Στέργιος Πλατανιώτης, "Αντιμετώπιση πολυπρακτορικής δρομολόγησης σε προβλήματα καθοδηγούμενου προσανατολισμού", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021 https://doi.org/10.26233/heallink.tuc.88952 | ||
| Εμφανίζεται στις Συλλογές |
Tο Πρόβλημα του Προσανατολισμού είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης, και αποτελεί γενίκευση του προβλήματος του πλανώδιου πωλητή. Μπορεί να αναπαρασταθεί σαν πρόβλημα εύρεσης μονοπατιού πάνω σε έναν γράφο, στον οποίο κάθε κόμβος συνδέεται με μία αμοιβή, ενώ η διάσχιση κάποιας ακμής με κάποιο κόστος. Γνωρίζοντας τον αρχικό και τον τελικό κόμβο, το ζητούμενο είναι η εύρεση ενός μονοπατιού που να τα συνδέει το οποίο μεγιστοποιεί τις συνολικές απολαβές (το "σκορ"), χωρίς την υπέρβαση ενός αρχικού προϋπολογισμού. Μπορεί να υπάρχουν και επιπλέον περιορισμοί, όπως κάποιο περαιτέρω κόστος για την επίσκεψη σε κάθε κόμβο, ή περιορισμοί σακιδίου. Καθώς το πρόβλημα είναι NP-hard, οι διάφορες παραλλαγές του αντιμετωπίζονται συνήθως με χρήση προσαρμοσμένων σε αυτές ευρετικών μεθόδων. Στην παρούσα εργασία, επεκτείνουμε αυτό το μοντέλο μετατρέποντάς το σε ένα πολυπρακτορικό πρόβλημα εύρεσης μονοπατιών, με την προσθήκη μιας "έκπτωσης αξίας" στη σχετιζόμενη με κάθε κόμβο αμοιβή, ανάλογα με τη συμφόρηση του εν λόγω κόμβου. Κατόπιν, αντιμετωπίζουμε το νέο αυτό πρόβλημα εφαρμόζοντας μεθόδους Τεχνητής Νοημοσύνης. Συγκεκριμένα, μοντελοποιούμε το πρόβλημα ως πολυπρακτορική Διαδικασία Αποφάσεων Markov καθώς και ως Μερικώς Παρατηρήσιμη Διαδικασία Αποφάσεων Markov, και το αντιμετωπίζουμε με τη χρήση μεθόδων πολυπρακτορικής ενισχυτικής μάθησης (multiagent reinforcement learning - MARL) και σχεδιασμού Monte-Carlo (με τον αλγόριθμο Partially Observable Monte Carlo Planning - POMCP) αντίστοιχα. Οι μέθοδοι MARL που χρησιμοποιούμε αξιοποιούν τον αλγόριθμο Sparse Cooperative Q-learning πάνω σε Συνεργατικούς Γράφους. Για τη λειτουργία του POMCP αλγορίθμου μας, μοντελοποιούμε τη συμφόρηση σε κάθε κόμβο ως αβεβαιότητα, και την αντιμετωπίζουμε με "φιλτράρισμα σωματιδίων". Συνολικά προτείνουμε έξι διαφορετικές αλγοριθμικές τεχνικές για την αντιμετώπιση του προβλήματος, και αξιολογούμε την απόδοσή τους πειραματικά με χρήση κατάλληλων προσομοιώσεων.
Copyright © DIAS 2013
