Anna University Regulation 2013 Information Technology (IT) CS6659 AI Notes for all 5 units are provided below. Download link for IT 6th SEM CS6659 Artificial Intelligence Lecture Notes are listed down for students to make perfect utilization and score maximum marks with our study materials.

Search:

Formulate a problem as a state space search by showing the legal problem states, the legal operators, and the initial and goal states .

• A state is defined by the specification of the values of all attributes of interest in the world

• An operator changes one state into the other; it has a precondition which is the value of certain attributes prior to the application of the operator, and a set of effects, which are the attributes altered by the operator

• The initial state is where you start

• The goal state is the partial description of the solution

State Space Search Notations

The set of notations involved in the state space search is :

1) An initial state is the description of the starting configuration of the agent

2) An action or an operator takes the agent from one state to another state which is called a successor state. A state can have a number of successor states.

3) A plan is a sequence of actions. The cost of a plan is referred to as the path cost.

Problem formulation & Problem Definition

Problem formulation means choosing a relevant set of states to consider, and a feasible set of operators for moving from one state to another.

Search is the process of considering various possible sequences of operators applied to the initial state, and finding out a sequence which culminates in a goal state.

A search problem consists of the following:

• S: the full set of states

• s0 : the initial state

• A:S→S is a set of operators

• G is the set of final states. Note that G ⊆S The search problem is to find a sequence of actions which transforms the agent from the initial state to a goal state g∈G.

A simple search procedure is

Do until a solution is found or the state space is exhausted.

1. Check the current state

2. Execute allowable actions to find the successor states.

3. Pick one of the new states.

4. Check if the new state is a solution state

If it is not, the new state becomes the current state and the process is repeated

Basic Search Algorithm is

Let L be a list containing the initial state (L= the fringe)

Loop if L is empty return failure

Node <- select (L)

if Node is a goal

then return Node (the path from initial state to Node)

else generate all successors of Node, and merge the newly generated states into L

End Loop

Factors to measure the search Algorithms:

1. Complete

2. Optimal

3. What is the search cost associated with the time and memory required to find a solution?

a. Time complexity b. Space complexity

The different search strategies that we will consider include the following:

1. Blind Search strategies or Uninformed search

a. Depth first search b. Breadth first search

c. Iterative deepening search d. Iterative broadening search

2. Informed Search

3. Constraint Satisfaction Search

Blind search:

Blind search or uninformed search that does not use any extra information about the problem domain.

The two common methods of blind search are:

• BFS or Breadth First Search

• DFS or Depth First Search

Search Tree is helpful for the searching the goal node. The terminologies involved in the search tree is Root Node: The node from which the search starts. Leaf Node: A node in the search tree having no children.

Ancestor/Descendant: X is an ancestor of Y is either X is Y’s parent or X is an ancestor of the parent of Y. If S is an ancestor of Y, Y is said to be a descendant of X.

Branching factor: the maximum number of children of a non-leaf node in the search tree Path: A path in the search tree is a complete path if it begins with the start node and ends with a goal node. Otherwise it is a partial path.

Let Queue be a list containing the initial state

Loop if Queue is empty return failure Node remove-first (fringe)

if Node is a goal

then return the path from initial state to Node

else generate all successors of Node, and

(merge the newly generated nodes into fringe)

add generated nodes to the back of Queue

End Loop

Finds the path of minimal length to the goal.

Requires the generation and storage of a tree whose size is exponential the the depth of the shallowest goal node

Depth First Search

Let Queue be a list containing the initial state

Loop if Queue is empty return failure

Node<-remove-first (fringe)

if Node is a goal

then return the path from initial state to Node

else generate all successors of Node,

and merge the newly generated nodes into Queue

add generated nodes to the front of Queue

End Loop

Depth Limited Search

Let fringe be a list containing the initial state

Loop if fringe is empty return failure

Node<-remove-first (fringe)

if Node is a goal

then return the path from initial state to Node

else if depth of Node = limit return cutoff

else add generated nodes to the front of fringe

End Loop

Depth-First Iterative Deepening (DFID)

If you require any other notes/study materials, you can comment in the below section.