Topic 11b
Agents that Reason/Search

Learning Outcomes

By the end of this topic students should be able to:

• Define and provide examples for foundational vocabulary terms including:
• Production System
• State
• Production (aka “actions”)
• Children
• State Space
• Search Tree
• breadth-first search
• depth-first search
• best-first search
• A* search
• Given a simple search problem and a particular node in the search space for that problem, identify the children that can be generated.
• Given a simple search problem, generate the search tree using:
• breadth-first search
• depth-first search
• Given a simple search problem and an appropriate heuristic, generate the search tree using:
• best-first search

Learning Materials

• Activity
  • Solve the Analysts and Hackers canoe problem
• Readings
• Section 11.3 - pp 574-585 in your book
• Videos
• Introduction to Search Problems (Production Systems)
• Breadth First Search
  • Analysts and Hackers
  • Travelling in Romania
    • Even if the Analysts and Hackers example made complete sense, please watch this video because it introduces some new ideas.
    • The map of Romania used in this video
• Depth First Search
  • Analysts and Hackers
  • Travelling in Romania
    • Again, even if the Analysts and Hackers example made complete sense, please watch this video because it introduces some new ideas.
• Summarizing BFS and DFS
• Using Heuristics
• Best-First/Best-Fit Search in Romania

 

Checking for Understanding

Consider the following problems

• Search Space Problems
• Answer Key

Additional Guidance

• NA

Further Information

On page 583 your book talks about the A* algorithm. Of all of the search techniques, this is the only one guaranteed to find the optimal path. While the implementation of the A* isn't a part of the Learning Outcomes for this course, in the end, the algorithm isn't that difficult to understand. If you would like to know more about A* you can use the materials below.

• Least-Cost Search (a non-heuristic search that is a sub piece of the A* search so we need to explain that first)
• A* Search from Arad to Bucharest
• A* Search Activity
  • Answer Key

In this Topic we focus on traditional search. Game-Playing is often viewed as a modification of traditional search. This one of the Learning Outcomes for this course. But you might find it interesting:

• Crash Course AI #12 - AI Playing Games