Course: Knowledge Based Engineering

Edward (Ned) S. Blurock

E-Mail:

Edward.Blurock@risc.uni-linz.ac.at

Snail-Mail (job)

Edward S. Blurock
Research Institute for Symbolic Computation (RISC-Linz)
Johannes Kepler University
A-4040 Linz
Austria, Europe
Phone: +43 732 2468 9928
Fax:   +43 732 2468 9930

This is all the course materials and slides for a lecture on Knowledge
Based Engineering. This course is basically an introduction to
artificial intelligence and expert systems. The general theme of the
course is methods of search. The expert system shell CLIPS is
introduced not only to give an example of an expert system shell, but
also as a programming medium (for the exercises) for illustrating the
search methods introduced in traditional AI textbooks (i.e. A, A*,
Decision Trees, AND/OR graphs). Depending on time, the numeric search
techniques will also be introduced, Gradient, Monte-Carlo and Genetic
Algorithms. The software system PRODIGY is introduced as a medium for
looking at planning problems. In addition, the software system OTTER
will be used to illustrate resolution. As one sees the course gives
emphasis on the practical exercises within the concepts
introduced. The software systems are used to enable the calculation of
non-trivial examples and to see, by example, the complexity the
problems can take. (The file expert.html gives the html document
organizing the various files in this directory).

Table Of Lectures

Lecture 1: Introduction
Lecture 2: CLIPS
Lecture 3: CLIPS
Lecture 4: Programs in Clips: Decision Trees and Production Systems
Lecture 5: Breadth First Search
Lecture 6: Tree/Graph Search
Lecture 7: AND/OR Graphs
Lecture 8: Game Theory
Lecture 9: Planning Systems
Lecture 10: Resolution with OTTER
Lecture11: Numeric Optimization
Lecture 12: Genetic Algorithms

Lecture 1: Introduction

General introduction about the course and what it entails. The course, on the programming side, will entail work with the expert system shell Clips and other AI programs and, on the theoretical side deal with the search techniques used within artificial intelligence.

Handouts:
Exercises:
Overheads:

Lecture 2: CLIPS

More aspects of clips are introduced: rules and templates.

Handouts:
Exercises:
Overheads:

Lecture 3: CLIPS

Handouts:
Exercises:
Overheads:

Lecture 4: Programs in Clips: Decision Trees and Production Systems

The diagnostic problem of repairing a stove is used as an example. This shows the decision tree form of searching. In the second half of the class the concept of production systems are introduced and illustrated in setting up the waterjug problem.

Handouts:
Exercises:
Overheads:

Lecture 5: Breadth First Search

A simplified water jug problem is set up: fill a jug 3 gallons where the only operations are add 1 gallon and add 2 gallons. This is done, in stages, by setting up a complete program using breadth first search. Several programs are shown, of increasing complexity, leading to the complete solution.

Handouts: The clips programs used in the lecture
Exercises:
Overheads:

Lecture 6: Tree/Graph Search

The concepts of Depth-first, Breadth-First and Best-First are put under a common terminology and each algorithm is defined under this context. Algorithm A (for simple graphs) is introduced and the various properties (such as Admissibility, Conditions under which a solution is found) are informally proved. Then a clips implementation of the algorithm with the simplified water jug example is explained. In addition, the topic of the elimination of cycles (as introduced in the cannibal and missionary problem) will be briefly discussed.

Handouts and/or Reference Materials:
Exercises:
Overheads:

Lecture 7: AND/OR Graphs

The graph search algorithms are presented in terms of AND/OR graphs. The solution is now a graph instead of a single path (or node). A rewrite system is shown in both the OR graph scheme and the AND/OR scheme. The AO* algorithm is explained in detail and another (artificial) example is stepped through.

Handouts and/or Reference Materials:
Exercises:
Overheads:

Lecture 8: Game Theory

The special type of search problem encountered in game theory is presented. Three methods are illustrated: MINMAX, ALPHA-BETA and SSS.

Handouts and/or Reference Materials:
Exercises:
Overheads:

Lecture 9: Planning Systems

The search methods involved in planning are illustrated by introducing the planning system PRODIGY. The formulation of problems and how PRODIGY solves them are illustrated. Several problems, each of increasing complexity, are shown in the lecture.

Exercises:
Overheads:

Lecture 10: Resolution with Otter

The simple automated theorem prover, OTTER, is used to illustrate resolution techniques.

Handouts and/or Reference Materials
Exercises:
Overheads:

Lecture 11: Numeric Optimization

This lecture is concerned with 'numeric' search in a vector domain. Three types of numeric optimization are introduced: Gradient, Probabilistic (Monte Carlo and Las Vegas Algorithms) and Simulated Annealing. These are used to set the stage for the discussion of genetic algorithms of the next

Handouts and/or Reference Materials
Exercises:
Overheads:

Lecture 12: Genetic Algorithms

This lecture is concerned, once again, with (though not exclusively) 'numeric' search using genetic algorithms. The public domain library of genetic algorithms (libGA of Arthur L. Corcoran) are used for illustrating the setup of a simple search procedure.

Handouts and/or Reference Materials
Exercises:
Overheads:

Edward.Blurock@risc.uni-linz.ac.at