State Space Search in Artificial Intelligence

The students should understand the state space representation, and gain familiarity with some common problems formulated as state space search problems.

Give a problem description, the student should be able to formulate it in terms of a state space search problem.

The student should understand how implicit state spaces can be unfolded during search.

Understand how states can be represented by features.

Goal directed Agent

• A goal directed agent needs to achieve certain goals.
• Many problems can be represented as a set of states and a set of rules of how one state is transformed to another
• The agent must choose a sequence of actions to achieve the desired goal.

Each state is an abstract representation of the agent's environment. It is an abstraction that denotes a configuration of the agent.

• Initial state : The description of the starting configurantion of the agent
• An action/ operator takes the agent from one state to another state. A state can have a number of successor states.
• A plan is a sequence of actions.
• A goal is a description of a set of desirable states of the world. Goal states are often specified by a goal test which any goal state must satisfy.
• Path cost : path → positive number Usually path cost = sum of step costs. 
• 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 imagining sequences of operators applied to the initial state, and checking which sequence reaches a goal state.

Search Problem

S : the full set of states

S0 : the initial state

A:S→S set of operators

G : the set of final states. G⊆S

Search problem : Find a sequence of actions which transforms the agent from the initial state to a goal state a∈G.

The search problem consists of finding a solution plan, which is a path from the current state to the goal state.

Represent search problems

 * A search problem is represented using a directed graph.

• The states are represented as nodes.
• The allowed actions are represented as arcs.

Searching Process

• Check the current state 
• Execute allowable actions to move to the next state
• 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 until a solution is found or the state space us exhausted.