Quick links

Colloquium

Sensing for Autonomous Driving: Some Lessons from the DARPA Urban Challenge Race

Date and Time
Friday, September 26, 2008 - 1:00pm to 2:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Prof. Dan Huttenlocher, from Cornell University
Host
Fei-fei Li
Team Cornell's Skynet is one of six vehicles that successfully completed the 2007 DARPA Urban Challenge, with over 55 miles of fully autonomous driving in an urban environment. The competition included many scenarios such as staying in a lane, merging into traffic, passing other vehicles, obeying queueing order at stop signs, parking, and robot-robot interaction. Skynet was designed to drive "human-like" with smooth, predictable behaviors, even in the presence of a vast array of uncertainties. In this talk I will describe the vehicle design with a focus on the systems for perception and planning, and will present some results from the semi-finals and the final race. In particular I will discuss the pose estimation system which uses visual input to improve the estimate of the vehicle's location, and the object tracking system which can simultaneously track dozens of objects while accurately estimating their speed and heading. I will also discuss some of the limitations of such systems, which played a role in the fender bender between Skynet and MIT's Talos robot. Speaker: Dan Huttenlocher is the John P. and Rilla Neafsey Professor of Computing, Information Science and Business at Cornell University, where he holds a joint appointment in the Computer Science Department and the Johnson Graduate School of Management. His current research interests are in computer vision, social and information networks, geometric algorithms and autonomous driving. He has been recognized for his research and teaching contributions, including being named an NSF Presidential Young Investigator, New York State Professor of the Year and Fellow of the ACM. In addition to academic posts he has been chief technical officer of Intelligent Markets, a provider of advanced trading systems on Wall Street, and spent more than ten years at Xerox PARC directing work that led to the ISO JBIG2 image-compression standard.

Building a Strong Foundation for the Future Internet

Date and Time
Wednesday, May 14, 2008 - 4:00pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Jennifer Rexford, from Princeton University
Host
Jennifer Rexford
The Internet is unquestionably a tremendous success---a research experiment that truly escaped from the lab. However, the Internet faces many technical challenges that, while deeply rooted in early design decisions, have grown even more complex as the network has evolved into a world-wide commercial infrastructure.

In this talk, we argue that perhaps the most important goal for a future Internet is the ability to define, model, and analyze it precisely, so we can make stronger statements about its basic properties. Using Internet routing as a driving example, we discuss the research challenges in designing protocols that are simultaneously programmable (so they are flexible and can evolve over time) and perform well in a competitive economic environment (where different parts of the system are controlled by parties with different, sometimes conflicting, objectives).

We believe that answering these fundamental questions presents a wonderful opportunity for theoretical research in computer science, electrical engineering, economics, and mathematics. _______________________________________________

Learning Structured Bayesian Networks: Combining Abstraction Hierarchies and Tree-Structured Conditional Probability Tables

Date and Time
Wednesday, May 7, 2008 - 1:00pm to 2:30pm
Location
Computer Science 418B
Type
Colloquium
Speaker
Marie desJardins, from University of Maryland
Host
Jennifer Rexford
In this talk, I will describe our research on incorporating background knowledge in the form of feature hierarchies during Bayesian network learning. Feature hierarchies enable the learning system to aggregate categorical variables in meaningful ways, thus enabling an appropriate "discretization" for a categorical variable. In addition, by choosing the appropriate level of abstraction for the parent of a node, we also support compact representations for the local probability models in the network. We combine this notion of selecting an appropriate abstraction with context-specific independence representations, which capture local ndependence relationships among the random variables in the Bayesian network. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models.

I will describe our primary contribution, the Tree-Abstraction-Based Search (TABS) algorithm, which learns a data distribution by inducing the graph structure and parameters of a Bayesian network from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. In order to construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. Empirical results in several benchmark domains show that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies.

BIOGRAPHY Dr. Marie desJardins is an associate professor in the Department of Computer Science and Electrical Engineering at the University of Maryland, Baltimore County. Her research is in artificial intelligence, focusing on the areas of machine learning, multi-agent systems, planning, interactive AI techniques, information management, reasoning with uncertainty, and decision theory.

Dr. desJardins can be contacted at the Dept. of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore MD 21250, mariedj@cs.umbc.edu,(410) 455-3967.

How are Mobile Phones Changing Families

Date and Time
Wednesday, April 30, 2008 - 4:30pm to 6:00pm
Location
McCosh Hall 46
Type
Colloquium
Speaker
Jim Katz
Host
Edward Felten

The truth about quantum computers.

Date and Time
Wednesday, April 23, 2008 - 4:30pm to 6:00pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Umesh Vazirani, from UC Berkeley
Host
Sanjeev Arora
Popular articles on quantum computers sometimes portray them as mythical devices that speed up any computation by an exponential factor. The truth is much more subtle, and over the last decade and a half we have learned a great deal about the circumstances under which Nature allows us access to its exponential computational resources. This has a bearing on our understanding of the foundations of both computer science and quantum physics. In this talk I will try to outline some of these issues. No background in quantum physics will be assumed.

Recent Directions in Nonparametric Bayesian Machine Learning

Date and Time
Thursday, March 27, 2008 - 4:15pm to 5:45pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Zoubin Ghahramani, from Carnegie Mellon University
Host
David Blei
Machine learning is an interdisciplinary field which seeks to develop both the mathematical foundations and practical applications of systems that learn, reason and act. Machine learning draws from many fields, ranging from Computer Science, to Engineering, Psychology, Neuroscience, and Statistics. Because uncertainty, data, and inference play a fundamental role in the design of systems that learn, statistical methods have recently emerged as one of the key components of the field of machine learning.

In particular, Bayesian methods, based on the work of Reverend Thomas Bayes in the 1700s, describe how probabilities can be used to represent the degrees of belief of a rational agent. Bayesian methods work best when they are applied to models that are flexible enough to capture to complexity of real-world data. Recent work on non-parametric Bayesian methods provides this flexibility.

I will touch upon key developments in the field, including Gaussian processes, Dirichlet processes, and the Indian buffet process (IBP). Focusing on the IBP, I will describe how this can be used in a number of applications such as collaborative filtering, bioinformatics, cognitive modelling, independent components analysis, and causal discovery. Finally, I will outline the main challenges in the field: how to develop new models, new fast inference algorithms, and compelling applications. >

Software Transactions: A Programming-Languages Perspective

Date and Time
Wednesday, March 26, 2008 - 4:15pm to 5:45pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Dan Grossman, from University of Washington
Host
David Walker
With multicore processors bringing parallel computing to the masses, there is an urgent need to make concurrent programming easier. Software transactions hold great promise for simplifying shared-memory concurrency,and they have received enormous attention from the research community in the last couple years. This talk will provide an overview of work done at the University of Washington to help bring transactions to the next generation of programming languages. No prior knowledge of software transactions will be necessary.

Our work complements research done on hardware and software algorithms for implementing transactions by considering essential issues regarding how transactions affect language semantics and language implementation. Our motivation takes the novel view that transactions can improve language support for concurrency much like garbage collection can improve language support for memory management. Our language design and language semantics work has considered the pitfalls of so-called "weak isolation" and how to avoid them, interaction with other language features like native calls and exceptions, and the implications for shared-memory consistency models. Our implementation work includes techniques for the special case of a uniprocessor, a whole-program static optimization that uses pointer information to remove unnecessary read- and write-barriers while providing "strong isolation", and ongoing work for allowing parallelism within transactions.

Dan Grossman is an Assistant Professor in the Department of Computer Science & Engineering at the University of Washington. His research in the design and implementation of programming languages is aimed at improving software quality.

TrafficSense: Rich Road and Traffic Monitoring Using Mobile Smartphones

Date and Time
Friday, March 14, 2008 - 11:00am to 12:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Venkat Padmanabhan, from Microsoft Research
Host
Jennifer Rexford
We consider the problem of monitoring road and traffic conditions in a city. Prior work in this area has required the deployment of dedicated sensors on vehicles and/or on the roadside, or the tracking of mobile phones by service providers. Furthermore, prior work has largely focused on the developed world, with its relatively simple traffic flow patterns. In fact, traffic flow in cities of the developing regions, which comprise much of the world, tends to be much more complex owing to varied road conditions (e.g., potholed roads), chaotic traffic (e.g., a lot of braking and honking), and a heterogeneous mix of vehicles (2-wheelers, 3-wheelers, cars, buses, etc.).

To monitor road and traffic conditions in such a setting, we present TrafficSense, a system that piggybacks on smartphones that users carry around with them. Each participating smartphone performs rich sensing using its communication radios, GPS, accelerometer, and microphone, scans for and exchanges information from other participating phones in its neighbourhood, and reports processed information back to a central server for aggregation and reporting. We discuss key technical challenges, including energy optimization and the need for hands-free operation, present the design of TrafficSense, including how information from multiple sensors is combined to make inferences, and evaluate it in various road and traffic settings in Bangalore.

(Joint work with Prashanth Mohan and Ram Ramjee.)

Bio: Venkat Padmanabhan is a Senior Researcher and Research Manager at Microsoft Research India in Bangalore, where he founded and now leads the Mobility, Networks, and Systems group. Venkat was previously with Microsoft Research Redmond for 8.5 years. His research interests are in networked systems and his current projects focus on mobile and senor systems, and network management. His professional service has included serving as program chair for ACM NOSSDAV 2004, ACM IMC 2005, and IEEE HotWeb 2008, and as an affiliate faculty member at the University of Washington, where he has taught and served in student thesis committees. Venkat holds a B.Tech. from IIT Delhi and an M.S. and Ph.D from UC Berkeley, all in Computer Science.

Reinventing Partially Observable Reinforcement Learning

Date and Time
Wednesday, March 12, 2008 - 4:15pm to 5:45pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Eyal Amir, from University of Illinois, Urbana-Champaign
Host
David Blei
Many complex domains offer limited information about their exact state and the way actions affect them. There, autonomous agents need to make decisions at the same time that they learn action models and track the state of the domain. This combined problem can be represented within the framework of reinforcement learning in POMDPs, and is known to be computationally difficult.

In this presentation I will describe a new framework for such decision making, learning, and tracking. This framework applies results that we achieved about updating logical formulas (belief states) after deterministic actions. It includes algorithms that represent and update the set of possible action models and world states compactly and tractably. It makes a decision with this set, and updates the set after taking the chosen action. Most importantly, and somewhat surprisingly, the number of actions that our framework takes to achieve a goal is bounded polynomially by the length of an optimal plan in a fully observable, fully known domain, under lax conditions. Finally, our framework leads to a new stochastic-filtering approach that has better accuracy than previous techniques.

* Joint work with Allen Chang, Hannaneh Hajishirzi, Stuart Russell, Dafna Shahaf, and Afsaneh Shirazi (IJCAI'03,IJCAI'05,AAAI'06,ICAPS'06,IJCAI'07,AAAI'07).

Computing Equilibria in Games

Date and Time
Wednesday, March 5, 2008 - 4:15pm to 5:45pm
Location
Computer Science Small Auditorium (Room 105)
Type
Colloquium
Speaker
Konstantinos Daskalakis, from UC Berkeley
Host
Sanjeev Arora
Game Theory is important for the study of large competitive environments, such as the Internet, the market, and even social and biological systems. A key tool in analyzing such systems (games) is the study of their stable states, that is, their equilibria. Understanding the properties of equilibria can give insights into the effectiveness of economic policies, engineering decisions, etc. However, due to the large scale of most interesting games, the problem of computing equilibria cannot be separated from complexity considerations. Motivated by this challenge, I will discuss the problem of computing equilibria in games. I will show first that computing a Nash equilibrium is an intractable problem. It is not NP-complete, since, by Nash's theorem, an equilibrium is always guaranteed to exist, but it is at least as hard as solving any fixed point computation problem, in a precise complexity-theoretic sense. In view of this hardness result, I will present algorithms for computing approximate equilibria. In particular, I will describe algorithms that achieve constant factor approximations for 2-player games and give a quasi-polynomial time approximation scheme for the multi-player setting. Finally, I will consider a very natural and important class of games termed anonymous games. In these games every player is oblivious to the identities of the other players; examples arise in auction settings, congestion games, and social phenomena. I will introduce a polynomial time approximation scheme for the anonymous setting and provide surprising connections to Stein's method in probability theory. Bio: Constantinos (or Costis) Daskalakis grew up in Athens, Greece, where he received his undergraduate degree in Electrical and Computer Engineering from the National Technical University of Athens. In 2004 he moved to California to pursue a Ph.D. in Computer Science at U.C. Berkeley under the supervision of Professor Christos H. Papadimitriou. Costis’s work has focused on computational game theory and applied probability, in particular the computation of equilibria in games, the study of social networks, and computational problems in biology. His research is motivated by two questions: "How does the algorithmic perspective influence economics, biology, physics, and the social sciences?" And, "how does the study of computational problems arising from areas outside computer science transform the theory of computation?"
Follow us: Facebook Twitter Linkedin