Forward and backward chaining in AI

Table of Content:

• What is inference engine in AI?
• What is horn clause and definite clause?
• Forward Chaining.
• How Forward Chaining Works?
• Example to Illustrate Forward Chaining.
• Steps to Solve Using Forward Chaining.
• Backward Chaining.
• How Backward Chaining Works?
• Example to Illustrate Backward Chaining.
• Steps to Solve Using Backward Chaining.
• Difference between forward chaining and backward chaining.

Content Highlight:

An inference engine is a vital component in AI, using logical rules to deduce new information from existing facts in the knowledge base. Operating in two modes, forward chaining and backward chaining, it enhances intelligent systems' problem-solving capabilities. Forward chaining is a data-driven approach starting with known facts and applying rules to reach a goal, while backward chaining is goal-driven, starting with a goal and working backward to find supporting facts. These methods enable AI systems to draw accurate conclusions and provide reliable solutions, essential for applications in expert systems, decision support systems, and logic programming.

What is inference engine in AI?

An inference engine is a crucial component in artificial intelligence (AI), fundamental to the functioning of intelligent systems. It employs logical rules to the knowledge base, deducing new information from existing facts. This concept was first implemented in expert systems. The inference engine operates in two primary modes:

1. Forward Chaining: This data-driven approach begins with known facts and applies logical rules to infer new facts progressively until a specific goal is achieved. The engine continuously advances, enriching the knowledge base with newly deduced information.
2. Backward Chaining: This goal-driven strategy starts with a particular goal and works backward, identifying the necessary facts to support that goal. The process continues until it traces back to the known facts that substantiate the goal.

By leveraging these methods, inference engines enable AI systems to draw accurate conclusions and provide reliable solutions based on the encoded knowledge. This capability is essential for applications in expert systems, decision support systems, and other AI-driven technologies, enhancing their ability to solve complex problems and make informed decisions.

What is horn clause and definite clause?

Horn clauses and definite clauses are specialized forms of sentences that enable the knowledge base to utilize more restricted and efficient inference algorithms. Logical inference algorithms, such as forward chaining and backward chaining, rely on the knowledge base being in the form of first-order definite clauses for optimal performance.

Definite Clause: A definite clause, also known as a strict horn clause, is a disjunction of literals with exactly one positive literal.

Horn Clause: A horn clause is a disjunction of literals with at most one positive literal. Therefore, all definite clauses are horn clauses, but not all horn clauses are definite clauses.

Example: Consider the clause (¬p ∨ ¬q ∨ k). This clause has only one positive literal, k, making it a horn clause. It is logically equivalent to the implication (p ∧ q→k).

By using horn clauses and definite clauses, logical inference algorithms can efficiently process and deduce new information, enhancing the overall performance of AI systems.

Forward Chaining: A Reasoning Method

Forward chaining, also known as forward deduction or forward reasoning, is a method used in inference engines. It starts with atomic sentences in the knowledge base and applies inference rules, such as Modus Ponens, in a forward direction to extract more data until a goal is reached.

How Forward Chaining Works?

The forward-chaining algorithm begins with known facts. It triggers all rules whose premises are satisfied and adds their conclusions to the known facts. This process repeats until the problem is solved.

Properties of Forward Chaining:

• Bottom-Up Approach: Forward chaining moves from the initial state (known facts) to the goal state, hence it is referred to as a bottom-up approach.
• Data-Driven: This approach is driven by the available data, starting from the initial state and reaching the goal state.
• Applications: Forward chaining is commonly used in expert systems like CLIPS, as well as in business and production rule systems.

Example to Illustrate Forward Chaining

Consider the following scenario:

Scenario: "As per the law, it is a crime for an American to sell weapons to hostile nations. Country A, an enemy of America, has some missiles, and all the missiles were sold to it by Robert, who is an American citizen."

Goal: Prove that "Robert is a criminal."

Steps to Solve Using Forward Chaining:

