It has long been recognized that users can have complex preferences on plans.  Non-intrusive learning of such preferences by observing the plans executed by the user is an attractive idea. Unfortunately, the executed plans are often not a true representation of user preferences, as they result from the interaction between user preferences and feasibility constraints. In the travel planning scenario, a user whose true preference is to travel by a plane may well be frequently observed traveling by car because of feasibility constraints (perhaps the user is a poor graduate student). In this work, we describe a novel method for learning true user preferences obfuscated by such feasibility constraints.  Our base learner induces probabilistic hierarchical task networks (pHTNs) from sets of training plans. Our approach is to rescale the input so that it represents the user's preference distribution on plans rather than the observed distribution on plans.

Despite the extensive development of first-principles planning in recent years, planning applications are still primarily developed using knowledge-based planners which can exploit domain-specific heuristics and weaker domain models.  Hierarchical Task Network (HTN) planners capture domain-specific heuristics for more efficient search, accommodate incomplete causal models, and can be used to enforce standard operating procedures.  Unfortunately, we do not have semantics for the methods or tasks that make up HTN models, that help evaluate the correctness of methods, or to build a reliable executive for HTN plans.  This paper fills the gap by providing a well-defined semantics for the methods and plans of SHOP2, a state-of-the-art HTN planner.  The semantics are defined in terms of concurrent golog (ConGolog) and the situation calculus.  We provide a proof of equivalence between the plans generated by SHOP2 and the action sequences of the ConGolog semantics.  We show how the semantics reflects the distinction between plan-time and execution-time, and provide some simple examples showing how the semantics can support method verification.  The semantics provide an implementation-neutral specification for an executive, showing how an executive must treat the plans SHOP2 generates in order to enforce the expected behaviors.  Future directions include automated verification of method specifications, automatically generating plan monitors, and plan revision and repair.

The problem of formulating knowledge bases containing action schema is a central concern in knowledge engineering for AI Planning. This paper describes LOCM, a system which carries out the automated induction of action schema from sets of example plans.  Each plan is assumed to be a sound sequence of actions; each action in a plan is stated as a name and a list of objects that the action refers to. LOCM exploits the assumption that actions change the state of objects, and require objects to be in a certain state before they can be executed.  The novelty of LOCM is that it can induce action schema without being provided with any information about predicates or initial, goal or intermediate state descriptions for the example action sequences.  In this paper we describe the implemented LOCM algorithm, and analyse its performance by its application to the induction of domain models for several domains. To evaluate the algorithm, we used random action sequences from existing models of domains, as well as solutions to past IPC problems.

We introduce a Bernstein-type inequality which serves to uniformly control quadratic forms of gaussian variables. The latter can for example be used to derive sharp model selection criteria for linear estimation in linear regression and linear inverse problems via penalization, and we do not exclude that its scope of application can be made even broader.

Let M be a random (alpha n) x n matrix of rank r<

We study the termination problem of the chase algorithm, a central tool in various database problems such as the constraint implication problem, Conjunctive Query optimization, rewriting queries using views, data exchange, and data integration. The basic idea of the chase is, given a database instance and a set of constraints as input, to fix constraint violations in the database instance. It is well-known that, for an arbitrary set of constraints, the chase does not necessarily terminate (in general, it is even undecidable if it does or not). Addressing this issue, we review the limitations of existing sufficient termination conditions for the chase and develop new techniques that allow us to establish weaker sufficient conditions. In particular, we introduce two novel termination conditions called safety and inductive restriction, and use them to define the so-called T-hierarchy of termination conditions. We then study the interrelations of our termination conditions with previous conditions and the complexity of checking our conditions. This analysis leads to an algorithm that checks membership in a level of the T-hierarchy and accounts for the complexity of termination conditions. As another contribution, we study the problem of data-dependent chase termination and present sufficient termination conditions w.r.t. fixed instances. They might guarantee termination although the chase does not terminate in the general case. As an application of our techniques beyond those already mentioned, we transfer our results into the field of query answering over knowledge bases where the chase on the underlying database may not terminate, making existing algorithms applicable to broader classes of constraints.

Symmetry is an important feature of many constraint programs. We show that any symmetry acting on a set of symmetry breaking constraints can be used to break symmetry. Different symmetries pick out different solutions in each symmetry class. We use these observations in two methods for eliminating symmetry from a problem. These methods are designed to have many of the advantages of symmetry breaking methods that post static symmetry breaking constraint without some of the disadvantages. In particular, the two methods prune the search space using fast and efficient propagation of posted constraints, whilst reducing the conflict between symmetry breaking and branching heuristics. Experimental results show that the two methods perform well on some standard benchmarks.

We study decompositions of NVALUE, a global constraint that can be used to model a wide range of problems where values need to be counted. Whilst decomposition typically hinders propagation, we identify one decomposition that maintains a global view as enforcing bound consistency on the decomposition achieves bound consistency on the original global NVALUE constraint. Such decompositions offer the prospect for advanced solving techniques like nogood learning and impact based branching heuristics. They may also help SAT and IP solvers take advantage of the propagation of global constraints.

We investigate the issue of model selection and the use of the nonconformity (strangeness) measure in batch learning. Using the nonconformity measure we propose a new training algorithm that helps avoid the need for Cross-Validation or Leave-One-Out model selection strategies. We provide a new generalisation error bound using the notion of nonconformity to upper bound the loss of each test example and show that our proposed approach is comparable to standard model selection methods, but with theoretical guarantees of success and faster convergence. We demonstrate our novel model selection technique using the Support Vector Machine.

In the context of clustering, we consider a generative model in a Euclidean ambient space with clusters of different shapes, dimensions, sizes and densities. In an asymptotic setting where the number of points becomes large, we obtain theoretical guaranties for a few emblematic methods based on pairwise distances: a simple algorithm based on the extraction of connected components in a neighborhood graph; the spectral clustering method of Ng, Jordan and Weiss; and hierarchical clustering with single linkage. The methods are shown to enjoy some near-optimal properties in terms of separation between clusters and robustness to outliers. The local scaling method of Zelnik-Manor and Perona is shown to lead to a near-optimal choice for the scale in the first two methods. We also provide a lower bound on the spectral gap to consistently choose the correct number of clusters in the spectral method.