Learning representations from data is one of the fundamental problems of artificial intelligence and machine learning. Many different approaches exist for learning representations, but what constitutes a good representation is not yet well understood. In this work, we view the problem of representation learning as one of learning features (e.g., hidden units of neural networks) such that performance of the underlying base system continually improves. We study an important case where learning is done fully online (i.e., on an example-by-example basis) from an unending stream of data, and the computational cost of the learning element should not grow with time or cannot be much more than that of the performance element. Few methods can be used effectively in this case. We show that a search approach to representation learning can naturally fit with this setting. In this approach good representations are searched by generating different features and then testing them for utility. We develop new representation-search methods and show that the generate-and-test approach can be utilized in a simple and effective way for continually improving representations. Our methods are fully online and add only a small fraction to the overall computation. We believe online representation search constitutes an important step toward effective and inexpensive solutions to representation learning problems.

This paper introduces a novel approach for abstraction selection in reinforcement learning problems modelled as factored Markov decision processes (MDPs), for which a state is described via a set of state components. In abstraction selection, an agent must choose an abstraction from a set of candidate abstractions, each build up from a different combination of state components.

We suggest to employ propositional satisfiability techniques in solving a problem of cooperative multi-robot path-finding optimally. Several propositional encodings of path-finding problems have been suggested recently. In this paper we evaluate how efficient these encodings are in solving certain cases of cooperative path-findings problems optimally. Particularly, a case where robots have multiple optional locations as their targets is considered in this paper.

In this paper, we present an efficient algorithm for verifying path-consistency on a binary constraint network. The complexities of our algorithm beat the previous conjectures on the lower bounds for verifying path-consistency. We therefore defeat the proofs for several published results that incorrectly rely on these conjectures. Our algorithm is motivated by the idea of reformulating path-consistency verification as fast matrix multiplication. Further, for a computational model that counts arithmetic operations (rather than bit operations), a clever use of the properties of prime numbers allows us to design an even faster variant of the algorithm. Based on our algorithm, we hope to inspire a new class of techniques for verifying and even establishing varying levels of local-consistency on given constraint networks.

Many real-world applications require the successful combination of spatial and temporal reasoning. In this paper, we study the general framework of the Traveling Salesman Problem with Simple Temporal Constraints. Representationally, this framework subsumes the Traveling Salesman Problem, Simple Temporal Problems, as well as many of the frameworks described in the literature. We analyze the theoretical properties of the combined problem providing strong inapproximability results for the general problem, and positive results for some special cases.

In this paper, a new approach for clauses learning is proposed. By traversing the implication graph sepa- rately from x and ¬x, we derive a new class of bi-asserting clauses that can lead to a more compact implication graph. These new kinds of bi-asserting clauses are much shorter and tend to induce more implications than the classical bi-asserting clauses. Experimental results show that exploiting this new class of bi-asserting clauses improves the performance of state-of-the-art SAT solvers particularly on crafted instances.

Many works have studied the properties of CSPs which are based on the structures of constraint networks, or based on the features of compatibility relations. Studies on structures rely generally on properties of graphs for binary CSPs and on properties of hypergraphs for the general case, that is CSPs with constraints of arbitrary arity. In the second case, using the dual representation of hypergraphs, that is a reformulation of the instances, we can exploit notions and properties of graphs. For the studies of compatibility relations, the exploitation of properties of graphs is possible studying a graph called microstructure which allows to reformulate instances of binary CSP. Unfortunately, this approach is limited to CSPs with binary constraints. In this paper, we propose theoretical tools based on graphs to represent microstructures for the general case. This approach avoids to exploit directly hypergraphs, even if the microstructure based on hypergraphs has already been mentioned in (Cohen 2003). The advantage of such an approach is that the literature of Graph Theory is really more extended than one of Hypergraph Theory. Thus the theoretical results and efficient algorithms are more numerous, offering a larger number of existing tools which can be operated. We introduce here three possible definitions of microstructures based on graphs. We show how these representations can form new theoretical tools to generalize a number of results already obtained on binary CSPs. We think that these representations should be of interest for the community, firstly for the generalization of existing results, but also to obtain original results for CSPs with constraints of arbitrary arity.

AI Planning is inherently hard and hence it is desirable to derive as much information as we can from the structure of the planning problem and let this information be exploited by a planner. Many recent planners use the finite-domain state-variable representation of the problem instead of the traditional propositional representation. However, most planning problems are still specified in the propositional representation due to the widespread modeling language PDDL and it is hard to generate a compact and computationally efficient state variable representation from the propositional model. In this paper we propose a novel method for automaticallygenerating an efficient state-variable representation from the propositional representation. This method groups sets of propositions into state variables based onthe mutex relations introduced in the planning graph. As we shall show experimentally, our method outperforms the current state-of-the-art method both in the smaller number of generated state variables and in the increased performance of planners.

In Automated Planning, learning and exploiting additional knowledge within a domain model, in order to improve plan generation speed-up and increase the scope of problems solved, has attracted much research. Reformulation techniques such as those based on macro-operators or entanglements are very promising because they are to some extent domain model and planning engine independent. This paper aims to exploit recent work on inner entanglements, relations between pairs of planning operators and predicates encapsulating exclusivity of predicate `achievements` or `requirements', for generating macro-operators. We discuss conditions which are necessary for generating such macro-operators and conditions that allow removing primitive operators without compromising solvability of a given (class of) problem(s). The effectiveness of our approach will be experimentally shown on a set of well-known benchmark domains using several high-performing planning engines.

Analysing the structures of solution plans generated by AI Planning engines is helpful in improving the generative planning process, as well as shedding light in the study of its theoretical foundations. We investigate a specific property of solution plans, that we called linearity, which refers to a situation where each action achieves an atom (or atoms) for a directly following action, or achieves goal atom(s). Similarly, linearity can be defined for parallel plans where each action in a set of actions executed at some time step, achieves either goal atom(s) or atom(s) for some action executed in the directly following time step. In this paper, we present a general and problem-independent theoretical framework focusing on the analysis of planning operator schema, namely relations of achiever, clobberer and independence, in order to determine whether solvable planning problems using a given operator schema have as solutions optimal (parallel) plans which are linear. The findings presented in this paper deepen current theoretical knowledge, provide helpful information to engineers of new planning domain models, and suggest new ways of improving the performance of state-of-the-art (optimal) planning engines.