Forward Chaining
Forward chaining is an example of the general concept of data-driven reasoning—that is, reasoning in which the focus of attention starts with the known data. It can be used within an agent to derive conclusions from incoming percepts, often without a specific query in mind.
For example, the wumpus agent might TELL its percepts to the knowledge base using an incremental forward-chaining algorithm in which new facts can be added to the agenda to initiate new inferences.
- First-order definite clauses are disjunctions of literals of which exactly one is positive. That means a definite clause is either atomic, or is an implication whose antecedent is a conjunction of positive literals and whose consequent is a single positive literal.
- Existential quantifiers are not allowed, and universal quantifiers are left implicit: if you see an in a definite clause, that means there is an implicit quantifier. A typical first-order definite clause looks like this:
King(x) ∧ Greedy(x) ⇒ Evil(x)
but the literals and also count as definite clauses. First-order literals can include variables, so Greedy is interpreted as "everyone is greedy".
First, we will represent these facts as first-order definite clauses:
1. "it is a crime for an American to sell weapons to hostile nations":
- American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x). - (rule 1)
2. "Nono has some missiles." The sentence is transformed into two definite clauses by Existential Instantiation, introducing a new constant;
- Owns(Nono,M1) - (rule 2)
- Missile(M1) - (rule 3)
3. "All of its missiles were sold to it by Colonel West":
- Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono). - (rule 4)
4. We will also need to know that missiles are weapons:
- Missile(x) ⇒ Weapon(x) - (rule 5)
5. and we must know that an enemy of America counts as "hostile":
- Enemy(x,America) ⇒ Hostile(x). - (rule 6)
6. "West, who is American... ":
- American(West) - (rule 7)
7. "The country Nono, an enemy of America ":
- Enemy(Nono,America). - (rule 8)
Simple forward-chaining algorithm
The simple forward chaining inference algorithm is shown below. Starting from the known facts, it triggers all the rules whose premises are satisfied, adding their conclusions to the known facts. The process repeats until the query is answered (assuming that just one answer is required) or no new facts are added.
For example, Likes(x,IceCream) and Likes(y,IceCream) are renaming of each other. They both mean the same thing: "Everyone likes ice cream."
Forward Chaining Inference Algorithm
function FOL-FC-ASK(KB,α) returns a substitution or false
inputs: KB, the knowledge base, a set if first-order definite clauses
α, the query, an atomic sentence
while true do
new ← {} // The set of new sentences inferred on each iteration
for each rule in KB do
(p1 ∧...∧ pn ⟹ q) ← STANDARDIZE - VARIABLES (rule)
for each θ such that SUBST (θ,p1 ∧...∧ pn) = SUBST(θ,p'1 ∧ ... ∧ p'n) for some p'1,...,p'n in KB q' ← SUBST(θ,q)
if q' does not unify with some sentence already in KB or new then
add q' to new
∅ ← UNIFY (q',α)
if ∅ is not failure then return ∅
if new = {} then return false
add new to KB
- On the first iteration, rule (1) has unsatisfied premises.
- Rule (4) is satisfied with, and is added.
- Rule (5) is satisfied with, and is added.
- Rule (6) is satisfied with, and is added.
- On the second iteration, rule (1) is satisfied with, and the inference is added.
Check this below image on how proof tree is generated?
 |
| Figure: The proof tree generated by forward chaining on the crime example. |
For general definite clauses with function symbols, FOL-FC-ASK can generate infinitely many new facts, so we need to be more careful. If the query has no answer, the algorithm could fail to terminate in some cases.
NatNum(0)
∀n NatNum(n) ⇒ NatNum(S(n)),
then forward chaining adds as, NatNum(S(0)), NatNum(S(S(0))), NatNum(S(S(S(0)))), and so on.
Below is the video for Forward Chaining to Understand better.
Efficient forward chaining
The forward-chaining algorithm shown in first image is designed for ease of understanding, not efficiency. There are three sources of inefficiency.
- First, the inner loop of the algorithm tries to match every rule against every fact in the knowledge base.
- Second, the algorithm rechecks every rule on every iteration, even if very few additions have been made to the knowledge base.
- Third, the algorithm can generate many facts that are irrelevant to the goal.
We address each of these issues in turn. Matching rules against known facts the problem of matching the premise of a rule against the facts in the knowledge base might seem simple enough. For example, suppose we want to apply the rule
Missile(x) ⇒ Weapon(x).
Then we need to find all the facts that unify with ; in a suitably indexed knowledge base, this can be done in constant time per fact. Now consider a rule such as
Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono).
 |
| Figure: Efficient Forward Chaining |
The connection between this pattern matching and constraint satisfaction is actually very close. We can view each conjunct as a constraint on the variables that it contains for example, Missile(x) is a unary constraint on x. Extending this idea, we can express every finite-domain CSP as a single definite clause together with some associated ground facts.
