Knowledge Representation - Course Handbook

Chris Thornton

Introduction

Knowledge Representation (KR) is a core course for the Intelligent Systems MSc. Based on a mixture of lectures, exercise classes, research tutorials and supervised debates, the course aims to give a broad introduction to knowledge representation and artificial intelligence (AI).

Sessions

Week 1
lecture 1: not used
lecture 2: Introduction to the course (and BugWorks)
sem/class: not used

Week 2
lecture 1: (lec01) Introduction to the field pr sl
lecture 2: (lec02) Route finding pr sl
sem/class: lab session - BugWorks `Quick Start' and `projectile' missions

Week 3
lecture 1: (lec03) Problem solving pr sl
lecture 2: exercise class - problem solving exercises
sem/class: lab session - BugWorks `obstacleAvoidance' and `singleWheeler' missions

Week 4
lecture 1: (lec04) Heuristic search with A* pr sl
lecture 2: briefing - Searle, the Chinese Room and debate-group allocation
sem/class: lab session - BugWorks `frictionSwerve' and `fear' missions

Week 5
lecture 1: (lec05) Game playing with minimax pr sl
lecture 2: exercise class - Heuristic search/Game playing exercises
sem/class: lab session - supervision groups A & B / BugWorks `agression' and `love' mission

Week 6
lecture 1: (lec06) Reasoning pr sl
lecture 2: first debate (group A vs group B)
sem/class: lab session - supervision groups A & B / BugWorks `exploration' and `maze' mission

Week 7
lecture 1: (lec07) Knowledge representation pr sl
lecture 2: briefing - Brooks and the insect-like robots
sem/class: lab session - BugWorks `circling' and `backAndForth' missions

Week 8
lecture 1: (lec08) Theorem proving pr sl
lecture 2: exercise class - knowledge representation in logic (song transcription)
sem/class: lab session - supervision groups C & D / BugWorks `delayedResponse', `breeding' and `fuseWire' missions

Week 9
lecture 1: (lec09) Induction pr sl
lecture 2; second debate (group C vs group D)
sem/class: lab session - supervision groups C & D / BugWorks `throbbing', `viciousCircle' and `catheringWheel' missions

Week 10
lecture 1: revision
lecture 2: revision
sem/class: revision

Lecture notes

Lecture slides can be accessed via the `pr' links but you are encouraged not to print these out if possible. Taking your own notes will improve your understanding in the long-run.

Times and locations

Times and locations for course sessions can be obtained from Sussex Direct. There should be two lecture sessions per week and one lab class.

The first meeting will be the first lecture session in week 1. There will be no lab class in week 1.

Attendance will be recorded at all lecture and lab sessions.

Lab sessions

Lab sessions should be used to work through the specified BugWorks exercises (`missions') and through lecture exercises (access the via the `pr' links above). Debate supervision will also take place in the lab.

The BugWorks exercises are largely based on the material in Braitenberg's book `Vehicles: Experiments in Synthetic Psychology' (Braitenberg, 1984). Each exercise involves using a virtual workshop environment (the BugWorks system) to build a simple robot to perform a target task.

These exercises are not formally assessed. However, I will check simulations during the lab session and give people feedback individually.

To access BugWorks, go to http://www.ChrisThornton.eu/bugworks and run the `Free Applet'. Once the system has loaded you can then press the `Tutor' button at the top of the window to bring up the instructions for the exercises.

If you need to run BugWorks off-line, or want to be able to save/load files etc., you can get the full version by downloading using the special course keycode. (Ask me for this).

If you are using a PC and have an up-to-date version of Java installed (e.g., 1.3 or higher), you should then be able to run the system by double-clicking on the bugworks.jar file. Alternatively, in a command window, you can type `java -jar bugworks.jar'.

If you use Internet Explorer to do the download you may find that the jar file gets renamed to `bugworks.zip'. To correct this, rename the file back to `bugworks.jar' and you should then be able to run it in the usual way.

Assessment

The formal assessment for the course is a 3-hour unseen exam which takes place early in term 2.

Reading

The core reading for the course is Russell and Norvig's `Artificial Intelligence: A Modern Approach' (2003). This covers all the theoretical material (and more) in great depth. Chapters of most relevance are 3, 4, 6, 8, 9, 18, 20, and 26.

A lighter, locally-written source is Blay Whitby's `Artificial Intelligence: A Beginner's Guide' (2003).

There is also the now somewhat out of date `Readings in Knowledge Representation' edited by Brachman and Levesque (BOOK, 1985) and the intermediate-level AI textbook `Artificial Intelligence', by Rich and Knight (Rich and Knight, 1991)

