Η επίλυση των λαβυρίνθων, που είναι μια φαινομενικά μικρή πρόκληση για τον μυαλό των
ανθρώπων, αποτελεί μια μεγάλη πρόκληση για τους εμπειρογνώμονες της τεχνητής νοημοσύνης
ώστε να μπορέσουν να δημιουργήσουν αυτόνομα οχήματα (ρομπότ) που να είναι σε θέση να
λύνουν οποιοδήποτε λαβύρινθο. Τα ερωτήματα που μας έρχονται αυτόματα στο μυαλό είναι, γιατί
απαιτούμε από τα ρομπότ να μας λύσουν ένα λαβύρινθο; Είναι πραγματικά τόσο απαραίτητο; Η
απάντηση είναι καταφατική και απολυτή, «ναι είναι». Τα ρομπότ μπορούν να αυτοματοποιήσουν
ένα ευρύ φάσμα φυσικών εργασιών από τη διαχείριση αποθήκης (Amazon Warehouse Robots)
[Εικόνα 1], μέχρι την εξεύρεση ανθρώπων σε συντρίμμια. Για αυτό ακριβώς το λόγο απαιτούμε
από τα ρομπότ να έχουν ως ένα βαθμό αναλυτική σκέψη και να μπορούν να λύσουν περίπλοκους
λαβυρίνθους.
Ένα τέτοιο ρομπότ πρέπει να αποφασίζει και να εκτελεί συνεχώς τις σωστές εντολές μέσα από
μια σειρά διαθέσιμων ενεργειών μέχρι να φτάσει στον προορισμό του. Οι αποφάσεις του ρομπότ
θα πρέπει αποσκοπούν στο να αποφεύγει τις συγκρούσεις και άλλα επιβλαβή συμβάντα, ενώ
ταυτόχρονα θα πρέπει να εξασφαλίζει τη συντομότερη διαδρομή και το μικρότερο δυνατό χρόνο
αναζήτησης. Αν και υπάρχουν πολλοί αλγόριθμοι για την επίλυση λαβυρίνθου, δεν μπορούμε να
πούμε με ευκολία ποιος είναι ο γρηγορότερος. Οι περισσότεροι αλγόριθμοι επικεντρώνονται στην
εύρεση του συντομότερου σε μήκος (βήματα) μονοπατιού, που όμως δεν είναι απαραίτητα και το
ταχύτερο (ή βέλτιστο) μονοπάτι. Οι αλγόριθμοι που μελετάμε στην παρούσα πτυχιακή εργασία
είναι αλγόριθμοι επίλυσης λαβυρίνθου, όπως οι Wall follower, Pledge algorithm, Chain algorithm,
Recursive backtracker, Trémaux's algorithm, Dead end filler, Cul-de-sac filler, Blind alley filler,
Blind alley sealer, Shortest path finder, Shortest paths finder, Collision solver, Random mouse και
τέλος ο Flood Fill, πού αναλύουμε με μεγαλύτερη λεπτομέρεια. Επομένως, η παρούσα πτυχιακή
εργασία αφορά το πρόβλημα της επίλυσης λαβυρίνθου και κινείται στο χώρο των αλγορίθμων
λήψης αποφάσεων της ρομποτικής.
Πιο συγκεκριμένα, παρουσιάζονται τα χαρακτηριστικά και οι κατηγορίες λαβυρίνθων.
Αναφέρονται οι πληροφορίες που χρειάζεται να έχει ένα αυτόνομο όχημα (ρομπότ) ώστε να
επιλύσει ένα λαβύρινθο και μελετώνται οι κυριότεροι αλγόριθμοι επίλυσης λαβυρίνθου,
επικεντρώνοντας στην βαθύτερη κατανόηση και την υλοποίηση του αλγορίθμου Flood Fill, μέσω
της δημιουργίας ενός προγράμματος προσομοίωσης γραμμένο σε γλώσσα Java. Τέλος μελετώνται
τα μηχανικά και ηλεκτρονικά μέρη που αποτελούν ένα αυτόνομο όχημα (ρομπότ) που επιλύει
λαβυρίνθους με βάση τον παραπάνω αλγόριθμο.
Maze (or labyrinth) solving, which seems to be a small challenge to people's minds, is a great
challenge for artificial intelligence experts to be able to create autonomous robots capable of
solving any maze. The questions that come to our mind are, why do we require robots to solve a
maze? Is it really necessary? The answer certainly is, "Yes, it is". Robots can automate a wide
range of physical tasks from Amazon Warehouse Robots [Figure 1] to finding people in debris.
That's why we require robots to have some degree of analytical thinking and be able to solve
complex labyrinths.
Such a robot must decide and execute the correct commands continuously through a range of
available actions until it reaches its destination. Robot decisions should be aimed at avoiding
conflicts and other harmful events, while at the same time ensuring the shortest route and the least
possible search time. Although there are many algorithms for maze solving, we cannot certainly
say who is the fastest. Most algorithms focus on finding the shortest path (steps), but it may not
necessarily the fastest (or optimal) path. The algorithms we study in this dissertation are maze
solving algorithms, such as the Wall follower, Pledge algorithm, Chain algorithm, Recursive
backtracker, Trémaux's algorithm, Dead end filler, Blind alley filler, Shortest path finder, Shortest
paths finder, Collision solver, Random mouse and finally Flood Fill, which is analyzed in more
detail. So, this dissertation deals with the problem of maze solving and moves into the field of
decision making algorithms in robotics.
More specifically, the features and classes of mazes are presented. We study the information that
a robot needs to solve a maze and the main labyrinth solving algorithms, focusing on a deeper
understanding and implementation of the Flood Fill algorithm through the creation of a simulation
program written in Java. Finally, the mechanical and electronic parts of a robot which solves
labyrinths based on the algorithms is studied.
Hellenic Open University
Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.
