AI planning techniques often require a given set of action models provided as input. Creating action models is, however, a difficult task that costs much manual effort. The problem of action-model acquisition has drawn a lot of interest from researchers in the past. Despite the success of the previous systems, they are all based on the assumption that there are enough training examples for learning high-quality action models. In many real-world applications, e.g., military operation, collecting a large amount of training examples is often both difficult and costly. Instead of collecting training examples, we assume there are abundant annotators, i.e., the crowd, available to provide information learning action models. Specifically, we first build a set of soft constraints based on the labels (true or false) given by the crowd or annotators. We then builds a set of soft constraints based on the input plan traces. After that we put all the constraints together and solve them using a weighted MAX-SAT solver, and convert the solution of the solver to action models. We finally exhibit that our approach is effective in the experiment.

We propose two local consistencies that extend bounds consistency (BC) by simultaneously considering combinations of constraints as opposed to single constraints. We prove that these two local consistencies are both stronger than BC, but are NP-hard to enforce even when constraints are linear. Hence, we propose two polynomial-time techniques to enforce approximations of these two consistencies on linear constraints. One is a reformulation of the constraints on which we enforce BC whereas the other is a polynomial time algorithm. Both achieve stronger pruning than BC. Our experiments show large differences in favor of our approaches.

Lazy Clause Generation (LCG) solvers dominate the current constraint programming competitions. These solvers successfully combine systematic propagation based search, global constraints and conflict clause learning from SAT solving into a hybrid approach. My research project extends the LCG methodology by using a mix of eager and lazy encodings and a richer set of constraint decompositions. Global Constraints exhibit a whole hierarchy of different decomposition into more basic constraints. In our work we want to take advantage of such hierarchies and identify criteria on how constraints could be decomposed before and during search.

In this game, each player deal with enormous sizes such as a smart grid is rapidly increasing associated with a variable keeps providing probability distributions in AI communities. The distributed constraint optimization over its domain, and tries to minimize the regret, problem (DCOP for short) is arguably the most which is the average additional cost incurred by the probability studied problem in this setting, where the goal is to find an distributions against the strategy of outputting a best assignment that minimizes the total sum of costs incurred single value all the time. We can make the regret of each by (local) cost functions. Since it takes a prohibitively long agent arbitrarily small by utilizing the multiplicative weights time to exactly solve DCOP, we need to resort to incomplete method. Finally, we round the obtained probability distributions algorithms, and a plethora of incomplete algorithms to integer values. We prove that our method converges have been proposed in the literature, such as local search to a certain kind of equilibrium, called a coarse correlated based algorithms (Maheswaran, Pearce, and Tambe 2004; equilibrium. Zhang et al. 2005), inference based algorithms (Farinelli We empirically compare our methods with previous stateof-the-art et al. 2008), graph based algorithms (Bowring et al. 2008; methods. We demonstrate that our methods are Kiekintveld et al. 2010), divide-and-coordinate based algorithms scalable, and that DMW-Game outperforms other methods (Vinyals, Rodriguez-Aguilar, and Cerquides 2010; in terms of solution quality and efficiency. Hatano and Hirayama 2013), and sampling based algorithms (Ottens, Dimitrakakis, and Faltings 2012; Nguyen, Yeoh, and Lau 2013).

We propose an auction algorithm to allocate tasks that have temporal constraints to cooperative robots. Temporal constraints are expressed as time windows, within which a task must be executed. There are no restrictions on the time windows, which are allowed to overlap. Robots model their temporal constraints using a simple temporal network, enabling them to maintain consistent schedules. When bidding on a task, a robot takes into account its own current commitments and an optimization objective, which is to minimize the time of completion of the last task alone or in combination with minimizing the distance traveled. The algorithm works both when all the tasks are known upfront and when tasks arrive dynamically. We show the performance of the algorithm in simulation with different numbers of tasks and robots, and compare it with a baseline greedy algorithm and a state-of-the-art auction algorithm. Our algorithm is computationally frugal and consistently allocates more tasks than the competing algorithms.

In Constraint Processing, many algorithms for enforcing the same level of local consistency may exist. The performance of those algorithms varies widely. In order to understand what problem features lead to better performance of one algorithm over another, we utilize an algorithm configurator to tune the parameters of a random problem generator and maximize the performance difference of two consistency algorithms for enforcing constraint minimality. Our approach allowed us to generate instances that run 1000 times faster for one algorithm over the other.

Model-Based Diagnosis techniques have been successfully applied to support a variety of fault-localization tasks both for hardware and software artifacts. In many applications, Reiter's hitting set algorithm has been used to determine the set of all diagnoses for a given problem. In order to construct the diagnoses with increasing cardinality, Reiter proposed a breadth-first search scheme in combination with different tree-pruning rules. Since many of today's computing devices have multi-core CPU architectures, we propose techniques to parallelize the construction of the tree to better utilize the computing resources without losing any diagnoses. Experimental evaluations using different benchmark problems show that parallelization can help to significantly reduce the required running times. Additional simulation experiments were performed to understand how the characteristics of the underlying problem structure impact the achieved performance gains.

Flexibility in agent scheduling increases the resilience of temporal plans in the face of new constraints. However,current metrics of flexibility ignore domain knowledge about how such constraints might arise in practice, e.g., due to the uncertain duration of a robot’s transitiontime from one location to another. Probabilistic temporalplanning accounts for actions whose uncertain durations can be modeled with probability density functions. We introduce a new metric called robustness that measures the likelihood of success for probabilistic temporalplans. We show empirically that in multi-robot planning,robustness may be a better metric for assessing the quality of temporal plans than flexibility, thus reframing many popular scheduling optimization problems.

Temporal uncertainty in large-scale logistics forces one to trade off between lost efficiency through built-in slack and costly replanning when deadlines are missed. Due to the difficulty of reasoning about such likelihoods and consequences, a computational framework is needed to quantify and bound the risk of violating scheduling requirements. This work addresses the chance-constrained scheduling problem, where actions' durations are modeled probabilistically. Our solution method uses conflict-directed risk allocation to efficiently compute a scheduling policy. The key insight, compared to previous work in probabilistic scheduling, is to decouple the reasoning about temporal and risk constraints. This decomposes the problem into a separate master and subproblem, which can be iteratively solved much quicker. Through a set of simulated car-sharing scenarios, it is empirically shown that conflict-directed risk allocation computes solutions nearly an order of magnitude faster than prior art, which considers all constraints in a single lump-sum optimization.

A homography matrix is used in computer vision field to solve the correspondence problem between a pair of stereo images. RANSAC algorithm is often used to calculate the homography matrix by randomly selecting a set of features iteratively. CS-RANSAC algorithm in this paper converts RANSAC algorithm into two-layers. The first layer is addressing sampling problem which we can describe our knowledge about degenerate features by mean of Constraint Satisfaction Problems (CSP). By dividing the input image into a N X N grid and making feature points into discrete domains, we can model the image into the CSP model to efficiently filter out degenerate feature samples using CSP in the first layer, so that computer has knowledge about how to skip computing the homography matrix in the model estimation step for the second layer. The experimental results show that the proposed CS-RANSAC algorithm can outperform the most of variants of RANSAC without sacrificing its execution time.