Recursividad Indirecta

… o quizás una vuelta de tuerca al argumento de la simulación.

Anuncios

C.A.R. Hoare cumple hoy 74 años

“Hay dos formas de realizar un diseño software: hacer que sea tan simple que sea obvio que no tiene deficiencias, o hacer que sea tan complicado que no tenga deficiencias obvias. El primer método es más difícil.“

C.A.R. Hoare (1934-), informático británico

Las “viejos cocodrilos” de la programación siguen cumpliendo años, y hoy le toca a Sir Charles Anthony Richard “Tony” Hoare, que cumple 74. A Hoare le debemos una de las joyas de la algorítmica, el algoritmo de ordenación quicksort, y el lenguaje formal CSP, en el que se basa Occam (lenguaje que en su día me dio tardes de gloria programando transputers). También desarrolló una lógica formal para verificación pre-post de algoritmos (qué tiempos aquellos, buscando invariantes en los bucles; luego vendría Dijkstra con su semántica de transformación de predicados y sus precondiciones más débiles). En 1980 recibió el premio Turing por “sus contribuciones fundamentales a la definición y diseño de los lenguajes de programación”. La frase del encabezado está tomada precisamente de su discurso de aceptación.

Hoare estuvo en 2005 en España, en el Primer Congreso Español de Informática, y dio una charla plenaria sobre software verificable. Se mostró en todo momento como una persona muy afable, y con toda amabilidad y la mayor de las sonrisas atendía a todo el que luego le buscaba para comentarle algo, o simplemente presentarle sus respetos. Sin duda, Sir C.A.R. Hoare es todo un caballero.

Donald Knuth cumple hoy 70 años

“Ciencia es aquello que conocemos lo suficientemente bien para explicárselo a un computador. El resto de lo que hacemos es Arte.“

Donald Ervin Knuth (1938-), informático estadounidense

Hoy cumple 70 años Donald E. Knuth, uno de los padres fundadores de la algorítmica. A él debemos The Art of Computer Programming y el TeX, gracias al cual toda la comunidad científica no está a estas horas en las manos de Microsoft Word. Además de científico genial, Knuth siempre ha tenido un humor y un punto geek fantásticos. Por ejemplo, la versión i-ésima de TeX se identifica con la expansión en i dígitos de π, al igual que hace con METAPOST y el número e. También tiene la ocurrencia de emitir cheques por 2.56$ (1 dólar hexadecimal) a favor de quien encuentre un error en algún libro suyo (estos cheques son un trofeo cotizadísimo).

Su padre tenía una imprenta, y por ahí quizás venga el desarrollo de TeX, y su obsesión por la tipografía, que le ha hecho afirmar que no puede ir a comer a un restaurante, ya que no deja de mirar las fuentes tipográficas de la carta del menú. De todas formas, además de con la cita de más arriba, me quedo con otra suya sobre las matemáticas:

“¡Una fórmula matemática no debería ser nunca propiedad de nadie! Las matemáticas pertenecen a Dios.”

y con otra bastante irónica sobre la verificación formal:

“Ten cuidado con este código. He demostrado su corrección, pero no lo he llegado a probar.”

, Profesor Knuth.

La vuelta al mundo en 10 minutos (o en 156 días)

El Degree Confluence Project es una curiosa iniciativa colaborativa consistente en visitar y tomar fotografías de todos los puntos del globo terráqueo con latitud y longitud enteras, esto es, de los puntos en los que se cruzan paralelos y meridianos correspondientes a un número entero (i.e., sin decimales) de grados de latitud o longitud respectivamente. Dado que la longitud puede tomar 360 valores enteros, y que la latitud puede tomar 181 (de 1º a 90º N o S, más el Ecuador), pero hay que descontar los polos en los que no hay variación de longitud, tenemos 360 x 179 + 2 = 64,442 confluencias. De éstas, una gran parte (más de 39,000) estarán en mitad de los mares u océanos, o se apiñarán cerca de los polos. Las restantes se hallan en tierra firme, o cerca de la costa, y definen una cuadrícula uniformemente distribuida por todos los continentes. Pueden considerarse en cierta medida como una muestra sistemática de lo que hay sobre la faz de la Tierra (de la tierra firme, claro).

