INTELLIGENT SYSTEMS QUALIFIER
MARCH 2004
ANSWER TWO OF THE FOLLOWING THREE QUESTIONS:
CORE 1
Let us suppose that your neighbor sometimes gets allergic reactions
when he eats out. He knows that you are an AI expert and so consults
you to find a pattern. He provides the following set of data:
Number Restaurant Meal
Day Cost Reaction?
Ex1 Jason's Dinner
Saturday Cheap Yes
Ex2 Mary's Lunch
Saturday Expensive No
Ex3 Jason's Lunch
Friday Cheap Yes
Ex4 Susan's Dinner
Sunday Cheap No
Ex5 Jason's Dinner
Sunday Expensive No
Show how the method of version spaces will find the right model for
this set of examples. This method requires that the first example
in any set of data be a positive instance as above. But suppose that
the order of the first two examples in the above dataset is reversed.
How does this affect the evolution of the model? Do you still get the
same result in the end? Why (or why not)?
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
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 for planning
algorithms, if any. Does this mean that it doesn't really matter
whether one uses Case Based Reasoning, A*, or whatever your favorite AI
algorithm is?
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 a structure-mapping model of analogy and similarity with one
other type: domain-specific models, transformation-based models,
multidimensional scaling models, or case-based reasoning. Now,
with this contrast in mind, pick two comparison tasks: one analogical
(i.e., the comparisons are being done between domains) and one that is
similarity-based (comparison is within a single domain). Coming
back to the two models you've contrasted, which would work best for
each domain? Why?
CogSci 3
Regularity and Robots. As a robot moves around an environment, it
encounters any number of regularities: sets of doorways along a
hallway, vertically symmetric objects such as chairs and (to some
extent) people, even the repetition of its own actions or tasks.
a) How might a robot learn and utilize regularities in its
environment? Consider two cases: the regularity of actions or
operations processed by the robot in the course of a larger task, and
visual repetition or symmetry in the environment. For each,
propose a technique for learning and using that regularity (these can
be stated in general terms).
b) Are there different kinds of regularity? In your design, would the
processing for both kinds of regularity be the same? If not, how
and why would they differ?
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 the
problem? In either case, what does this say about the problem?
ML 2
(a) Consider Support Vector Machines. Briefly justify the
principle that one should maximize the margin. Can you suggest
alternatives to maximizing the margin? Under what circumstances would
they make sense?
(b) Again for SVMs, suppose you were given *only* positive
examples. Now where would you put the boundary? If you have
no idea, do parts (c) and (d) and then come back.
(c) Suppose I told you I was drawing numbers from a uniform
distribution [a b] (over integers) and I tell you a priori that 0<
a,b < 100. Suppose the set I give you is <31,
49> (not actually using set brackets because we'll allow
repetitions in the "set".). How would you select a and b?
(d) Now suppose I tell you the set drawn from [a b] is <31, 38,
47,49,32,35,41,45,31,33, 36,44>. Now what estimate for [a b]
would you use? Why might they be the same estimate as the first
case? Why might they be different?
(e) What does part (b) have to do with parts (c) and (d)?
ML 3
Given an optimization problem, when does it make sense to use a
randomized search technique? Compare and contrast at least four
different randomized search techniques. Under what circumstances,
if any, would you recommend each of those algorithms?
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
In computer vision, many algorithms depend on a coarse-to-fine
approach. Explain how this technique can be used to find a face
in a scene (be sure to include specifics on how coarse-to-fine would be
implemented).
One way to think about video is a 3D volume of pixels with an x, y, and
t (time) dimension. How might coarse-to-fine be used to quickly
locate particular gestures in a video database? Specifically,
suppose we want to find every instance where someone waved their arm
with the "V" for victory sign in video footage of the Iraqi war.
Describe an algorithm using a coarse-to-fine approach that could
efficiently discover instances of this gesture. Your system will
report these video frames to a video editor who wants to include the
clips in a news story he is working on.
Perception 3
(a) Describe how you would design a particle filter-based tracker for
tracking a fixed number of ants observed by a camera? What do the
particles represent? What problems arise if there are too few or too
many particles? Why not use a Kalman filter instead?
(b) Suppose there is a leaf in the middle of the image such that ants
sometimes climb under and are temporarily occluded by the leaf .
How would you modify the tracking system?
(c) Suppose ants can enter or leave the field of view. Now how
would you change the tracker?
(d) Could you use any of these approaches for tracking people in
a subway station? How would you modify any of the above trackers for
this problem?
IF ROBOTICS IS ONE OF YOUR SPECIALIZATION AREAS, ANSWER TWO OF THE
FOLLOWING THREE QUESTIONS:
Robotics 1
a) Contrast the Kalman filter for robot localization with Monte Carlo
localization.
b) For each method, give an example where that filter would be
appropriate but another would not.
c) Suppose we had a very high-degree of freedom manipulator robot with
a single kinematic chain and an end effector with a (noisy) position
sensor, would MCL an appropriate way to infer the configuration of the
manipulator? Explain how inverse kinematics are relevant.
d) http://www.redteamracing.org/ is the web-site of CMU's entry to the
grand challenge. Is it appropriate for them to use MCL ? Why or why not
?
Robotics 2
You have to develop a controller for a (physical) soccer-playing
robot. The robot can sense the angular direction and approximate
distance to both the ball and the goal, assuming they are within the
finite field of view of the sensing system. The controller can
drive the left and right drive wheels independently. Every time
the robot scores a goal, a new ball is dropped randomly on the
(enclosed) field. The goal of the robot is to score as many goals
possible in 10 minutes. The robot is going to be trained for some
fixed period of time (say 3 days).
You would like your controller to use reinforcement learning
techniques. Explain how your controller would use them. (Be as specific
as possible.) What would your states and actions be and why? Then
explain how your controller addresses the following issues: that it is
not able to predict the movement of the ball with certainty, ie It
might move away from the robot when pushed, the size of the state space
and how long it would take to train the robot, and the time
horizon of 10 minutes.
Robotics 3
It is very exciting to see 2 rovers present on Mars at the same time:
NASA's Opportunity and Spirit. Unfortunately however, they are
operating totally independently, I would venture to say that they are
even unaware of each other's existence. You want to change that!
a) Describe how these 2 rovers could work collaboratively on MARS
surface. Keep in mind that these 2 rovers are virtually
identical. What could they do together that a single one could not:
i) If they
were co-located geographically
ii) if
they are located were they are now, on nearly opposite
sides of the planet.
How would they do this in each case? What knowledge represntations and
control strategies could be used to make their shared goals and mission
more effective? What kinds of sensing would be needed for shared
physical interactions? Be specific.
b) Suppose now you had the opportunity to redesign each Rover so that
they were not redundant physically but instead heterogeneous in
whatever ways you thought useful. What new missions could they carry
out with your new design? Describe how they could co-ordinate with each
other as robots with fundamentally different capabilities. Again be
specific in terms of planning, behaviors, sensing, actuation, etc.