Implementación de Esquemas Numéricos para la Ecuación de ...jaliste/pres_beamer.pdf · 5 Pruebas Numéricas Pruebas en 1D José Eduardo Aliste Prieto Implementación de Esquemas

Resumen

Implementacion de Esquemas Numericos para laEcuacion de Bellman y Aplicaciones a la

Optimizacion de Trayectorias

Jose Eduardo Aliste Prieto

Departemento de Ingenierıa MatematicaUniversidad de Chile

7 de enero de 2005

Jose Eduardo Aliste Prieto Implementacion de Esquemas Numericos para la Ecuacion de Bellman y Aplicaciones a la Optimizacion de Trayectorias

Resumen Parte I: Ecuacion de Hamilton Jacobi Bellman

Parte I: Ecuacion de Hamilton Jacobi Bellman1 Introduccion

Sistemas controladosProblema de ControlabilidadControl OptimoMetodos Numericos

2 Ecuacion de Hamilton-Jacobi-BellmanIntroduccion y MotivacionSoluciones de ViscosidadPrincipios de Comparacion y UnicidadContinuidad de la funcion valor

3 Metodos de diferencias finitas para HJBMotivacionDiferencias finitas en dimension superiorImplementacion

4 Metodos decentrados5 Pruebas Numericas

Pruebas en 1D








Pruebas en 1D








Pruebas en 1D








Pruebas en 1D








Pruebas en 1D



Parte II: Modelos Aeroespaciales

6 Modelo general

7 Modelo reducido

8 Hamiltoniano decentrado




6 Modelo general

7 Modelo reducido





6 Modelo general

7 Modelo reducido



IntroduccionEcuacion de Hamilton-Jacobi-Bellman

Metodos de diferencias finitas para HJBMetodos decentrados

Pruebas Numericas

Parte I

Ecuacion de Hamilton-Jacobi-Bellman




Pruebas Numericas


Resumen1 Introduccion





Pruebas en 1D




Pruebas Numericas


Sistemas controlados

Consideremos el siguiente sistema dinamico controlado:y(t) = f (y(t), α(t)), t ≥ 0

y(0) = x

donde x ∈ RN es la posicion inicial, yx ,α(·) ∈ RN es la trayectoria,f es la dinamica y α el control, elegido en el espacio de controles:

A = α : [0,∞) → Rm|α es medible y α(t) ∈ A c.t.p. t > 0

con A ⊂ Rm compacto. Supondremos que f es continua y quef (∗, a) es uniformemente Lipschitz con respecto a a ∈ A.




Pruebas Numericas


Ejemplo: El carro-cohete

Consideramos un carro el cual:

Esta restringido a moverse en una sola direccion.

El carro tiene control exacto de su aceleracion.

El modulo de la aceleracion es menor que 1[m/s2].

El sistema controlado para el carro es:y(t) =

(0 1

0 0

)y(t) +

(0

1

)α(t),

y(0) = x ,

A = [−1, 1]




Pruebas Numericas








(0 1

0 0

)y(t) +

(0

1

)α(t),

y(0) = x ,

A = [−1, 1]




Pruebas Numericas








(0 1

0 0

)y(t) +

(0

1

)α(t),

y(0) = x ,

A = [−1, 1]




Pruebas Numericas








(0 1

0 0

)y(t) +

(0

1

)α(t),

y(0) = x ,

A = [−1, 1]




Pruebas Numericas


Problema de Controlabilidad

Destino o Interfaz: T ⊂ RN conjunto cerrado con fronteracompacta.

Tiempo de llegada a Destino:tx(α) = inft > 0 : yx ,α(t) ∈ T Tiempo Mınimo: T (x) = inftx(α) : α ∈ AConjunto Alcanzable: R = x ∈ RN : T (x) < +∞Preguntas:

¿Como es el Conjunto R?¿Es posible caracterizar R de acuerdo a las propiedades de f yde A?




