Resumen: El hallazgo de ruta múltiple (MAPF) es el problema de encontrar un conjunto de rutas sin colisión, una para cada agente en un entorno compartido. Su objetivo es minimizar la suma de los costos de ruta (SOC), donde el costo de ruta de cada agente se define como el tiempo de viaje desde su ubicación de inicio a su ubicación objetivo. La búsqueda basada en conflictos de estimación explícita (EECBS) es el algoritmo principal para el MAPF subóptimo limitado, y el SOC de la solución es como máximo un factor especificado por el usuario $ W $ de óptimo. EECBS mantiene conjuntos de rutas y un límite más bajo $ lb $ en el SOC óptimo. Luego, selecciona iterativamente un conjunto de rutas cuyo SOC es como máximo $ W CDOT LB $ e introduce restricciones para resolver colisiones. Para cada ruta en un conjunto, EECBS mantiene un límite inferior en su ruta óptima que satisface las restricciones. Al encontrar una ruta subóptima individualmente limitada con el costo a lo sumo un umbral de $ W $ veces su límite inferior, EECBS garantiza encontrar una solución subpima limitada. Para acelerar los EECB, el trabajo anterior utiliza la distribución flexible para aumentar el umbral. Aunque los EECB con garantías de distribución FLEX para encontrar una solución subóptima limitada, el aumento de los umbrales puede empujar el SOC más allá de $ W CDOT LB $, lo que obliga a los EECB a cambiar entre diferentes conjuntos de rutas en lugar de resolver colisiones en un conjunto particular de rutas y así reducir la eficiencia. Para abordar este problema, proponemos una distribución flexible basada en conflictos que distribuye Flex en proporción al número de colisiones. También estimamos los retrasos necesarios para satisfacer las restricciones y proponer la distribución flexible basada en retrasos. Además de eso, proponemos una distribución flexible de estrategia mixta, combinando ambos en un marco jerárquico. Probamos que los EECB con nuestros nuevos mecanismos de distribución Flex son completos y limitados. Nuestros experimentos muestran que nuestros enfoques superan la distribución Flex original (codiciosa).
Publicado Originalme en export.arxiv.org El 23 de julio de 2025.
Ver Fuente Original
