Estudiantes-investigadores en MIT desarrollaron un planificador de viajes

Las agencias de viajes ayudan a proporcionar logística integral (como transporte, alojamiento, comidas y hospedaje) para personas de negocios, turistas y cualquier otra persona. Para quienes buscan organizar sus propios servicios, los modelos de lenguaje extenso (LLM) parecen ser una herramienta sólida para esta tarea debido a su capacidad de interactuar iterativamente con lenguaje natural, proporcionar razonamiento lógico, recopilar información y recurrir a otras herramientas para ayudar con la tarea en cuestión. Sin embargo, estudios recientes han descubierto que los LLM de vanguardia tienen dificultades con razonamientos logísticos y matemáticos complejos, así como con problemas con múltiples restricciones, como la planificación de viajes, donde se ha demostrado que proporcionan soluciones viables el 4 % o menos del tiempo, incluso con herramientas adicionales e interfaces de programación de aplicaciones (API).

Posteriormente, un equipo de investigación del MIT y del Laboratorio de IA Watson del MIT-IBM replanteó el problema para ver si podían aumentar la tasa de éxito de las soluciones LLM para problemas complejos. «Creemos que muchos de estos problemas de planificación son, por naturaleza, un problema de optimización combinatoria», donde es necesario satisfacer varias restricciones de forma certificable, afirma Chuchu Fan, profesora asociada del Departamento de Aeronáutica y Astronáutica del MIT (AeroAstro) y del Laboratorio de Sistemas de Información y Decisión (LIDS). También es investigadora del Laboratorio de IA Watson del MIT-IBM. Su equipo aplica aprendizaje automático, teoría de control y métodos formales para desarrollar sistemas de control seguros y verificables para robótica, sistemas autónomos, controladores e interacciones hombre-máquina.

Teniendo en cuenta la naturaleza transferible de su trabajo para la planificación de viajes, el grupo buscó crear un marco intuitivo que pudiera actuar como un agente de viajes de IA para ayudar a desarrollar planes de viaje realistas, lógicos y completos. Para lograrlo, los investigadores combinaron LLM comunes con algoritmos y un solucionador de satisfacibilidad completa. Los solucionadores son herramientas matemáticas que verifican rigurosamente si se pueden cumplir los criterios y cómo, pero requieren una programación informática compleja para su uso. Esto los convierte en el complemento ideal de los LLM para problemas como estos, donde los usuarios necesitan ayuda para planificar de manera oportuna, sin necesidad de conocimientos de programación ni investigación sobre opciones de viaje. Además, si la restricción de un usuario no se puede cumplir, la nueva técnica puede identificar y articular dónde radica el problema y proponer medidas alternativas al usuario, quien puede entonces elegir aceptarlas, rechazarlas o modificarlas hasta que se formule un plan válido, si existe.

“Las diferentes complejidades de la planificación de viajes son algo con lo que todos tendremos que lidiar en algún momento. Existen diferentes necesidades, requisitos, limitaciones e información del mundo real que se puede recopilar”, afirma Fan. “Nuestra idea no es pedir a los LLM que propongan un plan de viaje. En cambio, un LLM actúa como traductor para traducir esta descripción del problema en lenguaje natural a un problema que un solucionador pueda abordar [y luego proporcionarlo al usuario]”, añade Fan.

Yang Zhang, del Laboratorio de IA Watson del MIT-IBM, el estudiante de posgrado de AeroAstro Yilun Hao y el estudiante de posgrado Yongchao Chen, del MIT LIDS y la Universidad de Harvard, son coautores de un artículo sobre el trabajo con Fan. Este trabajo se presentó recientemente en la Conferencia de las Naciones de las Américas de la Asociación de Lingüística Computacional.

Desglosando el solucionador

Las matemáticas tienden a ser específicas de cada dominio. Por ejemplo, en el procesamiento del lenguaje natural, los LLM realizan regresiones para predecir el siguiente token, también conocido como «palabra», en una serie para analizar o crear un documento. Esto funciona bien para generalizar diversas entradas humanas. Sin embargo, los LLM por sí solos no funcionarían para aplicaciones de verificación formal, como en la industria aeroespacial o la ciberseguridad, donde las conexiones de circuitos y las tareas de restricción deben estar completas y probadas; de lo contrario, pueden filtrarse lagunas y vulnerabilidades que causen problemas de seguridad críticos. En este caso, los solucionadores sobresalen, pero necesitan entradas con formato fijo y tienen dificultades con consultas insatisfactorias. Sin embargo, una técnica híbrida ofrece la oportunidad de desarrollar soluciones para problemas complejos, como la planificación de viajes, de forma intuitiva para el usuario común.

