Un algoritmo indica la probabilidad de éxito e incluso sugiere alternativas

Los asistentes por voz y planificadores de rutas están cada vez más desarrollados. Sin embargo, todavía queda mucho camino por recorrer en este campo de la investigación.

Cada vez está más próximo el día en que se pueda pedir al teléfono que te conduzca desde tu casa en Boston a un hotel en el norte del estado de Nueva York, con una parada para almorzar en un Applebee a las 12.30, y que el viaje no dure más de cuatro horas.

Con esos datos, el dispositivo calcula que sólo hay un 66 por ciento de probabilidad de éxito, pero retrasando media hora el almuerzo o cambiándolo a otro restaurante se puede aumentar hasta el 99 por ciento.

Este tipo de aplicación es el objetivo del grupo de Brian Williams en el Laboratorio de Ciencias de la Computación e Inteligencia Artificial del Instituto Tecnológico de Massachusetts (MIT) en Estados Unidos, aunque partiendo de la misma base han creado un software que la NASA y el Instituto Oceanográfico Woods Hole han utilizado para planificar sus misiones.

Según informa el MIT en un comunicado, los investigadores han presentado un conjunto de algoritmos en la reunión anual de la Asociación para el Avance de la Inteligencia Artificial (AAAI) de este mes, que representa pasos significativos hacia lo que Williams describe como "un Siri mejorado", el asistente por voz de Apple. Sin embargo, podría aplicarse a cualquier tarea de planificación, desde programar vuelos a rutas de autobús.

Junto a Williams, los estudiantes Peng Yu y Cheng Fang han desarrollado un software que permite a un planificador especificar restricciones -por ejemplo, la llegada de autobuses de una ruta determinada a su destino con intervalos de 10 minutos-, y la fiabilidad de los umbrales, tales como que los autobuses deben llegar a tiempo en el 90 por ciento de las ocasiones.

Después, mediante modelos probabilísticos -que revelan datos como el tiempo medio que tarda un autobús en recorrer un kilómetro-, el sistema determina si existe una solución. Por ejemplo, escalonar la salida de los autobuses seis minutos a ciertas horas del día, y doce las demás.

Mitigar las limitaciones

Sin embargo, si no existe una solución, el software no se rinde. En su lugar, sugiere formas en que el planificador podría mitigar las limitaciones iniciales del problema. Así, en el caso de los autobuses, si el planificador rechaza el cambio a intervalos de doce minutos, se podría contemplar la posibilidad de añadir un autobús a la ruta.

Uno de los aspectos de este software que lo distingue de sistemas de planificación anteriores es que evalúa el riesgo. "Siempre hay que trabajar con probabilidades, porque añaden complejidad a los cálculos", señala Fang. De ahí que se cuestionen el margen de riesgo para cada misión y lo utilicen como un recurso.

Volviendo al mismo ejemplo, el tiempo que se necesita para recorrer cualquier distancia en una ruta de autobús, se puede representar en una distribución de probabilidad, una estadística con curvas gaussianas que enfrente el trazado de tiempo a la probabilidad, asignando a cada variable aleatoria la probabilidad de que el suceso ocurra.

Hacer un seguimiento de todas esas probabilidades generaría demasiados datos. Pero si el sistema sabe de antemano que el planificador tolera un cierto margen de fracaso, se pueden asignar esos fracasos a los resultados de probabilidad más bajos en la distribución, reduciendo los datos obtenidos. Eso hace que sean mucho más fáciles de tratar matemáticamente.

La teoría de grafos

En AAAI, Williams y otro de sus estudiantes, Andrew Wang, han presentado otro estudio sobre cómo evaluar esas tareas de manera eficiente, a fin de encontrar soluciones rápidas a problemas de planificación sencillos. Pero el que desarrolla con Yu y Fang se centra en identificar las limitaciones que impiden la solución del problema.

Ambos procedimientos se basan en la teoría de grafos. En este contexto, un grafo es una representación de datos que consta de nodos, representados generalmente como círculos, y los bordes, mostrados como segmentos de línea que conectan los nodos. Cualquier problema de programación se puede representar como un grafo. Los nodos representan eventos, y los bordes indican la secuencia en la que deben ocurrir. Cada borde tiene también un peso asociado, lo que indica el costo de progresar de un evento a otro -el tiempo que toma un autobús para viajar entre las paradas, por ejemplo.

El algoritmo de los investigadores del MIT representa primero un problema en forma de grafo, y luego comienza a agregar bordes con las restricciones impuestas por el planificador. Si el problema es sencillo, el peso de los bordes que representan limitaciones será mayor que el de los costos de transiciones entre eventos.

Los sistemas existentes pueden dirigirse rápidamente a círculos en el gráfico donde el peso esté desequilibrado. Sin embargo, el nuevo algoritmo calcula en ese caso el camino de menor costo para reequilibrarlos, presentando el planificador como una modificación de las limitaciones iniciales del problema.

Jiaying Shen, científico de Nuance Communications, donde desarrollaron la tecnología de reconocimiento de voz utilizada por Siri, destaca la importancia de esta investigación al añadir la incertidumbre al azar, generando problemas para modelar más complicados e impredecibles y, por tanto, más realistas. "Si se expone lo que hay que tener en cuenta en la etapa de planificación, aumenta la tasa de éxito en la ejecución del plan", añade Shen.