Cómo encontrar el camino más corto en situación dinámica

Question

Hace algunos días, alguien me preguntó: si tenemos algunos agentes en nuestro entorno, y quieren ir desde sus fuentes a sus destinos, cómo podemos encontrar el camino más corto para todos de tal manera que no deberían tener conflicto durante su caminata.

El punto del problema es que todos los agentes caminan simultáneamente en el entorno (que puede modelarse mediante un gráfico ponderado no dirigido), y no debería haber ninguna colisión. Pensé en esto, pero no pude encontrar la ruta óptima para todos ellos. Pero seguro que hay demasiadas ideas heurísticas para este problema.

Supongamos entrada es un gráfico G (V, E), agentes m que están en: S , S , ..., S _m nodos del gráfico de la puesta en marcha y que deben ir a los nodos D , ... D _m al final. También puede haber es conflicto en nodos S _i o D _i, ... pero estos conflictos no son importantes que no deberían haber conflicto cuando están en sus nodos internos de su camino.

Si su ruta no debe tener el mismo nodo interno, será un tipo de problema k-disjoint paths que es NPC, pero en este caso las rutas pueden tener los mismos nodos, pero el agente no debe estar en el mismo nodo al mismo tiempo. No sé, puedo decir la declaración exacta del problema o no. Si es confuso, dígame en los comentarios para editarlo.

¿Hay algún algoritmo óptimo y rápido (por óptimo quiero decir que la suma de la longitud de todas las rutas sea lo más pequeña posible, y por rápido quiero decir un buen algoritmo de tiempo polinomial).

Answer 1

una búsqueda en Google revela dos enlaces que pueden ser útiles:

• Cooperative path planning for multi-robot systems in dynamic domains
• Optimizing schedules for prioritized path planning of multi-robot systems

Editar: Desde el capítulo del libro (primer enlace):

Hay varios enfoques para planificar el camino Sin embargo, encontrar la solución óptima es NP-hard. Hopcraft et al. (1984) simplifican el problema de planificación al problema de mover rectángulos en un contenedor rectangular. Probaron la dureza NP de encontrando un plan de una configuración dada a una configuración de objetivo con la menor cantidad de pasos . Por lo tanto, todos los enfoques factibles para la planificación de rutas son un compromiso entre la eficiencia y la precisión del resultado.

No puedo encontrar el artículo original de Hopcroft en línea, pero dado que cita, sospecho que el problema se reduce a la tarea de navegación es similar a Rush Hour, que es PSPACE-completo.

Answer 2

Si es sólo una cuestión de ir del punto A al punto B para cada robot, sólo podría utilizar un algoritmo de búsqueda como A* (A Star) o Best-First.

Dale una heurística simple como la suma de distancias del objetivo.