Predicate Decision Diagrams for Explainable Policy Representation

This study introduces Predicate Decision Diagrams for Explainable Policy Representation, showcasing a structured approach for efficient policy modeling in complex systems. The diagrams illustrate a methodical way to represent policies through decision trees, aiding in transparent decision-making processes and policy explanation. Addressing the challenges of policy complexity, the diagrams offer a systematic framework for clear and interpretable policy design.

• Policy Representation
• Decision Diagrams
• Explainable Systems
• Complex Systems
• Decision Trees

orso_h Follow

Uploaded on Mar 03, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Predicate Decision Diagrams for Explainable Policy Representation Debraj Chakraborty [1] Clemens Dubslaff[2] Sudeep Kanav[1] Jan K et nsk [1] Christoph Weinhuber[3] [1] Masaryk University, Brno, Czechia [2] Eindhoven University of Technology, Netherlands [3] Technical University of Munich, Germany LiVe 2024 @ ETAPS

2. Running Example 2

3. Controller Action State System Controller 2

4. Controller x 0 1 2 3 4 5 6 7 8 9 Action , , , , 0 { , , } 1 2 3 4 y 5 6 7 State (x,y) 8 9 System Controller 2

5. Controller Policy x 0 1 2 3 4 5 6 7 8 9 Action , , , , 0 { , , } 1 2 3 4 y 5 6 7 State (x,y) 8 9 System Controller 2

6. Controller Policy x Controller Policy Controller Policy : States Actions 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 y 5 6 7 8 9 System 2

7. Policy Table x Controller Policy Controller Policy : States Actions 0 1 2 3 4 5 6 7 8 9 0 x y action 1 1 1 2 3 1 2 4 y 5 5 1 6 5 2 7 5 3 8 9 System 2

8. Policy Table x Controller Policy Controller Policy : States Actions 0 1 2 3 4 5 6 7 8 9 0 x y action 1 1 1 2 3 1 2 4 y 5 5 1 6 5 2 7 5 3 8 9 Too big unexplainable System 2

9. Decision Tree (DT) Decision tree Decision tree Policy Table Policy Table x y action x > 1 1 1 1 2 x > 7 y > 5 5 1 y > 5 y > 5 5 2 5 3 3

10. Decision Tree (DT) x > 1 Split the state-space based on some predicate 3

11. Decision Tree (DT) x > 1 Split the state-space based on some predicate Recursively create subtrees to represent the sub-policies x > 7 y > 5 y > 5 3

12. Decision Tree (DT) x > 1 Split the state-space based on some predicate Recursively create subtrees to represent the sub-policies x > 7 y > 5 y > 5 y > 5 3

13. Decision Tree (DT) x > 1 Split the state-space based on some predicate Recursively create subtrees to represent the sub-policies Splitting rule Splitting rule: optimize impurity measures (entropy, Gini index ) x > 7 y > 5 Classes of predicates Classes of predicates: Axis aligned : x > c y > 5 y > 5 Linear : ax + by + c > 0 Other algebraic predicates 3

14. Decision Tree (DT) x > 1 Split the state-space based on some predicate Recursively create subtrees to represent the sub-policies Splitting rule Splitting rule: optimize impurity measures (entropy, Gini index ) x > 7 y > 5 Classes of predicates Classes of predicates: Axis aligned : x > c y > 5 y > 5 Linear : ax + by + c > 0 Other algebraic/ categorical predicates Small Explainable 3

15. Decision Tree (DT) x > 1 Split the state-space based on some predicate Recursively create subtrees to represent the sub-policies Splitting rule Splitting rule: optimize impurity measures (entropy, Gini index ) x > 7 y > 5 Classes of predicates Classes of predicates: Axis aligned : x > c y > 5 y > 5 Linear : ax + by + c > 0 Other algebraic/ categorical predicates Small Explainable Redundant 3

16. Multi-Terminal Binary Decision Diagram (MTBDD) x0 Boolean variables in decision nodes Actions in the terminal nodes Ordered Ordered: strict variable ordering x1 x1 Reduced Reduced: merging isomorphic subgraphs x2 x2 4

17. Multi-Terminal Binary Decision Diagram (MTBDD) x0 Boolean variables in decision nodes Actions in the terminal nodes Ordered Ordered: strict variable ordering x1 x1 Reduced Reduced: merging isomorphic subgraphs x2 x2 Canonical representation Less redundant Not explainable 4

18. Predicate Decision Diagram (PDD) x0 x1 x1 x2 x2 5

19. Predicate Decision Diagram (PDD) x0 MTBDD + Predicate labeling function : Variables Predicates x0 x > 7 x2 x1 x1 x > 1 x2 y > 2 x2 x2 5

20. Predicate Decision Diagram (PDD) x > 7 MTBDD + Predicate labeling function : Variables Predicates x0 x > 7 y > 2 x > 1 x1 x > 1 x2 y > 2 y > 2 y > 2 5

21. Predicate Decision Diagram (PDD) x > 7 MTBDD + Predicate labeling function : Variables Predicates x0 x > 7 y > 2 x > 1 x1 x > 1 x2 y > 2 y > 2 y > 2 Small Explainable Less redundant Canonical representation for axis-aligned predicates 5

22. How to get ROPDD from DT? x > 1 x > 7 y > 2 y > 2 y > 2 6

