Agents and search

What an intelligent agent is, how to state a task as a search problem, and how to solve it with breadth-first, depth-first, uniform-cost, greedy and A* search.

About 5 hours of study

Learning objectives

Lessons

  1. 1

    Intelligent agents Intermediate

    An agent perceives its environment and acts on it. Learn the parts of an agent, how to describe a task with PEAS, the kinds of environment, and the step from simple reflex agents to agents that keep a model of the world.

  2. 2

    Problem solving by search Intermediate

    Turn a task into a search problem with states, actions, a goal and costs. Explore the state space with breadth-first, depth-first and uniform-cost search, and know which one finds the shortest or the cheapest solution.

  3. 3

    Heuristics and A* search Intermediate

    Guide search with an estimate of the distance to the goal. Compare greedy best-first search with A*, learn why an admissible heuristic makes A* optimal, and design heuristics such as Manhattan distance.

Module practice

Module quiz

1. What does a simple reflex agent base its action on?
2. Which search finds a solution with the fewest steps?
3. Which search finds the cheapest route when steps have different costs?
4. What does A* use to order its frontier?
5. Which heuristic is admissible for 4-direction moves on a grid?
6. Why can greedy best-first search return an expensive route?

Local search and games ›