title: Specifying desired orientations for automated vehicles on complex lane-free roundabouts via Dynamic Programming
title: Καθορισμός επιθυμητού προσανατολισμού για αυτόματα οχήματα σε περίπλοκους κυκλικούς κόμβους χωρίς λωρίδες μέσω Δυναμικού Προγραμματισμού

Creators: name: Μαυροειδη Μαρια-Κωνσταντινα
Publisher: name: Technical University of Crete
Year: 2023

description: Road traffic congestion is an increasingly grave social problem that contributes to excessive delays, substantial environmental pollution, and decreased traffic safety. The introduction of automated and connected vehicles could be an effective solution to tackle this problem since they can be promoted to make more appropriate decisions based on information received from the infrastructure, other vehicles, and their sensors.
Path planning for vehicles on large, complex, lane-free roundabouts is challenging due to the geometrical features and frequent conflicts among entering, navigating, and exiting vehicles. A fundamental difficulty is to properly determine the desired vehicle orientations on the roundabout so that vehicles enter the roundabout and move towards their corresponding exits smoothly and safely. The specification of vehicle orientations should consider the resulting trip distance, the angle difference from other vehicles, and the exploitation of the available roundabout surface for efficient traffic flow.
This diploma thesis proposes an optimal control approach to determine optimal vehicle orientations at each point on the roundabout, in dependence on the exit branch, to minimize a weighted summation of the trip distance and the deviation from the circular motion. Analytical solutions for two extreme cases, addressing only the shortest path or the minimum deviation from the circular angle, respectively, are derived. A Dynamic Programming-based (backward Dijkstra) algorithm is employed for the general weighted problem solution to deliver the optimal orientations in a 2-D space-discretized grid of the roundabout surface. In light of the optimal solution, a computationally light near-optimal approach is also proposed. As a challenging case study, the methods are applied to the famous roundabout of Place Charles de Gaulle in Paris, which features a road width of 38 m and comprises 12 bidirectional radial streets, hence a total of 144 origin-destination movements for the vehicles.

 
description: Η κυκλοφοριακή συμφόρηση αποτελεί ένα ολοένα και σοβαρότερο κοινωνικό πρόβλημα που συμβάλλει σε υπερβολικές καθυστερήσεις, σημαντική περιβαλλοντική ρύπανση και μειωμένη ασφάλεια της κυκλοφορίας. Η εισαγωγή αυτοματοποιημένων και διασυνδεδεμένων οχημάτων θα μπορούσε να αποτελέσει αποτελεσματική λύση για την αντιμετώπιση του προβλήματος αυτού, δεδομένου ότι μπορούν να ενθαρρυνθούν ώστε να λαμβάνουν καταλληλότερες αποφάσεις με βάση τις πληροφορίες που λαμβάνουν από την υποδομή, τα άλλα οχήματα και τους αισθητήρες τους.
Ο σχεδιασμός της διαδρομής που οφείλουν να ακολουθούν τα οχήματα σε μεγάλους, πολύπλοκους κυκλικούς κόμβους χωρίς λωρίδες κυκλοφορίας αποτελεί πρόκληση λόγω των γεωμετρικών χαρακτηριστικών τους και των συχνών συγκρούσεων μεταξύ των εισερχόμενων, πλοηγούμενων αλλά και εξερχόμενων οχημάτων. Μια θεμελιώδης δυσκολία είναι ο ορθός προσδιορισμός των επιθυμητών προσανατολισμών των οχημάτων στον κυκλικό κόμβο, έτσι ώστε τα οχήματα να εισέρχονται στον κυκλικό κόμβο και να κινούνται προς τις αντίστοιχες εξόδους τους ομαλά και με ασφάλεια. Ο καθορισμός των προσανατολισμών των οχημάτων θα πρέπει να λαμβάνει υπόψη την προκύπτουσα απόσταση διαδρομής, τη γωνιακή διαφορά από τα άλλα οχήματα και την εκμετάλλευση ολόκληρης της διαθέσιμης επιφάνειας του κυκλικού κόμβου για την αποτελεσματική ροή της κυκλοφορίας.
Η παρούσα διπλωματική εργασία προτείνει μια προσέγγιση βέλτιστου ελέγχου για τον προσδιορισμό των βέλτιστων προσανατολισμών οχημάτων σε κάθε σημείο του κυκλικού κόμβου, με βάση τον εκάστοτε επιλεγμένο κλάδο εξόδου, ώστε να ελαχιστοποιείται ένα σταθμισμένο άθροισμα της απόστασης διαδρομής και της απόκλισης από την κυκλική κίνηση. Παρουσιάζονται αναλυτικές λύσεις για τις δύο ακραίες περιπτώσεις, που αφορούν ξεχωριστά τη συντομότερη διαδρομή και την ελάχιστη απόκλιση από την κυκλική γωνία, αντίστοιχα. Ενώ, για τη γενική λύση του σταθμισμένου αθροίσματος των ανωτέρω, χρησιμοποιείται ένας αλγόριθμος βασισμένος στον δυναμικό προγραμματισμό (αναδρομικός Dijkstra) για να προσδιοριστούν οι βέλτιστοι προσανατολισμοί σε ένα δισδιάστατο χώρο-διακριτό πλέγμα της επιφάνειας του κυκλικού κόμβου. Υπό το πρίσμα της βέλτιστης λύσης, προτείνεται επίσης μια υπολογιστικά ελαφριά σχεδόν βέλτιστη προσέγγιση. Ως μια σύνθετη περίπτωση μελέτης, οι μέθοδοι εφαρμόζονται στον διάσημο κυκλικό κόμβο Place Charles de Gaulle στο Παρίσι, ο οποίος διαθέτει πλάτος 38 m και περιλαμβάνει 12 αμφίδρομους ακτινικούς δρόμους, άρα συνολικά 144 ζεύγη προέλευσης-προορισμού για τα οχήματα.