Artificial Intelligence 2 Module 1: Module Description
Aims and objectives
The aim of this module is to cover some basic methods used by AI problem
solving systems. It illustrates the importance of (a) analysing
a problem so as to exploit constraints and (b) considering how the way that a problem is
represented affects the nature of any search problem that arises. As well as
providing this general background, the module introduces specific techniques
for avoiding/limiting the inefficiency of naive uninformed search, including
memoisation/dynamic programming, constraint propagation, constraint logic
programming and stochastic methods. These are illustrated with examples from
various different areas of AI research.
The module refers to some extent to material on search, logic and Prolog from
AI1, but revisits this material from a different point of view and develops
the ideas further.
Syllabus
The module's material divides up into the consideration of two
different tasks:
Task 1: Using Constraints to Solve Problems
The emphasis here is on using problem constraints to
avoid
doing search. We consider how important it is to decompose problems into
appropriate subproblems. Dynamic Programming is illustrated using a
stereo computer vision problem.
The general notion of a Constraint
Satisfaction Problem is introduced, and Constraint Propagation techniques
are illustrated through work on Machine Vision. Mechanisms in Prolog
(including some simple Constraint Logic Programming techniques) which can be
useful for exploiting problem constraints are introduced.
Task 2: Solving Problems by Other Means
Here the "other means" are mainly search methods of one form or another. We
consider what search spaces can be like and how they can be visualised, as
well as briefly surveying a range of search algorithms and some of their
relevant properties. We take logical reasoning as a major example, motivating
the tasks of testing validity and satisfiability. We see how different
logical formalisations give rise to different kinds of search spaces. For
satisfiability, we see that relatively recent stochastic techniques (GSAT)
are now competing with older systematic search procedures. This leads to a
consideration of stochastic search methods in general.
Intellectual skills development
This module attempts to make students think more carefully about how they
choose to represent problems, about the complexity of different solution
approaches and how serious search problems can be tamed.
Although it does present some particular techniques that students are expected
to absorb, much of the material (e.g. the presentation of different rules of
inference for logic) is really aimed to show that there are alternative
possibilities and that it is necessary to think carefully before adopting any
particular approach.
The module shows
Prolog programming techniques being used for more advanced tasks
than were considered in AI1 and exercises these techniques in the assigned
work.
Activities
There are 14 lectures in two parts (7 each task) and five tutorials. The exercises set for the tutorials
intentionally cover more than can necessarily be treated directly in the
tutorials, and students are expected to spend some time on these exercises
outside of the tutorials themselves.
Assessment
There is one piece of assessed work for each of the two tasks described above.
Each assignment has the same value. The assignments are due:
- Assignment 1 Constraints: Friday 4pm, week 4 semester 1 (Oct 15)
- Assignment 2 Search: Friday 4pm, week 7 semester 1 (November 5)
There will also be a section in the AI2Ah exam based on material of this module.
Note that there is a demonstrator (Aroosha Laghaee - a.laghaee@sms.ed.ac.uk)
who can help answer questions about prolog and the coursework.
You can see her Prolog revision tutorial notes
here.
Context
Students should be familiar with basic material on knowledge representation
and inference (particularly, facts and rules) and search, as is taught in AI1.
Although this background will be reinforced by the material of this module,
nevertheless it will be presupposed to such an extent that a student without
it could get into difficulties. Students should be able to program in Prolog
at the level expected at the end of AI1.
References
There is no single textbook that covers all of this material really well.
The following has material for some parts and is worth acquiring because it
is useful also for other AI courses. A list of sources of background reading
is distributed to the students.
Russell, S. and Norvig, P.,
"Artificial Intelligence: A Modern Approach",
Prentice Hall, 1995.
Back to the module home page.
This page is maintained by the course lecturer, Bob Fisher,
r.b.fisher@ed.ac.uk, room 2107D JCMB, Tel 651-3441