Una vez identificados estos puntos, cabría considerar la tarea de dar una auténtica vuelta al mundo. No sólo circumnavegar el planeta, sino visitar cada pedacito de tierra firme del mismo, asumiendo estas confluencias como representativas de un área de ±0.5º de latitud/longitud (0.5º representa menos de 60 km en cualquiera de las cuatro direcciones principales en el Ecuador; en otros puntos la distancia E/W es todavía menor debido a la convergencia de los meridianos), lo que no parece descabellado. Tenemos entonces una instancia de nuestro bien conocido problema del viajante de comercio (TSP) con 16,189 “ciudades”. El vídeo inferior muestra un camino óptimo para recorrer todos estos puntos y volver al punto de partida. La longitud total del camino es de 1,628,716 km, lo que supone unos 156 días sin parar en una avioneta como la Mooney Acclaim.

La resolución del problema se ha realizado mediante Concorde, un paquete de optimización para el TSP que incorpora técnicas exactas tales como ramificación y corte, y heurísticas como el algoritmo de Lin-Kernighan. Es fácil ver que la solución óptima a una instancia del TSP sobre un plano no tendrá aristas que se crucen. La eliminación de estos cruces es precisamente una de las heurísticas más simples y efectivas para mejorar una solución obtenida mediante algún otro método. De hecho, es muy común incorporar una heurística de este tipo dentro de alguna otra metaheurística, e.g, un algoritmo genético. Estamos entonces hablando de algoritmos meméticos, a los que les dedicaremos algo más de tiempo más adelante.

La combinatoria de los brotes epidémicos

Uno de los aspectos claves para lidiar con brotes epidémicos es la identificación de los mismos (luego viene algo mucho más complejo que es analizar su dinámica para localizar el origen/causa, y predecir su evolución, pero dejemos eso para otra ocasión). Esta identificación no es algo trivial. Indudablemente, si se detectan cientos de casos de una enfermedad muy rara en un área muy reducida se está ante un fenómeno epidémico, pero el objetivo es realizar la identificación en una etapa más temprana, antes de que la enfermedad se disemine sin control. La clave está entonces en realizar una evaluación de cuándo un cierto número de casos de una enfermedad puede estar siendo motivada por un brote epidémico. Esto lógicamente dependerá de diferentes factores, como el número de casos, la prevalencia de la enfermedad, o el tamaño de la comunidad en la que se han detectado los casos. La combinatoria nos puede echar una mano en este caso. Concretamente, el clásico modelo de bolas y cajas puede ser muy útil. Veamos cómo.

Supongamos que tenemos un número N de cajas, sobre las que distribuimos uniformemente al azar B bolas. Cada una de estas cajas representará lógicamente un grupo o comunidad, y cada bola será un caso de la enfermedad en cuestión. La pregunta que queremos hacernos es si el hecho de que hayan caído m bolas en una cierta caja representa un evento estadísticamente improbable y por lo tanto existe una probabilidad no desdeñable de que haya una causa para el mismo más allá del azar. ¿Cuál es la probabilidad de una cierta configuración de bolas en las cajas? Dicha probabilidad viene determinada por la bien conocida distribución multinomial:

donde p_i es la probabilidad del evento i, x_i es el número total de veces que se produce dicho evento, y x=x₁+…+x_k. En nuestro caso suponemos N eventos distintos (elegir una caja concreta), p_i=1/N (todas las cajas tienen la misma probabilidad), y si b_i es el número de bolas en la caja i, b₁+…b_N=B. Entonces,

La probabilidad de que el número de bolas en la caja que más tiene sea menor o igual a m es

Finalmente, la probabilidad de que haya m o más bolas en la caja que más tiene es 1-P(N,m-1,B). El problema que tiene calcular de manera precisa esta expresión es la explosión combinatoria para valores grandes de N y B, motivo por el cual se emplean aproximaciones (por ejemplo basadas en métodos de Monte Carlo). Al menos esto era hasta ahora, ya que Warren J. Ewens, y Herbert S. Wilf, de la Universidad de Pennsylvania, han encontrado una forma eficiente de realizar el cómputo, según describen en un artículo titulado

