INTELLIGENT SYSTEMS QUALIFIER
OCTOBER 2003
 ANSWER TWO OF THE FOLLOWING THREE QUESTIONS:

CORE 1
You want to develop a controller for a five-elevator system in an office skyscraper.

a) Describe in detail how one can formulate the problem as a Markov decision process problem (for example, what are the states, what are the actions, what are the observations, and so on).

c) Markov decision process models originated outside of artificial intelligence but are now popular in artificial intelligence as well. Artificial intelligence researchers have explored in the past couple of years how to exploit the structure of Markov decision process problem to develop tractable solution methods. Describe two such ideas and then argue whether (and, if so, how) they can be exploited to solve Markov decision process problems for elevator scheduling.

b) Describe why Markov decision process problems for elevator scheduling are still difficult to solve despite the recent advances in solution methods and speculate on research directions that have the potential to result in tractable solution methods for such Markov decision process problems.

CORE 2
The original STRIPS program for planning was designed to control Shakey, one of the first AI robots to combine action, perception and cognition. Shakey's world consisted of rooms (say, two rooms) lined up along a corridor, where each room had only one (always open) door and a light switch. By convention, a door between a room and the corridor was considered as being in both of them. Although Shakey was not dexterous enough to climb on a box or toggle a switch, the STRIPS planner was capable of forming plans for climbing on a box and switching lights on/off. Shakey's six actions were the following:

Go (x,y) which requires that Shakey be at x; x and y are locations in the same room.

Push (b, x, y): Push box b from location x to location y.

ClimbUp(b) and ClimbDown(b): climb onto a box and climb down from a box, respectively.

TurnOn(s) and TurnOff(s): turn a light switch on and turn a light switch off, respectively. To turn a light switch on or off, Shakey needed to be on top of a box.

(a) Describe Shakey's actions in STRIPS notation.

(b) Assume that in the initial state, Shakey is in Room1 which also contains Box1, and the light in Room2 is turned on. Assume also that Shakey's goal is to turn the light in Room2 off. Describe the initial and goals states in STRIPS notation.

(c) Using any planning method you wish (not limited to the STRIPS method), describe how a modern Shakey may form a plan for achieving its goal starting from its initial state.



CORE 3
Consider the problem of developing software for two different types of RoboCup robot soccer teams: a small-size league team and a legged league team.

For the small-size team there is a camera over the field that can very accurately determine the locations of all the players and the ball.  This information is fed into a computer that reasons about the locations of the robots (both teammates and opponents) then sends movement commands to the team's robots using radio control.

For the legged league team there is no overhead camera. Each robot has its own camera with a limited field of view for sensing and a computer for determining what to do. The robots also have wireless Ethernet so they can communicate.

Briefly describe how you would design software for controlling these two different robot teams.  For instance, would you use planning,  behavior-based control or a combination of the two?  Explain the important ways that the problem is different between the two teams, and how your approach to programming them would differ accordingly.

 IF KRR IS ONE OF YOUR SPECIALIZATION AREAS, ANSWER TWO OF THE FOLLOWING THREE QUESTIONS:

KRR 1
Abduction is characterized as inference to the best explanation for a set of data. Medical diagnosis is an example of the abduction task; the data consists of signs, symptoms and other observables, and the explanation is a type of disease.  A simple set-theoretic characterization of the abduction task goes like this:

D is a set of data
DO is a set of observed data (subset of D)
H is a set of hypotheses
Each hypothesis in H can account for some subset of D

Compute HE, a subset of H that can account for DO

Clearly, this is equivalent to the set-cover problem, for which there exist many well-known algorithms. The abduction task becomes complex, however, when the hypotheses in H can interact, e.g., two hypotheses in H together can explain fewer data items than the sum of what each can explain individually.

(a) Briefly describe any set-cover algorithm you know (or design a simple one).

(b) How might the set-covering algorithm be modified to accommodate hypothesis interactions of the above type?

(c) What does your answer to (b) say about the abduction task and the use of set-cover methods for addressing it?


KRR 2
Traditional AI planners require a complete domain theory and a complete world state. Three approaches have been suggested to avoid these problems:

a) case-based planning, in which the planner uses a library of previous problem-solving experiences to solve new problems

b) mixed-initiative planning, in which the planner solves problems jointly wit  another planner (typically, a human)

c) reactive planning, in which the planner solves the problem at a high-level, leaving the details to be developed on the fly during execution

Compare and contrast these approaches. Explain whether they could be combined to solve a greater range of planning problems than either approach individually.


KRR 3
How might analogical comparison processes interact with a spatially-based design task, such as the design of architectural drawings? Consider feature-based models, frame comparisons (as in case-based reasoning), and structure-mapping.


