Colloquium

Automatically extracting structured facts from unstructured text is a key step toward natural language understanding. Many researchers study this problem, typically in the context of text collections such as newsfeeds or the web. This talk will explore information extraction from user workstations. While many of the subproblems are the same as for extraction from other corpora, there are characteristics of workstations that suggest very different approaches from "traditional" information extraction. For example, suppose the facts we wish to extract from the workstation consist of assertions about the key activites of the workstation user (e.g., which courses they are taking, which committees they serve on), and relations among the people, meetings, topics, emails, files, etc. associated with each such activity. Interestingly, workstations contain a great deal of redundant clues regarding these facts (e.g., evidence that Bob and Sue are both involved in the hiring committee exists in email, the calendar, individual files, ...). This redundancy suggests considering information extraction as a problem of integrating diverse clues from multiple sources rather than a problem of examining a single sentence in great detail. This talk will explore this formulation of the information extraction problem, and present our recent work on automatically extracting facts using workstation-wide information obtained by calling Google desktop search as a subroutine.

In this talk, I will present our recent research on our ARTS project. The goal of our ARTS project is to efficiently and effectively detect bugs in software, and to enable software surviving bugs to provide non-stop service.

Our ARTS project explores a spectrum of non-conventional approaches to improve the robustness and availability of software. These approaches include: (1) hardware architecture support for software debugging and testing, (2) applying data mining and statistic to program analysis, (3) OS support for interactive debugging, and (4) OS support for surviving software failures.

In particular, my talk will focus on hardware support for bug detection and OS support for surviving software faults. In addition, I will briefly describe how to use data mining to extract programming rules and detect related bugs in large software including OS codes (Linux, FreeBSD) and server codes (Apache, MySQL) as well as our bug characterization and benchmarking initiatives.

Current cameras capture instants in time and space. But there is something just beyond the reach of the camera that our minds seem to capture quite well: moments. We remember moments. We'd like to share moments. We want to capture moments. I will provide at least an informal definition of what I am calling a moment. I'll also discuss recent technology that lets us use current cameras+processing to capture moments. Finally, I'll argue for how I believe future cameras, editing systems, and display paradigms will support this new class of artifact. This talk should be interesting to both the computer scientist and the photographer.

Virtual Internets (VIs) are emerging as a useful tool for managing shared testbed infrastructure, as well as supporting emerging protocols and systems in an extension of the Internet architecture. This talk presents the principles of our Virtual Internet Architecture, and examines its impact on the architecture of end systems, routers, and protocols. The talk also summarizes related research exploring the capabilities of VIs and augmenting systems capabilities to support VIs. This includes: the X-Bone system for automated VI deployment and management; the DynaBone system for fault-tolerance and performance via multi-layer virtualization; the NetFS system for providing compartmentalized configuration of network resources; and the DataRouter system for supporting application-directed peer networks via a network-layer string rewriting mechanism. We discuss efforts underway to deploy a persistent, global X-Bone for collaborative network experiments, and steps that take a VI into a new Communicating System for the future.

This talk will also very briefly note some concurrent effots, including an all-optical IP router and LAN, high-performance zero-configuration security, encapsulating bridges, and "smart-start" TCP.

We discuss the online index-merging problem: documents arrive at a system continuously, and must be immediately indexed for fulltext search. Meanwhile, the system is continuously answering queries on its fulltext index. The system is I/O-limited, so a single online indexing data structure (e.g. Btree) cannot be used: this approach would require a random I/O for every word in every document that arrives. Instead, multiple off-line index structures are used. The off-line indexes are precomputed in memory and written out using only sequential I/O; at any time two or more of the indexes can be merged into a single new index using only sequential I/O. Every query must consult every off-line index, so the I/O cost of a query is proportional to the number of indexes. Thus, there is a tension between query cost and merging cost: by spending I/O on merging indexes, we can reduce the I/O required for future queries. The online index-merging problem is to find a merging schedule that minimizes the total I/O cost.

The problem is related to several well-studied problems in network design, but possesses some unique characteristics. For a restricted class of inputs, we describe an index-merging schedule that is optimal up to a small constant factor. For general inputs, we propose (by analogy with the ski rental problem) an algorithm with apparently good empirical properties, but it has so far resisted our attempts to prove nontrivial performance bounds.

Joint work with Frank McSherry.

The Protein Data Bank is the international repository for the structures of all biological macromolecules. The ways in which the data are represented, collected, archived, and queried will be described. The ways in which the PDB resource has been designed so as to accommodate a very diverse user community will be discussed.

With the enormous growth of wide-area networks, especially the Internet, one research focus within the operating systems community has moved to building coherent systems that can connect together a billion users who collectively have a trillion objects. No existing system can handle this. Current wide-area applications are constructed individually and do not have any common framework and do not interwork. Furthermore, each new application developer must begin again from scratch, since pieces of existing systems are rarely reusable.

