Vés enrere

Adrià Garriga: Solving Montezuma's Revenge with Planning and Reinforcement Learning

Adrià Garriga: Solving Montezuma's Revenge with Planning and Reinforcement Learning

Adrià Garriga, graduat en Enginyeria Informàtica per l'Escola Superior Politècnica (ESUP) de la UPF, ha estat guardonat amb el Premi Maria de Maeztu per a la Reproductibilitat en Programari, premi al Millor Projecte de Fi de Grau a Espanya en aquesta categoria, pel seu treball Solving Montezuma's Revenge with Planning and Reinforcement Learning.

15.12.2017

 

 

Adrià Garriga ens dedica unes paraules després de guanyar el El Premi Maria de Maeztu per a la Reproductibilitat en Programari,premi al Millor Projecte de Fi de Grau a Espanya.

"He estudiat Enginyeria Informàtica. Durant aquests quatre anys he après molt, i crescut immensament com a persona. El currículum que he cursat és tan bo com el que es pugui trobar a qualsevol altra universitat del món, i els professors no han fallat mai a resoldre els meus dubtes sobre el material. Tot i així, les experiències que més m'han marcat han estat fora de l'aula.

 

Primer vaig començar a involucrar-me en hackathons, maratons de creació ràpida de solucions tecnològiques a un problema. Després, juntament amb dos amics, vàrem crear una startup, MonkingMe. Allà vaig aprendre com manejar projectes de programari més grans i amb usuaris que en patirien els errors, i també sobre negocis. Finalment i molt importantment, em vaig involucrar en l'equip universitari de programació competitiva, on solucionem problemes d'algorítmica avançada el més ràpid possible. Cada any tenen problemes per trobar gent per l'equip, i és una llàstima; perquè les famoses "entrevistes difícils" de les glamuroses empreses de tecnologia com Google, Facebook, Microsoft, Apple, ..., no són res comparades amb els problemes que l'equip entrena per resoldre.

Va ser a partir del contacte amb els entrenadors de l'equip, Javier Segovia i Anders Jonsson, que vaig començar a interessar-me per la recerca. Ells dos són doctorand i professor al DTIC. Viatjant cap a una competició, vaig començar a llegir una tesi sobre reinforcement learning ("aprenentatge per reforç", RL) que en Javier estava estudiant, i ho vaig trobar fascinant. Un temps després vaig deixar l'empresa per això.

El meu treball de fi de grau, "Solving Montezuma's Revenge with Planning and Reinforcement Learning", és en part sobre aquest tema. És recerca sobre agents que solucionen processos de decisió seqüencials (SDP, sigles en anglès). En un SDP, l'agent ha de prendre decisions contínuament, i després de cada decisió obté una recompensa. L'objectiu és maximitzar aquesta recompensa. Un tipus de SDP sobre el qual és molt fàcil de provar algoritmes, per la seva fàcil emulació en un ordinador i la gran varietat que n'existeix ja feta, són els videojocs. Una col·lecció de jocs especialment ràpids d'emular són els d'Atari 2600, una consola dels anys 80. El 2015, l'empresa d'investigació DeepMind va publicar un algoritme, "Deep Q Networks" (DQN), que, només veient la pantalla del joc i la puntuació, aconseguia puntuacions superiors a les d'un jugador humà per la majoria de jocs. En alguns jocs, però, la seva puntuació era molt pitjor a la d'una persona, en alguns casos zero. Un d'aquests jocs és Montezuma's Revenge. En recerca d'intel·ligència artificial (IA), és sabut que és molt més difícil dissenyar un algoritme general, que solucioni molts problemes, que un de concret, que només en solucioni un. Així que, en el meu treball, vaig decidir solucionar només el problema de Montezuma's Revenge, per tenir una idea de com es podria fer un algoritme que solucionés els jocs que DQN no sap jugar.

 

El problema amb l'algoritme DQN és que no entén el joc en termes de personatges, objectes, un terra i gravetat, ... Al menys, no al principi, ha d'aprendre aquestes coses. Així, l'algoritme pren decisions aleatòries al començar. Depenent de la puntuació obtinguda amb cada acció aprèn, generalitzant, quines són les accions que porten a més recompensa. Si és molt improbable arribar de forma aleatòria a obtenir una puntuació diferent de zero, DQN no pot aprendre a jugar, només 

pot prendre accions a cegues. Això passa en general amb els algoritmes de RL. Així doncs, vaig utilitzar un algoritme de planificació en línia, que en cada moment mira una part de les possibles futures seqüències de decisions, i tria la millor. El resultat d'aquest algoritme es pot veure aquí: https://www.youtube.com/watch?v=KSPYzLE0uy8.

El premi María de Maeztu que he guanyat, més que per un bon TFG, és per la reproductibilitat del TFG. La reproductibilitat de la investigació científica és molt important. Per tal que una peça de coneixement sigui vàlida i pugui ser acceptada per la comunitat ha de ser possible verificar-la independentment. Per això estic molt orgullós d'haver pogut adherir-me a aquest principi en el meu TFG. Idealment, la reproducció d'un algoritme hauria de ser utilitzant només la descripció d'alt nivell que hi ha en l'article o tesi, sense mirar el programa de l'autor original. Fer aquesta reproducció, però, requereix de vegades mesos. Així, és molt útil per a la comunitat que, si és necessari, es pugui descarregar el programa original, i comprovar els resultats en com a molt unes hores d'executar-lo. De fet, el meu treball ha estat molt més fàcil gràcies a que he pogut obtenir el codi original de l'algoritme Iterated Width de Lipovetzky, Ramírez i Geffner. Els programes utilitzats en l'elaboració del meu TFG es poden obtenir a https://github.com/rhaps0dy/solving-mr-planning-rl, sota una llicència de programari lliure.

En el futur tinc planejat dedicar-me a recerca en IA. Aquest curs aniré a fer un màster sobre això a la universitat d'Oxford. Allà vull conèixer més a fons altres branques de la IA, sobretot l'enteniment del llenguatge natural, i el desconegut problema de control, o especificació d'objectius complexos. Així podré decidir millor qui anar a buscar com a supervisor del meu doctorat. Després cercaré feina en una universitat o empresa de recerca. No descarto començar una companyia, si veig una oportunitat de negoci interessant, però és improbable que així sigui."

Multimèdia

Multimedia

Multimedia

Categories: