FACULTY RESEARCH GUIDE 1999-00 Computer Science Department Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 (412) 268-2565

This file presents the current research interests of the faculty members of the Carnegie Mellon Doctoral Program in Computer Science, along with those of associated faculty of other departments. Each person listed has written his or her own section of the Guide. There has been no attempt to eliminate redundancy by combining descriptions of related work. In addition to the research descriptions, indices at the end of the document list the faculty by interest keywords, and by project names.

The primary purpose of the Guide is to acquaint new and prospective members of our community, especially graduate students, with the on-going research and with the faculty involved. We also use the Guide to inform outside colleagues and visitors, and to direct those looking for persons knowledgeable about any particular topic.

The goal of my research is to understand how people organize knowledge that they acquire from their diverse experiences to produce intelligent behavior. The concern is very much with how it is all put together and this has led to the focus on what are called "unified theories of cognition." A unified theory is a cognitive architecture that can perform in detail a full range of cognitive tasks. Our theory is called ACT-R (Anderson & Lebiere, 1998) and takes the form of a computer simulation which is capable of performing and learning from the same tasks that subjects in our laboratories work at.

ACT-R is also an instance of a hybrid cognitive architecture in that it represents knowledge symbolically as rules and facts but also has a neurally-based activation process that determines which facts and rules get deployed in which situations. We have engaged in extensive analyses of the situations which people have to deal with in order to understand how each of these components should work together to yield adaptive behavior.

Our research has two major branches. First, in the laboratory we are looking at how people learn and solve problems in very well-defined situations. Here we are interested in things like how strategies for problem-solving evolve, how people discover things about a new domain, how they deal with the working memory load imposed by the tasks, and how they get faster at accessing information relevant to task performance. Our subjects all interact with experiment-running computer programs and we try to develop ACT-R simulations that can interact with the same programs, take the same actions, make the same eye movements, and display the same latencies. The emphasis in this research is very much in getting the detail of the simulation to match up with the detail of the behavior.

The other branch of our research involves a much broader focus. We have taken on modeling the cognitive competences that are taught in the domains of mathematics, computer programming, and cognitive psychology. Much of the motivation for this research is to be able to tap into real situations where people learn and solve problems and understand the implications of these domains for the cognitive architecture. We have built larger-grain ACT-R simulations that are capable of solving problems in these domains and have developed computer-based instruction around these cognitive models. Many of these computer-based instructional systems have the cognitive models as a component and attempt to understand student behavior by actually simulating what the student is doing in real time. These are called cognitive tutors and are currently being used to help teach courses in schools around the country. Much of this research has gonebeyond the original goals of understanding human cognition and now is part of a major effort to produce a significant improvement in American mathematics education.

Robot Teams
I am interested in all aspects of the development of effective robot teams. To build effective teams we must address many challenges that are not a concern for single robot systems. Cooperation, diversity, communication, distributed learning and distributed planning are a few examples. Of these, two of the most interesting (and open) issues are robot team diversity and the development of cooperative behavior:

Robot Team Diversity
We have developed a metric of robot team diversity that has been used experimentally in the evaluation of robots performing multirobot tasks (e.g. soccer, foraging and cooperative movement). It was discovered that behavioral diversity is an effective means for providing cooperation in multirobot teams but that the utility of diversity depends on the task. For instance, behavioral diversity seems to be useful in robot soccer teams, but not in foraging teams.

We now have a formal basis from which to investigate a number of important open issues relating to diversity. Why, for instance, is diversity important in some tasks, but not others? How does communication between agents impact the need for diversity? These are some of the issues we will be investigating over the next few years.

Social Potentials for Cooperative Behavior
The potential field approach is a well-known strategy for robot navigation. In this paradigm, repulsive and attractive fields are associated with important objects in the environment (e.g. goal locations or obstacles to avoid). To navigate, the robot computes the value of the vectors corresponding to each relevant field, then combines them (usually by summation) to compute a movement vector based on its current position. The result is emergent navigational behavior reflecting numerous constraints and/or intentions encoded in the robot's task-solving behavior.

We have extended the mechanism to multiple robots so that the potential field impacting a robot's path is shaped by the presence of team or opponent robots. We call these potential functions "social potentials." This approach provides an elegant means for specifying team strategies in tasks like foraging, soccer and cooperative navigation.

While we have found the approach to be quite useful, it has not been analyzed or evaluated formally. The implementations have been ad hoc systems built to address a particular research goal. It would be very useful to explore this topic in more rigor and depth.

One research direction we plan to follow is to examine how and why animals exploit "social potential" behavior. Examples include flocking by geese (presumably for efficiency), fish schooling, ant columns and distribution of predatory animals by scent marking. It is likely that robot teams can benefit from these behaviors in the same ways animals do.

We will also characterize the various forms of social potentials for cooperative behavior. What types/shapes of potential fields for instance, might be useful for multirobot tasks? Can we enumerate or classify these functions? Finally, we will implement and evaluate these functions in practice (in simulation and on multirobot teams).

My main research interest is in the interaction between algorithms and languages, mostly in the context of parallel computing, and has consisted of both theoretical and experimental work. As programming languages become higher level, implementations become more complex, and parallelism becomes pervasive, users are naturally becoming more removed from the hardware and its costs. Rather than trying to bring programmers down to the level of the machine to understand and get good performance, however, I believe that we should be trying to bring languages and cost models up to the level of the programmer. My research therefore centers around questions of how to model costs (e.g. time and space) for very-high level programming constructs (e.g. dynamic parallelism, futures, garbage collection), of how to design systems so these costs have meaning, and of how to make use of these features in effective algorithms design.

My recent work includes work on the PSCICO project with Gary Miller, Bob Harper and Peter Lee. Here we are looking at how to use very-high level programming constructs in geometric and scientific algorithms. We hope this project will give guidance to future language design, and will identify new ways of thinking about algorithm implementation. I also work on applied algorithms, parallel garbage collection, parallel scheduling, efficient parallel algorithms, and continue to work, to some extent, on the NESL programming language, a parallel language that my students and I developed in the early 90s.

My main research interests are in computational learning theory, on-line algorithms, and approximation algorithms. I also am working on applying techniques from graph algorithms to planning problems.

Computational Learning Theory. The goals of computational learning theory are to provide a mathematical understanding of the issues involved in getting machines to learn from experience, as well as to provide new analyzable algorithms. One of the questions I am particularly interested in is: under what conditions can one quickly hone in on the most relevant information in a large feature space? What fundamentally is involved in this task? Some simple versions of this question can be viewed as trying to combine a large number of sources of advice that may be available in a learning setting. Other versions of this question have close relations to cryptography. I am also interested in algorithms for active learning --- learning in settings in which one may actively probe the outside environment to gain additional knowledge --- and methods for fruitfully combining both labeled and unlabeled data in a learning task.

On-line algorithms. On-line algorithms involve repeatedly making decisions knowing only one's past history and without knowledge of future events. For instance, what is a good strategy for deciding when to switch lanes in rush-hour traffic? The Metrical Task System problem is a general on-line problem I have been interested in that (at some level) models a number of settings of this form. Roughly, an algorithm must repeatedly decide whether to continue in its current state or to incur a cost to move to a seemingly better state; but, only at the end, in hindsight, can it tell if it really made the best decisions. There are many important open questions in this area, such as how to make good use of partial prior knowledge, and how to use randomization to beat known deterministic approaches.

Approximation algorithms. Many important problems turn out to be NP-hard, implying that it is unlikely there will be algorithms for them that are both efficient and optimal in the worst case. One approach, then, is to find algorithms that produce approximately-optimal solutions. I am interested in a variety of problems of this sort including traveling salesman-like problems, graph coloring problems, and problems in DNA sequencing. For example, an interesting problem from this perspective is the "trick-or-treater's problem": given a weighted graph (a map of a neighborhood) and an integer k (a candy bag of a certain size), find the shortest route that visits at least k vertices (enough different houses to fill the candy bag). Broadly, the key challenges are to understand the approximability of fundamental problems, as well as to better understand the set of fundamental techniques for achieving good approximation guarantees.

Domain Independent Planning. I have recently become interested in applying techniques from graph algorithms to the setting of domain independent planning. Together with Merrick Furst we have developed the Graphplan planner based on this approach, and I have most recently been exploring the extent to which this method can be applied to probabilistic planning settings.

URL: http://www.cs.cmu.edu/~avrim

Complexity and Real Computation. In 1989, Steve Smale, Mike Shub and I introduced a theory of computation and complexity over an arbitrary ring or field R. In 1997, along with Felipe Cucker, we published a book, Complexity and Real Computation (Springer-Verlag). From our Introduction:

"The classical theory of computation had its origin in the work of logicians -- of Godel, Turing, ... , among others -- in the 1930's. The model of computation developed in the following decades, the Turing machine, has been extraordinarily successful in giving the foundations and framework for theoretical computer science.

"The point of view of this book is that the Turing model (we call it "classical") with it's dependence on 0's and 1's, is fundamentally inadequate for giving such a foundation for modern scientific computation, where most of the algorithms - with origins in Newton, Euler, Gauss, et al. - are real number algorithms."

Our approach applies to the analysis of algorithms over continuous domains as well as the discrete. The classical theory is recovered if we allow the ring R to be Z_2 (the integers mod 2). But now R can also be the real or complex numbers, or any other field. The familiar complexity classes P, NP and fundamental question "does P= NP?" make sense over R and moreover, relate explicitly to fundamental problems in mathematics such as Hilbert's Nullstellensatz. Thus, we are particularly interested in research concerning the complexity of algorithms that solve systems of polynomial equations.

Transfer Principles for Complexity Theory.
A powerful tool of the classical theory is that of reduction: If problem A can be shown to be reducible to problem B, then techniques for solving B can be used to solve A. Classically, A and B are both discrete, i.e. defined over the same domain Z_2. But now we have an additional powerful tool, namely that of transfer:

When there was essentially only one model of computation (i.e. over Z_2), it didn't make sense to transfer complexity results from one domain to another. But now, transfer becomes a real possibility. We can ask: Suppose we can show P=NP over the complex numbers (using all the mathematics that is natural here). Then can we conclude that P=NP over another field such as the algebraic numbers or even over Z_2? (Answer: Yes and essentially yes.)

I am particularly interested in such transfer results and problems that appear in the interface between the discrete and the continuous.

My main interests concern the mathematical semantics of programming languages. I believe that proper attention to semantic foundations can yield significant benefits in developing techniques for proving properties of programs, in program design, in language design and implementation.

I am particularly interested in developing intensional semantic models, in which one is able to reason both about the correctness and efficiency of programs. This is in contrast to most traditional semantic models, which are extensional and focus on the input-output behavior of programs while abstracting away from computation strategy. I am working mainly on the semantic foundations of parallelism. This work includes the development of axiomatic proof techniques for establishing behavioral properties of parallel systems, design rules for parallel networks that guarantee desirable behavior such as deadlock-freedom, and the design and implementation of programming languages that employ parallelism uniformly and cleanly.

A semantics for a programming language is an assignment of meanings to program terms. For a semantics to be useful it should accurately capture the computational behavior of program terms, at an appropriate level of abstraction.

I believe that major improvements in the formal treatment of program properties can be achieved by paying careful attention to semantics. If we want to reason about a particular behavioral notion (such as partial correctness) we should first define a mathematical model for programs which precisely captures this behavior without being overly complicated. Ideally, we would like a fully abstract semantics: terms should be given the same meaning precisely when the terms would induce identical behavior in all program contexts. The construction of fully abstract models is by no means an easy task, and depends in any case on the underlying notion of behavior.

For modelling and reasoning about certain types of program behavior, such as partial or total correctness, an extensional semantics is satisfactory: the meaning of a program can be chosen to be a (partial) function from initial states to final states, and all details of how the program goes about its computation can be suppressed since all we really need to keep track of is the state transformation that the program induces. However, such a semantics is no use if we want to make comparisons between programs for the same function. In an extensional semantics all sorting programs have the same meaning, whereas we might well want to design a semantics with which we can compare sorting programs with different computation strategies. This motivation leads to a desire for a theory of intensional semantics. In an intensional semantics the meaning of a program is taken to be an algorithm rather than simply a function. An algorithm can be viewed as a function together with a (mathematical representation of a) computation strategy. I have recently developed a category-theoretic approach to the modelling of algorithms, and applied these ideas to the semantics of the lambda calculus. In the resulting semantic model, there is a complete partial order on algorithms and standard operations such as composition, application, and currying are continuous; thus, one may define algorithms recursively and use the standard techniques of denotational semantics (least fixed points) to reason about recursive programs, even at this intensional level. This approach using categories is rather general, and I am exploring several other possible applications.

Semantic principles and insights should be used in the design of new programming languages, to avoid the development of cumbersome languages in which the programmer may have to labor to overcome the syntactic quirks and idiosyncrasies of the programming language in order to express his algorithm as a program. I am particularly interested in designing a language that embodies parallelism uniformly: it ought to be as easy to specify parallel expression evaluation as it is to specify parallel execution of statements, and it ought to be easy to put together the results of parallel activities. The choice of an appropriate set of primitives for such a language should be guided by proper attention to semantic foundations, and I am carrying out research on this topic.

My primary research interest is in formally verifying hardware designs. This interest grew out of earlier work in logic simulation and symbolic circuit analysis. Over the past few years, we have made great progress in formal verification, to the point where industrial hardware designers are making use of our ideas and tools. These tools promise to eliminate the uncertainty that lingers even after extensive evaluation by techniques such as simulation. The recent fiasco with the defective floating point divider in the Intel Pentium has placed formal verification at the forefront in digital hardware research. Industry is showing great interest in our work. Much more research is required in formalizing and generalizing our methodology, as well as in tool development.

During the course of developing hardware verification tools, I have become quite interested in symbolic representations and manipulation of discrete functions. Most tasks performed by a symbolic manipulator require solving NP-hard problems, and hence there are no known algorithms with good guaranteed performance. Instead, this work seeks heuristic methods that give satisfactory performance in practice. Our approach involves representing functions by directed acyclic graphs and applying graph algorithms to perform operations on functions. The results of our work in this area have spread beyond the original application. Our methods are now being applied to such areas as, temporal logic model checking, logic circuit optimization, automated theorem proving, and truth maintenance systems.

In recent years, we have developed techniques that generalize from Boolean functions, representing each bit of data as a separate function, to word-level functions, representing an entire data word as a function. This has lead to a hierarchical methodology for verifying arithmetic circuits such as multipliers and dividers. In fact, Intel has already started using these methods on their floating point units. I also maintain a longstanding interest in parallel computing, particularly in efficient mappings of application programs onto parallel machines. I am particularly interested in applications involve the manipulation of sparse and dynamically changing data structures. Such applications have historically performed poorly on parallel machines, but I believe that the right combination of architecture, programming model, and algorithms could lead to efficient solution techniques.

I am particularly interested in developing techniques to formally verify pipelined microprocessors. Each generation of microprocessor uses increasingly complex mechanisms to maximize performance, but these mechanisms should not affect program behavior. The challenge is to verify that the hardware implements the sequential semantics of the instruction set definition despite the fact that many instructions are executed in parallel. Since the complexity of a microprocessor is in its control logic, we can model the data operations as unintepreted functions operating on symbolic data. We have recently devised techniques that can verify simple, superscalar processors. However, major research breakthroughs are required to handle the complexity of advanced microprocessors.

My research focuses on computational design theory, methods, automation, and practice, emphasizing. the early stages of design. In particular I explore computational representation, generation and optimizing search of the design space. My premise is that computational tools must support a design process modeled by lateral exploration followed by concentrated investigation of one or more good designs. Based on this premise, much of my work has focused on stochastic optimization algorithms as search techniques, and various grammatical representations to model, generate, and move within the design space. The result is a merging between artificial intelligence and operations research, giving a unique approach to addressing the conceptual design problem.

Grammars are able to concisely model large design spaces. In a competitive society, once such a space is created, it must be searched not only to find a feasible solution, but an optimally directed one. Further, solutions obtained from any computer tool are only as good as the model that represented them, namely the set of objectives and constraints. Thus several equally good solutions are desired from which a designer can consider all objectives, including those not articulated in the model, to select the most preferred one. This motivates our shape annealing technique; shape annealing combines shape grammars and simulated annealing for the generation of optimal shape topologies. Based on the initial success of the technique in solving a knapsack-like problem, we have pursued simulated annealing with shape, string, and graph grammars, and probabilistic move sets, for the design of structures, machines, process plans and product layouts. This work bridges the theoretical aspects of form to function reasoning, the general question of topology generation and optimization, and the practical problem of component layout under a variety of constraints.

From the shape annealing/simulated annealing work we have begun to move in new directions, focusing on agent-based design in a changing environment where agents act based on a grammar representation and focusing on the creation of new stochastic optimization techniques with improved properties over simulated annealing. We are also exploring approaches to symbolic optimization for non-monotonic functions by incorporating robustness considerations into the activity analysis method for monotonic symbolic optimization. These efforts help the designer identify regions of the design space in the early stages of design where optimally directed design concepts lie, for further refinement during the later design stages.

My interests span several areas of Artificial Intelligence and Language Technologies. In particular, my current research is focused on machine learning in the context of language processing, including: tracking and detection of new topics and events, extracting key facts from text, corpus-based techniques for machine translation and translingual information retrieval, and content-based text summarization and text mining. I also work on planning, problem-solving, integrated rational-agent architectures, and large-scale data mining.

The following are my current projects; all represent collaborative efforts with graduate students, research staff, and/or faculty colleagues:

The TDT Project (Topic Detection and Tracking) [with Brown, Lafferty, and Yang]
Automated topic-tracking and new-topic detection for textual, audio and video news media, including developing new classifiers trainable with very few positive instances of events or topics to track. Also, unsupervised learning discovery of new topics at different levels of granularity from unlabeled textual data.

The MMR Project (Maximal Marginal Relevance) [with Goldstein]
Combining information novelty with query relevance in Information Retrieval to minimize redundancy. Also, extending MMR for on-demand query-relevant passage extraction document summarization, including producing unifying summaries of topically-related document clusters.

The HPKB Project (High-Performance Knowledge Bases) [with Mitchell]
Extracting knowledge from text (primarily from The Web) in order to build large-scale knowledge-bases on-demand. My part of the project focuses on extraction of entities and relations.

The DIPLOMAT Project [with Frederking, Brown and Hogan]
Multi-engine machine translation for rapid corpus-based development of MT systems among new language pairs. Diplomat includes speech-to-speech MT and well as text-MT. My focus is on generalizing example-based machine translation methods to produce reasonable MT with "minimal" training corpora.

The Multilingual IR Project [with Yang and Brown]
Multiple methods for bridging the language barrier between queries and document collections in IR, including example-based thesauri, translingual pseudo-relevance feedback, generalized vector spaces, and latent semantic indexing.

The KANT Project [with Nyberg and Mitamura]
High-accuracy knowledge-based machine translation in well-defined semantic domains. Unlike other my other text-based projects that are corpus-based and domain independent, KANT is a knowledge-intensive project to optimize performance given semantically delineated domains.

The PRODIGY Project [with Veloso]
PRODIGY is an integrated intelligent system for problem-solving, planning, analogical reasoning and learning that serves as a baseline platform from which to launch various focused machine learning projects. Whereas Veloso carries the bulk of this project, my primary interest is on learning new domains from examples and observation.

My interests are in multimedia interface development and evaluation, digital video libraries, and computer support for situated learning. My current work as part of the Informedia Project leverages from other CMU CS research in image processing, natural language processing, and speech recognition to enable full content search and retrieval from digital video, audio and text libraries.

Given thousands of hours of video and the need to find a relevant ten minute clip, the user should be able to locate the relevant clip without investing hours of viewing time. I contribute to the development of segmentation and abstraction strategies to meet this goal of more efficient information retrieval from multimedia libraries. I also conduct empirical studies evaluating the effects of multimedia abstractions such as filmstrip views and video skims.

The Informedia library system is currently in use at a local high school. I am interested in improving browsing within this system by supplementing the current query interface with information visualization techniques. I am also involved in a follow-up project which will extend the Informedia scope of accessing broadcast quality multimedia materials in a library setting to capturing, integrating and communicating experiences across people, time and space.

My interests span three areas: Programming Systems, Hardware, and Theory. I use the techniques and insights of theoretical computer science to solve problems in programming systems and hardware design that are of practical interest. I have a number of active research projects in these areas that I would be happy to discuss with students. Below are short descriptions of two research projects that I think are particularly exciting.

Hardware and Software Verification.
Logical errors in finite state concurrent systems like sequential circuits and communication protocols are an important problem for computer scientists. They can delay getting a new product on the market or cause the failure of some critical device that is already in use. The most widely used verification method is based on extensive simulation and can easily miss significant errors when the number possible states of the system is very large. Although there has been considerable research on the use of theorem provers, term rewriting systems and proof checkers for verification, these techniques are time consuming and often require a great deal of manual intervention. My group has developed an alternative approach called temporal logic model checking in which specifications are expressed in a propositional temporal logic and an efficient search procedure is used to determine whether or not the specifications are satisfied.

In the fifteen years that have passed since the original algorithm was published, the size of the systems that can be verified by this means has increased dramatically. By developing special programming languages for describing transition systems, it became possible to check examples with several thousand states. This was sufficient to find subtle errors in a number of nontrivial, although relatively small, circuit and protocols designs. Use of boolean decision diagrams (BDDs) led to a major increase in the size of the examples we could handle by this technique. Representing transition relations implicitly using BDDs made it possible to verify examples that would have required 10@^20 states with the original version algorithm. Refinements of the BDD-based techniques have pushed the state count up over 10^100 states. By combining model checking with abstraction, we have been able to check even larger examples. In one case, we were able to verify a pipelined ALU design with 64 registers, each 64 bits wide, and more than 10^1300 reachable states.

Analytica --- A Theorem Prover for Mathematica.
Analytica is an automatic theorem prover for theorems in elementary analysis. The prover runs in the Mathematica environment and is written in Mathematica language. The goal of the project is to use a powerful symbolic computation system to prove theorems that are beyond the scope of previous automatic theorem provers. The theorem prover is also able to guarantee the correctness of certain steps that are made by the symbolic computation system and therefore prevent common errors like division by a expression that could be zero.

