Artificial Intelligence

Dr. Sanga Chaki

Assistant Professor
Department of Computer Science and Engineering
Indian Institute of Information Technology Pune
Problem Solving by Searching - I
Contents
1. What is a state
2. State space
3. State representations with example – Roomba, Tic-tac-toe
4. What is Problem Solving by Searching?
5. Problem Solving AI Agents - Design
6. Well defined problems
7. Example Problems
8. How to Search for solutions?
9. Measuring problem-solving performance of Search Algorithms
What is a State?
1. All information about the environment
2. A state will comprise of all information necessary (for the agent) to make
a decision for the task at hand
3. To complete the task, we will define a set of states – situations the agent
can be in - Based on this, we can define a state space - Which is a
representation of the input and output for the problem
4. We will put any information relevant to the decision mechanism in each of
those states
5. Further discussions on state and state space done in class.
How to represent a state?
1. Many views
Type State Representation Focus
Atomic 1. States indivisible 1. Search on atomic states
2. Every state is a unique number
3. No internal structure
Factored/Proposi 1. States made of state variables which 1. Search + inference in
tional take values propositional logic
2. Comparison of states is possible
Relational 1. States describe the objects in the world 1. Search + inference in predicate
and their relationships logic

First Order 1. States describe the objects in the 1. Search + inference in first order
world and their relationships + logic
functions over objects
States in the Vacuum World – Atomic View
A B A B
1. Number of possible states = 8
2. State are: S1, S2, …., S8
3. State here is seen as an indivisible snapshot
4. All actions are SXS matrix
5. If we have to search for a goal state, we
search in 8 states
6. If we add a second Roomba, number of
states = 16 – doubles
7. If we consider any other aspect of the room,
say presence of electricity, then number of
possible states = 32 – quadruples and so on
States in the Vacuum (Roomba) World
1. Number of possible states = 8
Location Dirt at L Dirt at R
of
Roomba
0 (L) 0 0
0 (L) 0 1
0 (L) 1 0
0 (L) 1 1
1 (R) 0 0
1(R) 0 1
1(R) 1 0
1(R) 1 1
States in the Vacuum World – Propositional/Factored View
1. Number of possible states = 8 = 23
2. States made of 3 variables (Propositions):
i. Dirt in Left room – T/F
ii. Dirt in Right room – T/F
iii. Location of Roomba – L/R
3. Each state is an assignment of values to these
variables
4. Actions can just mention the variables they
affect
5. Representation is much more compact
6. If we add a second Roomba -
• No of possible states = 16
• Representation increases by 1 more state
variable only.
States in the Vacuum World – Relational View
1. World made of objects:
i. Roomba
ii. Left Room
iii. Right Room
2. Relations:
i. In(<Agent>, <Room>)
ii. IsDirty(<Room>)
3. If we add a second Roomba or more rooms –
only the objects increase
4. If we want to consider presence/absence of
electricity in a room, one more relation is
added.
States in Search: Example Tic-Tac-Toe

Discussed in
class
Problem Solving by Searching
1. Automated Problem Solving by Searching
2. Problem Solving:
• Is the major aim of AI
• Can be done through AI agents
• Reflex agents are simple: Cannot operate well in many real-world problems
• Goal-based (and utility-based) agents consider future actions and the
desirability of their outcomes
3. Here, we will discuss problem-solving agents:
• one kind of goal-based agent
• performance measure related to a goal
4. What is search in problem solving?
• We want to search for a way/path to achieve our goal of solving problems
Problem-solving Agent’s Design
Goal Formulation – Related Concepts
1. Goals help organize behavior by
• limiting the objectives that the agent is trying to achieve
• and hence the actions it needs to consider.
2. Goal formulation is the first step in problem solving.
3. Always based on
• Agent’s current situation
• and the agent’s performance measure
4. A goal state of an agent is a set of world states for the agent in which the goal is satisfied.
• There might be more than one world state that satisfies a goal.
5. There might be more than one goal
6. There might be more than one action that helps in reaching a goal.
7. A goal is said to be achieved when the agent’s action(s) have led to one of these world states in
which the goal is satisfied
8. The agent’s task is to find out how to act, now and in the future, so that it reaches a goal state.
Problem, Solution & Search in Agent Terminology
1. Before it can do this, it needs to be decided what sort of actions and states
it should consider.
2. Problem formulation is the process of deciding what actions and states to
consider at each step, given a goal.
3. The solution to any problem is a fixed sequence of actions – there can be
many possible solutions to a problem
4. The process of looking for a sequence of actions that reaches the goal is
called search
5. A search algorithm takes a problem as input and returns a solution in the
form of an action sequence.
6. Once a solution is found, the actions it recommends can be carried out –
This is called the execution phase
Simple Agent Design
1. Simple formulate, search, execute design for the agent
i. Form goal
ii. Form problem to solve
iii. Call Search procedure to solve problem – find the sequence of actions
iv. Use the solution to guide its actions
v. One step done? Remove that step from the sequence
vi. All done? Present goal achieved? Formulate new goal and continue.
2. While the agent is executing the solution sequence, it ignores its percepts
3. Based on this, can you write the pseudocode for a simple problem-solving
agent?
• Takes percept, returns action
• What are the persistent?
• What are the steps?
Simple PS Agent Design - Pseudocode

