Relay Races Along a Pair of Selectable Routes

Рассматривается математическая модель, представляющая собой формализацию конкуренции двух команд, которые должны преодолевать дистанцию, состоящую из этапов. В рассматриваемом случае на каждом этапе есть различное количество маршрутов, которые участники команды могут выбрать для прохождения. Показано, что конкуренция носит характер эстафеты, а двухпараллельный полумарковский процесс - естественный подход к моделированию ситуации.
Получена формула для расчета числа коммутационных траекторий. Показано, что из сложного двухпараллельного полумарковского процесса, описывающего блуждание по выбранным маршрутам, можно получить обычный полумарковский процесс с использованием рекурсивной процедуры. Предложены формулы для реализации рекурсии.
Предложена концепция распределенной неустойки. Показано, что неустойка зависит от разности этапов, команды преодолевают в текущее время и маршруты, по которым участники решали преодолеть этап. Получена формула оценки общей суммы неустойки, которую выплачивает одна команда другой команде. Показано, что сумма неустойки может использоваться в качестве критерия оптимизации в задаче оптимизации стратегии игры.

Ключевые слова

эстафета; двухпараллельный полумарковский процесс; дистанция; этап; маршрут; распределенная неустойка; рекурсивная процедура.

Литература

1. Heymann, M. Concurrency and Discrete Event Control / M. Heymann // IEEE Control Systems Magazine. - 1990. - V. 10. - P. 103-112.
2. Chatterjee, K. Simple Stochastic Parity Games / K. Chatterjee, M. Jurdzi'nski, T. Henzinger // Lecture Notes in Computer Science. - 2003. - V. 2803. - P. 100-113.
3. Ivutin, A.N. Simulation of Concurrent Games / A.N. Ivutin, E.V. Larkin // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2015. - Т. 8, № 2. - С. 43-54.
4. Valk, R. Concurrency in Communicating Object Petri Nets / R. Valk // Concurrent Object-Oriented Programming and Petri Nets. - 2001. - P. 164-195.
5. Larkin, E.V. Simulation of Relay-Races / E.V. Larkin, A.N. Ivutin, V.V. Kotov, A.N. Privalov // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2016. - Т. 9, № 4. - С. 117-128.
6. Larkin, E.V. Estimation of Latency in Embedded Real-Time Systems / E.V. Larkin, A.N. Ivutin // 3-rd Meditteranean Conference on Embedded Computing (MECO-2014). - Budva; Montenegro, 2014. - P. 236-239.
7. Korolyuk, V. Semi-Markov Random Evolutions / V. Korolyuk, A. Swishchuk. - N.Y.: Springer-Science and Buseness Media, 1995.
8. Iverson, M.A. Run-Time Statistical Estimation of Task Execution Times for Heterogeneous Distributed Computing / M.A. Iverson, F. Ozguner, G.J. Follen // Proceedings of 5th IEEE International Symposium on High Performance Distributed Computing, N.Y., USA, August 6-9, 1996. - N.Y.: Institute of Electrical and Electronics Engineers, 1996. - P. 263-270.
9. Limnios, N. Discrete-Time Semi-Markov Random Evolutions and Their Applications / N. Limnios, A. Swishchuk // Advances in Applied Probability. - 2013. - V. 45, № 1. - P. 214-240.
10. Марков, А.А. Распространение закона больших чисел на величины, зависящие друг от друга / А.А. Марков // Известия физико-математического общества при Казанском университете. - 1906. - Т. 15. - С. 135-156.
11. Bielecki, T.R. Conditional Markov Chains: Properties, Construction and Structured Dependence / T.R. Bielecki, J. Jakubowski, M. Niewkeglowski // Stochastic Processes and Their Applications. - 2017. - V. 127, № 4. - P. 1125-1170.
12. Janssen, J. Applied Semi-Markov Processes / J. Janssen, R. Manca. - N.Y.: Springer, 2005.
13. Larkin, E.V. Semi-Markov Modeling of Command Execution by Mobile Robots / E.V. Larkin, A.N. Ivutin, V.V. Kotov, A.N. Privalov // Interactive Collaborative Robotics (ICR 2016), Budapest, Hungary, Lecture Notes in Artifical Intelligence. Subseries of Lecture Notes in Computer Science. - N.Y.: Springer, 2016. - P. 189-198.
14. Bauer, H. Probability Theory / H. Bauer. - Berlin; N.Y.: Walter de Gruyter, 1996.
15. Shiryaev, A.N. Probability / A.N. Shiryaev. - N.Y.: Springer Science and Business Media, 1996.
16. Bellman, R.E. Dynamic Programming / R.E. Bellman. - N.Y.: Dover Publications, 2003.
17. Myerson, R.B. Game Theory / R.B. Myerson. - Cambridge: Harvard University Press, 1997.
18. Goetz, B. Java Concurrency in Practice / B. Goetz, T. Peierls. - Boston: Addison Wesley, 2006.