RT Generic
T1 Estudio del problema de la planificación de objetos móviles sin colisiones con obstáculos móviles
T2 Study of the problem of collision-free mobile objects planning under the presence of mobile obstacles
A1 Carreño López, Daniel María
AB 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.
AB 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.
YR 2024
FD 2024
LK https://hdl.handle.net/20.500.14352/110345
UL https://hdl.handle.net/20.500.14352/110345
LA spa
NO Trabajo de Fin de Doble Grado en Ingeniería Informática y Matemáticas, Facultad de Informática UCM, Departamento de Sistemas Informáticos y Computación, Curso 2023/2024.
DS Docta Complutense
RD 9 abr 2025