Pro e contro - STUDIO TEORICO SUL CONTROLLO OTTIMO IN TEMPO REALE DI UN SISTEMA NON LINEARE E A

3.3 Modelli

4.1.3 Pro e contro

Il metodo presenta pregi e difetti. Tra i primi, essendo un metodo indiretto, non è limitato alla sola risoluzione di problemi di controllo ottimo, ma a tutti questi ultimi formalizzabili come BVP. Un altro pregio è che il numero di ingressi del sistema non influisce sulla complessità del problema poiché il comando ottimo viene immesso nelle equazioni del costato. Inoltre, dal punto di vista simulativo, è stato in grado di superare alcuni test per i metodi di ottimizzazione (funzioni tipo Rastrigyn o altre).

Tra i contro, risolve solo problemi abbastanza semplici (es manipolatore R), risulta intrattabile per sistemi con molti stati n poiché il sampling dovrà essere fatto su Rn _{e non garantisce di trovare una soluzione in tempi molto brevi ai quali}

siamo interessati (< 1 secondo). Inoltre, nonostante la solo semplicità, i metodi di shooting possono soffrire di problemi dovuti all’integrazione delle equazioni della dinamica [24].

Infine, se non riesce a raggiungere il minimo globale del problema, la soluzione ottenuta potrebbe differire di molto in termini di performance di interesse. Per spiegare meglio questo fatto viene ripreso l’esempio del manipolatore R. Nel caso in cui l’algoritmo sia finito in un minimo locale al termine del numero di iterazioni e la funzione costo ha raggiunto un valore abbastanza basso, è probabile che riesca a soddisfare i vincoli di posizione allo stato finale (dato che sono presenti in J ), ma la massimizzazione della ˙q non è detto che venga soddisfatta, anzi è possibile che la suddetta sia un valore molto diverso da quello desiderato.

4.2 Evolution Tree

La necessità di dover risolvere un problema di controllo ottimo non lineare in maniera molto veloce (< 1 sec), ci porta a considerare la possibilità di dover eseguire e memorizzare dei calcoli fuori linea per poterli poi utilizzare come patterns di riferimento per un ottimizzazione in tempo reale più agevole e immediata. Inoltre, visti i contro di 4.1.3, sarebbe opportuno eseguire queste traiettorie precalcolate in modo da poter verificare in maniera corretta la distanza effettiva da uno stato desiderato del sistema ed uno simulato.

Viene impostato il problema nel seguente modo.

Partiamo dalla formulazione descritta nella sezione 2.2.

Nell’ipotesi che il controllo ottimo u∗(t) possa essere descritto da una combinazione tra un numero finito di archi, ovvero

u ∈ U = {gi(t)} i ∈ [1 . . . l] (4.6)

minij,ti J = φ(x(tk)) subject to ˙x = f (x(t), gi1(t), t) , ∀t ∈ [0t1] .. . ˙x = f (x(t), gij(t), t) , ∀t ∈ [tj−1tj] .. . ˙x = f (x(t), gik(t), t) , ∀t ∈ [tk−1tk] x(t0) = x0 c(xtk) = θ tj− tj−1 ≥ 0 , (4.7)

la soluzione del quale è costituita dalla sequenza degli archi di controllo, gi(t) e

la loro durata temporale ti.

Si fa notare che nel caso in cui la durata temporale degli archi di controllo sia costante e fissata il risultato di (4.7) fornisce la sola sequenza dei gi.

Il controllo u può presentarsi in un numero finito di combinazioni k date dal funzionale g().

In un caso di controllo singolo bang-bang siamo nel caso di l = 2, g(1) = umax

in t ∈ [0 T ], g(2) = umin in t ∈ [0 T ].

Facciamo inoltre le seguenti ipotesi

• il controllo può effettuare uno switch solo in determinati istanti di tempo ts = kT dove k = 0, . . . , n

• lo stato iniziale del sistema è fissato x(t0) = ¯x0 (rimovibile nella sezione 4.3 a

pagina 40 )

Per semplicità, consideriamo t0 = 0. Sotto queste ipotesi, possiamo descrivere