• Computing the distribution of the maximum in balls-and-boxes problems with application to clusters of disease cases

publicado en los Proceedings of the National Academy of Sciences. El método de Ewens y Wilf se basa en el hecho de que P(N,m,B) es B!/N^B veces el coeficiente de x^B en la serie e_m(x)^N, donde e_m(x) es la expansión polinómica de la función e^x truncada en el término (m+1)-ésimo, y que estos coeficientes se pueden calcular eficientemente mediante una relación recurrente. De hecho su algoritmo emplea una cantidad de memoria O(m), y tiene un coste computacional O(mN).

Ewens y Wolf ilustran el método con dos ejemplos. En el primero se analiza la aparición de 8 casos de leucemia infantil en un pueblo de 20,000 personas. Durante el periodo en el que surgieron estos casos el número medio en todo el país (EE.UU.) era de 1.6 por 20,000 habitantes, y la población total era por aquel entonces de 180 millones. El análisis se realiza entonces con N=9,000 (180,000,000/20,000), B=14,400 (1.6·9,000), y m=8, resultando en una probabilidad del 90%, lo que no apoya la hipótesis de una causa común para estos casos. En el segundo ejemplo se analizan 12 casos de leucemia linfocítica aguda en un pueblo de 24,000 personas, cuando el número esperado era de 1, y la población total del país es de 288 millones. Tenemos entonces N=12,000, B=12,000, y m=12. En este caso la probabilidad de que todo sea debido al azar es virtualmente cero (ya para m=8 es sólo del 0.6%), por lo que la hipótesis de la causa común no puede ser obviada.

Por supuesto, en ambos casos se trata sólo de una estimación estadística, pero puede ser de gran utilidad para activar los sistemas de alerta, máxime teniendo en cuenta que el cómputo puede realizarse en sólo unos segundos en un ordenador portátil.

Exploración robótica del Cosmos: nuevos desafíos, nuevos algoritmos

El tema de la exploración humana del espacio es apasionante y controvertido. En muchas situaciones se tiende a hacer una analogía con los antiguos exploradores, que se adentraron en desconocidos territorios polares, desérticos, o selváticos, y aunque la imagen es evocadora, parece irreal. Básicamente, mucho antes de que se tengan los medios técnicos para una detallada exploración humana de, pongamos por caso, Marte, será factible realizarla mediante sondas robóticas. La lógica indica que este paso previo es mucho más prudente, con independencia de lo que luego se pudiera decidir sobre eventuales misiones tripuladas.

Credit: NASA

En relación con esta exploración robótica surgen diferentes cuestiones de gran interés. Por un lado está la planificación a gran escala de esta exploración. Jordi nos reseña en su bitácora un artículo en el que se aborda este tema. Es sin duda un asunto interesantísimo, y que se presta a diferentes análisis. No obstante, quería comentar algo en relación a otro aspecto de naturaleza más local, pero no por ello de menor importancia: el control de las sondas robóticas. Está claro que el límite físico de la velocidad de la luz impide que las comunicaciones se puedan desarrollar en tiempo real, y por lo tanto no es planteable que los robots sean meros instrumentos teledirigidos. Éste no es sólo el caso de una hipotética exploración de planetas extrasolares, sino que se trata de una consideración crucial para la exploración de Marte por ejemplo. Consideremos que la distancia que nos separa de Marte oscila entre unos 55 millones y unos 400 millones de kilómetros. Esto supone que los tiempos de comunicación bidireccional (mensaje y respuesta) oscilan entre poco más de seis minutos y casi 45 minutos. En general, esto significa que la sonda ha de tener un cierto grado de autonomía que le permita valerse por sí misma, e incluso planificar los detalles de la exploración. Para esto será necesario emplear técnicas de inteligencia artificial (IA), entendidas en un sentido amplio:

