L’approccio seguito in questa tesi si ispira al lavoro svolto nell’articolo [27]: il passaggio dalla pianificazione locale del moto a quella globale viene effettuato attraverso l’utilizzo di una metodologia di discretizzazione della pista e la costruzione di un grafo orientato.
Figura 2.2. Rappresentazione del settore e
delle celle di frontiera Il circuito viene diviso in settori, i qua-
li prevedono alla frontiera una discretiz- zazione delle posizioni e velocità che la macchina può assumere come stato inizia- le o finale sul tratto locale (vedi figura 2.2): ogni posizione finale del settore corrente è la posizione finale del settore successi- vo; le posizioni iniziali del settore corrente invece, sono identiche alle posizioni finali del settore precedente; così facendo, ogni settore prevede che il proprio spazio di ini-
zio e fine sia partizionato in un numero finito di celle, che associamo ai nodi di un grafo. Se l’intero tracciato è diviso in Nssettori (di curve e rettilinei), allora si ottiene la sequenza
di settori S1, S2, . . . , SNs, assumendo che SNs+1≡ S1.
Figura 2.3.Rappresentazione di settori adiacenti
All’interno del circuito, due no- di sono tra di loro connessi se nel tracciato si trovano su setto- ri adiacenti (vedi figura 2.3), e se esiste una sequenza di manovre ammissibile (WORDS), generata dall’alfabeto esposto nel paragra- fo 2.2.2, in modo tale che il veico- lo sia in grado di muoversi dalla cella iniziale a quella finale. Nei capitoli 4 e 3 vengono discusse le sequenze di manovre che risolvono la pianificazione locale in settori rettilinei e curvi, mostrando anche dei risultati numerici sul problema affrontato. Inoltre, ogni arco del grafo prevede un costo che indica il tempo necessario alla macchina per passare da una cella all’altra seguendo la sequenza di manovre ammissibile.
Il percorso a costo minimo che congiunge una cella iniziale con un’altra finale sull’intero tracciato rappresenta la soluzione del problema di pianificazione globale della traiettoria: la cella iniziale è la posizione che la macchina possiede all’inizio (assieme alla velocità), mentre il nodo finale del grafo rappresenta la posizione e la velocità che il veicolo raggiun- ge seguendo la sequenza di manovre ottime che permettono di terminare il giro; infine, il costo che congiunge il nodo iniziale a quello finale indica il tempo speso per completare il giro del circuito.
Un approccio di questo tipo, ottenuto discretizzando i casi di entrata ed uscita da ogni settore in un numero finito di casi e sviluppando un grafo che connette tutte le posizioni che prevedono una sequenza di manovre ammissibile, permette di eseguire un controllo ottimo della traiettoria sulla macchina in tempo reale: infatti, una volta determinate le soluzioni ottime che esistono tra le celle del circuito in maniera off-line, è sufficiente costruire il grafo che, tramite una ricerca della posizione ottima più vicina a quella che la macchina assume in ogni istante, fornisca in tempo reale la sequenza di manovre ottime che permettono di completare la gara nel minor tempo possibile; la pianificazione globale diventa un semplice problema di cammino minimo, ed il grafo può essere interrogato con i tradizionali algoritmi di ricerca noti in letteratura (es: Dijkstra e Bellman-Ford).
Capitolo 3
Analisi numerica della manovra in
curva
3.1
Applicazioni e librerie per il controllo ottimo
Per risolvere problemi di controllo ottimo esistono software che implementano delle inter- facce dedicate: un’interfaccia è un software che aiuta l’utilizzatore a preparare tutti i dati necessari a risolvere il problema, per passarli ad un risolutore (solver) che ha il compito di trovare la soluzione. Esistono due tipologie di interfacce: quelle di controllo ottimo (OCP) gestiscono le procedure di discretizzazione e trascrizione del problema, mentre le interfacce di programmazione non lineare (NLP) lasciano questo compito all’utilizzatore (vedi figura 3.1). PROBLEMA DI CONTROLLO OTTIMO PROBLEMA DI PROGRAMMAZIONE NON LINEARE SOVER NLP SOLUZIONE DISCRETIZZAZIONE E TRASCRIZIONE INTERFACCIA NLP INTERFACCIA OCP
Figura 3.1. Diagramma di Flusso
Le interfacce più utilizzate sono:
• ACADO (Automatic Control And Dynamic Optimization) Toolkit è un ambiente soft- ware ed una raccolta di algoritmi per il controllo automatico e l’ottimizzazione dinamica, che fornisce un insieme di strumenti per utilizzare algoritmi di controllo
ottimo diretto, tra cui il controllo predittivo, stima dei parametri e delle variabili di stato e ottimizzazione robusta1.
• AMPL (A Mathematical Programming Language) è un linguaggio ad alto livello, svi- luppato dai laboratori Bell, per descrivere e risolvere grossi e complicati problemi di programmazione matematica2. AMPL chiama dei solver (come CPLEX, FortMP,
MINOS, IPOPT, SNOPT, KNITRO, ed altri) per ottenere le soluzioni.
• BOCOP (The optimal control solver) è un toolbox open-source per la risoluzione di problemi di controllo ottimo3.
• DIDO (Automatic Control And Dynamic Optimization) è un programma Matlab per risolvere problemi di controllo ottimo basato sulla teoria pseudospettrale4.
• ICLOCS (Imperial College London Optimal Control Software) è un software per la risoluzione di problemi di controllo ottimo5implementato in Matlab .
• TACO (Toolkit for AMPL Control Optimization) definisce alcune estensioni per AMPL che permettono una formulazione elegante dei problemi di controllo ottimo6.
• PSOPT (Pseudospectral Optimal Control Solver) è un software open-source che utilizza metodi di collocazione diretta, con discretizzazioni locali e pseudospettrali, per la risoluzione del problema di controllo ottimo7. I metodi pseudospettrali risolvono
i problemi di controllo ottimo approssimando le variabili dipendenti dal tempo utilizzando polinomi globali, come funzioni di Legendre o Chebyshev. La soluzione viene fornita dal solver IPOPT (o, in alternativa, da SNOPT).
• GPOPS−II (General-Purpose Pseudospectral Optimal Control Software) è un nuovo software per controllo ottimo, utilizzato con Matlab , che implementa un nuovissi- mo metodo Pseudospettrale hp-adattivo con quadratura integrale Legendre-Gauss- Radau per la risoluzione generale dei problemi di controllo ottimo non lineari8.
Con l’utilizzo di GPOPS−II il problema di controllo ottimo viene trascritto come un problema di programmazione non lineare, la cui soluzione viene fornita da uno dei due solver compresi nel software, SNOPT e IPOPT.
Nel nostro lavoro abbiamo deciso di utilizzare GPOPS−II visto che:
• in generale, GPOPS−II è in grado di risolvere un’ampia gamma di problemi, im- piegando metodi di mesh refinement che offrono soluzioni precise, e permettendo una grande flessibilità nella formulazione del problema di controllo ottimo; • utilizza metodi pseudospettrali;
• permette una formulazione estremamente generale del problema di controllo otti- mo;
• permette l’inclusione di vincoli sui parametri del problema, sulle variabili di stato e di controllo, sul percorso da seguire e sull’integrale della funzione obiettivo; • permette la suddivisione del problema in fasi;
1vedi http://sourceforge.net/projects/acado/ 2vedi http://www.ampl.com 3vedi http://www.bocop.org/ 4vedi http://www.elissarglobal.com/academic/get-dido/try-dido/ 5vedi http://www.ee.ic.ac.uk/ICLOCS/ 6vedi http://www.iwr.uni-heidelberg.de/groups/optimus/software/ 7vedi http://www.psopt.org/ 8vedi http://www.gpops2.com/
20
• utilizza il metodo delle differenze finite sparse del primo e del secondo ordine per calcolare tutte le derivate richieste;
• richiede solo l’uso di Matlab .
3.1.1
Risolutori per la programmazione non lineare
Un solver è un software utilizzato per calcolare la soluzione numerica di un problema di controllo ottimo. I più comuni sono:
• IPOPT (Interior Point OPTimizer) è una libreria software per l’ottimizzazione non lineare su larga scala di sistemi continui. È stato progettato per trovare soluzioni (locali) di problemi di ottimizzazione matematica.
• KNITRO è una libreria software di ottimizzazione in grado di trovare soluzioni sia per modelli continui (con o senza vincoli), sia modelli discreti (con variabili intere o binarie). KNITRO è stato sviluppato in primo luogo per trovare la soluzione ottima locale su larga scala di problemi continui non lineari.
• SNOPT (Sparse Nonlinear OPTimizer) è una libreria software commerciale per risol- vere problemi di ottimizzazione (lineare e non lineare) su larga scala. È particolar- mente efficiente nel trovare la soluzione di problemi non lineari le cui funzioni e i cui gradienti sono computazionalmente costosi da valutare.