Forward and Backward Chaining

Forward chaining and backward chaining are two common inference strategies used in knowledge-based systems and rule-based reasoning. They are used to derive new information or reach conclusions based on a set of rules and facts within a knowledge base.

1. Forward Chaining: Forward chaining starts with the available facts and uses them to infer new conclusions or facts. It works in a data-driven or bottom-up manner, gradually applying rules to deduce new information until no further inferences can be made. The process continues until a specific goal or condition is satisfied.

Here’s a simplified step-by-step explanation of the forward chaining process:

• Start with the given facts or initial conditions.
• Identify rules that match the available facts.
• Apply the matching rules to infer new facts or conclusions.
• Add the newly derived facts to the knowledge base.
• Repeat the process, using the updated knowledge base, until the desired goal or condition is met or no further inferences can be made.

Forward chaining is often used in situations where the available data is plentiful, and the focus is on exploring and deriving new information from the known facts.

2. Backward Chaining: Backward chaining, on the other hand, starts with a goal or conclusion and works backward to determine what facts or rules can lead to that goal. It is a goal-driven or top-down approach that traces the chain of reasoning from the goal to the supporting facts.

Here’s a simplified step-by-step explanation of the backward chaining process:

• Start with the desired goal or conclusion.
• Identify rules that can directly or indirectly contribute to the goal.
• Check if the required facts or conditions for applying the identified rules are available.
• If the required facts are not available, recursively apply backward chaining to find the facts that can satisfy the conditions.
• Repeat the process until all necessary facts are identified or until it is determined that the goal cannot be reached.

Backward chaining is often used in situations where the focus is on finding the causes or explanations for a particular conclusion or goal. It is particularly useful when working with diagnostic systems or troubleshooting scenarios.

Both forward chaining and backward chaining have their strengths and are suitable for different problem domains. The choice between them depends on the nature of the problem, available data, and the desired approach to reasoning and inference.

In artificial intelligence, forward and backward chaining is one of the important topics, but before understanding forward and backward chaining lets first understand that from where these two terms came.

Inference engine:

The inference engine is the component of the intelligent system in artificial intelligence, which applies logical rules to the knowledge base to infer new information from known facts. The first inference engine was part of the expert system. Inference engine commonly proceeds in two modes, which are:

1. Forward chaining
2. Backward chaining

Horn Clause and Definite clause:

Horn clause and definite clause are the forms of sentences, which enables knowledge base to use a more restricted and efficient inference algorithm. Logical inference algorithms use forward and backward chaining approaches, which require KB in the form of the first-order definite clause.

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

Horn clause: A clause which is a disjunction of literals with at most one positive literal is known as horn clause. Hence all the definite clauses are horn clauses.

Example: (¬ p V ¬ q V k). It has only one positive literal k.

It is equivalent to p ∧ q → k.

A. Forward Chaining

Forward chaining is also known as a forward deduction or forward reasoning method when using an inference engine. Forward chaining is a form of reasoning which start with atomic sentences in the knowledge base and applies inference rules (Modus Ponens) in the forward direction to extract more data until a goal is reached.

The Forward-chaining algorithm starts from known facts, triggers all rules whose premises are satisfied, and add their conclusion to the known facts. This process repeats until the problem is solved.

Properties of Forward-Chaining:

• It is a down-up approach, as it moves from bottom to top.
• It is a process of making a conclusion based on known facts or data, by starting from the initial state and reaches the goal state.
• Forward-chaining approach is also called as data-driven as we reach to the goal using available data.
• Forward -chaining approach is commonly used in the expert system, such as CLIPS, business, and production rule systems.

Consider the following famous example which we will use in both approaches:

Example:

“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.”

Prove that “Robert is criminal.”

To solve the above problem, first, we will convert all the above facts into first-order definite clauses, and then we will use a forward-chaining algorithm to reach the goal.

Facts Conversion into FOL:

• It is a crime for an American to sell weapons to hostile nations. (Let’s say p, q, and r are variables)
  American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p)       …(1)
• Country A has some missiles. ?p Owns(A, p) ∧ Missile(p). It can be written in two definite clauses by using Existential Instantiation, introducing new Constant T1.
  Owns(A, T1)             ……(2)
  Missile(T1)             …….(3)
• All of the missiles were sold to country A by Robert.
  ?p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A)       ……(4)
• Missiles are weapons.
  Missile(p) → Weapons (p)             …….(5)
• Enemy of America is known as hostile.
  Enemy(p, America) →Hostile(p)             ……..(6)
• Country A is an enemy of America.
  Enemy (A, America)             ………(7)
• Robert is American
  American(Robert).             ……….(8)