AI_21_1

Jak uczy

przy braku wzorców?

dy rodzaj uczenia wymaga sprz

ęŜ

enia zwrotnego

informuj

cego agenta o skuteczno

ci nauki.

Uczenie indukcyjne i probabilistyczne wykorzystuje zbiory
wzorców ucz

cych do dostrajania parametrów modeli.

Uczenie ze wzmocnieniem

(uczenie z krytykiem;

reinforcement learning) wykorzystuje

kary

nagrody

informuj

ce agenta o poprawno

ci jego działa

Celem uczenia ze wzmocnieniem jest wykorzystanie

F.A. Dul 2007

Celem uczenia ze wzmocnieniem jest wykorzystanie
obserwowanych nagród i kar do znalezienia optymalnej
strategii działania w danym (nieznanym)

rodowisku.

Uczenie ze wzmocnieniem jest niezast

pione w grach

(np. w szachach), gdzie liczba mo

liwych wzorców jest

tak du

e wyklucza to uczenie indukcyjne.

Uczenie ze wzmocnieniem stanowi jedyn

liwo

ść

uczenia w przypadku gdy

rodowisko jest całkowicie

nieznane - w zadaniach eksploracji.

21.2. Uczenie pasywne ze wzmocnieniem

Uczenie pasywne ze wzmocnieniem

polega na nauczeniu

yteczno

ci stanów

(s)

przy danej strategii działania

(s)

(w stanie

agent wykonuje działanie

(s)

Zakłada si

rodowisko jest obserwowalne.

W uczeniu pasywnym agent nie zna modelu przej

cia

T(s,a,s’)

i funkcji nagrody

R(s).

Agent wykonuje w

rodowisku zbiór

prób

ywaj

c strategii

Celem tych prób jest nauczenie si

funkcji u

yteczno

(s)

dla ka

dego stanu

© F.A. Dul 2007

-1

0.705

0.762

0.812 0.868 0.918

0.660

0.611 0.388

0.655

RZYKŁAD

Strategia

i u

yteczno

ci stanów w

wiecie 4x3.

dla ka

dego stanu













∑

∞

)

(

)

(

21.2. Uczenie pasywne ze wzmocnieniem

W adaptacyjnym programowaniu dynamicznym (ADP) agent
uczy si

funkcji przej

cia

T(s,a,s’)

Adaptacyjne programowanie dynamiczne

Uczenie metod

adaptacyjnego programowania dynamicznego

Uczenie si

funkcji przej

cia

T(s,a,s’)

i obserwacje funkcji

nagrody

R(s)

pozwalaj

wykorzysta

równanie Bellmana

∑

)

(

)

(

)

(

)

(

Umo

liwia to uwzglednienie zale

ci mi

dzy u

yteczno

cia-

mi stanów i w efekcie lepsze przybli

enie funkcji u

yteczno

ci.

© F.A. Dul 2007

Uczenie metod

adaptacyjnego programowania dynamicznego

jest łatwe, gdy

odpowiadaj

ce mu równanie Bellmana jest

liniowe (przy stałej strategii nie ma maksymalizacji).

Liczba prób

0.2

0.4

0.6

0.8

1.0

100

Wyniki uczenia ADP dla zadania 4x3.

)

0.2

0.4

0.6

0.8

1.0

100

Liczba prób

(4,3)

(3,3)
(1,3)

(1,1)
(3,2)

21.3. Uczenie aktywne ze wzmocnieniem

W uczeniu pasywnym strategia działa

agenta jest ustalona.

uczeniu aktywnym

agent musi

nauczy

kompletnego

modelu

rodowiska ł

cznie z prawdopodobie

stwami efektów

wszystkich działa

Wybór działa

optymalnych oraz wyznaczenie funkcji

yteczno

mog

dokonane poprzez rozwi

zanie

na tego dokona

metodami adaptacyjnego programowania

dynamicznego.

© F.A. Dul 2007

W przypadku iteracji strategii działania optymalne s

otrzymy-

wane bezpo

rednio z równania Bellmana.

yteczno

mog

dokonane poprzez rozwi

zanie

nieliniowego równania Bellmana

∑

)

(

)

(

max

)

(

)

