L23 Politiche fuori linea senza apprendimento: progetto funzionale Rodolfo Soncini Sessa MODSS...

L23 Politiche fuori linea

senza apprendimento:progetto funzionale

Rodolfo Soncini Sessa

MODSSCopyright 2004 © Rodolfo Soncini Sessa.

R. Soncini Sessa, MODSS, 2004 2

Problema di controllo

Problema di minimizzazione del costo totale atteso su un orizzonte finito di lunghezza h.

J *(x0) =

u0 ,p[1,h)min

εt{ }t=1,...h

E gtt=0

h−1

∑ xt,ut,εt+1( ) +Gh xh( )⎡

⎣⎢

⎤

⎦⎥

xt+1 = ft xt,ut,εt+1( ) t=0,1,...,h−1

ut =mt xt( ) ∈Ut xt( ) t=0,1,...,h−1

εt+1 ∼φt .( ) t=0,1,...,h−1

p0h−1 = mt ⋅( ) t=0,1,...,h−1{ }

Funzione obiettivo separabile

Disturbo bianco


ma, tramite il nuovo stato che produce, influenza anche i costi degli stadi futuri.

Il costo futuro

Il Problema è un problema decisionale a più stadi, in ciascuno dei quali, noto lo stato xt , si deve adottare una decisione ut .

L’orizzonte è finito.

Ogni decisione comporta un costo immediato,

J = E

εt{ } t=1,...,h

+ + L + + L + ⎡⎣ ⎤⎦

u0 u1

x0 x1 x2

g0

ut

xt xt+1

gt g1

xh

gh


Un semplice esempio

ut

rt+1

εt+1

gt

εt+1 ut

st+1 st

rt+1

gt

Ad ogni istante dobbiamo stabilire il volume ut che vorremmo inviare al distretto irriguo; da cui consegue il volume st+1

inviato al futuro.


Un semplice esempio

tempot-1 t+1t

ut

rt+1

εt+1

gt

st+1 st


Un semplice esempio

st+1 st st+1 st

εt+1

rt+1

gt

ut


Il costo futuro

La decisione all’istante t deve quindi considerare :

• Il costo immediato gt(xt ,ut , εt+1)

• i costi futuri sul resto

dell’orizzonte h, che dipendono però anche dalle decisioni future. ε 1 E

t1,...,h 1

g x ,u ,ε 1 gh

xh

t1

h 1

mt*(x

t) arg min

ut

ε t+1

E gt

xt,u

t,ε

t1 Ht1* x

t1

ut

min ε t+1

E gt

xt,u

t,ε

t 1 Ht 1* x

t 1

EQUAZIONE DI BELLMAN

Definiamo il costo futuro ottimo (totale atteso) come il costo in cui incorreremmo se dall’istante t adottassimo decisioni ottime .

*t tH x

Ht*(x

t)

Quali costi dunque ?Consideriamoli entrambi!


=min

ut

Eεt+1

+ ⎡⎣ ⎤⎦

Isolamento di un passo del processo

ut

xt xt+1

gt(x

t,u

t,εt+1) Ht

*(xt) Ht+1

* (xt+1)

εt+1


La Programmazione Dinamica (DP)

1 Il costo futuro.

4. Politiche AUV, progetto funzionale:l’algoritmo risolvente per il problema su orizzonte finito.

2 Esempio.

3 Derivazione formale.

3.1 Una legge di dualità.

2 Esempio.


Esempio

1

2

2

5

2

3

13

3

10

1 1

∞

∞

0

1

4

12

1

1

1

2

13

3

10

0 1 2 3 4t

Penale

0 3

3*

0...

04 4( ) min ,t t t

u ut

J x g x G xu

1 , data dal grafot t t tx f x u 1 2 3( ) ( ) { , } ( ) { , , } ( ) { , }t t t t tu U x U x D G U x S D G U x S D


1

2

2

5

2

3

13

3

10

1 1

∞

∞

0

1

4

12

1

1

1

2

13

3

10

0 1 2 3 4t

Esempio

2

1

4

2

4

4

