Συντάχθηκε 07-10-2019 09:19
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΜΙΧΑΗΛ ΓΕΜΙΣΤΟΥ
με θέμα
Ανάπτυξη Ευφυούς Πράκτορα για τον Διαγωνισμό AIBIRDS
Implementation of an Intelligent Agent for the AIBIRDS Competition
Τρίτη 8 Οκτωμβρίου 2019, 11 π.μ.
Αίθουσα Εργαστηρίου Intelligence 141-Α14Α, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Λαγουδάκης Μιχαήλ (επιβλέπων)
Αναπληρωτής Καθηγητής Δεληγιαννάκης Αντώνιος
Αναπληρωτής Καθηγητής Χαλκιαδάκης Γεώργιος
Περίληψη
Το ευρύ πεδίο της Τεχνητής Νοημοσύνης (Artificial Intelligence - AI) προσπαθεί να αναπαράγει την ανθρώπινη συμπεριφορά στις μηχανές. Η Μηχανική Μάθηση, ως υποπεδίο, και πιο συγκεκριμένα η Ενισχυτική Μάθηση (Reinforcement Learning - RL), δίνει τη δυνατότητα σε αυτόνομους πράκτορες να επιλέγουν κατάλληλες ενέργειες κάτω από διαφορετικές συνθήκες μέσω μιας διαδικασίας μάθησης δοκιμών-και-σφαλμάτων, χωρίς να προγραμματίζονται για κάθε πιθανό σενάριο που μπορεί να συναντήσουν. Από το 2013, το συνέδριο International Joint Conference on Artificial Intelligence (IJCAI) φιλοξενεί τον Διαγωνισμό Angry Birds AI (AIBIRDS), όπου διάφοροι AI πράκτορες ανταγωνίζονται στο ηλεκτρονικό παιχνίδι Angry Birds. Οι πράκτορες ανταγωνίζονται σε άγνωστες πίστες παιχνιδιού χωρίς καμία ανθρώπινη παρέμβαση. Στην παρούσα διπλωματική εργασία, σχεδιάσαμε δύο πράκτορες για το AIBIRDS ακολουθώντας τις αρχές δύο γνωστών RL αλγορίθμων, συγκεκριμένα του Q-Learning και του Least Squares Policy Iteration (LSPI). Και οι δύο είναι RL αλγόριθμοι χωρίς μοντέλα και προσπαθούν να μάθουν την καλύτερη ενέργεια σε κάθε βήμα (πολιτική) για κάθε δεδομένη σκηνή του παιχνιδιού. Δεδομένου ότι οι χώροι ενεργειών και καταστάσεων του παιχνιδιού είναι εξαιρετικά μεγάλοι και λόγω της απουσίας ενός μοντέλου που περιγράφει τη μετάβαση από μια κατάσταση σε κάποια επόμενη κατάσταση υπό την επιρροή μιας επιλεγμένης ενέργειας, χρησιμοποιήσαμε μια αρχιτεκτονική προσέγγισης για να αναπαριστούμε τις μαθηματικές τιμές Q, οι οποίες εκτιμούν την ποιότητα κάθε ενέργειας σε κάθε κατάσταση. Η προσέγγιση χρησιμοποιεί ένα σύνολο από οκτώ συναρτήσεις βάσης (χαρακτηριστικά) που σχεδιάσαμε, τα οποία προσπαθούν να περιγράψουν αποτελεσματικά μια σκηνή παιχνιδιού, και κάθε μία σταθμίζεται με τη δική της παράμετρο (βάρος). Στα πειράματά μας, ο πράκτορας Q-Learning εκπαιδεύεται για 20.000 επαναλήψεις για την ενημέρωση των βαρών του σταδιακά κατά τη διάρκεια αυτής της εκπαίδευσης, καταλήγοντας στις τελικές τους τιμές, όταν ολοκληρωθούν οι επαναλήψεις. Σε κάθε επανάληψη, ο πράκτορας Q-Learning αποθηκεύει τοπικά το κάθε παρατηρούμενο δείγμα αλληλεπίδρασης με το παιχνίδι, το οποίο περιλαμβάνει την τρέχουσα κατάσταση, τη ενέργεια που έχει ληφθεί, τη νέα κατάσταση και την ανταμοιβή που αποκτήθηκε. Ο πράκτορας LSPI εκπαιδεύεται στη συνέχεια χρησιμοποιώντας το αποθηκευμένο σύνολο δειγμάτων για να βρει το δικό του σύνολο βαρών και επομένως τη δική του πολιτική. Όταν η διαδικασία εκπαίδευσης τελειώσει τόσο για τον Q-Learning όσο και για τον LSPI πάνω στα ίδια παρατηρούμενα δείγματα, εξετάζουμε κάθε πράκτορα σε 54 διαφορετικές πίστες που ελήφθησαν απευθείας από τον διαγωνισμό AIBIRDS, 34 εκ των οποίων είναι αυτές όπου εκπαιδεύτηκαν οι πράκτορές μας και 20 είναι παντελώς άγνωστες στους πράκτορες. Ο πράκτορας Q-Learning είναι σε θέση να ολοκληρώσει επιτυχώς το 68% και ο πράκτορας LSPI το 81% εξ αυτών, εκτελώντας κατά διαστήματα βολές ακριβείας με εκπληκτικά αποτελέσματα.
Abstract
The broad field of Artificial Intelligence (AI) strives to reproduce human behavior on machines. Machine Learning, as a subfield, and more specifically Reinforcement Learning (RL), enables autonomous agents to take suitable actions under different circumstances through a trial-and-error learning process, without being programmed for every possible scenario they may encounter. Since 2013, the International Joint Conference on Artificial Intelligence (IJCAI) hosts the Angry Birds AI Competition (AIBIRDS), where various AI agents compete on the Angry Birds computer game. The agents compete on unknown game levels without any human intervention. In this thesis, we designed two agents for AIBIRDS following the principles of two well-known RL algorithms, namely Q-Learning and Least Squares Policy Iteration (LSPI). Both of them are model-free RL algorithms, trying to learn the best action at each step (policy) for any given game scene. Since the action and state spaces of the game are extremely large and due to the absence of a model that describes the transition from a state to a next state affected by an action choice, we used an approximation architecture to represent the learned Q values, which estimate the quality of each action in each state. The approximation uses a set of eight basis functions (features) we designed, which try to describe a game scene effectively, and each one is weighted by its own parameter (weight). In our experiments, the Q-Learning agent is trained for 20,000 iterations updating its weights incrementally during the course of that training, concluding to their final values, when the iterations are completed. At each iteration, the Q-Learning agent stores locally each observed sample of interaction with the game, which includes the current state, the action taken, the new state and the reward gained. The LSPI agent is then trained using the stored set of samples to find its own set of weights and thus its own policy. When the process of training ends for both Q-Learning and LSPI on the same observed samples, we test each agent on 54 different levels taken directly from the AIBIRDS competition, 34 of those being the levels our agents were trained on and 20 levels being completely new to the agents. The Q-Learning agent is able to complete successfully 68% of these levels and the LSPI agent 81% of them, occasionally performing precise shots with amazing results.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 141Α-14, Αίθουσα Εργαστηρίου Intelligence, Πολυτεχνειούπολη
Έναρξη: 08/10/2019 11:00
Λήξη: 08/10/2019 12:00
