Συντάχθηκε 07-10-2019 11:27
Ενημερώθηκε:
07-10-2019 11:52
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΜΠΑΧΑΡΗΣ ΑΘΑΝΑΣΙΟΣ
με θέμα
Εναλλασσόμενη Επανάληψη Πολιτικής: Μία Ανάλυση και Μελλοντικές Κατευθύνσεις
Alternating Policy Iteration: An analysis and Future Directions
Τρίτη 8 Οκτώβρη 2019, 8 μ.μ.Αίθουσα 141.A141 (Intelligence),
Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης
Επίκουρος Καθηγητής Αθανάσιος Άρης Παναγόπουλος (CS, California State University)
Περίληψη
Οι Μαρκοβιανές Διαδικασίες Απόφασης (ΜΔΑ) αποτελούν ένα ισχυρό μαθηματικό μοντέλο για λήψη αποφάσεων υπό αβεβαιότητα. Έχουν εφαρμοστεί σε διάφορα επιστημονικά πεδία, όπως τα οικονομικά, η επιχειρησιακή έρευνα, η λήψη ιατρικών αποφάσεων, και η ρομποτική. Στη βάση της, η λύση μιας ΜΔΑ για την απόκτηση μίας βέλτιστης πολιτικής είναι υπολογιστικά ακριβή, και το πρόβλημα επιδεινώνεται στις μεγάλες διαστάσεις (δηλαδή σε μεγάλους χώρους κατάστασης-ενέργειας). Με βάση τα παραπάνω, έχει προταθεί στη βιβλιογραφία πληθώρα προσεγγιστικών μεθόδων για την αντιμετώπισης τη χωρικής και χρονικής πολυπλοκότητας υπολογισμού λύσεων ΜΔΑ.
Μία ενδιαφέρουσα προσέγγιση προτάθηκε το 2015, από τους Παναγόπουλο-Χαλκιαδάκη-Jennings. Η εν λόγω προσέγγιση χρησιμοποιεί μία εναλλασσόμενη μέθοδο βελτιστοποίησης αποφάσεων σε υποχώρους κατάστασης-ενέργειας. Παρόλο που η ιδέα εργασίας σε υποχώρους λύσεων ενός προβλήματος βελτιστοποίησης δεν ήταν καινούργια, αυτός ο αλγόριθμος ήταν ίσως ο πρώτος που πρότεινε μία τέτοια προσέγγιση στα πλαίσια της ΜΔΑ. Η ίδια δημοσίευση επίσης αναδεικνύει την επιτυχία μίας τέτοιας προσέγγισης στο χειρισμό ενός φωτοβολταϊκού συστήματος παρακολούθησης ηλίου. Ωστόσο, η ίδια δημοσίευση δεν ξεκαθαρίζει πώς αυτός ο καινούργιος αλγόριθμος κλιμακώνεται σε σχέση με το μέγεθος του προβλήματος, ούτε πως συγκρίνεται με τις κλασσικές προσεγγίσεις επανάληψης πολιτικής και επανάληψης ανταμοιβής· και δε μπορεί να χρησιμοποιηθεί σε περιβάλλοντα τα οποία δεν αφήνουν την εκτέλεση των υπολογισμένων ενεργειών έπειτα από την βελτιστοποίηση στις διαχωρισμένες διαστάσεις. Το τελευταίο συνδέεται εννοιολογικά με καταστάσεις που έχουμε φαινόμενα “παραποίησης” (aliasing) πληροφορίας. Η παραποίηση πληροφορίας εμφανίζεται σε διάφορα επιστημονικά πεδία, όπως οι τηλεπικοινωνίες και η ρομποτική, και αντιστοιχεί στην απώλεια πληροφορίας έπειτα από τη μείωση των διαστάσεων ενός προβλήματος προκειμένου να προσεγγιστεί η λύση του.
Ως εκ τούτου, σε αυτή τη διπλωματική εργασία παρουσιάζουμε μία νέα παραλλαγή του αλγορίθμου της εναλλασσόμενης επανάληψης πολιτικής που επιλύει τα προαναφερθέντα θέματα aliasing, και παρέχουμε συγκρίσεις με τους αλγορίθμους επανάληψης πολιτικής και επανάληψης ανταμοιβής. Δείχνουμε εμπειρικά ότι ο προτεινόμενος Aliasing Aware Alternating Policy Iteration (AAAPI) αλγόριθμός μας μπορεί να συγκλίνει στις βέλτιστες λύσεις (πολιτικές), με την παρουσία φαινομένων aliasing πληροφορίας. Επίσης, η υπολογιστική πολυπλοκότητα αυτού του αλγορίθμου είναι σε άμεση συσχέτιση με την ένταση της aliasing πληροφορίας. Σε περιβάλλοντα όπου τα φαινόμενα aliasing δεν είναι τόσο έντονα, ο AAAPI συγκλίνει γρηγορότερα σε σχέση με τις μεθόδους επανάληψης πολιτικής (policy iteration) και επανάληψης τιμών (value iteration)· αλλά σε περιβάλλοντα με υψηλό βαθμό aliasing πληροφορίας, όπως ο Λαβύρινθος, ο ρυθμός σύγκλισης του AAAPI πέφτει δραματικά και μπορεί να μη συγκλίνει στη βέλτιστη πολιτική. Μία επιπλέον συνεισφορά της εργασίας μας είναι η διατύπωση μία πιθανής επέκτασης του AAAPI σε πολυπρακτορικά περιβάλλοντα.
Abstract
Markov Decision Processes (MDPs) constitute a powerful mathematical model for decision making under uncertainty. They have been used widely in a number of application areas such as economics, operation research, health care and robotics. In their fundamental form, solving an MDP to derive its optimal policy is computationally expensive, and the problem is only exacerbated in its high dimensions (i.e., in large state-action spaces). To this end, a number of approximate solution methods have been proposed over time, tackling time and space complexity in various ways.
An interesting approach has been proposed in 2015, by Panagopoulos etal, that utilizes an iterative optimization method to optimize over state-action sub-spaces. Although the idea of iteratively optimizing over sub-spaces, is not new in optimization theory, this algorithm was perhaps the first to propose such an approach in the context of MDPs. The same paper also illustrates the success of such an approach in controlling a solar tracking system. Nevertheless, that work does not illustrate clearly how this new algorithm scales along with problem size, nor how it compares with typical policy iteration or value iteration approaches; and could not be used in environments that do not allow the execution of the actions computed after optimization in each separate dimensions. Intuitively, this corresponds to situations where we have information aliasing phenomena. Information aliasing is a concept which appears in many scientific fields, such as telecommunications and robotics, and describes the loss of information due to dimensionality reduction.
As such, in this thesis we provide a novel variant of the alternating policy iteration algorithm that resolves the aforementioned aliasing issues, and provide a comparison with policy iteration and value iteration. We show empirically that Aliasing Aware Alternating Policy Iteration (AAAPI) can converge to the optimal solutions (policies), in the presence of information aliasing phenomena. Also, the computational complexity of this algorithm is directly related to the intensity of information aliasing. In environments where information aliasing is not intense, AAAPI converges faster than policy iteration and value iteration; but in high-aliasing environments like the maze-grid, the AAAPI convergence rate is substantially reduced and it might also not converge to the optimal policy. Finally, we provide a discussion on a possible AAAPI multi-agent extension.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 141Α-14, Αίθουσα Εργαστηρίου Intelligence, Πολυτεχνειούπολη
Έναρξη: 08/10/2019 20:00
Λήξη: 08/10/2019 21:00
