MDP's i falcons milenaris

El Falcó Milenari

Esta es la primera entrada seria que vullc publicar, per tant volia fer honor al nom del blog, posant alguna cosa d'una de les "naus espacials" més conegudes i carismàtiques. Estem parlant del falcó milenari, una de les principals protagonistes de Star Wars. Tots (o quase tots) hem vist com aquesta nau fugia dels grans creuers de l'imperi Galàctic botant a l'hiperespai, que teóricament seria la velocitat de la llum. No vaig a entrar en el tema fisic de la posibilitat de viatjar a la velocitat de la llum, ja que aci ens centrarem més bé en la Inteligencia Artificial, i concretament en "L'ordinador de abordo".

En la primera part de la trilogia de Star Wars, ens presenten a Han Solo en la Cantina de Mos Eisley (la cançó es famosa), i vegem com Luke Skywalker i el seu mentor Obi wan Kenobi estan procurant un transport urgent al estar perseguits per els soldats imperials. Al cap d'uns minuts, pujen a la nau i intenten fugir del planeta, amb la mala sort que son descoberts per destructors imperials (personalment la meua nau favorita de Star Wars), i tenen que apresarse a fugir al hiperespai, on teóricament ningú els podria alcançar.

Fugint dels destructors imperials

 En un dels moments, Luke li demana apresarse a Han Solo, pero este li respon que no pot fer res ja que la computadora esta calculant la millor trajectoria per a pasar a la velocitat de la llum, i no pegarsela contra algun planeta. Com en la pelicula no se'ns explica com funciona aquesta tecnologia, m'he permitit de sugerir una interpretació, que es la que vaig a explicar utilitzant Processos de decissió Markovians (MDPs).

En primer lloc, vaig a intentar definir un MDP:
Un MDP es un model de problemes de planejament, amb accions probabilistiques i observacions totals, i on la probabilitat del proxim estat, no depén de la historia de les probabilitats anteriors, sino de l'estat actual només. Un MDP com a sistema ha de complir amb les seguents característiques:

1. Accions no-deterministiques (efectes probabilistics): Com hem indicat, les accions son probabilistiques. Es una millor manera de aproximarnos de la vida real.
2. Observació total: Podem observar tot el sistema en temps de planejament.
3. Metes exteses: Les metes son un conjunt de estats que maximitzen una funció de utilitat definida.

La solució a un MDP, és una política óptima, que maximitze la recompensa esperada. No vos asusteu i anem per parts. Quan dic politica, em referisc a una funció que transforma els estats en accions (π:S->A). O siga, si estic en l'estat S1, quina es la millor acció que puc fer? Això es al que em referisc com a política.

Per a entendre millor el problema, imagineu que el falco milenari tinga un mapa de les galaxies, amb els meteors, planetes, estels i demés. Un mapa que li permetisca poder vore on estan ocorrent "els camps de asteroids" i demes problemes que podrien afectar la trajectoria de la nau. El mapa li permet al sistema de observar tot l'espai, sense que ninguna part no siga visible (es una suposicició). Ara imagineu que com la nau no es perfecta (es un poc velleta), i a més en l'espai hi ha radiació, pols, i demés xatarra espacial, cada moviment pot ser fatal, sense contar la força atractiva de alguns cosos celestials dels quals hi hauria que mantindre's allunyat. Encara que el sistema li diguera a la nau, de anar endavant, aquesta pot tindre algun problema i trencarse intentant anar endavant, o desviarse massa cap a un forat negre. Aleshores colocarem una probabilitat a cada moviment de realitzarse correctament i una probabilitat menuda de realitzarse incorrectament i acabar o trencada, o al mateix lloc, o en un altre lloc. I per últim, la funcio de utilitat quina seria? Fàcil, si volem anar al sistema Alderaan, el estar a Alderaan!.

Fins ací tot clar? Imagineu-vos el mapa simplificat de la galaxia que vos presente a continuació:

Model en miniatura de una galaxia.

Sé que es un poc roinet com a mapa galactic, pero estic utilitzant encara el Paint. Per als proposits que vos descrit deuria de servir. Imagineu-vos que el Falcó milenari esta al canto dret baix de tot (la raia blava), i els sistema de Alderaan, el destí está al cantó superior esquerre (la estrela verda). Els punts negres son forats negres, i els punts grocs son estels. Les raies rojes representen l'atracció gravitatória de cada cos celest. Per a simplificar el model, no he colocat ningun asteroide solt ni res que puga mudar de trajectoria mentre es calcula el plan óptim de navegació.

Doncs be, el sistema de navigació del Falco milenari deu de implementar uns algoritmes que resolguen MDP's, de manera ràpida i eficient. Com la entrada s'esta fent llarga, vos propose com a repte que intenteu resoldre quina seria la trajectoria optima que deuria fer la nau, tenint en compte les seguents característiques:

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.

Evidentment, per a una persona seria fàcil resoldreho amb un esquema tan xicotet, i limitat. Imagineuvos ara tindre que calcular una trajectoria del tamany de una galaxia!
Al pròxim post, la resposta i les aclaracions. Ens veiem als comentaris!