1. Convert Facts into First-Order Logic (FOL) Definite Clauses:

   • It is a crime for an American to sell weapons to hostile nations.
     (Let p, q, and r be variables) American(p) ∧ weapon(q) ∧ sells(p, q, r) ∧ hostile(r) → Criminal(p) ... (1)
   • Country A has some missiles. Using Existential Instantiation, introduce a new constant T1.
     Owns(A, T1) ... (2)
     Missile(T1) ... (3)
   • All missiles owned by Country A were sold to it by Robert.
     Missile(p) ∧ Owns(A, p) → Sells(Robert, p, A) ... (4)
   • Missiles are weapons.
     Missile(p) → Weapon(p) ... (5)
   • An enemy of America is considered hostile.
     Enemy(p, America) → Hostile(p) ... (6)
   • Country A is an enemy of America.
     Enemy(A, America) ... (7)
   • Robert is an American.
     American(Robert) ... (8)

2. Apply Forward Chaining Algorithm:

   • Start with the known facts: Owns(A, T1) (2), Missile(T1) (3), Enemy(A, America) (7), and American(Robert) (8).
   • From (3) and (5), deduce Weapon(T1).
   • Using (2) and (4), deduce Sells(Robert, T1, A).
   • From (7) and (6), deduce Hostile(A).
   • Combining American(Robert), Weapon(T1), Sells(Robert, T1, A), and Hostile(A) with rule (1), deduce Criminal(Robert).

Thus, we have proven that Robert is a criminal using forward chaining.

2. Backward Chaining: A Reasoning Method

Backward chaining, also known as backward deduction or backward reasoning, is a method used in inference engines. It starts with a goal and works backward to determine if there is data in the knowledge base that supports the goal.

How Backward Chaining Works?

The backward-chaining algorithm begins with the goal and looks for rules that can conclude the goal. If a rule is found, the algorithm then tries to prove the premises of the rule by looking for facts or other rules that support these premises. This process repeats until the initial facts are found or no more rules apply.

Properties of Backward Chaining

• Top-Down Approach: Backward chaining moves from the goal state to the initial state, hence it is referred to as a top-down approach.
• Goal-Driven: This approach is driven by the goal, starting from the goal state and working backward to the initial state.
• Applications: Backward chaining is commonly used in expert systems for diagnosis and troubleshooting, as well as in logic programming languages like Prolog.

Example to Illustrate Backward Chaining:

Consider the following scenario:

Scenario: "As per the law, it is a crime for an American to sell weapons to hostile nations. Country A, an enemy of America, has some missiles, and all the missiles were sold to it by Robert, who is an American citizen."

Goal: Prove that "Robert is a criminal."

Steps to Solve Using Backward Chaining

1. Identify the Goal:

   Our goal is to prove Criminal(Robert).

2. Find a Rule That Concludes the Goal:

   We have the rule:
   American(p) ∧ weapon(q) ∧ sells(p, q, r) ∧ hostile(r) → Criminal(p) ... (1)
   To prove Criminal(Robert), we need to prove the premises of this rule:
   

   • Robert is an American.
   • Robert sold a weapon to a hostile nation.

3. Prove Each Premise:

   • Prove American(Robert). This is a given fact:
     American(Robert) ... (8)
   • Prove sells(Robert, q, r) where q is a weapon and r is a hostile nation:
     
     • From the fact that Robert sold missiles to Country A:
       Missile(p) ∧ Owns(A, p) → Sells(Robert, p, A) ... (4)
       We need to prove:
       Owns(A, p) ... (2) and Missile(p) ... (3)
     • We also need to prove that missiles are weapons:
       Missile(p) → Weapon(p) ... (5)
   • Prove hostile(A) where A is Country A:
     
     • From the fact that enemies of America are hostile:
       Enemy(p, America) → Hostile(p) ... (6)
       We need to prove:
       Enemy(A, America) ... (7)

4. Thus, using the premises:
   American(Robert) ... (8),
   Missile(T1) ... (3),
   Owns(A, T1) ... (2),
   Missile(T1) → Weapon(T1) ... (5),
   Enemy(A, America) ... (7),
   and
   Enemy(p, America) → Hostile(p) ... (6),
   we conclude
   Criminal(Robert).

Thus, we have proven that Robert is a criminal using backward chaining.

Difference between forward chaining and backward chaining: