Multi-agent reinforcement learning methods for congestion problem
Φόρτωση...
Ημερομηνία
Συγγραφείς
Σπαθάρης, Χρήστος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Multi-agent systems can be used to address problems in a variety of domains, including robotics, telecommunications, congestion avoidance and distributed control. Reinforcement learning framework can provide a robust and natural way for agents to learn how to coordinate their action options in multi-agent systems. The objective of this thesis is to propose and investigate the use of Collaborative Multi-Agent Reinforcement Learning methods for autonomous agents for resolving congestion problems. Such problems require the investigation of a joint policy in order to maximize a pay-off function. Agents have limited information about others pay offs and preferences, and need to coordinate their action to achieve their tasks while adhering to operational constraints.We study three different Multi-Agent Reinforcement learning methodologies: the independent case, the edge-based case and the agent-based case. We have applied these schemes to an interesting traffic application: solving the demand-capacity imbalances during pre-tactical phase in Air Traffic domain. Several experiments have been made based on real-world data and the results obtained confirm the effectiveness of our methods in resolving the demand-capacity problem.
Η παρούσα εργασία πραγματεύεται τον τρόπο επίλυσης προβλημάτων συμφόρης στο εναέριο δίκτυο με χρήση μεθόδων πολυπρακτορικής ενισχυτικής μάθησης. Πιο συγκεκριμένα, οι πράκτορες του δικτύου μας ανταποκρίνονται σε αεροσκάφη που πραγματοποιούν προκαθορισμένες διαδρομές και σκοπός τους είναι να εκτελέσουν ομαλά τη διαδρομή τους δίχως να δημιουργήσουν πρόβλημα στον εναέριο χώρο. Ο εναέριος χώρος, χωρίζεται σε εναέρια μπλοκ ή τομείς και κάθε τομέας έχει μια προκαθορισμένη τιμή Χωρητικότητας την οποία δεν πρέπει να υπερβεί σε καμία χρονική στιγμή. Αυτό το πρόβλημα, είναι γνωστό και ως Ανισορροπία μεταξύ Ζήτησης-Χωρητικότητας και σκοπός μας σε αυτή την εργασία είναι η εύρεση της βέλτιστης κοινής πολιτικής των πρακτόρων ώστε να αποφευχθούν οι συμφορήσεις στον εναέριο χώρο. Η Ζήτηση είναι η ποσότητα που μετράει πόσα αεροσκάφη διανύουν ή πρόκειται να διανύσουν έναν συγκεκριμένο εναέριο τομέα σε μια συγκεκριμένη χρονική στιγμή. Συνεπώς, όταν η τιμή της Ζήτησης ξεπεράσει την τιμή της Χωρητικότητας, τότε πλέον υπάρχει ανισορροπία μεταξύ των δύο ποσοτήτων και δημιουργείται ένα σημείο συμφόρησης στον τομέα. Η λύση του προβλήματος εντοπίζεται στην υπαγωγή των αεροσκαφών που προκαλούν τη συμφόρηση σε κάποιους κανονισμούς λειτουργίας. Στην περίπτωση μας αυτοι οι κανονισμοίλειτουργίας μεταφράζονται σε λεπτά καθυστέρησης. Στην εργασία μας, μελετάμε την επιβολή καθυστερήσεων στα αεροσκάφη κατα τη διάρκεια της ”προ-τακτικής” φασής. Η συγκεγκριμένη φάση λαμβάνει χώρα αρκετές μέρες πριν την πτήση των αεροσκαφων και περιλαμβανει την επιβολή καθυστερήσεων σε αεροσκάφη που επρόκειτο να δημιουργήσουν πρόβλημα στον εναέριο χώρο κατά τη μέρα αναχώρησής τους. Παράλληλα, κατά την επιβολή καθυστερήσεων χρήζει προσοχής το γεγονός ότι κάθε λεπτό καθυστέρησης κοστίζει στην αντίστοιχη εταιρεία κάποιο χρηματικό ποσό για τον δεδομένο τύπο αεροσκάφους. Στην προσέγγισή μας, χρησιμοποιήσαμε μεθόδους πολυπρακτορικής ενισχυτικής μάθησης στην οποία οι πράκτορες συνεργάζονται μεταξύ τους για την επίλυση του κοινου προβλήματος. Υλοποιήσαμε τρεις διαφορετικές μεθόδους οι οποίες επιτυγχάνουν διαφορετικές λύσεις του προβλήματος. Επιπλέον, αξίζει να σημιεωθεί ότι τα πειράματα έγιναν πάνω σε πραγματικά δεδομένα χιλιάδων πτήσεων που προσέφερε το πρόγραμμα DART. Οι μέθοδοί μας βασίζονται στην εύρεση βέλτισης κοινής πολιτικής η οποία ορίζει για τον κάθε πράκτορα αν πρέπει να καθυστερήσει την αναχώρησή του από το αεροδρόμιο ή αν είναι ελεύθερος να πετάξει με ασφάλεια. Στόχος της εργασίαςείναι να βρούμε αυτή την πολιτική η οποία να εξαλοίφει πλήρως τους τομείς συμφόρησης ενώ παράλληλα να μειώνει τα λεπτά καθυστέρησης και το συνολικό κόσος, όσο το δυνατόν περισσότερο.
Η παρούσα εργασία πραγματεύεται τον τρόπο επίλυσης προβλημάτων συμφόρης στο εναέριο δίκτυο με χρήση μεθόδων πολυπρακτορικής ενισχυτικής μάθησης. Πιο συγκεκριμένα, οι πράκτορες του δικτύου μας ανταποκρίνονται σε αεροσκάφη που πραγματοποιούν προκαθορισμένες διαδρομές και σκοπός τους είναι να εκτελέσουν ομαλά τη διαδρομή τους δίχως να δημιουργήσουν πρόβλημα στον εναέριο χώρο. Ο εναέριος χώρος, χωρίζεται σε εναέρια μπλοκ ή τομείς και κάθε τομέας έχει μια προκαθορισμένη τιμή Χωρητικότητας την οποία δεν πρέπει να υπερβεί σε καμία χρονική στιγμή. Αυτό το πρόβλημα, είναι γνωστό και ως Ανισορροπία μεταξύ Ζήτησης-Χωρητικότητας και σκοπός μας σε αυτή την εργασία είναι η εύρεση της βέλτιστης κοινής πολιτικής των πρακτόρων ώστε να αποφευχθούν οι συμφορήσεις στον εναέριο χώρο. Η Ζήτηση είναι η ποσότητα που μετράει πόσα αεροσκάφη διανύουν ή πρόκειται να διανύσουν έναν συγκεκριμένο εναέριο τομέα σε μια συγκεκριμένη χρονική στιγμή. Συνεπώς, όταν η τιμή της Ζήτησης ξεπεράσει την τιμή της Χωρητικότητας, τότε πλέον υπάρχει ανισορροπία μεταξύ των δύο ποσοτήτων και δημιουργείται ένα σημείο συμφόρησης στον τομέα. Η λύση του προβλήματος εντοπίζεται στην υπαγωγή των αεροσκαφών που προκαλούν τη συμφόρηση σε κάποιους κανονισμούς λειτουργίας. Στην περίπτωση μας αυτοι οι κανονισμοίλειτουργίας μεταφράζονται σε λεπτά καθυστέρησης. Στην εργασία μας, μελετάμε την επιβολή καθυστερήσεων στα αεροσκάφη κατα τη διάρκεια της ”προ-τακτικής” φασής. Η συγκεγκριμένη φάση λαμβάνει χώρα αρκετές μέρες πριν την πτήση των αεροσκαφων και περιλαμβανει την επιβολή καθυστερήσεων σε αεροσκάφη που επρόκειτο να δημιουργήσουν πρόβλημα στον εναέριο χώρο κατά τη μέρα αναχώρησής τους. Παράλληλα, κατά την επιβολή καθυστερήσεων χρήζει προσοχής το γεγονός ότι κάθε λεπτό καθυστέρησης κοστίζει στην αντίστοιχη εταιρεία κάποιο χρηματικό ποσό για τον δεδομένο τύπο αεροσκάφους. Στην προσέγγισή μας, χρησιμοποιήσαμε μεθόδους πολυπρακτορικής ενισχυτικής μάθησης στην οποία οι πράκτορες συνεργάζονται μεταξύ τους για την επίλυση του κοινου προβλήματος. Υλοποιήσαμε τρεις διαφορετικές μεθόδους οι οποίες επιτυγχάνουν διαφορετικές λύσεις του προβλήματος. Επιπλέον, αξίζει να σημιεωθεί ότι τα πειράματα έγιναν πάνω σε πραγματικά δεδομένα χιλιάδων πτήσεων που προσέφερε το πρόγραμμα DART. Οι μέθοδοί μας βασίζονται στην εύρεση βέλτισης κοινής πολιτικής η οποία ορίζει για τον κάθε πράκτορα αν πρέπει να καθυστερήσει την αναχώρησή του από το αεροδρόμιο ή αν είναι ελεύθερος να πετάξει με ασφάλεια. Στόχος της εργασίαςείναι να βρούμε αυτή την πολιτική η οποία να εξαλοίφει πλήρως τους τομείς συμφόρησης ενώ παράλληλα να μειώνει τα λεπτά καθυστέρησης και το συνολικό κόσος, όσο το δυνατόν περισσότερο.
Περιγραφή
Λέξεις-κλειδιά
Machine learning, Reinforcement learning, Μulti-agent systems, Congestion problems, Μηχανική μάθηση, Ενισχυτική μάθηση, Πολυπρακτορικά συστήματα, Προβλήματα συμφόρησης
Θεματική κατηγορία
Machine learning
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Μπλέκας, Κωνσταντίνος
Εξεταστική επιτροπή
Μπλέκας, Κωνσταντίνος
Λαγαρής, Ισαάκ
Λύκας, Αριστείδης
Λαγαρής, Ισαάκ
Λύκας, Αριστείδης
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 50-52
Ονόματα συντελεστών
Αριθμός σελίδων
52 σ.