Forward chaining in AI is an example of the general concept of data-driven reasoning – i.e., 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.
Table of Contents
Forward Chaining Procedure
- 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 in AI
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
1. 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.
2. On the second iteration, rule (1) is satisfied with, and the inference is added.
Check this below image on how the proof tree is generated?
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.
Forward Chaining Visualization Tool
Inferred Facts
Reasoning Process
Effective Forward Chaining
The forward chaining algorithm shown in the 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).
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.
Related Articles
Frequently Asked Questions
A type of reasoning known as “forward chaining” begins with basic facts from the knowledge base and proceeds forward by applying inference rules to extract more data until the desired outcome is obtained. Beginning with the objective, backward chaining searches through the rules for known facts that support the objective.
When teaching a sequence, forward chaining starts with the first step. Usually, a learner waits to proceed to the second step until they have mastered the first. When teaching a sequence using backward chaining, the final step is taught first.
The concept of backward chaining is the same as that of forward chaining, with the exception that the learner must first finish the task analysis of final step. This implies that you will carry out each of the earlier steps, either alone or with the learner, and that you will only start to reduce the frequency of your signals with the final step.
With forward chaining, the learner is first instructed to finish just the first task analysis step, and they are then required to complete that one step independently in order to receive a reward.
2 thoughts on “What is Forward Chaining in AI?”