Using constraint-based local search, we effectively model and efficiently solve the problem of balancing the traffic demands on portions of the European airspace while ensuring that their capacity constraints are satisfied. The traffic demand of a portion of airspace is the hourly number of flights planned to enter it, and its capacity is the upper bound on this number under which air-traffic controllers can work. Currently, the only form of demand-capacity balancing we allow is ground holding, that is the changing of the take-off times of not yet airborne flights. Experiments with projected European flight plans of the year 2030 show that already this first form of demand-capacity balancing is feasible without incurring too much total delay and that it can lead to a significantly better demand-capacity balance.

This paper considers Just-In-Time Job-Shop Scheduling, in which each activity has an earliness and a tardiness cost with respect to a due date. It proposes a constraint programming approach, which includes a novel filtering algorithm and dedicated heuristics. The filtering algorithm uses a machine relaxation to produce a lower bound that can be obtained by solving a Just-In-Time Pert problem. It also includes pruning rules which update the variable bounds and detect precedence constraints. The paper presents experimental results which demonstrate the effectiveness of the approach over a wide range of benchmarks.

The ability to automatically compose Web Services is critical for realising  more complex functionalities.  Several proposals to use automated planning to deal with the problem of service composition have been recently made. We present an approach, based on modelling the problem as a CSP (Constraint  Satisfaction Problem), that accommodates for the use of numeric variables, sensing and incomplete knowledge. We introduce a language for expressing extended goals, equipped with temporal constructs, maintainability properties, and an explicit distinction between sensing and achievement goals, in order to avoid undesirable situations.

In this paper we extend dynamic controllability of temporally-flexible plans to temporally-flexible reactive programs.  We consider three reactive programming language constructs whose behavior depends on runtime observations; conditional execution, iteration, and exception handling. Temporally-flexible reactive programs are distinguished from temporally-flexible plans in that program execution is conditioned on the runtime state of the world.  In addition, exceptions are thrown and caught at runtime in response to violated timing constraints, and handled exceptions are considered successful program executions.  Dynamic controllability corresponds to a guarantee that a program will execute to completion, despite runtime constraint violations and uncertainty in runtime state.  An algorithm is developed which frames the dynamic controllability problem as an AND/OR search tree over possible program executions.  A key advantage of this approach is the ability to enumerate only a subset of possible program executions that guarantees dynamic controllability, framed as an AND/OR solution subtree.

This paper presents multi-goal planning for an autonomous blasthole drill used in open pit mining operations. Given a blasthole pattern to be drilled and constraints on the vehicle's motion and orientation when drilling, we wish to compute the best order in which to drill the given pattern. Blasthole pattern drilling is an asymmetric Traveling Salesman Problem with precedence constraints specifying that some holes must be drilled before others. We wish to find the minimum cost tour according to criteria that minimize the distance travelled satisfying the precedence and vehicle motion constraints. We present an iterative method for solving the blasthole sequencing problem using the combination of a Genetic Algorithm and motion planning simulations that we use to determine the true cost of travel between any two holes.

This paper presents a generic anytime forward-search constraint-based algorithm for solving planning problems expressed in the CNT framework (Constraint Network on Timelines). It is generic because it allows many kinds of search to be covered, from complete tree search to greedy search. It is anytime because some parameter settings, together with domain-specific knowledge, allow high quality plans to be produced very quickly and to be further improved. It is forward because it systematically considers the decisions to be made in a chronological order. It is finally constraint-based because it is built on top of the CNT framework which is an extension of the CSP framework able to model discrete event dynamic systems and because it is implemented on top of the Choco constraint programming tool from which it inherits all the constraint handling machinery. Experimental comparisons are made in terms of quality profile with other domain-dependent and domain-independent planners.

Recently, Helmert and Geffner proposed the context-enhanced additive heuristic, where fact costs are evaluated relative to context states that arise from achieving first a pivot condition of each operator. As Helmert and Geffner pointed out, the method can be generalized to consider contexts arising from arbitrary precedence constraints over operator conditions instead. Herein, we provide such a generalization. We extend Helmert and Geffner's equations, and discuss a number of design choices that arise. Drawing on previous work on goal orderings, we design a family of methods for automatically generating precedence constraints. We run large-scale experiments, showing that the technique can help significantly, depending on the choice of precedence constraints. We shed some light on this by profiling the behavior of all possible precedence constraints, using a sampling technique.

The dispatcher uses the dispatchable form to quickly make dynamic scheduling decisions. As autonomous systems become more capable and common, However, developing flexible executives for plans with they will need to reason about complex tasks and robustly choices, has been more difficult. Kim, Williams, and execute plans in uncertain environments. In previous work, Abramson present an executive called Kirk, which uses a Williams et al. introduced the Reactive Model-Based Programming deliberative planning step to change the execution sequence Language (RMPL), which is designed to allow online (2001). Although their results show improvement engineers to simply and intuitively express the desired behavior over prior planning systems, the latency is still too high for of the system (2003). Then the agent's executive determines tightly coupled systems, for example robots working with the correct sequence of actions to accomplish this humans or walking robots with fast dynamics. Recently, behavior, relieving the programmer of explicitly coding that Shah and Williams extended the compiler and dispatcher logic. RMPL programs often involve temporal constraints model to Temporal Constraint Satisfaction Problems (TCwhich the executives must reason over. SPs), a type of temporal problems with choice, by compactly Kim, Williams, and Abramson previously developed recording the possible set of solutions and efficiently Temporal Plan Networks (TPNs) as a temporal constraint reasoning over the possible options (2008).

Temporally expressive planning, an important class of temporal planning, has attracted much attention lately. Temporally expressive planning is difficult; few existing planners can solve them, as they have highly concurrent actions. We propose an optimal approach to temporally expressive planning based on a SAT formulation of the problem, finding solutions with the shortest time spans. Our experiments on several temporally expressive domains showed that our planner is able to optimally solve many instances in a reasonable amount of time, comparing favorably to existing temporally expressive planners. Our second result is a temporally expressive planning problem formulation of the Peer-to-Peer (P2P) network communications. In addition to demonstrating a better performance of our new method than the only existing temporally expressive planners on several temporally expressive problem domains, we apply our new planner to find optimal communication schedules for P2P networks. Our results will be potentially useful for designing efficient communication protocols in P2P networks.

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.