Design, implementation and benchmarking of a two-stage local planner: graph search and quadratic programming smoothing

Autonomous driving in urban environments offers several advantages, including improved road safety and more efficient vehicle utilization. Within a modular autonomous driving architecture, the local path planner plays a central role, as it is responsible for computing the local path that the vehicle must follow. In many real-world scenarios, this task is strongly influenced by static obstacles, such as parked vehicles, road works, and lane narrowings, which may require avoidance maneuvers even in constrained spaces. Under these conditions, it is essential to generate safe, collision-free paths while ensuring comfort. This thesis presents a comparative evaluation of local planning strategies for static-obstacle avoidance in urban scenarios. The already implemented local planning algorithm is compared with an alternative algorithm, implemented and integrated within the same software, in order to use a common simulation environment and the same measurement and data-logging setup. Both approaches adopt a modular two-stage structure. In the first stage, a graph search produces a drivable, collision-free raw path. In the second stage, a quadratic programming problem refines the raw path by computing a nearby path that improves smoothness and comfort while preserving feasibility. The two approaches are compared through a module-by-module benchmark, evaluating the two graph-search stages, the two quadratic programming stages and the complete pipelines. The analysis first focuses on the performance delivered by each module and then examines execution time. In addition, further trade-off analyses are reported for the two graph-search solvers, relating geometric quality and minimum static-obstacle clearance to execution time.

La guida autonoma in ambito urbano offre diversi vantaggi, tra cui un miglioramento della sicurezza stradale e un utilizzo più efficiente dei veicoli. In un’architettura modulare di guida autonoma, il pianificatore locale del percorso svolge un ruolo centrale, ovvero ha il compito di calcolare il percorso locale che il veicolo deve seguire. In molti scenari reali, questo compito è fortemente condizionato dalla presenza di ostacoli statici, come veicoli in sosta, cantieri e restringimenti, che possono richiedere manovre di evitamento anche in spazi limitati. In tali condizioni è fondamentale generare percorsi sicuri e privi di collisioni, garantendo allo stesso tempo comfort. Questa tesi presenta una valutazione comparativa di strategie di pianificazione locale per l’evitamento di ostacoli statici in scenari urbani. L’algoritmo di pianificazione locale già implementato viene confrontato con un algoritmo alternativo, implementato e integrato nello stesso software, così da disporre di un ambiente di simulazione comune e della stessa configurazione di misurazione e acquisizione dati. Entrambi gli approcci adottano una struttura modulare articolata in due fasi. Nella prima fase, una ricerca grafo produce un percorso grezzo percorribile e privo di collisioni. Nella seconda fase, un problema di programmazione quadratica raffina il percorso grezzo calcolando un percorso vicino ad esso che migliora la regolarità e il comfort, preservando la fattibilità. I due approcci sono stati confrontati tramite un benchmark modulo per modulo, mettendo a confronto le due ricerche grafo, i due problemi di programmazione quadratica e i due algoritmi completi. L’analisi si focalizza inizialmente sulle prestazioni offerte da ciascun modulo e poi passa a esaminare i tempi di esecuzione. Inoltre, per le due ricerche grafo viene riportata un’ulteriore analisi dei trade-off, mettendo in relazione la qualità geometrica e la minima distanza dall’ostacolo statico più vicino con i tempi di esecuzione.