Introduction
This article helps the beginner of an AI course to learn the objective and implementation of Uninformed Search Strategies (Blind Search) which use only information available in the problem definition.
Uninformed Search includes the following algorithms:
- Breadth First Search (BFS)
- Uniform Cost Search (UCS)
- Depth First Search (DFS)
- Depth Limited Search (DLS)
- Iterative Deepening Search (IDS)
- Bidirectional Search (BS)
Background
This article covers several Search strategies that come under the heading of Uninformed Search. The term means that the strategies have no additional information about States beyond that provided in the problem definition. All they can do is generate successors and distinguish a goal state from a non-goal state. All Search strategies are distinguished by the order in which nodes are expanded.
To go ahead in these series, I will use some AI Terminologies such as the following:
A problem can be defined by four components:
- Initial State that the problem starts in
- Goal State that the problem ends in
- Finding sequences of actions that lead to Goal State
- A path Cost to solve problem
Together, the initial state, goal state, actions and path cost define the state space of the problem (the set of all states reachable from the initial state by any sequence of actions). The path in the state space is a sequence of states connected by a sequence of actions. A solution to the problem is an action sequence that leads from the initial state to the goal state.
The process of looking at asequence of actions that reaches the goal is called search. A search algorithm takes a problem as input and returns a solution in the form of an action sequences. The search starts from the initial state which represents the root node in the problem search space. The branches are actions and the nodes corresponding to the states in the problem state space.
Example
A small part of the 8-puzzle problem state space:
Note: Depth=number of steps from initial state to this state.
A collection of nodes that are generated but not yet expanded is called the fringe; each element of fringe is a leaf node (i.e. with no successors in tree).
Let's start to explain the first two algorithms of blind search:
- Breadth First Search (BFS): is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. Fringe is a FIFO queue.
- Uniform Cost Search (UCS): modifies BFS by always expanding the lowest cost node on the fringe using path cost function g(n) (i.e. the cost of the path from the initial state to the node n). Nodes maintained on queue in order of increasing path cost.
- Depth First Search (DFS): always expands the deepest node in the current fringe of the search tree. Fringe is a LIFO queue (Stack).
- Depth Limited Search (DLS): The embarrassing failure of DFS in infinite state spaces can be alleviated by supplying DFS with a predetermined depth limit l, that is nodes at depth l are treated as if they have no successors.
- Iterative Deepening Depth First Search (IDS): is a general strategy often used in combination with depth first tree search that finds the best depth limit. It does this by gradually increasing limit first 0, then 1, then 2, and so on until the goal is found.
- Bidirectional Search (BS): The idea behind bidirectional search is to simultaneously search both forward from the initial state and backward from the goal state, and stop when the two searches meet in the middle. Here there are two fringes, one that maintains nodes forward and other that maintains nodes backward. Each fringe is implemented as LIFO or FIFO depends on the search strategy used in the search (i.e. Forward=BFS, Backward=DFS).
Using the Code
The first class in my code is Node.cs which represents the node as a data structure in the state space. Each node has some attributes such as depth, cost, state, and parent node. The state attribute is defined according to a physical configuration within the problem state space. My code is simply searching for a number in the state space of positive numbers so the state here is defined simply as an integer number.
Let's explore the Node class by the following snippet:
Collapse
// class Node.cs
class Node
{
public int depth;
public int State;
public int Cost;
public Node Parent;
// Parent Node which has depth =0 and parent = null;
public Node (int State)
{
this.State = State;
this.Parent = null;
this.depth = 0;
}
// another form of Node Constructor which accepts only the State;
public Node(int State)
{
this.State = State;
}
// this form of Generalization of Node Constructor which accepts
// any node root or ordinary node;
public Node(int State,Node Parent)
{
this.State = State;
this.Parent = Parent;
if (Parent == null)
this.depth = 0;
else
this.depth = Parent.depth + 1;
}
// this form of Generalization of Node Constructor which accept
// any node root or ordinary node and accept the cost of each node;
public Node(int State, Node Parent, int Cost)
{
this.State = State;
this.Parent = Parent;
this.Cost = Cost;
if (Parent == null)
this.depth = 0;
else
this.depth = Parent.depth + 1;
}
}
My code search is for a number in the range from 0, 1, 2, .N. so, the initial state is 0 and the goal state is the number specified by the user. Each step of number generation costs random number or 1. Class GetSucc.cs defines GetSussessor() function which includes the possible set of actions that are required for positive number generation in order. The input of GetSussessor() is the current state of the problem (i.e. initial State 0) and the output is the ArrayList of next states that are reached from current state(i.e. from 0 the next states 1,2 assuming that our tree is the binary tree).
Collapse
class GetSucc
{
//if search go forward from 0 to number n
public ArrayList GetSussessor(int State)
{
ArrayList Result = new ArrayList();
Result.Add(2 * State + 1);
Result.Add(2 * State + 2);
return Result;
}
//if search go backward from n to number 0
public ArrayList GetSussessor_Reverse(int State)
{
ArrayList Result = new ArrayList();
if (State % 2 == 0)
{
int P = State / 2 - 1;
Result.Add(P);
Result.Add(State - 1);
}
else
{
int Sib = State + 1;
Result.Add(Sib / 2 - 1);
Result.Add(Sib);
}
return Result;
}
//if the cost of each node must be determined
public ArrayList GetSussessor(int State,Node Parent)
{
ArrayList Result = new ArrayList();
Random n = new Random();
Test s = new Test();
Result.Add(new Node(2* State + 1,Parent,n.Next(1,100)+Parent.Cost));
Result.Add(new Node(2* State + 2, Parent,n.Next(1,100) + Parent.Cost));
Result.Sort(s);
return Result;
}
}//end class
//implement the interface IComparer to compare objects in ArrayList
public class Test : IComparer
{
public int Compare(object x, object y)
{
int val1 = ((Node)x).Cost;
int val2 = ((Node)y).Cost;
if (val1 <= val2)
return 1;
else
return 0;
}
}//end class Test
From here, let'sbegin to code the uninformed Search Strategies:
Breadth First Search
Collapse
public static void Breadth_First_Search(Node Start, Node Goal)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Queue Fringe = new Queue();
Fringe.Enqueue(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Dequeue();
Console.WriteLine("Node {0} Visited ", Parent.State);
//Console.ReadKey();
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
break;
}//end if
children = x.GetSussessor(Parent.State);
for (int i = 0; i < children.Count; i++)
{
int State = (int)children[i];
Node Tem = new Node(State, Parent);
Fringe.Enqueue(Tem);
}//end for
}//end while
}//end method
Uniform Cost Search
Collapse
public static void Uniform_Cost_Search(Node Start,Node Goal)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Queue Fringe = new Queue();
Fringe.Enqueue(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Dequeue();
Console.WriteLine("Node {0} Visited with Cost {1} ",
Parent.State,Parent.Cost);
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
break;
}//end if
children = x.GetSussessor(Parent.State,Parent);
for (int i = 0; i < children.Count; i++)
{
Fringe.Enqueue((Node)children[i]);
}//end for
}//end while
}// end method
Depth First Search
Collapse
public static void Depth_First_Search(Node Start, Node Goal)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Stack Fringe = new Stack();
Fringe.Push(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Pop();
Console.WriteLine("Node {0} Visited ", Parent.State);
Console.ReadKey();
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
break;
}//end if
children = x.GetSussessor(Parent.State);
for (int i = 0; i < children.Count; i++)
{
int State = (int)children[i];
Node Tem = new Node(State, Parent);
Fringe.Push(Tem);
}//end for
}//end while
}//end method
Depth Limited Search
Collapse
public static void Depth_Limited_Search(Node Start, Node Goal, int depth_Limite)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Stack Fringe = new Stack();
Fringe.Push(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Pop();
Console.WriteLine("Node {0} Visited ", Parent.State);
// Console.ReadKey();
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
break;
}//end if
if (Parent.depth == depth_Limite)
{
continue;
}
else
{
children = x.GetSussessor(Parent.State);
for (int i = 0; i < children.Count; i++)
{
int State = (int)children[i];
Node Tem = new Node(State, Parent);
Fringe.Push(Tem);
}//end for
}//end else
}//end while
}//end method
Iterative Deepening Search
Collapse
public static void Iterative_Deepening_Search(Node Start, Node Goal)
{
bool Cutt_off = false;
int depth = 0;
while(Cutt_off == false)
{
Console.WriteLine("Search Goal at Depth {0}",depth);
Depth_Limited_Search(Start, Goal, depth,ref Cutt_off);
Console.WriteLine("------");
depth++;
}
}//end method
public static void Depth_Limited_Search(Node Start, Node Goal,
int depth_Limite,ref bool Cut_off)
{
GetSucc x = new GetSucc();
ArrayList children = new ArrayList();
Stack Fringe = new Stack();
Fringe.Push(Start);
while (Fringe.Count != 0)
{
Node Parent = (Node)Fringe.Pop();
Console.WriteLine("Node {0} Visited ", Parent.State);
// Console.ReadKey();
if (Parent.State == Goal.State)
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent.State);
Cut_off = true;
break;
}//end if
if (Parent.depth == depth_Limite)
{
continue;
}
else
{
children = x.GetSussessor(Parent.State);
for (int i = 0; i < children.Count; i++)
{
int State = (int)children[i];
Node Tem = new Node(State, Parent);
Fringe.Push(Tem);
}//end for
}//end else
}//end while
}//end method
Bidirectional Search
Collapse
public static void Bidirectional_Search(Node Start,Node Goal)
{
GetSucc x = new GetSucc();
ArrayList Children_1 = new ArrayList();
ArrayList Children_2 = new ArrayList();
Queue Fringe_IN = new Queue();
Queue Fringe_GO = new Queue();
Fringe_IN.Enqueue(Start);
Fringe_GO.Enqueue(Goal);
while((Fringe_IN.Count !=0)&(Fringe_GO.Count!=0))
{
Node Parent1 = (Node)Fringe_IN.Dequeue();
Console.WriteLine("Node {0} Visited ", Parent1.State);
//Console.ReadKey();
if ((Parent1.State == Goal.State)||Contain(Fringe_GO,Parent1))
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent1.State);
break;
}//end if
Children_1 = x.GetSussessor(Parent1.State);
for (int i = 0; i < Children_1.Count; i++)
{
int State = (int)Children_1[i];
Node Tem = new Node(State, Parent1);
Fringe_IN.Enqueue(Tem);
}//end for
Node Parent2 = (Node)Fringe_GO.Dequeue();
Console.WriteLine("Node {0} Visited ", Parent2.State);
//Console.ReadKey();
if ((Parent2.State == Start.State) || Contain(Fringe_IN,Parent2))
{
Console.WriteLine();
Console.WriteLine("Find Goal " + Parent2.State);
break;
}//end if
Children_2 = x.GetSussessor_Reverse(Parent2.State);
for (int i = 0; i < Children_2.Count; i++)
{
int State = (int)Children_2[i];
Node Tem = new Node(State, Parent2);
Fringe_GO.Enqueue(Tem);
}//end for
}//end while
}//End Method
public static bool Contain(Queue Fringe,Node Parent)
{
object[] S = new object[Fringe.Count];
S = Fringe.ToArray();
for (int i = 0; i < S.Length; i++)
{
Node Target = (Node)S[i];
if (Target.State == Parent.State)
{
return true;
}
}
return false;
}
Reference
- Stuart Russell, Peter Norving, Artificial Intelligence: A Modern Approach
Building Goal-Based Agents
To build a goal-based agent we need to answer the following questions:
- What is the goal to be achieved?
Could describe a situation we want to achieve, a set of properties that we want to hold, etc. Requires defining a "goal test" so that we know what it means to have achieved/satisfied our goal.
This is a hard part that is rarely tackled in AI, usually assuming that the system designer or user will specify the goal to be achieved. Certainly psychologists and motivational speakers always stress the importance of people establishing clear goals for themselves as the first step towards solving a problem. What are your goals???
- What are the actions?
Quantify all of the primitive actions or events that are sufficient to describe all necessary changes in solving a task/goal. No uncertainty associated with what an action does to the world. That is, given an action (also called an operator or move) and a description of the current state of the world, the action completely specifies (1) if that action CAN be applied to the current world (i.e., is it applicable and legal), and (2) what the exact state of the world will be after the action is performed in the current world (i.e., we don't need any "history" information to be able to compute what the new world looks like).
Note also that actions can all be considered as discrete events that can be thought of as occurring at an instant of time. That is, the world is in one situation, then an action occurs and the world is now in a new situation. For example, if "Mary is in class" and then performs the action "go home," then in the next situation she is "at home." There is no representation of a point in time where she is neither in class nor at home (i.e., in the state of "going home").
The number of operators needed depends on the representation used in describing a state (see below). For example, in the 8-puzzle, we could specify 4 possible moves for each of the 8 tiles, resulting in a total of 4*8=32 operators. On the other hand, we could specify four moves for the "blank" square and there would need to be only 4 operators.
- What information is necessary to encode about the the world to sufficiently describe all relevant aspects to solving the goal? That is, what knowledge needs to be represented in a state description to adequately describe the current state or situation of the world?
The size of a problem is usually described in terms of the number of states that are possible. For example, in Tic-Tac-Toe there are about 3^9 states. In Checkers there are about 10^40 states. Rubik's Cube has about 10^19 states. Chess has about 10^120 states in a typical game.
We will use the Closed World Assumption: All necessary information about a problem domain is available in each percept so that each state is a complete description of the world. There is no incomplete information at any point in time.
What's in a state is the knowledge representation problem. That is, we must decide what information from the raw percept data is relevant to keep, and what form the data should be represented in so as to make explicit the most important features of the data for solving the goal. Is the color of the boat relevant to solving the Missionaries and Cannibals problem? Is sunspot activity relevant to predicting the stock market? What to represent is a very hard problem that is usually left to the system designer to specify. How to represent domain knowledge is a topic that will be treated later in the course.
Related to this is the issue of what level of abstraction or detail to describe the world. Too fine-grained and we'll "miss the forest for the trees." Too coarse-grained and we'll miss critical details for solving the problem.
The number of states depends on the representation and level of abstraction chosen. For example, in the Remove-5-Sticks problem, if we represent the individual sticks, then there are 17-choose-5 possible ways of removing 5 sticks. On the other hand, if we represent the "squares" defined by 4 sticks, then there are 6 squares initially and we must remove 3 squares, so only 6-choose-3 ways of removing 3 squares.
Examples
- 8-Puzzle
Given an initial configuration of 8 numbered tiles on a 3 x 3 board, move the tiles in such a way so as to produce a desired goal configuration of the tiles. State = 3 x 3 array configuration of the tiles on the board. Operators: Move Blank square Left, Right, Up or Down. (Note: this is a more efficient encoding of the operators than one in which each of four possible moves for each of the 8 distinct tiles is used.) Initial State: A particular configuration of the board. Goal: A particular configuration of the board. - Missionaries and Cannibals
There are 3 missionaries, 3 cannibals, and 1 boat that can carry up to two people on one side of a river. Goal: Move all the missionaries and cannibals across the river. Constraint: Missionaries can never be outnumbered by cannibals on either side of the river, or else the missionaries are killed. State = configuration of missionaries and cannibals and boat on each side of the river. Operators: Move boat containing some set of occupants across the river (in either direction) to the other side. - Cryptarithmetic
Find an assignment of digits (0, ..., 9) to letters so that a given arithmetic expression is true. For example, SEND + MORE = MONEY Note: In this problem, unlike the two above, the solution is NOT a sequence of actions that transforms the initial state into the goal state, but rather the solution is simply finding a goal node that includes an assignment of digits to each of the distinct letters in the given problem. - Remove 5 Sticks
Given the following configuration of sticks, remove exactly 5 sticks in such a way that the remaining configuration forms exactly 3 squares. - - -
- | | |
- - -
- | | |
- - -
- | | |
- - -
- Water Jug Problem
Given a 5-gallon jug and a 2-gallon jug, with the 5-gallon jug initially full of water and the 2-gallon jug empty, the goal is to fill the 2-gallon jug with exactly one gallon of water. - State = (x,y), where x = number of gallons of water in the 5-gallon jug and y is gallons in the 2-gallon jug
- Initial State = (5,0)
- Goal State = (*,1), where * means any amount
- Operators
- (x,y) -> (0,y) ; empty 5-gal jug
- (x,y) -> (x,0) ; empty 2-gal jug
- (x,2) and x<=3 -> (x+2,0) ; pour 2-gal into 5-gal
- (x,0) and x>=2 -> (x-2,2) ; pour 5-gal into 2-gal
- (1,0) -> (0,1) ; empty 5-gal into 2-gal
- State Space (also called the Problem Space)
- (5,0) = Start
- / \
- (3,2) (0,0)
- / \
- (3,0) (0,2)
- /
- (1,2)
- /
- (1,0)
- /
- (0,1) = Goal
Formalizing Search in a State Space