Στα πλαίσια της παρούσας εργασίας θα ασχοληθούμε με παθητικές μεθόδους τρισδιάσατης ανακατασκευής του χώρου και συγκεκριμένα με την επεξεργασία δεδομένων εικόνων που λαμβάνονται από μια φωτογραφική μηχανή. / In this paper we will analyse pathetic methods of 3D reconstruction and especially data proccess of pictures received from a digital camera.

Την τελευταία δεκαετία έχει παρατηρηθεί μια σημαντική διάδοση των συστημάτων πλοήγησης οχημάτων. Τα συστήματα αυτά συνδυάζοντας τις δυνατότητες που προσφέρει η τεχνολογία και χρησιμοποιώντας τη γεωγραφική αναπαράσταση του οδικού δικτύου, την τρέχουσα θέση του οχήματος και συχνά πληροφορίες για την κίνηση προτείνουν στους οδηγούς τη διαδρομή που πρέπει να ακολουθήσουν για να φτάσουν πιο γρήγορα στον προορισμό τους. Οι εφαρμογές πλοήγησης οχημάτων μπορούν να προσφέρουν τη δυνατότητα διαχείρισης της κυκλοφορίας με τέτοιο τρόπο που επιτρέπει την αύξηση της χωρητικότητας του οδικού δικτύου και επομένως τη μείωση της συμφόρησης, χωρίς να είναι απαραίτητη η υψηλού κόστους επέκταση της οδικής υποδομής. Σε αντίθεση με το βέλτιστο για το χρήστη μοντέλο που εφαρμόζεται στα κλασικά συστήματα πλοήγησης και που δεν παρέχει καμία εγγύηση βελτίωσης της κυκλοφοριακής κατάστασης, για το σκοπό αυτό έχει προταθεί το βέλτιστο για το σύστημα μοντέλο. Το μοντέλο προτείνει διαδρομές με στόχο τη βελτίωση της κυκλοφοριακής κατάστασης στο δίκτυο, αλλά η εφαρμογή του είναι μη ρεαλιστική καθώς οι προτεινόμενες διαδρομές μπορεί να είναι πολύ μακρύτερες από το αναμενόμενο. Στην παρούσα διπλωματική εργασία μελετάται μια τρίτη προσέγγιση: ένας βέλτιστος για το σύστημα υπό περιορισμούς αλγόριθμος. Πρόκειται για ένα συνδυασμό των δύο μοντέλων πλοήγησης με σκοπό τη μείωση της συμφόρησης και ταυτόχρονα τη διατήρηση της δικαιοσύνης στην επιλογή των προτεινόμενων διαδρομών για τους οδηγούς. Αφού γίνει θεωρητική μελέτη του προβλήματος παρουσιάζεται η υλοποίηση ενός συστήματος πρότασης διαδρομών που χρησιμοποιεί το βέλτιστο για το σύστημα υπό περιορισμούς αλγόριθμο. / During the last decade, vehicles' route guidance systems have known a significant spread. These systems, taking advantage of the available technological features and by using the geographical representation of the road network, the current position of a vehicle and often traffic data, propose to drivers the route they should follow in order to reach faster their destination. The applications of route guidance systems offer the chance to manage traffic in such a way that allows an increase in road network capacity and therefore a decrease in traffic congestion, without being necessary the high cost expansion of the road infrastructure. In contrast to the user optimal model that is followed by typical route guidance systems and provides no traffic improvement guarantees, the system optimal model has been proposed for this purpose. The model proposes paths with the goal of improving the traffic condition of the network, however its application is unrealistic since the proposed routes may be much longer than expected. In this thesis a third approach is studied: a constrained system optimal algorithm. The algorithm is a combination of the two navigation models with the goal of reducing congestion and at the same time remaining fair for drivers when selecting a route. After the theoretical study of the problem, the implementation of a route recommendation system that incorporates the constrained system optimal algorithm is presented.

