Research

Carlos Guestrin

Research interests - keywords

	Probabilistic artificial intelligence
	Machine learning
	Planning under uncertainty, Markov decision processes
	Wireless sensor networks
	Distributed algorithms
	Probabilistic graphical models, Bayesian networks, Markov networks
	Multiagent systems
	Optimization theory and algorithms
	Network and query optimization
	Classification

Research objectives

My main long-term research interest is in developing efficient algorithms and methods for designing, analyzing and controlling complex real-world systems. A common thread in my research has been the focus on large-scale stochastic dynamical systems, where the state of the system evolves over time and uncertainty is prevalent. Such systems exist in many diverse application areas: from economics, through computer science and engineering, to computational biology.

Wireless sensor networks are a central application domain for my research efforts. These networks are usually composed of small, low-cost devices that communicate wirelessly to achieve global sensing and decision-making tasks. Current real-world deployments range from scientific data collection and analysis applications (e.g., monitoring of bird habitats in the Great Duck Island), through environmental monitoring and intervention (e.g., precision agriculture in vineyards), to large-scale fault diagnosis and prevention (e.g., diagnosis from vibration data at Intel factories).

To tackle such real-world systems, one must link theoretically-founded algorithms and techniques from computer science, artificial intelligence, statistics, optimization theory and operations research, to knowledge and structure specific to the problem at hand. This link between theoretically well-posed algorithms and problem-specific structure allows us to scale up methods to tackle complex, large-scale systems. Such scaling up of algorithms to real-world problems is the central long-term goal of my research efforts.

Sensor networks offer an additional set of challenges: Due to cost and space constraints, typical nodes in sensor networks have very limited processing power. Additionally, wireless networks are usually very lossy, suffering from undetectable packet losses, packet collisions and other forms of interference. Finally, battery power is a very strong constraint in these networks. At full duty cycle, the batteries of typical nodes last no more than a couple of days. Successful long-term deployments thus require effective power management.

My long-term research goals are to develop efficient distributed algorithms for effective inference, learning and control in large-scale real-world distributed systems, such as sensor networks. These algorithms must perform the global inference and optimization tasks required by sensor network applications, while being robust to network losses and failures, and limiting communication and power requirements. In addition to developing theoretically-founded algorithms, we seek to evaluate these methods on data from real sensor network deployments, and to implement some of these approaches on real deployed systems.

Current projects

Our current projects seek, in the long-run, to develop the required algorithms and methods to scale up decision-making and inference methods to large-scale distributed systems where the state of the world is not fully observable.

Please visit our complete list of publications for full details of current projects and specific collaborators for each project, including:

	Distributed inference in sensor networks: algorithms for coherent probabilistic inference in sensor networks while minimizing communication cost, and robustly responding to network failures. Inference (or state estimation) is an indispensable building block for decision-making tasks. Our efficient method is leveraged by representation and inference approaches from probabilistic graphical models, and by novel networking and message passing algorithms.
	Efficient distributed multiagent coordination, planning and learning: Using the factored Markov decision processes representation, which exploits problem-specific structure using Bayesian networks, we design efficient approximate planning algorithms, leveraged by a novel linear programming (LP) decomposition technique. Our decomposition technique yields efficient distributed algorithms for planning and learning in collaborative multiagent settings, where multiple decision makers must coordinate their actions to maximize a common goal.
	Generalizing plans to new environments: Agents are often faced with many similar planning problems, such similarities can be modeled by a relational Markov decision process. Using LP decomposition and sampling techniques, we design algorithms for generalizing plans from a set of environments to a new, unseen (potentially larger) one.
	Cost sensitive query optimization: in sensor networks, the energy cost of acquiring a measurement can vary widely for different types of sensors. Furthermore, measurements from different sensors can be highly correlated. We design algorithms for obtaining query plans that minimize the expected cost for answering a query, by exploiting these correlations between attributes.
	Maximum margin classification in structured domains: we developed max-margin Markov networks (M³ nets), an efficient learning algorithm that combines the margin maximization and high-dimensional features (kernels) from support vector machines (SVMs), and the ability to exploit problem structure from graphical models, to obtain strong theoretical generalization bounds and empirical performance. When combined with our distributed inference techniques, this method can provide an effective solution for distributed classification in sensor networks.
	Distributed modeling of sensor network data: efficient algorithm for building a regression model of data measured by a sensor network, allowing us to perform complex data extraction tasks, while constraining the amount of communication required. These lower dimensional models minimize the communication required for extracting data from the network, and allow us to perform local inference tasks, such as outlier detection.
	Modeling of temporally and spatially-correlated sensor net data: building stochastic temporal models of the data, taking into account short-term correlations and long-term cyclical trends. These models are important for distributed inference and decision making. When combined with efficient planning techniques, such temporal models can allow us to solve decision-making problems in real-world large-scale sensor network deployments.

Comments, questions and suggestions? Please contact me.