Αυτόνομη ρομποτική εξερεύνηση και αποφυγή εμποδίων σε στατικά περιβάλλοντα άγνωστων δισδιάστατων εσωτερικών χώρων
Loading...
Date
2024-11-01
Authors
Τσιαμήτρος, Κωνσταντίνος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Το πρόβλημα της χαρτογράφησης ενός εσωτερικού ή εξωτερικού χώρου ταυτόχρονα με τον εντοπισμό της θέσης του ρομπότ μέσα σε αυτόν τον χώρο χωρίς την παρέμβαση ανθρώπου αναφέρεται στην βιβλιογραφία ως «ταυτόχρονος εντοπισμός και χαρτογράφηση» (SLAM– Simultaneous Localization and Mapping [1], [2]. Η επίλυση του προβλήματος αυτού γίνεται ακόμα πιο δύσκολη όταν δεν βασίζεται σε προϋπάρχουσα γνώση του περιβάλλοντος (π.χ. γνωστά σημεία ενδιαφέροντος) ή/και δεν είναι διαθέσιμο κάποιο σύστημα εντοπισμού παγκόσμιας θέσης (GPS- Global Positioning System).
Στη βιβλιογραφία υπάρχουν τριών ειδών προσεγγίσεις για την επίλυση του SLAM [3]. Συγκεκριμένα:
λύσεις που βασίζονται στο φίλτρο Κάλμαν (EKF-Extended Kalman Filters)
λύσεις που βασίζονται στα φίλτρα σωματιδίων (particle filters) και
λύσεις που βασίζονται σε μη γραμμικές τεχνικές βελτιστοποίησης (nonlinear optimizations).
Η προσέγγιση που επιλέχθηκε να ακολουθηθεί στην εργασία αυτή ανήκει στις τελευταίες.
Η Εργασία αυτή ασχολείται με μια ακόμα πιο «δύσκολη» εκδοχή του προβλήματος αυτού. Θεωρούμε ακόμη ότι το ρομπότ ξεκινάει την λειτουργία του από μια τυχαία θέση στον χώρο χωρίς να γνωρίζει ποιά είναι αυτή. Η εκδοχή αυτή του προβλήματος είναι γνωστή ως «το πρόβλημα του απαχθέντος ρομπότ» (kidnapped robot problem). Παράλληλα με τον αυτόματο εντοπισμό της θέσης του ρομπότ στον χώρο, η ΜΔΕ αυτή ασχολείται και με το πρόβλημα της πλήρους εξερεύνησης ενός χώρου που οριοθετείται από τοίχους και ο οποίος μπορεί να περιέχει στατικά εμπόδια. Για την επιλογή της διαδρομής που θα ακολουθήσει το ρομπότ προκειμένου να εξερευνήσει τον χώρο στον οποίο βρίσκεται, υπάρχουν τρεις κύριες προσεγγίσεις [4], [5]. Συγκεκριμένα:
οι τεχνικές οδικών χαρτών (roadmap techniques),
οι αλγόριθμοι αποσύνθεσης κελιών (cell decomposition algorithms), και
οι μέθοδοι τεχνητού δυναμικού (artificial potential methods).
Η προσέγγιση που θα ακολουθηθεί στο πλαίσιο της διπλωματικής είναι ένας αλγόριθμος αποσύνθεσης κελιών. Συγκεκριμένα προτείνεται μια αλγοριθμική προσέγγιση, η οποία βασίζεται στην φιλοσοφία της αναζήτησης πρώτα στο καλύτερο (best first search) με βάση μια ευρετική συνάρτηση. Παρόλο που η προσέγγιση αυτή απαιτεί τετραγωνικό χώρο σε μνήμη σε συνάρτηση με το μέγεθος των θέσεων στις οποίες μπορεί να βρεθεί το ρομπότ (δηλαδή Ο(Ν2), όπου Ν = max{autonomous_distance}), ο χρόνος λήψης της επόμενης κατεύθυνσης στην οποία θα κινηθεί το ρομπότ είναι Ο(1), διότι περιορίζουμε την αναζήτηση σε μόλις 25 γειτονικά κελιά της τρέχουσας θέσης του ρομπότ. Εκμεταλλευόμενοι το χαρακτηριστικό αυτό του αλγορίθμου, το αρχικό πρόβλημα θα διατυπωθεί ως πρόβλημα κατηγοριοποίησης, το οποίο θα υλοποιηθεί με χρήση Συνελικτικών Νευρωνικών Δικτύων (Convolutional Neural Networks). Η προσέγγιση αυτή θα απαλείψει τις μεγάλες απαιτήσεις και σε χώρο στη μνήμη αλλά και σε υπολογιστική ισχύ.
Description
Keywords
Αναζήτηση πρώτα στο καλύτερο, Συνελικτικά νευρωνικά δίκτυα, Πλέγμα πληρότητας, Ευρετική συνάρτηση, Αλγόριθμος αποσύνθεσης κελιών, Αυτόνομη ρομποτική εξερεύνηση, Πρόβλημα απαχθέντος ρομπότ, Μη γραμμική βελτιστοποίηση, Ταυτόχρονος εντοπισμός και χαρτογράφηση, Μη διαθέσιμο παγκόσμιο σύστημα εντοπισμού, Άγνωστο περιβάλλον