l’evoluzione temporale del sistema con un grafo ad albero orientato G = (V, E) dove V è il set dei nodi e E = V × V è il set degli archi. G viene definito Evolution Tree.

Ogni nodo del grafo rappresenta uno stato, mentre ogni arco rappresenta una combinazione di controlli. Il nodo v0 viene chiamato zero node ed è associato allo

stato x(t0) = ¯x0.

Il j-esimo nodo del grafo vj(kj, uhisj ) rappresenta lo stato del sistema al tempo

t = kjT con una specifica storia di controlli rappresentata dal percorso (unico) dal

nodo zero al nodo vj uhisj = e(v0 → vj), è un arco rappresenta la combinazione di

controlli, data dalla funzione g(∗), nell’intervallo temporale [(k − 1)T, kT ]. kj è la

profondità del nodo (o livello), definita come la somma del numero di archi dallo zero node al nodo j.

Ogni nodo ha un padre (eccetto per il zero node) e 2l _{figli. Da notare che nel}

caso l = 2, l’albero definito in questo modo è un Albero binario (Fig. 4.3).

Senza vincolare l’albero, il numero di nodi alla massima profondità dello stesso risulta 2lkmax

Per frenare la crescita dell’albero, vengono fatte le seguenti ipotesi • smax numero massimo di switch ∀ui ∈ Rm

• tmin

t 0 t1 t2 1 1 1 0 0 0 time x 0 = control = state T T

Figura 4.3: Albero Binario

L’algoritmo si suddivide quindi in due fasi: • Fase Offline

• Fase Online

4.2.1 Fase Offline

Nella fase offline viene costruito l’Evolution Tree tenendo in considerazione smax

and tmin_s . Fatto questo viene esplorato interamente e memorizzato. La fase offline si suddivide quindi in

1. Building : Scegliere la massima profondità dell’albero kmax, tempo finale

massimo tmax

f , massimo numero di switch per input smax, ed il tempo minimo

di permanenza del medesimo comando tsmin. La costruzione dell’albero con i

parametri descritti risulta univoca.

2. Exploring : Esploriamo l’intero Evolution Tree integrando la dinamica ˙x = f (x(t), u(t), t) con un metodo di integrazione a scelta.

Il metodo fin qui descritto rappresenta quindi una ricerca esaustiva (aka forza bruta) di tutto lo spazio delle soluzioni, descritte in maniera finita equivalente al numero di nodi dell’albero. Ciò garantisce che la soluzione ottima del sotto-problema descritto dall’Evolution Tree venga trovata con probabilità 1.

4.2.2 Fase Online

Nella fase Online, il sistema di controllo deve essere in grado di trovare una soluzione al problema di controllo ottimo in un tempo considerato ragionevole per il problema stesso. Nel nostro caso, in cui il task di evoluzione ha una durata di circa 1 secondo, dobbiamo riuscire a risolvere il problema di ottimizzazione a ciclo aperto in qualche centesimo di secondo, ed è proprio per questo motivo che sfruttiamo la conoscenza della dinamica del sistema in determinati patterns, ovvero utilizziamo l’Evolution Tree.

Suddividiamo la fase Online in 2 step: 1. Ottimizzazione globale

2. Ottimizzazione locale Ottimizzazione Globale

Viene richiesto al sistema di massimizzare (o minimizzare) alcune variabili di interesse xmax

α (td) rispettando i vincoli dello stato xcnsβ (td) = ¯xβ in un certo tempo

finale desiderato td massimizzando (o minimizzando) degli indici di performance

integrali wpathPγ_γ=1maxξ(x(k), u(k)). Vengono quindi ispezionati alla profondità kd=

f loor{td−tcomp

T } dell’albero tutti i nodi utilizzando il seguente indice di performance

J (vj|k(vj)=kd) = wcns βmax X β=1 (¯xβ − xcnsβ (vj))2− wmax αmax X α=1 xα(vj) − wpath γmax X γ=1 ξ(x(k), u(k)) (4.8) dove sono stati trasformati i vincoli xcns_β (td) = ¯xβ (hard constraints) in termini

dell’indice di performance wcns

Pβmax

