Module 3: Search in the Real World

Overview

Executive 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
    • Particle filtering
    • Other real-world adaptations, including handling uncertainty
  • Length: The content of this module will take one and a half weeks to complete.  
  • Assigned chapters: Section 4.1 of Chapter 4 (we will not cover the rest of Chapter 4)
  • Project: Project 2 

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 

Jump to the next topic

MODULE MENU