AI Backward Chaining implementation for propositional logic horn form knowledge bases


/ Published in: Java
Save to your folder(s)

Artificial intelligence basics : This is a backward chaining implementation which works with horn form knowledge bases. Had some trouble finding any simple and easy to understand examples online - so here's my version!!! http://en.wikipedia.org/wiki/Backward_chaining


Copy this code and paste it in your HTML
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. // to run simply do a: new BC(ask,tell) and then bc.execute()
  5. // ask is a propositional symbol
  6. // and tell is a knowledge base
  7. // ask : p
  8. // tell : p=>q;q=>r;r;
  9.  
  10. class BC{
  11. // create variables
  12. public static String tell;
  13. public static String ask;
  14. public static ArrayList<String> agenda;
  15. public static ArrayList<String> facts;
  16. public static ArrayList<String> clauses;
  17. public static ArrayList<String> entailed;
  18.  
  19. public BC(String a, String t){
  20. // initialize variables
  21. agenda = new ArrayList<String>();
  22. clauses = new ArrayList<String>();
  23. entailed = new ArrayList<String>();
  24. facts = new ArrayList<String>();
  25. tell = t;
  26. ask = a;
  27. init(tell);
  28. }
  29.  
  30.  
  31. // method which sets up initial values for backward chaining
  32. public static void init(String tell){
  33. agenda.add(ask);
  34. // split kb into sentences
  35. String[] sentences = tell.split(";");
  36. for (int i=0;i<sentences.length;i++){
  37. if (!sentences[i].contains("=>"))
  38. // add the facts
  39. facts.add(sentences[i]);
  40. else{
  41. // add the premises
  42. clauses.add(sentences[i]);
  43. }
  44. }
  45. }
  46.  
  47. // method which calls the main bcentails() method and returns output back to iengine
  48. public String execute(){
  49. String output = "";
  50.  
  51. if (bcentails()){
  52. // the method returned true so it entails
  53. output = "YES: ";
  54. // loop through all entailed symbols in reverse
  55. for (int i=entailed.size()-1;i>=0;i--){
  56. if (i==0)
  57. output += entailed.get(i);
  58. else
  59. // no comma at the end
  60. output += entailed.get(i)+", ";
  61.  
  62. }
  63. }
  64. // no
  65. else{
  66. output = "NO";
  67. }
  68. return output;
  69. }
  70.  
  71. // method which runs the bc algorithm
  72. public boolean bcentails(){
  73. // while the list of symbols are not empty
  74. while(!agenda.isEmpty()){
  75. // get current symbol
  76. String q = agenda.remove(agenda.size()-1);
  77. // add the entailed array
  78. entailed.add(q);
  79.  
  80. // if this element is a fact then we dont need to go further
  81. if (!facts.contains(q)){
  82. // .. but it isnt so..
  83. // create array to hold new symbols to be processed
  84. ArrayList<String> p = new ArrayList<String>();
  85. for(int i=0;i<clauses.size();i++){
  86. // for each clause..
  87. if (conclusionContains(clauses.get(i),q)){
  88. // that contains the symbol as its conclusion
  89.  
  90. ArrayList<String> temp = getPremises(clauses.get(i));
  91. for(int j=0;j<temp.size();j++){
  92. // add the symbols to a temp array
  93. p.add(temp.get(j));
  94. }
  95. }
  96. }
  97. // no symbols were generated and since it isnt a fact either
  98. // then this sybmol and eventually ASK cannot be implied by TELL
  99. if (p.size()==0){
  100. return false;
  101. }
  102. else{
  103. // there are symbols so check for previously processed ones and add to agenda
  104. for(int i=0;i<p.size();i++){
  105. if (!entailed.contains(p.get(i)))
  106. agenda.add(p.get(i));
  107. }
  108.  
  109.  
  110. }
  111. }
  112.  
  113. }//while end
  114. return true;
  115. }
  116.  
  117. // methid that returns the conjuncts contained in a clause
  118. public static ArrayList<String> getPremises(String clause){
  119. // get the premise
  120. String premise = clause.split("=>")[0];
  121. ArrayList<String> temp = new ArrayList<String>();
  122. String[] conjuncts = premise.split("&");
  123. // for each conjunct
  124. for(int i=0;i<conjuncts.length;i++){
  125. if (!agenda.contains(conjuncts[i]))
  126. temp.add(conjuncts[i]);
  127. }
  128. return temp;
  129. }
  130.  
  131.  
  132. // method which checks if c appears in the conclusion of a given clause
  133. // input : clause, c
  134. // output : true if c is in the conclusion of clause
  135. public static boolean conclusionContains(String clause, String c){
  136. String conclusion = clause.split("=>")[1];
  137. if (conclusion.equals(c))
  138. return true;
  139. else
  140. return false;
  141.  
  142. }
  143.  
  144. }

URL: http://en.wikipedia.org/wiki/Backward_chaining

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.