β=1 (¯xβ − xcnsβ (vj))2 (soft constraints). I termini

wcns ≥ 0 ,wmax e wpath sono delle costanti di peso, floor() è la funzione che associa

ad un numero reale la sua approssimazione intera inferiore e tcomp è una stima in

eccesso del tempo richiesto per eseguire le fasi di ottimizzazione globale e locale online. Si sceglie quindi il j-esimo nodo vj (quindi il control path associato) tale che

J (vj) risulti massima/minima.

La funzione ξ(x(k), u(k)) riguarda la parte integrale della funzione costo. Visto che per ogni evoluzione temporale è presente nell’albero solamente un numero finito di nodi, è necessario ricavare la traiettoria degli stati del sistema con metodi di approssimazione / interpolazione, ad esempio utilizzando il metodo dei trapezi.

Remark. Riguardo alla fase di Building, si potrebbe pensare di “guidare” la costruzione dell’albero secondo dei metodi probabilistici “a priori” (es Metodi Monte- Carlo, Simulated annealing), guidando la costruzione dello stesso verso rami con- siderati più probabili secondo qualche criterio. Il problema di una considerazione del genere è che non si conosce a priori l’indice di performance dell’ottimizzazione globale, quindi non abbiamo nessun criterio che ci possa dire se una costruzione particolare o un determinato nodo dell’albero risultino aprioristicamente migliori rispetto ad altri casi.

Indice di performance con parte integrale nulla Nel caso in cui l’indice di performance del problema originale dipenda esclusivamente da variabili dello stato al tempo finale tf, nella forma

J = φ[x(tf)] (4.9)

è possibile riscrivere (4.8) come

J (vj|k(vj)=kd) = wratio βmax X β=1 (¯xβ− xcnsβ (vj))2− αmax X α=1 xα(vj) (4.10) x₁ x₂ (0,0)

Figura 4.4: Sottospazio di ricerca Evolution Tree: esempio x₂(tf)max e x1(tf) = 0

dove wratio = _ww_maxcns. La ricerca del percorso ottimale nell’Evolution Tree risulta

molto semplice perché basta considerare il solo stato dei nodi in una data profondità dell’albero corrispondente al tempo finale desiderato. Inoltre in questo caso, risulta poco efficiente controllare tutti i nodi vj corrispondenti alla profondità kd del grafo

e calcolarne l’indice di performance perché in base alla loro posizione nello spazio degli stati (ogni nodo è associato ad uno stato ammissibile) un nodo potrebbe essere facilmente scartato a priori. Ad esempio nel caso in cui x(t) ∈ R2, sono interessato a massimizzare x2(tf) rispettando il vincolo x1(tf) = 0, posso cercare solo nelle

regioni che rispettano il vincolo e dove mi aspetto di trovare una soluzione (fig4.4). Si consigli quindi in fase di implementazione di tenere in considerazione questo aspetto organizzando i nodi in liste o strutture in base alla loro posizione nello spazio degli stati.

Ottimizzazione Locale

Una volta restituito il comando dalla fase di ottimizzazione globale, è possibile utilizzarlo come punto di partenza per l’ottimizzazione locale, dato che tutti i metodi locali hanno bisogno di un guess iniziale. E’ possibile eseguire un qualsiasi metodo locale, ad esempio Sequential Quadratic Programming, Interior point (richiedono

gradiente), iLQG, o altri. Nel nostro caso si effettua un sampling in un intorno arbitrario dei tempi di switch restituiti dall’ottimizzazione globale. Questo può essere visto come un semplice metodo di shooting, come da figura 4.5. L’intento è quello di migliorare l’indice di performance 4.8 a pagina 37.

Δt

_s1

Δt

_s2

tempi di switch dall'ottimizzazione globale tempi di switch da valutare

Figura 4.5: Ottimizzazione locale: variazione dei tempi di switch dell’ottimizzazione globale (caso con 2 tempi di switch)

Finita questa fase, siamo a conoscenza del controllo da dare in input al sistema e dell’evoluzione degli stati in tutto l’intervallo temporale del task u(ttask) con

ttask ∈ [t0 tf] .

