All IS students
must answer two of the following three questions:
Consider the following
problem for a robot. The robot
should search the environment for empty soda cans to collect, pick them up, and
then drop them in a recycling container.
The robot carries a canister on its back in which it can store up to two
cans. It does not have a sensor to
tell it if there is anything in the canister. It is provided the following
behaviors (which may be considered ÒoperatorsÓ or ÒactionsÓ in the context of
your favorite AI technique):
The robot uses
continuous sensor inputs in each of the behaviors above, but it uses binary
features to decide which behavior to use.
The robot is provided the following binary perceptual features that may
be used to select behaviors:
Answer these questions
in regard to the problem outlined above:
*
You can assume that if at-can is true, put-can-in-canister is 100% reliable
Core 2
It is said that a cat attempts to pass through a narrow space,
such as the bars on a window, only if the width of space between adjacent bars
is more than the size of his whiskers. Now consider a robot cat, which does not
have whiskers. The robot cat thinks it can pass through the window bars if the
coast is clear, e.g., there is no dog around. Sometimes however the robot cat gets trapped between the
bars as it attempts to pass through because the space between the bars is not
large enough.
a.
Write
the following English-language sentences in first-order logic:
á
There
is no dog around.
á
The
window bar is passable.
á
If
there is no dog around and the window bar is passable, then the cat will not be
trapped.
b.
Now
when the robot cat does get trapped between the bars, can it use logical
deduction (by resolution, for example) to figure out that the bars in question
were not passable after all? Show how (or why not)?
Core 3
Can
analogy be applied to affordances? What are the arguments against applying
analogy to affordances, in the traditional understanding of affordance
perception? Are those arguments convincing, in your opinion? Feel free to use
an example from any domain of research (e.g., behavior-based robotics).
If Perception
is one of your specialization areas, answer two of the following three
questions:
Perception 1
Vision is frequently
proposed as a sensing technology for mobile robot localization and navigation.
For example, a robot with a stereo head could simultaneously reconstruct its
3-D environment and estimate its motion. Suppose you are given the task of
designing a vision-based robot navigation system for the Hall of Mirrors.
This is a building with the property that every interior surface is
covered with mirror glass. You can assume that all walls are planar and that
any pair of walls are either parallel or orthogonal. Design a
sensing and navigation strategy that would map the interior of the Hall of
Mirrors. Describe both the sensing algorithms and navigation process in
detail. Given an accurate map and a known starting point, how could you
use vision sensing to follow a desired path to some destination? Provide a
detailed algorithm description. You are allowed to configure the robot
with any reasonable number of cameras (and light sources), but assume that no
other sensors (e.g. dead reckoning, sonar-ranging, etc.) are available.
The Shell Game is a
standard carnival game in which three containers of identical shape and color,
such as cups or bowls, are placed upside-down on a tabletop. A small ball
is placed under one of the cups by the dealer, who then shuffles the cups
around, face down, while you watch*. After a certain number of moves in
which cups are exchanged, shifted, and so forth, you are asked to guess which
cup the ball is under. In many
real-life versions of this game, both money and cheating are involved. Here
you are asked to design a computer vision system that could solve a fair
version of this game. You can assume that you have a camera view looking down
on the tabletop from above and that the dealer handles the cups by
grasping them from above and sliding them around on the tabletop without
lifting them. Although the dealer doesn't cheat, he/she is allowed to make
distracting hand motions as well as ones that actually move the cups.
Describe an approach to solving this game using the output of a single video
camera. Characterize the core technical problem. Describe all of the
necessary algorithms as well as your solution approach, and discuss
possible failure modes of your system.
*You may wish to consult
one of the many web versions of this game, such as http://www.free-web-games.com/games/shell.html, for
an example of the procedure.
Suppose you are asked to track monkeys in a cage. The monkey cage
has a video-wall on the back-wall portraying various jungle-scenes to put the
moneys at ease. Various methodologies have been proposed for tracking targets
with a changing shape and/or appearance. Three of them feature prominently in
the perception reading list: Kass & Witkin's Active Contour Models, Cootes
& Taylor's Active Shape Models, and the more recent Robust Online
Appearance Models by Jepson et al.
a.
Please
contrast these three approaches within the context of the application
b.
which
one you would use, and why?
c.
How
will your answer change if you know the video-wall will be turned off during
these experiments?
If Machine
Learning is one of your specialization areas, answer two of the following
three questions:
Machine Learning 1
Naive Bayes (NB)
classifiers have been shown to work surprisingly well for a wide range of
classification problems. In some domains, substantial effort is required to
improve upon their performance. Why is this surprising? How can you
explain their success? Compare the following three classifier architectures:
Naive Bayes, Neural Network, Support Vector Machine. Under what conditions
would you expect each of them to dominate the others in performance? In your
discussion, consider the following characteristics: number of features, amount
of training data, presence of label noise, computational cost at run-time
(testing phase). A NB classifier can be viewed as a statistical graphical model
(specifically, a Bayesian network). From this perspective, one recent proposal
to improve upon the performance of NB classifiers suggests adding
additional edges between pairs of features to the model. Why would this be
helpful? Comment on when this approach is likely to work well. Can you think of
any reasonable criteria for deciding how to add edges, from the standpoint of
both accuracy and computational cost?
In J Yedidia, W.
Freeman, Y Weiss (2003). "Understanding Belief Propagation and Its
Generalizations", Yedidia et al. proposed an interesting scheme to do
belief propagation in binary Markov random fields.
Sutton
(1984), among others, has made a distinction between two kinds
of
credit assignment problems: temporal and structural. What is the difference
between the two?
Reinforcement
learning is a learning technique that addresses the temporal credit assignment
problem. Why is reinforcement learning suitable for temporal credit assignment
but not for structural credit assignment?
Describe
any AI method you know (or propose a new one) for addressing the structural
credit assignment problem. Illustrate the method in a simple problem-solving
domain, say tic-tac-toe.
If
Robotics is one of your specialization areas, answer two of the
following three questions:
Robotics
1
The
DARPA Grand Challenge focuses on off-road navigation over desert terrain for
long distances (around 150 miles) at fairly high speeds (25 mph or so).
(a)
What are two major
technical problems in achieving a winning entry?
(b) The Army currently uses a variant of Albus'
architecture, a derivative of NASREM referred to as 4D-RCS, for these sorts of
applications. What is the basis by which navigation is conducted with this type
of system in terms of sensing, planning, and acting?
(c)
Several of last
yearÕs entries used behavior-based approaches. How would this differ from the
approach described in (B)? What potential advantages/disadvantages would this
yield over the 4D-RCS approach?
(d)
Describe what you
would use for the perceptual capabilities for your entry (both sensors AND
algorithms), which must navigate on poorly defined dirt and gravel roads, avoid
obstacles and deal with barbed wire, brush and other vegetation. Assume you
entry is a standard sport-utility vehicle (SUV). Your design should incorporate existing algorithms (i.e.
donÕt be concerned about creating an entirely new approach).
The mapping overview paper by Thrun on the reading list provided
an overview of recent SLAM approaches, including EM-based mapping and FastSLAM.
a.
Please
contrast both approaches in terms of what quantity they are optimizing, and
what data is needed.
b.
(b) In
a large environment, which one do you think will perform better, and why ?
c.
Is a FastSLAM approach feasible if
instead of landmarks we use grid-based maps ? How ?
d.
how
would you implement FastSLAM if instead of 2D landmark measurements we instead
have a robot with an omni-directional camera-rig ?
As
robotics as a science continues to mature, ethical implications of our work
become more and more relevant. Indeed Bill Joy, co-founder of Sun Microsystems,
has gone on the record stating that robotics (as well as bio-engineering and
nano-technology) may lead to the downfall of mankind.
(a)
Drawing from your
own personal research in the area, explain the ethical consequences, both
positive and negative, of the work you have already conducted or are currently
conducting in this area.
(b) Given the apparent dangers associated with the
field, why should you personally be granted license to become a robotics
practitioner, especially at the Ph.D. level where you will articulate new
research agendas? What are your own personal responsibilities (if any) to
society in this regard?
If Planning and
Search is one of your specialization areas, answer two of the following
three questions
Like many other AI systems, planners often model the problem of
acting as continually repeating three steps: 1) sensing the world, 2) deciding
on an action to take, and 3) executing that action. Also like many other AI
systems, they often assume a synchronous world where each action takes a single
time step and the system otherwise halts while an action is executing. Imagine instead a more complicated
model where multiple actions can be taken concurrently at each decision epoch.
Assume further that each action is temporally extended; that is, each action
may (perhaps stochastically) take more than one "step". For example: while walking towards a
car one might walk, reach for the keys, talk to a companion and avoid obstacles
simultaneously.
First, describe several issues that arise in such an environment.
Second, describe the strengths and weaknesses of your favorite modern planning
techniques with respect to such an environment. Finally, briefly discuss how you might extend some of those
techniques and what the trade-offs would be in implementing your extensions.
What is the relationship between planning and reinforcement
learning?
In your discussion be sure to formally define planning, Markov
Decision
Processes (MDPs) and partially observable Markov Decision Process
(POMDPs). Further,
explain both the technical difficulties that arise when formulating
probabilistic planning problems as MDPs or POMDPs as well as the technical
challenges of learning from data those representations (e.g., STRIPS and SAT
encodings) that traditional planners use.
STRIPS-type planning problems can be solved with search methods,
such as depth-first search or variants of A*. Pick either GraphPlan or ASP.
Sketch how the planner you chose uses search methods for planning. What are some
of the limitations of the planner you chose? Speculate on promising research
directions that might overcome these limitations (justify your answer).
If Knowledge
Representation and Reasoning is one of your specialization areas, answer
two of the following three questions:
Knowledge
Representation and Reasoning 1
Nebel and Koelher
(1995) (see citation below) provide complexity results for case-based planning
that are quite pessimistic. In particular, by expressing the plan generation
and the plan modification problems in a STRIPS-like propositional language,
they are able to show that the worst-case time complexity of plan modification
in general is no better than that of plan generation. This, they claim, is true
even if plan modification is conservative, i.e., it reuses as much of the old
plan as possible and makes minimal changes for achieving the new goal (which is
what case-based planners typically do). One reason for this, they say, is that
the complexity of determining the maximal reusable part of the plan itself is
in the same class as that of generating the plan.
This of course flies against the intuitions, hypotheses and
experiences of case-based planning. How may one reconcile the theoretical
results of Nebel and Koelher with the experimental evidence for case-based
planning?
[citation: http://www.informatik.uni-freiburg.de/~koehler/papiere/planning.html
; to save time, look at the short
IJCAI paper rather than the long AIJ one; also focus on the introduction,
discussion and concluding sections, not on the proofs of the various theorems.]
Knowledge
Representation and Reasoning 2
a. What are the differences between logic-based and
justification-based truth-maintenance systems (TMS)?
b.
Pick any
problem-solving domain, and determine whether a justification- or logic-based
TMS would be most suitable. Justify your answer.
Knowledge
Representation and Reasoning 3
Model-based autonomy (Williams and Nayak 1996; Muscettola, Nayak,
Pell and Williams 1988) is a recent paradigm for designing
autonomous agents. The key idea is that if, in addition to a continuous model,
a discrete model that captures the causal structure of a hardware system is
available, then model-based diagnosis can be used to identify causes for
malfunctions in the hardware and to recover/reconfigure/repair the system. Since model-based autonomous systems
have been deployed aboard Cassini, a recently launched spacecraft for exploring
the moons of Jupiter, they make an AI success story.
However, an important limitation of of model-based autonomous
systems is that they are applicable only to immobile agents; in case of
Cassini, model-based autonomy is limited to the immobile engines of the
spacecraft, not to the mobile spacecraft as a whole.
a.
Why is
model-based autonomy as practiced by Williams and Nayak limited to immobile
agents? That is, what is the source of the limitation?
b.
What
additional issues arise in realizing model-based autonomy for mobile agents
that can explore an environment, make decisions, form plans, etc?
c.
How
might the paradigm of model-based autonomy be adapted to address autonomy in
mobile agents?