Hanna Pasula

IJCAI Conference 2007 Conference Paper

• Stephen Friedman
• Hanna Pasula
• Dieter Fox

The ability to build maps of indoor environments is extremely important for autonomous mobile robots. In this paper we introduce Voronoi random fields (VRFs), a novel technique for mapping the topological structure of indoor environments. Our maps describe environments in terms of their spatial layout along with information about the different places and their connectivity. To build these maps, we extract a Voronoi graph from an occupancy grid map generated with a laser range-finder, and then represent each point on the Voronoi graph as a node of a conditional random field, which is a discriminatively trained graphical model. The resulting VRF estimates the label of each node, integrating features from both the map and the Voronoi topology. The labels provide a segmentation of an environment, with the different segments corresponding to rooms, hallways, or doorways. Experiments using different maps show that our technique is able to label unknown environments based on parameters learned from other environments.

ICAPS Conference 2004 Conference Paper

Learning Probabilistic Relational Planning Rules

• Hanna Pasula
• Luke Zettlemoyer
• Leslie Pack Kaelbling

To learn to behave in highly complex domains, agents must represent and learn compact models of the world dynamics. In this paper, we present an algorithm for learning probabilistic STRIPS-like planning operators from examples. We demonstrate the effective learning of rule-based operators for a wide range of traditional planning domains.

UAI Conference 2002 Conference Paper

Decayed MCMC Filtering

• Bhaskara Marthi
• Hanna Pasula
• Stuart Russell 0001
• Yuval Peres

Filtering---estimating the state of a partially observable Markov process from a sequence of observations---is one of the most widely studied problems in control theory, AI, and computational statistics. Exact computation of the posterior distribution is generally intractable for large discrete systems and for nonlinear continuous systems, so a good deal of effort has gone into developing robust approximation algorithms. This paper describes a simple stochastic approximation algorithm for filtering called {em decayed MCMC}. The algorithm applies Markov chain Monte Carlo sampling to the space of state trajectories using a proposal distribution that favours flips of more recent state variables. The formal analysis of the algorithm involves a generalization of standard coupling arguments for MCMC convergence. We prove that for any ergodic underlying Markov process, the convergence time of decayed MCMC with inverse-polynomial decay remains bounded as the length of the observation sequence grows. We show experimentally that decayed MCMC is at least competitive with other approximation algorithms such as particle filtering.

NeurIPS Conference 2002 Conference Paper

Identity Uncertainty and Citation Matching

• Hanna Pasula
• Bhaskara Marthi
• Brian Milch
• Stuart Russell
• Ilya Shpitser

Identity uncertainty is a pervasive problem in real-world data analysis. It arises whenever objects are not labeled with unique identifiers or when those identifiers may not be perceived perfectly. In such cases, two ob- servations may or may not correspond to the same object. In this paper, we consider the problem in the context of citation matching—the prob- lem of deciding which citations correspond to the same publication. Our approach is based on the use of a relational probability model to define a generative model for the domain, including models of author and title corruption and a probabilistic citation grammar. Identity uncertainty is handled by extending standard models to incorporate probabilities over the possible mappings between terms in the language and objects in the domain. Inference is based on Markov chain Monte Carlo, augmented with specific methods for generating efficient proposals when the domain contains many objects. Results on several citation data sets show that the method outperforms current algorithms for citation matching. The declarative, relational nature of the model also means that our algorithm can determine object characteristics such as author names by combining multiple citations of multiple papers.

AAAI Conference 1999 Short Paper

A Bayesian Approach to Object Identification

• Hanna Pasula
• University of California
• Berkeley

There are many real world domains where an agent can observe the world state only partially and intermittently, using noisy sensors. Merely keeping track of the objects present in such a system is non-trivial. The problem may be complicated further if the system dynamics are not fully known or unpredictable, so that some on-line learning is necessary. Ihave been working on a principled approach to state estimation and prediction under these realistic conditions. So far, I have focused mostly on object identification, deciding if some newly observed object is the same as a previously observed one. The work has been applied to the surveillance of a large metropolitan freeway system.

IJCAI Conference 1999 Conference Paper

Tracking many objects with many sensors

• Hanna Pasula
• Stuart Russell
• Michael Ostland
• YdacovRitov

Keeping track of multiple objects over time is a problem that arises in many real-world domains. The problem is often complicated by noisy sensors and unpredictable dynamics. Previous work by Huang and Russell, drawing on the data association literature, provided a probabilistic analysis and a threshold-based approximation algorithm for the case of multiple objects detected by two spatially separated sensors. This paper analyses the case in which large numbers of sensors are involved. We show that the approach taken by Huang and Russell, who used pairwise sensor-based appearance probabilities as the elementary probabilistic model, does not scale. When more than two observations are made, the objects' intrinsic properties must be estimated. These provide the necessary conditional independencies to allow a spatial decomposition of the global probability model. We also replace Huang and Russell's threshold algorithm for object identification with a polynomial-time approximation scheme based on Markov chain Monte Carlo simulation. Using sensor data from a freeway traffic simulation, we show that this allows accurate estimation of long-range origin/destination information even when the individual links in the sensor chain are highly unreliable.