4.2.3 Pro e contro

Tra i vantaggi di questo metodo possiamo notare la rapidità della ricerca di una soluzione “grezza” al problema data dalla ricerca nell’albero del cammino ottimo. Abbiamo la certezza di trovare la soluzione ottima per il problema quantizzato ad albero dato che esploriamo tutte le possibili evoluzioni della dinamica associate, affinando poi il controllo con un’ottimizzazione locale successiva il cui tempo com- putazionale è impostabile in base alle esigenze del problema. Non ci sono possibili errori che provocano lo stop del metodo (es. inversioni di matrici singolari come nel- l’utilizzo del metodo di Newton) e non ci sono casi in cui la soluzione trovata risulti errata per mancata convergenza della soluzione ottima (es. mancata convergenza di metodi quali GPOPS) o per errori computazionali intermedi (es. inversione jacobia- no singolare utilizzando il metodo di Newton come succede utilizzando BVP-4C). Inoltre è possibile impostare “a priori” una soluzione con un numero desiderato di switch, oppure evitare durante le traiettorie restituite dall’albero insiemi particolari nel dominio degli stati ammissibili X (collision avoidance) salvando alcune infor- mazioni aggiuntive ai nodi. In generale è possibile sfruttare qualsiasi informazione ottenibile dalle traiettorie della dinamica del sistema precalcolate.

Come svantaggi notiamo che risulta idoneo solo per problemi in cui è possibile quantizzare in un numero limitato i controlli, non è adatto per un numero elevato

di comandi e di switch del comando, richiede un pre-calcolo fuori linea e lo stato iniziale del sistema per qualsiasi evoluzione risulta fissato.

Notiamo però che questo metodo è l’unico tra quelli provati a rispondere in maniera efficace ed istantanea a problemi abbastanza complessi come il controllo ottimo su un braccio RR con rigidezza fissata ai giunti, caso principale preso in esempio per questa tesi.

4.3 Evolution Network

I vincoli più restrittivi della fase offline dell’Evolution Tree sono • stato iniziale dell’albero fissato x(t0) = ¯x0

• massimo tempo finale del task dell’albero fissato tf

Il primo nonostante per molte applicazioni in robotica è abbastanza usuale avere una posizione di home, nel caso in cui desiderassimo un braccio sempre in movimento, il vincolo è sicuramente una restrizione non di poco conto. Vorremmo quindi poter ricavare un albero con stato iniziale arbitrario e tempo finale arbitrario. Per far questo, consideriamo l’Evolution Tree definito nella fase online, eliminando qualche ipotesi e aggiungendone altre. Ipotesi eliminate:

• smax • tmin s • tmax f • kmax

tolte queste ipotesi che limitavano in parte la crescita esponenziale dell’albero (diminuendo l’esponente), ogni nodo dell’albero ha 2l figli.

Introduciamo prima il concetto di raggiungibilità locale in tempo breve

Definizione 2 (raggiungibilità locale in tempo breve). Un sistema non lineare è detto “raggiungibile localmente in tempo breve” (small-time locally controllable) da x se, per ogni V e per ogni T (arbitrariamente piccoli), RT

V(x) contiene un intorno

di x. RT

V(x) indica l’insieme dei punti raggiungibili da x al tempo T > 0 seguendo

traiettorie che rimangono contenute nell’intorno V di x per t ≤ T . Tornando al problema originale aggiungiamo le seguenti ipotesi

• lo stato del sistema x(t) ∈ Rn _{è vincolato in un insieme convesso e limitato D,}

quindi se lo stato xi, associato al nodo vi è tale per cui xi ∈ D, allora elimina/

il nodo vi dalla rete. Inoltre se vj è il nodo padre di vi e se la traiettoria nello

spazio degli stati associata all’arco e(vi → vj) non è interamente contenuta in

• se per due nodi vi e vj, che corrispondono agli stati associati xi e xj, vale

(xi− xj)TA(xi− xj) < R (4.11)

e se xj è raggiungibile localmente in tempo breve da xi (“small-time locally

controllable”) e viceversa, allora i due nodi sono indistinguibili tra loro, ed uno dei due nodi può essere eliminato

