Multiagent decision making for lane-free traffic

Abstract

The technological and methodological progress in the field of transportation, and more specifically in vehicle automation, gives rise to research endeavours that address the existence and incorporation of Automated Vehicles (AVs) in traffic. In a future era of traffic environments without human-driven vehicles, concepts that today appear deeply-rooted might become outdated due to the enhanced observational, computational and communication capabilities of AVs when compared to human drivers. Clearly, the communication capabilities of AVs—introducing the notion of Connected and Automated Vehicles (CAVs)—unfold unprecedented possibilities for coordinated behaviour. To this end, TrafficFluid is a research project that examines the abandonment of the lane-principle in environments solely populated with CAVs. The two primary investigated aspects involve: (a) lane-free vehicle movement, meaning that CAVs are no longer restricted to specific lane-placements and can fully mobilize the available road; and (b) nudging, that is, CAVs can also react with smooth 2-dimensional movements according to the behaviour of other CAVs located in the back, thus assisting faster vehicles wishing to overtake. In the present thesis we investigate lane-free traffic with controllable CAVs under a multiagent environment. As such, each CAV is modeled as an agent, and we put forward novel approaches for multiagent decision making of CAVs in this newly-found domain. Firstly, we introduce a Factor Graph structure considering the local interactions of nearby agents that evaluates the goals regarding their individual desired speed and collision avoidance. Then, with the use of Max-Sum, a message-passing algorithm, the communicating agents exchange locally calculated messages and can then decide upon their action in a tractable way based on the intents of nearby agents as well, thereby resulting in collaborative behaviour. The local utility functions rely on a fitting ellipsoid form of Artificial Potential Fields, which effectively quantifies the risk of collision between two agents. This formulation has also resulted in extensions for single-agent Reinforcement Learning approaches and in more inclusive frameworks where external non-communicating agents occupy the road as well and introduce uncertainty to the problem. Moving forward, we focus on the message-passing algorithm and its inherent limitation regarding operation in a continuous space. In particular, the lane-free domain is a continuous one, while the Max-Sum algorithm targets discretized spaces and existing extensions towards that direction have unmet requirements for the domain of interest. To tackle this we propose the embedding of Quadtrees in Max-Sum, a tree data structure stemming from computational geometry that can approximate a 2-dimensional action space of the variables. Consequently, all locally-exchanged messages—that contain evaluation of the variable space—have a Quadtree representation that is constructed based on our approach, which results in a dynamic discretization procedure of the continuous domain. Our experimental evaluation shows that Max-Sum with Quadtrees can automatically adapt to the intensity of the problem and select additional discrete points that avoid collisions when compared to an a-priori set of specified discrete points. Then, we shift our attention towards more realistic communication frameworks, along with a reliance on other components as fallback-safety mechanisms and underlying control of CAVs. To accomplish this, we present a hybrid method consisting of a rule-based mechanism that we devise, and an updated Factor Graph approach that is distributed and considers more realistic (and limited) communication among agents based on broadcasting. The instrumental element of this approach is the introduction of dynamic lateral regions, a novel technique that allows the agents to obtain a structured representation of the surrounding lane-free traffic environment. We utilize this representation by employing models stemming from the literature for the control and regulation of agents according to safety rules. As such, the agents’ control variable, that the updated Factor Graph formulation coordinates, is now a strategic and high-level action, that of the desired lateral alignment—i.e., how can the agents be placed laterally in coordination so as to collaboratively enable faster vehicles to advance in a timely manner. The realistic communication framework for the Factor Graph is akin to the asynchrony of agents’ variable updates, while the messages calculation of Max-Sum assumes a synchronized update for the agents. Therefore, we provide Conditional Max-Sum as an extension of Max-Sum with a revised equation for the messages’ calculation, considering the relative timing of the connected agents’ upcoming updates. Experimental evaluation is conducted in both static and large-scale environments, where the proposed hybrid formulation showcases high adeptness to intense conditions, and Conditional Max-Sum exhibits higher efficiency regarding speed and comfort of agents when compared to the standard message-passing method. Finally, we present TrafficFluid-Sim, a lane-free microscopic simulator that extends the well-established SUMO simulation infrastructure to model lane-free traffic environments, allowing vehicles to be located at any lateral position, disregarding standard notions of car-following and lane-change maneuvers that are typically embedded within a (lane-based) simulator. A dynamic library has been designed for traffic monitoring and lane-free vehicle movement control, one that does not impose any inter-tool communication overhead that standard practices introduce; and enables the emulation of vehicle-to-vehicle and vehicle-to-infrastructure communication. Outside of the simulation needs on the above-mentioned research endeavours, TrafficFluid-Sim is also utilized in more complex lane-free simulation environments and emerging applications that are unique to lane-free traffic. In summary, the main contributions of this thesis are the following. Initially, we propose a formulation for Collaborative multiagent decision making in lane-free traffic, then we put forward Max-Sum with Quadtrees for decentralized coordination in continuous domains. Following that, we devise a method for Lane-free vehicle movement with dynamic lateral regions and examine the possibilities for Asynchronous decision making with the Conditional Max-Sum algorithm. Lastly, we develop a tool for Lane-free microscopic simulation of connected and automated vehicles.

