ARTIFICIAL INTELLIGENCE

CSE 3201

Problems, State Spaces and Search

1
 Problem Solving
We want:
– To automatically solve a problem
We need:
– A representation of the problem
– Algorithms that use some strategy to solve the problem defined in that representation

2
 Problem Representation
■ General:
– State space: Set of all possible states for a given problem is known as state space
of the problem.
A problem is divided into a set of resolution steps from the initial state to the goal
state.
– Reduction to sub-problems: a problem is arranged into a hierarchy of sub-problems.

3
 States
■ A problem is defined by its elements and their relations.
■ In each instant of the resolution of a problem, those elements have specific
descriptors (How to select them?) and relations.
■ A state is a representation of those elements in a given moment.

• Two special states are defined:

– Initial state (starting point)
– Final state (goal state)

4
 State Modification: Successor Function
• A successor function is needed to move between different states.
– It is a transformation function on a state representation, which convert it into
another state.
• A successor function is a description of possible actions, a set of operators.

5
 State Space
■ We need to formulate a state space over which we perform search.
A state space consists of:
■ A set of states
- The start state represents the initial problem
- Each state represents some configuration reachable from
the start state
- Some states may be goal states (solutions)
■ A set of operators
-Applying an operator to a state transforms it to another state in the state space

6
 Problem Solution
■ A path in the state space is a sequence of states connected by a sequence of actions.
■ A solution in the state space is a path from the initial state to a goal state or, sometimes,
just a goal state.
■ Path/solution cost: function that assigns a numeric cost to each path.
■ Solution quality is measured by the path cost function, and an optimal solution has the
lowest path cost among all solutions.

7
 Problem Description
■ Components:
– State space
– Initial state
– Goal state (or the conditions it has to fulfill)
– Available actions (operators to change state)
– Restrictions (e.g., cost)

8
Example: 8-puzzle

9
 Example: 8-puzzle
• State space: configuration of the eight tiles on the
board
• Initial state: any configuration
• Goal state: tiles in a specific order
• Operators or actions: “blank moves”
– Condition: the move is within the board
– Transformation: blank moves Left, Right, Up, or
Down
• Solution will be a sequence of moves of the blank
that transform the initial state to goal state.

Here, our goal condition is satisfied by only a single

state.

10
Example: n-queens

11
 Example: n-queens

■ State space: configurations from 0 to n queens on the board with only one queen per row
and column
• Initial state: configuration without queens on the board
• Goal state: configuration with n queens such that no queen attacks any other
• Operators or actions: place a queen on the board
- Condition: the new queen is not attacked by any other already placed
- Transformation: place a new queen in a particular square of the board
• Solution: solution after fulfilling the criteria.

12
 Structure of the state space
■ Data structures:
– Trees: only one path to a given node
– Graphs: several paths to a given node
■ Operators: directed arcs between nodes
■ The search process explores the state space.
■ In the worst case all possible paths between the initial state and the goal state are
explored.

13
 To build a system to solve a problem
1. Define the problem precisely
2. Analyze the problem
3. Isolate and represent the task knowledge that is necessary to solve the problem
4. Choose the best problem-solving techniques and apply it to the particular problem.

14
 Defining the problem as State Space
Search
■ Search is a very important process in the solution of hard problems for which no more
direct techniques are available.

15
 Example: Romania

■ On holiday in Romania; currently in

Arad.
■ Flight leaves tomorrow from Bucharest
■ Formulate goal:
– be in Bucharest
■ Formulate problem:
– states: various cities
– actions: drive between cities
■ Find solution:
– sequence of cities, e.g., Arad,
Sibiu, Fagaras, Bucharest

16
 State-Space : Problem Formulation
A problem is defined by four items:

■ initial state e.g., "at Arad“

■ actions or successor function : Given a particular state s, action(s) returns the set of actions is
applicable in s. For example, from the state In(Arad), the applicable actions are {Go(sibiu),
Go(Timisoara), GO(Zerind)}
■ goal test, (or goal state)
e.g., x = "at Bucharest”, Checkmate(x)
■ path cost (additive)
– e.g., sum of distances, number of actions executed, etc.
– c(x,a,y) is the step cost, assumed to be ≥ 0
■ A solution is a sequence of actions leading from the initial
state to a goal state.

17
 Defining Search Problems
