Ένας σημαντικός ερευνητικός στόχος στον τομέα της ρομποτικής είναι η ανάπτυξη ρομπότ που έχουν την δυνατότητα να λειτουργούν αυτόνομα. Η αυτόνομη συμπεριφορά ορίζεται σε ορισμένες περιπτώσεις ως η λειτουργία του ρομπότ για την εκτέλεση διαφόρων ενεργειών πλοήγησης χωρίς την ανθρώπινη παρέμβαση. Στη βιβλιογραφία των αυτόνομων κινούμενων ρομπότ αναφέρονται ως συνηθισμένες λειτουργίες πλοήγησης η εύρεση της θέσης του ρομπότ (localization), η χαρτογράφηση του περιβάλλοντος χώρου (mapping), η σχεδίαση διαδρομών μέσα στο χώρο προς αυθαίρετα ορισμένες θέσεις/στόχους (path planning) και η αποφυγή εμποδίων (obstacle avoidance). Η λύση κάθε λειτουργίας πλοήγησης χωριστά είναι ένα δύσκολο πρόβλημα από μόνο του. Αυτό οφείλεται στην έμφυτη πολυπλοκότητα τόσο του χώρου αλλά και του ίδιου του ρομπότ, αφού καθ' ένα από αυτά είναι ένα πολύπλοκο δυναμικό σύστημα που χαρακτηρίζεται από αβεβαιότητα για την κατάστασή του κάθε χρονική στιγμή. Σε αυτή τη διατριβή προτείνεται ένα πιθανοκρατικό πλαίσιο για την αυτόνομη πλοήγηση ρομπότ βασιζόμενο σε Μερικώς Παρατηρήσιμες Μαρκοβιανές Διαδικασίες Απόφασης - ΜΠΜΔΑ (Partially Observable Markov Decision Processes - POMDPs). Το προτεινόμενο μοντέλο έχει την δυνατότητα να εκτελεί τις λειτουργίες πλοήγησης της εύρεσης της θέσης του ρομπότ, του σχεδιασμού διαδρομών καθώς και αποφυγής εμποδίων. Οι ΜΠΜΔΑ είναι μοντέλα για διαδοχική λήψη αποφάσεων όπου το περιβάλλον στο οποίο λειτουργεί το ρομπότ είναι μερικώς παρατηρήσιμο, δηλαδή η πραγματική κατάσταση του ρομπότ δεν είναι γνωστή. Επιπλέον, το αποτέλεσμα των ενεργειών που εκτελεί το ρομπότ μοντελοποιούνται πιθανοκρατικά. Συνεπώς, οι λειτουργίες πλοήγησης εκτελούνται με πιθανοκρατικό τρόπο. Το βασικό μειονέκτημα των ΜΠΜΔΑ είναι η εξαιρετικά μεγάλη υπολογιστική πολυπλοκότητα λύσης τους και για αυτό το λόγο έχουν εφαρμοστεί στην ρομποτική μέχρι σήμερα κυρίως ως μοντέλα για την λήψη αποφάσεων σε υψηλό επίπεδο μόνο. Σε αυτή τη διατριβή προτείνεται μια νέα ιεραρχική αναπαράσταση των ΜΠΜΔΑ ειδικά σχεδιασμένη για το πρόβλημα της αυτόνομης πλοήγησης ρομπότ που αποκαλείται Ιεραρχικές ΜΠΜΔΑ - Ρομποτικής Πλοήγησης (ΙΜΠΜΔΑ-ΡΠ). Οι ΙΜΠΜΔΑ-ΡΠ έχουν τη δυνατότητα να αναπαριστούν με αποδοτικό τρόπο μεγάλα πραγματικά περιβάλλοντα και λύνονται σε πραγματικό χρόνο. Αυτό επιτυγχάνεται κυρίως λόγω της σχεδιαστικής επιλογής να μοντελοποιηθούν οι συναρτήσεις μετάβασης (transition) και παρατηρήσεων (observation) βάση του μοντέλου κίνησης του ρομπότ και ανεξάρτητα από τον περιβάλλον στο οποίο λειτουργεί, όπως γίνεται συνήθως στην βιβλιογραφία των ΜΠΜΔΑ. Επιπλέον, εισάγεται η έννοια της αναφορικής ΜΠΜΔΑ (αΜΠΜΔΑ) που διατηρεί το μοντέλο κίνησης του ρομπότ χρησιμοποιώντας μια πολύ μικρή ΜΠΜΔΑ και το μεταφέρει στην ιεραρχική δομή κατά την διάρκεια της λύσης της. Η δομή και κατάσταση του περιβάλλοντος μοντελοποιείται στην συνάρτηση ανταμοιβής (reward) της ΙΜΠΜΔΑ-ΡΠ. Το προτεινόμενο μοντέλο εφαρμόζεται ως ένα ενιαίο πλαίσιο πλοήγησης το οποίο δεν χρησιμοποιεί εξωτερικά συνεργαζόμενες μονάδες. Για την επίτευξη αυτού του στόχου η λύση της ΙΜΠΜΔΑ-ΡΠ σε πραγματικό χρόνο είναι απαραίτητη εφ' όσον πρέπει να σχεδιάζει εκ νέου σε κάθε χρονική στιγμή το μονοπάτι προς τον στόχο και κατά συνέπεια να διεξάγει την λειτουργία της αποφυγής εμποδίων. Η ΙΜΠΜΔΑ-ΡΠ σχεδιάστηκε για εφαρμογή στο πρόβλημα της πλοήγησης σε δυναμικά πραγματικά περιβάλλοντα στα οποία υπάρχει πυκνή κίνηση ανθρώπων. Έτσι, είναι επιθυμητό το ρομπότ να εκτελεί την αποφυγή εμποδίων με τρόπο παρόμοιο με τον οποίο αποφεύγουν εμπόδια οι ίδιοι οι άνθρωποι. Δηλαδή το ρομπότ θα πρέπει να έχει τη δυνατότητα να αποφασίζει την κατάλληλη συμπεριφορά για αποφυγή εμποδίων δεδομένης της κατάστασης του περιβάλλοντος. Επομένως, το ρομπότ μπορεί να αποφασίσει να εκτελέσει μια παράκαμψη ή να ακολουθήσει ένα εντελώς καινούργιο μονοπάτι προς τον στόχο του και επιπλέον να αυξήσει ή να μειώσει την ταχύτητά του για να προσπεράσει ένα εμπόδιο ή να του επιτρέψει να περάσει, αντίστοιχα. Κάθε μια από τις παραπάνω τέσσερις συμπεριφορές για την αποφυγή εμποδίων θα πρέπει να αποφασιστεί αρκετά πριν φτάσει το ρομπότ κοντά στο εμπόδιο. Γι' αυτό το λόγο, η χρήση πρόβλεψης της κίνησης εμποδίων είναι απαραίτητη. Εφαρμόζονται δύο τύποι πρόβλεψης κίνησης: η βραχυπρόθεσμη και η μακροπρόθεσμη πρόβλεψη κίνησης. Η βραχυπρόθεσμη πρόβλεψη αναφέρεται στην πρόβλεψη της θέσης του εμποδίου την αμέσως επόμενη χρονική στιγμή ενώ η μακροπρόθεσμη αναφέρεται στην πρόβλεψη του τελικού σημείου κίνησης του εμποδίου. Kαι τα δύο είδη πρόβλεψης ενσωματώνονται στην συνάρτηση ανταμοιβής της ΙΜΠΜΔΑ-ΡΠ. Το προτεινόμενο πλαίσιο ρομποτικής πλοήγησης δοκιμάστηκε σε πραγματικές συνθήκες και τα αποτελέσματα επιβεβαιώνουν την αποδοτικότητα και αποτελεσματικότητά του. Η πιθανοκρατική φύση καθώς και η ακρίβεια και σταθερότητα της ΙΜΠΜΔΑ-ΡΠ όπως και η πρόβλεψη της κίνησης κρίνονται απαραίτητα στοιχεία για την αποτελεσματική και αποδοτική πλοήγηση σε δυναμικά πραγματικά περιβάλλοντα με πυκνή κίνηση ανθρώπων.
(EL)
A primary goal in robotics research is to provide means for mobile platforms to perform autonomously within their environment. Depending on the task at hand, autonomous performance can be defined as the execution by the robot, without human intervention, of certain navigational tasks. In mobile robotics literature, commonly addressed navigation tasks include the localization, mapping, path planning and obstacle avoidance tasks. Solving any of these tasks is a hard problem by itself. The reason stems from the inherent complexity associated with both the robot and its environment, each of them being an extremely complex dynamical system with uncertainty involved. In this thesis, we propose a probabilistic framework for mobile robot navigation in dynamic environments based on the Partially Observable Markov Decision Process (POMDP) model. The proposed model is able to perform the navigation tasks of localization, path planning and obstacle avoidance. POMDPs are models for sequential decision making where the world in which the robot operates is partially observable, i.e. the true underlying robot's state is not known, and the outcome of actions it executes is modeled probabilistically. As such POMDPs perform localization and path planning in a probabilistic manner. POMDPs have the major shortcoming of their extreme computational complexity and hence they have been mainly used in robotics as high level path planners only. In this thesis, we propose a novel hierarchical representation of POMDPs, specifically designed for the autonomous robot navigation problem and termed as the Robot Navigation - Hierarchical POMDP (RN-HPOMDP). The proposed hierarchical POMDP can efficiently model large real-world environments and is amenable to real time solution. This is achieved mainly due to the design choice of modeling the state transition and observation functions dependent only on the robot motion model and not on the environment as it is commonly used in the POMDP literature. Furthermore, the notion of the reference POMDP (rPOMDP) is introduced that infers the robot motion model in a very small POMDP and it transfers this information to the hierarchical structure while being solved. The environment specific information is modeled within the reward function of the RN-HPOMDP. The employed model is utilized as a unified probabilistic navigation framework that accommodates for localization, path planning and obstacle avoidance. Hence, real-time solution of the RN-HPOMDP is essential since no other external modules are utilized and paths have to be replanned at each time step. The RN-HPOMDP has been developed for the application of robot navigation in dynamic real-world environments that are highly populated. Thus, it is desirable for the robot to perform obstacle avoidance in a manner that resembles the human motion for obstacle avoidance. That is, the robot should be able to decide the most suitable obstacle avoidance behavior based on the state of the environment. Therefore, the robot can decide to either perform a detour or follow a completely new path to the goal and also modify its speed of movement (increase it or decrease it) to bypass an obstacle or let it move away respectively. Any of the above four distinct behaviors for obstacle avoidance should be decided well before the robot comes too close to the obstacle. For that reason, future motion prediction of obstacles is employed. Two kinds of prediction are utilized: short-term and long-term prediction. Short term prediction refers to the one-step ahead prediction whereas long-term prediction refers to the prediction of the final destination point of the obstacle's movement. Both kinds of prediction are integrated into the reward function of the RN-HPOMDP and the speed decision is performed through a modified solution of the RN-HPOMDP. As a result, the RN-HPOMDP can decide the optimal obstacle avoidance behavior based on the current and the predicted state of the environment without the intervention of any other external module. Experimental results have shown the applicability and effectiveness of the proposed framework for the navigation task. The robustness and the probabilistic nature of the RN-HPOMDP as well as the future motion prediction are required to be able to perform efficiently and effectively in dynamic real-world environments that are highly populated.
(EN)
Πανεπιστήμιο Κρήτης
