lOMoARcPSD|22829212

PAI M2 Notes

Artificial Intelligence (Visvesvaraya Technological University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Karthik Karthik (kreddys500@gmail.com)
 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

Module: 2
Problem‐solving: Problem‐solving agents, Example problems, Searching for Solutions,
Uninformed Search Strategies: Breadth First search, Depth First Search, Iterative Deepening
Depth First Search
Textbook 1: Chapter 3- 3.1, 3.2, 3.3, 3.4

Chapter 3
SOLVING PROBLEMS BY SEARCHING
• Agent: It is something which perceives (senses) and acts in an environment.
• Agent Function: The agent function for an agent specifies the action taken by
the agent in response to any percept sequence.
• An agent is anything that can perceive its environment through sensors and acts upon
that environment through actuators.
• Agent can be anything and everything!

PROBLEM-SOLVING AGENTS

• Intelligent agents are supposed to maximize their performance measure.

• Problem-solving agents use atomic representations, —that is, states of the world are
considered as wholes, with no internal structure visible to the problem-solving
algorithms.

• Problem formulation is the process of deciding what actions and states to consider,
given a goal.
• Goal-based agents use more advanced factored or structured representations are usually
• called planning agents.
• Goals help organize behavior by limiting the objectives that the agent is trying to
achieve and hence the actions it needs to consider.
• Goal formulation, based on the current situation and the agent’s performance measure,
is the first step in problem solving.
• Consider a goal to be a set of world states—exactly those states in which the goal is
satisfied. The agent’s task is to find out how to act, now and in the future, so that it
reaches a goal state. Before it can do this, it needs to decide (or we need to decide on its
behalf) what sorts of actions and states it should consider.
• In general, an agent with several immediate options of unknown value can decide what
to do by first examining future actions that eventually lead to states of known value.
• The process of looking for a sequence 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 sequence.

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

• A description of the possible actions available to the agent.

• Once a solution is found, the actions it recommends can be carried out. This is called
the execution phase. Thus, we have a simple “formulate, search, execute” design for
the agent, as shown in Figure below.

A simple problem-solving agent.

• It first formulates a goal and a problem, searches for a sequence of actions that
would solve the problem, and then executes the actions one at a time. When
this is complete, it formulates another goal and starts over.

Well-Defined Problems and Solutions

A problem can be defined formally by five components:

i. The initial state that the agent starts in.
For example, the initial state for our agent in Romania might be described
as In(Arad).
ii. A description of the possible actions available to the agent. Given a
particular state s, ACTIONS(s) returns the set of actions that can be executed
in s. We say that each of these actions is applicable in s.
For example, from the state In(Arad), the applicable actions are:
{Go(Sibiu), Go(Timisoara), Go(Zerind)}.
iii. A description of what each action does; the formal name for this is the
transition model, specified by a function RESULT (s, a) that returns the state
that results from doing action a in state s. We also use the term successor to

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

refer to any state reachable from a given state by a single action. For
example, we have
RESULT(In(Arad),Go(Zerind)) = In(Zerind) .
Together, the initial state, actions, and transition model implicitly
define the state space of the problem—the set of all states reachable from the
initial state by any sequence of actions. A path in the state space is a sequence
of states connected by a sequence of actions.
iv. The goal test, which determines whether a given state is a goal state.
Sometimes there is an explicit set of possible goal states, and the test simply
checks whether the given state is one of them.
The agent’s goal in Romania is the singleton set {In (Bucharest)}
v. A path cost function that assigns a numeric cost to each path. The problem-
solving agent chooses a cost function that reflects its own performance
measure. The step cost of taking action, a in state, s to reach state, s is
denoted by c (s, a, s’). The step costs for Romania are shown in Figure below
as route distances.

A simplified road map of part of Romania

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

• A solution to a problem is an action sequence that leads from the initial

state to a goal state.
• Solution quality is measured by the path cost function, and an optimal
solution has the lowest path cost among all solutions.

Formulating Problems

• The process of removing detail from a representation is called abstraction.

• The abstraction is valid if we can expand any abstract solution into a solution in the more
detailed world; a sufficient condition is that for every detailed state.
• The abstraction is useful if carrying out each of the actions in the solution is easier than
the original problem; in this case they are easy enough that they can be carried out
without further search or planning by an average driving agent.
• The choice of a good abstraction thus involves removing as much detail as possible while
retaining validity and ensuring that the abstract actions are easy to carry out.

EXAMPLE PROBLEMS
• A toy problem is intended to illustrate or exercise various problem-solving methods. It
can be given a concise, exact description and hence is usable by different researchers to
compare the performance of algorithms.
• A real-world problem is one whose solutions people actually care about. Such problems
tend not to have a single agreed-upon description, but we can give the general flavor of
their formulations.

Standardized Problems

A. Toy Problem

- Let us examine the toy problem - vacuum world.

- This can be formulated as a problem as follows:

• States: The state is determined by both the agent location and the dirt locations.
The agent is in one of two locations, each of which might or might not contain
dirt. Thus, there are 2 × 22 = 8 possible world states.
• Initial state: Any state can be designated as the initial state.
DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

• Actions: In this simple environment, each state has just three actions: Left,
Right, and Suck. Larger environments might also include Up and Down.
• Transition model: The actions have their expected effects, except that moving
Left in the leftmost square, moving Right in the rightmost square, and Sucking
in a clean square have no effect. The complete state space is shown in Figure
below.
• Goal test: This checks whether all the squares are clean.
• Path cost: Each step costs 1, so the path cost is the number of steps in the path.

B. 8-Puzzle Problem

- The 8-puzzle, an instance of which is shown in Figure below, consists of a 3×3 board
with eight numbered tiles and a blank space.
- A tile adjacent to the blank space can slide into the space. The object is to reach a
specified goal state, such as the one shown on the right of the figure.

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

- The standard formulation is as follows:

• States: A state description specifies the location of each of the eight tiles and the
blank in one of the nine squares.
• Initial state: Any state can be designated as the initial state. Note that any given
goal can be reached from exactly half of the possible initial states
• 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.
• Transition model: Given a state and action, this returns the resulting state; for
example, if we apply Left to the start state in Figure 3.4, the resulting state has the
5 and the blank switched.
• Goal test: This checks whether the state matches the goal configuration shown in
Figure.
• Path cost: Each step costs 1, so the path cost is the number of steps in the path.

C. 8-Queens Problem:

- The goal of the 8-queens problem is to place eight queens on a chessboard such that
no queen attacks any other. (A queen attacks any piece in the same row, column or
diagonal.)
- Figure shows an attempted solution that fails: the queen in the rightmost column is
attacked by the queen at the top left.

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

- There are two main kinds of formulation.

i. An incremental formulation involves operators that augment the state
description, starting with an empty state; for the 8-queens problem, this
means that each action adds a queen to the state.
ii. A complete-state formulation starts with all 8 queens on the board and
moves them around.
- In either case, the path cost is of no interest because only the final state counts.
- The first incremental formulation is as following:
• States: Any arrangement of 0 to 8 queens on the board is a state.
• Initial state: No queens on the board.
• Actions: Add a queen to any empty square.
• Transition model: Returns the board with a queen added to the specified square.
• Goal test: 8 queens are on the board, none attacked.

D. Knuth’s Problem

• Our final toy problem was devised by Donald Knuth (1964) and illustrates how
infinite state spaces can arise.
• Knuth conjectured that, starting with the number 4, a sequence of factorial,
square root, and floor operations will reach any desired positive integer.
• For example, we can reach 5 from 4 as follows:

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

Real – World Problems

A. Airline Travel-Planning Systems

- Consider the airline travel problems that must be solved by a Travel-Planning Web site:
• States: Each state obviously includes a location (e.g., an airport) and the
current time.
• Initial state: This is specified by the user’s query.
• Actions: Take any flight from the current location, in any seat class, leaving
after the current time, leaving enough time for within-airport transfer if needed.
• Transition model: The state resulting from taking a flight will have the flight’s
destination as the current location and the flight’s arrival time as the current
time.
• Goal test: Are we at the final destination specified by the user?
• Path cost: This depends on monetary cost, waiting time, flight time, customs
and immigration procedures, seat quality, time of day, type of airplane,
frequent-flyer mileage awards, and so on.

B. Touring problems
- It is closely related to route-finding problems, but with an important difference.
- Consider, for example, the problem “Visit every city in Figure – Route Map of Romania
at least once, starting and ending in Bucharest.”
- As with route finding, the actions correspond to trips between adjacent cities.
- The state space, however, is quite different.

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

- Each state must include not just the current location but also the set of cities the agent
has visited. So the initial state would be In(Bucharest), Visited({Bucharest}), a typical
intermediate state would be In(Vaslui), Visited({Bucharest, Urziceni, Vaslui}).
- The goal test would check whether the agent is in Bucharest and all 20 cities have been
visited.

C. VLSI Layout
- A VLSI layout problem requires positioning millions of components and connections
on a chip to minimize area, minimize circuit delays, minimize stray capacitances, and
maximize manufacturing yield.
- The layout problem comes after the logical design phase and is usually split into two
parts: cell layout and channel routing. In cell layout, the primitive components of the
circuit are grouped into cells, each of which performs some recognized function.
- Each cell has a fixed footprint (size and shape) and requires a certain number of
connections to each of the other cells.
• States: It might be anywhere on the cell layout
• Initial State: Starting position from where the routing starts.
• Actions: Each channel routing finding a specific route for each wire through
the gaps.
• Transition model: Continuous channel routing between the components.
• Goal: The aim is to place the cells on the chip so that they do not overlap and
so that there is room for the connecting wires to be placed between the cells.
• Path Cost: Time taken for channel routing to finds a specific route for perfect
positioning.

D. Robot Navigation
- Robot navigation is a generalization of the route-finding problem.
- Rather than following a discrete set of routes, a robot can move in a continuous space
with an infinite set of possible actions and states.
- For a circular robot moving on a flat surface, the space is essentially two-dimensional.
- When the robot has arms and legs or wheels that must also be controlled, the search
space becomes many-dimensional.
- Advanced techniques are required just to make the search space finite.

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

- Let us consider a robot moving in a room:

• States: Finite space within the room.
• Initial state: Starting position of the robot.
• Actions: Move to Left or Right, Turn Front or Back, Turn around
• Transition Model: Continuous movements - Move leftward or rightward, Turn
Back or move front.
• Goal: To reach the destination point.
• Path cost: Time taken to reach the destination.

SEARCHING FOR SOLUTIONS

- A solution is an action sequence, so 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 actions and the nodes correspond to states in
the state space of the problem.
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.

The function CHILD-NODE takes a parent node and an action and returns the resulting child
node:

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

- 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 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 element of the queue;
→ The last-in, first-out or LIFO queue (also known as a stack), which pops the newest
element of the queue;
→ The priority queue, which pops the element of the queue with the highest priority
according to some ordering function.

Measuring Problem-Solving Performance

- Let us 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?

BREADTH-FIRST SEARCH
- Breadth-first search 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.
- In general, all the nodes are expanded at a given depth in the search tree before any
nodes at the next level are expanded.
- Since this algorithm searches breadth-wise in a tree or graph, so it is called Breadth-
First Search.
- It is an example of general graph search algorithm.
- It is implemented using FIFO queue data structure

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

Advantages:
- Breadth-first search will provide a solution if any solution exists.
- If there are more than one solution for a given problem, the breadth-first search will
provide minimal solution which requires the least number of steps.
Disadvantages:
- It requires lots of memory since each level of the tree must be saved into memory to
expand the next level.
- Breadth first search needs a lot of time since it reads all the nodes from the root node.
- Let us consider an example, the path between A to G.

- Total number of nodes,

• Complete: Yes.
• Optimal: Yes, if the path cost is non-decreasing function of depth.
• Time complexity: O(bd)
• Space complexity: O(bd), if the search is in finite space.

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

- Another example, shows the path between A and O.

DEPTH-FIRST SEARCH
- Depth first search always expands the deepest node in the current frontier of the search
tree.
- It is a recursive algorithm for traversing a tree or graph data structure, it is called so

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

because it starts from the root node.

- The search proceeds immediately to the deepest level of the search tree, where the
nodes have no successors.
- As those nodes are expanded, they are dropped from the frontier, so then the search
“backs up” to the next deepest node that still has unexplored successors.

- Depth-first search uses a LIFO queue. A LIFO queue means that the most recently
generated node is chosen for expansion.
- A variant of depth-first search called backtracking search uses still less memory.

Advantages:
- It requires very less memory as it only needs to store a stack of the nodes on the path
from root node to the current node.
- It takes less time to reach to the goal node than breadth-first search algorithm.

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

Disadvantages:
- There is the possibility that many states keep re-occurring and there is no guarantee of
finding the solution.
- It goes for deep down searching and sometime it may go to the infinite loop.

Consider an example, to find a path between A and O.

Depth-First Search

• Complete: No (Yes for finite trees).

• Optimal: No
• Time complexity: O(bm) where m – maximum depth
• Space complexity: O(bm), if the search is in finite space

ITERATIVE DEEPENING DEPTH-FIRST SEARCH

- The Iterative Deepening Depth First Search is generally called as IDS (Iterative
Deepening Search).
- Combine the benefits of Depth First search and Breadth First Search to finds the best
solution.
- It gradually increases the limit from 0, 1, 2and so on until reaches the goal.
- It will terminate when the depth limit reaches d, depth of the shallowest goal node.
- It might seem waste of time as the states are generated multiple times but actually not
very costly. Since the last levels are generated only once.
- The overhead of these multiple expansions is small, because most of the nodes are
towards bottom levels of the search tree. Thus, the nodes that are evaluated several
times are relatively small number.
- Iterative depending is the preferred uninformed search method when the search space
is large and the depth of the solution is unknown.

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

Advantages:
- It has the benefits of both DFS and BFS.
- It is a complete and optimal algorithm with modest memory requirements, making it
suitable for searching in large or unknown search spaces.
Disadvantages:
- Repeats the all the processes of previous phase.

Consider an example given below showing the iterative deepening depth-first search
from the node A to G. IDDFS algorithm performs various iterations until it does not
find the goal node. The iteration performed by the algorithm is given as:

1'st Iteration → A
2'nd Iteration → A, B, C
3'rd Iteration → A, B, D, E, C, F, G
4'th Iteration → A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.
• Complete: Yes.
• Optimal: Yes, if the step path cost is 1.
• Time complexity: O(bd)
• Space complexity: O(bd).

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)

 lOMoARcPSD|22829212

PRINCIPLES OF ARTIFICIAL INTELLIGENCE (21AI54)

Comparison between different search strategies

Evaluation of Tree-Search Strategies
b is the branching factor; d is the depth of the shallowest solution; m is the maximum
depth of the search tree
Criterion Breadth First Depth First Iterative Deepening
Search Search DFS
Complete? Yes, if b is finite No Yes, if b is finite
Time O(bd) O(bm) O(bd)
Space O(bd) O(bm) O(bd)
Optimal? Yes, if step cost =1 No Yes, if step cost =1

DEPT OF AI&ML, VKIT MODULE 2 NOTES

Downloaded by Karthik Karthik (kreddys500@gmail.com)