Zero-Shot Signal Temporal Logic Planning with Disjunctive Branch Selection in Dynamic Semantic Maps

Resumen Técnico: Planificación de Lógica Temporal de Señales Zero-Shot con Selección de Ramas Disyuntivas en Mapas Semánticos Dinámicos

1. Formulación del Problema

El artículo aborda el desafío de la planificación de Lógica Temporal de Señales (STL) en entornos de mapas variables donde la dinámica del sistema es desconocida. El objetivo es sintetizar una trayectoria de horizonte finito $x_{0:T}$ que satisfaga una especificación STL compleja $\phi$, cumpliendo al mismo tiempo las restricciones de evitación de colisiones definidas por un mapa laberinto binario dinámico $M$.

Las restricciones y desafíos clave incluyen:

• Generalización Zero-Shot: El solucionador debe manejar diseños de mapas no vistos, configuraciones de obstáculos y especificaciones STL sin reentrenamiento ni ajuste fino específicos de la instancia.
• Dinámicas Desconocidas: El planificador opera sin una función de transición explícita $f(x_t, u_t)$, dependiendo en su lugar de un conjunto de datos offline de trayectorias históricas.
• Complejidad Disyuntiva: Las especificaciones STL a menudo contienen disyunciones (operadores O, $\lor$). Resolverlas requiere seleccionar una rama específica de la lógica para satisfacer. En entornos dinámicos, una selección no guiada puede llevar a elegir ramas que son geométricamente inviables o dinámicamente difíciles, causando fallos en la planificación.
• Anclaje Temporal: Descomponer una fórmula STL de alto nivel en subtareas requiere una asignación temporal precisa (determinar cuándo visitar regiones específicas), lo cual es difícil de aprender consistentemente a través de geometrías de mapas variables.

2. Metodología

El marco propuesto sigue un paradigma de "descomponer-luego-sintetizar", integrando tres componentes principales:

A. Selección Heurística de Ramas Disyuntivas
Para abordar la explosión combinatoria y los problemas de viabilidad de las disyunciones, la fórmula STL se convierte primero en Forma Normal Disyuntiva (DNF). Una heurística ligera luego clasifica las ramas candidatas ($\phi_k$) para seleccionar la más viable ($\phi^*$) basándose en tres criterios:

1. Complejidad de Operadores Temporales: Penaliza las ramas con anidamiento complejo de operadores temporales (por ejemplo, $U$, $G$), que empíricamente son más difíciles de satisfacer.
2. Alcanzabilidad del Mapa: Calcula distancias basadas en grafos (por ejemplo, BFS/DFS) en el mapa actual $M$ para penalizar las ramas que requieren regiones difíciles de alcanzar o separadas por obstáculos.
3. Holgura Temporal: Premia las ramas con intervalos de tiempo más grandes entre subtareas, ofreciendo más flexibilidad para la generación de trayectorias.
   La rama con la puntuación heurística mínima se selecciona para la planificación posterior.

B. Aprendizaje por Refuerzo Transitivo (TRL) para Predicción de Tiempo
Un predictor de tiempo aprendido estima la cantidad de pasos de tiempo discretos requeridos para viajar entre puntos de referencia de subobjetivos. Para garantizar la consistencia temporal a través de diferentes escalas y diseños de mapas, el predictor se entrena utilizando Aprendizaje por Refuerzo Transitivo (TRL) en lugar de la regresión punto a punto estándar.

• Mecanismo: TRL impone que las longitudes de pasos predichas preserven el orden relativo implicado por los datos de entrenamiento. Si la trayectoria $i$ toma más tiempo que la trayectoria $j$ en la verdad fundamental, el modelo debe predecir $\hat{\Delta t}_i > \hat{\Delta t}_j$.
• Función de Pérdida: El objetivo de entrenamiento combina una pérdida de regresión $L_1$ con una pérdida de clasificación basada en márgenes ($L_{TRL}$) que penaliza las violaciones de las restricciones de ordenamiento transitivo. Esto mejora la calibración global de las estimaciones de tiempo.

