[(COMP472)Artificial Intelligence] - State Space Representation

< State Space Representation >

: Finding a solution from initial state to a goal state

 

[ State Space ]

·      Problem is represented by

1)    Initial State

-       Starting state

2)    Set of Operators

-       Actions for transition between states

3)    Goal test function

-       determine if it is matched with a goal state

4)    Calculate Path cost function

-       Assigns a cost to a path if a path is best among others

 

·      State space

-       The set of all states that can be reached from the initial sate by any sequence of action

-       Size : state space is too large to be generated in advance so it is generated dynamically while searching in real problem.

è We explore a node : if it’s the goal, stop and trace back to calculate the path(solution path) from the initial node

è If it’s not the goal, then generating it’s successors(children) and explore these recursively

è To avoid cycles, the search algorithm will check duplicate nodes!

 

·      Search Algorithm

-       How the search space is visited

-       Exploration of alternatives

 

[ State Space Graph ]

: each state is represented by a distinct node.

·      An arc(or edge) connects a node s to a node s’ if s’ belongs to SUCCESSOR(s)

-       The state graph may contain more than on connected component.