MIRPUR UNIVERSITY OF SCIENCE AND TECHNOLOGY (MUST), MIRPUR
DEPARTMENT OF COMPUTER SCIENCE & INFORMATION TECHNOLOGY
Artificial Intelligence
BCS-3604
Lecture 3 : AI Classical Approach- General Problem Solving
Ms. Sania Khadim
Lecturer
Lecture Contents
• Problem Solving
• Problem Solving Task
• Measuring Performance
• Sample Examples of Problem
• References
Artificial Intelligence 3
Problem Solving
• Rational agents1 need to perform sequences of actions in
order to achieve goals.
• Intelligent behavior can be generated by having a look-up
table or reactive policy that tells the agent what to do in
every circumstance, but:
- Such a table or policy is difficult to build
- All contingencies must be anticipated
Artificial Intelligence 4
Problem Solving
•A more general approach is for the agent to have
knowledge of the world and how its actions affect it and be
able to simulate execution of actions in an internal model of
the world in order to determine a sequence of actions that
will accomplish its goals.
•This is the general task of problem solving2 and is
typically
performed by searching2 through an internally modelled
space of world states.
Artificial Intelligence 5
Problem Solving Task
•Given:
-An initial state of the world
-A set of possible actions or operators
that can be performed.
-A goal test that can be applied to a
single state of the world to determine if
it is a goal state.
Artificial Intelligence 6
Problem Solving Task
•Find:
-A solution stated as a path of states and
operators that shows how to transform the
initial state into one that satisfies the goal
test.
•The initial state and set of operators
implicitly define a state space of states of
the world and operator transitions between
them. May be infinite.
Artificial Intelligence 7
Measuring Performance
•Path cost: a function that assigns a cost to a path, typically
by summing the cost of the individual operators in the path.
May want to find minimum cost solution.
•Search cost: The computational time and space (memory)
required to find the solution.
•Generally there is a trade-off between path cost and search
cost and one must satisfice and find the best solution in
the time that is available.
Artificial Intelligence 8
Sample Route Finding Problem
Initial state: Arad
Goal state: Bucharest
Path cost: Number of
intermediate cities, distance
traveled, expected travel time
Artificial Intelligence 9
Sample Sliding Tiles Problem
States: tile locations
Initial state: one specific tile configuration
Operators: move blank tile left, right, up, or
down
Goal: tiles are numbered from one to eight
around the square
Path cost: cost of 1 per move (solution cost
same as number of most or path length)
Artificial Intelligence 10
Sample 8-Queens Problem
States: locations of 8 queens on chess board
Initial state: one specific queens configuration
Operators: move queen x to row y and column z
Goal: no queen can attack another (cannot be in
same row, column, or diagonal)
Path cost: 1 per move
Artificial Intelligence 11
More Realistic Problems
•Route finding
•Travelling salesman problem
•VLSI layout
•Robot navigation
•Web searching
Artificial Intelligence 12
References
1. Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig,
Chapter 2 .
2. Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig,
Chapter 3.
3. The University of Texas and Austin, Artificial Intelligence , Available from:
[Link] [Accessed on 10th May 2020]
Artificial Intelligence 13
THANKS