(

21.3. Aktywne uczenie ze wzmocnieniem

Eksploracja polega na poznawaniu nieznanego

rodowiska.

Eksploracja

Agent nie posiada modelu

rodowiska; musi si

go nauczy

na podstawie działa

i obserwacji.

RZYKŁAD

Zadanie 4x3. Sekwencja działa

optymalnych (dla modelu

cisłego)...

Strategia wyznaczona na podstawie modelu wyuczonego
mo

e jednak nie by

optymalna.

-1

...oraz wyznaczona na podstawie strategii

© F.A. Dul 2007

-1

Agent nie nauczył si

prawdziwej strategii

optymalnej; nie nauczył si

prawdziwych

warto

ci u

yteczno

ci stanów.

...oraz wyznaczona na podstawie strategii
optymalnej dla modelu wyuczonego.

Wyznaczona strategia jest

suboptymalna

Agent wyznaczaj

cy strategie suboptymalne nazywany jest

agentem zachłannym

(greedy agent).

Agent zachłanny bardzo rzadko uczy si

strategii optymalnej.

21.3. Aktywne uczenie ze wzmocnieniem

Przyczyn

wyznaczenia strategii suboptymalnych jest

bezkrytyczne uwzgl

dnianie nagród, bez zwracania uwagi

na popraw

jako

ci modelu

rodowiska.

Agent powinien zatem d

ąŜ

do kompromisu pomi

dzy

eksploatacj

rodowiska w celu maksymalizacji nagrody

eksploracj

rodowiska w celu poprawienia jako

ci modelu.

Metoda

GLIE

(Greedy in the Limit of Infinite Exploration)

polega na próbowaniu wszystkich działa

we wszystkich

stanach w celu unikni

cia przeoczenia strategii optymalnej.

© F.A. Dul 2007

stanach w celu unikni

cia przeoczenia strategii optymalnej.

Metoda GLIE pozwala agentowi nauczy

modelu

prawdziwego, ale odbywa si

to du

ym kosztem.

21.3. Aktywne uczenie ze wzmocnieniem

Uczenie funkcji działania

Agent aktywny który nie korzysta z ustalonej strategii mo

metody czasowo-ró

nicowej (TD),

Alternatywn

wersj

metody czasowo-ró

nicowej jest

Q-uczenie

, które zamiast u

yteczno

ci u

ywa reprezentacji

w postaci warto

ci działania, tzw.

Q-warto

Q(a,s)

oznacza warto

ść

wykonania działania

dla stanu

Q-warto

ci zwi

zane s

z u

yteczno

nast

puj

)

(

)

(

)

(

)

(

)

(

−

←

© F.A. Dul 2007

Q-warto

ci zwi

zane s

z u

yteczno

nast

puj

)

(

max

)

(

Agent czasowo-ró

nicowy ucz

cy si

Q-funkcji nie potrzebuje

modelu

rodowiska ani do uczenia, ani do wyboru działania.

Q-uczenie wymaga znajomo

ci modelu

rodowiska.

∑

)

(

max

)

(

)

(

)

(

Równanie dla Q-warto

ci ma posta

21.3. Aktywne uczenie ze wzmocnieniem

Równanie metody czasowo-ró

nicowej dla Q-uczenia ma

posta

)

(

)

(

max

)

(

)

(

)

