Recerca de la vida quotidiana: Lògica i Futbol.

El grup de recerca de Lògica i Programació (LOGPROG) del Departament d'LSI de la UPC investiga per millorar el nostre dia a dia. Científics com en Roberto Nieuwenhuis, na Mª Luis Bonet, l'Albert Rubio, en Javier Larrosa i els altres membres del seu grup de recerca combinen aquest dia a dia amb lògica i programació.

El grup LOGPROG s'enfronta als típics "problemes difícils" pels que no hi ha una solució estàndard algorítmica. Problemes NP complets. Molts problemes de la vida quotidiana de seguida es converteixen en altament complexos. En particular, els que tenen a veure amb la planificació i gestió de recursos compartits: construcció d'horaris, rutes de transports, logística...etc. El grup LOGPROG ha desenvolupat els fonaments teòrics per poder aplicar la lògica en àmbits on tradicionalment les solucions eren numèriques o procedien d'altres disciplines com la Investigació Operativa. Ha mostrat el camí de la convergència entre la Lògica, la Investigació Operativa i la Satisfacció de Restriccions. Aquesta darrera és l'àrea que lidera Javier Larrosa en aquest grup.

En Roberto és integrant del col·lectiu humà i com a tal participa d'alegries, aficions esportives i problemes complexos quotidians. Com a científic cercador de respostes investiga com aconseguir veure un bon partit de futbol a la televió cada setmana, o com donar resposta al problema social del col·lapse als hospitals catalans. Aparentment, sembla difícil relacionar el futbol amb la planificació dels hospitals, o fins i tot amb els horaris o el tall de la roba d'alta costura; però tots aquests conceptes formen part de la mateix classe de problemes NP complexos. Un simple algoritme de cerca no és suficient per a poder donar resposta a com distribuir la lliga, planificar els quiròfans o com fer els interminables horaris rotatius d'algunes empreses; o simplement dóna resultats que després no són pas tan bons com caldria.

La Lliga Espanyola de Futbol, per exemple, decideix la distribució anual dels partits mitjançant un sorteig més o menys restringit. A priori, aquest mètode ens podria semblar un mètode força just i apersonal, però un segon cop d'ull ens alerta de diverses problemàtiques. En efecte, aquesta operació distribueix els partits de forma no homogènia segons la seva importància. El resultat es que hi haurà setmanes en què els espectadors gaudiran de sobredosi de partits rellevants i setmanes en què el futbol quedarà pràcticament oblidat. D'altra banda, no es prenen en consideració factors de seguretat. Per exemple, que un partit d'alt risc sigui jugat en horari de tarda i no pas de vespre. A més el mètode fa que als aparallaments entre equips es generi l'anomenat "efecte seqüència" : hi ha equips que sempre tenen com adversari qui va jugar el partit previ contra el Barça o el Madrid. A posteriori, veiem que la justícia desitjada ha esdevingut una fal·làcia.

Amb una matriu tres per tres (dos dimensions pels equips i la tercera per la informació de la jornada) que conté desenes de milers de restriccions de tot tipus, lògica i un bon software. Així és com estructuren l'any esportiu els encarregats de la Lliga Holandesa des de l'any 2004, gràcies als mètodes de LOGPROG. En Roberto Nieuwenhuis, holandès de naixement i afeccionat al futbol està content de veure com els directius del seu país confien en la seva operativitat. Tan mateix, altres membres de l'equip de recerca, més aficionats al bàsquet com l'Albert Rubio, poden somriure quan recorden que ja a l'any 1992, any de les Olimpíades, la UPC planificava els partits de l'ACB.

No només el món esportiu es beneficia del talent d'aquests recercadors. L'Hospital St. Joan de Déu els va demanar ajuda en la gestió de les intervencions en els seus quiròfans. Intel (USA) i Microsoft també treballen i han col·laborat amb el grup LOGPROG en projectes de verificació de chips o de software. Els mètodes de LOGPROG han estat guanyadors en les 4 categories de la competició SAT Módulo Teories 2005 i ara preparen la competició SAT que es realitzarà al maig del 2008. Ademés aquest grup també compta amb persones com na MªLLuïsa Bonet, que investiga l'aplicació d'aquest tipus de mètodes relacionats en Bioinformàtica (reconstrucció d'arbres genealògics i genètics) i lingüística (classificació retroactiva de les llengües) o en Javier Larrosa que optimitza els recursos de fàbriques metal·lúrgiques. El grup ha desenvolupat un important "know how" per saber traduir a les expressions de lògica les restriccions i especificacions que expressen les persones amb qui col·laboren en els projectes amb empresa.

Actualment, en Roberto Nieuwenhuis gaudeix d'una distinció I3. Es tracta d'un finançament del Ministeri d'Educació i Ciència de Madrid per a alliberar temps de docència i dedicar-lo només a investigar. Durant aquest tres anys en Roberto vol dedicar-se intensament a la solució de problemes fonamentals i pràctics i a la millora i el refinament dels mètodes actuals. Molts d'aquests problemes poden traduir-se en problemes SAT módulo Teories. A més hi ha una reconsideració de l'actual forma de col·laborar amb empreses que té el grup. Fins ara, les empreses plantejaven la seva problemàtica al grup LOGPROG i aquests traduïen el problema per a poder fer servir el seu software pertinent i venien la resposta. A partir d'ara, es planteja la possibilitat de no només vendre les solucions, si no també poder posar a la venda software més específic, i fins i tot acabar aquesta etapa amb alguna forma empresarial. Una nova empresa que portaria el nom de Barcelogic. Esperem que així sigui i que Barcelogic faci més fàcil tots quests problemes més complexos que colpegen el dia a dia de moltes persones.

De moment, si volem tornar a veure a en Roberto Nieuwenhuis o sentir a parlar més sobre aquests temes ho podem fer a:

• El 23è Simposium de la Lògica a la Ciència Computacional IEEE (LICS 2008).
  
• La 14ta Conferència en Constraint Programming (CP 2008)
• La 19a Conferència International en Rewriting Techniques i les seves Applications (RTA 2007)
• El 6è Taller International en Satisfiability Modulo Theories (SMT 2008)
  
  

ilapuente@lsi.upc.edu

(Tornar al butlletí)