Επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ
Στη διπλωματική λύνουμε το πρόβλημα του sudoku με χρήση του εκπαιδευτικού ρομπότ της Lego, το LEGO Mindstorm NXT. Το εκπαιδευτικό ρομπότ αυτό δεν έχει συγκεκριμένη μορφή αλλά αποτελείται από αλληλοσυνδεόμενα μεταξύ τους πλαστικά μέρη. Με χρήση αυτών κατασκευάσαμε ένα όχημα που αποτελεί παραλλαγή οχή...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2011
|
| Θέματα: | |
| Διαθέσιμο Online: | http://nemertes.lis.upatras.gr/jspui/handle/10889/4228 |
| id |
nemertes-10889-4228 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Εκπαιδευτικά ρομπότ Τοπολογική πλοήγηση Μετρική πλοήγηση Μορφολογική επεξεργασία εικόνας Εξαγωγή χαρακτηριστικών Αναζήτηση κατά βάθος Διάδοση περιορισμών LEGO NXT Mindstorm Sudoku Educational robots Topological navigation Metric navigation Morphological image Processing Feature extraction Depth-first search Constraint propagation 006.333 |
| spellingShingle |
Εκπαιδευτικά ρομπότ Τοπολογική πλοήγηση Μετρική πλοήγηση Μορφολογική επεξεργασία εικόνας Εξαγωγή χαρακτηριστικών Αναζήτηση κατά βάθος Διάδοση περιορισμών LEGO NXT Mindstorm Sudoku Educational robots Topological navigation Metric navigation Morphological image Processing Feature extraction Depth-first search Constraint propagation 006.333 Αλεξανδρίδης, Ζαχαρίας Επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ |
| description |
Στη διπλωματική λύνουμε το πρόβλημα του sudoku με χρήση του εκπαιδευτικού ρομπότ της Lego, το LEGO Mindstorm NXT. Το εκπαιδευτικό ρομπότ αυτό δεν έχει συγκεκριμένη μορφή αλλά αποτελείται από αλληλοσυνδεόμενα μεταξύ τους πλαστικά μέρη. Με χρήση αυτών κατασκευάσαμε ένα όχημα που αποτελεί παραλλαγή οχήματος από άλλη εργασία. Το όχημα αυτό μπορεί να κινείται μόνο μπροστά και πίσω. Διαθέτει έναν βραχίονα που μπορεί να κινεί δεξιά-αριστερά και στον οποίο εφαρμόζεται ένας αισθητήρας φωτεινότητας. Τέλος, στον βραχίονα υπάρχει θέση για στυλό.
Το πρόβλημα του sudoku που δίνεται στο ρομπότ είναι εκτυπωμένο σε ένα χαρτί Α4. Το ρομπότ αναλαμβάνει να το αναγνωρίσει με τον αισθητήρα, να το επιλύσει και να το αποτυπώσει με τη χρήση του στυλό. Για την επίτευξη αυτού του στόχου επιστρατεύονται αλγόριθμοι ρομποτικής και αλγόριθμοι τεχνητής νοημοσύνης. Συγκεκριμένα για την πλοήγηση του οχήματος εφαρμόζεται μετρική και τοπολογική πλοήγησης, στη συνέχεια για την αναγνώριση του προβλήματος και την ταυτοποίηση κάθε εικόνας που λαμβάνεται υλοποιήσαμε αλγόριθμους μορφολογικής επεξεργασία και τέλος για την επίλυση του προβλήματος sudoku υλοποιήσαμε και συγκρίναμε δύο αλγόριθμους, την αναζήτησης κατά βάθος και την αναζήτηση κατά βάθος με διάδοση περιορισμών. Οι τελικοί αλγόριθμοι που αναπτύχθηκαν διαπιστώσαμε ότι πετυχαίνουν το σκοπό τους αφού το όχημα αναγνωρίζει τους αριθμούς του δοσμένου προβλήματος με ποσοστό επιτυχίας 95%, λύνει τα περισσότερα προβλήματα σε λιγότερο από ένα δευτερόλεπτο και συμπληρώνει επιτυχώς τα κελιά του sudoku με τους σωστούς αριθμούς.
Πέρα από αυτές τη σύγκριση των αλγορίθμων θεωρούμε ότι η μελέτη ενός τέτοιου συστήματος είναι ιδανική για εισαγωγή σε θέματα ρομποτικής και μπορεί να χρησιμοποιηθεί ως εκπαιδευτικό εργαλείο πειραματισμού. Μάλιστα ο κώδικας μας σχολιάζεται επαρκώς σε αυτή την εργασία για να είναι ευκολότερη η κατανόηση του. Εκτός αυτού έχουμε αναπτύξει και πρόγραμμα αλληλεπίδρασης χρήστη-ρομπότ μέσω κονσόλας. |
| author2 |
Χατζηλυγερούδης, Ιωάννης |
| author_facet |
Χατζηλυγερούδης, Ιωάννης Αλεξανδρίδης, Ζαχαρίας |
| format |
Thesis |
| author |
Αλεξανδρίδης, Ζαχαρίας |
| author_sort |
Αλεξανδρίδης, Ζαχαρίας |
| title |
Επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ |
| title_short |
Επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ |
| title_full |
Επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ |
| title_fullStr |
Επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ |
| title_full_unstemmed |
Επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ |
| title_sort |
επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ |
| publishDate |
2011 |
| url |
http://nemertes.lis.upatras.gr/jspui/handle/10889/4228 |
| work_keys_str_mv |
AT alexandridēszacharias epilysētouproblēmatossudokumechrēsēeuphyōntechnikōnapoekpaideutikorompot |
| _version_ |
1771297269726838784 |
| spelling |
nemertes-10889-42282022-09-05T20:18:18Z Επίλυση του προβλήματος sudoku με χρήση ευφυών τεχνικών από εκπαιδευτικό ρομπότ Αλεξανδρίδης, Ζαχαρίας Χατζηλυγερούδης, Ιωάννης Χατζηλυγερούδης, Ιωάννης Alexandridis, Zaxarias Εκπαιδευτικά ρομπότ Τοπολογική πλοήγηση Μετρική πλοήγηση Μορφολογική επεξεργασία εικόνας Εξαγωγή χαρακτηριστικών Αναζήτηση κατά βάθος Διάδοση περιορισμών LEGO NXT Mindstorm Sudoku Educational robots Topological navigation Metric navigation Morphological image Processing Feature extraction Depth-first search Constraint propagation 006.333 Στη διπλωματική λύνουμε το πρόβλημα του sudoku με χρήση του εκπαιδευτικού ρομπότ της Lego, το LEGO Mindstorm NXT. Το εκπαιδευτικό ρομπότ αυτό δεν έχει συγκεκριμένη μορφή αλλά αποτελείται από αλληλοσυνδεόμενα μεταξύ τους πλαστικά μέρη. Με χρήση αυτών κατασκευάσαμε ένα όχημα που αποτελεί παραλλαγή οχήματος από άλλη εργασία. Το όχημα αυτό μπορεί να κινείται μόνο μπροστά και πίσω. Διαθέτει έναν βραχίονα που μπορεί να κινεί δεξιά-αριστερά και στον οποίο εφαρμόζεται ένας αισθητήρας φωτεινότητας. Τέλος, στον βραχίονα υπάρχει θέση για στυλό. Το πρόβλημα του sudoku που δίνεται στο ρομπότ είναι εκτυπωμένο σε ένα χαρτί Α4. Το ρομπότ αναλαμβάνει να το αναγνωρίσει με τον αισθητήρα, να το επιλύσει και να το αποτυπώσει με τη χρήση του στυλό. Για την επίτευξη αυτού του στόχου επιστρατεύονται αλγόριθμοι ρομποτικής και αλγόριθμοι τεχνητής νοημοσύνης. Συγκεκριμένα για την πλοήγηση του οχήματος εφαρμόζεται μετρική και τοπολογική πλοήγησης, στη συνέχεια για την αναγνώριση του προβλήματος και την ταυτοποίηση κάθε εικόνας που λαμβάνεται υλοποιήσαμε αλγόριθμους μορφολογικής επεξεργασία και τέλος για την επίλυση του προβλήματος sudoku υλοποιήσαμε και συγκρίναμε δύο αλγόριθμους, την αναζήτησης κατά βάθος και την αναζήτηση κατά βάθος με διάδοση περιορισμών. Οι τελικοί αλγόριθμοι που αναπτύχθηκαν διαπιστώσαμε ότι πετυχαίνουν το σκοπό τους αφού το όχημα αναγνωρίζει τους αριθμούς του δοσμένου προβλήματος με ποσοστό επιτυχίας 95%, λύνει τα περισσότερα προβλήματα σε λιγότερο από ένα δευτερόλεπτο και συμπληρώνει επιτυχώς τα κελιά του sudoku με τους σωστούς αριθμούς. Πέρα από αυτές τη σύγκριση των αλγορίθμων θεωρούμε ότι η μελέτη ενός τέτοιου συστήματος είναι ιδανική για εισαγωγή σε θέματα ρομποτικής και μπορεί να χρησιμοποιηθεί ως εκπαιδευτικό εργαλείο πειραματισμού. Μάλιστα ο κώδικας μας σχολιάζεται επαρκώς σε αυτή την εργασία για να είναι ευκολότερη η κατανόηση του. Εκτός αυτού έχουμε αναπτύξει και πρόγραμμα αλληλεπίδρασης χρήστη-ρομπότ μέσω κονσόλας. We solve the problem of sudoku using the educational robot LEGO Mindstorm NXT, made by LEGO. This educational robot doesn't have specific form but consists of interlinked plastics. We constructed a vehicle that is a variant from another work. This vehicle can move only forward and back. It has an arm that can move side to side and is equipped with a light sensor and a marker. The problem of sudoku is given to the robot in printed form on a A4 paper. The robot at first recognize the problem with the sensor, then it resolves it and finally writes the solution down by using the pen. To achieve this goal we implemented various algorithms. Specifically, we studied robotic algorithms such as metric and topological navigation. Moreover, to identify the printed problem we processed every captured image morphologically and finally to solve the sudoku instance we implemented and compared two methods, first-depth search and first-depth search with constraint propagation. We should mention that our code is written in Java for the lejOS firmware. The final code is capable of recognizing the numbers of the given problem with a success rate of 95%, solving most problems in less than a second and completing the cells on the paper with the correct numbers. Finally, we have developed an accompanying program that is usable for debugging purposes and for calibrating the robot. Even more, it can be used as education tool. 2011-04-07T14:23:10Z 2011-04-07T14:23:10Z 2010-09-29 2011-04-07T14:23:10Z Thesis http://nemertes.lis.upatras.gr/jspui/handle/10889/4228 gr 6 application/pdf winzip/winrar |