Η πρόοδος της τεχνολογίας και των μεθόδων στον τομέα των μεταφορών, και πιο συγκεκριμένα στον αυτοματισμό των οχημάτων, οδηγεί σε ερευνητικές προσπάθειες που εξετάζουν την ύπαρξη και την ενσωμάτωση Αυτοματοποιημένων Οχημάτων (Automated Vehicles, AV) στην κυκλοφορία. Σε μια μελλοντική εποχή που θα υπάρχουν περιβάλλοντα κυκλοφορίας χωρίς οχήματα οδηγούμενα από ανθρώπους, έννοιες που σήμερα φαίνονται βαθιά ριζωμένες μπορεί μελλοντικά να ξεπεραστούν, λόγω των βελτιωμένων δυνατοτήτων παρατήρησης, υπολογιστικής ισχύος και επικοινωνίας των AV σε σύγκριση με τους ανθρώπινους οδηγούς. Σαφώς, οι δυνατότητες επικοινωνίας των AV—εισάγοντας την έννοια των Συνδεδεμένων και Αυτοματοποιημένων Οχημάτων (Connected and Automated Vehicles, CAV)—παρουσιάζουν νέες δυνατότητες για συντονισμένη συμπεριφορά. Για αυτό το σκοπό, το TrafficFluid είναι ένα ερευνητικό έργο που εξετάζει την εγκατάλειψη της έννοιας της λωρίδας σε περιβάλλοντα που αποτελούνται αποκλειστικά με CAV. Οι δύο κύριες πτυχές που εξετάζονται στο TrafficFluid αφορούν: (α) κίνηση οχημάτων χωρίς λωρίδες, που σημαίνει ότι τα CAV δεν περιορίζονται πλέον σε συγκεκριμένες χωροθετήσεις με βάση την ύπαρξη λωρίδων, αλλά μπορούν να κινούνται πλήρως ελεύθερα εντός του διαθέσιμου δρόμου, και (β) nudging (ώθηση), δηλαδή, τα CAV μπορούν να αντιδράσουν με ομαλές κινήσεις, σύμφωνα με τη συμπεριφορά άλλων οχημάτων που βρίσκονται στο πίσω μέρος, βοηθώντας έτσι τα ταχύτερα οχήματα που επιθυμούν να προσπεράσουν. Στην παρούσα διατριβή μελετάμε την κυκλοφορία χωρίς λωρίδες με ελεγχόμενα CAV ως ένα πολυπρακτορικό περιβάλλον (multiagent environment). Ως εκ τούτου, κάθε CAV έχει τη μορφή ενός πράκτορα, και προτείνουμε καινοτόμες προσεγγίσεις για τη λήψη αποφάσεων των CAV σε αυτό το νέο περιβάλλον. Αρχικά, μοντελοποιούμε το πρόβλημα με μια δομή γράφου Factor Graph που ενσωματώνει τις αλληλεπιδράσεις γειτονικών πρακτόρων και αξιολογεί τους στόχους που αφορούν την επιθυμητή ταχύτητα του εκάστοτε πράκτορα αλλά και την αποφυγή συγκρούσεων. Στη συνέχεια, με τη χρήση του Max-Sum, ενός αλγόριθμου μετάδοσης μηνυμάτων, πραγματοποιείται ένας τοπικός υπολογισμός μηνυμάτων από τη πλευρά του κάθε πράκτορα, με σκοπό να μπορούν να λάβουν αποφάσεις με βάση και τις προθέσεις των κοντινών τους πρακτόρων, κάτι που έχει ως αποτέλεσμα τη συντονισμένη συμπεριφορά. Οι τοπικές συναρτήσεις αξιολόγησης βασίζονται σε μια προσαρμοσμένη ελλειψοειδή μορφή Artificial Potential Fields, που ποσοτικοποιεί αποτελεσματικά τον κίνδυνο σύγκρουσης μεταξύ δύο πρακτόρων. Η συγκεκριμένη προσέγγιση έχει αποτελέσει τη βάση για επεκτάσεις στην Ενισχυτική Μάθηση σε περιβάλλον ενός πράκτορα, καθώς και σε ένα πιο διευρυμένο πλαίσιο, όπου ο αλγόριθμος μπορεί πλέον να ενσωματώσει την ύπαρξη εξωτερικών οχημάτων που δεν επικοινωνούν με τους πράκτορες, εισάγοντας αβεβαιότητα στο πρόβλημα. Στη συνέχεια, εστιάζουμε την προσοχή μας στον αλγόριθμο μετάδοσης μηνυμάτων και τον εγγενή περιορισμό του σχετικά με την εφαρμογή του σε συνεχείς χώρους. Συγκεκριμένα, το περιβάλλον κυκλοφορίας χωρίς λωρίδες είναι συνεχές, ενώ ο αλγόριθμος Max-Sum στοχεύει σε διακριτούς χώρους και οι υπάρχουσες επεκτάσεις προς αυτή την κατεύθυνση έχουν απαιτήσεις που δεν συνάδουν με το πεδίο εφαρμογής. Για την αντιμετώπιση αυτού του προβλήματος, προτείνουμε την ενσωμάτωση των Quadtrees στον Max-Sum, μια δεντρική δομή δεδομένων που προέρχεται από την υπολογιστική γεωμετρία και μπορεί να προσεγγίσει έναν διδιάστατο χώρο αποφάσεων. Κατά συνέπεια, όλα τα τοπικά μηνύματα—που περιέχουν αξιολόγηση του χώρου των μεταβλητών—έχουν πλέον μία Quadtree αναπαράσταση που κατασκευάζεται αυτόματα με βάση τη προσέγγισή μας, η οποία οδηγεί σε ένα μηχανισμό δυναμικής διακριτοποίησης του συνεχούς χώρου. Η πειραματική αξιολόγηση δείχνει ότι ο Max-Sum με Quadtrees μπορεί να προσαρμοστεί στην δυσκολία του προβλήματος, επιλέγοντας αυτόματα περισσότερα διακριτά σημεία για την αποφυγή συγκρούσεων, σε σύγκριση με ένα προκαθορισμένο σύνολο διακριτών σημείων.Έπειτα, στρέφουμε την προσοχή μας σε πιο ρεαλιστικά περιβάλλοντα επικοινωνίας, μαζί με την χρήση άλλων συνθετικών στοιχείων ως μηχανισμών ασφαλείας και βασικού ελέγχου των CAVs. Για να το επιτύχουμε αυτό, παρουσιάζουμε μια υβριδική μέθοδο που αποτελείται από έναν μηχανισμό κανόνων για το όχημα, και μία αναθεωρημένη Factor Graph προσέγγιση που είναι πλέον κατανεμημένη και λαμβάνει υπόψη πιο ρεαλιστική (και περιορισμένη) επικοινωνία μεταξύ των πρακτόρων βασισμένη σε αναμετάδοση πληροφοριών. Ένα βασικό στοιχείο αυτής της προσέγγισης είναι η χρήση δυναμικών πλευρικών περιοχών, μιας νέας τεχνικής ή οποία παρέχει στους πράκτορες μια δομημένη αναπαράσταση των κοντινών οχημάτων. Οι πράκτορες αξιοποιούν αυτή την αναπαράσταση και ενσωματώνουν μοντέλα που προέρχονται από τη βιβλιογραφία για τον έλεγχό τους, αλλά και για τον καθορισμό κανόνων ασφαλείας. Ως εκ τούτου, οι μεταβλητές που συντονίζει η νέα μοντελοποίηση Factor Graph αντιστοιχούν πλέον σε μια πιο στρατηγική ενέργεια, αυτή της επιθυμητής πλευρικής ευθυγράμμισης, δηλαδή, το πώς μπορούν οι πράκτορες να τοποθετηθούν πλευρικά, ώστε να επιτευχθούν οι επιθυμητές προσπεράσεις πιο έγκαιρα και με συντονισμένες κινήσεις. Το ρεαλιστικό πλαίσιο επικοινωνίας των πρακτόρων στο Factor Graph συνδέεται με την ασύγχρονη ενημέρωση των μεταβλητών τους, ενώ ο υπολογισμός των μηνυμάτων του Max-Sum προϋποθέτει συγχρονισμένη ενημέρωση μεταξύ των πρακτόρων. Συνεπώς, παρέχουμε τον Conditional Max-Sum ως επέκταση του Max-Sum με μια αναθεωρημένη εξίσωση για τον υπολογισμό των μηνυμάτων, λαμβάνοντας υπόψη το σχετικό χρονισμό των επικείμενων ενημερώσεων μεταξύ συνδεδεμένων πρακτόρων. Η πειραματική διαδικασία διεξάγεται τόσο σε στατικά όσο και σε περιβάλλοντα μεγάλης κλίμακας, όπου η προτεινόμενη υβριδική προσέγγιση παρέχει υψηλές επιδόσεις, ακόμα και σε πιο απαιτητικές συνθήκες, ενώ ο Conditional Max-Sum επιδεικνύει καλύτερη απόδοση όσον αφορά στην ταχύτητα και στην άνεση των πρακτόρων σε σύγκριση με την υπάρχουσα μέθοδο υπολογισμού των μηνυμάτων. Τέλος, παρουσιάζουμε το TrafficFluid-Sim, έναν προσομοιωτή για περιβάλλοντα χωρίς λωρίδες στο μικροσκοπικό επίπεδο, ο οποίος επεκτείνει τον υφιστάμενο προσομοιωτή SUMO με αρκετά διαδεδομένη χρήση σε συμβατικά περιβάλλοντα με λωρίδες. Για τη μοντελοποίηση κυκλοφορίας χωρίς λωρίδες, πλέον τα οχήματα έχουν την ελευθερία να βρίσκονται σε οποιαδήποτε πλευρική θέση, αγνοώντας τις τυποποιημένες έννοιες των ελιγμών αλλαγής λωρίδας που είναι συνήθως ενσωματωμένες σε έναν προσομοιωτή. Αναπτύχθηκε μια δυναμική βιβλιοθήκη (API) για την άμεση παρακολούθηση της κυκλοφορίας και τον έλεγχο της κίνησης των οχημάτων, η οποία δεν προκαλεί καμία επιβάρυνση επικοινωνίας, κάτι που οι υπάρχουσες πρακτικές συνήθως επιβάλλουν. Μέσω του API, μπορούν επίσης να προσομοιωθούν γνωστά μοντέλα επικοινωνίας, όπως μεταξύ οχημάτων (vehicle-to-vehicle) και επικοινωνία οχημάτων με κάποια υποδομή (vehicle-to-infrastructure). Εκτός από τις ανάγκες προσομοίωσης για την παρούσα διατριβή, το TrafficFluid-Sim έχει αναπτυχθεί και για να υποστηρίξει τις ανάγκες πιο πολύπλοκων περιβαλλόντων, καθώς και νέες εφαρμογές κυκλοφορίας με χαρακτηριστικά που αφορούν αποκλειστικά σε περιβάλλοντα χωρίς λωρίδες κυκλοφορίας. Συνοψίζοντας, οι κύριες συνεισφορές της παρούσας διατριβής είναι οι ακόλουθες. Αρχικά, προτείνουμε μια μοντελοποίηση για τη συνεργατική λήψη αποφάσεων πολλαπλών πρακτόρων σε περιβάλλοντα χωρίς λωρίδες κυκλοφορίας. Στη συνέχεια παρουσιάζουμε το Max-Sum με Quadtrees για αποκεντρωμένο συντονισμό σε συνεχείς χώρους. Έπειτα, προτείνουμε μια μέθοδο για κίνηση οχημάτων αξιοποιώντας δυναμικές πλευρικές περιοχές, και εξετάζουμε τις δυνατότητες για ασύγχρονη λήψη αποφάσεων με τον αλγόριθμο Conditional Max-Sum. Τέλος, αναπτύσσουμε ένα εργαλείο για προσομοίωση χωρίς λωρίδες που αφορά CAVs.