In a previous paper, Liu argued for the importance of establishing a precise theoretical foundation for program debugging from first principles. In this paper, we present a first step towards a theoretical exploration of program debugging algorithms. The starting point of our work is the recent debugging approach based on predicate switching. The idea is to switch the outcome of an instance of a predicate to bring the program execution to a successful completion and then identify the fault by examining the switched predicate. However, no theoretical analysis of the approach is available. In this paper, we generalize the above idea, and propose the bounded debugging via multiple predicate switching (BMPS) algorithm, which locates faults through switching the outcomes of instances of multiple predicates to get a successful execution where each loop is executed for a bounded number of times. Clearly, BMPS can be implemented by resorting to a SAT solver. We focus attention on RHS faults, that is, faults that occur in the control predicates and right-hand-sides of assignment statements. We prove that for conditional programs, BMPS is quasi-complete for RHS faults in the sense that some part of any true diagnosis will be returned by BMPS; and for iterative programs, when the bound is sufficiently large, BMPS is also quasi-complete for RHS faults. Initial experimentation with debugging small C programs showed that BMPS can quickly and effectively locate the faults.

Non-invasive identity inference in the home environment is a very challenging problem. A practical solution to the problem could have far reaching implications in many industries, such as home entertainment. In this work, we consider the problem of identity inference using a TV remote control. In particular, we address two challenges that have so far prevented the work of Chang et al. (2009) from being applied in a home entertainment system. First, we show how to learn the patterns of TV remote controls incrementally and online. Second, we generalize our results to partially labeled data. To achieve our goal, we use state-of-the-art methods for max-margin learning and online convex programming. Our solution is efficient, runs in real time, and comes with theoretical guarantees. It performs well in practice and we demonstrate this on 4 datasets of 2 to 4 people.

Intentions have been widely studied in AI, both in the context of decision-making within individual agents and in multi-agent systems. Work on intentions in multi-agent systems has focused on joint intention models, which characterise the mental state of agents with a shared goal engaged in teamwork. In the absence of shared goals, however, intentions play another crucial role in multi-agent activity: they provide a basis around which agents can mutually coordinate activities. Models based on shared goals do not attempt to account for or explain this role of intentions. In this paper, we present a formal model of multi-agent systems in which belief-desire-intention agents choose their intentions taking into account the intentions of others. To understand rational mental states in such a setting, we formally define and investigate notions of multi-agent intention equilibrium, which are related to equilibrium concepts in game theory.

We address the problem of mining name transliterations from comparable corpora in languages P and Q in the following resource-poor scenario: Parallel names in PQ are not available for training. Parallel names in PR and RQ are available for training. We propose a novel solution for the problem by computing a common geometric feature space for P,Q and R where name transliterations are mapped to similar vectors. We employ Canonical Correlation Analysis (CCA) to compute the common geometric feature space using only parallel names in PR and RQ and without requiring parallel names in  PQ. We test our algorithm on data sets in several languages and show that it gives results comparable to the state-of-the-art transliteration mining algorithms that use parallel names in PQ for training.

Search based solvers for Quantified Boolean Formulas (QBF) have adapted the SAT solver techniques of unit propagation and clause learning to prune falsifying assignments. The technique of cube learning has been developed to help them prune satisfying assignments. Cubes, however, have not been able to achieve the same degree of effectiveness as clauses. In this paper we demonstrate how a circuit representation for QBF can support the propagation of dual truth values. The dual values support the identical techniques of unit propagation and clause learning, except now it is satisfying assignments rather than falsifying assignments that are pruned. Dual value propagation thus exploits the circuit representation and the duality of QBF formulas so that the same effective SAT techniques can now be used to prune both falsifying and satisfyingly assignments. We show empirically that dual propagation yields significantperformance improvements and advances the state of the art in QBF solving.

Partially-observable Markov decision processes (POMDPs) provide a powerful model for sequential decision-making problems with partially-observed state and are known to have (approximately) optimal dynamic programming solutions. Much work in recent years has focused on improving the efficiency of these dynamic programming algorithms by exploiting symmetries and factored or relational representations. In this work, we show that it is also possible to exploit the full expressive power of first-order quantification to achieve state, action, and observation abstraction in a dynamic programming solution to relationally specified POMDPs. Among the advantages of this approach are the ability to maintain compact value function representations, abstract over the space of potentially optimal actions, and automatically derive compact conditional policy trees that minimally partition relational observation spaces according to distinctions that have an impact on policy values. This is the first lifted relational POMDP solution that can optimally accommodate actions with a potentially infinite relational space of observation outcomes.

The ability to discover the effects of actions and apply this knowledge during goal-oriented action selection is a fundamental requirement of embodied intelligent agents. In our ongoing work, we hope to demonstrate the utility of learned control models for whole-body mobile manipulation. In this short paper we discuss preliminary work on learning a forward model of the dynamics of a balancing robot exploring simple arm movements. This model is then used to construct whole-body control strategies for regulating state variables using arm motion.

It is standard in multiagent settings to assume that agents will adopt Nash equilibrium strategies. However, studies in experimental economics demonstrate that Nash equilibrium is a poor description of human players' initial behavior in normal-form games. In this paper, we consider a wide range of widely-studied models from behavioral game theory. For what we believe is the first time, we evaluate each of these models in a meta-analysis, taking as our data set large-scale and publicly-available experimental data from the literature. We then propose modifications to the best-performing model that we believe make it more suitable for practical prediction of initial play by humans in normal-form games.

Matrix factorization is a fundamental technique in machine learning that is applicable to collaborative filtering, information retrieval and many other areas. In collaborative filtering and many other tasks, the objective is to fill in missing elements of a sparse data matrix. One of the biggest challenges in this case is filling in a column or row of the matrix with very few observations. In this paper we introduce a Bayesian matrix factorization model that performs regression against side information known about the data in addition to the observations. The side information helps by adding observed entries to the factored matrices. We also introduce a nonparametric mixture model for the prior of the rows and columns of the factored matrices that gives a different regularization for each latent class. Besides providing a richer prior, the posterior distribution of mixture assignments reveals the latent classes. Using Gibbs sampling for inference, we apply our model to the Netflix Prize problem of predicting movie ratings given an incomplete user-movie ratings matrix. Incorporating rating information with gathered metadata information, our Bayesian approach outperforms other matrix factorization techniques even when using fewer dimensions.

Although falls are undesirable in humanoid robots, they are also inevitable, especially as robots get deployed in physically interactive human environments. We consider the problem of fall prediction, i.e., to predict if a robot's balance controller can prevent a fall from the current state. A trigger from the fall predictor is used to switch the robot from a balance maintenance mode to a fall control mode. Hence, it is desirable for the fall predictor to signal imminent falls with sufficient lead time before the actual fall, while minimizing false alarms. Analytical techniques and intuitive rules fail to satisfy these competing objectives on a large robot that is subjected to strong disturbances and therefore exhibits complex dynamics. Today effective supervised learning tools are available for finding patterns in high-dimensional data. Our paper contributes a novel approach to engineer fall data such that a supervised learning method can be exploited to achieve reliable prediction. Specifically, we introduce parameters to control the tradeoff between the false positive rate and lead time. Several parameter combinations yield solutions that improve both the false positive rate and the lead time of hand-coded solutions. Learned predictors are decision lists with typical depths of 5-10, in a 16-dimensional feature space. Experiments are carried out in simulation on an Asimo-like robot.