Función de utilidad del tiempo

Una función de tiempo/utilidad ( TUF ), anteriormente función de tiempo/valor , especifica la utilidad específica de la aplicación que una acción (por ejemplo, tarea computacional, movimiento mecánico) produce en función de su tiempo de finalización. ^{[ 1 ] [ 2 ]} Las TUF y sus interpretaciones de utilidad (semántica), escalas y valores se derivan del conocimiento específico del dominio de la aplicación. Un ejemplo (pero no el único) de interpretación de la utilidad es la importancia relativa de una acción, que de otro modo es independiente de su puntualidad . El plazo tradicional representado como una TUF es un caso especial: un paso descendente de utilidad de 1 a 0 en el momento del plazo; por ejemplo, puntualidad sin importancia. Una TUF es más general: tiene un tiempo crítico, con formas y valores de utilidad específicos de la aplicación a cada lado, después del cual no aumenta. Las diversas definiciones de tiempo real firme y flexible de investigadores y profesionales también pueden representarse como casos especiales del modelo TUF.

El criterio de optimalidad para programar múltiples acciones con restricciones TUF ha sido históricamente en la literatura solo la acumulación máxima de utilidad ( UA ), por ejemplo, una suma ponderada (quizás esperada) de las utilidades de finalización de las acciones individuales. Esto toma en cuenta la puntualidad con respecto a los tiempos críticos. Se han añadido criterios adicionales (por ejemplo, energía, previsibilidad), restricciones (por ejemplo, dependencias), modelos de sistema, algoritmos de programación y garantías a medida que el paradigma TUF/UA y sus casos de uso han evolucionado. De manera más expresiva, TUF/UA permite intercambiar la utilidad acumulada, la puntualidad, la previsibilidad y otros criterios y restricciones de programación para que la programación produzca QoS de aplicación situacional ^{[ a ]} , en lugar de solo la puntualidad per se. Se han empleado instancias del paradigma TUF/UA en una amplia variedad de dominios de aplicación, con mayor frecuencia en sistemas militares.

El paradigma TUF/UA se creó originalmente para abordar ciertas necesidades de puntualidad de acción, previsibilidad de puntualidad y programación basada en QoS de aplicaciones de diversas aplicaciones militares para las cuales los conceptos y prácticas tradicionales en tiempo real no son suficientemente expresivos (por ejemplo, para sistemas dinámicos críticos en cuanto a puntualidad que no tienen plazos) y resiliencia de carga (por ejemplo, para sistemas sujetos a sobrecargas de acción rutinarias). Una clase de ejemplo común importante de tales aplicaciones es la defensa antimisiles (nocionalmente ^{[ 3 ] [ 4 ] [ 5 ]} ).

Posteriormente, se han estudiado numerosas variaciones del modelo TUF original, el modelo de sistema del paradigma TUF/UA y, por lo tanto, las técnicas y algoritmos de programación, en la literatura académica —por ejemplo, ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ]} —y se han aplicado en contextos civiles.

Algunos ejemplos de estos últimos incluyen: sistemas ciberfísicos, ^{[ 11 ]} IA, ^{[ 12 ]} sistemas multi-robot, ^{[ 13 ]} programación de drones, ^{[ 14 ]} robots autónomos, ^{[ 15 ]} transferencias inteligentes de datos de vehículos a la nube, ^{[ 16 ]} control de procesos industriales, ^{[ 17 ]} sistemas de transacciones, ^{[ 18 ]} computación de alto rendimiento, ^{[ 19 ]} sistemas en la nube, ^{[ 20 ]} clústeres heterogéneos, ^{[ 21 ]} computación orientada a servicios, ^{[ 22 ]} redes, ^{[ 23 ]} y gestión de memoria para máquinas reales ^{[ 24 ]} y virtuales ^{[ 25 ]} . Un ejemplo de una acería se describe brevemente en la Introducción de la tesis doctoral de Clark. ^{[ 26 ]}

Los TUF y sus interpretaciones de utilidad (semántica), escalas y valores se derivan del conocimiento específico del dominio. ^{[ 27 ] [ 5 ]} Una interpretación históricamente frecuente de la utilidad es la importancia relativa de las acciones. ^{[ b ]} Se ha ideado un marco para asignar a priori valores de utilidad estáticos sujetos a fuertes restricciones en los modelos del sistema, ^{[ 8 ]} pero la investigación y el desarrollo posteriores (al igual que los anteriores) de TUF/UA han preferido depender de explotar la especificidad de la aplicación en lugar de intentar crear marcos más generales. Sin embargo, dichos marcos y herramientas siguen siendo un tema de investigación importante.

Por convención tradicional, una TUF es una función cóncava , incluidas las lineales. Véase la representación de algunos ejemplos de TUF.

Los artículos TUF/UA en la literatura de investigación, con pocas excepciones, por ejemplo, ^{[ 28 ] [ 6 ] [ 29 ] [ 30 ] [ 8 ] [ 10 ]} son ​​solo para TUF lineales o lineales por partes ^{[ 31 ]} (incluidos los convencionales basados ​​en plazos) porque son más fáciles de especificar y programar. En muchos casos, los TUF son solo monótonamente decrecientes .

Una función constante representa la utilidad de una acción, independientemente de su tiempo de finalización; por ejemplo, su importancia relativa constante. Esto permite programar de forma coherente tanto acciones dependientes como independientes del tiempo.

