Introduction - some problems with classical AI


next up previous contents
Next: Reactive planning and nouvelle AI
Up: No Title
Previous: Contents
Back: to main list of student notes

Introduction - some problems with classical AI

In the handout on AI and PopBeast, I described a simple artificially intelligent program. Its mental functioning is clearly separated into three parts. There is a perception box that takes ``visual'' input and builds from it a description of the world. There is a reasoning box that takes this description, together with a goal generated by analysing the last command, and builds a plan. And there is an action box that executes each action in the plan in turn. This three-way division is typical, as I said there, of what is sometimes called ``classical'' AI: typical of almost all robot designs up to the mid-80's, though of course my program is a lot simpler. Incidentally, ``classical AI'' is a fairly loose term. If you intend to use it in essays or exams, give some examples to show what you mean.

Many AI workers no longer accept this separation as the best way to build robots that can act in an uncertain and changing world. There are many reasons why. Here is one, as an example: building a complete description of the world from sensory data is a very difficult job, and demands a lot of computer time. We can't yet do it for data coming from any but the crudest sensors. Even if we could, our description-builders could not possibly run fast enough to have finished computing the description by the time it is needed. The robot would run into a door before realising that it was there.

Moreover, it seems obvious (with hindsight) that the type of description one needs depends on what one is trying to achieve. A robot typesetter, looking at these notes, would have to build a painstakingly detailed description of them in terms of sentences, paragraphs, tab settings, fonts, and margins. However, if I were to drop them out of my window, a robot street-cleaner need only classify them as ``scrap paper'' in order to do its job - that of throwing away anything that's not a person, dog, cat, or piece of street furniture. As another example, when crossing the road, it's sufficient to perceive a speeding car as something to be avoided - quickly! But a garage attendant or traffic warden needs rather more detail than that. The paper An emerging paradigm in robot architecture by Malcolm, Smithers and Hallam (PSY AI box photocopy M149) is a nicely-written not-very-technical account of classical AI in robotics and of some newer alternatives. Most of it should be intelligible after reading the AI and PopBeast notes, and I recommend it.

Although PopBeast does not address these problems, it does have some educational value, in that it can demonstrate ideas such as multiple representations, logic-based world-models, path planning, and many other concepts which are themselves still widely used. In addition, it's an important demonstration of history, as well as of some current practice, such as the FMC self-guiding vehicle mentioned in the above paper. And those who don't know their history are condemned to repeat it.

However, I can't let you experiment with it because it isn't robust enough. Its planner is based on a classical planner called Warplan, written in the mid-70's. Although an important advance in its time, it can't solve problems much more complicated than the ``open the door'' one - on trying, it frequently gets into infinite loops. This is not surprising. It has been shown that this kind of planning is computationally intractable. Roughly speaking, the amount of time needed to make a complete plan increases with the exponential of the number of objects and plan steps being reasoned about.

One can circumvent this by giving the planner more knowledge about specific objects and tasks, by using clever heuristics, by trying to adapt previous solutions to similar problems, and by planning in less detail. However, although such programs do exist, even finding them takes a lot of work. I have therefore taken a different approach in this practical.




next up previous contents
Next: Reactive planning and nouvelle AI
Up: No Title
Previous: Contents
Back: to main list of student notes



Jocelyn Ireson-Paine
Thu Feb 15 00:10:39 GMT 1996