Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Monte carlo tree search for autonomous driving in lane-free traffic settings

Giankoulidis Pantelis

Simple record


URIhttp://purl.tuc.gr/dl/dias/1C96B21D-8F10-429E-AAFF-D5E7EA7812CC-
Identifierhttps://doi.org/10.26233/heallink.tuc.96157-
Languageen-
Extent64 pagesen
Extent2 megabytesen
TitleMonte carlo tree search for autonomous driving in lane-free traffic settingsen
TitleΔενδρική αναζήτηση Monte Carlo για αυτόνομη οδήγηση σε απαλλαγμένη από λωρίδες κυκλοφορία el
CreatorGiankoulidis Pantelisen
CreatorΓιανκουλιδης Παντεληςel
Contributor [Thesis Supervisor]Chalkiadakis Georgiosen
Contributor [Thesis Supervisor]Χαλκιαδακης Γεωργιοςel
Contributor [Committee Member]Samoladas Vasilisen
Contributor [Committee Member]Σαμολαδας Βασιληςel
Contributor [Committee Member]Papamichail Ioannisen
Contributor [Committee Member]Παπαμιχαηλ Ιωαννηςel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitTechnical University of Crete::School of Electrical and Computer Engineeringen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
DescriptionΔιπλωματική εργασία που εκπονήθηκε στα πλαίσια της πλήρωσης προυποθέσεων λήψης πτυχίου από τη σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Content SummaryLane-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.en
Content SummaryΤο περιβάλλον οδήγησης χωρίς λωρίδες κυκλοφορίας είναι ένα πρόσφατα προτεινόμενο παράδειγμα περιβάλλοντος κίνησης οχημάτων, το οποίο αφαιρεί την έννοια των λωρίδων κυκλοφορίας σε περιπτώσεις δρόμων όπου υπάρχουν μόνο αυτόνομα οχήματα και οδηγεί σε μεγαλύτερη εκμετάλλευση της χωρητικότητας του δρόμου. Αν και έχει εισαχθεί πρόσφατα, σημαντική έρευνα έχει εκπονηθεί πάνω στο περιβάλλον οδήγησης χωρίς λωρίδες κυκλοφορίας. Ωστόσο, αλγόριθμοι σχεδίασης βασισμένοι σε βιβλιογραφία τεχνητής νοημοσύνης δεν έχουν ακόμα ερευνηθεί. Σε αυτή την εργασία, επεκτείνουμε την έρευνα όσο αφορά τις στρατηγικές κίνησης οχημάτων σε περιβάλλοντα οδήγησης χωρίς λωρίδες κυκλοφορίας, εισάγοντας μια νέα προσέγγιση στο πρόβλημα. (MCTS), ένας δημοφιλής αλγόριθμος απόφασης σε αλυσίδες Μαρκόβ, εφαρμόζεται στο πρόβλημα. Εισάγουμε μία νέα πρόταση για το πρόβλημα της αυτόνομης οδήγησης χωρίς λωρίδες κυκλοφορίας με τη χρήση αλγορίθμων σχεδίασης και ερευνούμε την αποτελεσματικότητά του σε δύο διαφορετικές εκδοχές ανάλογα με την δυνατότητα επικοινωνίας μεταξύ των οχημάτων και των ίδιων των επιλεγόμενων αλγόριθμων. Στην πρώτη εκδοχή, κάθε όχημα δρα ανεξάρτητα από τα υπόλοιπα σύμφωνα με μια προσαρμογή του περιβάλλοντος χωρίς λωρίδες κυκλοφορίας κατάλληλη για τον MCTS αλγόριθμο. Η πρόταση που εισάγουμε λαμβάνει υπόψη τους δύο αντικειμενικούς στόχους των οχημάτων εν κινήσει, δηλαδή την αποφυγή συγκρούσεων και την κίνηση με μια προεπιλεγμένη επιθυμητή ταχύτητα. Μολονότι η προσέγγιση αυτή δίνει ικανοποιητικά αποτελέσματα, δεν λαμβάνει υπόψη της την αλληλεπίδραση μεταξύ των οχημάτων. Για κάθε όχημα, τα υπόλοιπα οχήματα είναι απλώς εμπόδια κινούμενα με σταθερή ταχύτητα. Εισάγωντας την επικοινωνία μεταξύ οχημάτων, μπορούμε επιπλέον να υπολογίσουμε αυτές τις αλληλεπιδράσεις και την επίπτωση τους στη λήψη αποφάσεων. Λαμβάνοντας υπόψη τα προηγούμενα, εισάγουμε στην δεύτερη εκδοχή, εναν πρόσφατα προτεινόμενο αλγόριθμο για σχεδίαση σε πολυπρακτορικά περιβάλλοντα βασιζόμενο στον MCTS και σε Coordination Graphs. Με βάση τον αλγόριθμο αυτό, τα οχήματα ανταλλάσουν μηνύματα που επηρεάζουν τις αποφάσεις τους, συμβάλλοντας σε μια συντονισμένη διαδικασία αποφάσεων. Στη συνέχεια, μια σειρά αναλυτικών πειραμάτων μετράει αντικειμενικά την ποιότητα των προτεινόμενων δύο λύσεων. Η πειραματική διαδικασία έχει δύο διαφορετικές φάσεις. Στην πρώτη φάση, η απόδοση του απλού MCTS εξετάζεται σε μια σειρά από σενάρια δρόμων με πολλά οχήματα σε αυτοκινητόδρομο, όπου όλα τα οχήματα εφαρμόζουν τον MCTS ανεξάρτητα. Υπολογίζουμε την αποτελεσματικότητά του μετρώντας τις συγκρούσεις μεταξύ οχημάτων και την μέση απόκλιση από την επιθυμητή ταχύτητα, σε σενάρια που η χωρητικότητα του δρόμου σε οχήματα είναι μεγαλύτερη από αυτή των δρόμων με λωρίδες κυκλοφορίας. Τέλος, στην δεύτερη φάση, η απόδοση του πολυπρακτορικού αλγορίθμου εξετάζεται για τρεις συγκεκριμένες περιπτώσεις σεναρίων σε σύντομους δρόμους χωρίς λωρίδες κυκλοφορίας με λίγα οχήματα, και δείχνουμε τις ικανότητες συντονισμού σε σύγκριση με τον απλό MCTS αλγόριθμο, με κόστος έναν αυξημένο χρόνο υπολογισμού.el
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2023-06-19-
Date of Publication2023-
SubjectMonte Carlo tree searchen
SubjectArtificial Intelligenceen
SubjectMultiagent systemsen
SubjectLane-free drivingen
Bibliographic CitationPantelis Giankoulidis, "Monte carlo tree search for autonomous driving in lane-free traffic settings", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2023en
Bibliographic CitationΠαντελής Γιανκουλίδης, "Δενδρική αναζήτηση Monte Carlo για αυτόνομη οδήγηση σε απαλλαγμένη από λωρίδες κυκλοφορία ", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2023el

Available Files

Services

Statistics