23. How to get ROPDD from DT? x > 1 Fix a variable ordering x > 7, x > 1, y > 5 x > 7 y > 2 Recursive algorithm using If If- -Then Then- -Else Else operator (ITE) y > 2 y > 2 ITE(f, g, h)=ITE(x, ITE(fx=1 , gx=1 , hx=1) , ITE(fx=0 , gx=0 , hx=0) ) 6

24. How to get ROPDD from DT? x > 1 Fix a variable ordering x > 7, x > 1, y > 5 x > 7 y > 2 Recursive algorithm using If If- -Then Then- -Else Else operator (ITE) y > 2 y > 2 ITE(f, g, h)=ITE(x, ITE(fx=1, gx=1, hx=1) , ITE(fx=0, gx=0, hx=0) ) 6

25. How to get ROPDD from DT? x > 1 Fix a variable ordering x > 7, x > 1, y > 5 x > 7 Recursive algorithm using If If- -Then Then- -Else Else operator (ITE) y > 2 y > 2 y > 2 ITE(f, g, h)=ITE(x, ITE(fx=1 , gx=1 , hx=1) , ITE(fx=0 , gx=0 , hx=0) ) 6

26. How to get ROPDD from DT? x > 1 Fix a variable ordering x > 7, x > 1, y > 5 x > 7 Recursive algorithm using If If- -Then Then- -Else Else operator (ITE) y > 2 y > 2 y > 2 ITE(f, g, h)=ITE(x, ITE(fx=1, gx=1, hx=1) , ITE(fx=0, gx=0, hx=0) ) 6

27. How to get ROPDD from DT? x > 7 Fix a variable ordering x > 7, x > 1, y > 5 x > 1 x > 1 Recursive algorithm using If If- -Then Then- -Else Else operator (ITE) y > 2 y > 2 y > 2 ITE(f, g, h)=ITE(x, ITE(fx=1 , gx=1 , hx=1) , ITE(fx=0 , gx=0 , hx=0) ) 6

28. How to get ROPDD from DT? x > 7 Fix a variable ordering x > 7, x > 1, y > 5 x > 1 x > 1 Recursive algorithm using If If- -Then Then- -Else Else operator (ITE) y > 2 y > 2 y > 2 ITE(f, g, h)=ITE(x, ITE(fx=1, gx=1, hx=1) , ITE(fx=0, gx=0, hx=0) ) 6

29. Inconsistency! x > 7 (x > 7) and NOT (x > 1) is not feasible x > 1 x > 1 y > 2 y > 2 y > 2 7

30. Inconsistency! x > 7 (x > 7) and NOT (x > 1) is not feasible Remove inconsistent nodes x > 1 x > 1 y > 2 y > 2 y > 2 7

31. Inconsistency! x > 7 (x > 7) and NOT (x > 1) is not feasible Remove inconsistent nodes x > 1 x > 1 y > 2 y > 2 y > 2 7

32. Inconsistency! x > 7 (x > 7) and NOT (x > 1) is not feasible Remove inconsistent nodes x > 1 Direct solution for axis-aligned predicates y > 2 y > 2 y > 2 Use SMT SMT- -based approach based approach for complicated predicates 7

33. More optimizations Reordering Reordering: Find better variable order by sifting [Rudell, 93] Locally swap position of adjacent variables 8

34. More optimizations Reordering Reordering: Find better variable order by sifting [Rudell, 93] Locally swap position of adjacent variables Don t care reduction Don t care reduction: Restrict the set of evaluations to a care-set [Coudert, Madre; 90] Decisions in certain states are not relevant and can be chosen arbitrarily 8

35. More optimizations Reordering Reordering: Find better variable order by sifting [Rudell, 93] Locally swap position of adjacent variables Don t care reduction Don t care reduction: Restrict the evaluations to a care-set [Coudert, Madre; 90] Decisions in not relevant states can be chosen arbitrarily Implemented in Python, based on dtControl dtControl 2.0 2.0 and BDD library BuDDy BuDDy 8

36. Full pipeline Reducing & ordering Exhaustive reordering, Consistency checking, Don t care reductions Decision Tree PDD Policy table Reduced Ordered Inconsistent Reduced Ordered Consistent Smaller Non-reduced Unordered Reduced Ordered Consistent Controller policy PDD PDD DT learning Algorithm Consistency checking 9

37. Experimental Results Benchmarks Benchmarks 10rooms blocksworld.5 consensus.2.disagree cruise-latest csma.2-4.some_before dcdc States States 26288 1124 2064 295615 7472 593089 MTBDD size MTBDD size 1102 4043 112 2115 1172 814 DT size DT size 8648 617 33 493 51 135 PDD size PDD size 344 796 31 476 53 135 exploding-blocksworld.5 firewire_abst.3.rounds helicopter pacman.5 philosophers-mdp.3 pnueli-zuck.5 traffic_30m triangle-tireworld.9 zeroconf.1000.4.true.correct_max 76741 610 280539 232 344 303427 16639662 26244 1068 39436 51 3348 440 251 59217 4522 38 520 2490 12 3169 21 195 85685 6286 13 41 3635 12 3158 21 203 72192 2350 13 44 10

38. Experimental results PDD size Number of states MTBDD size Number of states PDD size ratio = BDD size ratio = 11

39. Experimental results PDD size Number of states DT size PDD size ratio = DT size ratio = Number of states 12

40. Conclusion Joining the benefits of DTs and MTBDDs seems promising More explainabilty while maintaining canonicity Exploit existing tools for size reduction Already size reductions; even without dedicated PDD learning Future works Future works: compare different DT learning methods Future works Future works: dedicated PDD-based synthesis algorithms from controllers 13

41. Questions? 14