INTELLIGENT SYSTEMS QUALIFIER
November 2, 1999
*********************************************************************
Answer 8 out of the 13 questions .
1. What are anytime algorithms? How can they be used as parts of complex systems, such as mobile robots? What are their advantages and disadvantages, and what are some of the technical challenges that the research community needs to address to extend their applicability? Justify your answer.
2. What are totally observable Markov Decision Process models (MDPs)? What are partially observable Markov Decision Process models (POMDPs)? Sutton and Barto describe the "elevator dispatching" problem as follows: "Waiting for an elevator is a situation with which we are all familiar. We press a button and then wait for an elevator to arrive traveling in the right direction. We may have to wait a long time if there are too many passengers or not enough elevators. Just how long we wait depends on the dispatching strategy the elevators use to decide where to go. For example, if passengers on several floors have requested pickups, which should be served first? If there are no pickup requests, how should the elevators distribute themselves to await the next one?" Sketch how one can formulate the problem of elevator dispatching as an MDP or POMDP. Using elevator dispatching as example, sketch the technical challenges that one faces when one a) attempts to formulate probabilistic planning and learning problems as MDPs or POMDPs and then b) attempts to solve them using dynamic programming methods from operations research, such as value iteration or policy iteration (justify your answer).
3. Give a high-level description of how SATPlan works. Describe its advantages and disadvantages compared to more traditional planners, such as partial-order planners. Speculate on promising research directions that might result in planners that combine the advantages of SATPlan with the advantages of more traditional planners (justify your answer).
4. STRIPS-type planning problems can in principle 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).
5. According to http://doc.altavista.com/company_info/press/pr072297.shtml, the AltaVista web search engine at http://www.altavista.com/ provides a feature called "Dynamic Categorization". With a single click, so it is claimed, the user can categorize thousands of web hits from a query into neatly defined categories that are more meaningful than an unordered mass of hits. Using what you know about conceptual clustering algorithms, propose a method by which this feature might be implemented (if you believe the claim) or provide a convincing argument that this is hype (if you don't believe the claim).
6. According to the same press release, the AltaVista web search engine also provides multilingual search capabilities. Indeed, http://doc.altavista.com/company_info/about_av/background.shtml claims full-fledged natural language capabilities, and until recently the search box on http://www.altavista.com/ was preceded by the following prompt: "Type your question in any language". Using what you know about natural language understanding algorithms, propose a method by which this capability might be implemented (if you believe the claim) or provide a convincing argument that this is hype (if you don't believe the claim).
7. Describe some failure modes of the algorithms presented in the Reynolds' paper, "Flocks, Herds, and Schools: A Distributed Behavioral Model", and what you would do to fix these problems.
8. Abduction presents a conundrum for AI for two reasons. Firstly, deductive logic is a common and productive formalism for describing computing machines, but logically abduction is almost the converse of deduction. Secondly, abduction is known to be computationally intractable, and yet it appears to be ubiquitous in cognition. Characterize abduction and contrast it with deduction. Show that under certain knowledge conditions, it is feasible to convert an abduction problem into a deduction problem. Argue whether this conversion is useful for addressing abduction problems.
9. From MYCIN to TEIRESIAS, from SOAR to PRODIGY, from LEX to AUTOGNOSTIC, the notion of "trace" has played many important roles in AI systems. Characterize the various ways in which these systems make use of trace. Do you know of any other use of trace in AI? What makes trace so powerful anyway?
10. Douglas Hofstadter and his associates have recently posited that for a design program to be creative, it must meet the following requirements: (i) the program must make its own decisions, (ii) its knowledge must be rich, (iii) its concepts and inter-relationships must be flexible and context-dependent, (iv) it must be able to evaluate its own tentative output and be able to accept it, and (v) the program must gradually converge on a satisfactory solution through interleaving of judgments and suggestions for improvement. They have also postulated that items (ii) through (v) provide the answer to the issue raised by (i) above.
But it seems that many existing design programs already satisfy the above criteria; in fact, even the old antique HACKER appears to satisfy them. Consider any design program (other than HACKER) that you know about, analyze it in terms of the above criteria, and argue whether you think the program is creative.
11. One of the major issues and distinguishing characteristics regarding behavior-based control is not simply in the design of the behaviors themselves but equally importantly the methods by which the behaviors can be coordinated. At least 2 different strategies can be used:
* Competitive behavioral arbitration
* Cooperative behavioral fusion
a) Describe what's involved in each of these coordination strategies and discuss for each a representative behavioral architecture (name it) that employs it.
b) Is it possible to use two or more different coordination mechanisms within a given behavioral control system? If not why not? If so, explain how?
c) Create (on paper) a simple behavioral controller for a robot that is capable of fetching your newspaper from the driveway in the morning and bringing it directly to you in the kitchen. Feel free to use any of the available modeling methods for expressing such control systems (SR diagrams, functional notation, or FSAs), but express it in sufficient detail to illustrate your understanding of both the perceptual and motor needs of the task.
12. Describe the concept of regularization, and how it can be used to help perception, learning, and control algorithms. Give an example.
13. A well-known issue in intelligent systems is their need to interface programs with some external environment. Since the external environment acts in real-time whereas programs do not (necessarily), when intelligent systems programs are run, special care must be taken to coordinate their execution. Rate monotonic scheduling and deadline-based scheduling are two methods commonly used for IS program execution. First, distinguish RM from EDF (earliest deadline first) scheduling, by defining both. Second, explain how both may be implemented. Third, explain the following statement: "EDF scheduling is dynamically optimal", by commenting on what optimality means in a dynamic system.