Estudio del problema de la planificación de objetos móviles sin colisiones con obstáculos móviles

Abstract

En este trabajo consideramos el problema de desplazar dinámicamente varios objetos por las aristas y vértices de un grafo valorado bidireccional en el que hay también obstáculos móviles, sin que los objetos sufran riesgo de colisionar entre sí ni con los obstáculos. Mostramos que averiguar si esto es posible se trata de un problema PSPACE-duro. También discutimos cómo podría llegar a demostrarse que es un problema en PSPACE. Estudiamos también varias variaciones de dicho problema, algunas de ellas PSPACE-completas.In this work, we consider the problem of moving dynamically multiple objects through the edges and vertexes of a weighted undirected graph in which there are mobile obstacles while avoiding any risk of the objects colliding between themselves or with the obstacles. We show that determining whether this is possible is a PSPACE-hard problem. We also discuss how this problem could be shown to be in PSPACE. Additionally, we study the complexity of some variations of said problem, some of them PSPACE-complete.