🤖 AI

Declarative Problem Solving in UAM Strategic Deconfliction

Este artículo propone un enfoque de Programación de Conjuntos de Respuestas (ASP) para la desconflicción estratégica en la Movilidad Aérea Urbana, demostrando mediante una evaluación comparativa frente a la Programación de Restricciones que el ASP ofrece una velocidad de ejecución y escalabilidad superiores para escenarios de planificación de vuelos de pequeño a mediano tamaño.

Autores originales: Gioacchino Sterlicchio, Angelo Oddi, Riccardo Rasconi, Francesca Alessandra Lisi

Publicado 2026-07-24

📖 3 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Gioacchino Sterlicchio, Angelo Oddi, Riccardo Rasconi, Francesca Alessandra Lisi

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que el cielo sobre nuestras ciudades está a punto de volverse mucho más concurrido. En lugar de solo unos pocos aviones y helicópteros, nos enfrentamos a un futuro lleno de miles de vehículos voladores eléctricos —como drones gigantes y taxis aéreos— zigzagueando entre rascacielos para entregar paquetes o llevar a personas al trabajo. Esto se llama Movilidad Aérea Urbana (UAM, por sus siglas en inglés). ¿El gran problema? Si todo el mundo vuela cuando quiere, chocarán entre sí o se quedarán atrapados en un enorme atasco aéreo. Para solucionar esto, los científicos necesitan una forma de planificar las rutas de vuelo de todos antes incluso de que despeguen. Esto se llama "desconflicto estratégico", que es solo una forma elegante de decir "asegurarse de que dos cosas voladoras no intenten estar en el mismo lugar al mismo tiempo". Para resolver esto, los investigadores utilizan lenguajes informáticos especiales que actúan como resolutores de rompecabezas súper inteligentes. Un tipo de resolutor se llama "Programación de Restricciones" (CP), que es como un bibliotecario muy estricto que revisa cada una de las reglas antes de dejar salir un libro. Otro tipo es la "Programación de Conjuntos de Respuestas" (ASP), que es más como un arquitecto creativo que esboza rápidamente muchos planos posibles y elige el mejor que se ajuste a todas las normas de seguridad.

Este artículo presenta un nuevo sistema llamado STRADA, que utiliza ese enfoque de arquitecto creativo (ASP) para resolver el rompecabezas del tráfico de la UAM. Los autores, un equipo de investigadores de Italia, querían ver si este enfoque creativo podía manejar mejor el caos de un cielo urbano concurrido que el enfoque del bibliotecario estricto (CP). Construyeron un modelo digital del cielo utilizando "carriles" (como autopistas invisibles en el aire) y simularon miles de vehículos voladores intentando moverse a través de ellos. Probaron su sistema aumentando el número de vehículos voladores y haciendo que las ventanas de tiempo para el despegue fueran más anchas o más estrechas.

Los resultados fueron un poco como una carrera entre un velocista y un corredor de maratón. Cuando el número de vehículos voladores era pequeño o mediano (hasta aproximadamente 300), el sistema ASP (STRADA) fue increíblemente rápido, encontrando planes de vuelo seguros en segundos. Fue mucho más rápido que el sistema CP, que tardó mucho tiempo en encontrar siquiera una solución. Sin embargo, el sistema ASP tenía un inconveniente: utilizaba mucha memoria informática. Cuando el equipo intentó simular un cielo muy concurrido con 5,000 vehículos o ventanas de despegue muy amplias, el sistema ASP se quedó sin memoria y colapsó, como un cerebro intentando retener demasiados pensamientos a la vez. El sistema CP, por otro lado, fue más lento pero mucho mejor gestionando su memoria; no colapsaba tan fácilmente, aunque tardaba una eternidad en terminar el trabajo.