Since we wanted to generate proofs that were as similar as possible to proofs constructed by humans, we use a variant of natural deduction to generate proofs. We have demonstrated the power of our theorem prover on several non-trivial examples including the basic properties of the stereographic projection and a series of three lemmas that lead to a proof of Weierstrass's example of a continuous nowhere differentiable function. Each of the lemmas in the latter example is proved completely automatically. In a related project that uses similar techniques, we have managed to prove all of the theorems and examples in Chapter 2 of Ramanujan's Collected Works completely automatically. We believe these examples provide convincing justification for combining powerful symbolic computation techniques with theorem provers.

I am interested in image understanding and computer vision systems, especially in the area of binocular stereo from passively-acquired imagery. I am currently working with Dave McKeown, Chris McGlone and Jefferey Shufelt at the Digital Mapping Laboratory in the investigation of the automated analysis of aerial imagery to support research in computer vision for digital mapping and the creation of databases for virtual world simulation.

Binocular Stereo.
Humans are able to surmise depth in 2-D "monocular" images and to perceive it through the stereoscopic fusion of a pair of images. The process used by the human visual system to achieve this, however, is not well understood. How, then can we produce autonomous systems which are able to extract depth information about, and interact with, their environments? One way is to attempt to emulate some of those processes, which seem to be present in the human visual system, and learn what does and does not work. This approach allows us to attempt automatic visual recognition of objects, and, perhaps in some cases, to gain insight about the operation of the human visual system. The perception of depth from a stereo pair provides both a qualitative and a quantitative measure in depth determination that is not available from a monocular view and produces the ability to detect objects which are difficult to distinguish from the background due to similar image intensities or textures. For my theses work at USC, I developed a Stereo Vision System (SVS) in which I showed methods to integrate primitives derived from area-based and feature-based stereo matching algorithms. I have continued this work at CMU particularly with respect to improvements in stereo matching accuracy and refinement.

Data Fusion.
Stereo data alone is not sufficient to solve the cartographic feature extraction problem. To achieve that goal, we will need to gather together various partial scene abstractions formed by differing methods: stereo, monocular, multi-spectral and others. Relating image derived measurements and features into a consistent and rigorous object-space representation is an important first step in automated fusion. As an example, four aerial images that cover a common area allow twelve different sets of pairwise stereo data to be produced, along with four sets of monocular estimates of building hypotheses. The key issue is finding common robust structure from this noisy and diverse set of information.

Evaluation.
It is not enough to simply point at a set of results and saying Look! I am doing a great job. It is necessary to determine quantitatively, as well as qualitatively, how well an approach is working in order to justify claims of an improvement to that approach. At the same time it is difficult and/or expensive to obtain or generate a complete ground-truth model of a test scene. Therefore I have been working on ways to generate quantitative results with respect to a set of goals. For instance, if the goal is to extract all of the buildings in the scene, then only the buildings need to be explicitly modeled in the ground reference data.

URL: http://www.cs.cmu.edu/~sdc

My interests are in the application of artificial intelligence to education, in particular, the use of cognitive models in computer-based tutoring environments. Our approach is to build tutoring programs around rule-based models of how people perform skills, such as programming. Such a model allows the tutoring program to solve practice exercises along with the student, providing help as needed. My research has focused recently on estimating students' mastery of the knowledge represented in the cognitive model. By integrating learning and performance assumptions with the cognitive rules, we attempt to predict students' test performance, shape practice appropriately and improve the model. I am also interested in related issues in the design of computer-based practice environments, for example the content and timing of help messages and their impact on students' performance.

My research interests are in the design and implementation of advanced programming languages and in applying programming language technology to improve the development, maintenance, and performance of software systems. I am particularly interested in the application of types to the structure and implementation of programming languages.

A current focus of my research is on typed compilation. Compilation using types offers some compelling benefits over conventional, untyped compilation. For example, preserving types through compilation provides additional information that may be used to optimize programs. Type-based optimizations are particularly useful for compiling advanced programming languages, such as ML. Advanced programming languages, provide many features such as first-class functions, automatic memory management, polymorphism and abstraction, that are valuable to programmers but are also hard to implement efficiently. Modern implementation strategies, including type-based optimization, allow advanced languages to be implemented roughly as efficiently as less advanced ones. For instance, the TIL (Typed Intermediate Languages) compiler for ML, one project I work on, uses type-based optimizations to obtain a 3-fold speedup over other ML compilers.

An even more important benefit of typed compilation lies in its application to mobile code security. With the increasing importance of the widely distributed computing (particularly with the World Wide Web), it has become impractical for agents to limit their computing interactions to other agents whom they trust. This leads directly to a need for mechanisms whereby an agent can safely execute untrusted and potentially malicious programs. However, it is important that such mechanisms not substantially sacrifice performance, as is the case with run-time checking mechanisms. Typed compilation gives us a tool for producing certified executables, which can be statically determined to be safe before execution. This certification strategy works by attaching types to mobile code; that code is then type-checked and is run only if type-checking succeeds. If it does succeed, the formal semantics of the type system guarantees that code is safe.

For this to work requires a type system suitable for low-level code, in particular for machine binaries. However, most research into type systems has focused on high-level languages, in part because low-level languages can be uncooperative to type-theoretic analysis. Recently, I and others have been studying typed assembly languages, machine-level programming languages with sound type systems. In a typed assembly language, one can program with direct access to machine resources without sacrificing the safety guarantees provided by typed high-level languages. In practice, however, typed assembly code is typically produces by a typed compiler from high-level source code. My ongoing research into typed assembly languages focuses on enhancing their type systems both to make them more flexible and to strengthen the safety properties they can guarantee.

My work is focused on various aspects of computer music, a field which poses many challenges for computer science. I also direct the Just-In-Time Lecture Consortium, which offers a new technology for low-cost, computer-based training and education.

A central problem in computer music is expressive control, that is, the detailed control of timing, gesture, nuance, and tone quality that is essential to music. This problem has many facets, resulting in a variety of research directions. The Computer Music Project has developed new languages, development tools for real-time systems, synthesis techniques, and music understanding systems. This research is more than intrinsically interesting. It can shed light on related problems in real-time systems, multimedia, human-computer interaction, and artificial intelligence. Moreover, new possibilities of control and interaction in music are changing the very nature of music composition, performance, and aesthetics.

One research example is the the development of new languages for expressing temporal behavior. One of these is Nyquist, a language that provides a single abstraction mechanism for the seemingly different notions of ``note,'' ``instrument,'' and ``musical score.'' Nyquist gives composers an elegant, uniform notation that spans the range from low-level digital signal processing to high-level music composition. At present, Nyquist does not generate sound in real-time, but as processors increase in speed, software for sound synthesis will replace special-purpose hardware synthesizers. Nyquist already provides one of the fastest sound synthesis implementations, and a future version will support real-time synthesis.

Expressive control of musical tones is another topic of research. A violin is expressive because there are many parameters under continuous control by the player, including bow pressure, finger and bow positions, and bow velocity. These give rise to variations in the resulting sound. My colleagues and I have developed a new synthesis technique, spectral interpolation, which allows us to synthesize tones with interesting variations in spectra. Spectral interpolation has been used to accurately synthesize a variety of instruments. In the future, we will use this technique to give composers and performers greater intuitive control over synthesized sound.

Real-time performance systems present interesting problems. I have developed several systems for real-time music understanding that ``listen'' to a live performance and derive some abstract information regarding rhythm, tempo, harmony, etc. The degree of understanding is usually demonstrated by having the system participate in the performance. One example is Computer Accompaniment, in which the computer follows a performance in a score and plays an accompaniment in synchronization with the performer. My computer accompaniment technology appeared in a commercial product in 1994. Another example is a system that listens to an improvisor playing 12-bar blues and plays the part of a rhythm section. Systems that perform both of these tasks have been built here, but this is only the beginning of what is possible. Current work includes more sophisticated systems for listening to improvisations, ensembles, and vocalists.

Education is another interest. Our country spends more for education than for health care, and as with health care, education costs are growing faster than the inflation rate. Computer-based tutoring systems have much to offer, but development costs and lack of expertise have made it difficult to produce good tutoring systems. Work on automating instructional design principles to lower the cost of intelligent tutoring systems led to an even simpler approach, ``Just-In-Time Lectures,'' in which presentations are captured using digital video, synchronized slides, a table-of-contents, and links to the Web. Just-In-Time Lectures have been used to deliver entire courses and by large corporations for training.

I am interested in making robots act purposefully and successfully in a world in which most everything is uncertain. Sensory information is inaccurate or noisy, actions seldom have a precise effect, and objects in the world are often in the wrong location or orientation. Despite such obstacles to purposeful action, there are many tasks that can be accomplished successfully. Humans, animals, and some machines are proof. Providing robots with the ability to operate autonomously and purposefully requires an understanding of how different tasks may be accomplished by different repertoires of actions. Grasping, hitting, and dropping are some actions that are useful in a robot's repertoire. More exotic actions include shaking, twirling, and other actions that randomize an object's state. My current work focuses on two-palm manipulation, in which two arms cooperate to manipulate objects dynamically, that is, without the need for full kinematic constraint. My work is motivated by several desires. First, I would like to program robots more easily than is currently possible. Second, I would like to understand the scope and limitations of autonomous systems, whether biological or artificial. Third, I would like to reduce the complexity of design and planning by codifying the design parameters required to achieve a given level of automation. An underlying goal of my research is to understand the relationship between sensing, action, and prediction. In the past, I have explored various extreme points in this space. With Matt Mason I explored sensorless strategies, for my thesis work I looked at randomized strategies, and most recently I investigated fast-action minimal-sensing strategies. My research draws on tools from geometry, mechanics, planning, and probability.

AI and Machine Learning:
For most of my career I have been exploring the idea that recognition and other essential operations of human intelligence may depend on the use of massively parallel computation rather than clever algorithms and data structures. Instead of using a single processor to look at data sitting passively in memory, we need some kind of active memory in which all of the available knowledge participates in producing a response. My first experiments in this area led to the NETL system, essentially a semantic network with a very simple computing element permanently assigned to each node and link in the network. In recent years, I have become interested in more neuron-like architectures that represent knowledge in a distributed form and that can learn new behaviors from examples.

My students and I have developed several improved learning algorithms for neural networks, including Quickprop, Cascade-Correlation, and several variations on these. Cascade-correlation is very fast, scales up well, and it constructs a network of the appropriate size and shape as it works on a problem. These algorithms are being used in a large number of application projects worldwide.

Most current learning algorithms employ "supervised" learning: the system is trained by showing it a collection of input/output pairs illustrating the desired behavior. However, in many domains, such labeled training data is scarce. I am currently interested in developing better algorithms for "unsupervised" and "partially unsupervised" learning, in which the learning algorithm must discover interesting and useful structure in an unlabeled stream of experiences.

Tools for Software Development.
Most of software engineering is concerned with developing programs that correctly implement a pre-existing specification. I am more interested in tools for "evolutionary" or "incremental" software development, in which the requirements may change over time, and in which the developer doesn't know exactly what he wants until after the software is running. Languages of the Lisp family always have been excellent vehicles for this kind of programming.

I was one of the principal designers of the Common Lisp language, and my CMU Common Lisp group developed a widely used, public-domain implementation of Common Lisp with a very powerful compiler. Later, my "Gwydion" research group worked on the Dylan language and on Sheets, an advanced software development environment for Java. I do not currently have any active research projects in this area, but I still am very much interested in software tools of this kind, and in the future of programming in general.

Just Research.
I am currently on leave of absence from the CMU faculty so that I can head Just Research, a new computer science research center located a few blocks from CMU. This laboratory was established by Justsystem, a large software company based in Tokushima, Japan. Just Research conducts research in many areas, including information retrieval, natural language processing, image processing, and machine learning applied to all of the above. The lab maintains close ties to the CMU community. Many of our Ph.D.-level researchers have adjunct faculty appointments in SCS, and we have employed a number of CMU students in part-time and summer positions.

The first project examines fast methods for approximate matching in multimedia databases. Typical queries are as follows: "in a collection of product photographs, find pro- ducts that look like tennis shoes"; "in a collection of med- ical X-rays, find ones that look like the X-ray of the current patient, and list the corresponding diagnoses". The main idea behind our approach is to extract n features from the objects of interest (typically, with the help of a domain expert), thus mapping each object into a point in n-dimensional feature space. Subsequently, we can use state-of-the-art database techniques (like the 'R-trees') to store and retrieve these n-dimensional points. The philo- sophy of our approach is to provide a the vast majority of irrelevant objects. Allowing some 'false alarms' is accept- able, because they can be easily discarded by a elaborate test, or even by the user. We have already successful sets of features for 2-d color images, 2-d shapes, and 1-d time series (such as stock-price movements). Depending on the domain, we are experimenting with modern signal processing techniques, such as the discrete wavelet transform for sound and images, hidden Markov chains for digitized voice, the discrete cosine transform for stock-price time series.

The second project focuses on data mining. The goal is to discover correlations ('rules') in a collection of records. For example, in a set of patient records with demographic characteristics, symp- toms and diagnoses, we would like to find all the 'interesting' rules (eg., 'patients >50 years old with cholesterol >300 have 10% probability of heart attack'). We are studying traditional clustering methods as well as statistical methods like the 'Singular Value Decomposition' (SVD), to do cluster analysis and rule discovery.

The last project examines algorithms and architectures for fast execution of expensive database operations. We are working on Active Disks for data mining, on striping and placement algorithms for video servers, and on buffering algorithms for database operations.

My main research interests are the theory, design and implementation of high performance information systems. The general theme of my work is to understand and exploit the interplay of applications and new technologies. At various times this work has involved designing parallel algorithms, parallel architectures, custom chips, and specialized compilers. My current activity centers on the architecture and control of high speed networks as infrastructure for communication and for parallel computation. Colleagues and I have recently completed the Credit Net project, which has designed and is in the deployed a 622 megabit-per-second ATM local area network. I am currently working with Peter Steenkiste, Hui Zhang and our students and staff on the Darwin project, which involves the design of algorithms to allocate and control resources in the network, and of interfaces and software to support applications in parallel computing and multiparty, multimedia communication. The overall goal of Darwin is to develop the infrastructure need to provide dynamic electronic service creation and deployment in future networks.

I have broad research interests in computer systems, including operating systems, networking, storage systems, computer architecture, performance evaluation, and distributed systems. I am particularly interested in developing new ways of structuring computer systems (hardware and/or software) to address technology changes and enable new applications. One place where I see an opportunity for large, fundamental changes is in the ongoing shift in importance from conventional computing to I/O and data movement -- we need computer system designs that treat I/O components as first-class entities, allowing them to actively and adaptively cooperate in the completion of useful work.

My students and I are currently pursuing several topics of research:

* design and implementation of extensible I/O software.
* design and implementation of application-level networking.
* construction of high-performance network servers
* implementation and use of application-controlled storage management
* improved general-purpose file system support for small file I/O

My field of interest is software engineering, and specifically the areas of applied formal methods, software architectures, and software development environments. The common thread that links these areas is the problem of controlling the complexity of large software systems by providing a scientific basis for software design.

Applied Formal Methods.
The traditional use of formal (or mathematically-based) methods has been to solve the problem of refinement: given a formal specification of a system, how does one construct an implementation that is correct with respect to that specification. In contrast, my interest in formal methods is in dealing with the inverse problem of abstraction: given a family of existing systems, how does one construct a formal model that characterizes the important commonalities in these systems. When used in this way, formal methods become a tool for extracting reusable software architectures, for clarifying system design, for simplifying the way we think about a class of system, and for building a framework for reuse. Among the important research issues are those of methodology (How should we use formal notations in practice to arrive at system abstractions?), language (What notations, type systems, parameterization mechanisms, etc. are best suited to this use of formal methods?), and reusability (What properties of a formal model best support reusability, evolution, and adaptation?).

Software Architecture.
Successful design of software architecture has always been a major factor in determining the success of a software system. But until recently architectural design has been largely based on ad hoc choice, informal experience, and local expertise. The goal of this research is make this knowledge precise, codified, and available to engineers as a matter of routine engineering. An example of where this has been successfully accomplished is compiler construction: what once took years to develop is now done routinely by undergraduates in a semester course. This is because compiler development is based on a well-defined, formalized software architecture, which defines a set of abstractions that give the software engineer a conceptual grasp of the problem, leads to a focused set of tasks that must be performed to specialize the architecture for a specific compiler (lexical analysis, parsing, flow analysis, etc.), and enables automated support for the compiler construction tools (parser generators, attribute evaluators, etc).

The goal of this research is to demonstrate that similar architectures can be obtained for other classes of software. In particular, the design abstractions obtained through the application of formal methods to the design process (mentioned above) are natural candidates for architectures.

Software Development Environments.
Given a well-defined architecture, it is natural to attempt to support its use with development tools and environments. The ABLE project is currently building a system, called AESOP, for generating environments that support specific classes of architectures -- or architectural styles. Given a description of an architectural style, AESOP produces an open environment for creating software designs in that style, reasoning about properties of those systems, integrating external tools, and graphically visualizing architectural designs. The ABLE project also is developing transformational techniques for specializing general-purpose environments: using these techniques we are able to adapt existing environments so that they support the creation of application-specific programs.

I am interested in computer systems architectures, in particular, memory systems architectures employing prefetching, parallel and video file systems, redundant arrays of disks, high bandwidth networks and workstations and multicomputer operating systems. Towards these goals, I lead the Parallel Data Laboratory (PDL) in the following projects.

Currently, most of our effort is focussed on the Network-Attached Secure Disks (NASD) project. The central goal of NASD is to establish an intelligent storage interface and to develop the distributed and parallel file system technology to exploit it. This new interface features direct communication between clients (possibly cluster servers) and storage devices or subsystems. Direct communication enables cost-effective scalable striped storage, file server offloading and reduced messaging, storage processing and bandwidth proportional to capacity, device-enforced security, and extensible storage intelligence available for application needs (Active Disks). The Lab develops full-function prototype systems and evaluates these against real applications. For example, in the fall of 1998 we are building a 1.25 TB array of 100 NASD (or Active Disk) nodes to be tested with data mining applications (such as association discovery from consumer transactions) and multimedia applications (such as medical image processing and digital library retrieval and viewing). In the spring of 1998, this project branched out to examine the use of intelligent network devices (Active Networks) for storage functions such as caching, redundancy or load balancing. We also participate in a National Storage Industry Consortium (NSIC) industry working group devoted to developing the appropriate interfaces for network-attached storage devices.

Our informed prefetching and caching research (TIP) proactively tailors file system resource management to the needs of I/O-intensive applications. With applications disclosing access patterns, TIP increases I/O concurrency to exploit the full parallelism of disk arrays, fetching further ahead on congested disks as needed. Our implementation is based on an extensible cost-benefit resource allocator and encapsulates within each module bidding for resources all policy related to that module's allocation strategy. Hints, the key to TIP's dramatic reduction in elapsed time (approximately linear in the number of disks for many I/O-intensive applications), can be automatically generated by runtime and compilation means. Both techniques are currently being explored; speculative pre-execution of runtime code stalled waiting for I/O generates probable future reads and compile time loop unrolling predicts a superset of future virtual memory page-ins.

Our Scalable I/O collaboration (SIO) , with Caltech, Rice, Princeton, Arizona, Washington, Argonne, Illinios and others, is focussed on defining and demonstrating extensions to the traditional UNIX file system programmer's interface to portably support high-performance, parallel applications. PDL researchers are implementing the SIO parallel file system API in a cluster of workstations environment employing network-attached secure disks. Designed to operate outside of client operating system kernels while providing dynamically configurable failure tolerance, our parallel file system will fully exploit the features of NASD devices.

The Lab's original and most well-documented project, redundant disk arrays (RAID) , is largely complete. In its heyday we worked on RAID architectures for improved performance in the presence of failures and architectures for reducing the failure-free penalty for maintaining redundant information. More recently, the RAID project developed and published a rapid prototyping framework for RAID systems. This executable framework, RAIDframe, enables us to treat RAID architectures as simple graphical programs amenable to automatic error recovery and rapid modification. RAIDframe efforts persist as local and remote colleagues port and extend RAIDframe.

The Lab is equipped with a few hundred disk drives in various arrays and standalone configurations. About 50 Digital Equipment Alpha workstations with 133 to 500 MHz processors form the basis of the Lab's computing. To these we have recently added 64 300 MHz Pentium II workstations. Networking is provided with a 52-port OC3 ATM switch, a collection of 24-port 100Mbps Ethernet switches and am 8-port 1.28 Gbps Myrinet switch.

The Lab is advised and supported by a consortium of companies including Hewlett-Packard, Intel, Compaq, 3Com, Seagate, Quantum, Clariion, Symbios Logic, StorageTek and Wind River. Representatives of these sponsors visit CMU for at least three days per year to participate in the Lab's annual retreat and workshop, typically in the late fall at an off-campus conference facility nearby CMU.

My research area is computer architecture and compilers. Currently my interest is focused on novel ways to use the hundreds of millions to billions of transistors that will be available to processor designers in the near future. In particular, I am interested in how user programs written in high-level languages can be compiled directly into hardware, yielding order of magnitude speedups.

The key architectural feature that enables huge speedups is the reconfigurable fabric (similar in concept to today's FPGAs), which can be configured to any hardware circuit. The reconfigurable fabric is then integrated with a simple super-scalar processor core, resulting in a high-powered general-purpose processor. The compiler for such a system partitions a program into sections that are executed either on the core or on the reconfigurable fabric. It synthesizes communication and synchronization code and also creates the hardware configurations.

The research is proceeding on four fronts: (1) the development of techniques for compiling high-level languages to reconfigurable fabrics, (2) the design of Tiger, a TIghtly coupled General-purpose processor with a Reconfigurable fabric, (3) The design and implementation of PipeRench, a compiler-friendly computation-based reconfigurable fabric, and (4) the creation of a benchmark suite workload 2000.

The compilation technology we are developing allows users to program Tiger processors in high-level languages without requiring them to understand the actual implementation details of the reconfigurable fabric or the processor/fabric interface. We have already completed our first version of a compiler that creates configurations for fabrics from a text-based dataflow intermediate language (DIL). We are now investigating techniques to turn C programs into executables for Tiger machines. Among other things, we are investigating how to automatically partition a C program between the general-purpose core and the reconfigurable fabric, how to create hardware pipelines from C code, how to retime circuits to reduce register pressure, and how to speed up place-and-route without compromising efficiency.

As part of this research effort I am collaborating on the design of a new reconfigurable fabric called PipeRench. PipeRench is the first FPGA-like device that virtualizes the physical array allowing designs larger than the physical device to run efficiently. Furthermore, unlike previous FPGAs, PipeRench is oriented toward the implementation of data paths instead of random logic. We expect to fabricate PipeRench in late 1998. Currently, using our DIL compiler, we have implemented many kernels on PipeRench and have, at least initially, validated our assumption that PipeRench's compiler-friendly design enables our goal of compiling high-level languages automatically to the fabric.

My other areas of interest are parallel object-oriented languages and fine-grained parallelism.

Areas: (I have included all areas, including the ones I am currently listed under in this list. Also note that reconfigurable computing new areas)

My research interests center on how to build (design, program, implement) systems. "Systems" in this context refers to a software system executing on some hardware platform. One of the challenges in system design is to develop good abstractions and tools (both for the software and hardware side) to simplify the task of building the system. Therefore, my research includes the building of tools (often compilers) to support system development.

I'm involved in two projects: one (Fx) focusses on the mapping of programs onto parallel and distributed systems; the other (cmcc -- for CMU's C Compiler) investigates the construction of an optimizing C compiler.

