Skip To Content

Athabasca University

Unit 1: Informed Search and Online Search

Commentary

This unit discusses one of the most important AI approaches: search. The main focus is on three groups of search algorithms: (1) informed search, which makes use of problem-specific knowledge to find solutions more efficiently; (2) local search, which finds solutions by evaluating and modifying current state(s); and (3) online search, which conducts a search in an completely unknown state space. Before jumping into these topics, you are asked to briefly review some basic AI topics, such as the history of AI, intelligent agents, and problem-solving by searching.

Unit Purpose

When you complete this unit, you will be able to

  • Describe some general information about AI, such as its history, main branches and approaches, and the state-of-the-art.
  • Define intelligent agents, and describe its main structures and processes.
  • Explain how the main techniques used for informed search strategies differ from general search methods.
  • Analyse and propose a proper heuristic function according to the specific problem or domain to be solved.
  • Design several improved A* search algorithms, and apply them to some typical AI problems.
  • Explain the principle and algorithms behind local search algorithms that are based on hill-climbing, simulated annealing, local beam, or the genetic process.
  • Exemplify an online search agent, and explain how it works under unknown environments.

Section 1: Introduction to artificial intelligence
Section 2: Heuristic function, A* search, and its modified algorithms
Section 3: Simulated annealing, local beam search, and genetic algorithms
Section 4: Online search agents and unknown environments

Readings

Supplemental Unit Readings

Book: Luger, G. F. (2005). Artificial intelligence: Structures and strategies for complex problem solving (5th ed.). Boston, MA: Addison-Wesley.

  • Introduction to AI (Chapter 1), and search (Chapters 2-5)
  • AI Program languages (Chapters 15 & 16 - for those who want to learn Prolog and Lisp for AI programming in this course).

Magazine: IEEE Intelligent Systems.

  • Browse the magazine for some interesting articles on AI, intelligent agents and advanced search algorithms, and their applications.

Activities

Explore introductory AI websites, including

Updated December 16 2021 by FST Course Production Staff