En resumen, el artículo sugiere que, para cielos urbanos de tamaño pequeño o mediano, el enfoque creativo de ASP es el ganador porque es rápido y eficiente. Pero si el cielo se vuelve demasiado concurrido o las reglas de planificación se vuelven demasiado laxas, el sistema choca contra un muro. Los autores concluyen que, si bien su nuevo método es un gran primer paso para gestionar el futuro tráfico aéreo, necesitan encontrar formas de hacer que pueda manejar multitudes aún mayores sin quedarse sin memoria. También planean probar sus ideas con datos del mundo real y diferentes sistemas informáticos para ver si se mantienen en el mundo real.

Resumen Técnico: Resolución Declarativa de Problemas en la Desconflicción Estratégica de la UAM

Definición del Problema

El artículo aborda la Desconflicción Estratégica (SD) de la Movilidad Aérea Urbana (UAM), una capa crítica de la Gestión del Tráfico Aéreo centrada en la planificación previa al vuelo. A medida que aumenta la demanda de vehículos aéreos (drones, taxis aéreos, eVTOLs) en áreas densamente pobladas, aumenta el riesgo de colisiones en el aire y conflictos con el tráfico existente. El problema central es generar un conjunto de trayectorias de vuelo programadas de tal manera que ningún par de aeronaves viole una distancia de seguridad especificada o separación temporal ( $h$ ) tanto en tiempo como en espacio.

El problema se formaliza como una pareja $(N, F)$ , donde $N$ es un grafo dirigido que representa la red del espacio aéreo (nodos como puntos de entrada/salida o puntos de paso, aristas como corredores unidireccionales) y $F$ es el conjunto de vuelos a programar. Cada vuelo $f_i$ se define por su ruta (un subgrafo acíclico), nodos de inicio/fin, velocidad y un intervalo de tiempo de lanzamiento solicitado $[e_i, l_i]$ . El objetivo es asignar una ruta específica y un tiempo de salida para cada vuelo de modo que:

Los vuelos despeguen dentro de sus intervalos solicitados.
Los vuelos que comparten un nodo de inicio tengan tiempos de salida distintos separados por al menos $h$ .
Los vuelos que ocupan el mismo nodo o carril en cualquier momento mantengan una separación temporal segura de al menos $h$ .
Se minimice el retraso total (la diferencia entre el tiempo de lanzamiento real y el tiempo solicitado más temprano).

Metodología

Los autores proponen STRADA (Scalable Trajectory Resolution Architecture for Deconfliction using ASP), un marco basado en Programación de Conjuntos de Respuestas (ASP). Este enfoque contrasta con los métodos numéricos tradicionales y las codificaciones existentes de Programación de Restricciones (CP).

1. Enfoque de Modelado

STRADA modela el problema de SD utilizando una estructura de espacio aéreo basada en carriles donde los carriles son grafos dirigidos. El marco soporta dos variaciones:

Velocidad Constante: Todos los vuelos mantienen una velocidad fija en todos los carriles.
Velocidad Variable: Las velocidades pueden ajustarse por carril para dar cuenta de obstáculos o clima, lo que requiere una modificación al predicado de velocidad en la codificación.

La codificación ASP (implementada utilizando el solver clingo) utiliza:

Hechos (Facts): Para definir la topología de la red (nodos, aristas, longitudes), restricciones de separación y especificaciones de vuelo (rutas, velocidades, ventanas temporales).
Reglas: Para calcular la Hora Estimada de Llegada (ETA) de los vuelos que atraviesan los carriles basándose en la distancia y la velocidad.
Restricciones de Integridad: Para eliminar conjuntos de respuestas inválidos donde se violen las restricciones de seguridad (por ejemplo, dos vuelos en el mismo nodo con insuficiencia de separación temporal, o dos vuelos en el mismo carril cruzando sus trayectorias).
Optimización: Se utiliza una directiva #minimize para minimizar la suma de los retrasos de todos los vuelos.

2. Línea Base Comparativa