The Globe system is being designed to address these problems. It consists of an object-based layer of software ("middleware") that can be placed on top of each operating system to provide a common interface for applications to deal with. A key idea used in Globe is the distributed object, in which an object resides in multiple (possibly widely-separated) addresses spaces at the same time. Properties and structure of distributed objects will be discussed, as will object binding and location, a highly complex matter for a system with a trillion (potentially mobile) objects owned by a billion users. In addition, security and some applications will be discussed.

Complete and robust intelligent agents capable of facing complex environments require an effective integation of perception, cognition, and action. Robot soccer, as a pioneering multi-robot task, has offered a concrete challenging research testbed, where a team of robots faces an uncertain and dynamic environment created by a team of opponent robots. We have researched in robot soccer developing single-robot and multi-robot perception, cognition, and action algorithms. To form an effective team of robots, individual robots need to be robust. We have developed effective object recognition, localization, and behavior-based algorithms. In addition, to achieve a reliable team of robots, we research on team coordination strategies, team response to a dynamic world, behavior recognition, opponent modeling, and learning. In this talk, I will present our contributions to addressing these multi-robot challenges. I will conclude setting my research goals in perspective. I will discuss some of the fascinating open questions towards creating increasingly robust teams of autonomous intelligent robots.

Bio:

Manuela M. Veloso is Professor of Computer Science at Carnegie Mellon University. She earned her Ph.D. in Computer Science from Carnegie Mellon. She also received a B.S. in Electrical Engineering in 1980 and an M.Sc. in Electrical and Computer Engineering in 1984 from the Instituto Superior Tecnico in Lisbon.

Veloso researches in the area of artificial intelligence with focus on planning, control learning, and execution for single and multirobot teams. Veloso has a long experience of classic deterministic planning by analogy transfer, and more recently she has developed probabilistic plan and policy reuse algorithms. She is currently particularly interested in learning and using abstract domain representations that can be reused for planning and problem solving.

Veloso has extensively researched in action selection algorithms to address uncertain, dynamic, and adversarial environments. Veloso and her students have developed teams of robot soccer agents, which have been RoboCup world champions several times. She investigates learning approaches to a variety of control problems, in particular the performance optimization of algorithm implementations, and plan recognition in complex data sets.

Veloso is a Fellow of the American Association of Artificial Intelligence. She is Vice President of the RoboCup International Federation. She was awarded an NSF Career Award in 1995 and the Allen Newell Medal for Excellence in Research in 1997. Veloso was Program Co-Chair of 2005 National Conference on Artificial Intelligence and is now the Program Chair of the 2007 International Joint Conference on Artificial Intelligence.

Veloso strongly endorses the new Carnegie Mellon Technology Bridge World effort. She created the new "V-unit" project that provides an opportunity for graduate students to grow a vision of how computer science and technology can affect non-traditional problems dealing with society, ecology, and sustained devlopment.

Veloso is the author of one book on "Planning by Analogical Reasoning" and editor of several other books. She is also an author in over 200 journal articles and conference papers.

Simultaneous Localization and Mapping (SLAM) is the task of building an accurate map of an environment without getting lost in the process. This problem is of great significance in robotics for situations in which an accurate global position sensor, such as GPS, is not available. This includes undersea, subterranean, and space exploration missions, as well as most indoor environments.

A major challenge faced by SLAM algorithms is that of avoiding accumulating error: Small errors in localization can lead to small errors in the map which, when compounded over a long exploration path, can lead to inconsistent and misaligned maps. I will present the DP-SLAM algorithm, an approach to the slam problem that minimizes accumulated error by efficiently maintaining hundreds of map hypotheses using a particle filter and a novel map data structure.

Using DP-SLAM, we have built maps at 3cm resolution with no discernible alignment errors or blemishes for robot trajectories over 100m. Our approach can handle highly ambiguous environments with features such as glass and thin columns.

The web site for the project, which includes sample maps, is: http://www.cs.duke.edu/~parr/dpslam.

This talk is based on joint work with Austin Eliazar (Duke University).

Speaker Bio

Since 2000, Ron Parr has been assistant professor at the Duke University Computer Science Department. He received his A.B. (Cum Laude) in Philosophy in 1990 from Princeton University, where he was advised by Gilbert Harman. His bachelor's thesis, "Minds, Brains and Searle," addressed Searle's criticisms of strong AI. In 1998, he received his Ph.D. in computer science from the University of California at Berkeley, under the supervision of Stuart Russell. His dissertation topic was, "Hierarchical Control and Learning for Markov Decision Processes." After graduating from Berkeley, Ron spent two years as a postdoctoral research associate at Stanford University, where he worked with Daphne Koller. At Stanford, Ron worked on decision theory, tracking and on solving factored Markov Decision Processes using linear value function approximators. Ron's current research interests include most forms of planning under uncertainty, reinforcement learning and robotics. Ron has served on the editorial board of the Journal of Artificial Intelligence Research (JAIR) and was selected as a Sloan fellow in 2003.