(

−

Efektywno

ść

metody TD dla Q-uczenia nie jest zadowalaj

ca.

Metody adaptacyjnego programowania dynamicznego (ADP)
u

ywaj

ce (lub ucz

ce si

) modelu

rodowiska s

zazwyczaj

znacznie wydajniejsze.

Co jest zatem lepsze dla agenta:

© F.A. Dul 2007

Co jest zatem lepsze dla agenta:

Badania AI pokazały,

e podej

cie oparte na wiedzy jest

zazwyczaj lepsze.

Efektywny agent AI powinien zatem posiada

modele

przynajmniej niektórych własno

rodowiska.

uczenie si

modelu i funkcji u

yteczno

ci czy te

uczenie si

funkcji działania bez modelu?

Im bardziej zło

one jest

rodowisko, tym wyra

niej widoczne

zalety podej

cia opartego na wiedzy.

21.4. Uogólnienia w uczeniu ze wzmocnieniem

Pierwszym zastosowaniem uczenia ze wzmocnieniem było
opracowanie

programu do gry w warcaby

(1959).

Zastosowania uczenia ze wzmocnieniem - gry

Program wykorzystywał aproksymacj

liniow

z szesnastoma

parametrami; nie wykorzystywał w trakcie uczenia nagród!
Program grał na poziomie dobrych graczy w warcaby.
System TD-Gammon opracowany do

gry w trik-traka

(1992)

ukazuje mo

liwo

ci uczenia ze wzmocnieniem.

Funkcja szacuj

ca była reprezentowana sieci

neuronow

© F.A. Dul 2007

Funkcja szacuj

ca była reprezentowana sieci

neuronow

z jedn

warstw

ukryt

zło

z czterdziestu w

złów.

Nagrod

był tylko ko

cowy wynik gry.

Uczenie wykorzystywało metod

TD w wersji parametrycznej.

Uczenie przeprowadzono za pomoc

200,000 prób (obliczenia

trwały dwa tygodnie).
Pó

niejsza wersja programu zawierała 80 w

złów w warstwie

ukrytej i była uczona za pomoc

300,000 prób.

Poziom gry programu TD-Gammon odpowiadał najlepszym
graczom w trik-traka na

wiecie.

21.2. Sformułowanie statystyczne uczenia

Zastosowania uczenia ze wzmocnieniem - robotyka

Przykładem zastosowania uczenia ze wzmocnieniem
w robotyce jest zadanie sterowania wahadłem odwróconym.
Nale

y tak sterowa

poło

eniem

wózka aby utrzyma

wahadło

w poło

eniu pionowym,

Poło

enie wózka jest ograniczone,

∈

[0,L].

Zmienne stanu s

głe.

© F.A. Dul 2007

Zadaniu temu po

cono tysi

ce prac z zakresu teorii

sterowania oraz AI.

Zmienne stanu s

głe.

Sterowanie jest typu bang-bang.

Algorytm B

OXES

(1968) pozwalał wyznaczy

sterowanie

za pomoc

uczenia ze wzmocnieniem ju

po 30 próbach.

Umo

liwiało to sterowanie realnym urz

dzeniem całymi

godzinami.
Obecnie algorytmy oparte na uczeniu ze wzmocnieniem
pozwalaj

wyznacza

sterowanie wahadłem potrójnym.

21.5 Poszukiwania strategii

Uczenie ze wzmocnieniem mo

e by

zastosowane

do poszukiwania strategii działania agenta.

Strategia jako funkcja odwzorowuj

ca stany na działania

e by

reprezentowana w postaci parametrycznej,

np. jako Q-funkcja liniowa wzgl

dem parametrów,

Poszukiwanie strategii jest w ten sposób sprowadzone
do dostrojenia parametrów.

)

(

max

)

(

© F.A. Dul 2007

do dostrojenia parametrów.

Algorytm P

EGASUS

(2000) wykorzystuje ci

g N liczb losowych

do generowania strategii.

Algorytm P

EGASUS

był u

ywany do wyznaczania efektywnych

strategii w wielu zagadnieniach, np. do

autonomicznego

sterowania

migłowcem

Na podstawie artykułów:

„Autonomous helicopter flight via Reinforcement Learning”,

„P

EGASUS:

A policy search method for large MDPs and POMDPs”,

Andrew Y. Ng, Stanford University,

H. Jin Kim, Michael I. Jordan, and Shankar Sastry University of California, Berkeley

(2000). (

www.cs.berkeley.edu

)

Autonomiczne sterowanie

migłowcem jest zadaniem trudnym,

gdy

dynamika ruchu

migłowca jest wyj

tkowo zło

ona.

21.6 Autonomiczne sterowanie

migłowcem -

przykład zastosowania uczenia ze wzmocnieniem

© F.A. Dul 2007

gdy

dynamika ruchu

migłowca jest wyj

tkowo zło

ona.

Ze wzgl

du na niesymetrie zjawisk dynamicznych i aerodyna-

micznych oraz sprz

ęŜ

enia pomi

dzy poszczególnymi stopniami

swobody ruchu nawet proste manewry wymagaj

precyzyjnego

sterowania.
Metody sztucznej inteligencji pozwoliły opracowa

sterownik

autonomicznie pilotuj

migłowiec w trakcie wykonywania

ró

nych, nawet do

ść

trudnych, manewrów.

Sterownik został opracowany przy u

yciu

algorytmu uczenia

ze wzmocnieniem P

EGASUS

oraz

filtracji Kalmana

21.6. Autonomiczne sterowanie

migłowcem

Proces decyzyjny Markowa (MDP) jest opisany poprzez:

Uczenie ze wzmocnieniem: algorytm P

EGASUS

• zbiór stanów

• stan pocz

tkowy

∈

• przestrze

działa

• prawdopodobie

stwa przej

cia stanów

(s,a)

→

s’ : P

(·)

• funkcja nagrody

R(s): S a R

• współczynnik dyskonta

< 1

• rodzina

strategii

: S a A

© F.A. Dul 2007

gdzie

, s

,... jest trajektori

, czyli ci

giem stanów

odwiedzonych podczas realizacji strategii

]

)

