Computer Science 456: Artificial Intelligence and Expert Systems

Unit 3: Graph Theory and Strategies for State Space Search

In this unit, you will learn about the theory of state space search and its use in problem solving. In fact the representation of problems using state space graphs allows us to have a model of the situation. This model will be used to design an automated solver and answer key questions such as If the problem solver is guaranteed to find a solution, will the solver always terminate? Will the solution be optimal?, and How can the solution search complexity be reduced?

Section 3.1: Graph Theory and Finite State Machines

This section discusses the state space description of problems. It introduces two main structures used for representing AI problems: graphs and state machines. An overview of graph theory and finite state machines is presented as well as a description of how they are used to formally represent the state space of a problem.

Learning Objectives

  • Review the key concepts of graph theory and finite state machines.
  • Use graph theory to represent problems.
  • Illustrate the state space representation of problems.

Key Terms

graph, rooted graph, tree, state, finite state machine, finite state acceptor, state space representation, state space search

Readings

Read the sections “Introduction” and “Structures for State Space Search” from Chapter 3, Structures and Strategies for State Space Search.

Tasks

Practice the following exercises from Chapter 3 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 3.2: State Space Search Algorithms and Reasoning Representation

This section examines strategies for state space search and reasoning. The forward chaining and backward chaining strategies are introduced using the backtrack algorithm. The depth-first and breadth-first search algorithms are also presented in detail. Using application examples, this section discusses the concept of and/or graphs and how state space and predicate calculus is used to represent reasoning.

Learning Objectives

  • Describe the data-driven and goal-driven search.
  • Implement forward-chaining and backward-chaining strategies.
  • Illustrate the use of depth-first and breadth-first searches as reasoning strategies.
  • Construct and/or graphs for a set of propositional calculus expressions.

Key Terms

forward chaining, backward chaining, backtrack, depth-first, breadth-first, and/or graph

Readings

Read the sections “Strategies for State Space Search” and “Using the State Space to Represent Reasoning with the Propositional and Predicate Calculus” from Chapter 3, Structures and Strategies for State Space Search.

Tasks

Practice the following exercises from Chapter 3 of the textbook:

  • Exercises 7, 8 and 10. 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.

TOP