Eötvös Loránd Tudományegyetem Informatika Doktori Iskola Az informatika alapjai és módszertana
Intelligens robotikai modellek vezérlés, döntéshozatal és környezettel való interakció megvalósítására A doktori értekezés tézisei
Tudományos témavezető: Dr. Istenes Zoltán Prof. Dr. Horia F. Pop
Doktori hallgató: Hunor Sándor Jakab
A doktori program vezetője: Prof. Dr. Demetrovics János Budapest 2012
1
Bevezetés A robotika mint kutatási terület napjainkban egyre nagyobb népszeruségnek ˝ örvend. Robotikai kutatások egyik legfontosabb célja intelligens robotok fejlesztése, melyek képesek önálló döntéshozatali mechanizmusok kialakítására és új képességek elsajátítására. Ezen dolgozat a robotikai mozgásvezérlés problémájának tanulás által történ˝o megoldására összpontosít, mely alapvet˝o el˝ofeltétele a robotok bizonytalan, strukturálatlan környezetben való muködtetésének. ˝ Az utóbbi évtizedben jelent˝os el˝orelépés történt a robotikai mozgásvezérlés területén. Ennek ellenére a helyváltoztatás vagy tárgyak manipulálásához hasonló alapvet˝o képességek autonóm tanulás által történ˝o elsajátítására nem született általános megoldás. Idegtudományi kutatások rámutattak arra, hogy a különböz˝o biológiai rendszerek a vezérlési feladatokat bels˝o, dinamikát és optimalitást közelít˝o modellek segítségével valósítják meg. Ezen közelít˝o modellek igen hatékonyan képesek bizonyos motor parancsok hosszú távú következményeinek becslésére. Ahhoz, hogy a robotikai mozgásvezérlés terén, a biológiai rendszerekéhez hasonló közelít˝o modelleket tudjunk felépíteni különböz˝o matematikai és algoritmikai eszközökre van szükségünk, melyek a környezettel való interakció során begyujtött ˝ adatokat dolgozzák fel. Ezen kutatás a meger˝osítéses tanulás keretrendszerében fellelhet˝o gépi tanulási módszerekre alapoz, melyek segítségével bizonyos szintu˝ önállóság érhet˝o el a tanuló rendszerekben. A hagyományos meger˝osítéses tanulási módszerek alkalmazása robotvezérlési feladatokra már alacsony komplexitású robotok esetében (ahol a robot kis számú állapottal és végrehajtható muvelettel ˝ rendelkezik) is nehézkes, . A nehézségek egyik f˝o oka a keresési tér méretének exponenciális növekedése a vezérelend˝o rendszer komplexitásának növekedésével, valamint a fizikai komponensek pontatlanságából adódó magas fokú bizonytalanság. Robotok esetében úgy a végrehajtható kísérletek száma, mint ezek természete is korlátozott és a legtöbb esetben folytonos állapot illetve mu˝ velet térrel rendelkeznek. Ennek következtében a kimerít˝o keresési algoritmusok alkalmazása lehetetlenné válik és specializált módszerekre van szükségünk. Ezen dolgozat célja intelligens robotikai tanulási modellek kidolgozásában felmerül˝o alapvet˝o problémák elemzése és enyhítése újszeru˝ meger˝osítéses tanulási módszerek bevezetésével, melyeket kifejezetten a robotikai vezérlési feladatok tartományára fejlesztettem. A legfontosabb probléma területek melyeket ezen dolgozat tárgyal a következ˝ok: folytonos állapot-muvelet ˝ terek kezelése, valós id˝oben (on-line) megvalósítható tanulás, minta hatékonyság, intelligens felfedezési stratégiák és a tapasztalati adatok szekvenciális voltából ered˝o információk feldolgozása. Módszereim validálása érdekében egy sor különböz˝o komplexitású robotikai vezérlési feladatot hoztam létre szimulációs környezetekben. Ezen vezérlési feladatok lehet˝ové teszik a bevezetett újítások valósághu˝ körülmények között történ˝o tesztelését hiszen több szabadságfokkal, folytonos állapot-muvelet ˝ térrel és zajos állapot-átmeneti modellel rendelkeznek.
Robotvezérlési feladatok megoldása megerosítéses ˝ tanulással A robotikai mozgásvezérlés alapját a különböz˝o aktuátorokhoz küldött jelek vezérlési stratégia által történ˝o generálása képezi. A vezérlési stratégia tulajdonképpen egy mu˝ velet kiválasztó mechanizmust definiál, amely lehet˝ové teszi, hogy a robot egy el˝ore meghatározott feladat végrehajtása érdekében mozgásszekvenciákat generáljon. 1 1
Muvelet ˝ alatt egy bizonyos motor parancsot értünk amely végrehajtható a robot valamely aktuátorán. Ez lehet egy bizonyos mértéku˝ forgatónyomaték kifejtése szervo motornál, vagy egy adott szögnek megfe-
2 Formálisan egy vezérlési stratégia egy paraméterezett függvényként definiálható, amely egy s állapotban végrehajtható a muveletre ˝ való leképezést valósít meg. Robotok esetében egy állapotot különböz˝o kinematikai, dinamikai és mérési információkat tartalmazó vektor formájában tárolunk. Az optimális vezérlési stratégia tanulása, környezettel történ˝o interakció (tapasztalatszerzés) során valósul meg, ahol robot bizonyos muveletek ˝ végrehajtása után a begyujtött ˝ információk alapján változtatja a vezérlési stratégia paramétereit. Autonóm tanulás esetében igen fontos megszorítás az el˝ore legyártott tanuló minták hiánya, a robotnak csupán a saját tapasztalati információi állnak rendelkezésére következtetések levonására. Az ilyen fajta tanulás megvalósítása érdekében a meger˝osítéses tanulás keretrendszerében fellehet˝o módszerekhez kell folyamodnunk. A robot csupán végrehajtott muveletei ˝ azonnali értékének megállapítására képes egy jutalomfüggvényen keresztül. Ennek segítségével kell megtanulnia egy jó vezérlési stratégiát, amely a környezettel való interakció során maximalizálja a begyujtött ˝ jutalmak várható értékét. A legtöbb vezérlési feladat esetében, jó stratégia tanulásához nem elégséges az azonnali jutalmak figyelembe vétele. A robotnak olyan következményekkel is számolnia kell amelyek a jöv˝obe el˝oretekintve tetsz˝olegesen távoli id˝opillanatban következhetnek be. Vezérlési feladatok esetében a legtöbb esetben feltételezzük, hogy a tanuló rendszer rendelkezik a Markov tulajdonsággal: a rendszerben fellép˝o jöv˝obeli állapotok feltételes valószínusége ˝ csak az aktuális állapottól függ, nem szükséges a múltbéli állapotokat nyilván tartani. [Papoulis, 1991]. A Markov tulajdonsággal rendelkez˝o szekvenciális döntéshozatali feladatokat matematikailag Markov döntési folyamatok segítségével modellezzük. A Markov döntési folyamatoknak igen fontos szerepe van a meger˝osítéses tanulás fejl˝odésében, hiszen ezek képezik a legkorábbi megoldások matematikai alapját. 1. Meghatározás. Folytonos Markov döntési folyamatnak nevezzük az M(S, A, P, R) négyest, ahol a következ˝o jelöléseket használtuk: S az állapotok halmaza, A a muveletek ˝ halmaza , P : 0 0 S × A × S → [0, 1], melyet P (s |s, a) is írhatunk, az s állapotba érkezés valószínuségét ˝ jelöli amennyiben egy s állapotban a muveletet ˝ hajtunk végre . P -t átmeneti valószínuségnek ˝ nevezzük, ez képezi a tanuló rendszer modelljét. R : S × A → R, r = R(s, a) a jutalom függvényt jelöli. A robot döntési hozatali mechanizmusának absztrakt megfogalmazásaként definiálhatjuk a πθ : S × A → [0, 1] paraméterezett stratégiát amely egy valószínuségi ˝ eloszlás az állapot-muvelet ˝ téren és egy leképezést valósít meg bármely s ∈ S állapotból és a ∈ A muveletb˝ ˝ ol a π (a |s) feltételes valószínuségen ˝ keresztül, amely az a muvelet ˝ s állapotban való végrehajtásának valószínuségét ˝ jelöli. Felfedez˝o muveletek ˝ beépíthet˝osége érdekében általában sztochasztikus stratégiákkal dolgozunk, melyeket egy f : S → R determinisztikus vezérl˝ohöz történ˝o Gauss eloszlású Σex = σ I szórású zaj hozzáadásával állíthatunk el˝o a legegyszerubb ˝ módon. πθ (a|s) = f(s, θc ) + ∼ N (0, σ I) (a − fθc (s))2 1 = √ exp − (1) σ2 2πσ T ahol πθ (·, s) a θ = θTc σ által paraméterezett sztochasztikus stratégia, nulla átlagú Gauss eloszlású zaj σ szórással, és θc a determinisztikus vezérl˝o paraméter vektora. A vezérl˝onek fontos szerepe van a mozgásvezérlési stratégiák kialakításában, és számos különböz˝o modell került leírásra a szakirodalomban. Ezek közül megemlítenénk a különböz˝o trajektória generáló kontrollereket, ilyenek a spline alapú kontrollerek, dinamikus motor primitívek, és a közvetlen motor vezérl˝ok mint amilyen a cerebellar model articulation controller (CMAC). A fentiekben leírt döntéshozatali feladat megoldását az optimális lel˝o rotáció léptet˝omotorok esetében.
3 stratégia π∗ megtalálása jelenti, amely a kumulatív jutalmak várható értékét maximalizálja: "∞ # X Jπ = Eπ γt rt+1 (2) π∗ = πθ∗ = argmax (Jπ ) , with π
t=0
π
J az optimalizálás objektív függvénye, a diszkontált kumulatív jutalmak várható értéke, ahol a várható értéket a πθ stratégiára értékeljük ki és r1 , r2 , . . . az azonnali jutalmakat jelöli. A környezettel való interakció során a robot az érzékel˝oin keresztül begyujtött ˝ információkat használja fel különböz˝o bels˝o modellek felépítésére, melyek segítségével muvelet ˝ kiválasztó stratégiák értelmezhet˝oek: Ezen modelleket értékel˝ofüggvényeknek nevezzük és úgy állapot mint állapot-muvelet ˝ téren értelmezhet˝oek: "∞ # X Qπ (s, a) = Eπ γt rt |s0 = s, a0 = a (3) t=0
A hagyományos meger˝osítéses tanulási módszerek nagy része értékel˝o függvények közelítésén alapszik. A Bellman egyenletek segítségével megfogalmazható egy általános értékel˝o függvény tanulási mechanizmus: X X Qπ (s, a) = P(s 0 |s, a) π(a 0 |s 0 ) (R(s, a) + γQπ (s 0 , a 0 )) s 0 ∈S
a 0 ∈A
Egy másik stratégia tanulási módszer a gradiens alapú stratégia keresés, amely robotikai kontroll feladatok esetében jobban alkalmazható. " H−1 # X ∇θ J(θ) = Eτ ∇θ log π(at |st )R(τ) τ = {(s1 , a1 , r1 ), . . . , (sH , aH , rH )} (4) t=0
Ebben a formában kifejezve a gradiens közelíthet˝o empirikus átlagolással az állapotátmeneti valószínuségek ˝ ismerete nélkül[Williams, 1992]. Kutatásaim során nemparametrikus függvényközelítési módszerek, f˝oleg Gauss folyamattal történ˝o regresszió alkalmazhatóságát vizsgáltam tudásreprezentáció értékel˝o függvény formájában történ˝o felépítésére. Ezt kombinálva értékel˝o függvény alapú valamint gradiens alapú tanulási módszerekkel újszeru˝ algoritmusokat dolgoztam ki melyek jobban illeszkednek a robotikai vezérlési feladatok doméinumába a hagyományos módszereknél.
I Tézis: Értékelofüggvények ˝ nem-parametrikus közelítése robot-vezérlési feladatok esetében A megszerzett ismeretek értékel˝ofüggvény formájában, bels˝o modellként történ˝o felépítése fontos eleme a legtöbb meger˝osítéses tanulási módszernek. A folytonos állapotmuvelet ˝ terek kezelése, valamint a fizikai rendszerek magas fokú bizonytalanságából adódó problémák enyhítése érdekében nemparametrikus függvényközelít˝ok használhatóságát vizsgáltam, külön figyelmet szentelve a Gauss folyamatokkal történ˝o értékel˝ofüggvény közelítés el˝onyeinek és hátrányainak kiemelésére [Jakab és Csató, 2010]. Az értékel˝ofüggvényt egy Gauss folyamat segítségével modellezzük függvénytérben. A környezettel való interakció során a robot egy n állapot-muvelet ˝ párból és ezekhez tartozó jutalmakból álló trajektóriát ír le: τ = [(s1 , a1 , r1 ), . . . , (sH , aH , rH )]. Ha m különböz˝o trajektóriát járunk be, a D = [(x1 , r1 ), . . . , (xn , rn )]
4 tanuló halmaz áll a rendelkezésünkre ahol n = mH adatpontunk van. Az adathalmazban def
szerepl˝o állapot-muvelet ˝ párok xt = (st , at ) ∈ D valamint az ezekhez tartozó kumulatív P i−t jutalmak Ret(xt ) = Ret(st , at ) = H R(st , at ) képezik a tanító mintáink halmazát. i=t γ Ezek segítségével egy teljes valószínuségi ˝ modellt kaphatunk az értékel˝ofüggvényünkr˝ol a következ˝o formában: QGP |D, xn+1 ∼ N µn+1 , σ2n+1 µn+1 = kn+1 αn
σ2n+1 = kq (xn+1 , xn+1 ) − kn+1 Cn kTn+1 ,
(5)
ahol αn és Cn a Gauss folyamat paraméterei – részletekért lásd: [Rasmussen és Williams, 2006] – és a következ˝o alakkal rendelkeznek: ^ αn = [Knq + Σn ]−1 Q, Cn = [Knq + Σn ]−1 . (6) A tanító minták halmaza (ebben az esetben D), melyek alapján a GP paraméterei α és C meghatározásra kerülnek, a bázis vektor halmaz nevet viseli. A fent leírt függvényközelítés egyetlen meghatározatlan eleme a kovariancia függvény. A kovariancia függvény megfelel˝o kiválasztása valamint paramétereinek finomhangolása fontos el˝ofeltétele a jó közelítési teljesítmény elérésének. A robotikai vezérlési feladatok esetében fellép˝o szekvenciális sémának megfelel˝oen, a Gauss folyamattal történ˝o regresszió on-line változatát használjuk, ahol az α és C paraméterek minden új adatpont érkezésekor frissít˝odnek. Az on-line frissítés lehet˝ové teszi az algoritmus, környezettel való interakcióval párhuzamos futtatását. 1. Tézis. Gauss folyamattal közelített értékel˝ofüggvények segítségével a gradiens varianciája nagy mértékben csökkenthet˝o gradiens alapú stratégia keres˝o módszerek esetében. Ennek következtében gyorsabb konvergencia és jobb végteljesítmény érhet˝o el. Id˝obeli differenciákon alapuló módszerek esetében is jó eredmények érhet˝oek el. [Jakab et al., 2011] [Jakab és Csató, 2010]. A stratégia gradiensének kiszámolása, a kísérletek során begyujtött ˝ adatok segítségével a likelihood trükk segítségével, valósítható meg. Emellett felcseréljük a Monte Carlo mintavételezett kumulatív jutalmakat k lépéses diszkontált jutalmak valamint a Gauss folyamat predikciójának kombinációjára. A gradiens a következ˝o analitikus alakban fejezhet˝o ki: !+ * H−1 k−1 X X −1 ^ ∇θ log π(at |st ) γk R(st+k , at+k ) + kxt+k [Kq + Σ] Q (7) ∇θ J(θ) = i=0
t=0
τ
A Gauss folyamattal történ˝o közelítés alkalmazható id˝obeli differenciákon alapuló mód˝ párokból álló τ trajektóriát. szerek esetében is. Tekintsük a {(st , at )}t=1,H állapot-muvelet A trajektória végrehajtása során látogatott állapot-muvelet ˝ párok és a közvetlen jutalmak segítségével valósítjuk meg a Gauss folyamat tanítását ahol a célváltozók az azonnali jutalmak és az el˝oz˝o GP közelítésb˝ol származó értékek kombinációjaként vannak megadva: m
Q (st , at ) =
m−1 X
γi R(st+i , at+i ) + γm max Qpred (st+m , at+m ),
i=0
a
(8)
A fenti képletben R(st , at ) a t id˝opontban megfigyelt jutalmat, γ ∈ (0, 1] a diszkontálási rátát, és Qpred a t + m id˝opillanatban látogatott állapot-muvelet ˝ párnak megfelel˝o Gauss folyamat által becsült értéket jelenti. Továbbá a Q-tanulás szabályát és az on-line Gauss folyamat frissítési egyenleteit kombinálva a következ˝o kifejezésekhez jutunk: q
n+1
^ 1 (st , at ) − Qpred (st , at ) Q = σ20 + σ2n+1 α R(st , at ) + γ maxa Qpred (st+1 , a) − Qpred (st , at ) = . σ20 + σ2n+1
5 100 5
80
0
70 60 50 40
λ=0 λ=10
30
λ=100
Average performance
percentage of new basis functions
90
−5
−10 λ=0 λ = 100
−15
λ = 103
λ=400
20
3
λ=10
−20
10 0
10
20 30 40 50 Number of policy improvements
10
60
20
30
40
50
60
Number of policy improvements
(a)
(b)
1. ábra. A λ paraméter kihatása a (a) teljesítmény változására (b) a bázis vektorok halmazának összetételére A fenti kifejezés értelmében az id˝obeli differenciákból ered˝o hibák értékel˝ofüggvény közelítésbe történ˝o beépítése megfelel a sztochasztikus átlagolásnak, amely a tabuláris Q-tanulás esetén is megfigyelhet˝o. A valósághu˝ tanuló rendszerek esetében fellép˝o magas fokú bizonytalanság következtében a tanuló algoritmusok teljesítményét nagy mértékben befolyásolhatják a zajos megfigyelések illetve a küls˝o behatások. A Gauss folyamattal kapott teljes valószínuségi ˝ modell létez˝o, gradiens alapú és értékel˝ofüggvény alapú módszerekkel történ˝o kombinálása jelent˝os teljesítmény növekedéshez vezet robotikai kontroll feladatok esetében.
II. Tézis: Minta hatékonyság és stabilitás növelése A fentiekben felvázolt nem-parametrikus függvényközelítés esetében, a számítási költségek köbösen növekednek a tanító minták számával. Ezen probléma kiküszöbölése érdekében bemutatunk egy kölcsönös információn alapuló ritkítási mechanizmust, amely csökkenti a Gauss folyamattal történ˝o közelítés számítási költségeit és további lehet˝oségeket tár fel a minta hatékonyság javítására. Egy új adat pontot kifejezhetünk az eddig vizsgált adatpontok jellemz˝o térben vett lineáris kombinációjaként: φn+1 = γn+1 φres +
n X
e^n+1 (i)φi
(9)
i=1
A vetítés kordinátáinak és a közelítés hibájának analitikus alakja megadható a következ˝o képpen: (10) e^n+1 = [Knq ]−1 kn+1 , γn+1 = kq (xn+1 , xn+1 ) − kTn+1 e^n+1 ahol Knq a kernel Gram matrix az els˝o n adatpontra, és kn+1 a kernel függvény kiértékelése az új és régi adatpontok kombinációira: T kn+1 = kq (x1 , xn+1 ) . . . kq (xn , xn+1 )
(11)
A γ paraméter segítségével dönthetünk egy adatpont bázis vektor halmazhoz történ˝o hozzáadásáról. 2. Tézis. Kifejlesztettem egy újszeru˝ ritkítási mechanizmust [Jakab és Csató, 2011], amely lehet˝ové teszi az értékel˝o függvény stratégia frissítések közötti újrakezdésének elkerülésé. A módszer növeli
6 a közelített értékel˝ofüggvény stabilitását és újrahasznosítja a régi tanuló adatokat. Értékel˝o függvény alapú módszerek esetében lehet˝ové teszi az azonnali frissítést és kiküszöböli a parametrikus függvényközelít˝ok esetében észlelt fluktuációkat. A módszer alapötlete egy id˝o függ˝o változó hozzárendelése a tréning adatokhoz: D = {(x1 , y1 ), . . . xn , yn } → {(x1 , y1 , t1 ), . . . (xn , yn , tn )}
(12)
Ugyanakkor bevezetünk egy módosított, kölcsönös információn alapuló pontozási mechanizmust amely az id˝ofügg˝o változó alapján lepontozza a régi tanítómintákat ezáltal el˝osegítve ezek miel˝obbi lecserélését. Egy új adatpont hozzáadásakor kiszámítjuk a módosított pontozási értékeket ε 0 (·) minden bázis vektor esetében: ε 0 (i) = (1 − λ)
α2 (i) + λg (t(i)) , q(i) + c(i)
(13)
ahol a λ ∈ [0, 1] változó az információ vesztés és a közelítés pontossága közötti egyensúlyozást teszi lehet˝ové. A legalacsonyabb pontszámmal rendelkez˝o bázis vektort felcseréljük az új adatpontra. Itt g(·) egy függvény amelyet a bázis vektorokhoz rendelt id˝ováltozó alapján értékelünk ki. Kísérleteink során exponenciális és logit függvényekkel próbálkoztunk: ti / max(ti ) g(ti ) = c exp ti − min(ti ) g(ti ) = c log i = 1...n (14) i 1 − ti / max(ti ) Az 1-es ábra a bázis vektor halmaz összetételét szemlélteti különböz˝o λ értékek esetében. A λ értéke nagy mértékben befolyásolja a tanuló algoritmusok teljesítményét is.
III. Tézis: Intelligens felfedezo˝ stratégiák kifejlesztése A harmadik témakör, melynek vizsgálatával ezen tézis foglalkozik, a felfedez˝o muveletek ˝ hatékonyabbá tétele. Adaptív felfedez˝o stratégiák létrehozását vizsgáltam, az el˝obbiekben felvázolt értékel˝ofüggvény közelítésb˝ol ered˝o teljes valószínuségi ˝ modell [Jakab, 2010] segítségével. 3. Tézis. Adaptív felfedez˝o stratégiát fejlesztettem ki, amely a Gauss folyamattal közelített modell megbízhatóságához igazítja a felfedez˝o muveletek ˝ szórását. Ennek következtében a felfedez˝o muveletek ˝ az állapot-muvelet ˝ tér magas bizonytalansággal rendelkez˝o tartományait célozzák meg [Jakab és Csató, 2011],[Jakab és Csató, 2012b] amely az állapot-muvelet ˝ tér alaposabb bejárásához vezet. Az így létrehozott sztochasztikus muvelet ˝ kiválasztási stratégia a következ˝o formában adható meg: πθ = f(s, θ) + N (0, σ2GP I) σ2GP = λ kq (x∗ , x∗ ) − k∗ Cn k∗T def
ahol x∗ = {s, f(s, θ)}
(15)
x∗ = (s, f(s, θ)) egy adott állapot és a kontroller által generált muveletb˝ ˝ ol álló páros, kq kovariancia függvény, Cn a Gauss folyamat paramétere n adatpont feldolgozása után. A tanulás el˝orehaladtával a modell megbízhatósága egyre növekedik ami a becslési szórás csökkenéséhez, ezáltal a felfedez˝o muveletek ˝ ritkulásához és az értékel˝o függvény stabilizálódásához vezet.
7
2.6
2.6
2.4
2.4 7
2.2 6
2 5
1.8 4
1.6 −8
3
−6 −4
7
2.2 6
2 5
1.8 4
1.6 −10
3 −5
2
−2 0
2 0
2
1
4 6 8
0
1 5 10
0
4. Tézis. Kifejlesztettem egy Gibbs eloszláson alapuló sztochasztikus vezérlési stratégiát ahol a különböz˝o muveletekhez ˝ rendelt energiák a Gauss folyamat által közelített értékek függvényében vannak meghatározva. Ennek segítségével a felfedez˝o muveleteket ˝ az állapot-muvelet ˝ tér releváns régióira korlátozhatjuk amely környezettel való interakciók számának csökkenéséhez és gyorsabb konvergenciához vezet [Jakab és Csató, 2011],[Jakab és Csató, 2012b]. A bevezetett új vezérlési stratégia a mohó kiválasztás és a kontroller által visszatérített muveletek ˝ f(s, θ) követése között képez átmenetet ugyanakkor lehet˝ové teszi a felfedez˝o muveletek ˝ által a robot olyan régiókba történ˝o vezérlését amelyek magasabb becsült értékkel rendelkeznek. A generált állapot eloszlás a kontroller által generált állapot eloszlástól nem tér el nagy mértékben. Z eβE(s,a) , ahol Z(β) = da eβE(s,a) (16) π(a|s) = Z(β) A Z(θ) elem egy normalizáló konstans, β a fordított h˝omérséklet. A h˝omérséklet határozza meg, hogy az egyes muveletekhez ˝ rendelt energiák közötti különbségek mennyire befolyásolják a kiválasztási valószínuségeket. ˝ A determinisztikus kontroller figyelembe vétele érdekében fθ az E(s, a) energia függvényt úgy építjük fel, hogy csupán az fθ (s) közelében elhelyezked˝o muveletek ˝ rendelkezzenek magas kiválasztási valószínuséggel. ˝ Az energia függvény a következ˝o alakban adható meg: k a − fθ (s) k2 E(s, a) = QGP (s, a) · exp − 2σ2e A fenti energiafüggvényt a (16)-os egyenletben leírt vezérlési stratégiával kombinálva a következ˝o kifejezést kapjuk: h i 2 exp βQGP (s, a) · exp − ka−f2σθ 2(s)k e π(a|s) = (17) Z(β) Z k a − fθ (s) k2 Z(β) = da exp βQGP (s, a) · exp − 2σ2e A 2-es ábra a fentiekben leírt muvelet ˝ kiválasztási stratégiát szemlélteti. Ahogyan azt [Jakab és Csató, 2011]és[Jakab és Csató, 2012b]-ben kimutattuk, a modell megbízhatóságon alapuló keresési zaj és irányváltoztatási módszerek nagy mértékben növelik a kontroll stratégiák tanulásának hatékonyságát.
8 1
1000
0.9
900 800
0.7
QGP(s,a)
0.6
fθ(s)
Selection frequencies
0.8
E(s,a)
0.5
π(a|s)
0.4 0.3
700 600 500 400 300
0.2
200
0.1
100
0 −5
0 Actions
5
0 −6
−4
−2
0 Actions
2
4
2. ábra. A gibbs vezérlési stratégia β−1 = 1 esetében
IV. Tézis: Geodezikus távolságokon alapuló on-line tanulás, szerkezeti tulajdonságok figyelembevételével Számos robotvezérlési feladat esetében az értékel˝ofüggvények szakadásokat tartalmaznak az állapot-muvelet ˝ tér különböz˝o régióiban. Ezen szakadások pontos reprezentációja nagy mértékben befolyásolja a tanuló algoritmusok teljesítményét. A Gauss folyamatok használatának egyik legnagyobb hátránya az, hogy csupán folytonos függvények közelítése valósítható meg hagyományos kernel függvényekkel. Stacionárius kernel függvények az adatpontok közötti távolságok segítségével muködnek. ˝ A GP becslés egy új adatpontra a tanító minták súlyozott átlagaként fogható fel, ahol a súlyok a minták és az adatpont közötti Euklideszi távolság függvényei. Ezzel ellentétben id˝obeli differenciákon alapuló módszerek esetében egy bizonyos állapot-muvelet ˝ párhoz tartozó érték csupán azon állapotok értékeit˝ol függ amelyek között átmenet jöhet létre a rendszer dinamikája alapján. 5. Tézis. A tézis utolsó hozzájárulásaként bevezettem egy módszert mellyel növelhet˝o a Gauss folyamatokkal történ˝o értékel˝o függvények közelítésének pontossága. Ezt egy új kernel függvény család bevezetésével értem el amely a MDP által indukált gráfon értelmezett geodezikus távolságokon van definiálva. Kidolgoztam egy módszert a Markov döntési folyamat által indukált gráf struktúra tanulás folyamán történ˝o felépítésére. Az új kernel függvény a gráfon értelmezett legrövidebb utakat használja távolsági mértékként[Jakab, 2011b],[Jakab és Csató, 2012a]. A tézis ötödik fejezetében bemutatunk egy gráf struktúra felépítési mechanizmust. A gráf csomópointjait a kísérletek során látogatott állapot-muvelet ˝ párok képezik, új csomópontok hozzáadása a gráfhoz a Gauss folyamat on-line tanításával párhuzamosan történik. Megmutatjuk, hogy ez a felépítési módszer egy ritka, összekötött gráf struktúrához vezet, amely a rendszer állapot átmeneteinek kezdetleges reprezentációjaként fogható fel. Legyen G(V, E) MDP által indukált ritka gráf sturktúra, ahol V a csomópontok halmaza és E az élek halmaza. A gráf csomópontjai közötti kapcsolatokat a Gauss folyamat bázisvektorához történ˝o új pont hozzáadásával párhuzamosan végezzük a következ˝o szabályok alapján: kxi − xt k2 if exp −kxi − xt k2 > γ γ ∈ [0, 1] i = 1...n (18) Ext ,xi = 0 otherwise A γ küszöbérték egy xt csomópontjainak számát közvetetten korlátozza. A G(V, E) gráf struktúra alapján egy új kernel függvényt értelmezhetünk amely a gráfon értelmezett
6
9 6
5
6
5
5
4
4
θ
3
θ
θ
4
6
3
3
2
2
2
1
1
1
−8
−6
−4
−2
0
ω
2
4
6
8
−8
−6
−4
−2
0
ω
2
4
6
8
−8
−6
−4
−2
0
ω
2
4
6
8
3. ábra. (a) Euklideszi távolság , (b)legrövidebb út eq. (21) , (c) interpolált legrövidebb út eq. (20) legrövidebb utakat használja távolsági mértékként. SP(x, x 0 )2 0 ksp (x, x ) = A exp − 2σsp
(19)
Ahol A és σsp a kernel függvény hiperparaméterei. Sajnos a legrövidebb út csupán a bázis vektor halmazban jelen lev˝o pontok között értelmezett ezért egy interpolációs módszerre van szükségünk a folytonos állapot-muvelettér ˝ lekezelésére: (1)
SP(x∗ , xj ) = kx∗ − xi k2 + Pi,j
where xi = argminkx∗ − x` k2
(20)
x` ∈BV (2)
= kTx∗ Pej =
n X
k(x∗ , xi )Pi,j
(21)
i=1
ahol P a bázis vektorok közötti legrövidebb utak hosszát tartalmazó mátrix és ej j-dik n hosszúságú egységvektor. Az els˝o módszer csupán az új x∗ ponthoz legközelebb es˝o bázisvektort használja az xj -be vezet˝o legrövidebb út megkereséséhez, amíg a második az összes bázis vektor között átlagol. A 3-as ábra a fentiekben leírt értékel˝o függvény közelít˝o módszereket szemlélteti. Az ábrán jól megfigyelhet˝oek az értékel˝ofüggvényben jelen lev˝o nem folytonos régiók a geodezikus távolságon alapuló közelítések esetében, míg a standard Gauss folyamattal történ˝o közelítés ezeket kisimítja.
10
A szerzo˝ tézishez kötod ˝ o˝ publikációi Megjelent cikkek: 1. Jakab, H. Geodesic distance based kernel construction for Gaussian process value function approximation. KEPT-2011:Knowledge Engineering Principles and Techniques International Conference, Selected Papers., 2011c. ISSN 2067-1180 2. Jakab, H. Geodesic distance based kernel construction for Gaussian process value function approximation. Studia Universitatis Babes-Bolyai Series Informatica, 61(3):51– 57, 2011b. ISSN 1224-869 3. Jakab, H. és Csató, L. Improving Gaussian process value function approximation in policy gradient algorithms. In Honkela, T., Duch, W., Girolami, M., és Kaski, S., editors, Artificial Neural Networks and Machine Learning – ICANN 2011, volume 6792 of Lecture Notes in Computer Science, pages 221–228. Springer, 2011. ISBN 978-3-64221737-1 4. Jakab, H. Controlling the swinging atwood’s machine using reinforcement learning. Müszaki tudományos füzetek: XVI. FMTÜ international scientific conference, pages 141– 145, 2011a. ISSN 2067 - 6808 5. Jakab, H., Bócsi, B., és Csató, L. Non-parametric value function approximation in robotics. In Pop, H. F., editor, MACS2010: The 8th Joint Conference on Mathematics and Computer Science, volume Selected Papers, pages 235–248. Györ:NOVADAT, 2011. ISBN 978-963-9056-38-1 6. Jakab, H. Guided exploration in policy gradient algorithms using Gaussian process function approximation. In volume of extended abstracts CSCS2010, Conference of PhD Students in Computer Science, 2010 7. Jakab, H. és Csató, L. Using Gaussian processes for variance reduction in policy gradient algorithms. In Egri-Nagy, A., Kovács, E., Kovásznai, G., Kusper, G., és Tómács, T., editors, ICAI2010: Proceedings of the 8th International Conference on Applied Informatics, volume 1, pages 55–63, Eger, Hungary, 2010. BVB. ISBN 978-963-989-723 8. Jakab, H. és Csató, L. Q-learning and policy gradient methods. Studia Universitatis Babes-Bolyai Series Informatica, 59:175–179, 2009. ISSN 1224-869 Elfogadott cikkek: • Jakab, H. és Csató, L. Manifold-based non-parametric learning of action-value functions. In European Symposium on Artificial Neural Networks (ESANN), Bruges, Belgium., 2012a(Accepted) Beküldött cikkek: • Jakab, H. és Csató, L. Reinforcement learning with guided policy search using Gaussian processes. In International Joint Conference on Neural Networks (IJCNN), 2012b • Jakab, H. és Csató, L. Guided exploration in direct policy search with Gaussian processes. Acta Cybernetica, Under Review, 2011
