Symbolic search using BDDs usually saves huge amounts of memory, while in some domains its savings are moderate at best. It is an open problem to determine if BDDs work well for a certain domain. Motivated by finding evidences for BDD growths for state space search, in this paper we are concerned with symbolic search in the domain of Connect Four. We prove that there is a variable ordering for which the set of all possible states – when continuing after a terminal state has been reached – can be represented by polynomial sized BDDs, whereas the termination criterion leads to an exponential number of nodes in the BDD given any variable ordering.

We consider the problem of routing electric vehicles (EV) in the most energy-efficient way within a road network taking into account both their limited energy supply as well as their ability to recuperate energy. Employing a classical result by Johnson and an observation about Dijkstra under non-constant edge costs we obtain O(n log n +m) query time after a O(nm) preprocessing phase for any road network graph whose edge costs represent energy consumption or recuperation.If the energy recuperation is height induced in a very natural way,the preprocessing phase can even be omitted. We then adapt a technique for speeding-up (unconstrained) shortest path queries to our scenario to achieve a speed-up of another factor of around 20. Our results drastically improve upon the recent results in (Artmeier et al. 2010) and allow for route planning of EVs in an instant even on large networks.

Automated feature discovery is a fundamental problem in machine learning. Although classical feature discovery methods do not guarantee optimal solutions in general, it has been recently noted that certain subspace learning and sparse coding problems can be solved efficiently, provided the number of features is not restricted a priori. We provide an extended characterization of this optimality result and describe the nature of the solutions under an expanded set of practical contexts. In particular, we apply the framework to a semi-supervised learning problem, and demonstrate that feature discovery can co-occur with input reconstruction and supervised training while still admitting globally optimal solutions. A comparison to existing semi-supervised feature discovery methods shows improved generalization and efficiency.

This paper extends existing plan recognition research to handle plans containing loops. We supply an encoding of plans with loops for recognition, based on techniques used to parse lexicalized grammars, and demonstrate its effectiveness empirically. To do this, the paper first shows how encoding plan libraries as context free grammars permits the application of standard rewriting techniques to remove left recursion and ε-productions, thereby enabling polynomial time parsing. However, these techniques alone fail to provide efficient algorithms for plan recognition. We show how the loop-handling methods from formal grammars can be extended to the more general plan recognition problem and provide a method for encoding loops in an existing plan recognition system that scales linearly in the number of loop iterations.

Aggregate factors (that is, those based on aggregate functions such as SUM, AVERAGE, AND etc.) in probabilistic relational models can compactly represent dependencies among a large number of relational random variables. However, propositional inference on a factor aggregating n k -valued random variables into an r -valued result random variable is O ( r k 2 n ). Lifted methods can ameliorate this to O ( r n k ) in general and O ( r k log n ) for commutative associative aggregators. In this paper, we propose (a) an exact solution constant in n when k  = 2 for certain aggregate operations such as AND, OR and SUM, and (b) a close approximation for inference with aggregate factors with time complexity constant in n . This approximate inference involves an analytical solution for some operations when k > 2. The approximation is based on the fact that the typically used aggregate functions can be represented by linear constraints in the standard ( k  –1)-simplex in R k where k is the number of possible values for random variables. This includes even aggregate functions that are commutative but not associative (e.g., the MODE operator that chooses the most frequent value). Our algorithm takes polynomial time in k (which is only 2 for binary variables) regardless of r and n, and the error decreases as n increases. Therefore, for most applications (in which a close approximation suffices) our algorithm is a much more efficient solution than existing algorithms. We present experimental results supporting these claims. We also present a (c) third contribution which further optimizes aggregations over multiple groups of random variables with distinct distributions.

Students have implemented approaches to these problems, using our HRTeam framework (Sklar et al. 2010), which is built on Player/Stage (Vaughan and Gerkey 2007).

We consider settings in which a semi-autonomous agent has uncertain knowledge about its environment, but can ask what action the human operator would prefer taking in the current or in a potential future state. Asking queries can improve behavior, but if queries come at a cost (e.g., due to limited operator attention), the value of each query should be maximized. We compare two strategies for selecting action queries: 1) based on myopically maximizing expected gain in long-term value, and 2) based on myopically minimizing uncertainty in the agent's policy representation. We show empirically that the first strategy tends to select more valuable queries, and that a hybrid method can outperform either method alone in settings with limited computation.

We present a computational method to generate explanations to answers of complex queries over biomedical ontologies and databases, using the high-level representation and efficient automated reasoners of Answer Set Programming. We show the applicability of our approach with some queries related to drug discovery over PHARMGKB, DRUGBANK, BIOGRID, CTD and SIDER.

Partially supervised text classification has received great research attention since it only uses positive and unlabeled examples as training data. This problem can be solved by automatically labeling some negative (and more positive) examples from unlabeled examples before training a text classifier. But it is difficult to guarantee both high quality and quantity of the new labeled examples. In this paper, a multi-level example based learning method for partially supervised text classification is proposed, which can make full use of all unlabeled examples. A heuristic method is proposed to assign possible labels to unlabeled examples and partition them into multiple levels according to their labeling confidence. A text classifier is trained on these multi-level examples using weighted support vector machines. Experiments show that the multi-level example based learning method is effective for partially supervised text classification, and outperforms the existing popular methods such as Biased-SVM, ROC-SVM, S-EM and WL.

Much recent work in satisficing planning has aimed at striking a balance between coverage - solving as many problems as possible - and plan quality. Current planners achieve near perfect coverage on the latest IPC benchmarks. It is therefore natural to investigate their scaling behavior on more difficult instances. Among state of the art planners, LAMA (Richter, Helmert, and Westphal 2008) is able to generate high quality plans, but its coverage drops off rapidly with increasing prob- lem complexity. The Arvand planner (Nakhost and Müller 2009) scales to much harder instances but generates lower quality plans. This paper introduces a new algorithm, Monte Carlo Random Walk-based Local Tree Search (MRW-LTS), which uses random walks to selectively build local search trees. Experiments demonstrate that MRW-LTS combines a scaling behavior that is better than LAMA’s with a plan quality that is better than Arvand’s.