Please check reference book for the pseudocode

Well-Defined Problems
How to define problems so that they can be solved by AI agents
Well-defined problems
1. A problem can be defined formally by five components:
a) Initial state and state space
b) Actions
c) Transition model from one state to another
d) Goal test
e) Path and Path Cost
Problem Formulations - Examples
1. Vacuum World Problem Formulation
2. N-Puzzle Problem Formulation
3. The Traveling Agent Problem Formulation
4. Robotic Assembly Agent Problem Formulation
5. The Knuth Problem Formulation
6. N-Queen Problem Formulation
Problem Formulations
1. To formulate a problem as a search problem, we need:
• State space and Initial state
• Actions
• Transition model
• Goal test
• Path and Path Cost
2. From our previous knowledge, how can we formulate the Vacuum World
Problem as a search problem?
The Vacuum World Problem Formulation
1. States: The state is Location Dirt at L Dirt at R
determined by both the of
agent location and the dirt Roomba
locations. 0 (L) 0 0
0 (L) 0 1
2. The agent is in one of two
locations, each of which 0 (L) 1 0
might or might not contain 0 (L) 1 1
dirt. 1 (R) 0 0
3. Thus, there are 2 × 22 = 8 1(R) 0 1
possible world states. 1(R) 1 0
4. A larger environment with n 1(R) 1 1
locations has n · 2n states.
5. Initial state: Any state can be
designated as the initial
state.
The Vacuum World Problem Formulation
1. Actions: Each state has just three actions: Left, Right, and Suck/Clean dirt.
2. Transition model:
• The actions have their expected effects,
• except that moving Left in the leftmost square, moving Right in the
rightmost square, and Cleaning in a clean square have no effect.
3. Goal test: This checks whether all the squares are clean.
4. Path cost: Each step costs 1, so the path cost is the number of steps in the
path.
5. What does the complete state space look like along with the transition
model?
The Vacuum World Problem Formulation
The 8-puzzle Problem Formulation
1. Given: a 3×3 board with 8 tiles (each numbered from 1 to 8) and one empty
space (0) placed on the board
2. The objective is to place the numbers to match the final configuration using
the empty space.
3. We can slide four adjacent tiles (left, right, above, and below) into the
empty space.
The 8-puzzle Problem Formulation
1. States: A state description specifies the location of each of the
eight tiles and the blank in one of the nine squares.
2. Initial state: Any state can be designated as the initial state.
3. Actions: The simplest formulation defines the actions as
movements of the blank space Left, Right, Up, or Down.
• Different subsets of these are possible depending on where
the blank is.
4. Transition model: Given a state and action, this returns the
resulting state; for example, if we apply Left to the start state,
the resulting state has the 5 and the blank switched.
5. Goal test: This checks whether the state matches the goal state
6. Path: each step
7. Path cost: Each step costs 1, so the path cost is the number of
steps in the path.
8. What is the size of state space for this problem?
The Traveling Agent Problem Formulation
To formulate this problem as a well-defined
search problem, we need:
1. Initial state: In(Arad)
2. State space – various cities
3. Actions: drive between connected cities
4. Transition Model: Which action will
take the agent from a starting state to
another state
5. Goal Test: In(Bucharest)
6. Path: Any sequence of cities visited
7. Path cost: Sum of the weights
Fairly simple – entire state space graph can
be seen – WHAT IF WE SCALE THIS
PROBLEM? – Case of Google Maps?
The Robotic Assembly Problem Formulation
The Robotic Assembly Problem Formulation

1. State Space: Real valued coordinates and joint angles of the parts of the object
to be assembled
2. Actions: Continuous motions of the robot: Rotate, Attach etc
3. Goal test: Complete assembly of the object
4. Path cost: Time to execute entire assembly step by step
5. Initial state: Disassembled
6. Path: Sequence of actions performed by the Robot
7. Transition model: How each action affects the assembly as a whole
The Knuth Problem Formulation
1. Devised by Donald Knuth in 1964
2. Illustrates how infinite state spaces can arise.
3. Conjectured that
a) starting with the number 4,
b) a sequence of factorial, square root, and floor operations will reach
c) any desired positive integer
4. For example, we can reach 5 from 4 as follows:
The Knuth Problem Formulation
1. Problem formulation:

