1 of 62

Introduction to Artificial Intelligence

By:

Dr. Mohammad Shoab

Week 3

2 of 62

Problem Solving Agents

  • Problem solving agent
    • A kind of “goal based” agent
    • Finds sequences of actions that lead to desirable states.

​

  • The algorithms are uninformed
    • No extra information about the problem other than the definition
      • No extra information
      • No heuristics (rules)

2

Introduction to Artificial Intelligence

Department of Computer Science

3 of 62

Goal Based Agent

3

Goal Based Agent

Environment

Percepts

Actions

What the world

is like now

Sensors

Actuators

What action I

should do now

Goals

State

How the world evolves

What my actions do

What it will be like

if I do action A

Introduction to Artificial Intelligence

Department of Computer Science

4 of 62

Goal Based Agents

  • Assumes the problem environment is:
    • Static
      • The plan remains the same
    • Observable
      • Agent knows the initial state
    • Discrete
      • Agent can enumerate the choices
    • Deterministic
      • Agent can plan a sequence of actions such that each will lead to an intermediate state

​

  • The agent carries out its plans with its eyes closed
    • Certain of what’s going on
    • Open loop system

4

Introduction to Artificial Intelligence

Department of Computer Science

5 of 62

Well Defined Problems and Solutions

  • A problem
    • Initial state
    • Actions and Successor Function
    • Goal test
    • Path cost

5

Introduction to Artificial Intelligence

Department of Computer Science

6 of 62

Example: Water Pouring

  • Given a 4 gallon bucket and a 3 gallon bucket, how can we measure exactly 2 gallons into one bucket?
    • There are no markings on the bucket
    • You must fill each bucket completely

6

Introduction to Artificial Intelligence

Department of Computer Science

7 of 62

Example: Water Pouring

  • Initial state:
    • The buckets are empty
    • Represented by the tuple ( 0 0 )

​

  • Goal state:
    • One of the buckets has two gallons of water in it
    • Represented by either ( x 2 ) or ( 2 x )

​

  • Path cost:
    • 1 per unit step

7

Introduction to Artificial Intelligence

Department of Computer Science

8 of 62

8

Introduction to Artificial Intelligence

Department of Computer Science

9 of 62

Example: Eight Puzzle

9

  • States:
    • Description of the eight tiles and location of the blank tile
  • Successor Function:
    • Generates the legal states from trying the four actions {Left, Right, Up, Down}
  • Goal Test:
    • Checks whether the state matches the goal configuration
  • Path Cost:
    • Each step costs 1

1

2

3

​

4

6

7

5

8

1

2

3

4

5

6

7

8

​

Introduction to Artificial Intelligence

Department of Computer Science

10 of 62

Example: Eight Puzzle

  • Eight puzzle is from a family of “sliding –block puzzles”
    • NP Complete
    • 8 puzzle has 9!/2 = 181440 states
    • 15 puzzle has approx. 1.3*1012 states
    • 24 puzzle has approx. 1*1025 states

10

Introduction to Artificial Intelligence

Department of Computer Science

11 of 62

Other Toy Examples

11

Introduction to Artificial Intelligence

Department of Computer Science

12 of 62

Example: Map Planning

12

Introduction to Artificial Intelligence

Department of Computer Science

13 of 62

Searching For Solutions

  • Initial State
    • e.g. “At Arad”
  • Successor Function
    • A set of action state pairs
    • S(Arad) = {(Arad->Zerind, Zerind), …}
  • Goal Test
    • e.g. x = “at Bucharest”
  • Path Cost
    • sum of the distances traveled

13

Introduction to Artificial Intelligence

Department of Computer Science

14 of 62

Searching For Solutions

  • Having formulated some problems…how do we solve them?

​

  • Search through a state space

​

  • Use a search tree that is generated with an initial state and successor functions that define the state space

14

Introduction to Artificial Intelligence

Department of Computer Science

15 of 62

Searching For Solutions

  • A state is (a representation of) a physical configuration

​

  • A node is a data structure constituting part of a search tree
    • Includes parent, children, depth, path cost

​

  • States do not have children, depth, or path cost

​

  • The EXPAND function creates new nodes, filling in the various fields and using the SUCCESSOR function of the problem to create the corresponding states

15

Introduction to Artificial Intelligence

Department of Computer Science

16 of 62

Searching For Solutions

16

Introduction to Artificial Intelligence

Department of Computer Science

17 of 62

Searching For Solutions

17

Introduction to Artificial Intelligence

Department of Computer Science

18 of 62

Searching For Solutions

18

Introduction to Artificial Intelligence

Department of Computer Science

