The Most Probable Path Derivation for Quasi-Birth–Death Processes by Using Symbolic Control

Öz

In this study, we utilize the control theory of discrete event systems to compute the most likely paths in quasi-birth-death processes through hidden Markov models. We begin by discussing how quasi-birth-death processes can be framed as a control problem within the context of discrete event systems. Following this, we encode quasi-birth-death processes as a controller synthesis problem, explaining how to apply safety and optimization algorithms enables the controller to select the best paths. We validate our proposed method through several case studies and report its superior performance compared to various state-of-the-art techniques found in the literature.

Anahtar Kelimeler

• Discrete Event Systems
• Discrete Controller Synthesis
• Quasi-Birth–Death Processes
• Hidden Markov Models
• Maximum Likelihood Estimation
• Optimization Algorithm

Sembolik Kontrol Kullanarak Quasi-Doğum-Ölüm Süreçleri İçin En Olası Yol Hesaplaması

Öz

Bu çalışmada, gizli Markov modelleri aracılığıyla quasi-doğum-ölüm süreçlerinde en olası yolları hesaplamak için ayrık olay sistemlerinin kontrol teorisini kullanıyoruz. İlk olarak, quasi-doğum-ölüm süreçlerinin, ayrık olay sistemleri ağlamında bir kontrol problemi olarak nasıl çerçevelenebileceğini ele alıyoruz. Ardından, quasi-doğum-ölüm süreçlerini bir kontrol sentez problemi olarak kodluyoruz. Güvenlik ve optimizasyon algoritmalarının uygulanması ile elde edilen denetleyicinin en iyi yolları nasıl seçmesini sağladığını açıklıyoruz. Önerilen yöntemi vaka çalışmaları ile doğruluyoruz ve sunduğumuz yaklaşımın literatürde kullanılan yöntemlere kıyasla üstün performans sağladığını gösteriyoruz.

Anahtar Kelimeler

• Ayrık Olay Sistemleri
• Ayrık Denetleyici Sentezi
• Quasi-Doğum-Ölüm Süreçleri
• Gizli Markov Modelleri
• Maksimum Olasılık Tahmini
• Optimizasyon Algoritması

Kaynakça

1. Antoniotti M., Mishra B. Discrete event models + temporal logic = supervisory controller: Automatic synthesis of locomotion controllers. In Proceedings of 1995 IEEE International Conference on Robotics and Automation 1995; 2: 1441-1446.
2. Asarin E., Maler O., Pnueli A., Sifakis J. Controller synthesis for timed automata. IFAC Proceedings Volumes 1998; 31(18): 447-452.
3. Bean N., Latouche G., Taylor P. Physical interpretations for quasi-birth-and-death process algorithms. Queueing Models and Service Management 2018; 1(2): 59-78.
4. Bean NG., Nielsen BF. Quasi-birth-and-death processes with rational arrival process components. Stochastic Models 2010; 26(3): 309-334.
5. Berthier N., Marchand H. Discrete controller synthesis for infinite state systems with reax. IFAC Proceedings Volumes 2014; 47(2): 46-53.
6. Bonafonte CA., Ros MX., Marino JB. An efficient algorithm to find the best state sequence in hsmm. In Eurospeech 1993: 3rd European Conference on Speech Communication and Technology 1993; 22-25.
7. Brejova B., Brown DG., Vinar T. The most probable annotation problem in hmms and its application to bioinformatics. Journal of Computer and System Sciences 2007; 73(7): 1060-1077.
8. Chen YL., Lin F. Safety control of discrete event systems using finite state machines with parameters. In Proceedings of the 2001 American Control Conference 2001; 2: 975-980.

9. Çaşka S. The performance of symbolic limited optimal discrete controller synthesis in the control and path planning of the quadcopter. Applied Sciences 2024; 14(16): 1-27.
10. Cawley SL., Pachter L. Hmm sampling and applications to gene finding and alternative splicing. Bioinformatics 2003; 19(2): 36-41.
11. Elhafsi EH., Molle M. On the solution to qbd processes with finite state space. Stochastic Analysis and Applications 2007; 25(4): 763-779.
12. Etessami K., Wojtczak D., Yannakakis M. Quasi-birth–death processes, tree-like qbds, probabilistic 1-counter automata, and pushdown systems. Performance Evaluation 2010; 67(9): 837-857.
13. Koller H., Widhalm P., Dragaschnig M., Graser A. Fast hidden markov model map-matching for sparse and noisy trajectories. In 2015 IEEE 18th International Conference on Intelligent Transportation Systems 2015; 2557-2561.
14. Latouche G., Ramaswami V. Introduction to matrix analytic methods in stochastic modeling. SIAM 1999; 45-78.
15. Luo J., Zhou M. Petri-net controller synthesis for partially controllable and observable discrete event systems. IEEE Transactions on Automatic Control 2016; 62(3): 1301-1313.
16. Marchand H., Bournai P., Le Borgne M., Le Guernic P. Synthesis of discrete-event controllers based on the signal environment. Discrete Event Dynamic System: Theory and Applications 2000; 10(4): 325-346.
17. Oura R., Ushio T., Sakakibara A. Bounded synthesis and reinforcement learning of supervisors for stochastic discrete event systems with ltl specifications. IEEE Transactions on Automatic Control 2024; 69(10): 6668-6683.
18. Özbaltan M. Hidden abstract stack markov models with learning process. Mathematics 2024; 12(13): 1-19.
19. Özbaltan M., Berthier N. Power-aware scheduling of data-flow hardware circuits with symbolic control. Archives of Control Sciences 2021; 31(2): 431-446.
20. Özbaltan M., Çaşka S. Incorporating symbolic discrete controller synthesis into a virtual robot experimental platform: An implementation with collaborative unmanned aerial vehicle robots. Drones 2021; 8(5): 1-15.
21. Özbaltan M., Kurucan M. Obtaining the most likely path in stochastic hidden input automata by using limited optimal discrete control. IEEE Access 2024; 12: 14776-14786.
22. Rabiner LR. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 1989; 77(2):257–286.
23. Ramadge PJ., Wonham WM. Supervisory control of a class of discrete event processes. SIAM Journal on Control and Optimization 1987; 25(1): 206-230.
24. Samari B., Akbarzadeh O., Zaker M., Lavaei A. From a single trajectory to safety controller synthesis of discrete-time nonlinear polynomial systems. IEEE Control Systems Letters 2024; 8: 3123-3128.
25. Tayachi Z., Escheikh M., Barkaoui K. Performance evaluation of virtual switch with batch arrival using quasi-birth–death process. In 2019 International Conference on Industrial Engineering and Systems Management 2019; 1-6.
26. Van LJ., Winands E. Quasi-birth-and-death processes with an explicit rate matrix. Stochastic Models 2016; 22(1): 77-98.
27. Viterbi AJ. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory 1967; 13(2): 260–269.
28. Wu JL. Control synthesis for discrete-time nonlinear control systems under state and input constraints. IEEE Transactions on Automatic Control 2024; 69(12): 8418-8432.