Partial-order schedules are valued because they are flexible, and therefore more robust to unexpected delays. Previous work has indicated that constructing partial-order schedules by a two-stage method, in which a fixed-time schedule is first found and a partial order then lifted from it, is far more efficient than constructing them directly by a least-commitment partial-order scheduling algorithm. However, the two-stage method is limited to exploring only a fraction of the space of partial-order schedules, namely those that can be obtained from the given fixed-time schedule. We introduce a novel constraint formulation of partial-order scheduling, which establishes explicit resource-providing "links" between activities instead of detecting and eliminating potential resource conflicts. We show that this yields an algorithm that is much faster than previous (precedence constraint posting) partial-order scheduling methods, and comparable to the two-stage method in terms of the quality and robustness of the schedules it finds. This algorithm is also complete, and because it searches the entire space of partial-order schedules, can be adapted to optimising different robustness criteria.

Applying learning techniques to acquire action models is an area of intense research interest. Most previous works in this area have assumed that there is a significant amount of training data available in a planning domain of interest, which we call target domain, where action models are to be learned. However, it is often difficult to acquire sufficient training data to ensure that the learned action models are of high quality. In this paper, we develop a novel approach to learning action models with limited training data in the target domain by transferring knowledge from related auxiliary or source domains. We assume that the action models in the source domains have already been created before, and seek to transfer as much of the the available information from the source domains as possible to help our learning task. We first exploit a Web searching method to bridge the target and source domains, such that transferrable knowledge from source domains is identified. We then encode the transferred knowledge together with the available data from the target domain as constraints in a maximum satisfiability problem, and solve these constraints using a weighted MAX-SAT solver. We finally transform the solutions thus obtained into high-quality target-domain action models. We empirically show that our transfer-learning based framework is effective in several domains, including the International Planning Competition (IPC) domains and some synthetic domains.

Considering directed graphs on n vertices and m edges with real (possibly negative) weights, we present two new, efficient algorithms for computing all-pairs shortest paths (APSP). These algorithms make use of directed path consistency (DPC) along a vertex ordering d. The algorithms run in O(n 2 w d ) time, where w d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n 2 ) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. We show empirically that also in many general cases, both constructed and from realistic benchmarks, the algorithms often outperform Johnson's algorithm, which represents the current state of the art with a run time of O(nm + n 2 log n). These algorithms can be used for temporal and spatial reasoning, e.g. for the Simple Temporal Problem (STP), which underlines its relevance to the planning and scheduling community.

We address a scheduling problem in the context of military aircraft maintenance where the goal is to meet the aircraft requirements for a number of missions in the presence of breakdowns. The assignment of aircraft to a mission must consider the requirements for the mission, the probability of aircraft failure, and capacity of the repair shop that maintains the aircraft. Therefore, a solution both assigns aircraft to missions and schedules the repair shop to meet the assignments. We propose a dispatching heuristic algorithm; three complete approaches based on mixed integer programming, constraint programming, and logic-based Benders decomposition; and a hybrid heuristic-complete approach. Experiments demonstrate that the logic-based Benders variation combining mixed integer programming and constraint programming outperforms the other approaches, that the dispatching heuristic can feasibly schedule the repair shop in a very short time, and that using the dispatching solution as a bound marginally improves the complete approaches.

We discuss and evaluate metrics for difficulty rating of Sudoku puzzles. The correlation coefficient with human performance for our best metric is 0.95. The data on human performance were obtained from three web portals and they comprise thousands of hours of human solving over 2000 problems. We provide a simple computational model of human solving activity and evaluate it over collected data. Using the model we show that there are two sources of problem difficulty: complexity of individual steps (logic operations) and structure of dependency among steps. Beside providing a very good Sudoku-tuned metric, we also discuss a metric with few Sudoku-specific details, which still provides good results (correlation coefficient is 0.88). Hence we believe that the approach should be applicable to difficulty rating of other constraint satisfaction problems.

Cognitive psychology and artificial intelligence have provided valuable insights into the scope and limitations of human thought and behavior. As technology becomes more of a fixture in our daily routines, advances in artificial intelligence increasingly impact how we think and interact with others. This track is motivated by these two fronts of research: the basic theoretical integration of cognition and artificial intelligence; and its application to real-world domains. As such, the track will cover a wide range of issues. We welcomed submissions in any area where cognition and computers are mutually explored, but especially encouraged work in how humans and computers communicate or how artificial intelligence facilitates communication.

Multi-Attribute Reverse Auctions (MARAs) are excellent protocols to automate negotiation among sellers. Eliciting the buyer0s preferences and determining the winner are both challenging problems for MARAs. To solve these problems, we propose two algorithms namely MAUT* and CP-net*, which are respectively the improvement of the Multi-Attribute Utility Theory (MAUT) and constrained CP-net. The buyers can now express conditional, qualitative as well as quantitative preferences over the item attributes. To evaluate the performance in time of the proposed algorithms, we conduct an experimental study on several problem instances. The results favor MAUT* in most of the cases.

We describe a software tool to select among camera feeds from multiple virtual cameras in a virtual environment using semiring constraint satisfaction problem techniques (SCSP), a soft constraint approach. We show how to encode a designer's preferences, and select the best camera feed even in over-constrained or under-constrained environments. The system functions in real time for dynamic scenes, using only current information (ie. no prediction). To reduce computation costs for a final implementation, the SCSP evaluation can be cached and converted to native code. Our approach is implemented in two virtual environments: a virtual hockey game using a spectator viewpoint, and a virtual 3D maze game using a third person perspective. Comparisons against hard constraints (constraint satisfaction problems) are made.

A parallel plan is a sequence of sets of actions such that any ordering of actions in the sets gives a traditional sequential plan. Parallel planning was popularized by the Graphplan algorithm and it is one of the key components of successful SAT-based planers. SAT-based planners have recently begun to exploit multi-valued state variables – an area which seems traditionally more suited for constraint-based planners – and they improved their performance further. In this paper we propose a novel view of constraint-based planning that uses parallel plans and multi-valued state variables. Rather than starting with the planning graph structure like other parallel planners, this novel approach is based on the idea of timelines and their synchronization.

The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. Cases of the constraint satisfaction problem appear in many fields of study, including artificial intelligence, spatial and temporal reasoning, logic, combinatorics, and algebra. Indeed, the constraint satisfaction problem is flexible in that it admits a number of equivalent formulations. In this paper, we work with the formulation as the relational homomorphism problem: given two similar relational structures A and B, does there exist a homomorphism from A to B? In this formulation, one can view each relation of A as containing variable tuples that are constrained together, and the corresponding relation of B as containing the permissible values for the variable tuples [18]. The constraint satisfaction problem is in general NPhard; this general intractability has motivated the study of restricted versions of the CSP that have various desirable complexity and algorithmic properties.