Κατάλογος Εκδηλώσεων

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

Παντελή Γιανκουλίδη

με θέμα

Δενδρική Αναζήτηση Monte Carlo για Αυτόνομη Οδήγηση σε Απαλλαγμένη από Λωρίδες Κυκλοφορία 
Monte Carlo Tree Search for Autonomous Driving in Lane-Free Traffic Settings

Εξεταστική Επιτροπή

Καθηγητής Γεώργιος Χαλκιαδάκης (επιβλέπων)
Αναπληρωτής Καθηγητής Βασίλης Σαμολαδάς
Καθηγητής Ιωάννης Παπαμιχαήλ (ΜΠΔ)

Περίληψη

Το περιβάλλον οδήγησης χωρίς λωρίδες κυκλοφορίας είναι ένα πρόσφατα προτεινόμενο παράδειγμα περιβάλλοντος κίνησης οχημάτων, το οποίο αφαιρεί την έννοια των λωρίδων κυκλοφορίας σε περιπτώσεις δρόμων όπου υπάρχουν μόνο αυτόνομα οχήματα και οδηγεί σε μεγαλύτερη εκμετάλλευση της χωρητικότητας του δρόμου.
Αν και έχει εισαχθεί πρόσφατα, σημαντική έρευνα έχει εκπονηθεί πάνω στο περιβάλλον οδήγησης χωρίς λωρίδες κυκλοφορίας.
Ωστόσο, αλγόριθμοι σχεδίασης βασισμένοι σε βιβλιογραφία τεχνητής νοημοσύνης δεν έχουν ακόμα ερευνηθεί. Σε αυτή την εργασία, επεκτείνουμε την έρευνα όσο αφορά τις στρατηγικές κίνησης οχημάτων σε περιβάλλοντα οδήγησης χωρίς λωρίδες κυκλοφορίας, εισάγοντας μια νέα προσέγγιση στο πρόβλημα.
(MCTS), ένας δημοφιλής αλγόριθμος απόφασης σε αλυσίδες Μαρκόβ, εφαρμόζεται στο πρόβλημα.

Εισάγουμε μία νέα πρόταση για το πρόβλημα της αυτόνομης οδήγησης χωρίς λωρίδες κυκλοφορίας με τη χρήση αλγορίθμων σχεδίασης και ερευνούμε την αποτελεσματικότητά του σε δύο διαφορετικές εκδοχές ανάλογα με την δυνατότητα επικοινωνίας μεταξύ των οχημάτων και των ίδιων των επιλεγόμενων αλγόριθμων.
Στην πρώτη εκδοχή, κάθε όχημα δρα ανεξάρτητα από τα υπόλοιπα σύμφωνα με μια προσαρμογή του περιβάλλοντος χωρίς λωρίδες κυκλοφορίας κατάλληλη για τον 
MCTS αλγόριθμο. Η πρόταση που εισάγουμε λαμβάνει υπόψη τους δύο αντικειμενικούς στόχους των οχημάτων εν κινήσει, δηλαδή την αποφυγή συγκρούσεων και την κίνηση με μια προεπιλεγμένη επιθυμητή ταχύτητα. Μολονότι η προσέγγιση αυτή δίνει ικανοποιητικά αποτελέσματα, δεν λαμβάνει υπόψη της την αλληλεπίδραση μεταξύ των οχημάτων. Για κάθε όχημα, τα υπόλοιπα οχήματα είναι απλώς εμπόδια κινούμενα με σταθερή ταχύτητα. Εισάγωντας την επικοινωνία μεταξύ οχημάτων, μπορούμε επιπλέον να υπολογίσουμε αυτές τις αλληλεπιδράσεις και την επίπτωση τους στη λήψη αποφάσεων. 