= [∞, 0, ∞] 4*4 4 4( )x GH x

H

3*(x

3) =

u3min g3 x3,u3( ) + H4

* x4( )⎡⎣

⎤⎦ = [4, 2, 1] =[G, D, S]

*3 ( )m

H

2*(x

2) =

u2min g2 x2 ,u2( ) + H3

* x3( )⎡⎣

⎤⎦ = [4, 4, 2] =[G, G, D]

*2 ( )m


1

2

2

5

2

3

13

3

10

1 1

∞

∞

0

1

4

12

1

1

1

2

13

3

10

0 1 2 3 4t

2

1

4

2

4

4

Esempio

Una delle possibili sequenze di controlli ottimi è quindi :

u0=D u1=S u2=G u3=D

7

6

57

H

1*(x

1)

u1m in g1 x1,u1 H2

* x2 ⎡⎣

⎤⎦

H

0*(x

0)

u0m in g0 x0 ,u0 H1

* x1 ⎡⎣

⎤⎦

= [6, 5, 7]

=[D, S/G, D]*1 ( )m

= [7] =[S/D]*0 0( )m x


Esempio

S/GS/D

GD

D D S

G D

G

tx

0 1 2

1

2

3

3u

In realtà abbiamo trovato molto di più di una sequenza di controlli ottimi, abbiamo trovato una politica APV

*p *tM *( )t tM x

t xt


Esempio

t

7

46

7 2 1

4 2

4x

0 1 2

1

2

3

3

5

4

∞

0

∞

H*

Conviene quindi memorizzare solo la tabella H*.

ut=arg min

ut

εt+1

E gt xt,ut,εt+1( ) + Ht+1* xt+1( )⎡

⎣⎤⎦

Abbiamo ottenuto anche i valori dei costi futuri ottimi per tutti i t e tutti gli stati.

Ht*(x

t)

Nota si può calcolare ad ogni istante la decisione ottima

risolvendo l’equazione*( )t t tu m x Ht

*(xt)



1 Il costo futuro.

4 Politiche AUV, progetto funzionale:l’algoritmo risolvente per il problema su orizzonte finito.

2 Esempio.





Derivazione formale

Problema di minimizzazione del costo totale atteso su un orizzonte finito di lunghezza h.

J *(x0) =

u0 ,p[1,h)min

εt{ }t=1,...h

E gtt=0

h−1

∑ xt,ut,εt+1( ) +Gh xh( )⎡

⎣⎢

⎤

⎦⎥

xt+1 = ft xt,ut,εt+1( ) t=0,1,...,h−1

ut =mt xt( ) ∈Ut xt( ) t=0,1,...,h−1

εt+1 ∼φt .( ) t=0,1,...,h−1

p0h−1 = mt ⋅( ) t=0,1,...,h−1{ }

Ipotesi: processo bianco

Funzione obiettivo separabile

*0 0( )H x

R. Soncini Sessa, MODSS, 2004 17 1

1 1,..., 1htp m t h

Derivazione formale

H0*(x

0) =

u0 ,p[1,h−1)min

εt{ }t=1,...

E gtt=0

h−1

∑ xt,ut,εt+1( ) +Gh xh( )⎡

⎣⎢

⎤

⎦⎥

H0*(x

0) =

uo

minε1E g0 x0 ,u0 ,ε1( ) +

p[1,h−1)min

εt{ }t=2,3,..

E gtt=1

h−1

∑ xt,ut,εt+1( ) +Gh xh( )⎛

⎝⎜⎜

⎞

⎠⎟⎟

⎡

⎣⎢⎢

⎤

⎦⎥⎥

Ipotesi di processo bianco

1 1, , 1,..., 1t t t t tx f x u t hε 1 0 0 0 1, ,x f x u ε

1 ~ 1,..., 1t t t hε 1 0~ε

( ) 1,..., 1t t t t tu m x U x t h 0 0 0u U x

*1 1H x


Derivazione formale

• In generale quindi il costo futuro ottimo sull’orizzonte temporale [0,h] è calcolabile con la seguente equazione ricorsiva:

