计算机科学技术学报 ›› 2022,Vol. 37 ›› Issue (1): 106-127.doi: 10.1007/s11390-021-1484-8

所属专题： Software Systems

• • 上一篇    下一篇

面向自适应系统的马尔可夫决策过程的更新与修复

  

  • 收稿日期:2021-03-31 修回日期:2021-10-10 接受日期:2021-10-19 出版日期:2022-01-28 发布日期:2022-01-28

Meaningful Update and Repair of Markov Decision Processes for Self-Adaptive Systems

Wen-Hua Yang1,2,3 (杨文华), Member, CCF, Min-Xue Pan2 (潘敏学), Member, CCF, Yu Zhou1,2 (周宇), Senior Member, CCF, and Zhi-Qiu Huang1 (黄志球), Senior Member, CCF        

  1. 1College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
    2State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China
    3Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing University, Nanjing 210023, China
  • Received:2021-03-31 Revised:2021-10-10 Accepted:2021-10-19 Online:2022-01-28 Published:2022-01-28
  • Contact: Wen-Hua Yang E-mail:ywh@nuaa.edu.cn
  • About author:Wen-Hua Yang is an assistant professor in the College of Computer Science and Technology at Nanjing University of Aeronautics and Astronautics, Nanjing. He received his Ph.D. degree in computer science and technology from Nanjing University, Nanjing, in 2017. His research interests include software engineering, self-adaptive software systems, and cyber-physical systems.
  • Supported by:
    This work was partially supported by the National Natural Science Foundation of China under Grant Nos.61802179, 61972193 and 61972197, the Fundamental Research Funds for the Central Universities of China under Grant No.NS2021069, and the Natural Science Foundation of Jiangsu Province of China under Grant No.BK20201292.

PDF (PC)

22

补充材料

1

自适应系统能够根据环境的变化调整自身的行为，并作为网构软件被广泛部署。自适应系统被认为是一种可有效应对不断增长的软件系统复杂性的方法，获得了许多研究关注并涵盖了各种应用，例如，自动小车系统和自适应网络系统。研究人员提出了许多构建自适应系统的方法，而其中基于概率模型（如马尔可夫决策过程，MDP）的方法，是最使用最广泛的方法之一。然而，它们中的大多数没有处理自适应系统底层MDP在新环境下已经过时或对给定属性不满足的问题。这导致从这种MDP中生成的策略不能指导自适应系统正确运行并满足目标。在这篇文章中，我们提出了一种系统化的方法，通过探索新的状态和迁移并删除过时的状态和迁移来更新过时的MDP，并通过以更有意义的方式调整其结构来修复不满足属性的MDP，而不是任意地将迁移概率修改为与现实不符的值。实验结果表明，与原始的MDP相比，通过我们的方法更新和修复的MDP在指导自适应系统的正确运行方面更有效。

关键词: 自适应系统, 马尔可夫决策过程, 模型修复

Abstract: Self-adaptive systems are able to adjust their behaviour in response to environmental condition changes and are widely deployed as Internetwares. Considered as a promising way to handle the ever-growing complexity of software systems, they have seen an increasing level of interest and are covering a variety of applications, e.g., autonomous car systems and adaptive network systems. Many approaches for the construction of self-adaptive systems have been developed, and probabilistic models, such as Markov decision processes (MDPs), are one of the favoured. However, the majority of them do not deal with the problems of the underlying MDP being obsolete under new environments or unsatisfactory to the given properties. This results in the generated policies from such MDP failing to guide the self-adaptive system to run correctly and meet goals. In this article, we propose a systematic approach to updating an obsolete MDP by exploring new states and transitions and removing obsolete ones, and repairing an unsatisfactory MDP by adjusting its structure in a more meaningful way rather than arbitrarily changing the transition probabilities to values not in line with reality. Experimental results show that the MDPs updated and repaired by our approach are more competent in guiding the self-adaptive systems' correct running compared with the original ones.

Key words: self-adaptive system, Markov decision process, model repair

