Introduction to AI

Module 2: Intelligent search

Summary

  • Topics: This module will cover the following topics.
    • Problem formulation (how to formulate a problem for search)
    • Uninformed search methods (how to search when you have minimal information to guide you)
    • Informed search techniques (how to search with some guidance)
  • Length: The content of this module will take two weeks to complete.  
  • Assigned chapters: Chapter 3
  • Project: This module is associated with Project 1 and 2 but only Project 1 is assigned during the module.  

Problem Solving & search

Much of the press coverage on AI focuses on machine learning.  While we will cover machine learning this semester, this is a lot of AI that is driven by intelligent search!  Think about how many times you have used Google search or another search method to get directions.  Did you stop to think about how many choices it has to sift through to get you directions that are nearly optimal and arrive nearly as soon as you ask?  

In this module, we will cover intelligent search methods starting with ones that require minimal knowledge about the problem being solved (e.g., breadth first search and depth first search) and moving to methods that can provide optimal solutions but which require background knowledge about the solution (e.g. A*).   

Before discussing the search methods, we will discuss how to formulate a search problem precisely so that a solution is possible.  This involves understanding the characteristics of the environment as we discussed in the previous module.  Knowing what information is available to you and what environment your search is operating in is critical to choosing the right search method.  Just because A* is optimal in some situations does not make it the best search method for every problem domain.

Intelligent search

Google search

Example of a Google search from Devon to Dale

readings and videos for Module 2

Topic 1: problem formulation

Before jumping into the search techniques themselves, we will discuss how to formulate a search problem so that it can be solved by search and also ensure we are using the same definitions and assumptions for search.  As before, you can do the reading first then videos or the videos then reading, whichever works for you!

  • (30 min) Reading
    • Read Sections 3.1-3.3 of Chapter 3 (Problem-Solving agents through search algorithms)
  • (20 min) We discuss the highlights of how to formulate a search problem 
  • (5 min) We also discuss definitions for search techniques so that we are all on the same page when we run the algorithms.  We also discuss how to evaluate all of our search algorithms.
  • When we have in-person class, I will ask for examples of non-map based search problems and we then formulate them.  Consider this a fun exercise to do in slack on #general:  Post an idea for a non-map based search problem and how to formulate it.  Also comment on your fellow student’s ideas and we can come up with a nice list, just asynchronously! 

Topic 2: Uniformed searches

For this topic, we will move into the uninformed search strategies.  Those are the strategies that do not require the agent to know anything about the relationships between its current position and the goal.

  • (30 min) Reading
    • Read Section 3.4 of Chapter 3 (Uninformed search strategies)
  • (60 min) Searches
    • You have probably studied breadth first search in other classes but likely not from the same perspective.  This should at least be a quick search algorithm to study and learn.
    • The remaining algorithms in this topic are in one video since they are related to each other. They all build on depth first search.  
    •  Again, in class, we would be working on these together so please feel free to ask if you are stuck on any of the search methods!  Use the #general channel

Topic 3: informed searches

Uninformed searched can be useful in many situations. However, often the human can provide helpful strategies to guide the agent in the search, which means we can improve our search efficiency and find optimal paths in many cases.  This topic focuses on informed searches.  Both algorithms will use information provided to estimate how far it is to the goal from the current node but they differ after that.

  • (60 min) Reading
    • Read Section 3.5-3.6 of Chapter 3 (Informed (Heuristic) Search Strategies through Heuristic Functions)
  • (60 min) Informed Searches
    • The first search algorithm we will discuss in this module is one that uses only the heuristic information provided by the user to estimate distance from the current node to the goal.  This is called greedy best first search
    • The second algorithm we will discuss combines the heuristic with the actual path costs to achieve an optimal path (with some requirements, discussed in the video and in the chapter). This is A* search.
    • I did something a little different for your final part of this topic.  Instead of recording a video, I made a page to read about how to create effective heuristics
    • Discussion assignment:  complete the grading declaration on discussions for module 2 

projects for Module 2

projects

Project 0

  • (1-2 hours) Reminder that Project 0 Part 2 from Module 1 is due during week 1 of this module (Due Wednesday Sep 1 11:59pm)

Project 1

Project 1 is your first full-scale project in Space Settlers.  It focuses on uninformed search methods and is assigned Sep 2 and due Sep 12 11:59pm

Suggested schedule for Module 2

Week 1 (Aug 29 – Sep 5)

  • Complete Topics 1 by Tuesday
  • Complete project 0 by Wednesday
  • Read Project 1 by Friday
  • Complete Topic 2 by Friday 
  • Start Project 1 by Sunday

Week 2 (Sep 5 – Sep 12)

  • Complete Topic 3 by Wednesday 
  • This week is lighter on topics as the assumption is you will focus on your project
  • Finish Project 1 by end of this module (Sep 12)