Backward Chaining implementation as State Space Search problem

To me, Backward Chaining implementation can be viewed as a state space search problem.

In this problem, a state consists two components:

(Path, Goals)

  • Path is the list of ordered rules that are used.
  • Goals is the set of facts that currently need to be deduced.

An available action at a state is a applicable rule for that state.

The below example will clarify the idea.

Suppose that you have a set of rules:

 Rules = \left \{ \left \{ A \right \} \Rightarrow \left \{ E \right \}, \left \{ B \right \} \Rightarrow \left \{ D \right \}, \left \{ H \right \} \Rightarrow \left \{ A \right \}, \left \{ E, G \right \} \Rightarrow \left \{ C \right \}, \left \{ E, K \right \} \Rightarrow \left \{ B \right \}, \left \{ D, E, K \right \} \Rightarrow \left \{ C \right \}, \left \{ F, G, K\right \} \Rightarrow \left \{ A \right \} \right \}

Also suppose that we are facing a problem in which we have already known \left \{ H, K \right \}, and we want to know if \left \{ C, D \right \} can be deduced (if yes, then how?).

The green one is the initial state while the blue one is the goal state.

By this insight, now you know that you can implement Backward Chaining in various ways. Two path-finding algorithms that I suggest are A* and Depth-First Search. At first, I thought that Breadth-First Search might be good in finding shortest solution, however after an inspection, I find that a tuned Depth-First Search is still better than Breadth-First Search in such case.

By the way, if you exclude the Path component from a state (or at least do not let the Path component decides the unique of a state), you will have a more flexible state space search problem for backward chaining implementation.

MAPLE implementation using Depth-First Search:


Leave a Reply

Your email address will not be published. Required fields are marked *