Λαμβάνοντας υπόψη τα προηγούμενα, εισάγουμε στην δεύτερη εκδοχή, εναν πρόσφατα προτεινόμενο αλγόριθμο για σχεδίαση σε πολυπρακτορικά περιβάλλοντα βασιζόμενο στον 
MCTS και σε Coordination Graphs.
Με βάση τον αλγόριθμο αυτό, τα οχήματα ανταλλάσουν μηνύματα που επηρεάζουν τις αποφάσεις τους, συμβάλλοντας σε μια συντονισμένη διαδικασία αποφάσεων.

Στη συνέχεια, μια σειρά αναλυτικών πειραμάτων μετράει αντικειμενικά την ποιότητα των προτεινόμενων δύο λύσεων. Η πειραματική διαδικασία έχει δύο διαφορετικές φάσεις. Στην πρώτη φάση, η απόδοση του απλού MCTS 
εξετάζεται σε μια σειρά από σενάρια δρόμων με πολλά οχήματα σε αυτοκινητόδρομο, όπου όλα τα οχήματα εφαρμόζουν τον MCTS ανεξάρτητα. Υπολογίζουμε την αποτελεσματικότητά του μετρώντας τις συγκρούσεις μεταξύ οχημάτων και την μέση απόκλιση από την επιθυμητή ταχύτητα, σε σενάρια που η χωρητικότητα του δρόμου σε οχήματα είναι μεγαλύτερη από αυτή των δρόμων με λωρίδες κυκλοφορίας. 

 Τέλος, στην δεύτερη φάση, η απόδοση του πολυπρακτορικού αλγορίθμου εξετάζεται για τρεις συγκεκριμένες περιπτώσεις σεναρίων σε σύντομους δρόμους χωρίς λωρίδες κυκλοφορίας με λίγα οχήματα, και δείχνουμε τις ικανότητες συντονισμού σε σύγκριση με τον απλό 
MCTS αλγόριθμο, με κόστος έναν αυξημένο χρόνο υπολογισμού.

Abstract

Lane-Free traffic is a novel paradigm that lifts the notion of lanes in traffic environments populated (as a first step, only) with autonomous vehicles, resulting in much higher efficiency since the road capacity is better exploited.
Despite its novelty, a significant amount of research on lane-free autonomous driving has been already performed.
However, well-known Artificial Intelligence (AI) intelligent search and decision planning algorithms have not been yet explored in this setting.

To this end, we expand upon the research in lane-free vehicle movement strategies by introducing a different approach to the problem. Monte Carlo Tree Search (MCTS), a popular search algorithm for decision planning in games, is adopted for the problem at hand.
We introduce a formulation for the task of lane-free driving using this algorithm and examine its efficiency under two different settings, which differ with respect to the existence of communication among vehicles, and the very constituents of the basic MCTS algorithm.

In the first setting, each vehicle acts independently from the others according on the formulation of the lane-free environment that is suitable for the MCTS algorithm.
The formulation we introduce addresses the two objectives of the vehicles, namely collision avoidance and reaching or preserving a desired speed of choice.

While this approach gives satisfactory results, it does not take into consideration online interactions among vehicles. For every vehicle, other vehicles are observed as moving obstacles with constant speed.
If we consider communication among vehicles as well, we can additionally model these interactions and examine their influence in their decision making.

As such, in the second setting we address the multiagent nature of the lane-free environment. For that, we adopt a recently introduced multiagent planning algorithm based on MCTS and Coordination Graphs. Essentially, vehicles exchange messages that affect their planning, consequently resulting in a coordinated decision making process.
Then, we provide an extensive set of experiments in order to evaluate our proposed approach under these two settings. Our experimental procedure correspondingly involves two distinct phases. First, the single-agent performance is investigated in scenarios populated with a large number of vehicles in a highway, all employing the  MCTS algorithm independently. We observe the performance by evaluating collision occurrences and deviation from the desired speed in demanding scenarios that exceed the capacity of equivalent lane-based environments.
Finally, we evaluate the multiagent algorithm in three lane-free scenarios that involve a few vehicles, and showcase its increased coordination capabilities compared to the plain MCTS algorithm at the expense of computational time.

Meeting ID: 961 3303 0613
Password: 562637