Constructing a testbed for abductive reasoning and implementing and testing 2 algorithms on this problem using the testbed - exhaustive search and GA.
The following search problem from the theoretical exercise, also known as the WEIGHTED ABDUCTION problem is known to be NP-hard. You have a KB of weighted clauses, i.e. clauses of the form:
X1 and X2 and ... and Xn implies Y
where each clause C has a weight w(C). For some rules, n=0, i.e. nothing is required to imply Y. A proof is defined as a set of clauses P (from KB), such that if C is in P, then all propositions in the body of C must also be in the head of some clause C' in P. In addition, proof P is a proof of X if X is also in the head of some clause C' in P. The weight (or cost) of a proof P is the sum of costs of all the clauses in P. The problem is: given clauses KB and proposition Y, find the proof P (subset of KB) for Y that has the least cost. In addition, there is a requirement that the the proof be consistent, i.e. that it it contains a literal X, it does not contain (not X).
The testbed should allow for reading a KB from a file, and for generating a KB with certain parameters randomly. Random KB generation parameters are: number of rules, cost distribution type, maximum number of antecedents in a rule, and number of propositions. For simplicity, we will assume that we always need to prove a specific proposition X, and generate randomly only "relevant" rules, i.e. only generate rules that have as a consequent either X or a literal appearing in some antecedent in the KB.
You will implement 2 algorithms: A* with 2 heuristic, one admissible and one inadmissible. Also, implement a genetic algorithm for finding a solution, and test them. Next, you need to run some experiments. The idea is to run an algorithm and TIME it. Then, you report the solution qualities as time allocated to the algorithm inceases. Talk to me about the details!
You need to turn in:
Deadline: September 15, 2003. Deadline is flexible, depending on when you need the grade, but only with prior agreement by the instructor.
Note - this is an individual assignment. Credit for a (perfectly completed) assignment is 10% of final grade added to the computed final grade from mid-term exams and other assignments.