Search

The multi-agent pathfinding (MAPF) problem has attracted considerable attention because of its relation to practical applications. The majority of solutions for MAPF are algorithmic. Recently, declarative solutions that reduce MAPF to encodings for off-the-shelf solvers have achieved remarkable success. We present a constraint-based declarative model for MAPF, together with its implementation in Picat, which uses SAT and MIP. We consider both the makespan and the sum-of-costs objectives, and propose a preprocessing technique for improving the performance of the model. Experimental results show that the implementation using SAT is highly competitive. We also analyze the high performance of the SAT solution by relating it to the SAT encoding algorithms that are used in the Picat compiler.

In order to achieve both fast and coordinated data transfer to collaborative sites as well as to create a distribution of data over multiple sites, efficient data movement is one of the most essential aspects in distributed environment. With such capabilities at hand, truly distributed task scheduling with minimal latencies would be reachable by internationally distributed collaborations (such as ones in HENP) seeking for scavenging or maximizing on geographically spread computational resources. But it is often not all clear (a) how to move data when available from multiple sources or (b) how to move data to multiple compute resources to achieve an optimal usage of available resources. We present a method of creating a Constraint Programming (CP) model consisting of sites, links and their attributes such as bandwidth for grid network data transfer also considering user tasks as part of the objective function for an optimal solution. We will explore and explain trade-off between schedule generation time and divergence from the optimal solution and show how to improve and render viable the solution's finding time by using search tree time limit, approximations, restrictions such as symmetry breaking or grouping similar tasks together, or generating sequence of optimal schedules by splitting the input problem. Results of data transfer simulation for each case will also include a well known Peer-2-Peer model, and time taken to generate a schedule as well as time needed for a schedule execution will be compared to a CP optimal solution. We will additionally present a possible implementation aimed to bring a distributed datasets (multiple sources) to a given site in a minimal time., 10 pages; ACAT 2008 workshop

Global constraints proved themselves to be an efficient tool for modelling and solving large-scale real-life combinatorial problems. They encapsulate a set of binary constraints and using global reasoning about this set they filter the domains of involved variables better than arc consistency among the set of binary constraints. Moreover, global constraints exploit semantic information to achieve more efficient filtering than generalised consistency algorithms for n-ary constraints. Continued expansion of constraint programming (CP) to various application areas brings new challenges for design of global constraints. In particular, application of CP to advanced planning and scheduling (APS) requires dynamic additions of new variables and constraints during the process of constraint satisfaction and, thus, it would be helpful if the global constraints could adopt new variables. In the paper, we give a motivation for such dynamic global constraints and we describe a dynamic version of the well-known alldifferent constraint., 11 pages. Proceedings ERCIM WG on Constraints (Prague, June 2001)

How humans reason about syllogistic statements is a problem that currently lacks a comprehensive, universally accepted explanatory theory. The goal of this article is twofold: First, it sheds light on the actual predictive quality of existing theories by providing a standardized implementation of a subset of them. To that end, the theories are algorithmically formalized, including their capabilities for adaptation to an individual reasoner. The implementations are modular with regard to mental operations defined by the cognitive theories. Based on such operations, a novel composite approach is devised, resulting in a prediction model for predicting an individual reasoner before she draws the inference. It uses sequences of operations, selected from possibly different theories, to form its predictions. Among the basic models, our implementations of PHM, mReasoner and Verbal Models make the best predictions. The composite model is able to significantly surpass it by exploiting synergies between different models. Therefore, the composite approach is a promising tool to model and study syllogistic reasoning and possibly other reasoning tasks as well.