19 of 62

Uninformed Search Strategies

  • Uninformed strategies use only the information available in the problem definition
    • Also known as blind searching

​

  • Breadth-first search
  • Uniform-cost search
  • Depth-first search
  • Depth-limited search
  • Iterative deepening search

19

Introduction to Artificial Intelligence

Department of Computer Science

20 of 62

Comparing Uninformed Search Strategies

  • Completeness
    • Will a solution always be found if one exists?
  • Time
    • How long does it take to find the solution?
    • Often represented as the number of nodes searched
  • Space
    • How much memory is needed to perform the search?
    • Often represented as the maximum number of nodes stored at once
  • Optimal
    • Will the optimal (least cost) solution be found?

​

20

Introduction to Artificial Intelligence

Department of Computer Science

21 of 62

Comparing Uninformed Search Strategies

  • Time and space complexity are measured in
    • b – maximum branching factor of the search tree
    • m – maximum depth of the state space
    • d – depth of the least cost solution

21

Introduction to Artificial Intelligence

Department of Computer Science

22 of 62

Breadth-First Search

  • Recall from Data Structures the basic algorithm for a breadth-first search on a graph or tree

​

  • Expand the shallowest unexpanded node

​

  • Place all new successors at the end of a FIFO queue

22

Introduction to Artificial Intelligence

Department of Computer Science

23 of 62

Breadth-First Search

23

Introduction to Artificial Intelligence

Department of Computer Science

24 of 62

Breadth-First Search

24

Introduction to Artificial Intelligence

Department of Computer Science

25 of 62

Breadth-First Search

25

Introduction to Artificial Intelligence

Department of Computer Science

26 of 62

Breadth-First Search

26

Introduction to Artificial Intelligence

Department of Computer Science

27 of 62

Properties of Breadth-First Search

  • Complete
    • Yes if b (max branching factor) is finite
  • Time
    • 1 + b + b2 + … + bd + b(bd-1) = O(bd+1)
    • exponential in d
  • Space
    • O(bd+1)
    • Keeps every node in memory
    • This is the big problem; an agent that generates nodes at 10 MB/sec will produce 860 MB in 24 hours
  • Optimal
    • Yes (if cost is 1 per step); not optimal in general

27

Introduction to Artificial Intelligence

Department of Computer Science

28 of 62

Lessons From Breadth First Search

  • The memory requirements are a bigger problem for breadth-first search than is execution time

​

  • Exponential-complexity search problems cannot be solved by uniformed methods for any but the smallest instances

28

Introduction to Artificial Intelligence

Department of Computer Science

29 of 62

Uniform-Cost Search

  • Same idea as the algorithm for breadth-first search…but…
    • Expand the least-cost unexpanded node
    • FIFO queue is ordered by cost
    • Equivalent to regular breadth-first search if all step costs are equal

29

Introduction to Artificial Intelligence

Department of Computer Science

30 of 62

Uniform-Cost Search

  • Complete
    • Yes if the cost is greater than some threshold
    • step cost >= ε
  • Time
    • Complexity cannot be determined easily by d or d
    • Let C* be the cost of the optimal solution
    • O(bceil(C*/ ε))
  • Space
    • O(bceil(C*/ ε))
  • Optimal
    • Yes, Nodes are expanded in increasing order

30

Introduction to Artificial Intelligence

Department of Computer Science

31 of 62

Depth-First Search

  • Recall from Data Structures the basic algorithm for a depth-first search on a graph or tree

​

  • Expand the deepest unexpanded node

​

  • Unexplored successors are placed on a stack until fully explored

31

Introduction to Artificial Intelligence

Department of Computer Science

32 of 62

Depth-First Search

32

Introduction to Artificial Intelligence

Department of Computer Science

33 of 62

Depth-First Search

33

Introduction to Artificial Intelligence

Department of Computer Science

34 of 62

Depth-First Search

34

Introduction to Artificial Intelligence

Department of Computer Science

35 of 62

Depth-First Search

35

Introduction to Artificial Intelligence

Department of Computer Science

36 of 62

Depth-First Search

36

Introduction to Artificial Intelligence

Department of Computer Science

37 of 62

Depth-First Search

37

Introduction to Artificial Intelligence

Department of Computer Science

38 of 62

Depth-First Search

38

Introduction to Artificial Intelligence

Department of Computer Science

39 of 62

Depth-First Search

39

Introduction to Artificial Intelligence

Department of Computer Science

40 of 62

Depth-First Search

40

Introduction to Artificial Intelligence

Department of Computer Science

41 of 62

Depth-First Search

41

Introduction to Artificial Intelligence

