Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

Recent Post

Search

Friday, 12 April 2019

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.


No comments:

Post a Comment