Computer Science 456: Artificial Intelligence and Expert Systems
Unit 5: Control and Implementation of State Space Search
In previous units, we have presented different techniques and algorithms used to implement problem solving as a search through a set of states. Problem solving is represented as a path in the graph state space from the start state to the goal. In this unit we introduce further techniques for building search algorithms, and we present some control architectures used in AI problem solving such as production rules and blackboard.
Section 5.1: Recursion-based Search
This section introduces the concept of recursive search and presents a more concise and natural way for implementing depth-first, breadth-first, and best-first search algorithms using recursion. The concept of unification is also presented and used to introduce augmented recursion as used in the pattern-directed search algorithm.
Learning Objectives
- Present the concept of recursive search.
- Implement recursive-based versions of the depth-first, breadth-first, and best-first search algorithms.
- Present the concept of unification.
- Apply unification using the pattern-directed search algorithm.
Key Terms
recursive search, unification, pattern-directed search
Readings
Read the sections “Introduction” and “Recursion-Based Search” from Chapter 6, Building Control Algorithms for State Space Search.
Tasks
Practice the following exercises from Chapter 6 of the textbook:
- Exercises 1, 2, and 3. You may want to use the Personal Workspace wiki on the course home page and/or share your observations with classmates in the COMP 456 General Discussion forum.
Section 5.2: Production Systems and Blackboard Systems
This section presents some system architectures used for implementing search-based AI problem solvers. These architectures include production rules usually used in expert systems and blackboard.
Learning Objectives
- Discuss the concepts related to production systems.
- Describe different control strategies in production systems
- Carry out problem solving development using production rules.
- Present the blackboard architecture for system control.
Key Terms
production rules, working memory, recognize–act cycle, data-driven control, goal-driven control, blackboard architecture, knowledge source
Readings
Read the sections “Production Systems” and “The Blackboard Architecture for Problem Solving” from Chapter 6, Building Control Algorithms for State Space Search.
Tasks
Practice the following exercises from Chapter 6 of the textbook.
- Exercises 5, 7 and 9. You may want to use the Personal Workspace wiki on the course home page and/or share your observations with classmates in the COMP 456 General Discussion forum.