Together with other researchers (both inside the School of Computer Science and in other departments), I work on developing applications, usage models, abstractions, and programming tools for scalable computers. This class of platforms includes networked workstation clusters (or "networks of workstations", although these networks in practice include a lot more than workstations) as well as parallel systems. The core of our effort is the Fx compiler, which maps application programs written in a dialect of High Performance Fortran (HPF) onto a variety of systems. The Fx compiler system has been (re)targeted at the Cray T3D, the Intel Paragon and iWarp, and the Nectar Gigabit Testbed. Efforts to target new ATM-based networks like CreditNet are under way. The Fx compiler provides a unique framework to explore issues in parallel computing, ranging from applications to computer architecture. For example our input language allows the user to pass hints about the alignment and distribution of data objects (i.e., how the elements of an array are to be placed relative to other arrays and relative to other elements of the same array). These directives guide the compiler when mapping applications with access patterns that are too hard for a compiler to analyze.

HPF and its dialects form one class of languages that can be used for the programming, and HPF has demonstrated some success for the programming of "regular" problems. (A problem is called "regular" when the distribution of data can be described with a few parameters, like the block size and stride.) However, there exist a number of applications (often referred to a "irregular") that are beyond the capabilities of current compilers for HPF. That it, is is either hard or impossible to efficiently map these code onto parallel or distributed systems. The Archimedes project attempts to support such applications, and the Archimedes and Fx compilers share the communication back-end. To address the needs of these applications, however, it is necessary to consider all aspects of the execution environment, including the runtime system. Therefore, one of our current projects investigates the interface between compilers, applications, and the memory and synchronization models provided by the runtime system.