• Il controllo ottimo è dato da:

m

t*(x

t) arg m in

ut ∈Ut xt Eεt+1∼φt ⋅

gt xt,ut,εt1 Ht1* xt1 ⎡

⎣⎤⎦

1

* *1 1 1

( ) ( )( ) min , ,

t t t t tt t t t t t t t

u U xH x E g x u H x

ε ε




1 Il costo futuro.

2 Esempio.






H

t* x

t m inut

Εεt+1~φt

gt xt,ut,εt1 Ht1∗ xt1 ⎡

⎣⎤⎦ LAPLACE

La legge di dualità

L’equazione di Bellman per i problemi di Wald si ottiene dalla precedente con le seguenti sostituzioni:

+max

Ξt φt ⋅( )

Per questo mostreremo gli algoritmi solo per il caso di Laplace.

Eεt+1

maxεt+1

va al posto di

1

maxt tε Ξ

1 1 1max , , ,t t t t t tg x u H xε * WALD


Equazione di Bellman con criterio di Wald

• In generale quindi il costo sull’orizzonte temporale [t,h] è calcolabile con la seguente equazione ricorsiva:

• Il controllo ottimo è dato da:

m

t*(x

t) =arg

ut ∈Ut (xt )min

εt+1∈Ξt

max max gt xt,ut,εt+1( ),Ht+1* xt+1( )( )⎡

⎣⎤⎦

1

* *1 1 1

( )( ) max , , ,maxmin

t t t t t

t t t t t t t tu U x

H x g x u H xε

ε




1 Il costo futuro.


2 Esempio.





L’algoritmo risolvente per orizzonte finito

J * x0( ) = min

u0 ,p[1,h−1) ε1 ...εh

E gt xt,ut,εt+1( ) +Gh xh( )t=0

h−1

∑⎡

⎣⎢

⎤

⎦⎥

• Passo 0 (inizializzazione):

si calcolino ricorsivamente i costi-futuri mediante l’equazione di Bellman:

Ht* x

t( )

H

t*(x

t) =

ut

min εt+1

E gt xt,ut,εt+1( ) + Ht+1* xt+1( )⎡

⎣⎤⎦

∀xt ∈ Sxt

; t=h−1,h−2,...,1

si ponga

• Passo 1:

*[1, 1)hp


L’algoritmo risolvente per orizzonte finito

posto t =0 si calcoli

H

0*(x

0) =

u0min

ε1E g0 x0 ,u0 ,ε1( ) + H1

* x1( )⎡⎣

⎤⎦

Si ottiene così il valore ottimo J * x

0( ).

• Passo 2 (terminazione):

*0u


Complessità dell’algoritmo

0 321

23

1

1

1

5

1

0

4

3

4

1

23

12

4

4

3

4

1

x02

x11

x13

x12

x23

x21

x22

x33

x31

x32

0

0

0


Procedura esaustiva

35

76

4

55

66

46

87

56

67

7

57

975

68

99

23

1

1

1

5

1

0

4

3

4

1

23

12

4

4

3

1

x02

x11

x13

x12

x23

x21

x22

x33

x31

x32

4

0

0

0

27 confronti


0

0

0

23

12

4

4

3

4

1

x21

x23

x22

H2(x

23) =1

H2(x

22 ) =3

H2(x

21 ) =1

23

1

1

1

5

1

0

4

3

4

1

23

12

4

4

3

1

x02

11x

x13

x12

x23

12x

x22

x33

x31

x32

4

1

1

3

23

51

0

4

3

4

1

x11

x13

x12

H1(x

13) =4

H1(x

12 ) =3

H1(x

11) =2

La strategia della DP

9 confronti

9 confronti


23

1

1

1

5

1

0

4

3

4

1

23

12

4

4

3

1

20x

11x

31x

21x

32x

12x

22x

33x

13x

23x

4

1

1

3

23

51

0

4

3

4

1

x11

x13

x12

H1(x

13) =4

H1(x

12 ) =3

H1(x

11) =2

La strategia della DP

2

4

3

1

1

1 x0

2

H0(x

02 ) =3

3

