Relay Races Along a Pair of Selectable Routes

E. V. Larkin; A. V. Bogomolov; A. N. Privalov; N. N. Dobrovolsky

doi:10.14529/mmp180102

Авторы

E. V. Larkin Тульский государственный университет
A. V. Bogomolov Государственный научный центр Российской Федерации - Федеральный медицинский биофизический центр имени А.И. Бурназяна
A. N. Privalov Тульский государственный педагогический университет имени Л.Н. Толстого
N. N. Dobrovolsky Тульский государственный университет

DOI:

https://doi.org/10.14529/mmp180102

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

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

Аннотация

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

Биографии авторов

E. V. Larkin, Тульский государственный университет

Доктор технических наук, профессор

A. V. Bogomolov, Государственный научный центр Российской Федерации - Федеральный медицинский биофизический центр имени А.И. Бурназяна

Доктор технических наук, профессор

A. N. Privalov, Тульский государственный педагогический университет имени Л.Н. Толстого

Доктор технических наук, профессор

N. N. Dobrovolsky, Тульский государственный университет

Кандидат технических наук, доцент

Библиографические ссылки

Heymann M. Concurrency and Discrete Event Control. IEEE Control Systems Magazine, 1990, vol. 10, pp. 103-112. DOI: 10.1109/37.56284

Chatterjee K., Jurdzinski M., Henzinger T. Simple Stochastic Parity Games. Lecture Notes in Computer Science, 2003, vol. 2803, pp. 100-113. DOI: 10.1007/978-3-540-45220-1_11

Ivutin A.N, Larkin E.V. Simulation of Concurrent Games. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2015, vol. 8, no. 2, pp. 43-54.

Valk R. Concurrency in Communicating Object Petri Nets. Concurrent Object-Oriented Programming and Petri Nets, 2001,

pp. 164-195.

Larkin E.V., Ivutin A.N., Kotov V.V., Privalov A.N. Simulation of Relay-Races. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2016, vol. 9, no. 4, pp. 117-128.

Larkin E.V., Ivutin A.N. Estimation of Latency in Embedded Real-Time Systems. 3-rd Meditteranean Conference on Embedded Computing (MECO-2014). Budva, Montenegro, 2014, pp. 236-239.

Korolyuk V., Swishchuk A. Semi-Markov Random Evolutions. N.Y., Springer-Science and Buseness Media, 1995. DOI: 10.1007/978-94-011-1010-5

Iverson M.A., Ozguner F., Follen G.J. Run-Time Statistical Estimation of Task Execution Times for Heterogeneous Distributed Computing. Proceedings of 5th IEEE International Symposium on High Performance Distributed Computing, N.Y., USA, August

-9, 1996. N.Y., Institute of Electrical and Electronics Engineers, 1996, pp. 263-270. DOI: 10.1109/HPDC.1996.546196

Limnios N., Swishchuk A. Discrete-Time Semi-Markov Random Evolutions and Their Applications. Advances in Applied Probability, 2013, vol. 45, no. 1, pp. 214-240. DOI: 10.1239/aap/1363354109

Markov A.A. Extension of the Law of Large Numbers to Dependent Quantities. Izvestiya fiziko-matematicheskogo obshchestva pri Imperatorskom kazanskom universitete, 1906, vol. 15, pp. 135-156. (in Russian)

Bielecki T.R., Jakubowski J., Nieweg lowski M. Conditional Markov Chains: Properties, Construction and Structured Dependence. Stochastic Processes and Their Applications, 2017, vol. 127, no. 4, pp. 1125-1170.

Janssen J., Manca R. Applied Semi-Markov Processes. N.Y., Springer, 2005.

Larkin E.V., Ivutin A.N., Kotov V.V., Privalov A.N. Semi-Markov Modeling of Command Execution by Mobile Robots. Interactive Collaborative Robotics (ICR 2016) Budapest, Hungary, Lecture Notes in Artical Intelligence. Subseries of Lecture Notes in Computer

Science. N.Y., Springer, 2016, pp. 189-198.

Bauer H. Probability Theory. Berlin, N.Y., Walter de Gruyter, 1996.

DOI: 10.1515/9783110814668

Shiryaev A.N. Probability. N.Y., Springer Science and Business Midia, 1996.

Bellman R.E. Dynamic Programming. N.Y., Dover Publications, 2003. DOI: 10.1007/978-1-4757-2539-1

Myerson R.B. Game Theory. Cambridge, Harvard University Press, 1997.

Goetz B., Peierls T. Java Concurrency in Practice, Boston, Addison Wesley, 2006