Multiagent decision making for lane-free traffic
Authors: Τρουλλινός Δημήτριος 
Published: September 2024

Η πρόοδος της τεχνολογίας και των μεθόδων στον τομέα των μεταφορών, και πιο συγκεκριμένα στον αυτοματισμό των οχημάτων, οδηγεί σε ερευνητικές προσπάθειες που εξετάζουν την ύπαρξη και την ενσωμάτωση Αυτοματοποιημένων Οχημάτων (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.