In the second half of the term, there will be two supervised debates and, in preparing for these, students will be divided into small reading groups.

Debate arrangements

The arrangements for the two debates, scheduled for the latter part of term, are as follows.

At the debate briefing in week 4, students will be divided up into four groups (A, B, C and D). Group A will be delegated to argue in favour of the first debate motion, and group B against. Group C will be delegated to argue in favour of the second debate motion, group D against.

In the weeks running up to the debates themselves, students in each group work together to read up on the relevant sources and prepare notes etc. to enable them to argue their case as strongly as possible. As part of this process, I meet with each group to consult on suitable reading.

Each group should delegate one person to make an opening presentation, which should last around 10 minutes. However, all members of each group should be ready to participate fully in the exchange of views.

Debates will conclude with a vote on the original motion but votes will only be taken from the `audience', i.e., students who are not part of the active groups. Everyone in the whole class needs to appear at both debates therefore, otherwise there will be no `audience' to decide who has actually won.

Debate gruoups

Pro Searle: Jake, Maryam
Anti Searle: Elana, Kritonas
Pro Brooks: Deng Weicheng, Muhammad Khaud Adnan
Anti Brooks: Bharath Gojanur, Lalhming Muana

First debate

Motion

The chinese room argument proves that AI systems do not really understand anything.

There are hundreds of publications of relevance here, some of which are listed below. I will try to steer people towards other items of interest during supervision sessions. The key publication is Searle's BBS article which includes multiple commentaries. (In putting forward the chinese-room argument, Searle was reacting to AI natural-language systems such as SHRDLU, see http://hci.stanford.edu/~winograd/shrdlu/).

Searle, J. (1980). Minds, brains and programs [with peer commentaries]. BEHAVIOURAL AND BRAIN SCIENCES, No. 3 (pp. 417-57).

Readings largely in favour

Lucas, J. (1964). Minds, machines and godel. In A. Anderson (Ed.), MINDS AND MACHINES (pp. 43-59). New Jersea: Prentice Hall.
Dreyfus, H. (1981). From micro-worlds to knowledge representation: AI at an impasse. In J. Haugeland (Ed.), MIND DESIGN: PHILOSOPHY, PSYCHOLOGY, ARTIFICIAL INTELLIGENCE (pp. 161-219). Cambridge, Mass.: MIT Press.
Penrose, R. (1989). THE EMPEROR'S NEW MIND: CONCERNING COMPUTERS, MINDS, AND THE LAWS OF PHYSICS. Oxford University Press. (particualrly chaps 1 & 2)
Nagel, T. (1981). What is it like to be a bat?. In D.R. Hofstadter and D.C. Dennett (Eds.), THE MIND'S I. Basic Books.

Readings largely against

Turing, A. (1964). Computing machinery and intelligence. In A.R. Anderson (Ed.), MINDS AND MACHINES (pp. 4-30).
Hofstadter, D. and Dennett, D. (1981). Reflections on searle's chinese room argument. In D.R. Hofstadter and D.C. Dennett (Eds.), THE MIND'S I (pp. 373-382). Basic Books.
Boden, M. (1990). Escaping from the chinese room. In M.A. Boden (Ed.), THE PHILOSOPHY OF ARTIFICIAL INTELLIGENCE (pp. 89-104). Oxford University Press.
Gregory, R. (1987). In defence of artificial intelligence - a reply to john searle. In C. Blakemore and S. Greenfield (Eds.), MINDWAVES (pp. 235-247). Blackwell.
Feigenbaum, E. and McCorduck, P. (1984). THE FIFTH GENERATION. London: Pan Ltd.

Below are some alternative sources for the readings above. Note that any book which contains Searle's paper is very likely to contain other articles of relevance.