(

)

(

)

(

[

)

(

Celem uczenia jest wyznaczenie strategii

* o najwi

kszej

yteczno

ci,

Uczenie ze wzmocnieniem oparte jest na stochastycznej
funkcji u

yteczno

ci dla strategii

• rodzina

strategii

: S a A

*).

(

)

(

∈

∀

21.6. Autonomiczne sterowanie

migłowcem

yteczno

)

nie mog

obliczone bezpo

rednio, ale

na wyznaczy

ich przybli

enia

(

)

metod

Monte Carlo

Potrzebny jest do tego

stochastyczny model dynamiki obiektu.

Model taki wykorzystuje rozkład prawdopodobie

stwa stanu

nast

pnego

s’

(s’),

przy danych: stanie

i sterowaniu

)

(

→

Dla danej warto

ci losowej

model generuje stan nast

pny

s’

dla którego

(s’) = p,

© F.A. Dul 2007

)

(

)

(

−

Przykład Je

eli dla pary stan-działanie

(s,a)

model mo

generowa

dwa stany

’

z prawdopodobie

stwami:

to stan nast

pny

s’

zale

y od warto

ci zmiennej

nast

puj

co:

s’= s

’

eli

≤

p* ,

s’= s

’

eli

p > p* .

Dla danej losowej warto

stan nast

pny

s’

wyznaczany jest

deterministycznie

21.6. Autonomiczne sterowanie

migłowcem

Model sparametryzowany losowo pozwala uwzgl

dni

zaburzenia stanu lub sterowania spowodowane czynnikami
losowymi (turbulencj

, nierównomierno

pracy silnika, itp.)

(

Model stochastyczny mo

na przedstawi

w postaci modelu

deterministycznego

sparametryzowanego zmienn

losow

Model dynamiki

e by

konstruowany w oparciu o prawa

podstawowe (model przyczynowy) lub te

poprzez

© F.A. Dul 2007

W algorytmie P

EGASUS

sekwencje stanów obliczane s

przy

yciu modelu

deterministycznie

na podstawie sekwencji

liczb losowych

gi liczb losowych na podstawie których oblicza si

sekwencje stanów mog

generowane dla ka

dej strategii

w sposób

powtarzalny

podstawowe (model przyczynowy) lub te

poprzez

identyfikacj

na podstawie pomiarów obiektu rzeczywistego.

21.6. Autonomiczne sterowanie

migłowcem

Wyznaczenie przybli

onych u

yteczno

(

)

metod

Monte

Carlo przebiega nast

puj

co:

• zakłada si

liczb

kroków czasowych

;

• generuje si

g liczb losowych

, p

,..., p

;

• dla ka

dej strategii

π ∈ Π

– generuje si

losowo

stanów pocz

tkowych

(i)

∈

czyli tzw. scenariuszy;

– przy u

yciu modelu

dla ka

dego stanu pocz

tkowego

(i)

generuje si

trajektori

(i)

, ... ,

(i)

© F.A. Dul 2007

– wyznacza si

przybli

yteczno

ść

,...,

)

(

)

(

)

(

)

(

−

∑

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

ycie tego samego ci

gu liczb losowych

, p

,..., p

dla

wszystkich strategii

π∈Π

i wszystkich scenariuszy zapewnia

porównywalno

ść

i powtarzalno

ść

obliczonych u

yteczno

(

)

21.6. Autonomiczne sterowanie

migłowcem

Przy zało

eniu,

e liczba scenariuszy

spełnia warunek

Obliczenie zbioru u

yteczno

(

)

dla zbioru sekwencji

stanów pozwala wyznaczy

najlepsz

strategi

* jako

)),

