Searching Explicit State Spaces
To search in explicit graphs we use markers which are provided across the nodes of the Graph. The initial node is labeled with ‘0’. Then successively give numbering to the nodes along the path to goal.
Breadth First capital search method is employed to find a sequence across the graph. In this method each node is expanded in such a way that marked node puts the next higher integer on all of its unmarked nodes, The process repeats until an integer hits the goal. The path from goal to start node is obtained by decreasing the sequence number along the path.
Feature Based State Spaces
If we label the nodes of graph by features, it is easy to visualize the effects of actions on the states.
In STRIPS system, operators are defined to describe how an action affects features. Each operator is defined by following 3 lists.
1) Precondition List: It specifies the features that must have value 1 or value 0 in order that the action can be applied.
2) Delete List: It specifies the features that have values varies from 0 to 1.
3) Add List: It specifies the features that have values varies from 0 to 1.
We can train a neural network in such a way that it can predict the value of a feature vector at time t from previous feature vector at time t-1.
Graph Notation
Graph is a data structure consisting of a set of node which are connected by arcs. If nodes are connected by directed arcs then such a graph is known as directed graph. If an arc is directed from node x to node y then x is said to be parent of y and y is said to be child of x.
If arcs between two nodes directed from each other then we use edge. A graph containing only edges between nodes is called undirected graph.
A direct tree is subset of directed graph. In directed tree each node has exactly one parent. Root node has no parent and tip node or leaf node contains no successors.
A undirected tree is subset of undirected graph in which there exist only one path along edges between any pair of nodes.
All nodes except the leaf nodes have same number of Successors. Here this number is known as branch factor of the tree.
A path of length K from node x1 to xk, is the sequence of nodes from x1 to xk, in which xi+1 is a successor of xi for i = 1, 2, .... k-1. The cost of a path is calculated by adding Cost of all of the arcs along the path. If there exist multiple paths between two nodes then the path with minimum cost is known as minimal path or optimal path.
A spanning tree of a graph constitute all the paths from each node of graph to a particular node in the graph.
