1. Described and match

2. Goal reduction

3. Tree searching

4. Constraint satisfaction

5. Generate and test

6. Rule based system

Biological-inspired AI Techniques:

• Neural network

• Genetic algorithms

• Reinforcement learning

Let us understand them one by one

Describe and match:

In this technique, system’s behavior is explained in terms of a finite state model and computation model.

Finite state model: It consists of a set of states, a set of input events and the relations between them. Based on the current state and an input event, the next state of the model can be determined.

Computation model: It is finite state machine which includes a set of states, a start state, a transition function and an input alphabet. The transition function provides mapping between input symbols and current state to next states.

Transition relation: If a pair of states(S, S’) is such that one move takes the system from S to S’, then the transition relation is represented by S->S’. State- transition system is called deterministic if every state has at most one successor; it is called non-deterministic if at least one state has more than one successor.

Representation of the computational system includes start and end state description and a set or possible translation rules that might be applied. Problem is to find the appropriate translation rules.

Example: Problem of Towers of Hanoi with two discs. The state transitions are shown.

Problem Definition:

Move the disks from the leftmost post to the rightmost post with following conditions:

• A large disk can never be put on the top of a smaller one;

• Only one disk can never be moved at a time, from one peg to another;

• The middle post is only to be used for intermediate storage.

• Complete the task in the smallest number of moves possible.

Solution:

• Possible state transition into towers of Hanoi puzzle with two disks.

• In this problem, the optimal solution is the sequence of transition from the start state downward to the extreme left branch of the transition tree.

Tree searching:

Tree searching is a very commonly used technique to solve many problems. Goal reduction, constraint networks are few of the areas. Tree is searched through many nodes to obtain the goal node and it gives the path from source node to destination node.

If each node of the entire tree is explored while searching for the goal node, it is called as exhaustive search. All the searching techniques of AI are broadly classified as uninformed searching and informed searching.

Uninformed Searching Techniques

• Depth first Search

• Breadth first Search

• Uniform Cost Search

• Depth Limited Search

• Iterative Depending DFS

• Bidirectional Search

Informed Search Techniques

• Hill Climbing

• Best first search

• A* Search

• Iterative depending A*

• Beam Search

• AO* search.

Goal Reduction:

In goal reduction technique, the main goal is divided into sub goals. It requires some procedures to follow. Goal reduction procedures are an alternative to declarative and logic based representations.

Goal reduction process includes hierarchical sub division of goals into sub goals is carried out until the sub goals have an immediate solution. An AND-OR tree/graph structure can represent relations between goals and sub goals, alternative sub-goals and conjoint sub-goals.

There are different goal levels. Higher-level goals are higher in the tree, and lower level goals are lower in the tree. There are directed arcs from a higher level to lower level nodes, representing the reduction of higher level goal to lower level sub goals. Nodes are the leaf nodes of the tree. These goals cannot be divided further.

Example: An AND/OR tree structure to represent facts such as “enjoyment”, “earning/save money”, “old age” etc.

The and/or tree structure describe following things

i. Hierarchical relationship between goals and sub goals: The “Earn more money”, is a sub goal school of “Improve enjoyment of life”.

ii. Alternative ways of trying to solve a goal: The “Go on strike” and “Improve productivity” are alternative ways of trying to “Earn more money”.

iii. Conjoint Sub goals: There are the goal which depends on more than one sub- goals.

To “provide for old age”, not only need to “Earn more money” ,but also need to “Save money”. Constraint satisfaction in the process of generating solution that satisfies all the specified constraints for a given problem. There are variable which needs to get assigned values from a specific domain.

To generate the solution it uses backtracking mechanism. The optimal solution is the one in which is generated in minimum number of backtracks and satisfies all the constraints thereby assigning proper values to each of the variable.

There are multiple fields having applications of constraint satisfaction. Artificial Intelligence. Programming Languages, Symbolic Computing and computational logic are few of them to name.

Example: N- queen problem, as in this problem the queens are the variables to whom a position in an n*n Matrix need to be assigned which is a value for those variables. Also the problem States some conditions on placement of those Queens that is no two queens can clash either horizontally, vertically or diagonally.

Generate and test: It is the simplest form of searching technique. Generate and test method first generate a node in the search tree and then checks for whether it's goal node. It involves two processes as shown

1. Generate the successor node.

2. Test to match it with each of the proposed goal node.

As there are many unfruitful nodes gets generated during this process, it’s not a very efficient technique. E.g.: Problem of opening a combination lock by trial and error technique without knowing the combination.

Rule based system:

Rule based system are the simplest and most useful systems. In its simplest form they have set of rules, an interpreter and input from the environment. Rules are of the form IF< Condition>THEN<action>.

Rule based system components are as follows:

1. Working memory or knowledge base: It stores the facts of the outside world that are observed currently. It may take a form of a triplet <object ,attribute="" ,value="">. For example: To represent the fact that “The color of my car is black”, the knowledgebase will store<car, color="" black="">triplet.

2. Rule base: what will be the basic part of the system it contains all the rules rules are generated from the domain knowledge and can be used for modification based on the current observations.

For example: If <(temperature, over, 20)>

Then <add (ocean,="" swimabel,="" yes)&gt;<="" p="">

While using a particular rule, first the conditions are matched to the current observations and if satisfied then, rule may be fired.

1. Interpreter: It performs a matching of the rule with respect to the current percept observed in the environment. It has three repetitive task to follow: Retrieval of the matching rule, refinement of the rule and execution of the rule by performing the corresponding action.