Topic 11b
Agents that Reason/Search

Prior to Class

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

• Define and provide examples for foundational vocabulary terms including:
• Production System
• Production (aka “actions”)
• State
• Children
• State Space
• Search Tree
• breadth-first search
• depth-first 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, discuss the order that nodes are visited using:
• breadth-first search
• depth-first search

• Activity
  • Consider the Analysts and Hackers canoe problem
  • Scratch Program you can use to test Analysts and Hackers
    • Press the green flag to reset the program.
• Readings
• Section 11.3 - pp 574-585 in your book

 

In class

Discussion

Let's walk through this idea for a bit.

Checking for Understanding

Consider the following problems

• Search Space practice
  • Answers

Extra Help

• Videos
• Introduction to Search Problems (Production Systems)
• Analysts and Hackers - Breadth First Search
• Analysts and Hackers - Depth First Search

In the main materials I introduced search using an example with Analysts and Hackers. If you want to see this again, with a different example, you might consider my "Travelling in Romania" example.

• Traveling in Romania - BFS
• The map of Romania used in this video
• Traveling in Romania - DFS
• Summarizing BFS and DFS
• Using Heuristics
• Best-First/Best-Fit Search in Romania

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 (we do visit it in the last course in our program), 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

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

• Crash Course AI #12 - AI Playing Games