Relay Races Along a Pair of Selectable Routes

Case of two teams competition, which should overcome the distance divided onto stages, is considered. In the case under consideration, every stage has its own number of routes, which the participants of the team may select to overcome. It is shown, that competition bears the character of the relay race, and two-parallel semi-Markov process is the natural approach to modelling of the situation.
From all possible routes two were selected. The conception of switching space, which display all possible switching trajectories is proposed. The formula for calculation of switching trajectories number is acquired. It is shown, that ordinary semi-Markov process with the use of the recursive procedure may be obtained from the complex two-parallel semi-Markov process, which describes the wandering through selected routes. The formulae for realization of the recursion are proposed.
Conception of distributed forfeit is proposed. It is shown, that forfeit depends on difference of stages, teams overcome at current time, and routes, on which participants solved to overcome stage. The formula for estimation of total forfeit, which one team pays to other team is obtained. It is shown, that the sum of forfeit may be used as the optimization criterion in the game strategy optimization task.

Keywords

relay race; two-parallel semi-Markov process; distance; stage; route; distributed forfeit; recursive procedure.

References

1. Heymann M. Concurrency and Discrete Event Control. IEEE Control Systems Magazine, 1990, vol. 10, pp. 103-112. DOI: 10.1109/37.56284
2. Chatterjee K., Jurdzi'nski 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
3. 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.
4. Valk R. Concurrency in Communicating Object Petri Nets. Concurrent Object-Oriented Programming and Petri Nets, 2001, pp. 164-195.
5. 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.
6. 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.
7. Korolyuk V., Swishchuk A. Semi-Markov Random Evolutions. N.Y., Springer-Science and Buseness Media, 1995. DOI: 10.1007/978-94-011-1010-5
8. 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 6-9, 1996. N.Y., Institute of Electrical and Electronics Engineers, 1996, pp. 263-270. DOI: 10.1109/HPDC.1996.546196
9. 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
10. 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)
11. Bielecki T.R., Jakubowski J., Niewkeglowski M. Conditional Markov Chains: Properties, Construction and Structured Dependence. Stochastic Processes and Their Applications, 2017, vol. 127, no. 4, pp. 1125-1170. DOI: 10.1016/j.spa.2016.07.010
12. Janssen J., Manca R. Applied Semi-Markov Processes. N.Y., Springer, 2005.
13. 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 Artifical Intelligence. Subseries of Lecture Notes in Computer Science. N.Y., Springer, 2016, pp. 189-198.
14. Bauer H. Probability Theory. Berlin, N.Y., Walter de Gruyter, 1996. DOI: 10.1515/9783110814668
15. Shiryaev A.N. Probability. N.Y., Springer Science and Business Midia, 1996.
16. Bellman R.E. Dynamic Programming. N.Y., Dover Publications, 2003. DOI: 10.1007/978-1-4757-2539-1
17. Myerson R.B. Game Theory. Cambridge, Harvard University Press, 1997.
18. Goetz B., Peierls T. Java Concurrency in Practice, Boston, Addison Wesley, 2006.