Searching for Solutions

The Concept of State Space

• One general formulation of intelligent action is in terms of a state space.
• A state contains all the information necessary to predict the effects of an action and to determine whether a state satisfies the goal.

State-space searching assumes:

• The agent has perfect knowledge of the state space.
• At any time, it knows what state it is in; the world is thus fully observable.
• The agent has a set of actions with known the effects.
• The agent has a goal to achieve and can determine whether a state satisfies the goal.
• A solution to a search problem is a sequence of actions that will get the agent from its current state to a state that satisfies the goal.

​

The Concept of State Space

• A state-space search problem consists of:
• a set of states
• a distinguished state called the start state
• for each state, a set of actions available to the agent in that state
• an action function that, given a state and an action, returns a new state
• a goal specified as a Boolean function, goal(s), that is true when state s satisfies the goal, in which case s is a goal state
• a criterion that specifies the quality of an acceptable solution;
• for example, any sequence of actions that gets the agent to the goal state may be acceptable, or there may be costs associated with actions and the agent may be required to find a sequence that has minimal total cost.
• A solution that is best according to some criterion is called an optimal solution.

​

Searching for solution

• A solution is an action sequence.
• Search algorithms work by considering various possible action sequences.
• The possible action sequences, starting at the initial state form a search tree with:

- The initial state at the root

- The branches are the actions and the nodes correspond to states in the state space of the problem.

Searching for solution. Example

• The root node of the tree corresponds to the initial state,

In(Arad).

• The first step is to test whether this is a goal state.
• Then we need to consider taking various actions.

- we do this by expanding the current state

- Applying each legal action to the current state, thereby

generating a new set of states (Transition model)

We add three branches from the parent node In(Arad)

leading to three new child nodes:

- In(Sibiu)

- In(Timisoara)

- In(Zerind)

Now we must choose which of these three possibilities

to consider further.

​

Searching for solution. Example

• Suppose we choose Sibiu first.
• we check to see whether it is a goal state (it is not)

and then expand it to get In(Arad), In(Fagaras),

In(Oradea), and In(RimnicuVilcea)

• We can then choose any of these four

or go back and choose Timisoara or Zerind

• Each of these six node is a leaf node
• Leaf node: a node with no children in the tree
• Frontier: The set all leaf nodes available for expansion at

any given point is called the frontier.

- tree consists of those nodes with bold outlines.

• The process of expanding nodes on the frontier continues until

either a solution is found or there are no more states to expand.

​

Search Algorithms

• Search algorithms all share this basic structure; they vary primarily according to how they choose which state to expand next so-called search strategy.
• it includes the path from Arad to Sibiu and back to Arad again! We say that In(Arad) is a repeated state in the search tree, generated in this case by a loopy path.
• Loopy paths are a special case of the more general concept of redundant paths, which exist whenever there is more than one way to get from one state to another.
• The TREE-SEARCH algorithm does not remember previously explored states. Therefore, it may generate repeated states, explore redundant paths, and even get stuck in loops.
• The way to avoid exploring redundant paths is to remember where one has been.
• the GRAPH-SEARCH algorithm with a data structure called the explored set (also known as the closed list), which remembers every expanded node.
• Newly generated states that match states already in the explored set or the frontier can be discarded instead of being added to the frontier.
• the search tree constructed by the GRAPH-SEARCH algorithm contains at most one copy of each state, so we can think of it as growing a tree directly on the state-space graph.

Search Algorithms

Search Algorithms

Search Algorithms

The algorithm has another nice property:

• The frontier separates the state-space graph into the explored region and the unexplored region, so that every path from the initial state to an unexplored state must pass through a state in the frontier.
• As every step moves a state from the frontier into the explored region while moving some states from the unexplored region into the frontier, we see that the algorithm is systematically examining the states in the state space, one by one, until it finds a solution.

Infrastructure for search algorithms

• Search algorithms require a Data structure to keep track of the search tree that is being constructed.

​

​

​

​

​

• For each node n of the tree, we have a structure that contains four components:
• n.STATE: the state in the state space to which the node corresponds.
• n.PARENT: the node in the search tree that generated this node.
• n.ACTION: the action that was applied to the parent to generate the node.
• n.PATH-COST: the cost, traditionally denoted by g(n), of the path from the initial state to the node, as indicated by the parent pointers.

​

​

Data structures to keep track of the search tree

• Given the components for a parent node, it is easy to see how to compute the necessary components for a child node.
• The function CHILD-NODE takes a parent node and an action and returns the resulting child node:

​

​

​

​

​

​

• The PARENT pointers string the nodes together into a tree structure.
• These pointers also allow the solution path to be extracted when a goal node is found.
• we use the SOLUTION function to return the sequence of actions obtained by following parent pointers back to the root.

​

Data structures to keep track of the search tree

Nodes Vs States:

- A node is a bookkeeping data structure used to represent the search tree.

- A state corresponds to a configuration of the world.

• Nodes are on particular paths, as defined by PARENT pointers, whereas states are not
• Two different nodes can contain the same world state if that state is generated via two different search paths.

​

​

​

The queue data structure

• The frontier needs to be stored in such a way that the search algorithm can easily choose the next node to expand according to its preferred strategy. The appropriate data structure for this is a queue.

The operations on a queue data structure are as follows:

- EMPTY?(queue) returns true only if there are no more elements in the queue.

- POP(queue) removes the first element of the queue and returns it.

- INSERT(element, queue) inserts an element and returns the resulting queue.

- Queues are characterized by the order in which they store the inserted nodes

- Three common variants are:

- The first-in, first-out or FIFO queue, which pops the oldest of the queue.

- The last-in, first-out or LIFO queue (also known as stack), which pops newest element.

- The priority queue which pops the element of the queue with the highest priority according to some ordering function.

​

​

​

​

​

​

​

Measuring problem-solving performance

- We can evaluate an algorithms performance in four ways:

- Completeness: is the algorithm guaranteed to find a solution when there is one?

- Optimality: Does the strategy find the optimal solution?

- Time complexity: How long does it take to find a solution?

- Space complexity: How much memory is needed to perform the search?

- For S&T complexity, the typical measure is size of the state space graph, |V|+|E|.

- where V is the set of vertices(nodes) of the graph and E is the set of edges (links).

​

​

​

Measuring problem-solving performance

• In AI, the graph is often represented implicitly by the initial state, actions, and transition model and is frequently infinite.
• complexity is expressed in terms of three quantities:
• b, the branching factor or maximum number of successors of any node;
• d, the depth of the shallowest goal node (i.e., the number of steps along the path from the root);
• m, the maximum length of any path in the state space.
• Time is often measured in terms of the number of nodes generated during the search.
• Space in terms of the maximum number of nodes stored in memory.

​