Department of Computer Science

42 of 62

Depth-First Search

42

Introduction to Artificial Intelligence

Department of Computer Science

43 of 62

Depth-First Search

43

Introduction to Artificial Intelligence

Department of Computer Science

44 of 62

Depth-First Search

  • Complete
    • No: fails in infinite-depth spaces, spaces with loops
      • Modify to avoid repeated spaces along path
    • Yes: in finite spaces
  • Time
    • O(bm)
    • Not great if m is much larger than d
    • But if the solutions are dense, this may be faster than breadth-first search
  • Space
    • O(bm)…linear space
  • Optimal
    • No

44

Introduction to Artificial Intelligence

Department of Computer Science

45 of 62

Depth-Limited Search

  • A variation of depth-first search that uses a depth limit
    • Alleviates the problem of unbounded trees
    • Search to a predetermined depth l (“ell”)
    • Nodes at depth l have no successors

​

  • Same as depth-first search if l = ∞
  • Can terminate for failure and cutoff

45

Introduction to Artificial Intelligence

Department of Computer Science

46 of 62

Depth-Limited Search

46

Introduction to Artificial Intelligence

Department of Computer Science

47 of 62

Depth-Limited Search

  • Complete
    • Yes if l < d
  • Time
    • O(bl)
  • Space
    • O(bl)
  • Optimal
    • No if l > d

47

Introduction to Artificial Intelligence

Department of Computer Science

48 of 62

Iterative Deepening Search

  • Iterative deepening depth-first search
    • Uses depth-first search
    • Finds the best depth limit
      • Gradually increases the depth limit; 0, 1, 2, … until a goal is found

48

Introduction to Artificial Intelligence

Department of Computer Science

49 of 62

Iterative Deepening Search

49

Introduction to Artificial Intelligence

Department of Computer Science

50 of 62

Iterative Deepening Search

50

Introduction to Artificial Intelligence

Department of Computer Science

51 of 62

Iterative Deepening Search

51

Introduction to Artificial Intelligence

Department of Computer Science

52 of 62

Iterative Deepening Search

52

Introduction to Artificial Intelligence

Department of Computer Science

53 of 62

Iterative Deepening Search

53

Introduction to Artificial Intelligence

Department of Computer Science

54 of 62

Iterative Deepening Search

  • Complete
    • Yes
  • Time
    • O(bd)
  • Space
    • O(bd)
  • Optimal
    • Yes if step cost = 1
    • Can be modified to explore uniform cost tree

54

Introduction to Artificial Intelligence

Department of Computer Science

55 of 62

Lessons From Iterative Deepening Search

  • Faster than BFS even though IDS generates repeated states
    • BFS generates nodes up to level d+1
    • IDS only generates nodes up to level d

​

  • In general, iterative deepening search is the preferred uninformed search method when there is a large search space and the depth of the solution is not known

55

Introduction to Artificial Intelligence

Department of Computer Science

56 of 62

Avoiding Repeated States

  • Complication of wasting time by expanding states that have already been encountered and expanded before
    • Failure to detect repeated states can turn a linear problem into an exponential one

​

  • Sometimes, repeated states are unavoidable
    • Problems where the actions are reversable
      • Route finding
      • Sliding blocks puzzles

56

Introduction to Artificial Intelligence

Department of Computer Science

57 of 62

Avoiding Repeated States

57

State Space

Search Tree

Introduction to Artificial Intelligence

Department of Computer Science

58 of 62

Avoiding Repeated States

58

Introduction to Artificial Intelligence

Department of Computer Science

59 of 62

The End

59

Introduction to Artificial Intelligence

Department of Computer Science

60 of 62

Exercise

Q1. Explain problem solving agents.

Q2. What is goal based agent?

Q3. Explain uninformed search strategies with it’s algorithms.

Q4. What is Breadth First search?

Q5. What is depth first search?

Q6. How can we avoid repeated states.

60

Introduction to Artificial Intelligence

Department of Computer Science

61 of 62

Q7. Problem solving agent is a kind of

  1. Average agents
  2. Dumb agents
  3. Goal based agents
  4. None of the above

​

Q8. Which is a physical configuration?

  1. State
  2. Node
  3. Percept
  4. None of the above

​

61

Introduction to Artificial Intelligence

Department of Computer Science

62 of 62

Q9. Which is a data structure constituting part of a search tree?

  1. State
  2. Node
  3. Percept
  4. None of the above

​

Q10. Which is also known as blind search?

  1. Informed search
  2. Uninformed search
  3. Heuristic
  4. None of the above

62

Introduction to Artificial Intelligence

Department of Computer Science