The cmcc compiler is a compact, optimizing C compiler, implemented in C++. This compiler serves as a testbed for research into compiler construction; current topics of interest include code generation, instruction scheduling, register allocation, debugging of optimized code, as well as code optimization to reduce code space and program execution time. In addition, cmcc is a platform to explore code reuse and software construction. A compiler offers ample opportunities for code reuse, and the compiler includes a number of (application) frameworks, including frameworks for global data flow analysis, local instruction scheduling, and register allocation. These frameworks simplify the program structure (and are one of the reasons for cmcc's compactness). They also allow a fair comparison between different approaches (e.g., to register allocation), since different register allocators share the base tools (like building the interference graphs). Finally, a building a framework indicates that we are able to unify a number of so far disparate approaches and thereby expresses our improved understanding of the problem domain.

In summary, my research area includes the programming aspects of current and future systems. This research area can be loosely described by the overlap of compilers, operating systems, and computer architecture.

I am interested in the performance analysis and design of computer systems, particularly distributed systems. I work on finding analytical models which capture the important characteristics of a computer system and allow me to redesign the system to improve its performance.

I believe that many fundamental conventional wisdoms on which we base system designs are not well understood and sometimes false, leading to inferior designs. My research challenges these age-old beliefs. Here are just a few examples:

• Thousands of "load balancing" heuristics do exactly that -- they aim to balance the load among the existing hosts. But who said that's neccessarily a good thing?

• Migration policies for networks of workstations and distributed servers direct jobs to the host with least load. That seems good from the job's perspective, but is it best for the system overall?

• Given a choice between a single machine with power p , or n identical machines each with power p/n, which would you choose?

• Migrating active jobs is generally considered too expensive. Killing jobs midway through execution and restarting them from scratch later is even worse! Says who?

• Ever notice that the "proven best" scheduling policies like SRPT (shortest-remaining-processing-time-first) are never used in practice? There's a fear that the big jobs will starve. Is this true?

Application areas I currently work in include: Web servers, distributed Web servers, distributed supercomputing servers, networks of workstations, and communication networks.

My principal research interest is in the application of type theory to building and reasoning about programs. The focus of my work is the Fox Project, which I lead with Peter Lee and Frank Pfenning, and the PSciCo Project, which I lead with Guy Blelloch, Peter Lee, and Gary Miller. The Fox Project is concerned with the design, implementation, and application of advanced programming languages. The fundamental thesis of the project is that type theory is critically important for the implementation of robust, maintainable, and efficient software systems. The PSciCo Project is concerned with the application of advanced programming languages to the implementation of sophisticated algorithms for scientific computing.

Type theory provides a unifying conceptual framework for programming language design, specification, and implementation. As a design tool type theory provides a clean framework for organizing programming language constructs. A type consists of a collection of values together with a collection of primitive operations on those values. Familiar notions such as trees or lists may be viewed as values of recursive type; the operations permit traversal of these structures. Procedures may be viewed as values of function type, with operations to create procedures and to apply them to arguments. Abstract data structures such as dictionaries may be seen as values of existential type, with operations to create a data structure and to use a data structure without revealing its implementation details. In fact a programming language may be defined by giving an interpretation of its constructs in type theory. For example, modularity mechanisms might be rendered as uses of existential type, together with a notion of subtyping to admit code reuse and generic operations. A significant advantage of the type-theoretic viewpoint is that it has direct implications for compiler writers. My work on the TIL compiler demonstrates the importance of typed intermediate languages for building compilers that generate efficient machine code. The stages of the TIL compiler are defined as type-directed translations that transform both a program and its type. This allows the compiler to take advantage of type information at compile-, link-, and run-time. The TIL ML compiler generates code that is three times faster and uses half the space of other competing compilers.

Types are also a useful tool for prototyping programming languages and proving properties of programs. My work with Frank Pfenning on the LF logical framework is concerned with the development of a "logic workbench" that allows one to implement formal systems such as type systems for programming languages or logics for reasoning about programs. The LF language is a simple, yet expressive, type theory in which one may describe the abstract syntax and deductive apparatus of a formal logical system. The Elf programming language may be used to build proof checkers and theorem provers for a logic specified in LF. In a recent case study Elf was used to define a small assembly language for network packet filters and to define a logic for stating and proving memory invariants of programs written in this language. The program, together with the LF representation of its proof, form a "self-certified" binary that may be safely installed in an operating system kernel without fear of violating the kernel's memory. Elf has also been used to prototype experimental languages, and to study the properties of logical systems such as Girard's linear logic.

URL: http://www.cs.cmu.edu/~rwh
Fox Project: http://foxnet.cs.cmu.edu
Logical Frameworks: http://www.cs.cmu.edu/afs/cs/user/fp/www/lfs.html

My research interests revolve around the integration of text, image video and audio analysis. In the Informedia Project we have built the News-on-Demand application, which is an instantiation of the Informedia Digital Video Library idea, based completely on automatic methods for processing television and radio news. Through the combination of the strengths of speech recognition, natural language processing, information retrieval and interface design, the system is able to overcome some of the shortfalls inherent in each of the component technologies.

My goal is to utilize large corpora of "found data", that is data that is already available through the Internet or other readily accessible open sources, to improve speech and natural language processing by exploiting advantages across different modalities. It has become clear in recent years that large volumes of text, image, video and audio can be easily stored and made available for research and applications. However, most of these text, image, video and audio sources were not produced with computer processing in mind. My intention is to design and build intelligent, understanding programs that help process data from these sources and make the data useful for other applications. This data can be used to improve speech recognition, image understanding, natural language processing, machine learning as well as information retrieval. The challenge is to find the right data, process it into suitable form for training, learning or re-use and build mechanisms that can successfully utilize this data.

Speech and multimedia technology is about to make a major impact on our daily interaction with computers. What is needed at this point are clear demonstrations of the advantages of integrated speech and multimedia interfaces.

My interests are centered in computer graphics but include related fields such as image processing, computer vision, and scientific computing. I enjoy working with a variety of issues, including mathematical, computational, user-interface, and artistic concerns. A broad summary of my research goals is: the development of algorithms and software tools to facilitate the creation and manipulation of pictures and other multidimensional data. Some applications which motivate much of my work are: computer animation for movies, computer aided design, and scientific visualization for education, science, and engineering. Some of my recent research is in the area of image synthesis, also known as rendering. Realistic image synthesis, the generation of images of mathematically-described three-dimensional scenes that are indistinguishable from reality, is a very challenging goal.

One of the fundamental computational challenges of realistic image synthesis is the simulation of global illumination, the interreflection of light in a 3-D scene. I am currently investigating radiosity methods for doing such simulations, in which a surface is subdivided using a mesh and a large system of equations is solved to compute the brightness of each triangle in the mesh. Our current research involves better methods for meshing that take occlusion into account, wavelet techniques for solving the equations efficiently, and fast methods for generating shadows. Future work will generalize these methods to work well on curved and shiny surfaces.

Another area of my research is surface modeling: their interactive design, their representation, and their efficient display. Prof. Andy Witkin and I developed a particle-based technique that allows very general, interactive design of implicit surfaces. Our repelling particle technique has also been generalized to create a flexible 2-D mesh generator useful for surface meshing in computer graphics and other applications in scientific computing. To speed up the display of complex geometric models, I am currently developing new multiresolution modeling techniques that represent objects at multiple levels of detail. When an object is viewed from up close, a detailed model is drawn; but when viewed from the distance, a coarse approximation is drawn. How do we make multiresolution models quick, accurate, and seamless? Multiresolution techniques have applications in flight simulators, video games, computer aided design, geographic information systems, and cartography. A graduate student and I have recently developed some fast algorithms for simplifying terrain data and more general 3-D objects that generate quite accurate approximations.

This is a summary of my current research, but my interests are not limited to these topics.

My research interests lie in the area of user interface software and technology. I am interested in creating tools and software infrastructure which make it possible to produce high quality user interfaces quickly and economically. This work includes the creation of innovative new interaction techniques for 2D and 3D interaction, development of advanced user interface toolkits, work in the use of constraint systems for user interface implementation, and higher level user interface specification tools.

I am also interested in using new media (such and audio and video) and new interaction modalities (such as pen-based interaction) to create new ways in which people can interact with computers. In this area I am currently working on new techniques for hybrid paper electronic interfaces. This work attempts to expand the usefulness of physical paper as an interaction medium by adding electronic capabilities to it such as searching, hyperlinking, and dynamic content. Finally, I am also working on new techniques for using audio and video communications to support awareness in distributed work groups.

My primary research interest is in creating engineering models of human performance to be used in the design of human-computer interaction. Such models seek to optimize several criteria that distinguish them from traditional cognitive models: the ability to make zero-parameter predictions, the ability to be taught to and be used by computer systems designers, coverage of total tasks, and approximation.

Engineering models must be able to make predictions in the absence of a working, or even simulated, system because the predictions are needed early in the design process, where they can be used to shape the specifications of the system. Any parameters used to make the predictions must be set during the development of the modeling technique, not when the technique is being applied to a new situation. This does not mean that parameters have to be fixed constants for every situation, only that they must be determinable a priori. Tables of parameters covering a wide range of tasks can be used to estimate values for a new situation and these are created from research done in the development of the modeling technique. Such graphs or tables build in basic psychology so that computer designers can use the models effectively.

The target users of HCI engineering models are computer system designers, not usually trained psychologists or human factors experts. Thus, the designer cannot be counted on to bring psychological expertise to the task and the basic psychology must be built into the models. Tables of parameter estimates have already been given as an example of building in this expertise. In addition, the procedures must be clearly defined and representative examples must be presented to allow the techniques to be taught. This does not mean that the procedures have to be as structured as recipes in a cook book. However, there must be guidelines and rules about what to do in many representative situations so that a style of analysis can be developed that leads to good predictions.

The activities people perform when interacting with computers are quite varied. These include reading, searching for information on the CRT screen, processing information relevant to task goals, forming plans, typing, pointing, learning, making and recovering from errors, and a myriad of other activities that overlap and interact with each other. Engineering models must do more than focus on each activity in isolation, they must allow prediction of the overlap and interaction between activities. Coverage of total tasks is the most difficult criteria for engineering models to satisfy.

Engineering models of human performance must produce useful predictions at different levels of approximation. Some design situations require gross predictions of performance, e.g., selecting a word processor based on how long it will take to complete some benchmark tasks. Other design situations require much finer grained analyses, e.g. predicting where a combat pilot's visual attention is directed at every moment during a tactical maneuver so the effects of a new visual display can be assessed. Engineering models meet different design needs by providing approximations to the mechanisms that produce behavior. Models of mechanisms and processes allow operations to be grouped, averaged over, or ignored, as appropriate to the design situation.

One engineering model of human performance has been developed over the last decade, GOMS, which forms the basis for my continuing work. GOMS stands for Goals, Operators, Methods, and Selection rules, which are the components of the user's knowledge and task requirements necessary to predict user performance. GOMS has received a decade of academic interest and laboratory research, and has been demonstrated to be a valuable real-world evaluation and design tool for task-specific workstations (e.g., workstations for telephone operators). A current GOMS project models the behavior of architects using complex CAD systems to increase their productivity. I am currently working within the Soar cognitive architecture to extend GOMS and produce more complete engineering models. The current focus of this work is in modeling rapid interaction with the environment. One current project investigates how expert programmers interleave planning and coding and use the information displayed by their programming environment to structure their work. Another project investigates the mechanisms for problem solving and learning in the externally-driven, fast-paced domain of video games. A third models learning in an air-traffic controller task. My secondary research interest is in understanding the usefulness and usability of predictive HCI assessment techniques other than engineering models. I have an ongoing project to apply other techniques (e.g., Heuristic Evaluation, Cognitive Walkthrough, User Action Notation, Claims Analysis) to the design of complex systems (e.g., programming environments, multi-media authoring tools) to determine what types of usability problems these techniques can identify, how much effort it is to learn and use them, to what types of systems and at what stage of development they can best be applied, and how their results compare to empirical methods.

My research interests lie in the areas of network protocols, operating systems, and distributed systems, particularly in the interactions between these areas. Most of my current research is in the area of adaptive protocols for wireless and mobile networking, and I am currently leading the Monarch Project at CMU in this area.

Wireless networks have fundamentally different properties than typical wired networks, including higher error rates, lower bandwidths, nonuniform transmission characteristics, increased usage costs, increased susceptibility to interference and eavesdropping, and higher variability of performance. Similarly, mobile hosts behave differently and have fundamentally different limitations than stationary hosts. For example, mobile hosts generally operate on limited battery power and may move and change their point of connection to the network at any time. These differences in network and host properties produce many new challenges for network protocols.

Our research in the Monarch Project is addressing these challenges through the development of new networking protocols and protocol interfaces to allow a level of wireless and mobile networking support substantially beyond what is possible with traditional protocols. Our goal is to create an integrated set of protocols that allow mobile computers, and the applications running on them and communicating with them, to seamlessly make the most efficient use of the best available network connections at any time. For example, each time a mobile host changes its location, the routing protocols must adapt in order to continue to route packets to the mobile host. In addition, different wireless networking products or services, intended for example for local-area, metropolitan-area, and wide-area use, must make different tradeoffs in factors such as bandwidth, latency, error rate, and usage cost, providing different levels of quality of network connection to the mobile host. With each change in mobile host location, the routing decisions should take these differences into account, and higher-layer protocols and applications on the mobile host and on other hosts communicating with the mobile host should be able to adapt to the characteristics of the mobile host's new network connection.

The Monarch Project covers areas ranging roughly from portions of the ISO Data Link layer (layer 2) through the Presentation layer (layer 6). Our research approach consists of four themes:

• Protocol design and implementation of new protocols for wireless and mobile networking, or improvements to existing protocols to better support this goal. We have developed new protocols for mobile internetwork routing (Mobile IPv4 and Mobile IPv6) and wireless mobile ad hoc networking (DSR), and are also actively working on other protocol areas.
• Performance measurement and simulation of the protocols we develop, to better understand and improve their behavior and to improve their design. We have been very active in the implementation of the protocols we develop, and have also developed a very detailed, realistic wireless and mobile network simulator that we are using in evaluating our work.
• Usage-based evaluation of these protocols, to analyze how the protocols behave in actual operational usage. For example, we have deployed Mobile IP home agents and foreign agents on four major subnets on campus and hope to enlarge our user community to better evaluate the protocol under real usage.
• Active contribution to Internet standards through the IETF, the principal protocol standards development organization for the Internet. Active participation in the IETF (Internet Engineering Task Force) provides a unique opportunity to transfer the results of our research into the Internet community, and we have been very successful at this in our work.

The Monarch Project is named in reference to the migratory behavior of the monarch butterfly. Each autumn, millions of monarch butterflies migrate from central and eastern United States and Canada to overwintering roosts in central Mexico; with the coming of spring, the monarch population again migrates northward. The name Monarch can also be considered as an acronym for Mobile Networking Architectures. Our work is currently funded by NSF, DARPA, the AT&T Foundation, and Caterpillar Inc., and we have also previously received funding from Bellcore, the Carnegie Mellon Information Networking Institute, and AEG Transportation Systems.

My research interests are in the areas of computer vision, visual and multi-media technology, and robotics. Common themes that my students and I emphasize in performing research are the formulation of sound theories which use the physical, geometrical, and semantic properties involved in perceptual and control processes in order to create intelligent machines, and the demonstration of the working systems based on these theories. My current projects include basic research and system development in computer vision (motion, stereo and object recognition), recognition of facial expressions, virtual(ized) reality, content-based video and image retrieval, VLSI-based computational sensors, medical robotics, and an autonomous helicopter.

Computer vision.
Within the Image Understanding (IU) project, my students and I are conducting basic research in interpretation and sensing for computer vision. My major thrust is the "science of computer vision." Traditionally, many computer vision algorithms were derived heuristically either by introspection or biological analogy. In contrast, my approach to vision is to transform the physical, geometrical, optical and statistical processes, which underlie vision, into mathematical and computational models. This approach results in algorithms that are far more powerful and revealing than traditional ad hoc methods based solely on heuristic knowledge. With this approach we have developed a new class of algorithms for color, stereo, motion, and texture.

The two most successful examples of this approach are the factorization method and the multi-baseline stereo method. The factorization method is for robust recovering shape and motion from an image sequence. Based on this theory we have been developing a system for "modeling by video taping"; a user takes a video tape of a scene or an object by either moving a camera or moving the object, and then from the video a three-dimensional model of the scene or the object is created. The multi-baseline stereo method, the second example, is a new stereo theory that uses multi-image fusion for creating a dense depth map of a natural scene. Based on this theory, a video-rate stereo machine has been developed, which can produce a 200x200 depth image at 30 frames/sec, aligned with an intensity image; in other words, a real 3D camera!!

Currently, we are working on a rapidly trainable object recognition method, a system for modeling-by-video-taping, and a multi-camera 3D object copying/reconstruction method.

Visual media technology for human-computer interaction.
A combination of computer vision and computer graphics technology presents an opportunity for a new exciting visual media. We have been developing a new visual medium, named "virtualized reality." In the existing visual medium, the view of the scene is determined at the transcription time, independent of the viewer. In contrast, the virtualized reality delays the selection of the viewing angle till view time, using techniques from computer vision and computer graphics. The visual event is captured using many cameras that cover the action from all sides. The 3D structure of the event, aligned with the pixels of the image, is computed for a few selected directions using the multi-baseline stereo technique. Triangulation and texture mapping enable the placement of a soft-camera to reconstruct the event from any new viewpoint. The viewer, wearing a stereo-viewing system, can freely move about in the world and observe it from a viewpoint chosen dynamically at view time. We have built a 3D Virtualized Studio using a hemispherical dome, 5 meters in diameter, currently with 51 cameras attached at its nodes. There are many applications of virtualized reality. Virtualized reality starts with a real world, rather than creating an artificial model of it. So, training can become safer, more real and more effective. A surgery, recorded in a virtualized reality studio, could be revisited by medical students repeatedly, viewing it from positions of their choice.

Or, an entirely new generation of entertainment media can be developed - "Let's watch NBA in the court": basketball enthusiasts could watch a game from inside the court, from a referee's point of view, or even from the "ball's eye" point of view.

Also, I am interested in and currently working on vision techniques for recognizing facial expression, gaze, and hand-finger gestures. Such techniques will provide natural non-intrusive means for human-computer interface by replacing current clumsy mechanical devices, such as datagloves.

Computational Sensor.
While significant advancements have been made over the last 30 years of computer vision research, the consistent paradigm has been that a "camera" sees the world and a computer "algorithm" recognizes the object. I have been undertaking a project with Dr. Vladimir Brajovic that breaks away from this traditional paradigm by integrating sensing and processing into a single VLSI chip a computational sensor. The first successful example was an ultra fast range sensor which can produce approximately 1000 frames of range images per second an improvement of two orders of magnitude over the state of the art. A few new sensors are being developed including a sorting sensor chip, a 2D salient feature detector (2D winner-take-all circuits), and others.

Medical Robotics and Computer Assisted Surgery.
The emerging field of Medical Robotics and Computer Assisted Surgery strives to develop smart tools to perform medical procedures better than either a physician or machine could alone. Robotic and computer-based systems are now being applied in specialties that range from neurosurgery and laparoscopy to opthalmology and family practice. Robots are able to perform precise and repeatable tasks that would be impossible for any human. The physician provides these systems with the decision making skills and adaptable dexterity that are well beyond current technology. The potential combination of robots and physicians has created a new worldwide interest in the area of medical robotics. We have developed a new computer assisted surgical systems for total hip replacement. The work is based on biomechanics-based surgical simulations and less invasive and more accurate vision-based techniques for determining the position of the patient anatomy during a robot surgery. The developed system, HipNav, has been already test-used in clinical setting.

Vision-based Autonomous Helicopter.
An unmanned helicopter can take maximum advantage of the high maneuverability of helicopters in dangerous support tasks, such as search and rescue, and fire fighting, since it does not place a human pilot in danger. The CMU Vision-Guided Helicopter Project (with Dr. Omead Amidi) has been developing the basic technologies for an unmanned autonomous helicopter including robust control methods, vision algorithms for real-time object detection and tracking, integration of GPS, motion sensors, vision output for robust positioning, and high-speed real-time hardware. After having tested various control algorithms and real-time vision algorithms using an electric helicopter on an indoor teststand, we have developed a computer controlled helicopter (4 m long), which carries two CCD cameras, GPS, gyros and accelerometers together with a multiprocessor computing system. Autonomous outdoor free flight has been demonstrated with such capabilities as following pre-scribed trajectory, detecting an object, and tracking or picking it from the air.

Toward this goal, I create "cognitive models", computer simulations of student thinking and learning, that are used to guide the design of educational materials, practices and technologies. These cognitive models provide the basis for an approach to educational technology called "Cognitive Tutors" in which we create rich problem solving environments for students to work in and provide just-in-time learning assistance much like a good human tutor does. I have developed Cognitive Tutors for mathematics and science and have tested them in the laboratory and the classroom. In a whole-year classroom study with our Algebra Cognitive Tutor, I have shown that students in our experimental classrooms outperformed students in control classes by 50-100% on targeted real world problem solving skills and by 10-25% on standardized tests.

My research has contributed new principles and techniques for the design of educational software and has produced basic cognitive science research results on the nature of mathematical thinking and learning. I am currently a codirector of the Pittsburgh Advanced Cognitive Tutor (PACT) Center and am managing teams of cognitive scientists, programmers, and teachers to create integrated learning solutions that include text materials, teacher training and Cognitive Tutors. I am a co-founder and board member of Carnegie Learning Inc., a new company that is marketing these technology-enhanced learning solutions to schools and colleges across the country.

I have broad interests in the design and social impact of computing and have conducted research on office automation and employment quality, technology and home-based employment, the communication needs of collaborating scientists, the design of information technology for small-group intellectual work, and the impact of national information networks on organizations and families.

My research in an area examines in detail the challenges groups currently have in performing social tasks, designs new technology to meet some of these challenges, and evaluates the usefulness of the new technology. This cycle of needs assessment, technological design, and evaluation has both scholarly and applied products. For example, research on scientific communication treats scientists as prototypical of collaborating work teams and examined the problems they must solve to accomplish their work and the technologies that might aid them. Other empirical work examined the process by which executive teams engaged in a semester-long business simulation develop shared mental models and the effects of these models on their success. Together this research has contributed both to contemporary theories of team performance and to the design and demonstration of experimental information system for informal interaction, for collaborative writing, and for collaborative awareness.

I am also conducting research on the role that nationwide computer networks, like Minitel in France or the Internet in the United States, have on the interrelationships among firms and on the dynamics of the family. These networks increase the efficiency with which firms can search for or exchange information with each other, but they also shift the type of information that can easily exchanged, from personal to quantitative. The research examines how these shifts in the cost and quality of communication may influence interfirm loyalties and market relationships. At the level of the family, the research examines how easy access to remote and personalized information sources and communication partners changes family's dependence on local resources, among other topics.

Language Technologies.
One of the most challenging, fascinating, and applicable areas of research in human language technologies is the design of computational models of language as a statistical source. Suppose that we were to play a game where I read to you from the The New York Times and periodically ask you to guess the identity of the next word. The entropy of the Times is the average number of yes-or-no questions that you need to ask---if you're as clever as you can be---to determine the identity of the word. The goal of language modeling is to develop computer programs that play this game well. The notion of entropy provides a mathematical foundation on which to build solutions to this problem. We have recently used language models as the basis for a new approach to unsupervised clustering of documents and words; such clustering algorithms are important for a wide variety of tasks in information retrieval, natural language and speech processing.

Statistical Learning Algorithms.
Many of the tasks that we work on in language technologies use machine learning algorithms to extract patterns from historical data to predict future behavior. An example is our work on text segmentation in which we build an exponential model to extract relevant features of the surrounding text to determine where to place story boundaries. There are fascinating connections between these techniques and "boosting" algorithms in machine learning, as well as more classical regression techniques in statistics. We are working to develop the links between these different areas, and to formulate them in terms of a general computational framework for statistical inference.

Coding and Information Theory.
Algorithms on graphical structures play a central role in both communications technology and formal verification. We have recently established a close correspondence between trellises, which are widely used in the construction and decoding of error-correcting codes, and binary decision diagrams, which have found widespread use in computer-aided design and formal verification of digital circuits. Based on this bridge, we are working to transfer ideas between these previously disparate fields. The fundamental problem that confronts both uses of graphical methods is the same: devise techniques to combat the exponential blowup in the size of the graph. In addition to coding and verification, we are also investigating applications of the underlying ideas to such areas as database search.

My research is in the design and implementation of advanced programming languages. I am especially interested in approaches based on principles from formal semantics and type theory, with a particular emphasis on applications in operating systems and networks. Much of my work is centered around the Standard ML programming language (SML) and its theoretical underpinnings. SML provides many advanced features, including first-class functions and continuations, polymorphic types with automatic type inference, garbage collection, and a powerful system for specifying parameterized modules. Jointly with Robert Harper, I work on the Fox Project, which is using SML to implement high-speed network communication protocols. Not surprisingly, we get great benefits from the expressive power, type safety, and support for modularity and composability provided by SML. As a result, our networking system is extremely reliable and easy to reconfigure for special-purpose applications. (You can try out our web server written in SML. This is also a good way to get more information about the Fox Project.)

Using SML directly for systems programming is just the tip of an iceberg, however. What is actually more significant than the language itself is the theoretical foundation that has been developed for the language. This theory has the potential for applications beyond the realm of the SML language itself. The main areas for my focus are the following:

Proof-Carrying Code.
One problem that is becoming more important in distributed and web computing is how one agent (the code consumer) can be assured of safety when it executes code supplied by another agent (the code producer). Instead of using expensive run-time mechanisms such as separate address spaces or dynamic fault checks, Proof-Carrying Code (PCC) requires that the code producer to supply a proof that the code is safe. The proofs are written in a special language (without any use of cryptography) so that the code consumer can know with total confidence that the code is safe. To date, the concept and some limited demonstrations of PCC have been developed, but much more work needs to be done in order to make it fully practical.

Program Analysis and Transformation.
The ML language has a well-defined formal semantics, which forms an excellent basis for developing static analyses and optimizations. However, some of the advanced features of the language, such as higher-order functions, make it hard to get precise information from a static analysis. My students and I have been working in the general mathematical framework of Abstract Interpretation to overcome these problems.

Run-Time Code Generation.
There are many situations, especially in systems such as network protocols, where information that would be useful for compiler optimization becomes available only at run time, but once available, it remains relatively static. In such cases, it is often profitable to delay some optimization and code generation until run time. I have been working on using techniques from partial evaluation to achieve very fast and effective run-time optimization and generation of ML programs, so as to exploit these kinds of situations. For example, using a prototype system, we can demonstrate an interpreter for Berkeley Packet Filters written in ML. Our system achieves a 40% reduction in per-packet latency over the Berkeley C implementation. The unifying theme of all of these research problems is the exploitation of the underlying semantics of the programming language. It is my strong belief that this will be one of the keys to new approaches to software development.

My research involves the application of computational, modeling and electrophysiological techniques to study the neural basis of visual perception and recognition. The current effort of my laboratory is focused on the following scientific issues in the areas of computational neuroscience and computational vision.

The first issue concerns with feedback and hierarchical computation in the visual system. The classical paradigm for vision, as delineated by Marr, is that vision is accomplished by a series of feedforward computations in the visual hierarchy. The experimental findings from my laboratory show that global contextual information can modify the computation in early visual areas, presumably mediated by the massive recurrent feedback from the higher level cortices to the earlier ones. What is the functional role of this feedback? What are the advantages of the concurrent and interactive computation across the visual hierarchy? To address these questions, we are constructing and testing computational models and realistic neural circuits in conjunction with recording from neurons across the visual hierarchy while the monkeys are observing stimulus patterns of different complexity.

The second issue concerns with the dynamic and active aspects of vision. Much of the vision research has focused on the analysis of patterns in static situations by the visual system or by computer. Vision in reality is an active and dynamic process. Our eyes move constantly, purposefully scanning the environment to construct a coherent internal representation of the scene based on the retinal data, which is precise only in the fovea. How are these bits and pieces of retinal information assembled and integrated over time to form a seemingly coherent picture of the world? How and where are these scene elements represented in the brain? To address these questions, we are conducting human psychophysical experiments to examine information transfer across saccadic eye movements, formulating and testing computational models for scene integration, recording from neurons when monkeys are actively scanning and searching in the visual environment.

The third issue concerns with neural plasticity and learning. The brain is an adaptive system. Even after development, the neural circuits remain plastic and exhibit changes with learning. Currently, we are implanting electrode arrays of 100 electrodes into the monkeys' neocortex to record from the same neurons in the visual system over long periods of time (months) during which the monkeys will be trained to perform new perceptual grouping and perceptual discrimination tasks. The experiments are inspired by unsupervised and reinforcement learning models, but we hope to infer from the neurophysiological data the neural algorithms underlying the development, formation and maintenance of neural circuits in the visual hierarchy.

The fourth issue concerns with the structure of neural code For the last thirty years, the average firing rate of the neurons has been considered to be the most reliable measure of neural information. We are analyzing single and multi-electrode data to examine the possible existence of precise temporal spike pattern hidden in the neural spike trains that may encode higher order structures using various pattern analysis, machine learning and statistical techniques.

By elucidating the neural code, representations and algorithms underlying biological computation and learning, we hope not only to gain a better understanding of the mind and the brain, but also to discover new and more powerful ways to build learning systems and robots.

My research focuses on computational approaches to understanding cognition, especially the human language capability and its relationship to human and machine learning. My approach includes both the creation of fine-grained computational models of language processing and the creation of environments for augmenting and facilitating human-computer language interactions. Past research includes the creation of an adaptive natural language interface (CHAMP) that learned the idiosyncratic grammars of different individuals. Together with students, I subsequently developed two systems within the Soar architecture. EFH-Soar was a project that studied the efficacy of education in microworld environments through modeling and empirical testing. NL-Soar, my main focus during the past seven years, is a comprehensive cognitive model of adult language comprehension and production, integrating language, learning, problem-solving and action in a unified framework. Most recently I have refocused my research toward developing a computer-based environment for remediating language in language-disordered children -- work that builds directly on my previous experience with adaptive interfaces, human language modeling, and education in microworlds.

Unlike other software intervention, Simone Says is designed to be a speech-based, interactive environment intended initially for young, non-mute children with autistic spectrum disorders. It creates opportunities for meaningful, verbal language practice across a wide range of linguistic tasks in a simple social world. Tasks cover vocabulary, basic syntax, semantics and pragmatics, joint attention, conversational turn taking, and simple conversational repair. The system's design combines sound clinical practice with the engaging features found in off-the-shelf early learning software, including child-centered control, animation and sound, and readily-available help in the form of animated character guides. It is the child who decides which object(s) to talk about from those visually available and what to make the object(s) do. However, in all instances only referentially meaningful utterances produce an animation, with modeling available if the child cannot produce one. When a language concept is first introduced, the child is unlikely to give a meaningful response to the visual image. In this circumstance, using Simone Says is like a linguistic game of Simon Says: Simone models, the child repeats. As the child's language grows, however, using the system becomes more like verbally clicking on visual hot spots: meaningful speech produces meaningful action on demand. From the child's perspective, increasing proficiency is rewarded by increasing control. Creating Simone Says requires a number of advanced technologies. A primary requirement is a speaker-independent, continuous speech recognition system (such as SPHINX-II) with an acoustic model that can be adapted to young children's voices. Simone Says also requires a method for dynamically tracking the child's language development (such as the one in CHAMP) in order to construct the next target example and provide a constrained language model to the recognizer. Finally, the system must have a method for translating the linguistic description of the next example into a visual image and animation that can dynamically accommodate variation along dimensions such as color, size, number of objects, participation of animated characters, and substitution of objects from the same semantic class. The off-the-shelf animation authoring environment Director seems to be adequate to the task. Each of the components is understood well enough to make an initial implementation of Simone Says feasible. The main contribution clearly lies in bringing all these independently-developed technologies together into a coherent, engaging, and pedagogically effective real-time environment.

I am interested the computational principles underlying the ability of the brain to represent and process of complex, real-world patterns. To understand how we perform such tasks as speech or object recognition, we must not only tackle the question of how to code sensory information, but also how this code is processed to represent more abstract properties of the stimulus. For example, what are the basic computations underlying the formation of perceptual invariances such as the ability to recognize words independent of speaker or objects independent of orientation? Research in my lab works toward these goals by developing and applying principles of information representation and processing.

Computational Principles of Sensory Coding.
Part of my work focuses on the issue of sensory coding: How should natural images or sounds be encoded? One approach that my research has developed is the application of probabilistic models to learn codes that are efficient in an information theoretic sense. Given a particular sensory environment, this top-down computational approach makes predictions about the properties of neural codes at the population level. When this approach is applied to natural images, the resulting representation very closely matches the receptive field properties of visual cortex cells. This framework also demonstrates that the model system encodes natural images more efficiently than many common Fourier or wavelet-based coding schemes. Because the theory based on general probabilistic models of a high dimensional data space, it can be applied to a variety of sensory patterns including static and dynamic visual images as well as patterns from different acoustic environments. A recent extention of this theoretical framework to the temporal domain led to a theory for how continuous time-varying signals can be optimally represented by a population of spiking neurons.

Higher-Order Representation and Inference.
A second aim of my work is to develop algorithms for learning hierarchical representations. These are important because they can extract successively more abstract properties of the sensory patterns and may provide insight into how the brain carries out more complex aspects of perception that subserve object recognition. One result of this work has been a computational explanation for the role of feedback, which is ubiquitous in the brain, but poorly understood. The long term goal of this research is to develop abstract neural architectures and learning algorithms that help elucidate the details of the higher-level processes that allow the brain to perceive and process natural stimuli under a wide range of conditions. These include the computational principles underlying the representation and learning of perceptual invariances and attentional processes such as auditory and visual scene segmentation.

Image and Signal Processing.
As we better understand ways in which to represent and process sensory information, we can also develop better algorithms for image and signal processing. For example, the application efficient coding framework to natural images yields a code that is demonstrably more efficient than many standard methods of compression such as wavelets or JPEG. Furthermore, because this framework is based on probability theory, it leads naturally to algorithms for optimal inference in the face of uncertainty such as denoising and filling-in of missing information. Further extensions have led to novel algorithms for texture recognition and segmentation.

Efficient Algorithms for Processing Natural Signals.
Another important aspect of my research is the development of computationally efficient algorithms. Many algorithms are attractive from the viewpoint of theory but are of sufficient complexity that they can only be applied to small toy problems, which may not provide a valid test of the underlying computational theory. Developing efficient implementations of these algorithms allows them to be tested on more realistic problems and also affords the possibility of developing practical applications.

My research area is networks for parallel and distributed computer systems. For the past few years my research has focused on how to build the communications system that underlies a parallel computer. My goal has been to develop mechanisms for moving data between processors (or between processors and memory) that are both practical and provably effective. To this end, I have designed, analyzed, and implemented algorithms for routing, sorting, and tolerating faults in parallel computers.

As an example of this type of work, Berthold Voecking and I have recently shown that an N-node AKS network can be embedded in a 3N/2-node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorithms for sorting n keys on an n-input multibutterfly in O(log n) time, and a three-dimensional VLSI layout for the n-input AKS network with volume O(n^(3/2)). These algorithms provide further evidence of the robustness of multibutterfly networks. We have also discovered a separate, and more practical, deterministic algorithm for routing h relations on an n-input multibutterfly in O(h+log n) time. Previously, only algorithms for solving h one-to-one routing problems were known.

Micah Adler and I have been studying asymmetric networks. An asymmetric network is one in which the link bandwidth or the link reliability between two points u and v differs according to the direction u -> v or v -> u. My interest in this subject was sparked by a hobby of mine. Over the past few years I have established a high-speed internet connection between campus and my home. The link is asymmetric because it uses 2 megabit/second wireless Ethernet in one direction and a 33.6 kilobit/sec telephone line in the other. (The reason for this asymmetry is that there is too much radio-frequency noise on campus for a signal to get through from off campus.) Despite the asymmetry, the link has proved capable of supporting a remote X terminal and a web browser, thus allowing me to work from home in a graphical environment comparable to that of the workstation in my office.

Micah and I have devised protocols for transmitting information across an asymmetric communication link in the ``wrong'' (or slow) direction. We assume that a client has an n-bit data item drawn from a distribution D to transmit to a server, and that the distribution is known to the server, but not to the client. This model is motivated by the scenario in which a server is collecting a single data sample from each of many clients. We have shown that using the asymmetric link in the fast direction, the server can guide the client through a transmission in which the client does nearly as well without knowing the distribution D as it could knowing D. In particular, we have devised a protocol in which the expected number of bits sent by the server is at most 3n, while the expected number of bits sent by the client is at most 1.71H(D), where H(D) is the entropy of the distribution D. Even knowing D, the client cannot expected to send fewer than H(D) bits. We have developed variations on this protocol in which the number of handshakes between the client and server is reduced, and also proved matching lower bounds and impossibility results concerning the total number of bits sent, the amount of computation performed by the server, and the number of handshakes.

My research now continues on a new front: parallel algorithms for scientific computing.

Claudson Bornstein, Gary Miller, R. Ravi, and I have been studying the problem of solving linear systems using direct methods such as Gaussian elimination. We have focused on nested dissection. Viewing a system of equations as a graph, nested dissection can be summarized as follows. First find a set of ``separator'' vertices whose removal partitions the graph into two or more connected components. These vertices will be eliminated last. Order the individual components one after the other. (The separator prevents ``fill'' between the different components.) Within each component, order the vertices recursively.

We have analyzed the performance of a parallel variant of nested dissection that can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can be used to parallelize the ordering produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal completion that the heuristic generates from the input graph. The input to the algorithm is a chordal graph G with n nodes and m edges. The algorithm produces an ordering with height at most O(log^2 n) times optimal, fill at most O(m), and work at most O(W(G)), where W(G) is the minimum possible work over all elimination orderings for G. Experimental results show that when applied after some other heuristic, the increase in work and fill is usually small. In some instances the algorithm obtains an ordering that is actually better, in terms of work and fill, than the original one.

Claudson, Gary, and I have also analyzed a new sequential variant of nested dissection based on the following idea: once all but one of the components has been eliminated, the separator need not be eliminated last. We have developed a heuristic for determining when to eliminate the separator last, and when to merge it with the last component. In practice, our heuristic has been shown to outperform all of the publically available codes for nested dissection in terms of work and fill. The heuristic also has a theoretical motivation: unlike standard implementations of nested dissection, when applied to chordal graphs it produces a zero-fill elimination order.

My research area is robotics. Consider a human being in its natural habitat performing its natural patterns of behavior, for instance going to the lounge for coffee. As it walks down the corridor, dodges other humans, opens doors, pours the coffee, and makes more if it took the last cup, the brain demonstrates an impressive and apparently effortless ability to (1) know what is going on out in the real world, and (2) react appropriately. That is what brains are best at; in some sense that is what brains were designed to do.

Computers cannot do it, at least not yet, not nearly as well as a human. Why not? The main problem appears to be software. We need to know how to represent information about the state of the world, how to infer such information from sensory data, and how to apply that information to choose actions. Those problems are the foundation of robotics. My research aims to explore those problems and search for the principles and techniques that will enable computers to interact with the real world.

Mobile Manipulation (A Robotic Dungbeetle).
Dungbeetles use their legs both for locomotion and manipulation. We are building robots which apply the same principle. Our first system is a mobile robot which uses its wheels for manipulation as well as for locomotion. Imagine a small car planting its front wheels on a piece of paper, and using the rear wheels to drive the robot and the paper around. At the same time, if the front wheels are powered, the robot could use them to manipulate the paper. Or even more challenging: imagine the car rolling its front wheels onto a pencil, then rolling the pencil around on the desk, sort of like a dung beetle. Quicktime videos.

Dynamic Manipulation (Robot Juggling).
Robots typically use static and quasistatic methods to interact with the world. People, on the other hand, are adept with dynamic methods. Some scientists have argued that the evolution of the human brain was driven by the challenges of accurate throwing. It is an interesting challenge to model-based robotics to develop robots that can exploit the dynamics of a task domain. So far we have demonstrated several instances--a snatch, a throw, and a rolling throw. Each of them is planned automatically using information about the object such as its shape and mass, and also with a good model of the dynamic behavior of our arm.

Quicktime video of rolling throw.

RESEARCH GOALS.
Our goal is to make computer systems robust and safe. We are trying to understand why computers fail, and what can be done about it. This includes circumstances in which people fail when operating computers, as well as circumstances of autonomous operation. We are solving dependability problems by engaging in the design, implementation and evaluation of a wide variety of highly dependable systems (including their user interfaces) for mission-critical environments (e.g., hospital patient monitors, air traffic control systems, semiconductor wafer-fabrication process-control environments, and national infrastructure systems such as banking, communication and electric energy networks). By making systems more dependable, the consequences of downtime, such as monetary losses exceeding tens of thousands of dollars an hour, or loss of life, can be avoided.

OVERVIEW.
According to popular wisdom, about 95% of all errors are created by the systems under which we work. Computer systems are no exception; many people have personal experience with errors in hardware and software. Human error in conjunction with computer systems is now responsible for as much as 80% of system unavailability; when systems fail, 65% of the recovery effort is spent in diagnosis. Consequently, two important thrusts for our work lie in dependable user interfaces and automated real-time diagnosis, both of whose goals are to mitigate error and to reduce downtime along with its associated costs. Our work is highly quantitative and very much measurement- and data-driven. We conduct careful empirical and theoretical performance evaluations of all our systems; some of our research also involves the design and implementation of evaluation methods themselves.

Computer System Failure.
Computers have always been subject to hardware failures, most of which can be mitigated through the use of fault tolerance. Now that the mean time between hardware failures exceeds 40,000 hours, software failures appear to dominate undependability statistics. As progress is made in solving the problem of software reliability, the dominant cause of outages is likely to shift to those that are operator-induced, suggesting that the failures reside in the user interface. Sometimes these modes are mixed, such as when a software fault is the result of a programmer's failure to recognize and handle exceptions correctly. More recently, the growth in scale and complexity of computer systems has exacerbated the problem of making systems of systems robust to failure. One example is the Internet, which is subject not only to traditional failures, but also to malicious attacks such as denial of service, information theft, and intrusion and corruption by unauthorized users. Because corporations and nations have come to depend so heavily on computer-based information and infrastructure, some pundits have claimed that the next great war will be fought in information space, where foreign operatives use the Internet or other means in attempts to steal corporate secrets, disable regional power grids, cripple a nation's telephone system, or destroy a nation's military command and control system.

CURRENT PROJECTS:
Detection, Diagnosis And Compensation For Failures.
Detecting and interpreting unanticipated failures (failures that no one ever thought of during system design), including human interaction failures, is one focus for our research activities. We are building systems that cope with failures by learning about the characteristics of their own environments. One example lies in semiconductor wafer fabrication, one of the most complex manufacturing process known to mankind, in which we have conducted real-time fault-detection and diagnosis experiments in an operational semiconductor plant, achieving 100% correct diagnosis of faults injected during the course of producing over 46,000 customer wafers.

Intrusion Detection - Combating Information Terrorism/Warfare.
Our work in intrusion detection is closely related to our work in fault detection and diagnosis, and includes the construction of synthetic environments for validating the intrusion detection systems we field. We regard intrusions to be examples of unanticipated anomalous conditions, and we treat them as we do anomalies in hardware and software systems.

Dependable User Interfaces.
Undependable user interfaces are the Achilles' heels of highly dependable systems. Even if a system's hardware and software underpinnings are completely reliable, user-interface errors can cripple or destroy a mission. Our objectives are to mitigate these errors (and corresponding downtime) through careful design of predictably dependable systems, and to provide measurable confidence of dependability in user interfaces. This research is investigating what makes user interfaces dependable, what are the sources of human error, and what are the limitations of the human operator? It seeks an understanding of how such knowledge can be coupled with interfaces that can be depended on to work, as needed, the first time. User and system modeling are major constituents of ongoing efforts. The research incorporates work on human error, robust evaluation, methodologies for requirements analyses, task and user modeling, design and testing of predictably dependable interfaces, fault tolerance and reliability, quantitative metrics and instrumentation, and empirical and experimental methods.

Evaluation Workstation (Metristation).
The seriousness of user-induced failures demands that practitioners and scientists develop tools and methods for evaluating the efficacy and dependability of user interfaces before they are deployed. In this context, dependability is the probability that the system will work the first time it is used. User-interface evaluation is often tedious, time-consuming, error prone and not very robust. The very tediousness of effective evaluation frequently prevents researchers from engaging in it. The Evaluation Workstation project endeavors to reduce the tedium and inaccuracy of these analyses, and at the same time speed them up. It includes timestamped keystroke, mouse-click and event capture; digital audio for verbal protocols; digital video for video protocols; and eye tracking.

Data Mining-Structure Discovery In Large, Uncontrolled Data Sets.
Detection and diagnosis of faults usually necessitate recognizing known patterns or structures embedded in monitored data. If the system environment is novel, as it is in most new products or for new medical patients, then few if any known patterns exist. Such patterns must first be discovered before they can be employed in detection processes. This project seeks to understand how patterns can be discovered in large data sets monitored from such applications as manufacturing process control, networked communications, medical operating rooms, international banking transactions, intrusion-detection systems and others.

Synthetic Data Environment.
How do we gain confidence in a system's ability to detect failures, anomalies or performance perturbations? This project's goal is to build a synthetic environment that can be used for validating fault/intrusion detection systems. We expect it to be made available on the World Wide Web for anyone to use. It will have the capability to replicate environmental conditions faithfully and repeatably, and will be easy to use for both experts and novices. Safety Cases For Dependability. We are exploring the use of formal legal argumentation to support claims of system dependability. One example is justifying safety claims for fly-by-wire or drive-by-wire systems. Another example is justifying claims that a fault-diagnosis system will detect all unanticipated faults.

I am interested in Parallel-Distributed-Processing (PDP) models of perception, memory, language and thought. PDP models assume that cognitive processes in humans emerge from the interactions of large numbers of simple processing units. Each unit is very simple, in that it computes a monotonic function of a weighted sum of its inputs from other units, and adjusts its output accordingly. However, large networks of such units can exhibit intelligent behaviour, and lead us to new conceptions of the basis of intelligent processing. For example, representations in PDP networks are patterns of activation. These representations differ from representations in conventional computers in that they cause patterns to evolve and change (via the connections among units), without the requirement of the intervention of a CPU to interpret their content and take appropriate action. Knowledge in these networks is stored in the strengths of the connections among the units. This means that learning occurs not through the formulation and testing of explicit rules, but through the adjustment of the strengths of the connections among the units.

In recent years, my research has come to focus on issues related to learning, memory, and development, in a cognitive neuroscience context. In McClelland, McNaughton and O'Reilly (Psychological Review, 1995, 102, 419-457), we have developed a complementary learning systems perspective. On this view, the need to learn in ways that are sensitive to the general structure of events and experiences is computationally incompatible with the need to learn the specific contents of particular events and experiences. Complementary memory systems that use very different types of representations and very different parameters of learning are required to address these incompatible goals. Initial work focussed on the second, 'episodic' memory system, which is thought to be associated with the hippocampus and related structures in the medial temporal lobes (O'Reilly and McClelland, Hippocampus, 1994, 4, 661-682; McClelland and Goddard, Hippocampus, 1997, 6, 654-655). Currently, work focusses primarily on the structure-sensitive system, thought to be the basis for our acquisition and use of structured knowledge in a wide range of domains including the semantics of everyday objects, the structure of language, our intuitive understanding of the physical world, etc. Munakata, McClelland, Johnson, and Siegler (to appear in Psychological Review, 1997, 104, October issue) develop a computational model of the acquisition of Object Permanence knowledge. Other work in preparation addresses the acquisition and dissolution of semantic knowledge of everyday objects. Some of the most important current work relates to the hypothesis that learning in the neocortical system is Hebbian in character. This hypothesis is used to account for the apparent stability of language representations when persons from one language community attempt to learn a new language in adulthood, and to account for recent evidence that there may be far more plasticity in the language system than this apparent stability suggests, as indicated by remediation studies that appear to work because they rely on principles of Hebbian learning.