C. Generador de Trayectorias Transformer Condicionado al Mapa
La trayectoria final se sintetiza utilizando un Transformer autoregresivo que se condiciona en:

• Tokens de Mapa: Mapa laberinto binario codificado $M$ y descriptores de región.
• Tokens de Tiempo: Intervalos temporales derivados de la rama STL seleccionada.
• Prefijo de Trayectoria: El historial de estados actual.
  El modelo genera la trayectoria token por token (estado por estado). Para mitigar el sesgo de exposición durante el entrenamiento, se emplea muestreo programado, transitando gradualmente desde la fuerza del profesor (usando estados de verdad fundamental) hasta la generación autoregresiva (usando predicciones del modelo). El generador es agnóstico a la dinámica, lo que significa que no recibe parámetros explícitos del modelo dinámico en tiempo de inferencia.

3. Contribuciones Clave

1. Manejo Heurístico de Disyunciones: Introducción de una heurística ligera de tres criterios para seleccionar ramas disyuntivas, expandiendo significativamente el rango de especificaciones STL resolubles en la práctica al evitar caminos lógicos inviables.
2. Planificación Zero-Shot en Mapas Variables: Desarrollo de un generador de trayectorias Transformer condicionado al mapa que se generaliza a diseños de obstáculos no vistos y tamaños de mapas sin reentrenamiento, mejorando la universalidad de la resolución STL.
3. Aprendizaje por Refuerzo Transitivo para Anclaje Temporal: Aplicación de TRL para entrenar el predictor de tiempo, asegurando una asignación temporal consistente a través de subtareas descompuestas y mejorando la robustez general en la satisfacción de STL.
4. Validación Empírica: Demostración de ganancias consistentes de rendimiento en diversos entornos (complejidades de mapas variables) y dinámicas (modelos de doble integrador y unicycle), validando la robustez del marco frente a cambios de distribución.

4. Resultados Experimentales

Los experimentos se realizaron en una referencia de navegación basada en cuadrícula (familia U-Maze) con tamaños de mapa de $5\times5$, $7\times7$ y $9\times9$, bajo dinámicas de doble integrador (DI) y unicycle (UNI).

• Tasa de Éxito: El método propuesto logró mejoras consistentes en las tasas de éxito en comparación con una línea base (el mismo método sin selección heurística de ramas). Las ganancias fueron más pronunciadas en mapas más grandes y complejos (por ejemplo, $9\times9$), donde la heurística podó eficazmente las ramas inviables.
• Robustez: Los valores de robustez (medida cuantitativa de la satisfacción STL) permanecieron comparables o superaron a la línea base, lo que indica que las tasas de éxito más altas no se lograron sacrificando los márgenes de la especificación.
• Eficiencia: Aunque el tiempo de planificación nominal fue comparable al de la línea base, la inclusión de la selección heurística redujo sustancialmente el tiempo de planificación efectivo al podar el espacio de búsqueda tempranamente.
• Generalización: El generador de trayectorias sintetizó con éxito trayectorias viables para las dinámicas DI y UNI sin entradas explícitas del modelo dinámico, demostrando una fuerte transferibilidad entre modelos de movimiento.

5. Significado y Afirmaciones

El artículo afirma que su principal significado radica en cerrar la brecha entre el razonamiento lógico formal y la síntesis de trayectorias basada en datos en entornos dinámicos y desconocidos. Al desacoplar la ramificación lógica de alto nivel (mediante la heurística) de la realización geométrica de bajo nivel (mediante el Transformer), el marco aborda la fragilidad de los planificadores zero-shot existentes cuando se enfrentan a geometrías de mapas variables y lógica disyuntiva compleja.

Los autores enfatizan que su enfoque ofrece una solución escalable y zero-shot que no requiere reentrenamiento específico del entorno, convirtiéndolo en una dirección prometedora para desplegar planificadores basados en STL en escenarios del mundo real donde los mapas y los obstáculos cambian de manera impredecible. La integración de TRL se destaca como un método novedoso para mejorar la coherencia temporal de los planificadores aprendidos, un factor crítico para satisfacer restricciones temporales de largo horizonte.