3 confronti

Complessivamente 9+9+3=21 confronti invece di 27.



Se il vettore di disturbo ha una unica componente, che assume nε valori, il calcolo del valore atteso richiede nε valutazioni di L.

Εεt+1

L⎡⎣ ⎤⎦ Lεt1i

i1

nε

∑ φt εt1i

H

t*(x

t) =

ut

min εt+1

E gt xt,ut,εt+1( ) + Ht+1* xt+1( )⎡

⎣⎤⎦L(εt+1)

t

εt1

εt1nε1



Se il vettore di disturbo ha un’ unica componente, che assume nε valori, il calcolo del valore atteso richiede nε valutazioni di L.

Se invece il disturbo ha due componenti ε=(υ,η), ciascuna delle quali assume nε valori, le valutazioni di L sono nε

2.

H

t*(x

t) =

ut

min εt+1

E gt xt,ut,εt+1( ) + Ht+1* xt+1( )⎡

⎣⎤⎦L(εt+1)

υt1nε1

ηt1

Εεt+1

L⎡⎣ ⎤⎦= Lj=1

nε

∑i=1

nε

∑ (υt+1i ,ηt+1

j ) φt υt+1i ,ηt+1

j( )

1

nε


Complessità dell’algoritmoOccorre poi trovare il minimo rispetto ai valori che può assumere il controllo.

H

t*(x

t)

ut

m in εt+1

E gt xt,ut,εt+1 Ht+1* xt+1 ⎡

⎣⎤⎦

Come nel caso di ε, se il controllo è scalare e assume nu valori, occorre effettuare nu valutazioni per individuare il minimo.

Se il controllo ha due componenti, ne occorrono nu2.

1

1

…

nu

… nu ut

1

ut2



Occorre infine valutare il costo futuro per tutti gli stati:

H

t*(x

t)

ut

m in εt+1


⎣⎤⎦

Se lo stato ha due componenti, ne occorrono nx2.

1

1

nx

… nx xt1

xt2

…

Se lo stato è scalare e assume nx valori, occorre effettuare nx valutazioni per determinare l’intera funzione Ht

*(g)



Il tempo di calcolo della DP cresce: esponenzialmente con la dimensione di stato, controllo e disturbo,

linearmente con la durata dell’orizzonte.

H

t*(x

t)

ut

m in εt+1


⎣⎤⎦

Sxt

ha nx

dx elementi

Sut

ha nu

du elementi

Sεt+1ηa nε

dε εlεm εni

⎫

⎬

⎪⎪

⎭

⎪⎪

in oalε nxdx nu

du nεdε h valυazioni

dovε dx, du ε dε sono lε dim εnsioni dεllo sao, dεl conrollo ε dεl disυrbo

se lo stato iniziale non è dato;

( ) ( 1) valutazioni

in caso contrario.

u x ud d d d du x un n n n n hε ε

ε ε

se lo stato iniziale non è dato;

( ) ( 1) valutazioni

in caso contrario.

u x ud d d d du x un n n n n hε ε

ε ε



H

t*(x

t)

ut

m in εt+1


⎣⎤⎦

Sxt

ha nx

dx elementi

Sut

ha nu

du elementi

Sεt+1ηa nε

dε εlεm εni

⎫

⎬

⎪⎪

⎭

⎪⎪

in oalε nxdx nu

du nεdε h valυazioni

dovε dx, du ε dε sono lε dim εnsioni dεllo sao, dεl conrollo ε dεl disυrbo

Il tempo di calcolo della DP cresce: esponenzialmente con la dimensione di stato, controllo e disturbo,

linearmente con la durata dell’orizzonte. La procedura esaustiva richiede invece valutazioni.

E' dunque esponenziale rispetto alla durata dell'orizzonte.

uhd d

un n εε


Leggere

MODSS Cap. 12

L23 Politiche fuori linea senza apprendimento: progetto funzionale Rodolfo Soncini Sessa MODSS...

Documents

Transcript of L23 Politiche fuori linea senza apprendimento: progetto funzionale Rodolfo Soncini Sessa MODSS...