My background is in photogrammetry, the use of images to make precise measurements; my work here in the Digital Mapping Laboratory with Dave McKeown is concerned with the integration of rigorous photogrammetric techniques into image understanding algorithms.

I focus on realistic cartographic scenarios, using aerial mapping imagery and performing resections to determine the image location and orientation. Using this information about the image, always available in a cartographic environment, allows us to make much stronger statements about the geometric and metric properties of the scene and to reference external sources of information such as digital elevation models and feature data. I also study the geometric properties of images for ways to utilize the geometry in scene understanding. For instance, we have used the vanishing point geometry, calculated from the image orientation, to identify possible vertical and horizontal lines in the scene. These attributions are used in two monocular building extraction systems developed by Jeff Shufelt, VHBUILD and PIVOT, to help form and prune building hypotheses. The calculated measurements of scene features also aid in hypothesis evaluation and testing.

Along with imaging geometry, I am exploring the use of object-space geometric constraints to aid in the recognition, extraction, and precise measurement of buildings or other objects whose geometry is partially or completely known or can be inferred. I have extended statistical approaches used for data editing to the examination of these geometric constraints, to detect situations where the assumed geometry is incorrect--the constraint equations are not valid. An important part of standard photogrammetry is error analysis. I am extending traditional point error measures to extracted image features and then using these error estimates in feature fusion and evaluation for scene interpretation.

The use of rigorous photogrammetry is particularly important in stereo matching, especially for stereo pairs with oblique viewing geometry. Steven Cochran has shown that precise reprojection into epipolar alignment produces measurably better results than standard image warping approaches. In the future we will be looking at estimating the precision of the stereo match, based on parameters such as imaging geometry and image frequency content.

Another area of research in the MAPS lab is the classification of high-resolution multispectral and hyperspectral imagery and its fusion with panchromatic aerial imagery. I am working on the precise registration of the imagery, obtained from line scanners and linear pushbroom sensors, and the exploitation of its spectral and geometric properties for cartographic feature extraction.

I am also interested in optimization techniques, especially in the parallels between standard and robust least-squares adjustment as practiced in the photogrammetric community and energy-minization optimization techniques currently popular in the computer vision field. The underlying mathematics are basically similar; by "switching metaphors" from statistical to physical properties and back we can combine statistical concepts such as the standard deviation of a measurement with physical concepts such as the amount of force an operator must exert to move an object. This has potential for semi-automated image exploitation, yielding a good interactive metaphor while maintaining rigorous interpretations of inputs and results.

My research interests are in computer vision, remote sensing, cartography, and large-scale spatial databases. Within the Digital Mapping Laboratory we have a number of research projects each with components in image understanding and remote sensing, photogrammetry and cartography, and computer graphics.

Most recently our focus has been on a set of issues involving the rapid construction of virtual world databases for visual simulation. These databases require the integration of information from digital cartographic products, aerial and satellite imagery, and ground-based photography. They also require intelligent database compilation techniques to support maximal fidelity of the geo-spatial virtual world while using bounded, and often highly limited, visualization resources. In computer vision our research includes the automated analysis of traditional mapping photography as well as emerging multispectral and hyperspectral sensors. There is a common theme involving the fusion of information derived from multiple methods and reasoning about multiple plausible object space interpretations. There is a strong bias toward tying scene analysis 'to the ground' as a way to demonstrate and evaluate research progress.

My main interest is in algorithm design and parallel computation. For the last several years I have worked parallel algorithm design for problem arising in Scientific computation. This includes problems such as fast linear system solvers and mesh generators. Over the last several year our group has developed a large suit of fast and efficient algorithms for these types of problems.

Starting this year, in collaboration with faculty members Guy Blelloch, Bob Harper and Peter Lee, we have begun an ambitious project funded by the NSF to develop a Scientific computing package in a parallel extension of the language ML. I am very excited about this project for it will draw on the talents of the worlds best compiler, language, and parallel algorithm designers. We will be able to test and refine parallel scientific algorithms in a modern environment, as well as, tune the language and compiler to fit the applications.

I am interested in many areas of computer science, but especially in how to construct computers that learn from experience. At the heart of the problem of machine learning is the question of how to automatically formulate general hypotheses given a collection of very specific training examples. My research has addressed a number of approaches to this question, including statistical approaches that find regularities over large numbers of training examples, and analytical approaches that generalize from very few examples and rely instead on prior knowledge and reasoning.

Much of my current research focuses on developing software agents that learn about the world wide web. For example, my students and I recently developed a web browser that accompanies users from page to page, and learns to suggest hyperlinks that will be of interest to the current user. My main current project seeks to automatically construct a huge knowledge base whose content mirrors the world wide web. To see the motivation, consider the fact that your workstation can now retrieve any of 300,000,000 web pages, but it understands none of these pages -- they were written to be human readable, not machine readable. The goal of this research project is to use machine learning to train a web agent to automatically extract probabilistic, symbolic knowledge by reading the web hypertext. If successful, this would lead to a huge world-wide knowledge base that would make the web understandable to computers as well as people. This could be used for much more intelligent information retrieval, or as a large knowledge base for problem solving. Research issues here include inventing learning algorithms that will operate over hypertext, using previously extracted knowledge to guide subsequent learning, and combining natural language processing methods with machine learning.

In addition to my own research, I also direct CMU's new Center for Automated Learning and Discovery (CALD), an interdisciplinary center with faculty from computer science, statistics, GSIA, philosophy, engineering, and other departments. The mission of CALD is to invent new approaches to using historical data to improve future decisions. For example, within CALD we are studying problems such as using historical medical records to predict mortality rates in future pneumonia patients, using historical data on violent criminals to predict which will be repeat offenders, and using historical data describing credit card customers to identify future fraudulent behavior. I would be happy to discuss CALD and its research projects with interested students, and to help identify other CALD faculty with relevant interests.

My research interests center on Machine Learning and Reinforcement Learning with a particular emphasis on learning algorithms for self-improving factories, robot motion planning, adaptive control, industrial engineering. My primary goal is to help make AI become sufficiently practical, powerful and robust that is routinely used in controls and manufacturing industries. My ongoing projects:

General Memory Based learning.
A key component of any autonomous system is that it is able to constantly monitor itself and notice unexpected behavior such as unmodeled dynamics, changing dynamics or, in some cases, equipment malfunction. To do this, we make the system learn from experience. Our research has produced a highly automatic learning mechanisms. The controller explicitly remembers all its sensory experiences (typically such data is in the form of large vectors of real-valued numbers) in a large database of cases. Novel search algorithms are used to persistently monitor the database to spot unexpected trends, relations between variables, and opportunities for controller enhancements.

Reinforcement Learning.
This is an exciting new discipline in which systems learn to control themselves optimally based on arbitrary reward and punishment signals. The central issues concern processing such signals to develop optimal controllers. Our recent research involves scheduling search control during on-line planning to minimize wasted computations. Ongoing research extends this to the PartiGame algorithm, in which exploration and planning are scheduled in a multi-resolution manner. A recursive partitioning of state-space adapts itself in real time to yield fine detail in the critical regions, while remaining at a coarse granularity elsewhere. We are also investigating combining state-space triangulations and tree-search methods to combat to curse of dimensionality.

Auton: AI-based Evolutionary Operation.
Response Surface Methods (RSMs) are a heavily used, statistical technique used in the optimization of expensive industrial processes. Such processes are typically characterized by: a set of controllable parameters, a noisy measurement of the result of running a process with the given inputs. We desire to find the set of parameters which optimizes some measure of the result. Experiments are expensive, but there is plenty of computation time available between each experiment. Current RSM practice is, for sensible reasons, a far from automatic process. It is very possible that techniques from Machine Learning and AI may be of use in RSM applications. We have embarked on the production of a minimal-human-supervision controller for such systems, which watches and adjusts process over extended periods of use: persistently designing safe experiments and whenever appropriate improving the process.

Dealing with Massive Datasets.
In new research, we are examining the computational issues involved with massive datasets, including the Edinburgh-Durham Sky Catalogue of over a million galaxies. We are examining generalizations of kd-trees and R-trees for caching information sufficient to permit answers to extremely wide classes of statistical questions in near-constant time.

I am interested in Computer-Mediated Human Communication. At the low end this involves the engineering of distributed communication systems and the design of document interchange strategies. At high, or human, end it involves activities like calendar management, goal reconciliation, and group processes. The specific projects I'm currently involved with The Prep Editor, a collaborative writing tool, and Team-Centered Design, a new study of collaborative tools and methods for tasks such as crisis management.

The goal of my research is to dramatically boost the performance of future microprocessor-based systems. To accomplish this, we exploit various forms of parallelism through a combination of novel architectural, compiler and operating systems support. In particular, we have been focusing on the opportunities and challenges created by two important VLSI technology trends which are expected to reshape computer systems over the next decade: the potential for single-chip multiprocessing due to higher levels of single-chip integration, and the need to tolerate off-chip latency as the gap between processor speed and the speed of memory and I/O continues to widen.

Single-Chip Multiprocessing: The STAMPede Project.
As advances in integrated circuit technology continue to provide more and more transistors on a chip, processor architects are faced with the pleasant challenge of finding the best way to translate these additional resources into improved performance. One of the more compelling options is to integrate multiple processors onto the same chip. While this will certainly increase computational throughput, it will only reduce execution time of a given application if it can be run in parallel. Hence the key question is how do we convert the applications that we care about into parallel programs? Expecting programmers to only write parallel programs from now on is unrealistic. Instead, the preferred solution would be for the compiler to parallelize programs automatically. Unfortunately, compilers have only been successful so far at parallelizing the numeric applications commonly run on supercomputers. For single-chip multiprocessing to have an impact on the majority of users, we must also find a way to automatically parallelize the non-numeric applications (e.g., spreadsheets, web software, graphics codes, etc.) which account for the bulk of the software run on commercial microprocessors. Based on our preliminary studies, we believe that a breakthrough in our ability to automatically parallelize non-numeric applications may be possible through "thread-level data speculation", which is a technique that allows the compiler to safely parallelize applications in cases where it believes that dependences are unlikely, but cannot statically prove that they do not exist. To accomplish this, we add modest hardware support to track data dependence violations at run-time and alert the software so that it can recover appropriately. Developing the architectural, compiler, and operating system support necessary to turn this potential into a reality is the goal of the STAMPede (Single-chip Tightly-coupled Architecture for MultiProcessing) project.

Coping with Large Latencies.
Processor speeds are continuing to increase far more rapidly than off-chip components such as DRAM, disk, and networks, largely due to physical limitations such as distance and the speed of light. The challenge presented by this trend is that from the processor's perspective, the latency of main memory and I/O is increasing at a dramatic rate, and thus threatens to become an increasingly important performance bottleneck. The good news, however, is that the bandwidth of these off-chip devices has been improving through innovations such as synchronous (i.e. pipelined) DRAM, disk arrays, and fiber optic networks. Therefore we are exploring new ways that the compiler (with varying degrees of help from the hardware and the operating system) can use prefetching and other techniques to intelligently trade off consuming more bandwidth to reduce overall latency. Recent work in this area has included prefetching pointer-based codes, prefetching to hide disk latency in out-of-core numeric applications, and hiding network communication latency in workstation clusters.

Professor Nagle's research interests include architecture, embedded systems and reconfigurable computing. His primary research focuses on how careful architectural re-design throughout the system (hardware and software) can radically improve performance while greatly increase the functionality of computing systems. For example, the "Network-attached Secure Disk (NASD)" project is re-architecting traditional distributed storage systems to achieve a 10 fold increasing in system scalability. Unlike conventional approaches that fix assume either fixed hardware or software and focus on improving the other, NASD attacks both the software and hardware storage problems. Another project, "Software Defined Architectures", move processor and memory system management policy into the compiler which can more efficiently manage the underlying hardware.

I work in the general area of computer systems, specifically in the areas of Internet services and high-performance distributed computing.

Current Internet services are typically lightweight in the sense that requests for service require a relatively small amount of computation to satisfy. My students and I are addressing the problem of providing heavyweight Internet services --- such as remote visualization, data mining, and advanced search engines --- that require significant amounts of computation to satisfy requests.

Our current motivating application is the visualization of massive scientific datasets that are stored on remote servers. We are developing a toolkit for remote visualization over the Internet called Dv, which is based on a form of mobile objects called active frames that contain both code and data.

We are using Dv to provide remote visualization services for the Quake project, a long-term effort by computer scientists, engineers, and seismologists at Carnegie Mellon, UC-Berkeley, and the Southern California Earthquake Center to use computer simulation to predict the motion of the ground during strong earthquakes.

Providing heavyweight Internet services such as remote visualization on a regular basis will require advances along a number of fronts:

• Discovery, measurement, and monitoring of Internet resources (See for example, our Remos system).
• Techniques for building resource-aware applications that use tools such as Remos to sense and react to heterogeneous and dynamic network conditions.
• General-purpose toolkits for building heavyweight Internet services.

I work in the areas of human-computer interaction, virtual reality, and entertainment technology. My major interests are in how to use technology to create compelling illusions that enable us to suspend disbelief.

CMU has recently formed the Entertainment Technology Center (ETC), which I Co-Direct with Don Marinelli. As the directors demonstrate, this is a joint initiative between the School of Computer Science and the College of Fine Arts. The ETC's mission is "Leadership in education and research that combines technology and fine arts to create new processes, tools, and vision for storytelling and entertainment."

My Stage 3 Research Group has specific projects in:

