Search Classification

AI plays a vital role in searching algorithms. As we already know that AI means a thinking machine,
capable of acting like Humans. Humans have the capability to improvise in the middle of doing a
work. Similarly, machines can also be programmed to improvise while searching. Now we will see
how this can be achieved.

The searching algorithms can be divided into two main categories :
1. Blind / Uninformed
2. Heuristic / Informed

1. Blind / Uninformed searching technique means that search is not aware of its position
in the search space. For example - Breadth First Search, Depth First Search, etc.

2. Heuristic / Informed searching technique means that the search is aware of its position
in the search space. It uses a heuristic function to improvise its searching technique.
It can calculate how much distance it has covered and predict how many calculations
are required to reach its target.
For example - Simple Hill Climbing, Best First Search, A*, AO*, etc.

A heuristic function is a function that maps from the problem
state descriptions to measures of desirability, usually
represented as numbers.

The best example for demonstrating heuristic function is the 8-puzzle problem.
The 8-puzzle is a small board game for a single player; it consists of 8
square tiles numbered 1 through 8 and one blank space on a 3 x 3 board.
Moves of the puzzle are made by sliding an adjacent tile into the position
occupied by the blank space, which has the effect of exchanging the positions
of the tile and blank space. Only tiles that are horizontally or vertically
adjacent (not diagonally adjacent) may be moved into the blank space.
The goal is to set all the numbered tiles in ascending order starting
from the top left corner.

Let the heuristic function be like the total number of numbered tiles that
are exactly in its place. For example, Tile 4 is at the position 4.

From the above picture it is clear that we will select that state which has
higher heuristic value as it leads us to the goal perfectly.

That's an example of heuristic function. There is no hard and fast rule that
a problem will have same heuristic function. It completely depends on the
programmer how to solve the problem. For instance, anyone can make a heuristic
function that counts how tiles are not in places.

Now a formal definition of heuristic search process:
A heuristic is a technique that improves the efficiency of a search process,
possibly by sacrificing claims of completeness.

I will describe the heuristic algorithms in the next blog. Till then, keep coding.

Production System in AI

Okay!!! So before diving into deeper in the forest of AI, let us understand some basic terminologies
like what is problem, problem characteristics, state space, etc. This might seem little boring to
you but we need to discuss about these terminologies to proceed further. So I'll quickly give you
the idea about what they are :

A problem consists of four parts-
1. Initial state(s)
2. Set of actions
3. Goal test function
4. Path cost function

A state space comprised of all feasible state corresponding to the problem.
Solution may be a path from initial state to goal state incorporating various intermediate
states.

The characteristics of problem are :
1. Is the problem decomposable?
2. Can solution steps be ignored or undone ?
3. Is the problem universe predictable?
4. Is a good solution must, without comparing all other solutions ?
5. Is the desired solution a path to a state or simply a state?

Now, the important topic starts from here. Every problem must be solved using a system.
It is one of the very basic necessities of AI to solve a problem.

To build a system that can solve the problem must follow these :
1. Precise problem definition & specification of states
2. Analysis of important features
3. Isolate & represent task-knowledge
4. Choose the best problem solving techniques & apply it.

A system that solves a problem in AI is known as a Production System.
Describing & performing the search process during goal state determination will be done
by the production system. It consists of-
1. A set of rule : A set of do(s) and don't(s).
2. Database/knowledgebase : A collection of data or knowledge.
3. Control strategy : The control flow of the program for the solving the problem.
4. Rule applier : As the name implies, it applies the appropriate rule to the system.

A little more description about Control Strategy :
A good control strategy may ensure a goal state with
comparatively reasonable path cost. Two of its features are vital
1. Dynamic : will ensure newer and newer state only to enhance possibility of obtaining a goal state.
2. Systematic : this feature will drive it into either of the solution paths through least effort.

For simplicity, here we will take the example of Water Jug Problem for the better understanding of Production System.

Water Jug Problem
Two jugs of size 7 and 4 gallons and one liquid source with enough amount can be availed. The
container contains no scaling on them. Container can be filled, emptied or exchange liquid
between themselves. Perform operation in such an way that 7 gallon jug contains 2 gallon of water.

Production Rule :
1. (x,y) -> (x,4) Fill-up the 4-gallon Jug from Water Source.
     if(y<4)
2. (x,y) -> (7,y) Fill-up the 7-gallon Jug from Water Source.
     if(x<7)
3. (7,y) -> (7-(4-y),4) Fill-up the 4-gallon Jug from the 7-gallon Jug.
     if(y<4)
4. (x,4) -> (7,4-(7-x)) Fill-up the 7-gallon Jug from the 4-gallon Jug.
     if(x<7) && (x>2)
etc.

Knowledge Base :
7-gallon Jug
4-gallon Jug
Water Source

Control Strategy :
This problem can be solved in many ways. A small part of the search tree or graph will help you to visualise the different possibilities. But not all the possibilities will be followed. Only the path with the least effort will be taken.

Rule Applier :
x    y    Rule / Operation
0    0    Initial state
7    0    Fill-up the 7 gallon jug from the water source
3    4    Fill 4g jug from 7g jug
3    0    Empty the 4g jug
0    3    Fill 4g jug from 7g jug
7    3    Fill-up the 7g jug from the water source
6    4    Fill 4g jug from 7g jug
6    0    Empty the 4g jug
2    4    Fill 4g jug from 7g jug

In this way, this problem can be solved with the least effort.
Here is a small video for the solution.