• Los métodos clásicos de IA tales como los sistemas expertos, el razonamiento basado en casos, o los métodos bayesianos pueden ser útiles a la hora de planificar a alto nivel los objetivos a largo plazo, construir modelos del entorno, o realizar toma de decisiones estratégicas.
• Los métodos modernos englobados dentro de la inteligencia computacional, tales como la computación evolutiva o los sistemas neurodifusos, resultarán imprescindibles a la hora de resolver problemas de medio alcance que se planteen en la consecución de los objetivos estratégicos, tales como planificación de tareas, interpretación visual, u optimización de maniobras.
• Finalmente, el nivel más bajo deberá ser puramente reactivo: reglas de actuación ante patrones de entrada sensorial, que permitan una respuesta rápida ante situaciones tales como obstáculos imprevistos, terrenos impracticables, etc. Por supuesto, este nivel reactivo básico puede estar sujeto a continuo refinamiento mediante técnicas de aprendizaje, tales como los algoritmos evolutivos.

Evidentemente, en el caso de Marte es factible cierto tipo de control remoto, no en tiempo real, pero si al menos para determinar la planificación a medio y largo plazo de la exploración. Sigue existiendo entonces la problemática del control a muy corto plazo, y muy en particular la del cómputo de las trayectorias. Para ello, la NASA está recurriendo a una solución mucho más conservadora que las descritas anteriormente, cosa que tampoco es excesivamente criticable, dado que en el fondo la proximidad de Marte facilita las cosas, esto es, no es necesaria una total independencia de la sonda (salvo en circunstancias puntuales y transitorias, como un ocultamiento de Marte por el Sol, aunque en ese caso, se opta por dar unas “vacaciones” a las sondas).

Courtesy NASA/JPL-Caltech

El mecanismo que se emplea en la Spirit y en la Opportunity en lo que a planificación de trayectorias se refiere es una variante del clásico algoritmo A*. A grandes rasgos, el A* es un algoritmo completo de búsqueda para la exploración de grafos. En este caso, el grafo representa el terreno sobre el que la sonda se ha de desplazar, discretizado como si se tratase de las casillas de un tablero de ajedrez. El desplazamiento de una casilla a otra tendrá un coste que dependerá de las características del terreno. El algoritmo explora sistemáticamente todos los caminos que parten de la posición inicial, construyendo una lista de caminos abiertos, y seleccionando para su extensión a aquellos que resultan más prometedores de acuerdo con una función de coste heurística. Para evitar ciclos, se mantiene también una lista de las casillas visitadas (la gestión de esta lista tiene algunos matices, pero podemos obviarlos de momento). Si la función heurística es optimista (es decir, nos proporciona siempre una cota inferior del coste final de un camino incompleto), tenemos garantizado el encontrar finalmente la solución óptima.

El problema del A* es que obviamente parte del conocimiento del terreno, cosa que no es totalmente realista en el caso de las sondas: a medida que éstas avanzan obtienen nuevas imágenes que revelan nuevos obstáculos, o alteran las características que se suponía tenía el terreno. Esto conlleva que el grafo subyacente debe ser modificado, y el camino óptimo recomputado. Afortunadamente, hay formas eficientes de realizar esto, ya que por definición, las modificaciones que se realizan afectan fundamentalmente a la vecindad inmediata del la sonda. El algoritmo que se emplea a tal efecto es el D* (la D es de “dinámico”), y se basa en una astuta gestión de la lista de caminos abiertos. Para más detalles, puede consultarse el trabajo titulado:

• Optimal and Efficient Path Planning for Partially-Known Environments

realizado por Anthony Stentz, de la Carnegie Mellon University, y publicado en la 1994 IEEE International Conference on Robotics and Automation. Con este algoritmo y gracias a las últimas mejoras en los sistemas de análisis visual de la sondas, será posible que alcancen un nivel de autonomía muchísimo mayor que el que disfrutaban hasta ahora. Poca cosa si se piensa en lo que será preciso en misiones de más calado en regiones mucho más lejanas del Universo, pero un paso necesario en cualquier caso.