Ευφυείς αλγόριθμοι μάθησης και δρομολόγησης οχημάτων βάσει συνεργατικών σχημάτων

Intelligent learning algorithms for cooperative vehicular routing

Ευφυείς αλγόριθμοι μάθησης και δρομολόγησης οχημάτων βάσει συνεργατικών σχημάτων

Masikos, Michail

Μασίκος, Μιχαήλ

PhD Thesis

2013

The aim of the present thesis is to identify the most energy-efficient route towards the desired destination through the implementation of both computational intelligence and communications technologies. In particular, it proposes the implementation of machine learning techniques for reliably estimating the energy cost of the probable paths towards the desired destination based on the previously collected experience. Moreover, in order to further enhance the experience accumulating process, it suggests the use of the available V2V and V2I technologies and the establishment of cooperative networks enabling, thus, the exchange of experience between vehicles. Initially, the thesis identifies the current status and the expected development in the transport field and reveals the size of the energy problem faced globally. In order to limit the expansion of this problem, car manufacturers started developing the so called “green” vehicles (e.g. the fully electric vehicles) that adopt environmentally-friendly technologies. Nevertheless, these green technologies impose some functional limitations to the vehicle’s usage (e.g. in case of fully electric vehicles such limitations are the limited range and the time consuming recharging process). In this context, the objective of the present thesis is to expand the range of fully electric vehicles through the implementation of technologies that belong to fields not related to vehicular development, i.e. the computational intelligence field and the communications field. Not to mention, reviewing the state of the art related to the scope of this thesis renders the adopted approach innovative and rather challenging.Thus, the rest of the thesis is devoted to the development and the verification of the proposed energy-efficient routing algorithms. The development process starts with the formulation of the proposed solution and the justification of the introduced design choices. Forecasting reliably the energy costs of the probable paths towards the destination and confronting with the problems that accrue due to the specificities of the fully electric vehicles (e.g. energy recovery through regenerative breaking) constitute some of the major issues addressed by the present thesis. In particular, in order to address them successfully the thesis proposes the estimation of the route’s energy cost by means of machine learning techniques and promotes the exploitation of travelling experience that is either gathered by the vehicle itself or retrieved from other vehicles through synchronization. Furthermore, the thesis applies suitable shifting techniques so as to eliminate the negative energy costs from routing calculations and develops a methodology for protecting the user’s privacy during the exchange of experience between vehicles.Secondly, the thesis develops the architecture of an intelligent navigation system implementing the introduced routing algorithms. Based on the developed architecture, it further performs a scalability and performance analysis of the designed system. According to the results of this analysis, it is verified that the commercially available hardware and software are capable of supporting the functionality of the developed architecture. Finally, the thesis describes the development of a prototype system implementing the architecture designed previously and it presents the installation of the developed prototype in a fully electric vehicle serving as the test vehicle. This test vehicle performs a series of field trials especially planned for evaluating the efficiency of the proposed energy-efficient routing algorithms and the perceived user experience. The final conclusions of the thesis are extracted based on the generated evaluation report.

