Συντάχθηκε 15-07-2026 11:17
Ενημερώθηκε:
15-07-2026 11:45
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 145Π-58
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 16/07/2026 15:00
Λήξη: 16/07/2026 16:00
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Βίκτορος Παναγιώτου
με θέμα
Σχεδίαση και Ανάπτυξη Αυτόνομου Πράκτορα για το Επιτραπέζιο Παιχνίδι "Ricochet Robots"
Design and Development of an Autonomous Agent for the Board Game "Ricochet Robots"
Εξεταστική Επιτροπή
Καθηγητής Μιχαήλ Γ. Λαγουδάκης (Σχολή ΗΜΜΥ, Επιβλέπων)
Καθηγήτρια Αικατερίνη Μανιά (Σχολή ΗΜΜΥ)
Καθηγητής Θρασύβουλος Σπυρόπουλος (Σχολή ΗΜΜΥ)
Περίληψη
Η παρούσα διπλωματική εργασία ασχολείται με τη σχεδίαση και την ανάπτυξη αυτόνομου πράκτορα για το επιτραπέζιο παιχνίδι Ricochet Robots. Αυτό επιτεύχθηκε με τη δημιουργία μιας διαδικτυακής εφαρμογής με γραφική διεπαφή χρήστη, με κύριο σκοπό τη μελέτη αλγορίθμων αναζήτησης και ευρετικών συναρτήσεων σε ένα περιβάλλον που συνδυάζει απλούς κανόνες με έναν πολύ μεγάλο χώρο καταστάσεων. Το Ricochet Robots αποτελεί ένα ενδιαφέρον πρόβλημα για την Τεχνητή Νοημοσύνη, καθώς κάθε κίνηση ενός ρομπότ δεν τερματίζεται απλά σε κάποιο γειτονικό κελί, αλλά συνεχίζεται μέχρι να συναντήσει κάποιο εμπόδιο, όπως τοίχο, άλλο ρομπότ ή απαγορευμένη περιοχή. Αυτός ο απλός κανόνας δημιουργεί έναν σύνθετο χώρο καταστάσεων, όπου οι μεταβάσεις εξαρτώνται από την τρέχουσα τοπολογία της πίστας, και κάνει την εύρεση λύσης πιο απαιτητική, όσο αυξάνεται η δυσκολία του παζλ. Στο πλαίσιο της εργασίας υλοποιήθηκε ένα πλήρως παραμετρικό περιβάλλον παιχνιδιού, στο οποίο ο χρήστης μπορεί να δημιουργεί χάρτες, να παίζει χειροκίνητα, να επιλέγει έναν εκ των πέντε διαθέσιμων αλγόριθμων αναζήτησης για επίλυση και να παρακολουθεί την εκτέλεση της λύσης βήμα προς βήμα. Η εφαρμογή υποστηρίζει παραγωγή τυχαίων παζλ με χρήση φύτρου, ώστε κάθε χάρτης να μπορεί να δημιουργηθεί ξανά με τις ίδιες ρυθμίσεις, κάτι που είναι σημαντικό για την επανάληψη πειραμάτων και τη δίκαιη σύγκριση διαφορετικών μεθόδων. Για την επίλυση των παζλ υλοποιήθηκαν και ενσωματώθηκαν αλγόριθμοι μη πληροφορημένης (Breadth-First Search, Iterative-Deepening Depth-First search) και πληροφορημένης αναζήτησης (Greedy Best-First Search, A*, Iterative-Deepening A*). Παράλληλα, σχεδιάστηκαν διαφορετικές ευρετικές συναρτήσεις, οι οποίες αξιοποιούν με διαφορετικό τρόπο τη γεωμετρία της πίστας, τις θέσεις των ρομπότ και του στόχου και τις πιθανές ενδιάμεσες κινήσεις. Η υλοποίηση οργανώθηκε με τέτοιο τρόπο, ώστε οι αλγόριθμοι να χρησιμοποιούν κοινή αναπαράσταση καταστάσεων και κοινό μηχανισμό παραγωγής διαδόχων, επιτρέποντας έτσι την άμεση σύγκρισή τους στο ίδιο πρόβλημα. Επιπλέον, για τις διαδικασίες της αναζήτησης χρησιμοποιήθηκε η τεχνολογία των Web Workers, ώστε η διεπαφή της εφαρμογής να παραμένει ενεργή, ακόμη και όταν η επίλυση ενός παζλ απαιτεί περισσότερο χρόνο. Για την πειραματική αξιολόγηση δημιουργήθηκαν σύνολα παζλ διαφορετικών μεγεθών και επιπέδων δυσκολίας, ενώ καταγράφηκαν μετρικές, όπως χρόνος εκτέλεσης, αριθμός επεκταμένων και παραγόμενων κόμβων, μέγεθος frontier, ποσοστό επίλυσης και μήκος λύσης. Τέλος, η εργασία περιλαμβάνει και αξιολόγηση ευχρηστίας με βάση την κλίμακα System Usability Scale (SUS), ώστε να εξεταστεί όχι μόνο η αλγοριθμική πλευρά της εφαρμογής, αλλά και η εμπειρία χρήσης της από διαφορετικές κατηγορίες χρηστών. Με αυτόν τον τρόπο, η εργασία συνδυάζει την ανάπτυξη ενός λειτουργικού παιχνιδιού, την υλοποίηση αυτόνομου πράκτορα για το παιχνίδι και την πειραματική μελέτη τεχνικών αναζήτησης σε ένα ενιαίο σύστημα.
Abstract
This diploma thesis focuses on the design and development of an autonomous agent for the board game Ricochet Robots. This was achieved through the implementation of a web application with a graphical user interface, whose main purpose is the study of search algorithms and heuristic functions in an environment that combines simple rules with a very large state space. Ricochet Robots is an interesting problem for Artificial Intelligence, because each robot movement is not terminated simply in an adjacent cell, but continues until the robot meets an obstacle, such as a wall, another robot, or a forbidden area. This simple rule generates a complex state space, where transitions depend on the current topology of the board, and makes the search for a solution more demanding, as the difficulty of the puzzle increases. As part of this thesis, a fully parameterized game environment was implemented, in which the user can generate maps, play manually, select one of the five available search algorithms for solving, and observe the execution of the solution step by step. The application supports random puzzle generation using seeds, so that each map can be recreated with the same settings. This is important for repeating experiments and for fairly comparing different methods. For solving the puzzles, both uninformed (Breadth-First Search, Iterative-Deepening Depth-First search) and informed search algorithms (Greedy Best-First Search, A*, Iterative-Deepening A*) were implemented and integrated. At the same time, different heuristic functions were designed, each of which uses the geometry of the board, the position of the robots and the target, and the possible intermediate moves in different ways. The implementation was organized, so that all algorithms use a common state representation and a common successor generation mechanism, allowing them to be directly compared on the same problem. In addition, Web Workers were used for the search procedures, so that the application interface remains responsive, even when solving a puzzle requires more time. For the experimental evaluation, sets of puzzles with different sizes and difficulty levels were generated, while metrics, such as execution time, number of expanded and generated nodes, frontier size, solve rate, and solution length, were recorded. Finally, the thesis also includes a usability evaluation based on the System Usability Scale (SUS), in order to examine not only the algorithmic aspect of the application, but also the user experience for different categories of users. In this way, the thesis combines the development of a functional game, the implementation of an autonomous agent for this game, and the experimental study of search techniques in a unified system.
Meeting ID: 92635783061
Password: 757084