2. To our knowledge there is no bound on how large a number might be

constructed in the process of reaching a given target
3. For example, the number 620,448,401,733,239,439,360,000 is generated in the
sequence for generating 5
4. So, the state space for this problem is infinite.
5. Such state spaces arise frequently in tasks involving the generation of
mathematical expressions, circuits, proofs, programs, and other recursively
defined objects.
The n-queens Problem Formulation
1. The goal of the n-queens problem is
to place n queens on a chessboard
such that
• no queen attacks any other.
2. A queen attacks any piece in the
• same row,
Start State
• same column
• or same diagonal.

Goal State
The 8-queens Problem Formulation
There are two main kinds of formulation.
1. An incremental formulation
• involves operators that augment the state description,
• starting with an empty state;
• in each action: add a queen to the state util all n queens are added
2. A complete-state formulation
• starts with all n queens on the board
• In each action: move the queens around to achieve goal state

How can we formulate this problem using these two approaches?

The 8-queens Problem Formulation
The incremental formulation (F1): Assume n = 8
1. Initial state: No queens on the board.
2. State space: Any arrangement of 0 to 8 queens on the board is a state.
3. Actions: Add a queen to any empty square.
4. Transition model: Returns the board with a queen added to the specified
square.
5. Goal test: 8 queens are on the board, none attacked.
6. Path and path cost = Time
What is the size of the state space?
The 8-queens Problem Formulation
1. To accommodate 8 queens, board size = 64 X 64
2. Using this formulation, we have

64 X 63 X 62 X · · · X 57 ≈ 1.8 × 1014 possible sequences (states)

to investigate
The 8-queens Problem Formulation
A better incremental option (F2):
prohibit placing a queen in any square
that is already attacked
1. State space: All possible
arrangements of n queens (0 ≤ n ≤ 8),
one per column in the leftmost n
columns, with no queen attacking
another.
2. Actions: Add a queen to any square
in the leftmost empty column such
that it is not attacked by any other
queen.
The 8-queens Problem Formulation - Tasks
1. For F2, add the other information required for well defined problems for
this one.
a) Goal state
b) Initial state
c) Path and path cost
d) Transition model
2. For F2: what is the size of the state space?
3. For F1: if n = 100, what is the size of the state space? Is it any better using
F2?
4. Define the problem well, using the complete-state formulation.
Searching for Solutions
Searching for Solutions
1. Having formulated some problems, we now need to solve them.
2. A solution is a sequence of actions
3. So, search algorithms work by considering various possible action
sequences.
4. Issues:
a) Is it possible to store the entire state space graph in memory to apply
shortest path algorithms? – No
b) So, how do agents know which possible action sequences to consider? –
Look at the immediate successor states possible to achieve from the
current state.
c) How to know which of the successor states is best to take?
• No way of knowing – Uninformed search strategies
• Some extra info is there which helps in this decision – Informed/Heuristic search
strategies.
Different Search Strategies
1. Broadly two types of search strategies used:
2. Uninformed:
i. Breadth-first search (BFS)
ii. Uniform-cost search (UCS)
iii. Depth-first search (DFS)
iv. Depth-limited search (DLS)
v. Iterative deepening depth-first search (IDDFS)
vi. Bidirectional search
3. Informed (Heuristic)
i. Best-first search/Greedy best-first search
ii. A* search
iii. AO* search
Measuring problem-solving
performance of Search Algorithms
Measuring problem-solving performance
1. To be able to choose between specific search algorithms, we need to know the
criteria that might be used to compare them.
2. We can evaluate an algorithm’s performance in four ways:
i. Completeness: Is the algorithm guaranteed to find a solution when there is one?
ii. Optimality: Does the strategy find the optimal solution?
iii. Time complexity: How long does it take to find a solution?
iv. Space complexity: How much memory is needed to perform the search?
Measuring problem-solving performance
1. In theoretical computer science, the typical measure of complexity is the
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).
2. In AI, the graph is often represented implicitly by the initial state, actions,
and transition model and is frequently infinite.
3. For these reasons, 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 – the number of steps along the
path from the root to the goal
• and m, the maximum length of any path in the state space.
Measuring problem-solving performance
1. Time is often measured in terms of the number of nodes
generated/visited during the search
2. Space is measured in terms of the maximum number of nodes stored in
memory in order to perform the search properly
3. To assess the effectiveness of a search algorithm, we can consider just the
search cost = time and space complexities
4. Or we can also consider total cost which combines the search cost, and the
path cost of the solution found.
To be continued…