Η παρούσα διατριβή εστιάζει στην εύρεση της ενεργειακά βέλτιστης διαδρομής προς τον επιθυμητό προορισμό μέσω της εφαρμογής των σύγχρονων τεχνολογιών της υπολογιστικής νοημοσύνης και των επικοινωνιών. Συγκεκριμένα, εφαρμόζει τεχνικές μηχανικής μάθησης για την εκμετάλλευση της πρότερης εμπειρίας ενός οχήματος και την πραγματοποίηση αξιόπιστων εκτιμήσεων του ενεργειακού κόστους των πιθανών διαδρομών προς τον επιθυμητό προορισμό και αξιοποιεί τις διαθέσιμες τεχνολογίες V2V και V2I για την ενεργοποίηση της δυνατότητας ανταλλαγής εμπειρίας μεταξύ των οχημάτων μέσω της εδραίωσης συνεργατικών σχημάτων.Αρχικά, η διατριβή επικεντρώνεται στην παρουσίαση της τρέχουσας κατάστασης και των αναμενόμενων εξελίξεων στον τομέα των μεταφορών και απεικονίζει τις πραγματικές διαστάσεις του ενεργειακού προβλήματος που βιώνουμε. Προκειμένου να περιοριστεί το πρόβλημα αυτό, αναπτύχθηκαν τα λεγόμενα «πράσινα» οχήματα (όπως είναι για παράδειγμα τα πλήρως ηλεκτροκινούμενα οχήματα), τα οποία είναι φιλικότερα προς το περιβάλλον σε σχέση με τα οχήματα που εξοπλίζονται με μηχανές εσωτερικής καύσης. Ωστόσο, οι τεχνολογίες που υλοποιούν θέτουν κάποιους σημαντικούς περιορισμούς (π.χ. περιορισμένη αυτονομία και χρονοβόρος διαδικασία φόρτισης) όσον αφορά στη χρήση τους. Μέσα στα πλαίσια αυτά διατυπώνεται το αντικείμενο της διατριβής που συνίσταται στην επέκταση της αυτονομίας των πλήρως ηλεκτροκινούμενων οχημάτων με τη χρησιμοποίηση τεχνολογιών, που έγκεινται σε διαφορετικά επιστημονικά πεδία, όπως είναι οι τεχνολογίες υπολογιστικής νοημοσύνης και επικοινωνιών. Η μελέτη όλων των σχετικών εργασιών που έχουν πραγματοποιηθεί αναφορικά με το αντικείμενο της παρούσας διατριβής αποδεικνύει ότι μια τέτοια προσέγγιση είναι καινοτόμος και ως εκ τούτου παρουσιάζει μεγάλο ενδιαφέρον.Το υπόλοιπο της διατριβής, λοιπόν, κλιμακώνεται με στόχο την ανάπτυξη και επαλήθευση των προτεινόμενων ευφυών αλγορίθμων εύρεσης της ενεργειακά βέλτιστης διαδρομής. Σε πρώτο στάδιο, αναλύεται και διατυπώνεται το εξεταζόμενο πρόβλημα και τεκμηριώνονται οι επιλογές που πραγματοποιούνται για την επίλυσή του. Σημαντικά ζητήματα που καλείται να αντιμετωπίσει η συγκεκριμένη διατριβή είναι η αξιόπιστη εκτίμηση του ενεργειακού κόστους των πιθανών διαδρομών προς τον επιθυμητό προορισμό, καθώς και η ενσωμάτωση κάποιων ιδιαιτεροτήτων των πλήρως ηλεκτροκινούμενων οχημάτων στους υπολογισμούς (π.χ. η δυνατότητα επανάκτησης ενέργειας μέσω της αναγεννητικής πέδησης). Για την αντιμετώπιση των ζητημάτων αυτών προτείνεται η εφαρμογή τεχνικών μηχανικής μάθησης και η εκτίμηση του ενεργειακού κόστους των διαδρομών με βάση την πρότερη εμπειρία, που συλλέγεται κατά την κίνηση του οχήματος ή μετά την ανταλλαγή εμπειρίας με άλλα οχήματα. Παράλληλα, εφαρμόζονται κατάλληλες τεχνικές μετατόπισης για την εξάλειψη της πιθανότητας εμφάνισης αρνητικού ενεργειακού κόστους κατά τον υπολογισμό μιας διαδρομής και αναπτύσσεται μία μέθοδος διαφύλαξης της ιδιωτικότητας των χρηστών κατά την ανταλλαγή εμπειρίας μεταξύ των οχημάτων.Σε δεύτερο στάδιο, αναπτύσσεται η αρχιτεκτονική ενός ευφυούς συστήματος πλοήγησης που υλοποιεί τους προτεινόμενους αλγορίθμους εύρεσης της ενεργειακά βέλτιστης διαδρομής. Με βάση αυτήν την αρχιτεκτονική, μελετώνται οι δυνατότητες κλιμάκωσης και εφαρμογής του συστήματος πλοήγησης που σχεδιάστηκε. Αφού, λοιπόν, διαπιστώνεται ότι τα διαθέσιμα μέσα υλικού και λογισμικού μπορούν να υποστηρίξουν τη λειτουργία του συστήματος αυτού, ακολουθεί το τελικό στάδιο της ανάπτυξης της διατριβής.Κατά το στάδιο αυτό, αναπτύσσεται ένα πρωτότυπο σύστημα σύμφωνα με την αρχιτεκτονική που σχεδιάστηκε και στη συνέχεια αυτό εγκαθίσταται σε ένα πλήρως ηλεκτροκινούμενο όχημα. Το όχημα αυτό χρησιμοποιείται για την πραγματοποίηση δοκιμών πεδίου με στόχο την αξιολόγηση των προτεινόμενων αλγορίθμων εύρεσης της ενεργειακά βέλτιστης διαδρομής τόσο σε επίπεδο αποδοτικότητας, όσο και σε επίπεδο χρηστικότητας των παραγόμενων διαδρομών για τον οδηγό του οχήματος. Με βάση, λοιπόν, τα αποτελέσματα αυτά εξάγονται τα τελικά συμπεράσματα της διατριβής.

Φυσικές Επιστήμες ➨ Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική

Επιστήμες Μηχανικού και Τεχνολογία ➨ Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ

Οικολογική δρομολόγηση

Context awareness

Eco-routing

Gegeneral regression neural networks

Επικοινωνία οχήματος με υποδομή

Φυσικές Επιστήμες

Vehicular consumption forecast

Επιστήμες Μηχανικού και Τεχνολογία

Μηχανική μάθηση

Ενεργειακά αποδοτική δρομολόγηση

Energy efficient routing

Vehicle-to-vehicle communication

Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική

Natural Sciences

Support vector regressors

Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ

Πλήρως ηλεκτροκινούμενα οχήματα

Electrical Engineering, Electronic Engineering, Information Engineering

Νικευμένης παλινδρόμησης

Computer and Information Sciences

Παλινδρόμηση διανυσμάτων υποστήριξης

Πρόβλεψη ενεργειακής κατανάλωσης οχημάτων

Collaborative networks

Επικοινωνία μεταξύ οχημάτων

Επίγνωση του πλαισίου χρήσης

Engineering and Technology

Full electric vehicles

Machine learning

Vehicle-to-infrastructure communication

Πολυστρωματικά νευρωνικά δίκτυα

Multilayer perceptrons

Συνεργατικά σχήματα

Ελληνική γλώσσα

Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ)

National Technical University of Athens (NTUA)

Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Επικοινωνιών, Ηλεκτρονικής και Συστημάτων Πληροφορικής

Εθνικό Κέντρο Τεκμηρίωσης και Ηλεκτρονικού Περιεχομένου (ΕΚΤ)

Εθνικό Αρχείο Διδακτορικών Διατριβών

Συλλογή ΕΑΔΔ