IS Qualifier Fall 2002 Exam
CORE COMPONENT – Everyone must answer 4 of the following 6 questions
AI-1
In the Star Trek: The Next Generation episode "Darmok", Captain Picard and
his crew encounter an alien race that communicates only by reference to specific
episodes in their history and culture. For example, suppose you wanted to
express love. Instead of saying "I love you", you might say "Juliet on the
balcony". The person you are speaking to would conjure up a mental image
of the Shakespearean scene and thereby understand what you were trying to
communicate.
In IS terminology, we would call this "case-based NLP". There is some evidence
that humans communicate in this manner, albeit not exclusively. For example,
"you're an Einstein", "do a Napolean for the camera", and "he met his Waterloo".
For the purposes of this question, assume that case-based NLP is the only
method available for communication.
a) Draw an architecture of a case-based system that could understand a sentence
uttered in this manner. The architecture should include the processing modules
that are needed (e.g., a module to retrieve a case) as well as the knowledge
repositories that are needed (e.g., a library of cases). Be specific about
what each module does (e.g., how does retrieval work) and each repository
contains (e.g., what does a case contain).
b) .Take the following example utterance, "George Washington and the cherry
tree", intended to communicate the assertion "I am telling the truth". Describe
how your system would understand this sentence. Step through the process
systematically and describe the final output.
c) What would your system do with an utterance for which it had no referent,
such as the following utterance from the episode: "Darmok and Jilad at Tanagra"?
d) The episode writers suggest that the aliens understand their language
by creating a mental image of the scene in their head, as if they were literally
seeing a picture of the scene. Would this kind of capability aid your case-based
reasoning system? Why or why not?
AI-2
Let us suppose that an automated reasoner is given the following facts:
FOR ALL x,y,z: gt(x,y) AND gt(y,z) -> gt(x,z)
FOR ALL a,b: succ(a,b) -> gt(a,b)
FOR ALL x: NOT gt(x,x)
We want to prove that gt(5,2).
Let us consider the following attempt at a proof:
NOT gt(5,2)
NOT gt(x,y) OR NOT gt(y,z) OR gt(x,z)
------------------------------------------------------------
| 5/x,2/z
|
NOT gt(5,y) V NOT gt(y,2)
NOT succ(a,b) V gt(a,b)
--------------------------------------------------------
| y/a,2/b
|
NOT gt(5,y) V NOT succ(y,2)
NOT gt(x,y) OR NOT gt(y,z) OR gt(x.z)
----------------------------------------------------------------------
| 5/x,y/z
|
NOT gt(5,y)
OR NOT gt(y,y) OR NOT succ(y,2)
-------------------------------------------
|
|
TRUE
What is wrong with this proof? What changes to the unification and/or resolution
procedures implied above are needed to fix it? Make the needed changes and
show the correct proof.
AI-3
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)?
AI-4 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:
a) that it is not able to predict the movement of the ball with certainty,
ie it might move away from the robot when pushed,
b) the size of the state space and how long it would take to train the robot,
and
c) the time horizon of 10 minutes.
AI-5 Machine learning methods are sometimes categorized as “symbolic”
or “numerical”. (The IS faculty love to argue about this constantly!)
a) Provide a technical definition or two (of your own) of what it might mean
for a machine learning method to be symbolic versus numerical.
b) Identify at least two examples for each category, and justify why each
belongs where you've put it.
c) Describe in what ways numerical methods are symbolic and symbolic methods
are numerical.
d) Identify the strengths, weaknesses, and maximum potential of each category
of approaches, and the difficulties in achieving those potentials.
Back up your arguments with plenty of concrete examples. In particular,
don’t be victim to the current trend of declaring numerical to be better
for all purposes. When and how is symbolic learning a good idea?
AI-6 The students last year answered the following question:
Assume that you are on NASA's team to develop better AI planners for controlling
an autonomous spacecraft. The planner is always in charge of the spacecraft
and has to plan all spacecraft maneuvers (including emergency maneuvers).
Describe the strengths and weaknesses of STRIPS-based partial-order planners
in this context, and suggest five promising research directions for how to
make this and other artificial intelligence planning technology better suited
for the task.
Now it’s time for the next generation of design. Instead of a single
space-craft, the planner is responsible for directing 3 cooperating robotic
agents to perform various tasks. When performing these tasks the robots
are not necessarily in contact with the planner or even possibly each other
(they might be but can’t count on it).
How should the planning change, i.e. for a variety of methods that would
have been suggested by the first design team, which methods of planning might
be best adapted to this multi-agent planning task? Are emergency responses
now easier or harder – and under what assumptions? Does the 10 fold
increase in compute power matter?
ROBOTICS SPECIALIZATION – If you elected a robotics specialization,
answer the following 2 questions.
R1. Robots for the home seem to be moving into the mainstream, with
vacuum cleaners (Roomba), Toy robots (My Real Baby), Hobby Home robots (ER1),
Entertainment Robots (AIBO), even Humanoids that can be rented by the very
rich (Asimo). Robots at home though pose special challenges to roboticists.
a) What is fairly unique about the home environment that both makes it more
favorable for the deployment of robots yet also makes it more difficult than
say an outdoor or military application?
b) Human-robot interaction is absolutely essential when robots interact in
such close quarters with people. What sorts of research has recently been
conducted in the robotics community that would enable robots to be more accepted
by people in their homes? How should this type of research be conducted?
(i.e., sketch out a simple experiment).
c) Just seen on CNN: A RoboDragon being marketed in Japan for home security.
It is a lumbering quadraped, looking somewhat like a Komodo Dragon. If you
were going to write the software architecture for this robot that could perform
robot security tasks at home, in the presence of your family, what design
would you recommend, what sensors would you choose, and what tasks should
it be able to perform (and how)?
R2. Describe how schema theory can serve as the interlingua
between biologists and roboticists. What is a schema to a neuroscientist
and how do they use it for sensorimotor modeling?
From a computer scientists perspective, schema-based approaches afford recursive
formulations of control systems that other approaches, such as subsumption,
are hard-pressed to match. Give an example of the power of recursive expression,
using assemblages, in a schema-based controller.
Behavioral coordinators are also often at the root of architectural distinctions
in behavior-based systems. Describe at least 3 different types of coordination
mechanisms, and show for two how they can be used to control the simple task
of finding and following a wall inside a room. Use any coordinated combination
of these available behaviors (as you choose to define them):
1) avoid-obstacles
2) move-in-a-given-direction
3) wander-randomly
4) move-along-wall
If you feel the need to create other behaviors, feel free. Show the S-R and/or
FSA diagrams that show how these behaviors are coordinated.
COGNITIVE SCIENCE SPECIALIZATION – If you elected a CogSci specialization,
answer 2 of the following 3 questions .
C-1 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?
C-2 Recent psychological studies have found evidence of an interesting
trait of memory: that we may remember events better when we attempt to recall
them in a similar emotional state. This is potentially quite surprising,
since emotions are typically ignored in models of memory (and in cognitive
modeling in general until recently). In a domain of your own choosing
(e.g., planning), explain:
a) Why might this be a useful trait for memory to have?
b) Given a particular memory model (ACT-R’s retrieval system, CBR, MAC/FAC,
or any other cognitively-based model), how might this trait be incorporated
into it?
c) How convinced are by your own model? Is the addition of emotion information
natural or awkward?
C-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 mind. Recent critics have
argued that this view cannot accommodate the facts that the social, cultural,
and material environment are 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
sensory stimuli. In humans, and any natural or artificial PSS with
sensory receptors and motor action, sensory stimuli produce symbol structures
that cause motor 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?