En una de las escenas más memorables de la exitosa película Minority Report de 2002, Tom Cruise se ve obligado a esconderse de un enjambre de robots con forma de araña que recorre un complejo de apartamentos imponente. Mientras que la mayoría de los espectadores probablemente están paralizados por los pequeños y ágiles reemplazos de sabuesos, un ingeniero informático podría maravillarse con su elegante sistema de control.
En un edificio de varias plantas de altura con numerosas habitaciones, cientos de obstáculos y miles de lugares para inspeccionar, las varias docenas de robots se mueven como una unidad cohesiva. Se extienden en un patrón de búsqueda para verificar minuciosamente todo el edificio y al mismo tiempo dividir las tareas parapara no perder el tiempo duplicando sus propios caminos o revisando lugares que otros robots ya han visitado.
Tal cohesión sería difícil de lograr para los controladores humanos, y mucho menos para que un controlador artificial calcule en tiempo real.
"Si un problema de control tiene tres o cuatro robots que viven en un mundo con solo un puñado de habitaciones, y si la tarea de colaboración se especifica mediante reglas lógicas simples, existen herramientas de última generación que pueden calcular unsolución óptima que satisface la tarea en un período de tiempo razonable ", dijo Michael M. Zavlanos, Mary Milus Yoh y Harold L. Yoh, Jr. Profesor Asociado de Ingeniería Mecánica y Ciencia de Materiales en la Universidad de Duke.
"Y si no te importa la mejor solución posible, puedes resolver algunas habitaciones más y tareas más complejas en cuestión de minutos, pero solo una docena de robots", dijo Zavlanos.eso, y los algoritmos actuales no pueden superar el enorme volumen de posibilidades para encontrar una solución "
En un nuevo documento publicado en línea el 29 de abril en el Revista Internacional de Investigación en Robótica , Zavlanos y su reciente estudiante de doctorado, Yiannis Kantaros, quien ahora es investigador postdoctoral en la Universidad de Pensilvania, proponen un nuevo enfoque para este desafío llamado STyLuS *, para la Síntesis de lógica temporal óptima a gran escala, que puede resolver problemasmasivamente más grande de lo que los algoritmos actuales pueden manejar, con cientos de robots, decenas de miles de habitaciones y tareas altamente complejas, en una pequeña fracción del tiempo.
Para comprender la base del nuevo enfoque, primero se debe entender la lógica temporal lineal, que no es tan aterradora como parece. Suponga que desea programar un puñado de robots para recolectar correo de un vecindario y entregarlo en la publicaciónOffice todos los días. La lógica temporal lineal es una forma de escribir los comandos necesarios para completar esta tarea.
Por ejemplo, estos comandos pueden incluir visitar cada casa en orden secuencial, regresar a la oficina de correos y luego esperar a que alguien recupere el correo recolectado antes de salir nuevamente. Si bien esto puede ser fácil de decir en inglés, es másdifícil de expresar matemáticamente: la lógica temporal lineal puede hacerlo mediante el uso de sus propios símbolos que, aunque parezcan klingon para el observador común, son extremadamente útiles para expresar problemas de control complejos.
"El término lineal se usa porque los puntos en el tiempo tienen un sucesor único basado en un modelo lineal discreto de tiempo, y temporal se refiere al uso de operadores como hasta, luego, eventualmente y siempre", dijo Kantaros. "Usar este método matemáticoformalismo, podemos construir comandos complejos como 'visitar todas las casas excepto la casa dos', 'visitar las casas tres y cuatro en orden secuencial' y 'esperar hasta que haya estado en la casa uno antes de ir a la casa cinco' ".
Para encontrar controladores de robot que satisfagan tareas tan complejas, la ubicación de cada robot se asigna a un punto de datos discreto llamado "nodo". Luego, desde cada nodo, existen varios otros nodos que son un posible próximo paso para el robot.
Un controlador tradicional busca a través de cada uno de estos nodos y las posibles rutas a tomar entre ellos antes de encontrar la mejor manera de navegar. Pero a medida que aumenta el número de robots y ubicaciones para visitar, y a medida que las reglas lógicasseguir se vuelve más sofisticado, el espacio de solución se vuelve increíblemente grande en muy poco tiempo
Un problema simple con cinco robots que viven en un mundo con diez casas podría contener millones de nodos, capturando todas las posibles ubicaciones y comportamientos de los robots para lograr la tarea. Esto requiere mucha memoria para almacenar y poder de procesamiento para buscar.
Para evitar este problema, los investigadores proponen un nuevo método que, en lugar de construir estos gráficos increíblemente grandes en su totalidad, crea aproximaciones más pequeñas con una estructura de árbol. En cada paso del proceso, el algoritmo selecciona aleatoriamente un nodo deel gráfico grande, lo agrega al árbol y vuelve a cablear las rutas existentes entre los nodos en el árbol para encontrar rutas más directas de principio a fin.
"Esto significa que a medida que el algoritmo progresa, este árbol que crecemos gradualmente se acerca más y más al gráfico real, que nunca construimos realmente", dijo Kantaros. "Dado que nuestro gráfico incremental es mucho más pequeño, es fácil de almacenaren la memoria. Además, dado que este gráfico es un árbol, la búsqueda de gráficos, que de lo contrario tiene una complejidad exponencial, se vuelve muy fácil porque ahora solo necesitamos rastrear la secuencia de los nodos principales hasta la raíz para encontrar la ruta deseada ".
Durante mucho tiempo se había aceptado que los árboles en crecimiento no podían usarse para buscar el espacio de posibles soluciones para este tipo de problemas de control de robots. Pero en el documento, Zavlanos y Kantaros demuestran que pueden hacerlo funcionar implementando dos trucos ingeniosos.Primero, el algoritmo elige el siguiente nodo para agregar en función de la información sobre la tarea en cuestión, lo que permite al árbol aproximar rápidamente una buena solución al problema. Segundo, aunque el algoritmo crece árboles, aún puede detectar ciclos en el originalespacio gráfico que captura soluciones para tales tareas de lógica temporal.
Los investigadores muestran que este método siempre encontrará una respuesta si la hay, y siempre encontrará la mejor posible. También muestran que este método puede llegar a esa respuesta exponencialmente rápido. Trabajar con un problema de 10 robotsbuscar a través de un espacio de cuadrícula de 50 por 50 - 250 casas para recoger el correo - los algoritmos actuales de última generación tardan 30 minutos en encontrar una solución óptima.
STyLuS * lo hace en unos 20 segundos.
"Incluso hemos resuelto problemas con 200 robots que viven en un mundo de cuadrícula de 100 por 100, que es demasiado grande para los algoritmos actuales", dijo Zavlanos. "Si bien actualmente no hay ningún sistema que use 200robots para hacer algo como entregar paquetes, podría haberlos en el futuro. Y necesitarían un marco de control como STyLuS * para poder entregarlos mientras satisfacen reglas complejas basadas en la lógica ".
Fuente de la historia :
Materiales proporcionado por Universidad de Duke . Original escrito por Ken Kingery. Nota: El contenido puede ser editado por estilo y longitud.
Referencia del diario :
Cita esta página :