Alice : My students and I have developed the Alice 3d graphics system (http://www.alice.org ). Alice is designed to be easy to learn in a short period of time, allowing the user to author desktop 3D graphics simulations, specifically concentrating on the real-time behavior of objects. Alice makes it possible to literally try hundreds of variations per day, and enables our collaborations with non-technologists, who need to be able to take a "what if" approach during the design process. Over 70,000 copies of Alice have already been distributed, and we have demonstrated that even middle school students can model, paint, and animate 3d virtual worlds (and share them via the WWW) in just one evening with the system. We currently use the Teddy modeller by Takeo Igarashi to make 3d shapes, as well as importing several common file formats. Alice is available for free.

Virtual Reality : Virtual Reality is a new medium, just as film, radio, and Macintosh/MS-Windows-style "graphical user interfaces" (GUIs) are media. In the case of film and GUIs, there are well-acknowledged components of the medium (for film, flashback, crosscut, fade, etc., and for GUIs, scroll bars, pulldown menus, and the like). We are attempting to develop the lexicon of interaction techniques for VR. We have developed several such techniques, such as "World in Miniature," "Image Plane-based Manipulation, and the "Voodoo Dolls" technique, and presented them at CHI, SIGGRAPH, and the ACM Symposium on Interactive 3D Graphics.

Why Does Virtual Reality Work in the First Place? : Working with perceptual and cognitive psychologists , we are addressing the question "When is Immersion (Virtual Reality) Useful, and Why?" This work focuses on performing user studies to determine which aspects of immersion affect task performance. Our goal is to deduce general design principles, allowing us to predict which real-world applications will benefit from immersive interfaces, and what kind of immersive technology is appropriate for each application.

For more information, please see the Web Pages for:

My personal home page
The Entertainment Technology Center
My Research Group
The Alice Project

At the heart of my research lies the desire to understand the principles of programming languages. Programming languages are the key to the programming process and therefore of fundamental importance to computer science. Well-designed programming languages allow fast program development, ease software maintenance, and increase confidence in the correctness of implementations. Poorly designed programming languages lead to verbose and impenetrable programs that are difficult to debug and maintain. One of the trends in computer science has been the development of a plethora of languages, often for very specific purposes. Unfortunately, many of these languages are woefully misdesigned, because their developers were unaware of or have disregarded basic principles of programming language design. My research thus aims at discovering such principles and experimenting with them through implementations and environments.

In support of this goal, I am pursuing three interconnected threads of research. The first is the development of meta-languages which codify programming language concepts and support formal reasoning about properties of programming languages. The second is the design of expressive type systems for practical programming languages which allow more program errors to be caught at compile-time without sacrificing conciseness or efficiency of programs. The third is the application of programming language techniques in domains where they are currently undervalued, such as mobile code or robotics. In all of these I collaborate closely with colleagues and students who are not mentioned explicitly below. Please refer to my home page for recent drafts and publications.

Meta-languages. In this area my research focuses on the development of a uniform meta-language and environment which supports specification, implementation, and formal reasoning about programming languages and logics. The currently released implementation is Twelf 1.2 which embodies many of the representation and implementation techniques discovered in my research on logical frameworks. Underlying Twelf is a type theory which is used for specification, constraint logic programming, and meta-theoretic reasoning. Twelf is a significant step towards an environment for teaching and research in the areas of programming languages and logics. Current and future work on Twelf consists mainly in improving its expressive power to capture more language phenomena in a concise and natural way. There is ongoing work on a linear extension (to capture imperative and concurrent computation), a non-commutative extension (to capture ordering and sequencing), and extension by constraints (to capture integers, rationals, and similar domains).

Type systems. In this area I have concentrated on extending the expressive power of type systems to allow more properties of programs to be checked statically. Invariants which can otherwise only be stated informally can be expressed in these systems and verified by a type-checker. This provides additional machine-checked documentation, more detailed interface specifications at the module level, and allows more errors to be detected at compile-time. All these properties combine to improve programmer productivity and simplify program maintenance. Concretely, I have developed refinement types (for inductively specified properties of data representation), dependent types (for array bound and similar constraints) and modal types (for run-time code generation).

Applications. I believe that programming language research cannot exist in a vacuum---it must address problems encountered by real programmers in real applications. Whether this is the case is often difficult to assess, since at present the gap between research on advanced programming languages and programming practice is, unfortunately, very large. One way to reduce this gap is to take problems faced by programmers today in specific areas and contribute to their solution with programming language techniques. The Fox project at CMU is a perfect example of this: combining modularity with safety and efficiency in the context of operating systems and networking code is a formidable challenge. A recent development within the Fox project has been the design and implementation of proof-carrying code (PCC). PCC guarantees the safety of mobile code by attaching a formal safety proof to the binary. The code receiver checks and discards the proof and can then safely execute the binary without further run-time checks. Proofs are represented as formal objects in the logical framework, which provided inspiration for this approach to a safety architecture. Necula and Lee used the Elf implementation as a prototyping tool until a more efficient, specialized implementation became necessary. A related effort at Princeton by Appel and Felton uses the current experimental Twelf implementation with its new constraint domains.

My research involves using computational modeling, complemented by empirical studies, to investigate the nature of normal and disordered cognitive processing in the domain of reading and language. My modeling work is cast within a connectionist or parallel distributed processing framework, in which cognitive processes are implemented in terms of cooperative and competitive interactions among large numbers of simple, neuron-like processing units. These models provide new ways of thinking about how cognitive processes are implemented in the brain, and how disorders of brain function lead to disordersof cognition. I'm particularly interested in studying the effects of damage inconnectionist networks as a way of understanding the nature of cognitive impairments that can arise following brain damage, and in exploring ways of retraining damaged networks with the goal of helping to design more effective strategies for patient rehabilitation. I'm also interested in the implicationsof connectionist learning principles for the nature of normal and abnormal cognitive development.

Much of my work has focused on word reading, both in normal skilled readers andin brain-damaged patients with acquired reading disorders. My colleagues and Ihave developed connectionist models that exhibit many of the central characteristics of skilled reading, including the influences of word frequency and spelling-sound consistency on the time to pronounce words and the ability to pronounce word-like nonsense letter strings (e.g., MAVE) and to distinguish them from real words in lexical decision tasks. When the models are damaged invarious ways, they exhibit the major forms of acquired dyslexia, including "deep" dyslexia in which patients make semantic errors in reading aloud (e.g., misreading YACHT as "boat") and "surface" dyslexia in which patients produce regularization errors to exception words (e.g., misreading YACHT as "yatched").Moreover, retraining the damaged models yields patterns of recovery and generalization that are qualitatively similar to those found in cognitive rehabilitation studies, and generates specific suggestions for the design of more effective therapy for patients .

More recently, I have begun to extend my work to address other issues in language processing, including: 1) early language acquisition and the development of phonological representations through the interplay of speech comprehension and production; 2) semantic and associative priming effects in naming and lexical decision; 3) patterns of semantic impairments among brain-damaged patients, and their implications of the degree of functional specialization within the semantic system; and 4) sentence-level processing andthe interplay of syntax and semantics.

My primary research interests are in the area of real-time and multimedia systems, specifically in the areas of multimedia and real-time operating systems, resource management techniques for predictable end-to-end timing behavior in distributed real-time and multimedia systems, and QoS-driven middleware services for these systems. My work is carried out in the Real-Time and Multimedia Laboratory.

Real-Time Mach.
The primary objective of Real-Time Mach is to provide a paradigm for predictable time and resource management in order to support distributed real-time and multimedia systems. This paradigm is supported by augmenting and extending the existing primitives in the Mach operating system. In addition, integrated real-time toolsets are provided to significantly enhance the understanding of the behavior of the systems being built. Real-Time Mach supports many primitives: real-time scheduling policies, real-time threads, synchronization mechanisms which bound and minimize priority inversion, real-time virtual memory management, resource reservation to guarantee sessions, and real-time communication protocols. Scheduler 1-2-3 and ARM (Advanced Real-time Monitor) are tools which work with Real-Time Mach for schedulability analysis and real-time monitoring of RT-Mach events. We are currently developing and distributing Real-Time Mach on a network of ix86-based workstations/laptops, and high-performance single board systems.

Real-Time Scheduling Theory.
The primary goal here is to develop needed technologies to build predictable networked real-time systems with end-to-end timing constraints. The project develops theory to analyze system timing behavior in precise mathematical terms, distributed real-time operating systems, real-time communications and networks, and automation support using tools. The philosophy of time management is based on fixed priority preemptive scheduling and in particular, rate-monotonic scheduling. This approach is currently adopted by many significant standards in real-time systems including POSIX, by many commercial operating systems with real-time support including Solaris, OS/2, Windows NT, AIX, etc. and has been used in many industrial and defense applications.

Dependable Real-Time Systems.
Many industrial application domains including aerospace, medicine, financial services, transportation, process control and manufacturing have stringent timing, high availability, safety and user-friendliness requirements. These widely varying and often contradictory requirements have forced the use of proprietary, conservative and/or inflexible solutions. The rapid advent of commercial processing and networking technologies has made little, if any, inroads into such industrial computing systems. This is primarily because such technologies often focus on throughput as the primary measure of quality. In industrial computing systems, on the other hand, raw throughput takes a secondary seat to the concerns of timeliness, availability and safety. This effort focuses on the system architecture, primitives (API) and implementation which are needed to support distributed networked systems which must meet both real-time and stringent high availability requirements. In particular, real-time scheduling theory is being married with dependability/high-availability techniques among other QoS-based metrics.

Raj Reddy's research interests include the study of human-computer interaction and artificial intelligence. His current research projects include speech recognition and understanding systems; collaboration on the web; universal digital libraries; and learning on demand.

My research centers on the design of programming languages and languages for specifying program behavior, mathematical tools for defining the semantics of such languages, and methods for proving that programs meet their specifications.

At present, my main interest is type theory. The last fifteen years have seen the discovery of a variety of type systems that have vastly enlarged our notions of what types are and how they might be used. My goal is to understand the semantics of these systems and to find a general concept of type of which they are all instances.

A second area of interest is the design, definition, and proof methodology of languages, such as Algol, that combine imperative constructs with a powerful procedure mechanism. This has led to the design of Forsythe, an extremely general and uniform Algol-like language that encompasses object-oriented programming.

Finally, I am trying to devise a functional programming language that gives the user control over the allocation and retrieval of storage. For this purpose, I am exploring languages with linear typing systems.

My current research interests lie in stochastic modeling of real world computational processes, particularly sequential processes such as human language or financial data, using tools from machine learning, statistics, and information theory. The types of problems I am interested in include:

• Statistical modeling of natural language for Human Language Technology applications, such as automatic speech recognition, machine translation, topic detection, document classification and routing, information retrieval and textual datamining.
• Stochastic modeling of financial data. I am currently directing the Computer Science component of CMU's multidisciplinary Computational Finance program.

I also have a strong interest in the future of human machine speech communication. I am convinced that, in the not too far future, we will routinely communicate by speech with appliances, gadgets, office equipment, information servers, robots, and machines of other kinds. Communication with such mechanical- or information-servants does not require the full strength of natural language, nor should it have to cope with its ambiguities. What then is the ideal form of human-machine speech communication? Will there develop a particular style, or grammar, for talking to machines? If so, can we help this process along by developing principles for it? I have recently embarked on a project to develop and test such principles.

The main focus of my research is in complexity theory and the foundations of cryptography. The wide applicability of the technical ideas in these two areas has allowed me to extend my work into learning theory, probability theory, and combinatorics.

I concern myself with the fundamental questions of each field: How can one obtain a separation result for interesting complexity classes? How can one reduce the security of a cryptographic protocol to the security of a simple primitive? What is a powerful inference method? How can one generalize probability theory to a theory where the events are almost independent?

I work most actively is the meta-theory of the above areas. This means questions like: What are the reducibilities among the above questions? What are the reducibilities among approaches to these questions? When are the perceived technical barriers to their answers related? When are they inherent?

I will mention two examples of these meta-theoretical results. Much of cryptography concerns the reduction of the security of complex protocols to the security of simpler ones. The most important question along these lines is whether a public-key cryptosystem can be based on a black-box, private-key system (such as the Clipper chip). Russell Impagliazzo and I showed that any proof of this particular reduction would contain inside it a proof that P

Curiously, current approaches to the P v.s. NP question are themselves disguised forms of a problem in cryptanalysis. In order to prove that a function f is not in a complexity class C, the standard approach is to exhibit some combinatorial property of the function that provably prevents it from being in the class C. Alexander Razborov and I have argued that all the known lower bound proofs in circuit complexity use what we call Natural combinatorial properties. Any proof that uses a Natural property and shows that some function is not contained in a complexity class C, can be transformed into a successful cryptographic attack against any private-key cryptosystem which is implementable in the class C. Thus, these proof techniques cannot apply to classes (plausibly P, NC^1, or even TC^0) that contain unbreakable cryptography. A corollary greatly extends my previous work with Len Berman by showing that the restriction methods, which were so successful in showing AC^0 lower bounds, are essentially useless in resolving frontier questions in circuit complexity. At this time it remains unclear if proof methods which avoid Natural properties exist. Razborov has shown that in a weak fragment of arithmetic all proof methods are Natural in our sense; it follows under a cryptographic assumption that P v.s. NP is independent of this fragment. I have extended the notion of Natural property to that of NP-Natural property. This generalization also extends Razborov's independence result to more general (but still quite weak) proof systems.

My interests are in speech communication, machine perception, and human perception. My major interest is in the application of principles derived from the study of human communication to the design of speech understanding systems. Current approaches to speech recognition have attempted to engineer solutions for specific recognition tasks. The results have been impressive in the context of these tasks, but have contributed little to our understanding of the broader problem of speech understanding. A potentially better strategy is to examine in detail the performance of a system that has already successfully implemented a solution to this problem---the human listener.

My current work centers on the design of interactive systems using speech. Although speech appears to be the most natural communication modality for humans, its effective use for human-machine communication is not well understood. We are currently working to extend our knowledge in the following areas:

• The development of a theory of language design for speech-based interactive systems: Speech-mode communication predisposes the user to make certain word choices and to exhibit certain grammatical preferences. An understanding of these leads to better language design for interactive systems.
• Understanding the role of speech in the computer interface: Speech is an effective means of communication, but it is not always suitable for all types of interaction. The design of a speech interface takes place in the context of a task, of other available modalities and user preferences. We can approach this problem in a systematic way by developing an analysis interface appropriateness.
• Design of an environment that allow the automatic configuration of a speech channel for an interactive task, given an abstract specification of its capabilities.
• The study of human correction of misunderstandings and misrecognitions: People use certain conventions to recover from breakdowns in communication. These conventions can be transformed into heuristics that allow a speech system to automatically recover from recognition errors and more generally assume its share of channel maintenance duties.

As an experimental computer scientist, my interests lie in the design, implementation and evaluation of computing systems. I am especially interested in the question: "How can we provide mobile users with reliable, efficient and safe access to shared information?"

One outcome of this work is the Coda File System. This distributed file system, a descendant of AFS, supports disconnected and weakly-connected operation as well as read-write server replication. This design provides high availability and allows users who are temporarily isolated from servers to continue work uninterrupted.

A different approach to mobile information access is being explored in Odyssey. Here, applications collaborate with the operating system in adapting to the changes induced by mobility. These changes include variation in network bandwidth, battery level, cache state and other system resources. Our most recent work in Odyssey explores the concepts of energy-aware adaptation and multi-fidelity algorithms.

My research is in two areas-program manipulation tools and information structures for collaboration. I focus here on the Fluid Architecture project, which is in the first of these areas and involves the use of program analysis and manipulation techniques to support program development and evolution. Please feel free to come talk to me about any of these ideas, or about my research in computer-supported cooperative work (which is not covered here).

All programmers face the difficulty of having to make small-scale structural design decisions very early in the software process, well before the consequences of those decisions can be understood. For example, having decided to include an integrity check for a parameter, should the check be done at the procedure being called or at all calling sites? Which site is selected (or whether code is replicated in order to have it both ways) determines which optimization opportunities can be exploited, and is best decided later in the process. And in practice, once these small structural commitments are made, particularly in the design of an API, they can be very difficult to revise. My research hypothesis is that this brittleness is not a necessary attribute of software, and that semantics-based program analysis and manipulation techniques can offer a way for programmers to retain structural flexibility.

Program manipulation techniques of the sort we are exploring can also be used to adjust data representations or make other changes that require potentially pervasive alterations to code. A simple representational change to Java strings, for example, requires simultaneous changes to more than 80 methods. Practicing programmers can devote considerable effort to this "bureaucratic" business of organizing and reorganizing internal interfaces and encapsulations, maintaining and revising representation and control invariants, and managing response to exceptional conditions. Most of the time they are working with existing code.

I am interested in program analysis and manipulation techniques that can be embodied in tools that programmers can use easily for routine program evolution of this sort. For such tools to be practical, programmers must not have to write extensive specifications of program functionality or architecture. Also, the tools must be interactive, enabling software engineers to explore a space of possible design approaches and to explore multiple structural views of a system. To this end, we have built experimental tools for analyzing and manipulating Java programs.

My work in logic has mainly been in the areas of model theory, automata, set theory, modal and intuitionistic logic, constructive mathematics, and connections between category theory and logic. Philosophical interests concern the foundations of logic, the philosophy of mathematics, and the semantical analysis of natural language. Work in computer science has been directed to the development of denotational semantics of programming languages and the mathematical foundations of a suitable theory of computability. Current projects aim at unifying the semantical approach with constructive logical formalisms to be able to give rigorous and machine-implementable proof methods and development tools for the "inferential" construction of correct programs. Very recent research with current graduate students aims at combining categories of domains with traditional categories of mathematical structures and studying the computability and type theory that results. Another recent strong interest is in using methods of symbolic mathematical computation (computer algebra).

Image-Based Modeling and Rendering.
A central problem in computer graphics is producing images that appear photographic, thereby fooling people into believing they are viewing a real scene. While rendering techniques have advanced dramatically in recent years, we are still far from this goal of photorealism, largely because of the difficulty of constructing realistic 3D models. We propose to solve this problem by "importing" real-world objects and scenes from photographs and paintings. Towards this end, we are developing two classes of techniques, based on image morphing and 3D reconstruction, respectively. The first approach rearranges pixels in a set of input images in order to produce images of the scene from different camera viewpoints. This view morphing approach enables effects such as rotating a person's head in 3D from one photograph. We are also investigating voxel-based 3D reconstruction techniques to solve larger-scale visualization problems, such as producing building walkthroughs and flybys of complex landscapes by processing images from video camcorders.

3D Augmented Video Editing.
Imagine trying to remove a moving figure from one video sequence and paste it into another. While simple to describe, this operation is extremely difficult to achieve because of the need to manually trace moving contours in in every frame of an image sequence. The goal of this project is to develop video editing tools that blend user-interaction with computer vision techniques in order to manipulate entire video sequences by touching only a small number of frames. In addition to cut-and-paste operations, we are interested in 2D Photoshop-style editing operations that propagate (e.g., applying lipstick to a moving face by painting it into a single frame) as well as 3D effects like changing camera viewpoint and illumination conditions.

URL: http://www.cs.cmu.edu/~seitz

Software now accounts for the the lion's share of the cost of developing and using computer systems. My research is directed at establishing a genuine engineering discipline to support the design and development of software systems. Currently I'm working on design methods, analytic techniques, and notations for building complete software systems out of subsystems and their constituent modules. This is the software architecture level of design, which makes me a software architect.

Software designers often describe the architectures of their systems by referring to common patterns such as "pipe and filter systems", "client-server systems", "layered systems", and "object-oriented systems". They use box-and-line diagrams to explain the system organizations. Most of these descriptions are highly idiosyncratic and ad hoc; nevertheless, the designers manage to communicate.

People talk about a world in which software systems are developed by taking components off the shelf and hooking them together, "just like Tinkertoys". In fact, though, software components interact in many different ways -- via procedure calls, pipes, signals, shared data, etc. So the situation is more like grabbing parts at random from a bathtub full of Tinkertoys, Lego blocks, Lincoln logs, Mechano parts, and so on -- then expecting them to fit together in some sensible way. (Actually, it's more like taking parts at random from a landfill, but that's a different story.)

The Vitruvius project is developing theories, notations, and design strategies to make good software designers' ad hoc knowledge visible, precise, and subject to analysis. An initial prototype, UniCon, can describe a range of systems that rely on a variety of component interaction strategies. It can create wrappers to convert code to support certain kinds of interactions. We have recently reorganized it to simplify adding new connectors.

Organizing informal design guidance into well-grounded theories brings us closer to an engineering discipline for software. We follow a strategy of progressive codification -- we begin by capturing informal knowledge as carefully as possible, then make the descriptions more formal as we come to understand it better.

We want to be able to propose architectures for software in terms that other software engineers found comprehensible; we want to compare software organizations on an analytic basis; we want to convey knowledge of software structures more effectively to a maintainer or developer. In short, we could reuse knowledge of software organizations and particular software artifacts in reasonable ways.

Examples of research questions that interest me include:

• Notations and tools for software architecture: Identify or develop notations that are appropriate for describing system construction from components. What are the primitive elements and operations? What are the useful abstractions? What is the analog of the abstract-data-type abstraction function, which demonstrates that a component implements the interface abstraction it specifies?
• Taxonomy of styles and elements: Develop classifications of architectural styles and of the components and connectors that are used to create systems in these styles. Find ways to identify components that are used in mismatched ways and to correct the mismatch if possible.
• Consistency of views: When multiple different views (e.g., data flow and state transitions) are used in a design, how do you check their consistency?
• Interoperability: Architectural definitions may specify incompatible combinations of components. For example, the unix sort filter computes "the same" thing as the system call, but the two are not interchangeable. Check the definitions for consistency (under whatever specifications are provided). When inconsistencies are found, reconcile them if possible or report detailed nature of mismatch.
• Design guidance: Organize information about a class of systems to help the software developer make design decisions. Usually there are multiple architectural alternatives; how do you choose among them? How does information about the application you're constructing influence the design decisions?
• Partial, incremental specifications: Conventional doctrine says that specifications are fixed, complete, and homogeneous -- they capture everything there is to know about a component. In fact, however, they are intrinsically incomplete: you can't anticipate every property another component might depend on. They are incremental: as you learn more about a component, you must capture it. And they are heterogeneous: different properties require different notations. How do notations and tools have to change to cope with the difference between doctrine and reality?
• Establish analysis techniques: Identify properties such as system throughput that are appropriately specified and analyzed at the architectural level rather than the individual-component level. How do you specify and analyze them? How do you derive specifications for individual components that guarantee the system properties?
• Evaluate usability: Determine how useful the prototype system is for software designers.

My major interest is in the modular design and rapid prototyping of reliable computing structures. Three research projects support this interest: Mobile/Wearable Computers, Concurrent Design, and Reliable Systems.

Mobile/Wearable Computers.
The information processing industry is undergoing a paradigm shift. In the 1960's information processing was concentrated in mainframe computers operated by central staff and accessed by custom-built programs executed in batch mode. By 1970 the invention of the time-sharing operating system allowed users to interact with information on-line. However, time-sharing systems were still centrally based with most of the computing cycles devoted to information manipulation rather than the human computer interface. With the advent of the personal computer in the early 1980's a substantial portion of the computing power could be dedicated to the single user. In the 1990's wearable computers allow mobile users to remotely access information and collaborate with exerts. We have built twenty wearable computer systems in such diverse areas as heavy vehicle maintenance, aircraft manufacturing, plant operations, language translation, and medical monitoring. Example systems can be found on www.cs.cmu.edu/~wearable. Systems involve hardware architecture, software architecture, wireless communications, ergonomic design, and human computer interaction. Research is in cooperation with the Design Department, Electrical and Computer Engineering, and the Human Computer Interaction Institute

Concurrent Design.
The goal of the project is to support the generation of designs from high level systems specifications into completely assembled electronics, mechanical, and software systems. The goal is to reduce design time by 1 to 2 orders of magnitude. The Concurrent Design methodology has been used in all twenty generations of mobile computers described above. Groups of up to 30 designers representing up to five disciplines designed and fabricated multiple copies in less than four months, and developed tools to support the concurrent design process. For all levels of design there are common issues that must be addressed including design data bases, design information representation, human-computer interfaces, simulation/validation/ verification, automatic synthesis, test generation, and design selection criteria.

Reliable Systems.
For over two decades, computer system design and evaluation has been based upon performance benchmarks. Comparable benchmarks do not exist for evaluating the quality and robustness of computer hardware/software systems. This project is developing a family of portable benchmarks for a variety of operating systems and programming language environments. The benchmarks are based upon over a decade of experimentation with fault injection including the next generation air traffic control system. Information can be found on www.ices.cmu.edu/ballista.

