The study of phase transition phenomenon of NP complete problems plays an important role in understanding the nature of hard problems. In this paper, we follow this line of research by considering the problem of counting solutions of Constraint Satisfaction Problems (#CSP). We consider the random model, i.e. RB model. We prove that phase transition of #CSP does exist as the number of variables approaches infinity and the critical values where phase transitions occur are precisely located. Preliminary experimental results also show that the critical point coincides with the theoretical derivation. Moreover, we propose an approximate algorithm to estimate the expectation value of the solutions number of a given CSP instance of RB model.

We extend the precedence constraints contexts heuristic (hpcc) to a temporal and numeric setting, and propose rules to account precedence constraints among comparison variables and logical variables. Experimental results on benchmark domains show that our extension has the potential to lead to better plan quality than that with the heuristic proposed by Eyerich and others.

Model-based diagnosis (MBD) uses an abstraction of system to diagnose possible faulty functions of an underlying system. To improve the solution efficiency for multi-fault diagnosis problems, especially for large scale systems, this paper proposes a method to induce reasonable diagnosis solutions, under coarse diagnosis, by using the relationships between system outputs and components. Compared to existing diagnosis methods, the proposed framework only needs to consider associations between outputs and components by using an assumption-based truth maintenance system (ATMS) [de Kleer 1986] to obtain correlation components for every output node. As a result, our method significantly reduces the number of variables required for model diagnosis, which makes it suitable for large scale circuit systems.

Automatic semantic annotation of structured data enables unsupervised integration of data from heterogeneous sources but is difficult to perform accurately due to the presence of many numeric fields and proper-noun fields that do not allow reference-based approaches and the absence of natural language text that prevents the use of language-based approaches. In addition, several of these semantic types have multiple heterogeneous representations, while sharing syntactic structure with other types. In this work, we propose a new approach to use conditional random fields (CRFs) to perform semantic annotation of structured data that takes advantage of the structure and labels of the tokens for higher accuracy of field labeling, while still allowing the use of exact inference techniques. We compare our approach with a linear-CRF based model that only labels fields and also with a regular-expression based approach.

An ad hoc team setting is one in which teammates must work together to obtain a common goal, but without any prior agreement regarding how to work together. In this abstract we present a role-based approach for ad hoc teamwork, in which each teammate is inferred to be following a specialized role that accomplishes a specific task or exhibits a particular behavior. In such cases, the role an ad hoc agent should select depends both on its own capabilities and on the roles currently selected by the other team members. We present methods for evaluating the influence of the ad hoc agent's role selection on the team's utility and we examine empirically how to select the best suited method for role assignment in a complex environment. Finally, we show that an appropriate assignment method can be determined from a limited amount of data and used successfully in similar new tasks that the team has not encountered before.

In this paper, we investigate the hybrid tractability of binary Quantified Constraint Satisfaction Problems (QCSPs). First, a basic tractable class of binary QCSPs is identified by using the broken-triangle property. In this class, the variable ordering for the broken-triangle property must be same as that in the prefix of the QCSP. Second, we break this restriction to allow that existentially quantified variables can be shifted within or out of their blocks, and thus identify some novel tractable classes by introducing the broken-angle property. Finally, we identify a more generalized tractable class, i.e., the min-of-max extendable class for QCSPs.

Active learning traditionally relies on instance based utility measures to rank and select instances for labeling, which may result in labeling redundancy. To address this issue, we explore instance utility from two dimensions: individual uncertainty and instance disparity, using a correlation matrix. The active learning is transformed to a semi-definite programming problem to select an optimal subset with maximum utility value. Experiments demonstrate the algorithm performance in comparison with baseline approaches.

This work focuses on developing domain-independent heuristics for probabilistic planning problems characterized by full observability and non-deterministic effects of actions that are expressed by probability distributions. The approach is to first search for a high probability deterministic plan using a classical planner. A novel probabilistic plan graph heuristic is used to guide the search towards high probability plans. The resulting plans can be used in a system that handles unexpected outcomes by runtime replanning. The plans can also be incrementally augmented with contingency branches for the most critical action outcomes. This abstract will describe the steps that we have taken in completing the above work and the obtained results.

Drescher and Walsh, to satisfiability modulo theories, the key idea is to incorporate 2010). Then, constraint answer sets of the resulting program theory-specific predicates into propositional formulas, can be characterized via Boolean assignments over and extending an ASP solver's decision engine for a atom(Π) body(Π) that do not violate a set of nogoods more high-level proof procedure. A promising approach to imposed by Π. Formally, a Boolean assignment A is a sequence constraint answer set programming (CASP) has been presented (σ

A major difficulty in a search-based problem-solving process is the task of searching the potentially huge search space resulting from the exponential growth of states. State explosion rapidly occupies memory and increases computation time. Although various heuristic search algorithms have been developed to solve problems in a reasonable time, there is no efficient method to construct heuristic functions. In this work, we propose a method by which a neural network can be iteratively trained to form an efficient heuristic function. An adaptive heuristic search procedure is involved in the training iterations. This procedure reduces the evaluation values of the states that are involved in the currently known best solution paths. By doing so, the promising states are continuously moved forward. The adapted heuristic values are fed back to neural networks; thus, a well-trained network function can find the near-best solutions quickly. To demonstrate this method, we solved the fifteen-puzzle problem. Experimental results showed that the solutions obtained by our method were very close to the shortest path, and both the number of explored nodes and the search time were significantly reduced.