Queste due ipotesi ci permettono di porre un limite all’espansione dell’albero iniziale, poiché il numero di nodi che possono stare all’interno del dominio è un numero finito, qualsiasi sia la lunghezza del funzionale g(), numero di input, numero di stati del sistema (sempre che quest’ultimo sia vincolato in ogni suo componente), A matrice definita positiva e R > 0 scalare. La rete (non più un albero) definita in questo modo è l’Evolution Network.

Quindi, dopo aver costruito la rete in tal senso, possiamo scegliere lo stato iniziale del sistema in maniera arbitraria xd₀ all’interno del dominio in tal modo

xdr₀ = min

(xd₀− xj)TA(xd0− xj) (4.12)

e ricavando l’Evolution Tree associato allo stato iniziale xdr

0 , il quale ha una

profondità non limitata.

L’ipotesi di convessità del dominio degli stati del sistema viene spiegata con la figura 4.6. Se il dominio degli stati X non è convesso significa che esiste almeno una coppia di nodi {v1, v2} associati agli stati {x1, x2} ∈ X tale per cui il segmento

di intersezione ¯x12 tra {x1, x2} non è totalmente contenuto in X. Il segmento ¯x12

rappresenta però proprio il “gap” in modulo (xi− xj)TA(xi− xj) tra i valori degli

stati associati ai nodi in questione. Questo significa che la traiettoria a minima distanza tra i due nodi non è contenuta nel dominio degli stati e potrebbe essere un problema in alcuni casi (esempio macchinina che passa attraverso un muro).

X A B

Figura 4.6: Esempio: Nodi in insieme non convesso. La linea rossa rappresenta la traiettoria per arrivare al nodo A, mentre le linee versi sono le traiettorie che nascono dal nodo B

4.3.1 Pro e contro

Tra i vantaggi possiamo elencare tutti quelli del metodo Evolution Tree, integrando anche la non necessità per il sistema di avere uno stato iniziale fissato, ma di poterlo scegliere interno alla rete, ed un tempo finale di evoluzione tf arbitrario.

Questo libera, in linea teorica, il sistema dal dover eseguire dei task di lunghezza fissata per poi tornare allo stato iniziale, quindi permette di poter eseguire traiettorie con intervallo temporale tendente a infinito. Inoltre non è più richiesto un basso numero di comandi o switch del comando poiché l’intento principale è quello di riempire l’intero spazio degli stati ammissibili per il problema.

Tra gli svantaggi rimane che risulta idoneo solo per problemi in cui è possibile quantizzare in un numero limitato i controlli, richiede un pre-calcolo fuori linea e , rispetto all’Evolution Tree, non è facile gestire sistemi con numero di dimensioni molto elevate e con parametro di indistinguibilità degli stati R molto piccolo poiché porterebbe ad immagazzinare un numero spropositato di dati in memoria. Come ultima cosa, a causa della condizione di unione dei nodi 4.3 una buona parte dei patterns risultano discontinui negli stati. Si consiglia in questi casi di modificare il comando associato all’arco interessato in modo da minimizzare il valore (xi− xj)TA(xi− xj).

Simulazioni

In questo capitolo verranno illustrate delle simulazioni tra i metodi utilizzati per la risoluzione di OCP a ciclo aperto, principalmente GPOPS, IS-BVPS e Evolution Tree. Vengono svolte delle simulazioni con il metodo Evolution Tree con un controllo a ciclo chiuso nmpc sul sistema nominale e perturbato sugli stati. Infine viene riportata una applicazione di esempio: si utilizza il braccio robotico per colpire oggetti e indirizzarli in una certa zona nel piano in cui il braccio può effettuare dei movimenti. L’obiettivo è verificare quanto influiscono gli errori di posizionamento finale del braccio in applicazioni reali.

Nel documento STUDIO TEORICO SUL CONTROLLO OTTIMO IN TEMPO REALE DI UN SISTEMA NON LINEARE E APPLICAZIONE SPERIMENTALE AD UN BRACCIO ROBOTICO CON ATTUATORI ELASTICI (pagine 43-52)