Section 2 : Heuristic function, A* search, and its modified algorithms

Commentary

Section Goals

• To discuss heuristic functions and informed (heuristic) search strategies.
• To analyse informed search algorithms, such as A*, for improved variants for problem-solving.

Learning Objectives

Learning Objective 1

• Explain the rationale and function of information in improving search.
• Define the following concepts or terms: -
  • Best first search
  • Heuristic function
  • Informed search
  • A* search
  • Admissible heuristic
  • Iterative-deepening A* (IDA*)
  • Recursive best-first search (RBFS)
  • Memory bounded A* and SMA*
  • Parallel search
• Name the state-of-the-art search techniques.
• Explain when A* is optimal.
• Implementing and testing A* and recursive best-first search algorithms.

Objective Readings

Required Readings

Reading topics:

Informed (Heuristic) Search Strategies (see Section 3.5 of AIMA3ed)

Supplemental Readings

Mahanti, A. and Daniels, C. J. (1993). A SIMD approach to parallel heuristic search. Artificial Intelligence, 60(2), 243-282.

Objective Questions

• What are the differences between A* search, best-first search, and tree search?
• What does 'consistency' mean when referring to heuristic function?
• What kind of heuristics are good, and how are good heuristics constructed?

Objective Activities

• Summarize the most recent papers on AI searching from the Journal of Artificial Intelligence Research, and report your findings through the online conference.
• Explore the following search-related programs from the textbook's website.
  • Best-First-Search
  • A* - Search
  • Recursive-Best-First-Search
• Complete Exercise 3.28 of AIMA3ed.
• Complete Exercise 3.29 of AIMA3ed.

Learning Objective 2

• Describe the following concepts or terms in relation to heuristics:
  • Domination
  • Relaxed problem
  • Subproblem
  • Pattern databases
• Explain how the above concepts or terms are related to heuristic function design.
• Describe the general principle involved in inventing admissible heuristic functions.

Objective Readings

Required Readings

Reading topics:

Heuristic Functions (see Section 3.6 of AIMA3ed).

Supplemental Readings

Bulitko, V., Lustrek, M., Schaeffer, J., Bjornsson, Y., and Sigmundarson S. (2008). Dynamic Control in Real-Time Heuristic Search. Journal of Artificial Intelligence Research, 32, 419-452.

Objective Questions

• How are heuristic functions chosen if there is a collection of admissible heuristics?
• How can learning help to produce good heuristics?
• How can one invent admissible heuristic functions?

Objective Activities

• Analyse the supplemental readings for recent research on heuristics. This work can be done jointly with Section 4 of this unit.
• Complete Exercise 3.31 of AIMA3ed.
• Complete Exercise 3.32 of AIMA3ed (Optional).