Pruebas Numericas









Pruebas Numericas









Pruebas Numericas


Control Optimo

Seleccion de controles: Si x ∈ R, ¿ Cual es el mejor controlara alcanzar T ?

Criterio de minimizacion:

J(x , α) =

∫ tx (α)

0`(yx ,α(s), α(s))e−λsds+e−λtx (α)g(yx ,α(tx(α)))

(1)donde ` es el costo instantaneo, g es el costo final y λ ≥ 0 esla tasa de descuento.

Definition (Control Optimo)

Dado un estado inicial x , un control α∗ ∈ A se dice CONTROLOPTIMO si

J(x , α∗) = infJ(x , α) : α ∈ A




Pruebas Numericas


Control Optimo(cont.)

El objetivo general de este trabajo es:

El estudio de metodos numericos para encontrar controlesoptimos para un sistema (f ,A, `, g , T ) y estado inicial x

dados.




Pruebas Numericas


Algunos metodos en control optimo

Metodos Directos: Discretizan directamente el problema,obteniendo un programa no lineal (NLP), el cual resuelvenutilizando metodos conocido de optimizacion numerica:

Programacion Cuadratica Secuencial (SQP) (ver [Bet01])

Metodos de Punto interior (ver [BBH+03])

Metodos indirectos: Escriben condiciones de optimalidad para elproblema de control, las cuales son luego discretizadas y resueltasmediante algoritmos adhoc

Principio de Pontryagin y Metodos de tiro.(Ver [Gui02]).

Programacion Dinamica.




Pruebas Numericas












Pruebas Numericas












Pruebas Numericas












Pruebas Numericas

Introduccion y MotivacionSoluciones de ViscosidadPrincipios de Comparacion y UnicidadContinuidad de la funcion valor






Pruebas en 1D




Pruebas Numericas


Principio de la Programacion Dinamica

Consideremos la funcion valor:

v(x) = infJ(x , α) : α ∈ A

Proposicion (Principio de la Programacion Dinamica)

Si t ∈ (0,T (x)) entonces

v(x) = infα∈A

∫ t

0`(yx ,α(s), α(s))e−λsds + v(yx ,α(t))e−λt

.

(PPD)




Pruebas Numericas


Caso suave

Si suponemos que v es diferenciable en un punto x ∈ Ω = T c

entonces v satisface

λv(x) + supa∈A

−`(x , a)− f (x , a) · ∇v(x) = 0, (HJB)

que es una version infinitesimal de (PPD). Luego, si v esdiferenciable en todo Ω, sera solucion de la ecuacion anterior, lacual es conocida como Ecuacion de Hamilton-Jacobi-Bellman.




Pruebas Numericas


Caso suave: Sıntesis del Control Optimo

Sea S la multifuncion

S(z) = argmaxa∈A

−f (z , a) ∗ ∇v(z)− `(z , a).

Se puede probar que si α∗ es un control optimo partiendo de xentonces

α∗(t) ∈ S(yx ,α∗(t)). (CO)

Mas aun, bajo hipotesis adicionales se puede probar que estacondicion es tambien suficiente. Decimos que un control elegido deesta forma es retroalimentado y que S es una funcion deretroalimentacion.




Pruebas Numericas


Ventajas del enfoque de Bellman

Estabilidad de las trayectorias frente a perturbaciones.

Si uno conociera S explicitamente, podrıa calcular controlesoptima para cualquier condicion inicial x dada.

Si uno conociera v entonces para calcular S debemos resolverun programa no lineal ”standard”(En general, basta encontrarun solo mınimo).




Pruebas Numericas









Pruebas Numericas









Pruebas Numericas


Desventajas del enfoque de Bellman

v es imposible de calcular directamente.

v no es necesariamente diferenciable.¿Como interpretarentonces (HJB)?

Aun siendo v diferenciable, no hay unicidad de soluciones para(HJB), incluso con las correctas condiciones de borde.

Incluso para los problemas mas simples, (HJB) es unaecuacion completamente no lineal(Fully No linear), y por lotanto dificil de resolver.

En la mayorıa de las aplicaciones, N ≥ 4.




Pruebas Numericas











Pruebas Numericas











Pruebas Numericas











Pruebas Numericas











Pruebas Numericas


Conclusiones

Para calcular v tenemos dos herramientas: El principio de laProgramacion Dinamica y la Ecuacion deHamilton-Jacobi-Bellman.

Necesitamos una nocion de solucion bien adaptada a este tipode problemas, en la cual podamos caracterizar v comosolucion en este nuevo sentido de (HJB).

La respuesta al segundo puento fue dada por Crandall y Lions en[CL83], quienes proponen una nueva nocion de solucion(la solucionde viscosidad) que posee las propiedades deseadas.




Pruebas Numericas


Soluciones de Viscosidad para HJ

Sea Ω ⊂ RN un abierto, λ ≥ 0 y la ecuacion de Hamilton-Jacobi:

λu(x) + H(x ,∇u(x)) = 0 (HJ)

Definition

Una funcion u ∈ C (Ω) se dice subsolucion(respectivamentesupersolucion) de viscosidad de (HJ) si para cualquier ϕ ∈ C 1(Ω)y cualquier x0 ∈ Ω maximo local(respectivamente mınimo local) deu − ϕ se tiene

λu(x0) + H(x0,∇ϕ(x0)) ≤ 0.(resp. ≥ 0)

Finalmente, decimos que u es una solucion de viscosidad de (HJ)si es simultaneamente una subsolucion de viscosidad y unasupersolucion de viscosidad de (HJ).




Pruebas Numericas


Principio de Comparacion

Theorem ([BCD97, Teo. II.3.1])

Sea Ω un abierto acotado de RN . Suponga que u1, u2 ∈ C (Ω) son,respectivamente,una sub- y supersolucion de viscosidad de

u(x) + H(x ,∇u(x)) = 0, x ∈ Ω

y que u1 ≤ u2 sobre ∂Ω. Suponga ademas que H satisface

|H(x , p)− H(y , p)| ≤ ω1(|x − y |(1 + |p|)) (H1)

donde ω1 es un modulo de continuidad, es decir,ω1 : [0,+∞[→ [0,+∞[ es continua no decreciente y ω1(0) = 0.Entonces u1 ≤ u2 en Ω.




Pruebas Numericas


Unicidad del Problema de Dirichlet para HJ

Consideremos el siguiente Problema de contorno tipo Dirichlet:λu + H(x ,∇u) = 0, x ∈ Ω,

u = g , x ∈ ∂Ω,(HJC)

donde λ > 0. Decimos que una solucion de viscosidad que satisfacela condicion de borde es una solucion de (HJC). Supongamos que(HJC) tiene solucion y que H satisface las hipotesis del Teoremaanterior. Entonces, en C (Ω) hay una unica solucion de (HJC).




Pruebas Numericas


La funcion valor y la ecuacion HJB

Denotemos por Q el dominio de v , es decir,

Q = x ∈ RN : v(x) < +∞

Proposicion

Suponga que v es continua y Q es abierto. Entonces v es solucionde viscosidad de

λv(x) + supa∈A

−`(x , a)−∇v(x) · f (x , a) = 0, x ∈ Q \ T .




Pruebas Numericas


Continuidad de la funcion valor

El resultado anterior nos estimula a estudiar las condiciones bajolas cuales v es una funcion continua.




Pruebas Numericas


Horizonte infinito Clasico




Pruebas Numericas


Destino no vacıo: hipotesis de controlabilidad local




Pruebas Numericas


Tasa de descuento nula: Transformada de Kruzkov




Pruebas Numericas


Costo final no nulo: hipotesis de compatibilidad




Pruebas Numericas


Algunos comentarios sobre soluciones no-continuas de HJ




Pruebas Numericas

MotivacionDiferencias finitas en dimension superiorImplementacion






Pruebas en 1D




Pruebas Numericas


Motivacion

Consideremos la ecuacion:u(x)− 1 + |u′(x)| = 0, x 6= 0,

u(0) = 0,(2)

y la aproximacion centrada:uj − 1 +

|uj+1−uj−1|2δ = 0, j 6= 0,

u0 = 0,(3)

Podemos observar que:

Si u0 es la solucion de (2), entonces u0 es creciente.

Es razonable imponer que la aproximacion sea tambiencreciente, es decir, ui ≤ uj si i ≤ j . Ası, (3) queda

uj + 1 = uj−1 − 2δuj + 2δ (4)




Pruebas Numericas


Motivacion

Consideremos la ecuacion:u(x)− 1 + |u′(x)| = 0, x 6= 0,

u(0) = 0,(2)

y la aproximacion centrada:uj − 1 +

|uj+1−uj−1|2δ = 0, j 6= 0,

u0 = 0,(3)

Podemos observar que:

Si u0 es la solucion de (2), entonces u0 es creciente.

Es razonable imponer que la aproximacion sea tambiencreciente, es decir, ui ≤ uj si i ≤ j . Ası, (3) queda

uj + 1 = uj−1 − 2δuj + 2δ (4)




Pruebas Numericas


Motivacion(cont.)

(4) puede ser resuelta analıticamente,

uj = A(−δ +√

δ2 + 1)j + B(−δ −√

δ2 + 1)j + 1, j > 1,

con A y B constantes a determinar.

Para calcular A y B necesitamos valores a priori de u0 y u1.

Como u(0) = 0, resta ver que valor a priori dar a u1.

De la forma (4), esperamos que aparezcan oscilaciones en laaproximacion si el valor a prior de u1 es “MAL ELEGIDO”.




Pruebas Numericas


Motivacion: Efecto de u1

0

0.2

0.4

0.6

0.8

0.2 0.4 0.6 0.8 1

0.1

0.2

0.3

0.4

0.5

0.6

0 0.2 0.4 0.6 0.8 1

Figura: Aproximacion (4) usando δ = 0,01 y u1 = 0,2(izquierda) yu1 = 1− e−0,01 + 0,01(derecha)




Pruebas Numericas


Motivacion: Como elegir u1

Consideremos la siguiente aproximacion decentrada:

uj − 1 +|uj−1 − uj |

δ= 0, j 6= 0 (5)

Para resolver (5) necesitamos un valor a priori solo para u0.

Tenemos dos metodos para resolver (2):1 Resolver (4) utilizando (5) para calcular el valor a priori de

u1(metodo hibrido).2 Resolver (5)(metodo decentrado).




Pruebas Numericas


Comparacion de metodos: hıbrido v/s decentrado.

0.1

0.2

0.3

0.4

0.5

0.6

0.2 0.4 0.6 0.8 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7




Pruebas Numericas


Comparacion de metodos:(cont.)

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1−5

0

5

10

15

20x 10

−3

0 0.5 1 1.5 2 2.5 3 3.5 40

0.02

0.04

0.06

0.08

0.1

0.12

Figura: Error absoluto de los metodos con δ = 0,1. Metododecentrado(azul) y metodo hıbrido(verde)




Pruebas Numericas


Observaciones




Pruebas Numericas


Diferencias finitas en dimension superior: Notaciones

Si j ∈ ZN , |j | :=∑N

i=1 |ji |.Sea δ ∈ RN

++ el paso de discretizacion en espacio.

Sea iδ : ZN → RN definida por:

iδ(j) = (δ1j1, δ2j2, · · · , δnjn).

RNδ := iδ(Z

N) y denotamos x j = iδ(j).

Si A ⊂ RN , Aδ = A ∩ RNδ .

Si B ⊂ RNδ , B = i−1

δ (B).

Sea u : RN → R, denotamos por uj una aproximacion de u enx j y ∆φuj una aproximacion de ∇u(x j) dada por

∆Φuj := Φ(j , δ, E1, a).

donde E1 = (ul : |l − j | ≤ 1).




Pruebas Numericas


Diferencias finitas en dimension superior: Notaciones

Si j ∈ ZN , |j | :=∑N

i=1 |ji |.Sea δ ∈ RN

++ el paso de discretizacion en espacio.

Sea iδ : ZN → RN definida por:

iδ(j) = (δ1j1, δ2j2, · · · , δnjn).

RNδ := iδ(Z

N) y denotamos x j = iδ(j).

Si A ⊂ RN , Aδ = A ∩ RNδ .

Si B ⊂ RNδ , B = i−1

δ (B).

Sea u : RN → R, denotamos por uj una aproximacion de u enx j y ∆φuj una aproximacion de ∇u(x j) dada por

∆Φuj := Φ(j , δ, E1, a).

donde E1 = (ul : |l − j | ≤ 1).




Pruebas Numericas


Sistema de diferencias finitas

Con las notaciones anteriores podemos escribir la siguienteaproximacion:

λvj = infa∈A`(x j , a) + f (x j , a) ·∆Φvj, j ∈ Ωδ

vj = g(x j), j ∈ Tδ(PCD)




Pruebas Numericas


Existencia de aproximaciones




Pruebas Numericas


Convergencia de aproximaciones




Pruebas Numericas


Implementacion




Pruebas Numericas


Truncamiento




Pruebas Numericas






Pruebas en 1D




Pruebas Numericas

Metodo decentrado teorico




Pruebas Numericas

Metodo decentrado truncado




Pruebas Numericas

Condicion de estabilidad




Pruebas Numericas

Convergencia




Pruebas Numericas

Pruebas en 1D






Pruebas en 1D




Pruebas Numericas

Pruebas en 1D

Pruebas en 1D

ConsideramosN = 1, λ = 1, T = 0`(x , a) = x , f (x , a) = −xa,A = [0, 1].

(6)

La ecuacion (HJB) se reescribe como:

v(x) =

x − v ′(x)x si v ′(x)x > 0

x si v ′(x)x < 0(7)


Modelo generalModelo reducido

Hamiltoniano decentrado

Resumen

6 Modelo general

7 Modelo reducido





Resumen

6 Modelo general

7 Modelo reducido





Resumen

6 Modelo general

7 Modelo reducido



Conclusiones


Referencias

beamericonarticleN. Berend, J.F. Bonnans, M. Haddou, J. Laurent-Varin, andC. Talbot.A preliminary interior point algorithm for solving optimalcontrol problems.In Fifth Int. Conf. on Launcher Technology, Madrid, November25-27, 2003.

beamericonarticleMartino Bardi and Italo Capuzzo-Dolcetta.Optimal control and viscosity solutions ofHamilton-Jacobi-Bellman equations.Systems & Control: Foundations & Applications. BirkhauserBoston Inc., Boston, MA, 1997.With appendices by Maurizio Falcone and Pierpaolo Soravia.

beamericonarticleJ.T. Betts.Practical Methods for Optimal Control Using NonlinearProgramming.SIAM Advances in Design and Control, 2001.

beamericonarticleMichael G. Crandall and Pierre-Louis Lions.Viscosity solutions of Hamilton-Jacobi equations.Trans. Amer. Math. Soc., 277(1):1–42, 1983.

beamericonarticleT. Guilbaud.Methodes numeriques pour la commande optimale.PhD thesis, Universite de Paris VI, 2002.


Documents

Implementación de Esquemas Numéricos para la Ecuación de ...jaliste/pres_beamer.pdf · 5 Pruebas Numéricas Pruebas en 1D José Eduardo Aliste Prieto Implementación de Esquemas