El enfoque ASP se compara con una codificación de Programación de Restricciones (CP) (resuelta usando Minizinc/Gecode). La CP define el problema mediante variables, dominios y restricciones, con el objetivo de encontrar una solución que satisfaga todas las condiciones.

Contribuciones Clave

El artículo realiza tres contribuciones principales:

Formalización en ASP: Proporciona la primera formalización basada en lógica del problema de Desconflicción Estratégica de la UAM, definiendo las condiciones necesarias para la planificación de trayectorias libres de conflictos.
Marco STRADA: Introduce un marco completo que modela la topología de la red aérea, la flota de drones y la codificación de SD, capaz de manejar escenarios de velocidad constante y variable.
Evaluación Empírica: Presenta un análisis de escalabilidad exhaustivo comparando STRADA (ASP) frente a CP a través de diversos volúmenes de vuelo, tamaños de intervalo de lanzamiento y topologías de red (Intracity, Intercity, Airport Shuttle y mallas sintéticas).

Resultados Experimentales

Los experimentos se realizaron en una computadora portátil (AMD Ryzen 5, 8GB RAM) con un tiempo de espera de 900 segundos. El estudio varió el número de vuelos (15–400), los intervalos de lanzamiento (5–50 minutos) y los tamaños de red (mallas de 3x3 a 5x5).

Tiempo de Ejecución vs. Escalabilidad:
- ASP (STRADA): Demuestra una velocidad de ejecución superior para tamaños de problema pequeños a medianos (por ejemplo, menos vuelos, intervalos más estrechos). Sin embargo, tiene dificultades con la escalabilidad a medida que aumenta la complejidad. Para conteos de vuelos altos (300+) o intervalos de lanzamiento grandes, ASP frecuentemente alcanza el límite de tiempo o agota la memoria (errores de Out-of-Memory), exhibiendo una "explosión combinatoria" durante la fase de grounding.
- CP: Generalmente requiere significativamente más tiempo de ejecución que ASP, fallando a menudo en encontrar soluciones óptimas dentro del límite de tiempo incluso para tamaños de problema moderados. No obstante, la CP demuestra un uso de memoria más estable y eficiente a través de diversos tamaños de problema, rara vez alcanzando los límites de memoria donde la ASP falla.
Impacto de la Topología de Red:
- El tiempo de ejecución para ASP crece linealmente con el número de vuelos, pero aumenta de forma no lineal con el tamaño de la red debido a la generación de más átomos y reglas.
- Se observó un umbral crítico en la malla 5x5 con 5,000 vuelos, donde el uso de memoria se disparó de ~80 MB a 7.10 GB, indicando los límites actuales del modelo para escenarios de alta densidad.

Significancia y Reivindicaciones

El artículo afirma introducir la primera formulación basada en ASP para la Desconflicción Estratégica de la UAM. Los autores destacan tres ventajas clave de su enfoque:

Modelado Simplificado y Legible: La naturaleza declarativa de ASP permite una representación concisa de restricciones complejas.
Soporte para Optimización Compleja: ASP maneja eficazmente la naturaleza combinatoria de la planificación de trayectorias.
Adaptabilidad: El marco puede acomodar cambios en las especificaciones (por ejemplo, velocidades variables) sin una reprogramación mayor.

El estudio concluye que, si bien la ASP ofrece una ejecución más rápida para tareas de desconflicción estratégica en tiempo real de menor escala, su escalabilidad está actualmente limitada por las restricciones de memoria en escenarios de alta densidad. Por el contrario, la CP ofrece una mejor estabilidad de memoria pero sufre de un bajo rendimiento de tiempo. Los autores señalan que los parámetros experimentales actuales se alinean con los estándares contemporáneos de la UAM, pero sugieren que el trabajo futuro debe validar el modelo contra conjuntos de datos del mundo real y explorar el rendimiento de los solvers multiplataforma para evaluar plenamente la escalabilidad en entornos urbanos de alta densidad.