Los algoritmos de planificación se usan ampliamente en logística y control. Pueden ayudar a programar vuelos y rutas de autobuses, guiar robots autónomos y determinar políticas de control para la red eléctrica, entre otras cosas.
En los últimos años, los algoritmos de planificación han comenzado a tener en cuenta la incertidumbre: variaciones en el tiempo de viaje, comunicación errática entre robots autónomos, datos de sensores imperfectos y similares. Eso hace que la escala del problema de planificación crezca exponencialmente, pero los investigadores hanencontró formas inteligentes de resolverlo eficientemente.
Ahora, los investigadores del MIT y la Universidad Nacional de Australia ANU han hecho que el problema sea aún más complejo, al desarrollar un algoritmo de planificación que también genera planes de contingencia, en caso de que el plan inicial demuestre ser demasiado riesgoso. También identifica las condiciones, digamos, lecturas de sensores o retrasos incurridos, eso debería activar un cambio a un plan de contingencia particular.
A pesar de la mano de obra adicional impuesta por la generación de planes de contingencia, el algoritmo aún proporciona garantías matemáticas de que el riesgo de falla de sus planes cae por debajo de algún umbral, que el usuario establece.
"El problema con la planificación de contingencias es que hay tantas cosas que pueden salir mal, si generas planes para todas las posibles contingencias, te volverías loco", dice Brian Williams, profesor de aeronáutica y astronáutica cuyo grupo desarrolló elnuevo sistema. "Entonces, la pregunta termina siendo, '¿Cuántas contingencias genera?'"
Pedro Santana, un estudiante graduado en aeronáutica y astronáutica, es el primer autor en un documento que describe el sistema, que presentó en la reunión anual de la Asociación para el Avance de la Inteligencia Artificial el fin de semana pasado. Se le unieron Williams y Sylvie Thiébaux,profesor de ciencias de la computación en la Universidad Nacional de Australia e investigador del programa de investigación de la National Information Communications Technology Australia NICTA de Australia, que tiene una asociación con el MIT.
poda probabilística
Como explica Williams, el rango de posibles decisiones que enfrenta un planificador puede representarse como una estructura de datos llamada gráfico. Un gráfico consta de nodos, que generalmente se representan como círculos y bordes, que se representan como segmentos de línea que conectan elnodos. Los diagramas de red y los diagramas de flujo son ejemplos familiares de un gráfico.
En un sistema de planificación, cada nodo del gráfico representa un punto de decisión, como "¿Debería tomar el autobús o el metro?". Una ruta a través del gráfico se puede evaluar de acuerdo con las recompensas que ofrece: usted llega a sudestino seguro, y las penalizaciones que impone, llegarás cinco minutos tarde. El plan óptimo es el que maximiza la recompensa.
Tener en cuenta las probabilidades hace que ese tipo de cálculo de recompensa sea mucho más complejo: el viaje promedio en autobús puede ser de 15 minutos, pero hay alguna posibilidad de que sea 35; el viaje promedio en metro puede ser de 18 minutos, pero casi nunca es más de 24En ese contexto, incluso para una tarea de planificación relativamente simple, los planes de contingencia de escrutinio pueden ser prohibitivamente largos.
Para hacer que el problema sea manejable, los investigadores del MIT y ANU tomaron prestada una técnica de un trabajo anterior del grupo de Williams. Antes de que el planificador comience a construir el gráfico, le pide al usuario que establezca umbrales de riesgo. Un investigador que intenta desarrollar una información-El plan de recolección para un robot submarino multimillonario, por ejemplo, podría estar satisfecho con una probabilidad del 90 por ciento de que el robot tome todas las lecturas del sensor que se supone que debe hacer, pero podría querer una probabilidad del 99,9 por ciento de que el robot no colisionecon una pared de roca a alta velocidad.
El algoritmo de los investigadores trata estos umbrales como un "presupuesto de riesgo" que gasta mientras explora las rutas a través del gráfico. Si el planificador determina que una rama determinada del gráfico excederá el presupuesto, lo separa.
Mantenerse optimista
Sin embargo, esa determinación tiene que ser rápida. Por lo tanto, los investigadores usan algunas reglas simples, o, en lenguaje informático, heurística, para evaluar las ramas. Cada ruta a través de una rama dada, por ejemplo, podría incluir un automóvil diferenteruta entre dos puntos, cada uno con su propia distribución de probabilidad de posibles tiempos de viaje, pero si atraviesa una línea recta entre los puntos, a la velocidad máxima permitida, aún incurrirá en retrasos intolerables, no tiene sentido evaluar las probabilidades para cada ruta.puede ser eliminado
Mientras las heurísticas sean optimistas, posiblemente subestimando el riesgo pero nunca sobreestimándolo, el planificador puede cortar ramas sin comprometer la calidad de los planes finales. A veces, esas heurísticas son específicas de la aplicación, como la que evalúa rutas geométricamentePero a veces no lo son
Por ejemplo, una de las razones por las que las distribuciones de probabilidad agregan tanta complejidad a los cálculos de planificación es que no son lineales: sus gráficos toman formas que son más complicadas que las líneas simples. En un documento presentado en la Conferencia Internacional sobre AutomatizaciónPlanificación y programación en junio, Santana, de nuevo primer autor, Williams y sus colegas del MIT, la Universidad de São Paulo en Brasil, y Caltech describen una forma de producir aproximaciones lineales de distribuciones de probabilidad con las que es mucho más fácil trabajar matemáticamente.
Esas aproximaciones son optimistas: nunca sobreestiman el riesgo. Pero una computadora puede evaluarlos miles de veces más rápido que una distribución no lineal. Dichas heurísticas ofrecen la esperanza de que el sistema de planificación de los investigadores pueda actualizar los planes sobre la marcha, a la luz de nuevosinformación, así como generar planes de contingencia por adelantado.
Fuente de la historia :
Materiales proporcionado por Instituto de Tecnología de Massachusetts . Original escrito por Larry Hardesty. Nota: El contenido puede ser editado por estilo y longitud.
Cite esta página :