Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Template Decision Diagrams for Meta Control and Explainability

  • Conference paper
  • First Online:
Explainable Artificial Intelligence (xAI 2024)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 2154))

Included in the following conference series:

  • 506 Accesses

Abstract

Decision tree classifiers (DTs) provide an effective machine-learning model, well-known for its intuitive interpretability. However, they still miss opportunities well-established in software engineering that could further improve their explainability: separation of concerns, encapsulation, and reuse of behaviors. To enable these concepts, we introduce templates in decision diagrams (DDs) as an extension of multi-valued DDs. Templates allow to encapsulate and reuse common decision-making patterns. By a case study from the autonomous underwater robotics domain we illustrate the benefits of template DDs for modeling and explaining meta controllers, i.e., hierarchical control structures with underspecified entities. Further, we implement a template-generating refactoring method for DTs. Our evaluation on standard controller benchmarks shows that template DDs can improve explainability of controller DTs by reducing their sizes by more than one order of magnitude.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://anonymous.4open.science/r/tdd-97EC.

References

  1. Ethics guidelines for trustworthy AI - European commission, directorate-general for communications networks, content and technology (2019). https://data.europa.eu/doi/10.2759/177365

  2. Four principles of explainable artificial intelligence - (U.S.) national institute of standards and technology (NIST) (2020). https://doi.org/10.6028/NIST.IR.8312-draft

  3. Proposal for a regulation laying down harmonised rules on artificial intelligence (artificial intelligence act) and amending certain union legislative acts, com(2021) 206 final - European commission (2021). https://ec.europa.eu/transparency/regdoc/rep/1/2021/EN/COM-2021-206-F1-EN-MAIN-PART-1.PDF

  4. Anand, A., Nayak, S.P., Schmuck, A.K.: Synthesizing permissive winning strategy templates for parity games. In: Enea, C., Lal, A. (eds.) CAV 2023. LNCS, vol. 13694, pp. 436–458. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-37706-8_22

    Chapter  Google Scholar 

  5. Ashok, P., Jackermeier, M., Křetínský, J., Weinhuber, C., Weininger, M., Yadav, M.: dtControl 2.0: explainable strategy representation via decision tree learning steered by experts. In: Groote, J.F., Larsen, K.G. (eds.) TACAS 2021. LNCS, vol. 12652, pp. 326–345. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-72013-1_17

    Chapter  Google Scholar 

  6. Audemard, G., Bellart, S., Bounia, L., Koriche, F., Lagniez, J.M., Marquis, P.: On the explanatory power of boolean decision trees. Data Knowl. Eng. 142, 102088 (2022). https://doi.org/10.1016/j.datak.2022.102088

    Article  Google Scholar 

  7. Bagnell, J.A., et al.: An integrated system for autonomous robotics manipulation. In: 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2012, Vilamoura, Algarve, Portugal, 7–12 October 2012, pp. 2955–2962. IEEE (2012https://doi.org/10.1109/IROS.2012.6385888

  8. Baier, C., Dubslaff, C., Funke, F., Jantsch, S., Majumdar, R., Piribauer, J., Ziemek, R.: From verification to causality-based explications. In: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP) (2021)

    Google Scholar 

  9. Baier, C., Dubslaff, C., Wienhöft, P., Kiebel, S.J.: Strategy synthesis in Markov decision processes under limited sampling access. In: Rozier, K.Y., Chaudhuri, S. (eds.) NFM 2023. LNCS, vol. 13903, pp. 86–103. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-33170-1_6

    Chapter  Google Scholar 

  10. Blumreiter, M., et al.: Towards self-explainable cyber-physical systems. In: 22nd ACM/IEEE International Conference on Model Driven Engineering Languages and Systems Companion (MODELS-C), pp. 543–548 (2019)

    Google Scholar 

  11. Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and Regression Trees. Wadsworth (1984)

    Google Scholar 

  12. Bryant, R.E.: Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. 24(3), 293–318 (1992). https://doi.org/10.1145/136035.136043

    Article  MathSciNet  Google Scholar 

  13. Camilli, M., Mirandola, R., Scandurra, P.: XSA: explainable self-adaptation. In: Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering, pp. 1–5 (2022)

    Google Scholar 

  14. Chaki, S., Gurfinkel, A., Strichman, O.: Decision diagrams for linear arithmetic. In: 2009 Formal Methods in Computer-Aided Design, pp. 53–60 (2009). https://doi.org/10.1109/FMCAD.2009.5351143

  15. Chen, B., Peng, X., Yu, Y., Nuseibeh, B., Zhao, W.: Self-adaptation through incremental generative model transformations at runtime. In: Jalote, P., Briand, L.C., van der Hoek, A. (eds.) 36th International Conference on Software Engineering, ICSE ’14, Hyderabad, India, 31 May–07 June 2014, pp. 676–687. ACM (2014). https://doi.org/10.1145/2568225.2568310

  16. Cheng, S., Garlan, D.: Stitch: a language for architecture-based self-adaptation. J. Syst. Softw. 85(12), 2860–2875 (2012). https://doi.org/10.1016/J.JSS.2012.02.060

    Article  Google Scholar 

  17. Chrszon, P., Baier, C., Dubslaff, C., Klüppelholz, S.: Interaction detection in configurable systems - a formal approach featuring roles. J. Syst. Softw. 196, 111556 (2023)

    Article  Google Scholar 

  18. Chrszon, P., Dubslaff, C., Klüppelholz, S., Baier, C.: Profeat: feature-oriented engineering for family-based probabilistic model checking. Formal Aspects Comput. 30(1), 45–75 (2018)

    Article  MathSciNet  Google Scholar 

  19. Cioara, T., Anghel, I., Salomie, I., Dinsoreanu, M., Copil, G., Moldovan, D.: A self-adapting algorithm for context aware systems. In: 9th RoEduNet IEEE International Conference, pp. 374–379 (2010)

    Google Scholar 

  20. Colledanchise, M., Ögren, P.: Behavior trees in robotics and AI: an introduction. CoRR arxiv:1709.00084 (2017)

  21. Dijkstra, E.W.: On the role of scientific thought. In: Selected Writings on Computing: A Personal Perspective, pp. 60–66. Springer, Berlin (1982). https://doi.org/10.1007/978-1-4612-5695-3_12

  22. Drechsler, R., Lüth, C., Fey, G., Güneysu, T.: Towards self-explaining digital systems: a design methodology for the next generation. In: 3rd International Verification and Security Workshop (IVSW), pp. 1–6. IEEE (2018). https://doi.org/10.1109/IVSW.2018.8494900

  23. Dubslaff, C., Weis, K., Baier, C., Apel, S.: Feature causality. J. Syst. Softw. 209, 111915 (2024). https://doi.org/10.1016/j.jss.2023.111915

    Article  Google Scholar 

  24. Fey, G., Fränzle, M., Drechsler, R.: Self-explanation in systems of systems. In: 2022 IEEE 30th International Requirements Engineering Conference Workshops (REW), pp. 85–91. IEEE (2022)

    Google Scholar 

  25. Fowler, M.: Refactoring: Improving the Design of Existing Code. Addison-Wesley, Boston (1999)

    Google Scholar 

  26. Fujita, M., McGeer, P.C., Yang, J.C.: Multi-terminal binary decision diagrams: an efficient data structure for matrix representation. Formal Methods Syst. Des. 10(2/3), 149–169 (1997)

    Article  Google Scholar 

  27. Garg, P., Neider, D., Madhusudan, P., Roth, D.: Learning invariants using decision trees and implication counterexamples. In: POPL, pp. 499–512. ACM (2016)

    Google Scholar 

  28. Good, I.J.: Explicativity: a mathematical theory of explanation with statistical applications. Proc. R. Soc. Lond. A354, 303–330 (1977)

    MathSciNet  Google Scholar 

  29. Harder, H., Jantsch, S., Baier, C., Dubslaff, C.: A unifying formal approach to importance values in Boolean functions. In: Elkind, E. (ed.) Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pp. 2728–2737. International Joint Conferences on Artificial Intelligence Organization (2023). https://doi.org/10.24963/ijcai.2023/304

  30. Hezavehi, S.M., Weyns, D., Avgeriou, P., Calinescu, R., Mirandola, R., Perez-Palacin, D.: Uncertainty in self-adaptive systems: a research community perspective. ACM Trans. Auton. Adapt. Syst. 15(4) (2021). https://doi.org/10.1145/3487921

  31. Horváth, I., Tavčar, J.: Designing cyber-physical systems for runtime self-adaptation: knowing more about what we miss... J. Integr. Des. Process Sci. 25(2), 1–26 (2021).https://doi.org/10.3233/JID210030

  32. Husung, N., Dubslaff, C., Hermanns, H., Köhl, M.A.: OxiDD: a safe, concurrent, modular, and performant decision diagram framework in rust. In: Finkbeiner, B., Kovács, L. (eds.) TACAS 202. LNCS, vol. 14572, pp. 255–275. Springer, Cham (2024)

    Chapter  Google Scholar 

  33. Iovino, M., Scukins, E., Styrud, J., Ögren, P., Smith, C.: A survey of behavior trees in robotics and AI. Rob. Auton. Syst. 154, 104096 (2022). https://doi.org/10.1016/J.ROBOT.2022.104096

    Article  Google Scholar 

  34. Jung, G., Joshi, K.R., Hiltunen, M.A., Schlichting, R.D., Pu, C.: Generating adaptation policies for multi-tier applications in consolidated server environments. In: 2008 International Conference on Autonomic Computing, pp. 23–32 (2008). https://doi.org/10.1109/ICAC.2008.21

  35. Kephart, J.O., Chess, D.M.: The vision of autonomic computing. IEEE Comput. 36(1), 41–50 (2003). https://doi.org/10.1109/MC.2003.1160055

    Article  Google Scholar 

  36. Klös, V., Göthel, T., Glesner, S.: Comprehensible and dependable self-learning self-adaptive systems. J. Syst. Arch. 85, 28–42 (2018)

    Article  Google Scholar 

  37. Kohita, R., Wachi, A., Kimura, D., Chaudhury, S., Tatsubori, M., Munawar, A.: Language-based general action template for reinforcement learning agents. In: Zong, C., Xia, F., Li, W., Navigli, R. (eds.) Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pp. 2125–2139. Association for Computational Linguistics (2021). https://doi.org/10.18653/v1/2021.findings-acl.187

  38. Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 585–591. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22110-1_47

    Chapter  Google Scholar 

  39. Li, N., Adepu, S., Kang, E., Garlan, D.: Explanations for human-on-the-loop: a probabilistic model checking approach. In: Proceedings of the IEEE/ACM 15th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, pp. 181–187 (2020)

    Google Scholar 

  40. Lim, B.Y., Dey, A.K., Avrahami, D.: Why and why not explanations improve the intelligibility of context-aware intelligent systems. In: SIGCHI Conference on Human Factors in Computing Systems, pp. 2119–2128 (2009). https://doi.org/10.1145/1518701.1519023

  41. Little, I., Thiébaux, S.: Probabilistic planning vs replanning. In: Proceedings of ICAPS Workshop on IPC: Past, Present and Future (2007)

    Google Scholar 

  42. Mayr, M., Chatzilygeroudis, K., Ahmad, F., Nardi, L., Krueger, V.: Learning of parameters in behavior trees for movement skills. In: 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 7572–7579 (2021). https://doi.org/10.1109/IROS51168.2021.9636292

  43. McCabe, T.J.: A complexity measure. IEEE Trans. Softw. Eng. 4, 308–320 (1976)

    Article  MathSciNet  Google Scholar 

  44. McMillan, K.L.: Symbolic Model Checking. Springer, Boston (1993). https://doi.org/10.1007/978-1-4615-3190-6_3

  45. Minato, S.I.: Binary Decision Diagrams and Applications for VLSI CAD. Kluwer Academic Publishers, Boston (1996)

    Google Scholar 

  46. Mitchell, T.M.: Machine learning. McGraw Hill series in computer science. McGraw-Hill (1997)

    Google Scholar 

  47. Ouedraogo, L., Kumar, R., Malik, R., Akesson, K.: Nonblocking and safe control of discrete-event systems modeled as extended finite automata. IEEE Trans. Autom. Sci. Eng. 8(3), 560–569 (2011). https://doi.org/10.1109/TASE.2011.2124457

    Article  Google Scholar 

  48. Padalkar, A., et al.: Guiding reinforcement learning with shared control templates. In: 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 11531–11537 (2023). https://doi.org/10.1109/ICRA48891.2023.10161058

  49. Päßler, J., ter Beek, M.H., Damiani, F., Tapia Tarifa, S.L., Johnsen, E.B.: Formal modelling and analysis of a self-adaptive robotic system. In: Herber, P., Wijs, A. (eds.) Proceedings of the 18th International Conference on integrated Formal Methods (iFM 2023), LNCS, vol. 14300, pp. 343–363. Springer (2023). https://doi.org/10.1007/978-3-031-47705-8_18

  50. Plambeck, S., Fey, G., Schyga, J., Hinckeldeyn, J., Kreutzfeldt, J.: Explaining cyber-physical systems using decision trees. In: 2022 2nd International Workshop on Computation-Aware Algorithmic Design for Cyber-Physical Systems (CAADCPS), pp. 3–8 (2022). https://doi.org/10.1109/CAADCPS56132.2022.00006

  51. Quinlan, J.R.: Induction of decision trees. Mach. Learn. 1(1), 81–106 (1986)

    Article  Google Scholar 

  52. Rezende Silva, G., et al.: SUAVE: an exemplar for self-adaptive underwater vehicles. In: Proceedings of the 18th International Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS 2023), pp. 181–187. IEEE (2023). https://doi.org/10.1109/SEAMS59076.2023.00031

  53. Rodrigues, A., Caldas, R.D., Rodrigues, G.N., Vogel, T., Pelliccione, P.: A learning approach to enhance assurances for real-time self-adaptive systems. In: Andersson, J., Weyns, D. (eds.) Proceedings of the 13th International Conference on Software Engineering for Adaptive and Self-Managing Systems, SEAMS@ICSE 2018, Gothenburg, Sweden, 28–29 May 2018, pp. 206–216. ACM (2018). https://doi.org/10.1145/3194133.3194147

  54. Salehie, M., Tahvildari, L.: Self-adaptive software: landscape and research challenges. ACM Trans. Auton. Adapt. Syst. 4(2), 14:1–14:42 (2009). https://doi.org/10.1145/1516533.1516538

  55. Schwammberger, M., Klös, V.: From specification models to explanation models: an extraction and refinement process for timed automata. Electron. Proc. Theor. Comput. Sci. 371, 20–37 (2022). https://doi.org/10.4204/eptcs.371.2

    Article  Google Scholar 

  56. Shoulson, A., Garcia, F.M., Jones, M., Mead, R., Badler, N.I.: Parameterizing behavior trees. In: Allbeck, J.M., Faloutsos, P. (eds.) MIG 2011. LNCS, vol. 7060, pp. 144–155. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25090-3_13

    Chapter  Google Scholar 

  57. Sistla, M.A., Chaudhuri, S., Reps, T.: Cflobdds: context-free-language ordered binary decision diagrams. ACM Trans. Program. Lang. Syst. (2024). https://doi.org/10.1145/3651157

  58. Srinivasan, A., Ham, T., Malik, S., Brayton, R.: Algorithms for discrete function manipulation. In: 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers, pp. 92–95 (1990). https://doi.org/10.1109/ICCAD.1990.129849

  59. Sun, Y., Yin, X., Huang, F.: Temple: learning template of transitions for sample efficient multi-task RL. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 9765–9773 (2021)

    Google Scholar 

  60. Union, E.: On the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46/ec (general data protection regulation). In: Regulation (EU) 2016/679 of the European Parliament And of the Council. vol. Article 13(2)(f) (2016)

    Google Scholar 

  61. Watson, A., Wallace, D., McCabe, T., Associates, M.., of Standards, N.I., (U.S.), T.: Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric. No. v. 13 in NIST special publication, U.S. Department of Commerce, Technology Administration, National Institute of Standards and Technology (1996)

    Google Scholar 

  62. Weyns, D.: An Introduction to Self-Adaptive Systems: A Contemporary Software Engineering Perspective. John Wiley & Sons, Hoboken (2020)

    Google Scholar 

  63. Zapreev, I.S., Verdier, C., Mazo, M.: Optimal symbolic controllers determinization for BDD storage. IFAC-PapersOnLine 51(16), 1–6 (2018). https://doi.org/10.1016/j.ifacol.2018.08.001

    Article  Google Scholar 

  64. Zuse, H.: Software Complexity: Measures and Methods. Programming complex systems, W. de Gruyter (1991)

    Google Scholar 

