Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/6FEFC5DC-E7CD-439E-8A37-E1DBD4D6E364 | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.83626 | - |
| Language | en | - |
| Extent | 919,9 kilobytes | en |
| Title | Alternating policy iteration: an analysis and future directions | en |
| Title | Εναλλασσόμενη επανάληψη πολιτικής: μία ανάλυση και μελλοντικές κατευθύνσεις | el |
| Creator | Bacharis Athanasios | en |
| Creator | Μπαχαρης Αθανασιος | el |
| Contributor [Committee Member] | Lagoudakis Michail | en |
| Contributor [Committee Member] | Λαγουδακης Μιχαηλ | el |
| Contributor [Committee Member] | Panagopoulos Athanasios-Aris | en |
| Contributor [Committee Member] | Παναγόπουλος Αθανάσιος-Άρης | el |
| Contributor [Thesis Supervisor] | Chalkiadakis Georgios | en |
| Contributor [Thesis Supervisor] | Χαλκιαδακης Γεωργιος | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content Summary | 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 |
| Content Summary | Οι Μαρκοβιανές Διαδικασίες Απόφασης (ΜΔΑ) αποτελούν ένα ισχυρό μαθηματικό μοντέλο για λήψη αποφάσεων υπό αβεβαιότητα. Έχουν εφαρμοστεί σε διάφορα επιστημονικά πεδία, όπως τα οικονομικά, η επιχειρησιακή έρευνα, η λήψη ιατρικών αποφάσεων, και η ρομποτική. Στη βάση της, η λύση μιας ΜΔΑ για την απόκτηση μίας βέλτιστης πολιτικής είναι υπολογιστικά ακριβή, και το πρόβλημα επιδεινώνεται στις μεγάλες διαστάσεις (δηλαδή σε μεγάλους χώρους κατάστασης-ενέργειας). Με βάση τα παραπάνω, έχει προταθεί στη βιβλιογραφία πληθώρα προσεγγιστικών μεθόδων για την αντιμετώπισης τη χωρικής και χρονικής πολυπλοκότητας υπολογισμού λύσεων ΜΔΑ. Μία ενδιαφέρουσα προσέγγιση προτάθηκε το 2015, από τους Παναγόπουλο-Χαλκιαδάκη-Jennings. Η εν λόγω προσέγγιση χρησιμοποιεί μία εναλλασσόμενη μέθοδο βελτιστοποίησης αποφάσεων σε υποχώρους κατάστασης-ενέργειας. Παρόλο που η ιδέα εργασίας σε υποχώρους λύσεων ενός προβλήματος βελτιστοποίησης δεν ήταν καινούργια, αυτός ο αλγόριθμος ήταν ίσως ο πρώτος που πρότεινε μία τέτοια προσέγγιση στα πλαίσια της ΜΔΑ. Η ίδια δημοσίευση επίσης αναδεικνύει την επιτυχία μίας τέτοιας προσέγγισης στο χειρισμό ενός φωτοβολταϊκού συστήματος παρακολούθησης ηλίου. Ωστόσο, η ίδια δημοσίευση δεν ξεκαθαρίζει πώς αυτός ο καινούργιος αλγόριθμος κλιμακώνεται σε σχέση με το μέγεθος του προβλήματος, ούτε πως συγκρίνεται με τις κλασσικές προσεγγίσεις επανάληψης πολιτικής και επανάληψης ανταμοιβής· και δε μπορεί να χρησιμοποιηθεί σε περιβάλλοντα τα οποία δεν αφήνουν την εκτέλεση των υπολογισμένων ενεργειών έπειτα από την βελτιστοποίηση στις διαχωρισμένες διαστάσεις. Το τελευταίο συνδέεται εννοιολογικά με καταστάσεις που έχουμε φαινόμενα “παραποίησης” (aliasing) πληροφορίας. Η παραποίηση πληροφορίας εμφανίζεται σε διάφορα επιστημονικά πεδία, όπως οι τηλεπικοινωνίες και η ρομποτική, και αντιστοιχεί στην απώλεια πληροφορίας έπειτα από τη μείωση των διαστάσεων ενός προβλήματος προκειμένου να προσεγγιστεί η λύση του. Ως εκ τούτου, σε αυτή τη διπλωματική εργασία παρουσιάζουμε μία νέα παραλλαγή του αλγορίθμου της εναλλασσόμενης επανάληψης πολιτικής που επιλύει τα προαναφερθέντα θέματα aliasing, και παρέχουμε συγκρίσεις με τους αλγορίθμους επανάληψης πολιτικής και επανάληψης ανταμοιβής. Δείχνουμε εμπειρικά ότι ο προτεινόμενος Aliasing Aware Alternating Policy Iteration (AAAPI) αλγόριθμός μας μπορεί να συγκλίνει στις βέλτιστες λύσεις (πολιτικές), με την παρουσία φαινομένων aliasing πληροφορίας. Επίσης, η υπολογιστική πολυπλοκότητα αυτού του αλγορίθμου είναι σε άμεση συσχέτιση με την ένταση της aliasing πληροφορίας. Σε περιβάλλοντα όπου τα φαινόμενα aliasing δεν είναι τόσο έντονα, ο AAAPI συγκλίνει γρηγορότερα σε σχέση με τις μεθόδους επανάληψης πολιτικής (policy iteration) και επανάληψης τιμών (value iteration)· αλλά σε περιβάλλοντα με υψηλό βαθμό aliasing πληροφορίας, όπως ο Λαβύρινθος, ο ρυθμός σύγκλισης του AAAPI πέφτει δραματικά και μπορεί να μη συγκλίνει στη βέλτιστη πολιτική. Μία επιπλέον συνεισφορά της εργασίας μας είναι η διατύπωση μία πιθανής επέκτασης του AAAPI σε πολυπρακτορικά περιβάλλοντα. | el |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2019-10-11 | - |
| Date of Publication | 2019 | - |
| Subject | Policy iteration | en |
| Subject | Artificial intelligence | en |
| Subject | Markov Decision Process | en |
| Subject | Decision theoretic planning | en |
| Bibliographic Citation | Αθανάσιος Μπαχάρης, "Εναλλασσόμενη επανάληψη πολιτικής: μία ανάλυση και μελλοντικές κατευθύνσεις", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2019 | el |
| Bibliographic Citation | 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