Η παρούσα διπλωματική εργασία μελετά το θέμα της πλοήγησης ενός ρομποτικού οχήματος με στόχο την εξερεύνηση μιας περιοχής η οποία είτε είναι ελεύθερη είτε περιέχει εμπόδια σε γνωστές θέσεις. Για αυτό το πρόβλημα εξερεύνησης, υπάρχει επίσης ένας περιορισμός που αφορά το όχημα: θα πρέπει αυτό κατά τη διάρκεια της εξερεύνησης να διατηρεί την επικοινωνία του με ένα σταθερό σταθμό βάσης. Για να αντιμετωπιστεί το σύνθετο αυτό θέμα και για να αναπτυχθεί ένας αλγόριθμος για την πειραματική διαδικασία, αρχικά θεωρήθηκε ένα μοντέλο κινοδυναμικών εξισώσεων για το ρομποτικό όχημα. Στη συνέχεια, για το μοντέλο αυτό παρουσιάστηκε ένας μη-γραμμικός ελεγκτής που σχεδιάστηκε για παρακολούθηση επιθυμητών τροχιών. Για να υλοποιηθεί ο εν λόγω ελεγκτής, ήταν απαραίτητος ο εντοπισμός της θέσης του ρομποτικού οχήματος και αυτό επετεύχθη πειραματικά μέσω επεξεργασίας εικόνας. Το ρομπότ αναγνωριζόταν στις εικόνες που λαμβάνονταν από μια κάμερα παρακολούθησης, και με κατάλληλη γεωμετρική ανάλυση ήταν εφικτή η εκτίμηση της θέσης και του προσανατολισμού του ρομπότ. Για την επικοινωνία του ρομπότ με το σταθμό βάσης αναπτύχθηκε ασύρματο δίκτυο ΙΕΕΕ 802.15.4 και για την αξιολόγηση της ποιότητας της επικοινωνίας αυτής χρησιμοποιήθηκε το Received Signal Strength Indicator (RSSI). Ο αλγόριθμος σχεδιασμού διαδρομής, ο οποίος καθοδηγεί το ρομπότ στο περιβάλλον με στόχο την εξερεύνηση όλων των ελεύθερων σημείων, αξιοποίησε την εκ των προτέρων γνώση για τα εμπόδια, καθώς και τις μετρήσεις του RSSI κατά τη διάρκεια του πειράματος, ώστε να πετύχει το στόχο του. Πιο συγκεκριμένα, χρησιμοποιήθηκε μια on-line μέθοδος που πετυχαίνει όσο το δυνατόν μεγαλύτερη κάλυψη του περιβάλλοντος υπό τον περιορισμό της επικοινωνίας, έχοντας σαν οδηγό μια προσχεδιασμένη διαδρομή εξερεύνησης. Στο τέλος της εργασίας παρουσιάζονται πειραματικά αποτελέσματα και συμπεράσματα για τα διάφορα αντικείμενα της μελέτης. / The present diploma thesis studies the subject of the navigation of a robotic vehicle for the exploration of an environment which is either free or contains obstacles in known locations. For this area coverage problem, there is an additional constraint: during the exploration the robot must maintain its communication with a stationary base station. In order to address this complex subject and to develop an algorithm for the experimental procedure, a kinodynamic model is initially assumed for the robotic vehicle. Then, a non-linear controller is designed for this model to achieve tracking of reference trajectories. For the implementation of this controller, the localization of the robotic vehicle was necessary and it was achieved via image processing during the experiments. The robot was recognized in images taken by a surveillance camera, and after appropriate geometric analysis, it was possible to estimate the position and the orientation of the robot. For the robot-base communication, an IEEE 802.15.4 wireless network was developed and in order to evaluate the quality of this communication, the Received Signal Strength Indicator (RSSI) was utilised. The path planning algorithm, which navigates the robot inside the environment to explore all the available locations, achieved its goal by combining the prior knowledge about the obstacles and the RSSI measurements during the experiments. Specifically, an on-line method that achieves maximum possible coverage of the environment under the communication constraint was employed, using a pre-designed exploring path as a guide. At the end of this thesis, some experimental results and conclusions are presented concerning the versatile subjects of this study.

Στη διπλωματική λύνουμε το πρόβλημα του 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.

Η αυτόματη πλοήγηση πλοίων αποτελεί ένα αντικείμενο ιδιαίτερης μελέτης κατά τα τελευταία χρόνια. Αυτό οφείλεται αφενός στην μεγάλη χρησιμότητα της εφαρμογής της, αφετέρου στην δυσκολία μαθηματικής περιγραφής και μοντελοποίησης των αντίστοιχων συστημάτων. Κατά την διπλωματική εργασία αυτή, σχεδιάστηκε ένας ελεγκτής ανοικτού βρόχου εμπροσθογενούς δράσης, με τη βοήθεια πειραματικών μετρήσεων, που σε συνδυασμό με τους συνήθεις πλέον PD και ασαφείς ελεγκτές, υλοποιήθηκε με σκοπό τον πειραματικό έλεγχο της θέσης και του προσανατολισμού του μοντέλου ενός πραγματικού πλοίου. / Control in ship navigation is a field of excess research during the last few years. The increasing need for automated ship navigation, combined with the challenging to describe and model systems of ships and other vessels, has led to many great works on this area. In this diploma thesis an open loop feedforward controller was designed using experimental data. This controller was used together with PD and Fuzzy controllers to control the position and the orientation of a model ship.

Η παρούσα διπλωματική ασχολείται με την πλοήγηση κινούμενου ρομπότ. Δεδομένου ενός χώρου με εμπόδια και στόχο, ασχολείται με την δημιουργία ενός αλγορίθμου για την οδήγηση του ρομπότ διαμέσου του χώρου στο στόχο, αποφεύγοντας τα εμπόδια κατά την κίνηση. Επικεντρώνεται σε δίτροχα ρομπότ και αναλύει βήμα βήμα την διαδικασία εύρεση μονοπατιού, δημιουργία τροχιάς και έλεγχο του ρομπότ. / The present thesis deals with the navigation of moving robots. Granted an area with obstacles and target, it deals with the creation of an algorithm for guiding the robot through space at target, avoiding obstacles during movement. It focuses on two-wheeled robots and analyzes step by step the process of finding a path, creating the trajectory and controlling the robot.