KBAI CS 4635, CS 7637, OMS 7637 Ashok Goel
Fall 2014
Final Examination
Assigned: Monday, December 1st (via T-square) Due: Sunday, December 7th (via T-square)
General Instructions
(i) This is a take-home examination. This means that you may consult any material from this class and beyond. However, you
may not consult any other person on any aspect of the
examination: the answers must be wholly your own work.
(ii) Please answer all four questions. Each question pertains to a
specific problem. All questions carry equal weight. However, the questions become progressively more open-ended from the first to the last question.
(iii) Your answer may use one, more, or all of the lessons we learned in the KBAI class. In writing your answers, please make it clear what and how you are drawing from KBAI lessons. However, your answers need not be constrained by KBAI concepts and techniques: you are welcome to bring in ideas from other classes or your own experience.
(iv) Long essays in English will not count nearly as much as clear and precise answers in the language of computing: computational architectures, knowledge representations and data structures, methods and algorithms. Use examples to illustrate your answers. Justify the choices you make.
(v) You may think of each question on the examination as roughly equivalent to an assignment in the class. This should give you some idea about the requirements for a good answer.
(vi) Please submit only computer printouts. However, it is okay to draw figures by hand and the scan them into your answers.
(vii) Please start your answer to each question on a new page.
Please write your name on each page.
Question 1
Let us suppose that the US Department of Homeland Security hires you to develop an AI system for assisting intelligence analysts. Real intelligence analysts frequently receive reports from field stations from across the world about a variety of events. Many of these events turn out to be quite innocent; however, some might be indicative of a criminal (perhaps even a terrorist) plot. Let us assume that some low-level natural language processing extracts events from the field reports in the form of frames like this: (event (actor, object, location, time, instrument)). Let us consider what happens when the following input arrives in this specific order:
(Bought (JaneDoe, icecream, Atlanta, Tuesday, cash))
(Ate (JaneDoe, icecream, Atlanta, Tuesday, spoon)) (Videotaped (TidMarsh, bank, Atlanta, Thursday, video-camera)) (Bought (TidMarsh, gun, Atlanta, Monday, credit-card))
(Stole (TidMarsh, car, Atlanta, Friday, …))
(Drove (JaneDoe, car, Atlanta, Tuesday, …))
(Drove (TidMarsh, car, Atlanta, Friday, …))
Since you have taken the KBAI class, you decide to develop a story understanding system to act as an intelligence analysis assistant. The system consists of a long-term and a short-term memory. The long-term memory consists of a number of stories such as that of bank robberies. Develop a computational architecture, knowledge representations and pseudo-algorithms for the story understanding system so that it may recognize that the above input indicates that while JaneDoe’s actions are fairly typical and thus likely innocent, Tidmarsh might be preparing to rob a bank.
Question 2
Let us suppose that a top IT company, such as Apple given its recent misadventures with routing systems, hires you to build a new, personalized, adaptive routing system for navigating urban areas, such as metro Atlanta, by car. Initially, the routing method works as in current systems
(such as, say, Mapquest): it has a detailed map of Atlanta (or whatever major city you are familiar with) and uses some shortest-path algorithm to find a route from a given initial location on the map to the goal location. However, as people (you, family, friends, strangers, everyone) use the system, some of them use social media to enter a whole lot of additional information into the system in the form of their navigation experiences, for example, information that they liked some routes because they worked out very well, that they were okay with some routes, that they did not care for the routes that were too busy and slow, or dangerous, or ended in
failure, etc. Thus, over time, the route planning system acquires a large case base in addition to its preexisting map of the city.
Write/draw a computational architecture, knowledge representations and pseudo-algorithms for a multiple-strategy route planning system that uses the case-based method when an appropriate case is available, and the map-based method otherwise. Your system should also be able to combine the two methods, for example, by using the map-based method for case adaptation. Illustrate using examples.
Question 3
One of the common forms of learning in humans is learning by imitation: humans learn by imitating their parents and siblings, friends and colleagues, teachers and mentors, peers and associates, etc. In fact, many cognitive scientists believe that learning by imitation is a core process of human learning. Yet, cognitive science does not yet fully understand the processes of learning by imitation: What exactly do we learn when we imitate (a sequence of actions, a plan, a goal, or something else); and how we do learn it? Consider, as an example, a toddler on a high chair in the living room watching her father tilt a coffee mug into his mouth. The toddler imitates by tilting her water cup into her mouth. What exactly does the child learn and how did she learn it? Did the child learn about the goal of tilting the mug into one’s mouth? How did the child replace the observed mug with a cup? As you may expect, research on robot learning by imitation too is quite nascent.
Develop a computational model for learning by imitation using the above mentioned toddler scenario as an example. Possible methods include using classification, case-based reasoning, analogical reasoning, explanation-based learning, learning by correcting mistakes, etc – this list is not exhaustive. Pick any one KBAI method and describe how it works for some aspect of the problem. You are welcome to elaborate on the above scenario to meet the needs of your model. Please show computational architectures, knowledge representations, and high-level
pseudo algorithms.
Question 4
Environmental sustainability is a growing concern world wide. A major element in addressing environmental sustainability is the products that humans discard as waste. For example, in the US alone, 4 billion pounds of carpet are discarded each year in landfills (about 12 pounds per person per year). Apparently more than 70% of the discarded carpet is reusable and also cheaper to use than raw materials. However, the US carpet industry presently reclaims less than 5% of the discarded carpet. This is
because of several reasons: current policies do not require that consumers send discarded products for reuse and there are few economic incentives for customers to do so, and while manufacturers may incur significant economic benefits from reusing discarded products, there is little information technology that supports the manufacturers in reclaiming the discarded products. This pattern repeats itself in industry after industry. The problem of reclaiming discarded products (carpets, tires, batteries, bottles, etc.) is sometimes called reverse supply chain management. If we could help manufacturers reclaim an order of magnitude more discarded products than at present, we could simultaneously and substantially
help both the environment and the economy.
The question then becomes whether and how can we develop an
AI system for reverse supply chain management that would help manufacturers (and/or consumers) reclaim discarded products. Potential solutions could cover a very wide range, such as exploiting large scale data on the sale of products, making each product “smart” so that it can alert the manufacturer at the time of disposal, looking at biological processes for recycling/reuse as analogies for reclaiming products that have outlived useful lives, exploiting social media for detecting trends in product disposal, etc. This list is not exhaustive.
Design an AI system that can address the above problem using any KBAI strategy you envision. Please provide details. For example, if you decide to use data on the sale of products, describe how the KBAI agent will actually process that data; if you decide on a “smart” product that alerts the manufacturer, describe how the KBAI agent will help process the communication; if you decide to exploit social media for detecting trends in product disposal, describe how your KBAI agent will actually detect a trend, and so on. Use examples to illustrate your answers.