Turing, A. (1950). Computing machinery and intelligence. MIND, No. 59 (pp. 433-460).
Dreyfus, H. (1985). From micro-worlds to knowledge representation: AI at an impasse. In R.J. Brachman and H.J. Levesque (Eds.), READINGS IN KNOWLEDGE REPRESENTATION (pp. 71-94). Los Altos: Morgan Kaufmann.
Searle, J. (1990). Minds, brains and programs. In M.A. Boden (Ed.), THE PHILOSOPHY OF ARTIFICIAL INTELLIGENCE (pp. 67-88). Oxford University Press.
Searle, J. (1984). MINDS, BRAINS AND SCIENCE: THE 1984 REITH LECTURES. London: BBC Publications.
Searle, J. (1987). Minds and brains without programs. In C. Blakemore and S. Greenfield (Eds.), MINDWAVES (pp. 209-233). Blackwell.
Searle, J. (1981). Minds, brains and programs. In J. Haugeland (Ed.), MIND DESIGN: PHILOSOPHY, PSYCHOLOGY, ARTIFICIAL INTELLIGENCE (pp. 282-306). Cambridge, Mass.: MIT Press.
Searle, J. (1981). Minds, brains and programs. In D.R. Hofstadter and D.C. Dennett (Eds.), THE MIND'S I (pp. 353-372). Basic Books.
Penrose, R. (1987). Minds, machines and mathematics. In C. Blakemore and S. Greenfield (Eds.), MINDWAVES (pp. 259-278). Blackwell.

Second debate

Motion

Since explicit knowledge representation inevitably produces an information bottleneck, it is only appropriate for use in toy domains.

The key articles for this debate are Brooks' own papers. For Brooks' general approach see

Brooks, R. (1991). Intelligence without representation. ARTIFICIAL INTELLIGENCE, 47 (pp. 139-159). Available as http://www.ai.mit.edu/people/brooks/papers/representation.pdf

For more information on subsumption architectures and the information bottleneck see

Brooks, R, (1985) A Robust Layered Control System for a Mobile Robot. AI Memo 864, MIT AI Lab. http://people.csail.mit.edu/brooks/papers/AIM-864.pdf

There's also a nice powerpoint presentation on Brooks etc. at http://www.eecs.ucf.edu/~lboloni/Teaching/EEL6938_2005/slides/Presentation_RyanFitzGibbon_SubsumptionArchitecture.ppt

Readings largely in favour

Braitenberg, V. (1984). VEHICLES: EXPERIMENTS IN SYNTHETIC PSYCHOLOGY. London: The MIT Press.
Cliff, D., Husbands, P. and Harvey, I. (1993). Evolving visually guided robots. In J. Meyer, H. Roitblat and S. Wilson (Eds.), FROM ANIMALS TO ANIMATS: PROCEEDINGS OF THE SECOND INTERNATIONAL CONFERENCE ON SIMULATION OF ADAPTIVE BEHAVIOUR (SAB92). MIT/Bradford Books. Available as ftp://ftp.informatics.sussex.ac.uk/pub/reports/csrp/csrp220.ps

Wheeler, M. (1996). From robots to rothko: the bringing forth of worlds. In M.A. Boden (Ed.), THE PHILOSOPHY OF ARTIFICIAL LIFE (pp. 209-236). Oxford: Oxford University Press.
van Gelder, T. (1992). What might cognition be if not computation?. Research Report 75, Bloomington, IN47405: Cognitive Science, Indiana University (Indiana).

Readings largely against

Kirsh, D. (1996). Today the earwig, tomorrow man?. In M.A. Boden (Ed.), THE PHILOSOPHY OF ARTIFICIAL LIFE (pp. 237-261). Oxford University Press.
Lenat, D. and Feigenbaum, E. (1992). On the thresholds of knowledge. In D. Kirsh (Ed.), FOUNDATIONS OF ARTIFICIAL INTELLIGENCE (pp. 185-250). Amsterdam: MIT Press.
Nilsson, N. (1992). Logic and articial intelligence. In D. Kirsh (Ed.), FOUNDATIONS OF ARTIFICIAL INTELLIGENCE (pp. 31-56). Amsterdam: MIT Press.
Newell, A. (1980). The knowledge level: presidential address. AAAI80. Stanford: American Association for Artificial Intelligence. Also available as http://www.aaai.org/AITopics/assets/PDF/AIMag02-02-001.pdf

Readings with various viewpoints

Clark, A. and Toribio, J. (1994). Doing without representing?. CSRP 310, Cognitive and Computing Sciences, University of Sussex, UK. Available as www.cogs.indiana.edu/andy/DoingW-O-rep.pdf

Misc.

Brooks, R. and Steels, L. (Eds.) (1994). THE `ARTIFICIAL LIFE' ROUTE TO `ARTIFICIAL INTELLIGENCE'. Hillsdale, NJ: Erlbaum.
Brooks, R. and Stein, L. (1994). Building brains for bodies. ROBOTICS AND AUTONOMOUS SYSTEMS, aim 1439, 1, No. 1 (pp. 7-25).

Brooks' subsumption/information-bottleneck diagram

Page created on: Tue Nov 18 11:05:23 GMT 2008
Feedback to Chris Thornton