Una TUF tiene un tiempo crítico global , después del cual su utilidad no aumenta. Si una TUF nunca disminuye, su tiempo crítico global es el primer momento en que alcanza su utilidad máxima. Una TUF constante tiene un tiempo crítico arbitrario para fines de planificación, como el tiempo de liberación de la acción o el tiempo de terminación de la TUF. El tiempo crítico global puede ir seguido de tiempos críticos locales ^{[ 2 ]} ; por ejemplo, considérese una TUF con una secuencia de pasos descendentes, tal vez para aproximar una curva descendente suave. ^{[ c ]}

Los valores de utilidad de TUF suelen ser números enteros o racionales.

La utilidad TUF puede incluir valores negativos. (Una TUF que tenga valores negativos en su rango no necesariamente se descarta de la planificación ni se interrumpe durante su ejecución; esa decisión depende del algoritmo de planificación).

Un tiempo límite convencional ( d ) representado como un TUF es un caso especial: un TUF de paso descendente ^{[ d ]} que tiene una penalización unitaria (es decir, que tiene valores de utilidad 1 antes y 0 después de su tiempo crítico).

En términos más generales, una TUF permite que las funciones escalonadas descendentes (y ascendentes) tengan cualquier utilidad de tiempo pre y postcrítico.

La tardanza ^{[ 32 ]} representada como una TUF es un caso especial cuya utilidad no nula es la función lineal C - d , donde C es el tiempo de finalización de la acción, ya sea actual, esperado o creído. ^{[ e ]} De manera más general, una TUF permite que la anticipación y la tardanza no nulas sean no lineales ; por ejemplo, una mayor tardanza puede resultar en una utilidad que disminuye de forma no lineal, como cuando se detecta una amenaza.

De este modo, las TUF proporcionan una rica generalización de las restricciones de tiempo de finalización de acciones tradicionales en la computación en tiempo real .

Alternativamente, el paradigma TUF/UA puede emplearse para utilizar la puntualidad con respecto al tiempo crítico global como un medio para un fin de acumulación de utilidad, es decir, la calidad de servicio (QoS) a nivel de aplicación, en lugar de que la puntualidad en sí misma sea un fin en sí misma.

Un TUF (su forma y valores) puede ser adaptado dinámicamente por una aplicación o su entorno operativo, ^{[ 2 ]} independientemente de cualquier acción que esté actualmente en espera o en ejecución. ^{[ f ]}

Estas adaptaciones suelen ocurrir en eventos discretos, por ejemplo, en un cambio de modo de aplicación como en las fases de vuelo de un misil balístico. ^{[ 5 ]}

Alternativamente, estas adaptaciones pueden ocurrir de forma continua, como en el caso de acciones cuyas duraciones operativas y TUF son funciones específicas de la aplicación que dependen de cuándo se liberan o comienzan a operar dichas acciones. Las duraciones operativas pueden aumentar o disminuir, o ambas cosas, y pueden no ser monótonas. Este caso continuo se denomina programación dependiente del tiempo . ^{[ 33 ] [ 34 ]} La programación dependiente del tiempo se introdujo para (pero no se limita a) ciertas aplicaciones militares en tiempo real, como los sistemas de seguimiento por radar. ^{[ 35 ] [ 36 ] [ g ]}

Múltiples acciones en un sistema pueden competir por el acceso a recursos compartidos exclusivamente de forma secuencial ^{[ h ]} , tanto físicos como procesadores, redes, dispositivos de aplicación exógenos (sensores, actuadores, etc.) y lógicos como sincronizadores, datos.

El paradigma TUF/UA resuelve cada instancia de esta contención mediante una técnica algorítmica específica de la aplicación que crea (o actualiza) una planificación en eventos de planificación , por ejemplo, momentos (como la llegada o finalización de una acción) o estados. Las acciones en contención de la instancia se envían para el acceso a recursos de forma secuencial, en orden, desde el principio de la planificación. Por lo tanto, la secuenciación de acciones UA no es voraz. ^{[ i ]}

La técnica algorítmica crea un cronograma basado en uno o más objetivos específicos de la aplicación (es decir, criterios de optimización).

El objetivo principal de la programación de acciones con TUF es maximizar la utilidad acumulada ( UA ). La utilidad acumulada es una suma polinómica específica de la aplicación de las utilidades de las acciones completadas en la programación. Cuando las acciones tienen uno o más parámetros estocásticos (por ejemplo, la duración de la operación), la utilidad acumulada también es estocástica (es decir, una suma polinómica esperada).

La utilidad y la utilidad acumulada son genéricas, sus interpretaciones (semántica) y escalas son específicas de la aplicación. ^{[ 27 ]}

La duración de una acción puede ser fija y conocida en el momento de la configuración del sistema. En términos más generales, puede ser fija o aleatoria, pero no se conoce (ni con certeza ni con certeza) hasta que se ejecuta o se libera.

La duración de una operación puede ser una función específica de la aplicación que depende del tiempo de inicio de la operación; puede aumentar, disminuir o ambas cosas, y puede no ser monótona. Este caso se denomina planificación dependiente del tiempo . ^{[ 33 ] [ 34 ] [ 35 ] [ 36 ]}

• En tiempo real para el mundo real.
• 2006-2009, Grupo de Investigación de Software de Sistemas, Binoy Ravindran, ECE, Virginia Tech.
• Michael L. Pindo, Planificación: Teoría, algoritmos y sistemas, 5.ª ed., 2015.
• Stanislaw Gawiejnowicz, Modelos y algoritmos de planificación dependiente del tiempo , 2.ª ed., ISBN del libro electrónico 978-3-662-59362-2, Springer, 2020.
• Chris N. Potts y Vitaly A. Strusevich, Cincuenta años de planificación: un repaso de los hitos (2009)
• Revista de planificación.
• Conferencia internacional multidisciplinaria sobre planificación.
• Taller internacional sobre problemas de programación dinámica.