Introduction to AI

Module 3: Search in the real world

Summary

Topics: This module will cover the following topics.
- How to adapt search to handle real-world complexities
- Local search (this can also be used to adapt to real-world complexities!)
- Evolutionary computation and search
Length: The content of this module will take one week to complete. The project will be due later and the module will remain open only for the project after that first week.
Assigned chapters: Section 4.1 of Chapter 4 (we will not cover the rest of Chapter 4)
Project: Project 2 (will be open for 2 weeks beyond this module)

Adapting search

In the previous chapter, we learned about uninformed and informed search methods. These methods work well and can find the optimal answer (lowest cost path) in many situations but we had to make a number of assumptions to make these methods work.

All actions, states, and time steps were assumed to be discrete. We didn’t even really discuss time steps since the searches were performed once and then the plan was followed.
The environment was assumed to be deterministic. If you chose an action to move you from one state to another, the assumption was that you would in fact move to the next state with 100% probability.
Everything that the agent needed to know for search was fully observable.
There was only one agent acting in the environment (single-agent).
The search was sequential, the environmental dynamics were known, and the world did not change while the agent created its search plan so it was static.

In this chapter, we will work to relax many of these assumptions. We will discuss search in continuous state spaces. We will also discuss how to handle stochastic and multi-agent environments. Although we will not have time to cover them (since we want to cover many other great AI topics), the book and much of the remaining parts of the chapter that we do not cover include continuous action searches as well as partially observable environments.

For a different example than last module (where we used map search), imagine autonomous flights all searching for the optimal flight path from one destination to another. While it is similar to the map search, in this case, the planes have the full 3D volume of space in which to fly, which is essentially continuous. They need to avoid one another and also avoid any weather as well as any no-fly zones. Right now, the planes fly in prescribed lanes and heights to avoid many of these issues. But in a future world, they may well have some additional autonomy and such a search becomes critical that it is done right!

Real World search

Screenshot of flights across North America with weather

Screenshot from FlightRadar24 app

Topics for Module 3

Topic 1: adapting Search to work in the real-world

The search methods we discussed in the previous module made assumptions that are hard to achieve in more real-world scenarios. In this first topic, we will discuss how to handle relaxing these assumptions. This will be useful for your projects as well as useful in general!

(30 min) A* (and other searches) in the real-world
- (5 min) How to handle more real-world scenarios
- Link to the slides
- Note I did not make an exercise or quiz on this because you will implement much of this material in your projects.

Topic 2: Local search

In this topic, we will discuss multiple methods of search that are memory efficient and can handle continuous state spaces but do not guarantee optimality. Because of the efficiency of the approaches, they are often used to create solutions quickly.

(30 min) Reading
- Read Section 4.1 of Chapter 4 (Local Search and Optimization Problems) up to 4.1.4

(30 min) Local search
- (5 min) Hill climbing
  - Link to slides
- (5 min) Video on simulated annealing search
  - Link to slides
- (5 min) Video on local beam search
  - Link to slides
- (10 min) Complete the exercise on local search
- Post on #general some of the ways in which you do a local search in real-life (e.g. examples of how you, a human, perform local search)

Topic 3: Evolutionary algorithms

The final topic for this module focuses on a search method that could also appear in the machine learning module. The book chooses to have it appear as a local search method as it is often used for optimization.

(30 min) Reading
- Read Section the rest of section 4.1
(60 min) Evolutionary algorithms
- All of the videos below have their slides in one pdf file
- Overview of evolutionary computation and genetic algorithms
- Genes and Chromosomes
- Fitness functions and selection mechanisms
- Crossover and mutation
- Complete the exercise on evolutionary computation
- Easter egg: Post in #random your favorite amazing evolutionary creation from the natural world. Just pick something fun and creative, for example: do you love hedgehogs? Why did evolution make them the way they are? Post a photo or a meme of one and a thought on why it evolved that way.

Projects for module 3

Project

Project 2

This module covers search in the real-world and we want to implement informed search methods. As such, Project 2 is assigned this week. It is not due until partway through the next module (Sep 26) but you will want to work on it throughout this week.