IF COG-SCI IS ONE OF YOUR SPECIALIZATION AREAS, ANSWER TWO OF THE FOLLOWING THREE QUESTIONS:

CogSci 1
Schank's scripts attempted to describe many aspects of the human world and then reason with them.

a) How might statistical techniques be used to help verify the very idea of a script?

b) How might these techniques be used to reason about scripts?


CogSci 2
Contrast the case-based reasoning (CBR) and MAC/FAC models of analogical retrie
val. Pick an example domain, and use that domain to illustrate the weaknesses and strengths of each.
                                                                                                                                                              

CogSci 3 Next Page
 
CogSci 3
With cognitive science, the traditional view of cognition associated with GOFAI  (Good Old Fashioned AI) holds that thinking or intelligence is an abstractable structure that can be implemented in different media, including humans and computers, and identifies cognition with symbol processing that, in humans, takes place within an individual. Recent critics have argued that this view cannot accommodate the facts that the social, cultural, and material environment is essential to human thinking (i.e., human cognition is "embodied" and "embedded"). They argue that to accommodate these facts we need to re-conceptualize "cognition" by moving the boundary beyond the individual mind to the complex system encompassing the salient aspects of the environment (e.g. "distributed" and "situated" accounts of cognition).  This shift requires altering fundamental notions of the structures and processes employed in cognition.

In a recent response to these critics, Vera and Simon argue that the above characterization of the traditional view is a caricature, or at least rests on a misunderstanding of the original claims. They contend that the traditional view does not deny the importance of embodiment and socio-cultural context to cognition. Indeed, Simon's early "parable of the ant" (pp. 63-66) recognizes that in understanding human behavior, the complexity in behavior arises from acting in the environment. Rather, the claim is that what is important about the environment for thinking is abstracted through perception and represented in the symbols generated by the cognitive system. They call unit of analysis in studying cognition a "physical symbol system" (PSS). A PSS has a memory capable of storing and retaining symbols and symbol structures, and a set of information processes that form structures as a function of sensor stimuli. In humans, and any natural or artificial PSS with sensory receptors and motor action, sensory stimuli produce symbol structures that cause mot or actions and modify symbol structures in memory. Thus, a PSS can interact with environment by 1) receiving sensory stimuli from it and converting these into symbol structures in memory and 2) acting upon it in ways determined by the symbol structures it produces, such as motor symbols.  Perceptual and motor processes connect symbol systems with the environment and provide the semantics for the symbols. Clearly, then, they claim, for GOFAI cognition is also “embodied" and "embedded".

Does Vera and Simon's response dissolve the disagreement?


 IF ML IS ONE OF YOUR SPECIALIZATION AREAS, ANSWER TWO OF THE FOLLOWING THREE QUESTIONS:

ML 1
Ever since Samuel's checkers playing program in the fifties, credit assignment has been considered as an important problem in AI.  Yet many learning methods make scarce metion of this problem, e.g., connectionist methods of learning such as backprop in multi-layered feedforward networks.

(a) What is the credit assignment problem? Why is it important?

(b) Does the method of backprop solve the credit assignment problem? If so, how? If not, how can it get away without addressing theproblem?  In either case, what does this say about the problem?


ML 2
What is the no free lunch theorem?  If you don't know what it is go to google.com and type in "no free lunch theorem", complete with the quotes. You'll find several descriptions on the first page.  Now that you know what it is, explain the implications to machine learning algorithms, if any. What does this imply about, say, unsupervised learning techniques?

ML 3
Describe specific example applications illustrating where LDA, PCA,
and ICA are best used.  In other words, describe an application

a) where LDA will produce better results than PCA and ICA.
b) where PCA will produce better results than LDA and ICA.
c) where ICA will produce better results than PCA and LDA.

 IF PERCEPTION IS ONE OF YOUR SPECIALIZATION AREAS, ANSWER TWO OF THE FOLLOWING THREE QUESTIONS:

Perception 1
Some early work in gesture recognition used principal
component analysis on static images and looked at projection values
through time to determine what gesture the user was performing.
Example gestures included waving hello, good-bye, opening and closing
the fist, etc.

a) What role would dynamic time warping play in recognizing these               
gestures?

b) What benefits could be achieved by using modern hidden Markov
model framework (similar to modern speech systems) instead?

Perception 2
Analysis-synthesis techniques in computer vision sometimes recover
a 3D model of a given scene using video or multiple static images, try to recreate a 2D image of that scene based on the model, and then do a pixel-by-pixel Euclidean distance on the actual versus synthesized 2D image as an evaluation metric. Give some examples of when such a metric may be inappropriate.

Perception 2
Describe how a particle filter-based tracker would work for tracking an ant observed by a video camera.

A. What do the particles represent?  
B. What problems arise if there are too few or too many particles?
C.  Why not use a Kalman filter instead?