MDP (II)

Bon dia de nou!

La semana pasada vos vaig presentar els MDP's i el falcó milenari, i vos vaig mostrar com podriem aplicar aquesta representació per a resoldre problemes de trajectoria (El domini de tests Navigation). Estos problemes son molt comuns per a testar algoritmes, i solen variar amb el nombre de obstacles i el tamany. Recordeu les condicions que haviem dit?. Per si acàs les repetisc ací:

1. Cada moviment costa 1 punt de combustible.
2. Si caiguem en un forat negre, la nau es trenca. Igual si caiguem en un estel.
3. Si caiguem en la força de atracció de un estel, els camps en roig, tenim un 50% de probabilitats de ficar orbitant la estrela (anar al seguent camp seguint l'orbita) o del 90% de ser atrets al forat negre.

No ho vaig especificar, pero clar, si caiguem en un forat negre s'acaba el viatge. Per tant, evitem els forats negres. Al mateix temps podem vore que seguir una orbita pot ser satisfactori, perque si ens menegem en la direcció de l'orbit, arrivarem sense problemes.

El resultat pot ser observat en la ilustració seguent:

Podem vore que realment la trajectoria optima calculada per a la nau evita els forats negres i la seua orbita, pero s'aprofita de l'orbita dels estels, per a poder arrivar al estat final. Hem de recordar que la solucio a un d'aquests MDP's es una política optima, i no sols una trajectoria o seqüencia de accions. Es a dir, que cada estat té una acció corresponent, que en aquest cas sempre intenta colocar la nau en la ruta óptima de nou.

L'algoritme que he utilitzat per a resoldre aquest problema ha sigut el LRTDP (Bonnet and Geffner, 2003). Queda lluny de l'objectiu d'aquest blog explicar l'algoritme, pero si que voldria donar alguns resultats i comentar algunes cosetes. Per exemple l'algoritme es molt ràpid per a resoldre problemes, ja que en realitat els estats que no son interesants, no els visita. Per tant l'algoritme resol el problema en tan sols 0,4 segons aproximadament:



En la grafica podem vore la evolució del valor V desde la situació inicial fins a la convergència (no cambia més el valor). La grafica no es molt dificil de entendre, pero si no explique uns conceptes avans, pot pareixes confusa. Avans de iniciar el problema, hem de definir quina seria la recompensa per a cada estat. Per exemple, l'estat meta te una recompensa de 0 i els altres, de -1 (per aixo la pendent negativa).
El valor V(estat-inicial) representa qué guanyaria la nau (el agent inteligent) si estiguera al estat inicial.A cada itercio, esta més clar que aquest estat no es bo per a permaneixer, per aixo el valor va descendent fins que es queda fixe.

En fi, espere que en aquestes entrades tot el mon haja pogut vore de manera més clara com podem conseguir que les maquines realitzen accions inteligents i que facen coses que van més enllà del estrictament programat.

Fins prompte!