■ A statement of a Search problem has 4 components
– 1. A set of states
– 2. A set of “operators” which allow one to get from one state to another
– 3. A start state S
– 4. A set of possible goal states, or ways to test for goal states
– 4a. Cost path
• A solution consists of
– a sequence of operators which transform S into a goal state G

18
19
 Water Jug Problem
■ You are given two jugs, a 4-litre one and a 3-litre one.
■ Neither has any measuring markers on it.
■ There is a pump that can be used to fill the jugs with water.
■ How can you get exactly 2 liters of water into 4-litre jug.

20
 State Space Search: Water Jug Problem
■ State: (x, y) where,
x = 0, 1, 2, 3, or 4
y = 0, 1, 2, 3
■ Start state: (0, 0).
■ Goal state: (2, n) for any n.
■ Attempting to end up in a goal state.

21
Production Rules for Water Jug Problem

22
Production Rules for Water Jug Problem

23
State Space Search: Water Jug Problem
1. Current state = (0, 0)
2. Loop until reaching the goal state (2, 0)
- Apply a rule whose left side matches the current state
- Set the new current state to be the resulting state
(0, 0)
(0, 3)
(3, 0)
(3, 3)
(4, 2)
(0, 2)
(2, 0) 24
 To Solve Water Jug Problem
■ Required a control structure that loops through a
simple cycle in which some rule whose left side
matches the current state is chosen the appropriate
change to the state is made as described in the
corresponding right side, and the resulting state is
checked to see if it corresponds to goal state.

25
Try it: Measuring Problem– Water Jug Problem!
■ Problem: Using these three buckets, measure 7 liters of water.

26
Measuring Problem!

27
Measuring Problem!

28
 State Space Tree
■ State space tree is a tree constructed from all of the possible states of the problem as
nodes, connected via state transitions from some initial state as root to some terminated
state as leaf.

■ If the entire state space representations for a problem is given, it is possible to trace the
path from initial state to the goal state and identify the sequence of operators necessary
for doing it.

29
State Space Tree for Water-Jug Problem

30
 Sum of subsets
■ Problem:
Given n positive integers w1, ... wn and a positive integer S. Find all subsets of w1, ... wn that
sum to S.

■ Example:
n=3, S=6, and w1=2, w2=4, w3=6

■ Solutions:
{2,4} and {6}

31
 Sum of subsets
■ We will assume a binary state space tree.
■ The nodes at depth 1 are for including (yes, no) item 1, the nodes at depth 2 are for item
2, etc.
■ The left branch includes wi, and the right branch excludes wi.
■ The nodes contain the sum of the weights included so far.

32
Sum of subset Problem: State Space Tree
w1 = 2, w2 = 4, w3 = 6 and S = 6

0
yes no

i1 2 0
yes no yes no

i2 6 2 4 0

yes no yes no yes no yes no

i3 12 6 8 2 10 4 6 0

The sum of the included integers is stored at the node.

33
 Backtracking
■ Definition: We call a node nonpromising if it cannot lead to a feasible (or optimal)
solution, otherwise it is promising.

■ Main idea: Backtracking consists of doing a DFS of the state space tree, checking
whether each node is promising and if the node is non-promising, then backtrack to the
node’s parent.

34
 Backtracking
■ The state space tree consisting of expanded nodes only is called the pruned state space
tree.
■ The following slide shows the pruned state space tree for the sum of subsets example.
■ There are only 15 nodes in the pruned state space tree.
■ The full state space tree has 31 nodes.

35
 A Pruned State Space Tree
(find all solutions)
w1 = 3, w2 = 4, w3 = 5, w4 = 6; S = 13
0
3 0

3 0
4 0 4 0

7 3 4 0

5 0 5 0 5 0

12 7 8 3 9 4
6 0

13 7

Sum of subsets problem

36
 Farmer River Crossing Problem
■ A farmer with his wolf, goat and cabbage come to the edge of a river. They all want to
cross the river. There is a boat at the river’s edge, but only the farmer can row, the boat
can carry two things at a time. If the wolf is ever left alone with the goat, the wolf will
eat the goat. Similarly, if the goat is left alone with the cabbage, the goat will eat the
cabbage.

37
Solution

38
Sequence of Steps

39
State Space Representation

40
Missionaries and Cannibals Problem

41
Missionaries and Cannibals Problem

42
Missionaries and Cannibals Problem

43
Missionaries and Cannibals Problem

44