Download references

Acknowledgments

This work was partially supported by the DFG under the projects EXC 2050/1 (CeTI, project ID 390696704, as part of Germany’s Excellence Strategy) and TRR 248 (see https://perspicuous-computing.science, project ID 389792660), by the NWO through Veni grant VI.Veni.222.431, and by the European Union’s Horizon 2020 Framework Programme through the MSCA network REMARO (Grant Agreement No 956200). Authors in alphabetic order.

Author information

Authors and Affiliations

  1. Eindhoven University of Technology, Eindhoven, The Netherlands

    Clemens Dubslaff

  2. Centre for Tactile Internet with Human-in-the-Loop (CeTI), Dresden, Germany

    Clemens Dubslaff & Verena Klös

  3. University of Oslo, Oslo, Norway

    Juliane Päßler

Authors
  1. Clemens Dubslaff
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Verena Klös
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Juliane Päßler
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Clemens Dubslaff , Verena Klös or Juliane Päßler .

Editor information

Editors and Affiliations

  1. Technological University Dublin, Dublin, Ireland

    Luca Longo

  2. Fraunhofer Institute for Telecommunications, Berlin, Germany

    Sebastian Lapuschkin

  3. University of Marburg, Marburg, Germany

    Christin Seifert

Ethics declarations

Disclosure of Interests

The authors have no competing interests to declare that are relevant to the content of this article.

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Dubslaff, C., Klös, V., Päßler, J. (2024). Template Decision Diagrams for Meta Control and Explainability. In: Longo, L., Lapuschkin, S., Seifert, C. (eds) Explainable Artificial Intelligence. xAI 2024. Communications in Computer and Information Science, vol 2154. Springer, Cham. https://doi.org/10.1007/978-3-031-63797-1_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-63797-1_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-63796-4

  • Online ISBN: 978-3-031-63797-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation