Reunión Óptima en Tiempo Bajo Visibilidad Limitada con Acuerdo de Un Eje
Autores: Poudel, Pavan; Sharma, Gokarna
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Reunión Óptima en Tiempo Bajo Visibilidad Limitada con Acuerdo de Un Eje
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Robots
Recolección
Autónomos
Visibilidad limitada
Complejidad temporal
Algoritmo
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
Consideramos el entorno distribuido de N robots móviles autónomos que operan en ciclos de Mirar-Calcular-Mover (LCM) siguiendo el célebre modelo clásico de robots obliviosos. Estudiamos el problema fundamental de reunir N robots autónomos en un plano, lo que requiere que todos los robots se encuentren en un solo punto (o se posicionen dentro de un área pequeña) que no se conoce de antemano. Consideramos la visibilidad limitada bajo la cual los robots solo pueden ver a otros robots hasta una distancia euclidiana constante y nos enfocamos en la complejidad temporal de la reunión por parte de los robots bajo visibilidad limitada. Existe un algoritmo de tiempo O(DG) para este problema en el entorno totalmente sincrónico, asumiendo que los robots acuerdan un eje de coordenadas (digamos, el norte), donde DG es el diámetro del grafo de visibilidad de la configuración inicial. En este artículo, proporcionamos el primer algoritmo de tiempo O(DE) para este problema en el entorno asincrónico bajo la misma suposición de acuerdo de los robots con un eje de coordenadas, donde DE es la distancia euclidiana entre el par de robots más alejados en la configuración inicial. El tiempo de ejecución de nuestro algoritmo es una mejora significativa ya que para cualquier configuración inicial de N>=1 robots, DE.
Descripción
Consideramos el entorno distribuido de N robots móviles autónomos que operan en ciclos de Mirar-Calcular-Mover (LCM) siguiendo el célebre modelo clásico de robots obliviosos. Estudiamos el problema fundamental de reunir N robots autónomos en un plano, lo que requiere que todos los robots se encuentren en un solo punto (o se posicionen dentro de un área pequeña) que no se conoce de antemano. Consideramos la visibilidad limitada bajo la cual los robots solo pueden ver a otros robots hasta una distancia euclidiana constante y nos enfocamos en la complejidad temporal de la reunión por parte de los robots bajo visibilidad limitada. Existe un algoritmo de tiempo O(DG) para este problema en el entorno totalmente sincrónico, asumiendo que los robots acuerdan un eje de coordenadas (digamos, el norte), donde DG es el diámetro del grafo de visibilidad de la configuración inicial. En este artículo, proporcionamos el primer algoritmo de tiempo O(DE) para este problema en el entorno asincrónico bajo la misma suposición de acuerdo de los robots con un eje de coordenadas, donde DE es la distancia euclidiana entre el par de robots más alejados en la configuración inicial. El tiempo de ejecución de nuestro algoritmo es una mejora significativa ya que para cualquier configuración inicial de N>=1 robots, DE.