Another goal of the project is to develop technology to enable the construction of reliable systems from commercial-off-the-shelf (COTS) hardware and software. One approach is to add middleware between the applications software and the operating system. Sentries can perform error detection, data logging, and automatic retry, all transparent to the application software. Studies indicate that the majority of system downtime is due to human errors in either design or operation. This project also explores the design of software systems and interfaces to reduce human errors. Other research issues include automatic generation of assertion checks, checkpointing/rollback, and redundancy through replication. Research is in cooperation with Roy Maxion and Phil Koopman.

My research interests focus on artificial intelligence, primarily in the areas of highly autonomous systems (especially mobile robots) operating in rich, uncertain environments. This necessitates robots that can plan, effectively reason about uncertainty, diagnose and recover from unanticipated errors, and reason about their limitations. In particular, I am interested in architectures for autonomy that combine deliberative and reactive behavior, probabilistic and symbolic planning, and reliable execution monitoring and error recovery. The goal is to create intelligent systems that can operate autonomously for long periods of time in unstructured, natural environments.

Highly Autonomous Systems.
We are investigating methods for making mobile robots more robust and self-reliant. We are exploring the use of model-based reasoning techniques to detect and diagnose failures, hierarchies of monitors and exception handlers to catch unanticipated situations, and learning of new monitors and exception handlers from experience. The research incorporates symbolic (model-based) reasoning, probabilistic reasoning, interleaving of planning and execution and selective monitoring of relevant environmental features. We are also investigating social interaction between robots and humans, and reliably completing complex tasks (fax delivery, exploration). Testbeds include Xavier and Amelia (office-delivery robots), Nomad (Antarctic exploration rover), and NASA's next Mars Rover.

Architectures for Autonomy.
We have developed the general-purpose Task Control Architecture (TCA) to support distributed planning, execution, error recovery, and task management for autonomous systems. TCA has been used in over a dozen mobile robot projects at CMU and elsewhere. Current research is developing the Task Description Language (TDL), an extension of C++ that includes syntax to support task-level control, and is investigating using formal models to verify robot control systems. To date, we have developed tools for visualizing message traffic, task decomposition, and plan execution. Testbeds include Xavier (indoor mobile robot) and autonomous interplanetary spacecraft (NASA).

Multi-Robot Coordination.
We are researching issues of how multiple, heterogeneous robots can cooperate to carry out high-level tasks. Issues include having the robots negotiate which tasks they will achieve, and when, monitoring each other's performance, and adapting dynamically to changing situations. Testbeds include the Mercator project (urban exploration robots) and multi-robot assembly and construction.

Probabilistic Planning and Reasoning.
We are exploring advanced planning and reasoning techniques, many of which involve probabilistic reasoning. In particular, we are exploring issues of determining when to plan and when to act, in order to optimize the total time spent solving problems, and using partially observable Markov models to navigate robots in office environments.

I am interested in AI, especially the use of computers to simulate human thinking, discovery, and learning processes. At present, most of my research effort is directed to four areas.

Programs that Discover Scientific Laws.
During the past decade, I have been engaged with colleagues in studying the psychological processes that are involved in original scientific work, and in building computer programs that simulate the processes of scientific discovery. In 1987, MIT Press published Scientific Discovery, describing the first products of that work, including BACON, GLAUBER, STAHL, BLACK, and DALTON. Most of the work already completed has been concerned with discovery achieved inductively from data, but including the invention of new concepts and including some search guidance from prior theories. The systems are capable of rediscovering a considerable number of scientific laws and concepts of first magnitude.

Now the work is moving on to other aspects of scientific discovery, especially the processes that guide an experimental program and the design of experiments and the processes that develop and adapt appropriate problem representations. Work with Deepak Kulkarni has produced a computer program that simulates Hans Krebs' course of discovery of urea synthesis in living tissue. Work on representations, and especially diagrammatic or pictorial representations, is continuing. Wei-min Shen modeled a system capable of discovering hidden variables (variables not directly observable) to explain the behavior of a complex system (e.g. Mendelian genetics). Raul Valdes-Perez built a program for elucidating the paths of chemical reactions. Eugene Fink is working on the theory of representation change.

Modelling Expert and Novice Skills.
In collaboration with colleagues and students, I have been studying the behavior of novices and experts in various problem domains, especially physics and economics. The aim is to simulate novice and expert behavior, and use these programs to guide the construction of learning programs that will turn a novice into an expert. These explorations are leading to interesting discoveries about the role of representations in problem solving, and we plan to extend them to a broader range of domains, such as chemistry and molecular biology.

Learning Programs.
Adaptive production systems learn by solving problems by trial and error, then learn more powerful techniques from their experience; or they learn by analyzing worked-out examples of problem solutions. These are very powerful techniques and the surface has just been scratched. There are obvious possibilities of application to automatic programming. The results of earlier research (the dissertation of David Neves) have been applied to the construction of an algebra and geometry curriculum for human students that enables them to learn the subject from worked-out examples and problems, without lectures or textbooks. The curriculum is now being used successfully in a number of schools in China. This work has many implications for tutorial systems and computer-aided instruction, which I shall begin to explore.

An important issue is the distinction between a program that learns by rote and a program that learns with understanding, and the implications of this distinction for retention of what is learned and the ability to transfer learned skills to new tasks.

Diagrammatic Representations and Imagery.
The use of diagrams or other kinds of pictorial displays greatly facilitates problem solving in many domains. In the light of this fact, we have been exploring the function of diagrams in problem solving and the kinds of computer representations that will reap the same computational advantages that paper-and-pencil diagrams or CRT displays provide for humans. Programs have been constructed that demonstrate the value of diagrams in specific domains (e.g., pulley problems in physics, geometry theorems). Most recently we have been investigating how diagrams facilitate understanding of special relativity and of economics, and have built a simulation of the "Mind's Eye" and its processes for interpreting diagrams. We intend to develop the work in several directions: first, to examine a much wider range of examples of the use of diagrams; second, to explore the implications for computer graphics; third, to investigate how new representations, diagrammatic or other, can be generated; and fourth, to study the relation between diagrammatic and propositional representations.

I have worked in a variety of different areas of computer science, including amortized analysis of algorithms, self-adjusting data structures, competitive algorithms, natural language parsing, computer game playing, synthesis of musical sounds, and persistent data structures.

Natural Language:
I (jointly with coauthor Davy Temperley) wrote a parser for English. The system (which we call a link grammar) is unlike phrase structure parsing or context free parsing. The scheme is elegant and simple, and our grammar captures a very wide variety of complex phenomena in English. We (John Lafferty and I) plan to use this as a basis for a new statistical model of language. This work on language is described in two technical reports: CMU-CS-91-196, CMU-CS-92-181.

Competitive Algorithms:
Consider the idealized problem of deciding whether to rent or buy skis. You're about to go skiing. The cost of renting skis is $20, the cost of buying them is $400. Clearly if you knew that you were going to go skiing more than twenty times, then you could save money by immediately buying skis. If you knew that you would go skiing fewer than twenty times, the it would be prudent to always rent skis. However, suppose that you can not predict the future at all, that is, you never know until after one ski trip ends if you will ever go skiing again. What strategy would you use for deciding whether to rent or buy skis? Your goal is to minimize the ratio of the cost that you incur to the cost you would incur if you could predict the future. (Hint: you can come within a factor of two.)

Since the simple principle behind this example turns out to be very useful we have given it a name. A competitive algorithm is an on-line algorithm (it must process a sequence of requests, and it must process each request in the sequence immediately, without knowing what the future requests will be), whose performance is within a small constant factor of the performance of the optimal off-line algorithm for any sequence of requests. (In the skiing example, there is only one type of request, and the only uncertainty is in knowing how long the request sequence will be.)

My collaborators and I have discovered a surprising variety of practical problems for which there exist very efficient competitive algorithms. We have also developed a partial theory of competitive algorithms. However there remain many interesting open problems, from discovering competitive algorithms for specific problems, to answering general questions about when such algorithms exist.

Data Structures:
Data structure problems are typically formulated in terms of what types of operations on the data are required, and how fast these operations should take place. A worst-case analysis of the performance of a data structure is a bound on the performance of any operation. An amortized analysis of a data structure bounds the performance of the structure on a sequence of operations, rather than a single operation. It turns out that by only requiring amortized efficiency (rather than worst-case), a variety of new and elegant solutions to old data structure design problems become possible. My collaborators and I have devised a number of such solutions (splay trees, skew heaps, fibonacci heaps, self-adjusting lists, persistent data structures, etc.), and I continue to have a strong interest in data structures and amortized analysis.

Interactive Network Games:
I wrote and maintain the internet chess server. This very popular service allows people from all over the world to play chess, observe others playing, and communicate with each other in various ways. A rating is computed for each player as a function of his or her performance. You can try it yourself with "telnet ics.uoknor.edu 5000".

My research interests are in the areas of computer networking and distributed systems. I am specifically interested in developing techniques that make networks significantly more useful to applications. While some improvements in network technology do not depend on how the network is used (e.g. incremental improvements in link bandwidth), many optimizations depend on the application's communication behavior. For example, some optimizations exploit properties of application traffic (e.g. inherent bandwidth limits of multimedia traffic, temporal locality in traffic destinations). A more extreme example is network features that address specific application needs (e.g. quality of service, application-level congestion avoidance), and that require the network and application to explicitly collaborate to improve performance. As a result, my research often involves collaboration with network users, allowing me to better understand their problems and to evaluate results. This type of collaboration is becoming more important as applications use the network more aggressively.

Improvements in application-level network performance come in many forms and benefit a wide range of applications. Examples include increasing throughput and reducing latency (e.g. for distributed high-performance computing applications), making network performance more predictable (e.g. for multimedia applications), optimizations across multiple "cooperating" traffic streams (e.g. in video conferencing or parallel file systems), information exchange between the network and the application (e.g. in support of network-aware applications), and quality of service guarantees (e.g. for high quality electronic services). Because of the wide diversity of network optimizations, my research touches on many areas of computer science. For example, optimizing throughput requires optimizations in the architecture, operating system, and protocol implementation of the sending and the receiving computer systems. Supporting a new quality of service class, on the other hand, requires the development of new protocols and resource management algorithms.

In the last 10 years, I have worked on several high-performance networking projects that focused on dramatically increasing the throughput and reducing the latency between workstations and PCs. These projects include Nectar, the first "network of workstations" built around a high-speed switch-based local area network, Gigabit Nectar, a metropolitan area network that allowed workstations and supercomputers to communicate at 100s of Mbit/second using standard communication protocols (TCP/IP), and Credit Net, an OC-12 (622 Mbit/second) ATM network that supports a variety of protocols for traffic management. These projects used a variety of techniques such as data copy avoidance, hardware checksumming, application device access, and protocol specialization to optimize communication performance. All three networks were used extensively by applications in diverse areas such as environmental modeling, remote medical consulting, engineering design, circuit simulation, and medical image processing.

I am currently working on the Darwin project. The goal of Darwin is to define, implement and evaluate "application-aware" resource management mechanisms for networks. The idea is that given the wide diversity in network applications, networks will have to be able to support quality of service models that can be customized by applications. This is achieved by letting the application participate in resource management, so that network resources are applied in a way that is most effective for the application. Application-awareness is a very general technique that will have an impact on many areas of networking. For example, it can form the basis for sophisticated quality of service models for multiparty interactive applications. Other problems to which application-awareness can be applied include the generation of feedback for network-aware applications (e.g. for multimedia data streaming) or to support dynamic short-term reservations. I am also involved in the Remulac project, which is developing middleware in support of network-area applications, and we are starting a new project on Active Network Services in the Fall of 1999.

My research interests involve a number of topics joined by the common threads of signal processing, sound, and acoustics. At present I am most actively working on topics related to automatic speech recognition and signal processing in the auditory system. I have also been involved in projects in the areas of biomedical instrumentation, particularly with regard to the auditory system, physical acoustics, computer music, and computer-aided instructional systems.

Automatic Speech Recognition.
The SCS speech group is developing speech technology that can perform unlimited-vocabulary speech recognition on a speaker-independent basis under difficult acoustical conditions. We are also developing practical applications that make use of spoken language interfaces to perform useful tasks.

The major goal of my own work speech research is to enable CMU's SPHINX recognition system to become as robust to changes in acoustical environment and ambience as it is to changes in speaker. In particular, we must deal with problems in recognition accuracy resulting from additive noise sources, background music, competing talkers, change of microphone, and room reverberation. We are developing several different types of solutions for these problems including improved noise cancellation and speech normalization methods, the use of representations of the speech waveform that are based on the processing of sounds by the human auditory system, and the use of arrays of microphones to improve signal-to-noise ratio. In previous knowledge-based speech-recognition systems I had also worked on statistical classification, speaker adaptation, and the integration of syntactic, grammatic, and semantic information.

Signal Processing in the Auditory System.
The general goal of this research has been to develop a better understanding of how the auditory system processes sound, to apply this knowledge to the treatment of various kinds of hearing impairments, and to apply this knowledge to the development of more robust speech recognition systems. I am presently carrying out psychoacoustical measurements of various aspects of monaural and binaural perception, and developing models based on communications theory and linear system theory to relate the results of these experiments to neural coding of sounds by the auditory system. Most of my work in hearing has been concerned with the localization of sound and other aspects of binaural perception.

I am interested in AI, machine learning, artificial neural networks and robotics.

Machine Learning.
A primary goal of my research in machine learning is to contribute to the development of learning algorithms applicable to complex real-world tasks, particularly when training data is expensive to obtain. Despite the enormous complexity of the "real world," humans often generalize strikingly well even after having seen as few as a single training example--a capability currently unmatched by computers. My research on lifelong learning assumes that a learner encounters a whole collection of learning tasks over its entire lifetime. When learning a new task, a lifelong learning algorithm may re-use what has been learned in previous learning tasks. Key questions that arise in the context of lifelong learning are how to learn, represent, and transfer general-purpose domain knowledge across related learning tasks. In my recent PhD thesis I have developed several approaches that can accumulate and transfer domain knowledge, hence generalize better from less training data.

Robotics.
My core interest in robotics is robot learning. For robots to be truly autonomous, they must have the ability to adapt to unforeseen situations, and to improve with experience. In the past, I have applied various learning techniques to mobile robot perception and control. I am currently designing a unified robot learning architecture, and to explore principal ways for robots to interact with humans more naturally.

My current research activities are in the area of computational neuroscience and robot learning.

Neural Models of Animal Navigation.
How do animals represent space in their brains? In rats, ``place cells'' in the hippocampus fire when the rat is in a particular location. The firing fields of place cells are controlled by distal landmarks (e.g., they rotate when the landmarks are rotated), but they also persist (and the animal can navigate effectively) when the lights are turned out. Elsewhere in the brain, head direction cells in thalamus and postsubiculum fire selectively when the animal faces in a particular direction, and place fields have recently been shown to drift in synchrony with the head direction system. In addition, there is evidence that rodents perform path integration, combining vestibular cues and motor feedback to generate a running estimate of their coordinates in some reference frame. Using data from a variety of animal behavioral studies, my students and I are developing a neural network model to replicate the navigational properties of rodents. The goal is to have a single, unified architecture that deals with a broad range of navigation phenomena, including open-field tasks, proximal landmark-based tasks, and radial arm and Hampton Court type mazes. With this work we hope to shed light on the algorithms rodents are using, and the roles the hippocampus and other brain areas play in navigation. In addition, we are collaborating with Bill Skaggs of the Department of Neuroscience, University of Pittsburgh, on neurophysiological investigations of the hippocampal and head direction systems.

Robot Learning by Operant Conditioning.
Animals can be taught to perform complex tasks by a conditioning technique that reinforces desired behavior with a reward. This is how animal performers are trained, and seeing eye dogs as well. Through a process called shaping, complex behaviors can be built up gradually by shifting the reward policy as the animal progresses in learning the task. With the right learning algorithm, this training procedure should also be applicable to robots. Some students and I are exploring this idea and implementing our operant conditioning learning algorithm on Amelia. Current thinking in cognitive neuroscience is that there are several different memory systems involved in learning, e.g., hippocampus, amygdala, and striatum. By building a working model of operant learning, we hope to better understand the implications of this theory.

One measure of the fundamental character of a scientific problem is the interest it attracts outside the discipline. A fundamental CS question of wide interest is: what can computers ultimately do? On the research frontier is the question of whether high-end tasks of human creativity can be automated. My main interest is creative discovery in science and related areas.

Together with a variety of collaborators in CS and natural and social science disciplines, we focus on developing algorithms to partially automate high-end reasoning tasks that lead to the discovery of new scientific knowledge. We also spin off practical interactive software to enhance the work of researchers by making conclusions faster and more reliably. Research on computational scientific discovery enjoys the benefits of simultaneously being on frontiers of AI research and of being close to practical application in academic science and science-based industry.

Some current or recent projects include (1) elucidating reaction mechanisms in chemistry; (2) detecting subtle spatio-temporal patterns in biological imaging; (3) analyzing kinship terminologies in anthropological linguistics; (4) inferring particle models in high-energy physics. Also, we have recently developed very general methods for typological reasoning and are currently applying them to diverse fields.

Our main working hypothesis is that there are strongly generic elements present in scientific reasoning across the disciplines. This is obvious for highly mathematical tasks, but is less evident for the qualitative and symbolic inference that underly model building, pattern detection, and others.

My research area is Artificial Intelligence (AI). My current main research interest is the integration of machine learning with other areas of AI, in particular with problem solving/planning and with machine vision.

I have been working for several years in the Prodigy research project (see also Carbonell). Prodigy is a testbed for research in problem solving, planning and learning. I have studied different methods to learn control knowledge to improve the performance of a domain-independent problem solver. I developed learning algorithms for the integration of analogical/case-based reasoning and inductive explanation-based learning with general-purpose planning. I view the strategy-level learning process as the automation of the complete cycle of efficiently constructing, storing, retrieving, and flexibly reusing problem solving experience.

Towards this goal of improving planning performance from experience, we recently showed empirical evidence that there is no universally best domain-independent problem solving strategy. Therefore, I am currently interested in investigating new learning algorithms that integrate analytical, inductive, and experimental techniques to learn the correspondence between particular domain characteristics and specific search heuristics for planning effectively in complex domains.

My long term research goal is to bring AI systems and algorithms to a level that makes them applicable to real-world problems. To reach this goal, I have been expanding my work towards the integration of planning, execution, and learning in real robotics and information- processing agents. I am interested in combining multiple collaborative and adversarial reasoning agents in dynamic changing environments.

Furthermore, I have been investigating strategies in which the fields of perception, such as machine vision, and machine learning are combined to address jointly high-level and low-level real-world reasoning tasks. I aim at the development of autonomous agents capable of perceiving their surroundings through sensors, and improving their perception and problem solving ability through experience. I have recently started a new project for the integration of machine vision and machine learning. The goal of this project is to develop a new architecture where learning provides a flexible framework for the efficient recognition of everyday objects in in-door and out-door scenes. The architecture is currently based on a technique for learning object recognition algorithms by genetic programming where the image signals are used directly as a training and testing input. There is no built-in commitment to the manner in which the algorithms examine the images and the learning system evolves the algorithms to increase their decision-making fitness. The architecture has shown promising results in a challenging object recognition problem.

My research interests are in information retrieval systems, multimedia, speech/image/natural language understanding and distributed systems. My emphasis has been in multidisciplinary projects which led to my current large project, The Informedia Digital Video Library, which integrates several CS areas from AI to systems.

The Informedia Digital Video Library.
Vast digital libraries of video content are becoming available on the "Information Superhighway" as a result of emerging and converging technologies for audio and video analysis and distribution. The Informedia project is developing new technologies for video analysis, storage, search, and retrieval of image and audio content and embedding them in a distributed library system for use in education, training, sports and entertainment. The system uses intelligent, automatic mechanisms that provide full-content search and retrieval from an extremely large (scaling to several thousand hours) online digital video library. We are developing automated systems that populate the library and support access via the Internet. Our approach uses combined speech, language and image understanding technology to transcribe, segment and index the linear video. Complementary techniques are applied to accomplish intelligent search and selective retrieval. Innovations include rapid retrieval of "video paragraphs" which satisfy an arbitrary subject query and "video skimming", which enables an accelerated viewing of the key video and audio sequences without the perceptual disturbance of simply speeding up the frame rate and audio.

The research involves the application of diverse technologies and disciplines to a single focused application. The system builds on existing technologies and extends with focused research:

• Speech understanding for automatically derived transcripts and spoken queries
• Image understanding for video "paragraphing" (segmentation) and similarity matching
• Natural language for processing transcripts and queries
• HCI for creating novel user interfaces for video display, manipulation and reuse
• Network authentication and billing for controlled access
• Data architectures for network retrieval-on-demand
• User studies for validation and assessment

My research interests center around the interpretation and integration of speech, language and other human communication signals in the design of human-computer and human-human communication systems. Two particularly challenging examples of these interests are the JANUS project, a speech-to-speech translation system, that provides translation of spoken language between English, German, Spanish, Japanese, Korean (e.g., a translating telephone). Another, the INTERACT project, attempts to design multimodal interfaces, that incorporate not only speech, but also other communication modalities, such as gesture, lipreading, handwritten character recognition, face- and eye-tracking, in order to derive a robust understanding of user intent.

The JANUS project has provided one of the earliest demonstrations showing that speech-to-speech translation is possible. I am now working on extending the system's toward high quality translation of unlimited spontaneously spoken and ins eom cases conversational human speech. This involves new inroads in robust understanding of spoken language, improved speech recognition methods, ways to automatically learn language as well as interactive and/or mobile ways of deploying such a system to meet natural multi-lingual communication needs. We are also extending JANUS to accept and produce additional languages flexibly.

The INTERACT project is aimed at enhancing human-computer communication to include other communication modalities known to be helpful in human communicative situations, such as observing where a person might be looking or focusing attention, decoding his/her handwriting, gesturing and pointing in conjunction with speech, observing lip movement to enhance recognition of speech, etc. Several real-life human-computer interaction applications are explored to see how these modalities can be usefully captured to make them a natural and reliable part of any human-computer or communication interface. In an effort to achieving these practical goals, computer systems must be able to learn and adapt to a changing environment and growing demands of a user. I am interested in various machine learning and modeling strategies to develop learning and adaptation. I am interested in CONNECTIONIST and STATISTICAL LEARNING and ADAPTATION strategies, particularly as applied to speech, language, visual and interactive signal processing. I am collaborating with other faculty to develop and enhance learning algorithms, that have the required properties for deployment in the real world.