log(

(

)

(

)

(

−

∈

∀

przybli

enie funkcji u

yteczno

ci aproksymuje z prawdopodo-

bie

stwem 1-

warto

ść

dokładn

© F.A. Dul 2007

stanów pozwala wyznaczy

najlepsz

strategi

* jako

)

(

max

arg

∈

Poniewa

funkcja u

yteczno

ci jest deterministyczna,

to wyznaczenie najlepszej strategii

e by

przeprowadzone dowoln

metod

poszukiwa

metod

najwi

kszego spadku lub metodami gradientowymi.

21.6. Autonomiczne sterowanie

migłowcem

Wyposa

enie

migłowca:

• komputer nawigacyjny,

Do bada

yto zdalnie sterowanego modelu

migłowca

Yamaha R-50

• masa 20 kg,
• długo

ść

3.6 m,

•

rednica wirnika 2.8 m,

• warto

ść

70,000 $.

Dane

migłowca:

migłowiec i jego model

© F.A. Dul 2007

Komputer nawigacyjny wyznaczał estymacj

wektora stanu

na podstawie sygnałów z GPS, INS oraz kompasu cyfrowego
za pomoc

filtru Kalmana

• komputer nawigacyjny,
• inercyjny system nawigacji (INS) z trzema akcelerometrami

oraz trzema

yroskopami,

• ró

nicowy system GPS zapewniaj

cy z wyznaczenie poło

enia

z rozdzielczo

2 cm,

• kompas cyfrowy.

Sygnały wej

ciowe z GPS, INS oraz sygnały steruj

były próbkowane z cz

stotliwo

50Hz.

21.6. Autonomiczne sterowanie

migłowcem

Stan

migłowca opisuje dwana

cie zmiennych:

}

{

Sterowanie

migłowcem opisuj

cztery zmienne:

• x, y, z

- poło

enie,

•

- orientacja (k

ty Eulera),

•

- pr

dko

ci k

towe.

•

- pr

dko

ci liniowe,

}

{

• a

- pochylenie wirnika,

• a

- przechylenie wirnika,

• a

- skok wirnika,

• a

- skok

migła ogonowego.

}

{

Model dynamiki ma posta

niejawn

(„czarna skrzynka”)

...

...,

)

(

)

(

)

(

−

21.6. Autonomiczne sterowanie

migłowcem

Identyfikacja modelu

Wej

cie

modelu tworz

: stan

zdefiniowany w układzie

zwi

zanym ze

migłowcem,

)

(

Przy opracowaniu sterownika nie u

ywano klasycznego

modelu dynamiki w postaci równa

du i kr

tu, lecz

model

typu wej

cie-wyj

cie

z szumem gaussowskim o wariancji

}

{

)

(

)

(

−

]

[

}

{

oraz sterowanie

w chwili

Wyj

cia

tworz

przyrosty zmiennych stanu dla

k=1,...,8,

Wektor współczynników

jest wyznaczany osobno dla ka

dej

zmiennej stanu na podstawie

pomiarów wej

ść

i wyj

ść

modelu

w chwilach

t = 1,...,m.

21.6. Autonomiczne sterowanie

migłowcem

)

(

−

Współczynniki regresji dla k-tej zmiennej stanu

równe

Do identyfikacji modelu u

yto metody lokalnej regresji liniowej,

któr

zastosowano do ka

dej zmiennej stanu

, k=1,...,8.

























Pomiary wej

ść

i wyj

ść

modelu dynamiki dla

t = 1,...,m

zapisa

w postaci macierzowej nast

puj

)

(

)

(

exp(

(

diag

−

Do identyfikacji modelu wykorzystano sze

ciominutowe

rejestracje sterowania i stanu

migłowca sterowanego zdalnie

przez do

wiadczonego pilota.

























Macierz

zdefiniowana jest poprzez zapytanie

jako

gdzie

jest wektorem wag dla poszczególnych pomiarów.

21.6. Autonomiczne sterowanie

migłowcem

Do reprezentacji strategii
sterowania

migłowcem

w zawisie wykorzystano sie

neuronow

acykliczn

Struktura sieci została wybrana
tak, aby sterowania były
zwi

zane z odpowiadaj

cym

im zmiennym stanu.

Uczenie lotu w zawisie

ΣΣΣΣ

err

ΣΣΣΣ

err

ΣΣΣΣ

err

ΣΣΣΣ

)

tanh(

err

)

tanh(

ΣΣΣΣ

err

ΣΣΣΣ

Bł

dy stanu

wzgl

dem stanu po

Ŝą

danego

odpowiadaj

cego zawisowi s

równe

err

−

Przykładowo, sterowanie pochyleniem wirnika ma posta

Sie

ma dziesi

ęć

wej

ść

, jedn

warstw

ukryt

, cztery wyj

cia

i 32 współczynniki wagowe

21.6. Autonomiczne sterowanie

migłowcem

Funkcje nagrody dla stanu i sterowania maj

postacie

)

(

)

(

−

)

(

)

(

−

Współczynniki

,...,

zapewniaj

porównywalne wkłady

poszczególnych wyrazów do funkcji nagród.

Do wyznaczania przybli

onych u

yteczno

ci strategii

(

)

zastosowana została metoda P

EGASUS.

zastosowana została metoda P

EGASUS.

Poniewa

strategie

gładkimi funkcjami wag sieci, to

maksymalizacja

(

)

e by

przeprowadzona metod

najwi

kszego spadku lub metod

gradientow

Najkosztowniejsz

ęś

algorytmu

EGASUS

jest wyznaczanie sekwencji

stanów

s’

metod

Monte Carlo.

Pierwszy zawis sterowany autonomicznie

⇒

Wyznaczona strategia sterowania
umo

liwiła autonomiczne pilotowanie

migłowcem w zawisie.

21.6. Autonomiczne sterowanie

migłowcem

Do reprezentacji strategii
sterowania

migłowcem w

manewrach u

yto sieci

neuronowej stosowanej dla
zawisu, uzupełnionej trzema
poł

czeniami (

→

Uczenie manewrów

Strategie sterowania dla
manewrów otrzymuje si

poprzez gładkie przej

cie ze

err

Metoda P

EGASUS

pozwoliła wyznaczy

strategi

sterowania

migłowcem dla manewrów wykonywanych na zawodach

migłowców sterowanych zdalnie w Klasie III,

odpowiadaj

cej najwy

szemu poziomowi trudno

ci.

poprzez gładkie przej

cie ze

stanu dla zawisu

do stanu

dla manewru

(t),

Funkcje nagrody dla stanu i sterowania s

zmodyfikowane

pod k

tem uwzgl

dnienia zmiennej trajektorii.

(

→

err

Podsumowanie

• Uczenie ze wzmocnieniem polega na budowie modelu

na podstawie nagród i kar otrzymywanych przez agenta.

• Struktura agenta okre

la rodzaj informacji ucz

cej.

• Istniej

trzy typy struktur agenta uczonego ze wzmocnieniem:

– oparta na modelu

rodowiska

i funkcji u

yteczno

– oparta n funkcji działania

nie wykorzystuj

ca modelu

rodowiska,

– refleksowa, u

ywaj

ca zało

strategi

• Istniej

trzy sposoby uczenia si

yteczno

ci przez agenta:

– bezpo

rednia estymacja u

yteczno

ci,

– adaptacyjne programowanie dynamiczne (ADP),

F.A. Dul 2007

– adaptacyjne programowanie dynamiczne (ADP),
– ró

nicowa (TD).

• Uczenie z funkcj

działania

nie wymaga modelu

rodowiska,

ale mo

e by

utrudnione w

rodowisku zło

onym.

• Wybór działania w trakcie uczenia wymaga kompromisu

pomi

dzy jego skuteczno

i u

yteczno

w nauce.

• Poszukiwanie strategii polega na bezpo

redniej reprezentacji

strategii i jej ulepszaniu na podstawie oceny skuteczno

działa