Un Problema de Optimización Multi-Objetivo sobre la Evacuación de 2 Robots del Disco en el Modelo Cara a Cara; Compensaciones entre el Análisis del Peor Caso y el Análisis del Caso Promedio
Autores: Chuangpishit, Huda; Georgiou, Konstantinos; Sharma, Preeti
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Un Problema de Optimización Multi-Objetivo sobre la Evacuación de 2 Robots del Disco en el Modelo Cara a Cara; Compensaciones entre el Análisis del Peor Caso y el Análisis del Caso Promedio
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Evacuación
Robots
Análisis de caso promedio
Análisis de peor caso
Algoritmos aleatorios
Optimización restringida
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
El problema de evacuar dos robots del disco en el modelo cara a cara fue introducido por primera vez por Czyzowicz et al. [DISC"2014] y ha sido estudiado extensamente (junto con muchas variaciones) desde entonces en relación con el análisis del peor caso. Iniciamos el estudio del mismo problema en relación con el análisis del caso promedio, que también es equivalente a diseñar algoritmos aleatorios para el problema. En particular, introducimos el problema de optimización restringida 2EvacF2F, en el que se intenta minimizar el costo del algoritmo de evacuación en el caso promedio dado que el costo del peor caso no excede w. El problema es de especial interés con respecto a aplicaciones prácticas, ya que un objetivo común en operaciones de búsqueda y rescate es minimizar el tiempo promedio de finalización, dado que no se excede un cierto umbral en el peor caso, por ejemplo, por razones de seguridad o de energía limitada. Nuestra principal contribución es el diseño y análisis de familias de nuevos algoritmos de evacuación parametrizados que pueden resolver 2EvacF2F, para cada w para el cual el problema es factible. Notablemente, el análisis del peor caso del problema, desde su introducción, se ha basado en cálculos numéricos técnicos asistidos por computadora, siguiendo un tedioso análisis de trayectoria de robots. Parte de nuestra contribución es un nuevo procedimiento sistemático, que dado cualquier algoritmo de evacuación, puede derivar su rendimiento en el peor y en el caso promedio de manera clara y unificada.
Descripción
El problema de evacuar dos robots del disco en el modelo cara a cara fue introducido por primera vez por Czyzowicz et al. [DISC"2014] y ha sido estudiado extensamente (junto con muchas variaciones) desde entonces en relación con el análisis del peor caso. Iniciamos el estudio del mismo problema en relación con el análisis del caso promedio, que también es equivalente a diseñar algoritmos aleatorios para el problema. En particular, introducimos el problema de optimización restringida 2EvacF2F, en el que se intenta minimizar el costo del algoritmo de evacuación en el caso promedio dado que el costo del peor caso no excede w. El problema es de especial interés con respecto a aplicaciones prácticas, ya que un objetivo común en operaciones de búsqueda y rescate es minimizar el tiempo promedio de finalización, dado que no se excede un cierto umbral en el peor caso, por ejemplo, por razones de seguridad o de energía limitada. Nuestra principal contribución es el diseño y análisis de familias de nuevos algoritmos de evacuación parametrizados que pueden resolver 2EvacF2F, para cada w para el cual el problema es factible. Notablemente, el análisis del peor caso del problema, desde su introducción, se ha basado en cálculos numéricos técnicos asistidos por computadora, siguiendo un tedioso análisis de trayectoria de robots. Parte de nuestra contribución es un nuevo procedimiento sistemático, que dado cualquier algoritmo de evacuación, puede derivar su rendimiento en el peor y en el caso promedio de manera clara y unificada.