“El solucionador es realmente la clave aquí, porque al desarrollar estos algoritmos, sabemos exactamente cómo se resuelve el problema como un problema de optimización”, afirma Fan. Específicamente, el grupo de investigación utilizó un solucionador llamado teorías de satisfacibilidad módulo (SMT), que determina si una fórmula puede satisfacerse. “Con este solucionador en particular, no se trata solo de optimizar, sino de razonar con muchos algoritmos diferentes para comprender si el problema de planificación es posible o no. Esto es muy importante en la planificación de viajes. No es un problema de optimización matemática muy tradicional, ya que la gente se plantea todas estas limitaciones, restricciones y restricciones”, señala Fan.

Traducción en acción

El «agente de viajes» funciona en cuatro pasos que pueden repetirse según sea necesario. Los investigadores utilizaron GPT-4, Claude-3 o Mistral-Large como el LLM del método. Primero, el LLM analiza la solicitud de plan de viaje del usuario en pasos de planificación, anotando las preferencias de presupuesto, hoteles, transporte, destinos, atracciones, restaurantes y duración del viaje en días, así como cualquier otra prescripción del usuario. Estos pasos se convierten luego en código Python ejecutable (con una anotación en lenguaje natural para cada una de las restricciones), que llama a API como CitySearch, FlightSearch, etc. para recopilar datos, y al solucionador SMT para comenzar a ejecutar los pasos establecidos en el problema de satisfacción de restricciones. Si se puede encontrar una solución sólida y completa, el solucionador envía el resultado al LLM, que a su vez proporciona un itinerario coherente al usuario.

Si una o más restricciones no se pueden cumplir, el marco busca una alternativa. El solucionador genera código que identifica las restricciones conflictivas (con su anotación correspondiente) y el LLM proporciona al usuario una posible solución. El usuario puede entonces decidir cómo proceder hasta alcanzar una solución (o el número máximo de iteraciones).

Planificación generalizable y robusta

Los investigadores probaron su método utilizando los LLM mencionados anteriormente frente a otras líneas base: GPT-4 por sí solo, OpenAI o1-preview por sí solo, GPT-4 con una herramienta para recopilar información y un algoritmo de búsqueda que optimiza el coste total. Utilizando el conjunto de datos de TravelPlanner, que incluye datos de planes viables, el equipo examinó múltiples métricas de rendimiento: la frecuencia con la que un método podía ofrecer una solución, si la solución cumplía criterios de sentido común como no visitar dos ciudades en un día, la capacidad del método para cumplir una o más restricciones y una tasa de aprobación final que indicara que podía cumplir todas las restricciones. La nueva técnica logró, en general, una tasa de aprobación superior al 90 %, en comparación con el 10 % o inferior de las líneas base. El equipo también exploró la adición de una representación JSON dentro del paso de consulta, lo que facilitó aún más que el método proporcionara soluciones con tasas de aprobación del 84,4 al 98,9 %.

El equipo MIT-IBM planteó retos adicionales a su método. Analizaron la importancia de cada componente de su solución (como la eliminación de la retroalimentación humana o del solucionador) y cómo esto afectaba los ajustes del plan a consultas insatisfactorias en 10 o 20 iteraciones utilizando un nuevo conjunto de datos creado por ellos, llamado UnsatChristmas, que incluye restricciones imprevistas, y una versión modificada de TravelPlanner. En promedio, el marco del grupo MIT-IBM logró un 78,6 y un 85 % de éxito, porcentajes que se elevan al 81,6 y al 91,7 % con rondas adicionales de modificación del plan. Los investigadores analizaron su eficacia en la gestión de las nuevas restricciones imprevistas y en la parafraseo de las indicaciones de los pasos de consulta y del código de paso. En ambos casos, tuvo un excelente rendimiento, especialmente con una tasa de éxito del 86,7 % en la prueba de parafraseo.

Finalmente, los investigadores del MIT-IBM aplicaron su marco de trabajo a otros dominios con tareas como la selección de bloques, la asignación de tareas, el problema del viajante y el almacén. En este caso, el método debe seleccionar bloques numerados y coloreados y maximizar su puntuación; optimizar la asignación de tareas del robot para diferentes escenarios; planificar viajes minimizando la distancia recorrida; y completar y optimizar las tareas del robot.

«Creo que este es un marco muy sólido e innovador que puede ahorrar mucho tiempo a los humanos y, además, es una combinación muy novedosa del LLM y el solucionador», dice Hao.

Este trabajo fue financiado, en parte, por la Oficina de Investigación Naval y el Laboratorio de IA Watson del MIT-IBM.