Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/6FEFC5DC-E7CD-439E-8A37-E1DBD4D6E364 | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.83626 | - |
| Γλώσσα | en | - |
| Μέγεθος | 919,9 kilobytes | en |
| Τίτλος | Alternating policy iteration: an analysis and future directions | en |
| Τίτλος | Εναλλασσόμενη επανάληψη πολιτικής: μία ανάλυση και μελλοντικές κατευθύνσεις | el |
| Δημιουργός | Bacharis Athanasios | en |
| Δημιουργός | Μπαχαρης Αθανασιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Lagoudakis Michail | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Λαγουδακης Μιχαηλ | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Panagopoulos Athanasios-Aris | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Παναγόπουλος Αθανάσιος-Άρης | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Chalkiadakis Georgios | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Χαλκιαδακης Γεωργιος | el |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Εκδότης | Technical University of Crete | en |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περίληψη | 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 et al, 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. Finally, we provide a discussion on a possible AAAPI multi-agent extension. | en |
| Περίληψη | Οι Μαρκοβιανές Διαδικασίες Απόφασης (ΜΔΑ) αποτελούν ένα ισχυρό μαθηματικό μοντέλο για λήψη αποφάσεων υπό αβεβαιότητα. Έχουν εφαρμοστεί σε διάφορα επιστημονικά πεδία, όπως τα οικονομικά, η επιχειρησιακή έρευνα, η λήψη ιατρικών αποφάσεων, και η ρομποτική. Στη βάση της, η λύση μιας ΜΔΑ για την απόκτηση μίας βέλτιστης πολιτικής είναι υπολογιστικά ακριβή, και το πρόβλημα επιδεινώνεται στις μεγάλες διαστάσεις (δηλαδή σε μεγάλους χώρους κατάστασης-ενέργειας). Με βάση τα παραπάνω, έχει προταθεί στη βιβλιογραφία πληθώρα προσεγγιστικών μεθόδων για την αντιμετώπισης τη χωρικής και χρονικής πολυπλοκότητας υπολογισμού λύσεων ΜΔΑ. Μία ενδιαφέρουσα προσέγγιση προτάθηκε το 2015, από τους Παναγόπουλο-Χαλκιαδάκη-Jennings. Η εν λόγω προσέγγιση χρησιμοποιεί μία εναλλασσόμενη μέθοδο βελτιστοποίησης αποφάσεων σε υποχώρους κατάστασης-ενέργειας. Παρόλο που η ιδέα εργασίας σε υποχώρους λύσεων ενός προβλήματος βελτιστοποίησης δεν ήταν καινούργια, αυτός ο αλγόριθμος ήταν ίσως ο πρώτος που πρότεινε μία τέτοια προσέγγιση στα πλαίσια της ΜΔΑ. Η ίδια δημοσίευση επίσης αναδεικνύει την επιτυχία μίας τέτοιας προσέγγισης στο χειρισμό ενός φωτοβολταϊκού συστήματος παρακολούθησης ηλίου. Ωστόσο, η ίδια δημοσίευση δεν ξεκαθαρίζει πώς αυτός ο καινούργιος αλγόριθμος κλιμακώνεται σε σχέση με το μέγεθος του προβλήματος, ούτε πως συγκρίνεται με τις κλασσικές προσεγγίσεις επανάληψης πολιτικής και επανάληψης ανταμοιβής· και δε μπορεί να χρησιμοποιηθεί σε περιβάλλοντα τα οποία δεν αφήνουν την εκτέλεση των υπολογισμένων ενεργειών έπειτα από την βελτιστοποίηση στις διαχωρισμένες διαστάσεις. Το τελευταίο συνδέεται εννοιολογικά με καταστάσεις που έχουμε φαινόμενα “παραποίησης” (aliasing) πληροφορίας. Η παραποίηση πληροφορίας εμφανίζεται σε διάφορα επιστημονικά πεδία, όπως οι τηλεπικοινωνίες και η ρομποτική, και αντιστοιχεί στην απώλεια πληροφορίας έπειτα από τη μείωση των διαστάσεων ενός προβλήματος προκειμένου να προσεγγιστεί η λύση του. Ως εκ τούτου, σε αυτή τη διπλωματική εργασία παρουσιάζουμε μία νέα παραλλαγή του αλγορίθμου της εναλλασσόμενης επανάληψης πολιτικής που επιλύει τα προαναφερθέντα θέματα aliasing, και παρέχουμε συγκρίσεις με τους αλγορίθμους επανάληψης πολιτικής και επανάληψης ανταμοιβής. Δείχνουμε εμπειρικά ότι ο προτεινόμενος Aliasing Aware Alternating Policy Iteration (AAAPI) αλγόριθμός μας μπορεί να συγκλίνει στις βέλτιστες λύσεις (πολιτικές), με την παρουσία φαινομένων aliasing πληροφορίας. Επίσης, η υπολογιστική πολυπλοκότητα αυτού του αλγορίθμου είναι σε άμεση συσχέτιση με την ένταση της aliasing πληροφορίας. Σε περιβάλλοντα όπου τα φαινόμενα aliasing δεν είναι τόσο έντονα, ο AAAPI συγκλίνει γρηγορότερα σε σχέση με τις μεθόδους επανάληψης πολιτικής (policy iteration) και επανάληψης τιμών (value iteration)· αλλά σε περιβάλλοντα με υψηλό βαθμό aliasing πληροφορίας, όπως ο Λαβύρινθος, ο ρυθμός σύγκλισης του AAAPI πέφτει δραματικά και μπορεί να μη συγκλίνει στη βέλτιστη πολιτική. Μία επιπλέον συνεισφορά της εργασίας μας είναι η διατύπωση μία πιθανής επέκτασης του AAAPI σε πολυπρακτορικά περιβάλλοντα. | el |
| Τύπος | Διπλωματική Εργασία | el |
| Τύπος | Diploma Work | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2019-10-11 | - |
| Ημερομηνία Δημοσίευσης | 2019 | - |
| Θεματική Κατηγορία | Policy iteration | en |
| Θεματική Κατηγορία | Artificial intelligence | en |
| Θεματική Κατηγορία | Markov Decision Process | en |
| Θεματική Κατηγορία | Decision theoretic planning | en |
| Βιβλιογραφική Αναφορά | Αθανάσιος Μπαχάρης, "Εναλλασσόμενη επανάληψη πολιτικής: μία ανάλυση και μελλοντικές κατευθύνσεις", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2019 | el |
| Βιβλιογραφική Αναφορά | Athanasios Bacharis, "Alternating policy iteration: an analysis and future directions", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2019 | el |
Copyright © DIAS 2013
