AI Forward Chaining implementation for propositional logic horn form knowledge bases


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

Artificial intelligence basics : This is a forward 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/Forward_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 FC(ask,tell) and then fc.execute()
  5. // ask is a propositional symbol
  6. // and tell is a knowledge base
  7. // ask : r
  8. // tell : p=>q;q=>r;p;q;
  9.  
  10. class FC{
  11. // create variables
  12. public static String tell;
  13. public static String ask;
  14. public static ArrayList<String> agenda;
  15.  
  16. public static ArrayList<String> facts;
  17. public static ArrayList<String> clauses;
  18. public static ArrayList<Integer> count;
  19. public static ArrayList<String> entailed;
  20.  
  21.  
  22. public FC(String a, String t){
  23. // initialize variables
  24. agenda = new ArrayList<String>();
  25. clauses = new ArrayList<String>();
  26. entailed = new ArrayList<String>();
  27. facts = new ArrayList<String>();
  28. count = new ArrayList<Integer>();
  29. tell = t;
  30. ask = a;
  31. init(tell);
  32. }
  33.  
  34. // method which calls the main fcentails() method and returns output back to iengine
  35. public String execute(){
  36. String output = "";
  37. if (fcentails()){
  38. // the method returned true so it entails
  39. output = "YES: ";
  40. // for each entailed symbol
  41. for (int i=0;i<entailed.size();i++){
  42. output += entailed.get(i)+", ";
  43. }
  44. output += ask;
  45. }
  46. else{
  47. output = "NO";
  48. }
  49. return output;
  50. }
  51.  
  52. // FC algorithm
  53. public boolean fcentails(){
  54. // loop through while there are unprocessed facts
  55. while(!agenda.isEmpty()){
  56. // take the first item and process it
  57. String p = agenda.remove(0);
  58. // add to entailed
  59. entailed.add(p);
  60. // for each of the clauses....
  61. for (int i=0;i<clauses.size();i++){
  62. // .... that contain p in its premise
  63. if (premiseContains(clauses.get(i),p)){
  64. Integer j = count.get(i);
  65. // reduce count : unknown elements in each premise
  66. count.set(i,--j);
  67. // all the elements in the premise are now known
  68. if (count.get(i)==0){
  69. // the conclusion has been proven so put into agenda
  70. String head = clauses.get(i).split("=>")[1];
  71. // have we just proven the 'ask'?
  72. if (head.equals(ask))
  73. return true;
  74. agenda.add(head);
  75. }
  76. }
  77. }
  78. }
  79. // if we arrive here then ask cannot be entailed
  80. return false;
  81. }
  82.  
  83.  
  84.  
  85.  
  86. // method which sets up initial values for forward chaining
  87. // takes in string representing KB and seperates symbols and clauses, calculates count etc..
  88. public static void init(String tell){
  89. String[] sentences = tell.split(";");
  90. for (int i=0;i<sentences.length;i++){
  91.  
  92. if (!sentences[i].contains("=>"))
  93. // add facts to be processed
  94. agenda.add(sentences[i]);
  95. else{
  96. // add sentences
  97. clauses.add(sentences[i]);
  98. count.add(sentences[i].split("&").length);
  99. }
  100. }
  101. }
  102.  
  103.  
  104. // method which checks if p appears in the premise of a given clause
  105. // input : clause, p
  106. // output : true if p is in the premise of clause
  107. public static boolean premiseContains(String clause, String p){
  108. String premise = clause.split("=>")[0];
  109. String[] conjuncts = premise.split("&");
  110. // check if p is in the premise
  111. if (conjuncts.length==1)
  112. return premise.equals(p);
  113. else
  114. return Arrays.asList(conjuncts).contains(p);
  115. }
  116. }

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

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.