Tree Search

---

A problem-solving agent is one kind of goal-based agent. We already know that the characteristics of the environment dictate techniques for solving the problem. And the fast search techniques are suitable for known, observable, and deterministic environments.

Environment

Known: the agent knows which states are reached by each action
Observable: the agent always knows the current state
Deterministic: each action has exactly one outcome

Before trying to solve the problem, we need to formulate the problem.

Problem Formulation

• Initial state
• Actions & Cost
• Transition function: Result(state, action) = next state
• State space: include every possible state
• Goal test: which determines whether a given state is a goal state

Map of Rimania

Example

Imagine an agent in the city of Arad, Romania. It wants to reach Bucharest.

• The environment is
  – known: the agent has a map of Romania;
  – observable: each city has a sign indicating its presence to arriving drivers;
  – deterministic: if agent chooses to drive from Arad to Sibiu, it does end up in Sibiu.

• The problem formulation is
  – Initial state: Arad;
  – Actions & Cost: action == drive from city A to city B; cost == distance;
  – Transition function: Result(current city, action) = next city – known from the map;
  – State space: Cities on the map;
  – Goal test: Is state == Bucharest?

After formulated the problem, we now need to solve it.

Tree Search

• Component of a search tree
  – root : initial state
  – nodes: states in state space
  – branches : actions
  – frontier (open list): a queue which contains all leaf nodes available for expansion

//------------informal description of the general tree-search---------------
function TREE-SEARCH(problem) returns a solution, or failure
  initialize the frontier using the initial state of problem
  loop do
    if the frontier is empty then return failure
    choose a leaf node and remove it from the frontier
    if the node contains a goal state then return the corresponding solution
    expand the chosen node, adding the resulting nodes to the frontier
    
//---------------------- node of the search tree-------------------------
function CHILD-NODE(problem, parent, action) returns a node
  return a node with
    STATE = problem.RESULT(parent.STATE, action),
    PARENT = parent, ACTION = action,
    PATH-COST = parent.PATH-COST + problem.STEP-COST(parent.STATE, action)

The node has PARENT pointer, solution is the sequence of actions obtained by following parent pointers back to the root.

Example

Figure above shows the partial search trees for finding a route from Arad to Bucharest

• Component of the search tree
  – root : Arad
  – nodes (shaded): nodes that have been expanded;
  – nodes (outlined in bold): nodes that have been generated but not yet expanded;
  – nodes (dashed lines): nodes that have not yet been generated;
  – branches : parent node -> child node;
  – frontier (open list): nodes outlined in bold;

• Tree-Search
  initial frontier = { Arad };
  step1: remove Arad from frontier;
  step2: current city == goal city ? return solution : do step3.;
  step3: expand current city to adjacent cities: Sibiu, Timisoara, Zerind. Add them to frontier;
  step4: if frontier is not empty, choose a city to expand according to some strategy, and do step234 recurrently;
  step5: if frontier is not empty, return false.

Graph Search

Sometimes redundant paths are unavoidable, e.g. Arad -> Sibiu -> Arad …The way to avoid exploring redundant paths is to remember where one has been.
To do this, we augment the TREE-SEARCH algorithm with a data structure called the explored set (also known as the closed list), which remembers every expanded node.
Newly generated nodes that match previously generated nodes—ones in the explored set or the frontier—can be discarded instead of being added to the frontier. The new algorithm, called GRAPH-SEARCH.

The closed list should be implemented with a hash table to allow efficient checking for repeated states.

------------informal description of the general graphe-search---------------
function GRAPH-SEARCH(problem) returns a solution, or failure
  initialize the frontier using the initial state of problem
  initialize the explored set to be empty
  loop do
    if the frontier is empty then return failure
    choose a leaf node and remove it from the frontier
    if the node contains a goal state then return the corresponding solution
    add the node to the explored set
    expand the chosen node, adding the resulting nodes to the frontier
      only if not in the frontier or explored set

In fact, all search algorithms share the structures above, they vary primarily according to how they choose which state to expand next – the so-called search strategy.

We have two different search strategies, Uninformed Search and Informed Search, which will be covered in next two articles.

Evaluation Criteria for Algorithms

Before we get into the design of specific search strategies, we need to consider the criteria that might be used to choose among them. We can evaluate an algorithm’s 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?

In AI, 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.

Source of pictures for this article:

Russell and Norvig (2010). Artificial Intelligence: A Modern Approach.