We study the notion of informedness in a client-consultant setting. Using a software simulator, we examine the extent to which it pays off for consultants to provide their clients with advice that is well-informed, or with advice that is merely meant to appear to be well-informed. The latter strategy is beneficial in that it costs less resources to keep up-to-date, but carries the risk of a decreased reputation if the clients discover the low level of informedness of the consultant. Our experimental results indicate that under different circumstances, different strategies yield the optimal results (net profit) for the consultants.

In this paper, we address the problem of generating preferred plans by combining the procedural control knowledge specified by Hierarchical Task Networks (HTNs) with rich qualitative user preferences. The outcome of our work is a language for specifyin user preferences, tailored to HTN planning, together with a provably optimal preference-based planner, HTNPLAN, that is implemented as an extension of SHOP2. To compute preferred plans, we propose an approach based on forward-chaining heuristic search. Our heuristic uses an admissible evaluation function measuring the satisfaction of preferences over partial plans. Our empirical evaluation demonstrates the effectiveness of our HTNPLAN heuristics. We prove our approach sound and optimal with respect to the plans it generates by appealing to a situation calculus semantics of our preference language and of HTN planning. While our implementation builds on SHOP2, the language and techniques proposed here are relevant to a broad range of HTN planners.

Abstraction, reformulation, and approximation including some copresented at the Symposium (ARA) techniques are deemed crucial in the on Combinatorial Search (SoCS), which was ability of humans to reason about complex and collocated with SARA this year.

MINLP problems are hard constrained optimization problems, with nonlinear constraints and mixed discrete continuous variables. They can be solved using a Branch-and-Bound scheme combining several methods, such as linear programming, interval analysis, and cutting methods. Our goal is to integrate constraint programming techniques in this framework. Firstly, global constraints can be introduced to reformulate MINLP problems thus leading to clean models and more precise computations. Secondly, interval-based approximation techniques for nonlinear constraints can be improved by taking into account the integrality of variables early. These methods have been implemented in an interval solver and we present experimental results from a set of MINLP instances.

Perfect recall is the common and natural assumption that an agent never forgets. As a consequence, the agent can always condition its choice of action on any prior observations. In this paper, we explore relaxing this assumption. We observe the negative impact this relaxation has on algorithms: some algorithms are no longer well-defined, while others lose their theoretical guarantees on the quality of a solution. Despite these disadvantages, we show that removing this restriction can provide considerable empirical advantages when modeling extremely large extensive games. In particular, it allows fine granularity of the most relevant observations without requiring decisions to be contingent on all past observations. In the domain of poker, this improvement enables new types of information to be used in the abstraction. By making use of imperfect recall and new types of information, our poker program was able to win the limit equilibrium event as well as the no-limit event at the 2008 AAAI Computer Poker Competition. We show experimental results to verify that our pro- grams using imperfect recall are indeed stronger than their perfect recall counterparts.

A problem that often arises in using abstraction is the generation of abstract states, called spurious states, that are—in the abstract space—reachable from some abstract image of a state s, but which have no corresponding state in the original space reachable from s. Spurious states can have a negative effect on pattern database sizes and heuristic quality. We formally define a property—the downward path preserving property (DPP)—that guarantees an abstraction has no spurious states. Analyzing the computational complexity of (i) testing the DPP property for a given state space and abstraction and of (ii) determining whether this property is achievable at all for a given state space, results in strong hardness theorems. On the positive side, we identify formal conditions under which finding DPP abstractions is tractable.

The exploration of complex interaction networks has attracted considerable interest in various fields, ranging from fundamental biology and medicine to statistical physics and information technology.  In -omics disciplines, significant progresses have been made in understanding the large-scale properties and the biological relevance of these interactions. Some properties such as scale-free distribution of nodes connectivity or centrality are aspects commonly described in such complex interaction systems. In many of these studies the analysis of network topology is complemented by a semantic analysis that may rely on  different labels associated to the interacting entities.   One of the bottleneck of these semantic analysis is that they  are computationally costly. In this paper we present a framework to explore abstraction of networks useful to speedup the computation  of ground network measures. Such abstraction mechanisms may be used to efficiently provide accurate approximations of ground network measures.

Arc consistency algorithms are widely used to prune the search space of Constraint Satisfaction Problems (CSPs). Since many researchers associate arc consistency with binary normalized CSPs, there is a confusion between the notion of arc consistency and 2-consistency. 2-consistency guarantees that any instantiation of a value to a variable can be consistently extended to any second variable. Thus, 2-consistency can be stronger than arc-consistency in binary CSPs. In this paper, we present a new algorithm, called 2-C3, which achieves 2-consistency in binary and non-normalized CSPs. This algorithm is a reformulation of the well-known AC3 algorithm. The evaluation section shows that 2-C3 is able to prune more search space than AC3 and AC4.

This article presents two new algorithms whose purpose is to maintain the Max-RPC domain filtering consistency during search with a minimal memory footprint and implementation effort. Both are sub-optimal algorithms that make use of support residues, a backtrack-stable and highly efficient data structure which was successfully used to develop the state-of-the-art AC-3rm algorithm. The two proposed algorithms, Max-RPCrm and L-Max-RPCrm are competitive with best, optimal Max-RPC algorithms, while being considerably simpler to implement. L-Max-RPCrm computes an approximation of the Max-RPC consistency, which is guaranteed to be strictly stronger than AC with the same space complexity and better worst-case time complexity than Max-RPCrm. In practice, the difference in filtering power between L-Max-RPCrm and standard Max-RPC is nearly indistinguishable on random problems. Max-RPCrm and L-Max-RPCrm are implemented into the Choco Constraint Solver through a strong consistency global constraint. This work opens new perspectives upon the development of strong consistency algorithms into constraint solvers.

We study novel approaches for solving of hard combinatorial problems by translation to Boolean Satisfiability (SAT). Our focus is on combinatorial problems that can be represented as a permutation of n objects, subject to additional constraints. In the case of the Hamiltonian Cycle Problem (HCP), these constraints are that two adjacent nodes in a permutation should also be neighbors in the original graph for which we search for a Hamiltonian cycle. We use the absolute SAT encoding of permutations, where for each of the n objects and each of its pos- sible positions in a permutation, a predicate is defined to indicate whether the object is placed in that position. For implementation of this predicate, we compare the direct and logarithmic encodings that have been used previously, against 16 hierarchical parameterizable encodings of which we explore 416 instantiations. We propose the use of enumerative adjacency constraints—that enumerate the possible neighbors of a node in a permutation — instead of, or in addition to the exclusivity adjacency constraints — that exclude impossible neighbors, and that have been applied previously. We study 11 heuristics for efficiently choosing the first node in the Hamiltonian cycle, as well as 8 heuristics for static CNF variable ordering. We achieve at least 4 orders of magnitude average speedup on HCP benchmarks from the phase transition region, relative to the previously used encodings for solving of HCPs via SAT, such that the speedup is increasing with the size of the graphs.