[1] Esfahani N, Malek S. Uncertainty in self-adaptive software systems. In Proc. the International Seminar on Software Engineering for Self-Adaptive Systems, October 2010, pp.214-238. DOI: 10.1007/978-3-642-35813-5-9.
[2] Cámara J, Schmerl B, Moreno G A, Garlan D. MOSAICO: Offline synthesis of adaptation strategy repertoires with flexible trade-offs. Automated Software Engineering, 2018, 25(3): 595--626. DOI: 10.1007/s10515-018-0234-9.
[3] Weyns D, Schmerl B, Grassi V, Malek S, Mirandola R, Prehofer C, Wuttke J, Andersson J, Giese H, Göschka K M. On patterns for decentralized control in self-adaptive systems. In Lecture Notes in Computer Science 7475, de Lemos R, Giese H, Wüller M A et al. (eds.), Springer Berlin Heidelberg, 2013, pp.76-107. DOI: 10.1007/978-3-642-35813-5-4.
[4] Krupitzer C, Roth F M, VanSyckel S, Schiele G, Becker C. A survey on engineering approaches for self-adaptive systems. Pervasive Mob. Comput., 2015, 17: 184-206. DOI: 10.1016/j.pmcj.2014.09.009.
[5] Wang Q. Towards a rule model for self-adaptive software. SIGSOFT Softw. Eng. Notes, 2005, 30(1): Article No. 8. DOI: 10.1145/1039174.1039198.
[6] Sama M, Rosenblum D S, Wang Z, Elbaum S. Model-based fault detection in context-aware adaptive applications. In Proc. the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering, November 2008, pp.261-271. DOI: 10.1145/1453101.1453136.
[7] Filieri A, Hoffmann H, Maggio M. Automated design of self-adaptive software with control-theoretical formal guarantees. In Proc. the 36th International Conference on Software Engineering, May 31-June 7, 2014, pp.299-310. DOI: 10.1145/2568225.2568272.
[8] Filieri A, Hoffmann H, Maggio M. Automated multi-objective control for self-adaptive software design. In Proc. the 10th Joint Meeting on Foundations of Software Engineering, August 30-September 4, 2015, pp.13-24. DOI: 10.1145/2786805.2786833.
[9] Shevtsov S, Weyns D. Keep it SIMPLEX: Satisfying multiple goals with guarantees in control-based self-adaptive systems. In Proc. the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, November 2016, pp. 229-241. DOI: 10.1145/2950290.2950301.
[10] Cámara J, De Lemos R. Evaluation of resilience in self-adaptive systems using probabilistic model-checking. In Proc. the 7th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, June 2012, pp.53-62. DOI: 10.1109/SEAMS.2012.6224391.
[11] Franco J M, Correia F, Barbosa R, Zenha-Rela M, Schmerl B, Garlan D. Improving self-adaptation planning through software architecture-based stochastic modeling. J. Syst. Softw., 2016, 115: 42-60. DOI: 10.1016/j.jss.2016.01.026.
[12] Filieri A, Tamburrelli G. Probabilistic verification at runtime for self-adaptive systems. In Assurances for Self-Adaptive Systems: Principles, Models, and Techniques, Cámara J, De Lemos R, Ghezzi C, Lopes A (eds.), Springer, 2013, pp.30-59. DOI: 10.1007/978-3-642-36249-1-2.
[13] Ghezzi C, Pinto L S, Spoletini P, Tamburrelli G. Managing non-functional uncertainty via model-driven adaptivity. In Proc. the 2013 International Conference on Software Engineering, May 2013, pp.33-42. DOI: 10.1109/ICSE.2013.6606549.
[14] Brechtel S, Gindele T, Dillmann R. Probabilistic MDP-behavior planning for cars. In Proc. the 14th International IEEE Conference on Intelligent Transportation Systems, Oct. 2011, pp.1537-1542. DOI: 10.1109/ITSC.2011.6082928.
[15] Kwiatkowska M, Parker D. Automated verification and strategy synthesis for probabilistic systems. In Proc. the 11th International Symposium on Automated Technology for Verification and Analysis, October 2013, pp.5-22. DOI: 10.1007/978-3-319-02444-8-2.
[16] Bartocci E, Grosu R, Katsaros P, Ramakrishnan C R, Smolka S A. Model repair for probabilistic systems. In Proc. the 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, March 26-April 3, 2011, pp.326-340. DOI: 10.1007/978-3-642-19835-9-30.
[17] Chen T, Hahn E M, Han T, Kwiatkowska M, Qu H, Zhang L. Model repair for Markov decision processes. In Proc. the 7th International Symposium on Theoretical Aspects of Software Engineering, July 2013, pp.85-92. DOI: 10.1109/TASE.2013.20.
[18] Kephart J O, Chess D M. The vision of autonomic computing. Computer, 2003, 36(1): 41--50. DOI: 10.1109/MC.2003.1160055.
[19] Sykes D, Corapi D, Magee J, Kramer J, Russo A, Inoue K. Learning revised models for planning in adaptive systems. In Proc. the 2013 International Conference on Software Engineering, May 2013, pp.63-71. DOI: 10.1109/ICSE.2013.6606552.
[20] Cheng B H C, Sawyer P, Bencomo N, Whittle J. A goal-based modeling approach to develop requirements of an adaptive system with environmental uncertainty. In Proc. the 12th International Conference on Model Driven Engineering Languages and Systems, October 2009, pp.468-483. DOI: 10.1007/978-3-642-04425-0-36.
[21] Cámara J, Garlan D, Schmerl B, Pandey A. Optimal planning for architecture-based self-adaptation via model checking of stochastic games. In Proc. the 30th Annual ACM Symposium on Applied Computing, April 2015, pp.428-435. DOI: 10.1145/2695664.2695680.
[22] Moreno G A, Cámara J, Garlan D, Schmerl B. Proactive self-adaptation under uncertainty: A probabilistic model checking approach. In Proc. the 10th Joint Meeting on Foundations of Software Engineering, August 30-September 4, 2015, pp.1-12. DOI: 10.1145/2786805.2786853.
[23] Kwiatkowska M, Norman G, Parker D. PRISM 4.0: Verification of probabilistic real-time systems. In Proc. the 23rd International Conference on Computer Aided Verification, July 2011, pp.585-591. DOI: 10.1007/978-3-642-22110-1-47.
[24] Clarke E M, Emerson E A. Design and synthesis of synchronization skeletons using branching time temporal logic. In Proc. the Workshop on Logics of Programs, May 1981, pp.52-71. DOI: 10.1007/BFb0025774.
[25] Iftikhar M U, Ramachandran G S, Bollansée P, Weyns D, Hughes D. DeltaIoT: A self-adaptive Internet of Things exemplar. In Proc. the 12th IEEE/ACM International Symposium on Software Engineering for Adaptive and Self-Managing Systems, May 2017, pp.76-82. DOI: 10.1109/SEAMS.2017.21.
[26] Puterman M L. Markov Decision Processes: Discrete Stochastic Dynamic Programming (1st edition). John Wiley & Sons, 1994. DOI: 10.1002/9780470316887.
[27] Sama M, Elbaum S, Raimondi F, Rosenblum D S, Wang Z. Context-aware adaptive applications: Fault patterns and their automated identification. IEEE Transactions on Software Engineering, 2010, 36(5): 644-661. DOI: 10.1109/TSE.2010.35.
[28] Yang W, Xu C, Liu Y, Cao C, Ma X, Lu J. Verifying self-adaptive applications suffering uncertainty. In Proc. the 29th ACM/IEEE International Conference on Automated Software Engineering, September 2014, pp.199-210. DOI: 10.1145/2642937.2642999.
[29] Yang W, Xu C, Pan M, Cao C, Ma X, Lu J. Efficient validation of self-adaptive applications by counterexample probability maximization. Journal of Systems and Software, 2018, 138: 82-99. DOI: 10.1016/j.jss.2017.12.009.
[30] Wilcoxon F. Individual comparisons by ranking methods. Biometrics Bulletin, 1945, 1(6): 80-83. DOI: 10.2307/3001968.
[31] Abdi H. The bonferonni and Šidák corrections for multiple comparisons. In Encyclopedia of Measurement and Statistics, Salkind N (ed.), SAGE, 2007, pp.103-107.
[32] Salehie M, Tahvildari L. Self-adaptive software: Landscape and research challenges. ACM Trans. Auton. Adapt. Syst., 2009, 4(2): Article No. 4.
[33] Zhao T. The generation and evolution of adaptation rules in requirements driven self-adaptive systems. In Proc. the 24th IEEE International Requirements Engineering Conference, Sept. 2016, pp.456-461. DOI: 10.1109/RE.2016.18.
[34] Cheng S W, Huang A C, Garlan D, Schmerl B, Steenkiste P. Rainbow: Architecture-based self-adaptation with reusable infrastructure. In Proc. the 1st International Conference on Autonomic Computing, May 2004, pp.276-277. DOI: 10.1109/ICAC.2004.46.
[35] Chen B, Peng X, Liu Y, Song S, Zheng J, Zhao W. Architecture-based behavioral adaptation with generated alternatives and relaxed constraints. IEEE Transactions on Services Computing, 2019, 12(1): 73-87. DOI: 10.1109/TSC.2016.2593459.
[36] Howard R A. Dynamic Programming and Markov Processes (1st edition). The MIT Press, 1960.
[37] Sutton R S, Barto A G. Reinforcement Learning: An Introduction (2nd edition). Bradford Books, 2018.
[38] Calinescu R, Ghezzi C, Kwiatkowska M, Mirandola R. Self-adaptive software needs quantitative verification at runtime. Commun. ACM, 2012, 55(9): 69-77. DOI: 10.1145/2330667.2330686.
[39] Su G, Chen T, Feng Y, Rosenblum D S, Thiagarajan P S. An iterative decision-making scheme for Markov decision processes and its application to self-adaptive systems. In Proc. the 19th International Conference on Fundamental Approaches to Software Engineering, April 2016, pp.269-286. DOI: 10.1007/978-3-662-49665-7-16.
[40] Filieri A, Grunske L, Leva A. Lightweight adaptive filtering for efficient learning and updating of probabilistic models. In Proc. the 37th International Conference on Software Engineering, May 2015, pp.200-211. DOI: 10.1109/ICSE.2015.41.
[41] Nahabedian L, Braberman V, D'Ippolito N, Honiden S, Kramer J, Tei K, Uchitel S. Dynamic update of discrete event controllers. IEEE Transactions on Software Engineering, 2018, 46(11): 1220-1240. DOI: 10.1109/TSE.2018.2876843.
[42] Ghezzi C, Greenyer J, Manna V P L. Synthesizing dynamically updating controllers from changes in scenario-based specifications. In Proc. the 7th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, June 2012, pp.145-154. DOI: 10.1109/SEAMS.2012.6224401.
[43] Hahn E M, Han T, Zhang L. Synthesis for PCTL in parametric Markov decision processes. In Proc. the 3rd International Symposium on NASA Formal Methods, April 2011, pp.146-161. DOI: 10.1007/978-3-642-20398-5-12.
[44] Cubuktepe M, Jansen N, Junges S, Katoen J P, Papusha I, Poonawala H A, Topcu U. Sequential convex programming for the efficient verification of parametric MDPs. In Proc. the 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, April 2017, pp.133-150. DOI: 10.1007/978-3-662-54580-5-8.
[45] Arming S, Bartocci E, Sokolova A. SEA-PARAM: Exploring schedulers in parametric MDPs. In Proc. the 15th Workshop on Quantitative Aspects of Programming Languages and Systems, April 2017, pp.25-38. DOI: 10.4204/EPTCS.250.3.
[46] Pathak S, ábrahám E, Jansen N, Tacchella A, Katoen J P. A greedy approach for the efficient repair of stochastic models. In Proc. the 7th International Symposium on NASA Formal Methods, April 2015, pp.295-309. DOI: 10.1007/978-3-319-17524-9-21.
[47] Chatzieleftheriou G, Katsaros P. Abstract model repair for probabilistic systems. Information and Computation, 2018, 259: 142-160. DOI: 10.1016/j.ic.2018.02.019.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 周笛;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[3] 郑国梁; 李辉;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[4] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[5] 乔香珍;. An Efficient Parallel Algorithm for FFT[J]. , 1987, 2(3): 174 -190 .
[6] 段平; 蔡希尧;. A Real-Time Interprocessor Synchronization Algorithm for Communication in Distributed Computer Systems[J]. , 1987, 2(4): 292 -302 .
[7] 陈其明;. Extending the Object-Oriented Paradigm for Supporting Complex Objects[J]. , 1988, 3(2): 113 -130 .
[8] 范植华;. Vectorization for Loops with Three-Forked Jumps[J]. , 1988, 3(3): 186 -202 .
[9] 罗银芳;. Algorithm and Implementation of Parallel Multiplication in a Mixed Number System[J]. , 1988, 3(3): 203 -213 .
[10] 王能斌; 刘小青; 刘光富;. A Software Tool for Constructing Traditional Chinese Medical Expert Systems[J]. , 1988, 3(3): 214 -220 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：