My general research interests lie in distributed systems, programming languages, and software engineering. I especially enjoy integrating approaches from these different areas and applying results from more theoretical work on languages to practical problems found in real systems. A long-term goal that drives my research is to provide, where appropriate, as rigorous as possible a foundation to the design and implementation of software. My specific interest is the application of formal specification and analysis techniques to reason about complex software systems.

My current research interests are in security. In this context, my colleagues and I have been exploring different aspects of secure systems:

• Survivable Systems: We are using hybrid mathematical models and a suite of analysis tools to reason about faults and security vulnerabilities in interdependent systems.
• Authentication Protocols: We have applied a novel, fully automatic, "lightweight" technique called theory generation to reason about authentication protocols and simple electronic commerce protocols.
• Secure Auction Service: We are pursuing the combination of theorem proving and model checking to reason compositionally about a secure electronic auction protocol.

My past research projects include:

1. Larch, a family of specification languages noted for its two-tiered approach to specifying program modules;
2. Miro, a visual specification language for specifying file system security constraints;
3. Avalon, extensions to C++ and CommonLisp to support distributed transactions;
4. Venari, extensions to Standard ML to support concurrent multi-threaded transactions; and signature and specification matching of software components.
5. TinkerTeach, software infrastructure for electronic delivery of courseware, but best known for providing the TOM conversion service which is in heavy daily use worldwide.

My research has centered on the statistical learning approaches to automated text categorization, document clustering, cross-language information retrieval, novel event discovery from chronologically ordered data, and intelligent search in Internet/Web environments. Research contributions include a novel method using multi-variate regression ("the Linear Least Squares Fit Mapping) to solve high dimensional classification and cross-language retrieval problems, the development of several text categorization systems that improve the state-of-the-art in both accuracy and scaling, and the evaluation methodology regarding text learning.

Selected Publications:

Y. Yang. An evaluation of statistical approaches to text categorization. Journal of Information Retrieval, Vol. 1, pp69-90, 1999.

Y. Yang and J.G. Carbonell and R. Brown and Thomas Pierce and Brian T. Archibald and Xin Liu. Learning approaches for detecting and tracking news events. IEEE Intelligent Systems: Special Issue on Applications of Intelligent Information Retrieval, Vol. 14(4), pp.32-43,July/August 1999.

Y. Yang and J.G. Carbonell and R. Brown and R.E. Frederking. Translingual information retrieval: learning from bilingual corpora. Artificial Intelligence Journal, Special Issue: Best of IJCAI-97, vol. 103, pp323--345, 1998.

Yang, Y. and C.G. Chute. 1994. An example-based mapping method for text classification and retrieval. Proceedings of the ACM Transactions on Information Systems (TOIS'94); 12(3): 252-77.

My research interests lie in Internet, distributed systems, and multimedia systems. My work involves both designing practical algorithms with sound theoretical foundations and building prototype systems in real life environments. For the last 10 years, I have been studying QoS management and traffic control algorithms for the Internet. My research includes packet scheduling, traffic characterization, admission control. Recently, I have also been working on architecture and algorithms for implementing active value-added distributed services over the Internet, and customizable resource management algorithms for future services-oriented networks. More details can be found at http://www.cs.cmu.edu/~hzhang.

Abstraction (cf. Type Theory): Garlan, Shaw, Wing
Adaptive systems: Goldstein, Maxion
Algol-like languages: Reynolds
Algorithms: Blelloch, Blum, Bryant, Lafferty, G. Miller, Rudich, Sleator
Algorithms, approximation: Blum
Algorithms, distributed: Harchol-Balter, Johnson, Rudich
Algorithms, graph: Blum, G. Miller
Algorithms, learning: Blum, Carbonell, Fahlman, Lafferty, McClelland
Algorithms, on-line: Blum
Algorithms, parallel: Blelloch, Maggs, G. Miller
Algorithms, robot: Erdmann
Analogical reasoning: Carbonell, Mitchell, Veloso
Animation:: Heckbert
Application-aware networks: Zhang
Application-specific computing systems: Garlan
ATM networks: Steenkiste
Auditory modeling: Stern
Automated theorem proving: Clarke, Pfenning, Scott, Wing
Automatic compiler generation: P. Lee
Automatic grammar generation: Lafferty, Waibel
Automatic parallelization: Goldstein, Gross
Automatic programming: See Program Synthesis.
Automatic Presentation Design: Roth
Automatic speech understanding: Rosenfeld, Waibel
Autonomous mobile robots: Kanade, Simmons
Autonomous land vehicles: Simmons
Autonomous spacecraft: Simmons
Autonomous systems: Kanade

Biology, computational: Valdes-Perez

Causal reasoning: Carbonell, Maxion
Character recognition: Waibel
Code generation and optimization: Gross
Cognitive architecture: Carbonell, John, Lehman
Cognitive modelling: Carbonell, John, Lehman, Maxion, Plaut
Cognitive science: Carbonell, John, Koedinger, Lehman, McClelland, Maxion, Plaut
Combinatorics: G. Miller, Rudich, Sleator
Compilers: Blelloch, Gibson, Goldstein, Gross, Harper, P. Lee, Steenkiste
Complexity theory: Rudich
Computation theory: Brookes, Clarke, Lafferty, G. Miller, Rudich, Scott
Computational finance: Rosenfeld
Computational group theory: Lafferty
Computational linguistics: Carbonell, Hauptmann, Lafferty, Lehman, McClelland, Plaut, Rosenfeld, Rudnicky, Scott, Waibel
Computational science: Valdes-Perez
Computer-aided design: Bryant, Clarke, Garlan, John, Siewiorek
Computer-aided instruction: Christel, Pfenning
Computer architecture: Blelloch, Ganger, Gibson, Goldstein, Gross, Siewiorek, Steenkiste, Wactlar
Concept formation: Carbonell, Maxion, Mitchell
Concurrency, semantics of: Brookes, Clarke, Wing
Concurrent systems: Wing
Connectionist networks: See Neural nets.
Constraint logic programming: Pfenning
Constructive mathematics: Harper, Pfenning, Scott
Control theory: Moore
Cooperative computation: Touretzky
Cooperating robots: Erdmann
Cryptanalysis: Rudich
Cryptography: Rudich

Data fusion: Cochran

Data mining: Carbonell, Mitchell, Moore
Data structures: Sleator
Databases (cf. Information retrieval): Gibson, Satyanarayanan
Data types: See Abstraction, see Type Theory.
Debugging: Gross, Johnson
Dependability: See Reliability.
Design automation: See Computer-aided design.
Diagnosis and diagnostic reasoning: Maxion
Dialog: Rudnicky
Digital cartography: Cochran, McKeown
Digital video: Christel, Wactlar
Discourse modelling: Lehman
Discovery, scientific: Maxion, Mitchell, Simon, Valdes-Perez
Distributed computing: Gibson, Goldstein, Harchol-Balter, Johnson, O'Hallaron, Steenkiste
Distributed file systems: Ganger, Gibson, Satyanarayanan
Distributed systems: Clarke, Dannenberg, Ganger, Gibson, Harchol-Balter, Johnson, Maxion, O'Hallaron, Satyanarayanan, Steenkiste, Wing

Education, computer science: Brookes, Pfenning, Shaw
Educational technology: Christel, Dannenberg, Wing
Electronic commerce: Shamos
Emergent computation: Maxion
Experimentation: Carbonell, Gibson, Harchol-Balter, Johnson, Maxion, Mitchell, Satyanarayanan
Expert systems: See Knowledge-based systems.
Explanation: Mitchell, Roth
Eye-tracking: Waibel

Face tracking: Waibel
Fault tolerance: See Reliability.
File systems: Ganger.
File usage properties: Ganger, Gibson, Satyanarayanan
Formal methods: Garlan, Wing
Formal methods in AI: Garlan, Mitchell, Touretzky
Forsythe: Reynolds
Foundations of mathematics: Harper, Scott
Functional programming: Blelloch, Harper, P. Lee, Pfenning, Reynolds, Scott

Game-playing, computer: Rudich, Sleator
Game theory: Moore
Geometric modeling: Heckbert
Gesture recognition: Waibel
Graceful Degredation: McClelland
Graphics: Cochran, Heckbert, McKeown, Pausch, Roth

Hand-eye systems: Mitchell
Heuristic Search: Moore
Higher-order logic: See Type theory.
Human-computer interaction: Christel, Dannenberg, John, Koedinger, Maxion, Olsen, Pausch, Rosenfeld, Roth, Rudnicky, Shaw, Waibel
Human factors: Hauptmann, John, Maxion, Pausch, Rosenfeld, Rudnicky, Waibel
Human language technology: Rosenfeld, Waibel
Human machine speech communication: Rosenfeld
Hypercode: Fahlman

Image processing: Heckbert
Image understanding: See Vision.
Industrial computing: Rajkumar
Inferential programming: Scott
Information retrieval: Carbonell, Mitchell, Scott, Wing, Yang
Information systems: Wactlar
Input/Output: Ganger, Gibson
Integrated-services networks: Harchol-Balter, Zhang
Intelligent architectures: Carbonell, John, Lehman, Mitchell, Simmons
Intelligent interfaces: Roth
Intelligent tutoring systems: Dannenberg
Interactive graphic programming: Pausch
Interfaces, Human-computer: Carbonell, Christel, Dannenberg, John, Maxion, Pausch, Reddy, Rosenfeld, Rudnicky, Scott, Shaw, Waibel
Internet: Ganger, Harchol-Balter, Johnson, Zhang
Interprocess communication: Blelloch, Goldstein, Gross, Johnson

Knowledge acquisition: Carbonell, Cochran, Lehman, Maxion, McKeown, Mitchell
Knowledge-based systems: Carbonell, John, Lehman, McKeown, Mitchell, Valdes-Perez
Knowledge representation: Carbonell, Fahlman, Mitchell, Scott, Touretzky

Lambda calculus: Harper, Pfenning, Scott
Language acquisition: Lehman, Waibel
Language design: Fahlman, Shaw
Language implementation: Blelloch, Fahlman, Harper, P. Lee
Language modelling: Carbonell, Lafferty, Rosenfeld
Learning theory: Blum, Lafferty, Rudich
Library: Christel, Wactlar
Linear algebra, computational: G. Miller
Linguistics: See Computational Linguistics.
Lipreading: Waibel
Lisp: Clarke, Fahlman, Touretzky
Logic: Brookes, Harper, Pfenning, Scott
Logical frameworks: Harper, Pfenning
Logics of programs: Brookes, Clarke, Harper, Pfenning, Scott

Machine learning: Carbonell, Fahlman, Lafferty, Lehman, Maxion, Mitchell, Moore, Reddy, Rosenfeld, Simon, Valdes-Perez, Waibel
Machine translation: Carbonell, Hauptmann, Lafferty, Rosenfeld, Waibel
Manipulation: Erdmann, Mason, Mitchell
Manufacturing: Moore
Markov models: Harchol-Balter, Simmons
Mathematics of Computation: G. Miller, Rudich
Measurement and evaluation: Gibson, Harchol-Balter, Johnson, Maxion, Satyanarayanan
Medical robotics/computer-assisted surgery: Kanade
Memory architecture: Gibson
Mobile computing: Johnson, Pausch, Satyanarayanan, Siewiorek
Mobile networking: Johnson
Mobile robotics: Mitchell, Moore, Simmons
Model checking: Wing
Monitoring and error recovery: Simmons
Motion planning: Erdmann, Moore
Multicast: Zhang
Multicomputers: Gibson, Goldstein
Multilingual Spoken Language Systems: Waibel
Multimedia: Christel, Dannenberg, Gibson, Kanade, Rajkumar, Wactlar, Zhang
Multimodal interfaces: Pausch, Rosenfeld, Rudnicky, Waibel
Multiprocessors: Garlan, Goldstein, Harchol-Balter
Music, computer: Dannenberg, Scott

Natural language generation: Lehman
Natural language processing: See Computational Linguistics.
Network-aware applications: Ganger, Johnson, Steenkiste, Zhang
Network protocols: Ganger, Johnson, Harchol-Balter, Satyanarayanan, Steenkiste, Zhang
Networking: Ganger, Gibson, Johnson, Maxion, Steenkiste, Wactlar, Zhang
Neural Networks: Blum, Fahlman, McClelland, Plaut Touretzky, Waibel
Neuroscience: T. Lee, Touretzky
Numerical methods: G. Miller

Object-oriented programming: Wing
Operating systems: Ganger, Gibson, Johnson, Rajkumar, Wactlar

Parallel AI: Touretzky
Parallel applications: Gibson, Goldstein, Harchol-Balter
Parallel architectures: Blelloch, Gibson, Goldstein, Gross, Harchol-Balter, G. Miller
Parallel computing: O'Hallaron
Parallel file systems: Gibson
Parallel models of computation: Blelloch, G. Miller
Parallel processing: Blelloch, Brookes, Bryant, Clarke, Gibson, McClelland, Steenkiste, Touretzky
Parallel programming: Blelloch, Gross, O'Hallaron, Steenkiste
Parallel systems: Harchol-Balter, O'Hallaron
Parallelizing compilers: Goldstein, O'Hallaron
Parsing, natural language: Carbonell, Lafferty, Sleator
Pattern Recognition: Lafferty, Waibel
Perception, auditory: Stern
Performance evaluation: Ganger, Gibson, Harchol-Balter, Johnson, Maxion, Satyanarayanan, Zhang
Photogrammetry: McGlone
Planning: Blum, Carbonell, Erdmann, Mason, Mitchell, Simmons, Veloso
Polymorphism: Harper, Pfenning, Reynolds
Power management: Satyanarayanan, Siewiorek
Problem-solving: Carbonell, Erdmann, Mitchell
Probabilistic planning: Simmons
Process control: Maxion
Program analysis: P. Lee
Program manipulation tools: Scherlis
Program optimization: Goldstein
Program synthesis: Erdmann, Mason
Program transformation: Blelloch, Brookes, Scherlis, Scott
Program visualization: Garlan
Programming environments: Dannenberg, Fahlman, Garlan, Pausch, Scherlis, Scott, Shaw
Programming languages: Blelloch, Brookes, Clarke, Dannenberg, Fahlman, Harper, P. Lee, Pfenning, Reynolds, Scherlis, Scott, Shaw, Wing
Programming methodology: Brookes, Clarke, Garlan, Pausch, Pfenning, Scherlis, Scott, Shaw, Wing
Proof theory: Harper, Pfenning, Scott
Protocols: Gibson, Harchol-Balter, Johnson, Rudich, Satyanarayanan, Zhang
Protocol Analysis: Harchol-Balter, John, Maxion
Psychology: John, Maxion, Rudnicky

QoS Management: Rajkumar
Queueing Theory: Harchol-Balter

Randomization: Erdmann, Rudich
Reading Theory: Roth
Real-time networks: Harchol-Balter, Zhang
Real-time systems: Dannenberg, Harchol-Balter, Rajkumar
Reasoning, Inheritance: Touretzky
Reasoning, Non-monotonic: Touretzky
Reconfigurable Computing: Goldstein
Recovery: Johnson
Reflection: Mitchell
Reinforcement learning: Moore
Reliability: Ganger, Gibson, Goldstein, Johnson, Maxion, Satyanarayanan, Siewiorek, Wing
Remote execution: Wing
Remote procedure call: Johnson
Remote sensing: Cochran, McKeown
Rendering: Heckbert
Requirements analysis: Maxion
Resource management: Harchol-Balter, Zhang
Robot programming: Erdmann, Mason
Robotics: Erdmann, Kanade, Mason, Mitchell
Routine design: Shaw

Scheduling: Harchol-Balter, Moore
Scientific discovery: Maxion, Mitchell, Simon, Valdes-Perez
Scientific computing: Heckbert, O'Hallaron
Search: Valdes-Perez
Security: Gibson, Johnson, Satyanarayanan, Wing
Semantic networks: Fahlman, Touretzky
Semantics-based program analysis: P. Lee
Semantics-based compiler generation: P. Lee
Semantics-based program manipulation: Scherlis
Semantics of natural languages: Lehman, Scott
Semantics of programming languages: Brookes, Clarke, Harper, P. Lee, Pfenning, Reynolds, Scott, Wing
Semiconductor fabrication: Maxion
Sensing, action, prediction: Erdmann
Signal processing: Dannenberg, Stern
Simulation: Bryant, Gibson, Harchol-Balter, Johnson
Software architectures: Garlan, Scherlis, Shaw
Software construction: Gross
Software design methods: Garlan, Shaw
Software engineering: Fahlman, Garlan, Scherlis, Shaw, Wing
Spatial databases: McKeown
Spatial reasoning and representation: Cochran, Erdmann, McKeown, Mason
Specialized architectures: Goldstein
Special-purpose systems: Goldstein
Specification: Brookes, Clarke, Garlan, Harper, P. Lee, Pfenning, Reynolds, Scott, Shaw, Wing
Speech Based Instructional Software: Roth
Speech recognition: Rosenfeld, Stern, Waibel
Speech synthesis: Hauptmann
Speech translation: Waibel
Speech understanding: Hauptmann, Reddy, Rosenfeld, Rudnicky, Stern, Waibel
Statistics: Harchol-Balter, Lafferty, Moore, Rosenfeld
Stereo analysis: Cochran
Stochastic Modeling: Gibson, Harchol-Balter, Lafferty, Rosenfeld, Waibel
Storage: Ganger, Gibson
Supercomputers: Blelloch, Gibson, Goldstein, Reddy
Symbolic computation: Bryant, Scott

Tactile sensing: Mason
Task representation: Moore
Task-level control: Simmons
Telecommunication: Zhang
Text, electronic: Scott
Text processing: Carbonell, Rosenfeld
Theory formation: Mitchell, Valdes-Perez
Transaction processing: Wing
Typesetting: Scott
Type theory: Harper, P. Lee, Pfenning, Reynolds, Scott

Usability evaluation: John, Maxion, Pausch
User models: John, Maxion

Verification: Brookes, Bryant, Clarke, Harper, Reynolds, Scott, Wing
Virtual(ized) reality: Kanade, Pausch
Vision: Cochran, Kanade, McGlone, McKeown
Vision, 3D: Kanade
Visual programming: Garlan
Visualization: Christel, O'Hallaron, Pausch, Roth
VLSI: Blelloch, Brookes, Bryant, Clarke, Goldstein
VLSI-based sensors: Kanade

Wireless networking: Johnson

cmcc: Gross
Coda File System: Satyanarayanan
Communicator: Mosur, Reddy, Rosenfeld, Rudnicky, Stern
Composable Systems: Garlan, Shaw, Wing
Computational neuroscience: T. Lee, McClelland, Plaut, Touretzky
Computer Music: Dannenberg
Connectionist Research Group: Fahlman, McClelland, Plaut, Touretzky
COSMOS (COmpiled Simulator for MOS circuits): Bryant
Credit Net: Steenkiste
Cryptography: Wing

Darwin: Steenkiste, Zhang
DEMETER: Siewiorek
Design for Manufacturing: Siewiorek
DIPLOMAT: Carbonell, Frederking, Rudnicky
Distributed Sensor Networks (DSN): Reddy
Dynamic Source Routing: Johnson
DSSC (Data Storage Systems Center): Ganger, Gibson
Dv: O'Hallaron

Elf: Pfenning
EMC (Extended Model Checker): Clarke
ENVISAGE (Graphical Data Manipulation): Roth
Exokernel: Ganger
Experience on Demand": Christel, Hauptmann, Kanade, Wactlar

Fault Tolerance: Maxion
FISPE Project: Koedinger
Fox: Harper, P. Lee, Pfenning
Forsythe: Reynolds
Fx: Gross, O'Hallaron

GOMS: John
Gwydion: Fahlman

Harbinger: Maxion
HERO Robot: Mitchell
High Performance Computing Graphics: Heckbert
Image Understanding (IU): Kanade
Informedia: Christel, Hauptmann, Kanade, Wactlar
INTERACT: Waibel
Interactive Systems Lab: Waibel
JANUS: Waibel

KANT Knowledge-Based Automated Natural Language Translation: Carbonell

Larch: Wing
Learning Robot: Mason, Mitchell
LISTEN (Speech Recognition of Reading): Roth

MAPS (Digital Mapping Lab): Cochran, McGlone, McKeown
McDonnell Project: Koedinger
MECHEM: Valdes-Perez
Medical Robotics: Kanade
Mercator (coordinated mapping and planning): Simmons
Mercury (Electronic Library Project): Morris, Scott
MESS: P. Lee
MICON: Siewiorek
Miro: Wing
Mobile computing: Johnson, Satyanarayanan
Mobile IP: Johnson
Monarch: Johnson
Multi-Modal Human-Computer Interface: Waibel

NASD (Network-Attached Secure Disks): Gibson, Nagle, Zhang
Nectar: Steenkiste
Network Diagnosis: Maxion
New Millennium (autonomous spacecraft): Simmons
Nomad (Lunar Rover): Simmons
NPen++: Waibel

Odyssey: Satyanarayanan
OZ: Hauptmann

PACT (Pittsburgh Area Cognitive Tutoring) Center: Koedinger
Parallel Data Laboratory: Gibson
PARTHENON: Clarke
PENCHANT: Valdes-Perez
POP (Principles of Programming): Harper, P. Lee, Pfenning, Reynolds,
Scott, Wing PRODIGY: Carbonell, Veloso

Quake: O'Hallaron
Quality of Service (QoS): Zhang

RAIDframe (Rapid Prototyping for RAID): Gibson
REMULAC: O'Hallaron
RT-Mach: Rajkumar

SAGE (Automatic Presentation: Roth
SOAR: John, Lehman
Speech Understanding: Hauptmann, Reddy, Rosenfeld, Rudnicky, Stern, Waibel
SPFS (Scotch Parallel File System): Gibson
Sphinx Mosur, Reddy, Rosenfeld, Rudnicky, Stern

TCA (Task Control Architecture): Mitchell, Simmons
TDL (Task Description Language): Simmons
THEO: Mitchell
3D (Visualization and Interaction): Roth
TIP (Informed Prefetching File System): Gibson
TinkerTeach: Garlan, Shaw, Wing
TDT (Topic Detection and Tracking): Carbonell, Lafferty, Yang
TPS: Pfenning

UniCon: Shaw
Universal Library project: Carbonell, Reddy, Shamos, Thibadeau
USI (Universal Speech Interface): Rosenfeldn

Venari: Wing
Virtual World Simulation: McKeown
Virtualized Reality: Kanade
Vitruvius: Shaw