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.
Example of a Google search from Devon to Dale
Topic 1: problem formulation
Don’t forget, if you find any broken links or other bugs in the module before your fellow students and report them on #class-bug-reports, you can get extra credit!
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.
- Go to the google drive link in the assignment on problem formulation and work on ideas of how to formulate a non-map based search problem. Comment on your fellow student ideas and help refine the list! (Note the link is only inside canvas to prevent any issues with a generic open link).
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. You will be implementing BFS/DFS in your first project also!
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