Search

Peer-reviewed conferences, the main publication venues in CS, rely critically on matching highly qualified reviewers for each paper. Because of the growing scale of these conferences, the tight timelines on which they operate, and a recent surge in explicitly dishonest behavior, there is now no alternative to performing this matching in an automated way. This paper introduces Large Conference Matching (LCM) , a novel reviewer–paper matching approach that was recently deployed in the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), and has since been adopted (wholly or partially) by other conferences including ICML 2022, AAAI 2022-2024, and IJCAI 2022-2024. LCM has three main elements: (1) collecting and processing input data to identify problematic matches and generate reviewer–paper scores; (2) formulating and solving an optimization problem to find good reviewer–paper matchings; and (3) a two-phase reviewing process that shifts reviewing resources away from papers likely to be rejected and towards papers closer to the decision boundary. This paper also describes an evaluation of these innovations based on an extensive post-hoc analysis on real data—including a comparison with the matching algorithm used in AAAI's previous (2020) iteration—and supplements this with additional numerical experimentation.2 [ABSTRACT FROM AUTHOR]

Great efforts have been devoted to causal discovery from observational data, and it is well known that introducing some background knowledge attained from experiments or human expertise can be very helpful. However, it remains unknown that what causal relations are identifiable given background knowledge in the presence of latent confounders. In this paper, we solve the problem with sound and complete orientation rules when the background knowledge is given in a local form. Furthermore, based on the solution to the problem, this paper proposes two applications that are of independent interests. One is that we give a maximal ancestral graph (MAG) listing algorithm, to output all the MAGs consistent to the observational data in the presence of latent variables. The other application is that we present a general active learning framework for causal discovery in the presence of latent confounders, where we propose a baseline criterion to select the intervention variable with a Metropolis-Hastings MAG-sampling method. Experiments validate the efficiency of the proposed MAG listing method and the effectiveness of the active learning framework. [ABSTRACT FROM AUTHOR]

"Open world" environments are those in which novel objects, agents, events, and more can appear and contradict previous understandings of the environment. This runs counter to the "closed world" assumption used in most AI research, where the environment is assumed to be fully understood and unchanging. The types of environments AI agents can be deployed in are limited by the inability to handle the novelties that occur in open world environments. This paper presents a novel cognitive architecture framework to handle open-world novelties. This framework combines symbolic planning, counterfactual reasoning, reinforcement learning, and deep computer vision to detect and accommodate novelties. We introduce general algorithms for exploring open worlds using inference and machine learning methodologies to facilitate novelty accommodation. The ability to detect and accommodate novelties allows agents built on this framework to successfully complete tasks despite a variety of novel changes to the world. Both the framework components and the entire system are evaluated in Minecraft-like simulated environments. Our results indicate that agents are able to efficiently complete tasks while accommodating "concealed novelties" not shared with the architecture development team. [ABSTRACT FROM AUTHOR]

Boolean Satisfiability (SAT) is arguably the archetypical NP-complete decision problem. Progress in SAT solving algorithms has motivated an ever increasing number of practical applications in recent years. However, many practical uses of SAT involve solving function as opposed to decision problems. Concrete examples include computing minimal unsatisfiable subsets, minimal correction subsets, prime implicates and implicants, minimal models, backbone literals, and autarkies, among several others. In most cases, solving a function problem requires a number of adaptive or non-adaptive calls to a SAT solver. Given the computational complexity of SAT, it is therefore important to develop algorithms that either require the smallest possible number of calls to the SAT solver, or that involve simpler instances. This paper addresses a number of representative function problems defined on Boolean formulae, and shows that all these function problems can be reduced to a generic problem of computing a minimal set subject to a monotone predicate. This problem is referred to as the Minimal Set over Monotone Predicate (MSMP) problem. This work provides new ways for solving well-known function problems, including prime implicates, minimal correction subsets, backbone literals, independent variables and autarkies, among several others. Moreover, this work also motivates the development of more efficient algorithms for the MSMP problem. Finally the paper outlines a number of areas of future research related with extensions of the MSMP problem. [ABSTRACT FROM AUTHOR]

With the recent advent of risk awareness, decision-making algorithms' complexity increases, posing a severe difficulty to solve such formulations of the problem online. Our approach is centered on the distribution of the return in the challenging continuous domain under partial observability. This paper proposes a simplification framework to ease the computational burden while providing guarantees on the simplification impact. On top of this framework, we present novel stochastic bounds on the return that apply to any reward function. Further, we consider simplification's impact on decision making with risk averse objectives, which, to the best of our knowledge, has not been investigated thus far. In particular, we prove that stochastic bounds on the return yield deterministic bounds on Value at Risk. The second part of the paper focuses on the joint distribution of a pair of returns given a pair of candidate policies, thereby, for the first time, accounting for the correlation between these returns. Here, we propose a novel risk averse objective and apply our simplification paradigm. Moreover, we present a novel tool called the probabilistic loss (PLoss) to completely characterize the simplification impact for any objective operator in this setting. We provably bound the cumulative and tail distribution function of PLoss using PbLoss to provide such a characterization online using only the simplified problem. In addition, we utilize this tool to offer deterministic guarantees to the simplification in the context of our novel risk averse objective. We employ our proposed framework on a particular simplification technique - reducing the number of samples for reward calculation or belief representation within planning. Finally, we verify the advantages of our approach through extensive simulations. [ABSTRACT FROM AUTHOR]

Answer Set Programming (ASP) is a well-established paradigm of declarative programming that has been developed in the field of logic programming and non-monotonic reasoning. Advances in ASP solving technology are customarily assessed in competition events, as it happens for other closely related problem solving areas such as Boolean Satisfiability, Satisfiability Modulo Theories, Quantified Boolean Formulas, Planning, etc. This paper reports about the fifth edition of the ASP Competition by covering all aspects of the event, ranging from the new design of the competition to an in-depth analysis of the results. The paper comprises also additional analyses that were conceived for measuring the progress of the state of the art, as well as for studying aspects orthogonal to solving technology, such as the effects of modeling. A detailed picture of the progress of the state of the art in ASP solving is drawn, and the ASP Competition is located in the spectrum of related events. [ABSTRACT FROM AUTHOR]

Answer Set Programming (ASP) constitutes nowadays one of the most successful paradigms for practical Knowledge Representation and declarative problem solving. The formal analysis of ASP programs is essential for a rigorous treatment of specifications, the correct construction of solvers and the extension with other representational features. In this paper, we present a syntactic transformation, called the unfolding operator, that allows forgetting an atom in a logic program (under ASP semantics). The main advantage of unfolding is that, unlike other syntactic operators, it is always applicable and guarantees strong persistence, that is, the result preserves the same stable models with respect to any context where the forgotten atom does not occur. The price for its completeness is that the result is an expression that may contain the fork operator. Yet, we illustrate how, in some cases, the application of fork properties may allow us to reduce the fork to a logic program. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents two new search algorithms: Potential Search (PTS) and Anytime Potential Search/Anytime Non-Parametric ( ). Both algorithms are based on a new evaluation function that is easy to implement and does not require user-tuned parameters. PTS is designed to solve bounded-cost search problems, which are problems where the task is to find as fast as possible a solution under a given cost bound. is a non-parametric anytime search algorithm discovered independently by two research groups via two very different derivations. In this paper, co-authored by researchers from both groups, we present these derivations: as a sequence of calls to PTS and as a non-parametric greedy variant of Anytime Repairing . We describe experiments that evaluate the new algorithms in the 15-puzzle, KPP-COM, robot motion planning, gridworld navigation, and multiple sequence alignment search domains. Our results suggest that when compared with previous anytime algorithms, : (1) does not require user-set parameters, (2) finds an initial solution faster, (3) spends less time between solution improvements, (4) decreases the suboptimality bound of the current-best solution more gradually, and (5) converges faster to an optimal solution when reachable. [Copyright &y& Elsevier]

Abstract: This paper considers the problem of autonomous agents that need to pick one of several options, all plausible however differ in their value, which is a priori uncertain and can be revealed for a cost. The agents thus need to weigh the benefits of revealing further values against the associated costs. The paper addresses the problem in its multi-agent joint form, such that not a single but rather a group of agents may benefit from the fruits of the search. The paper formally introduces and analyzes the joint search problem, when carried out fully distributedly, and determines the strategies to be used by the agents both when fully cooperative and when self-interested. The analysis is used to demonstrate that elements that can easily be proved to be beneficial with fully cooperative agents' search (e.g., extension of the search horizon, increase in the number of cooperating agents) can actually degrade individual and overall expected utility in the self-interested case. The analysis contributes to the advancement of joint search theories, and offers important insights for system designers, enabling them to determine the mechanisms that should be included in the markets and systems they design. [Copyright &y& Elsevier]

Abstract: The problem of minimising the number of distinct values among a set of variables subject to difference constraints occurs in many real-life contexts. This is the case of the Shift Minimisation Personnel Task Scheduling Problem, introduced by Krishnamoorthy et al., which is used as a case study all along this paper. Constraint-Programming enables to formulate this problem easily, through several AllDifferent constraints and a single AtMostNValue constraint. However, the independence of these constraints results in a poor lower bounding, hence a difficulty to prove optimality. This paper introduces a formalism to describe a family of propagators for AtMostNValue. In particular, we provide simple but significant improvement of the state-of-the-art AtMostNValue propagator of Bessière et al., to filter the conjunction of an AtMostNValue constraint and disequalities. In addition, we provide an original search strategy which relies on constraint reification. Extensive experiments show that our contribution significantly improves a straightforward model, so that it competes with the best known approaches from Operational Research. [Copyright &y& Elsevier]

Abstract: This paper presents a new axiomatic decision theory for choice under uncertainty. Unlike Bayesian decision theory where uncertainty is represented by a probability function, in our theory, uncertainty is given in the form of a likelihood function extracted from statistical evidence. The likelihood principle in statistics stipulates that likelihood functions encode all relevant information obtainable from experimental data. In particular, we do not assume any knowledge of prior probabilities. Consequently, a Bayesian conversion of likelihoods to posterior probabilities is not possible in our setting. We make an assumption that defines the likelihood of a set of hypotheses as the maximum likelihood over the elements of the set. We justify an axiomatic system similar to that used by von Neumann and Morgenstern for choice under risk. Our main result is a representation theorem using the new concept of binary utility. We also discuss how ambiguity attitudes are handled. Applied to the statistical inference problem, our theory suggests a novel solution. The results in this paper could be useful for probabilistic model selection. [Copyright &y& Elsevier]

In this paper we relax two common assumptions that are made when studying coalition formation. The first is that any number of coalitions can be formed; the second is that any possible coalition can be formed. We study a model of coalition formation where the value depends on a social network and exactly k coalitions must be formed. Additionally, in this context we present a new problem for an organizer that would like to introduce members of the social network to each other in order to increase the social welfare or to stabilize a coalition structure. We show that, when the number of coalitions, k , is fixed and there are not many negative edges, it is possible to find the coalition structure that maximizes the social welfare in polynomial time. Furthermore, an organizer can efficiently find the optimal set of edges to add to the network, and we experimentally demonstrate the effectiveness of this approach. In addition, we show that in our setting even when k is fixed and there are not many negative edges, finding a member of the core is intractable. However, we provide a heuristic for efficiently finding a member of the core that also guarantees a social welfare within a factor of 1/2 of the optimal social welfare. We also show that checking whether a given coalition structure is a member of the core can be done in polynomial time. Finally, we consider the problem faced by an organizer who would like to add edges to the network in order to stabilize a specific coalition structure core: we show that this problem is intractable. [ABSTRACT FROM AUTHOR]

Bidirectional search algorithms interleave two separate searches, a normal search forward from the start state, and a search backward from the goal. It is well known that adding a heuristic to unidirectional search dramatically reduces the search effort. By contrast, despite decades of research, bidirectional heuristic search has not yet had a major impact. Additionally, no comprehensive theory was ever devised to understand the nature of bidirectional heuristic search. In this paper we aim to close this gap. We first present MM , a novel bidirectional heuristic search algorithm. Unlike previous bidirectional heuristic search algorithms, MM 's forward and backward searches are guaranteed to “meet in the middle”, i.e. never expand a node beyond the solution midpoint. Based on this unique attribute we present a novel framework for comparing MM , A*, and their brute-force variants. We do this by dividing the entire state space into disjoint regions based on their distance from the start and goal. This allows us to perform a comparison of these algorithms on a per region basis and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis. [ABSTRACT FROM AUTHOR]

Real world applications often require cooperation of multiple independent entities. Classical planning is a well established technique solving various challenging problems such as logistic planning, factory process planning, military mission planning and high-level planning for robots. Multi-agent planning aims at solving similar problems in the presence of multiple independent entities (agents). Even though such entities might want to cooperate in order to fulfill a common goal, they may want to keep their internal information and processes private. In such case, we talk about privacy-preserving multi-agent planning. So far, multi-agent planners based on heuristic search used either a local heuristic estimating the particular agent's local subproblem or a distributed heuristic estimating the global problem as a whole. In this paper, we present the Multi-Agent Distributed and Local Asynchronous (MADLA) Planner, running a novel variant of a distributed state-space forward-chaining multi-heuristic search which combines the use of a local and a distributed heuristic in order to combine their benefits. In particular, the planner uses two variants of the well known Fast-Forward heuristic. We provide proofs of soundness and completeness of the search algorithm and show how much and what type of privacy it preserves. We also provide an improved privacy-preserving distribution scheme for the Fast-Forward heuristic. We experimentally compare the newly proposed multi-heuristic scheme and the two used heuristics separately. The results show that the proposed solution outperforms classical (single-heuristic) distributed search with either one of the heuristics used separately. In the detailed experimental analysis, we show limits of the planner and of the used heuristics based on particular properties of the benchmark domains. In a comprehensive set of multi-agent planning domains and problems, we show that the MADLA Planner outperforms all contemporary state-of-the-art privacy-preserving multi-agent planners using a compatible planning model. [ABSTRACT FROM AUTHOR]

We report on the First International Competition on Computational Models of Argumentation (ICCMA'15) which took place in the first half of 2015 and focused on reasoning tasks in abstract argumentation frameworks. Performance of submitted solvers was evaluated on four computational problems wrt. four different semantics relating to the verification of the acceptance status of arguments, and computing jointly acceptable sets of arguments. In this paper, we describe the technical setup of the competition, and give an overview on the submitted solvers. Moreover, we report on the results and discuss our findings. [ABSTRACT FROM AUTHOR]

Constraint Programming (CP) is a powerful technique for solving large-scale combinatorial problems. Solving a problem proceeds in two distinct phases: modelling and solving. Effective modelling has a huge impact on the performance of the solving process. Even with the advance of modern automated modelling tools, search spaces involved can be so vast that problems can still be difficult to solve. To further constrain the model, a more aggressive step that can be taken is the addition of streamliner constraints, which are not guaranteed to be sound but are designed to focus effort on a highly restricted but promising portion of the search space. Previously, producing effective streamlined models was a manual, difficult and time-consuming task. This paper presents a completely automated process to the generation, search and selection of streamliner portfolios to produce a substantial reduction in search effort across a diverse range of problems. The results demonstrate a marked improvement in performance for both Chuffed, a CP solver with clause learning, and lingeling, a modern SAT solver. [ABSTRACT FROM AUTHOR]

Maximum Satisfiability (MaxSAT) has been used to solve efficiently many combinatorial optimization problems. At recent editions of international MaxSAT Evaluation (MSE), the best performing solvers for real world (industrial) problems were those implementing SAT-based algorithms. These algorithms reformulate the MaxSAT optimization problem into a sequence of SAT decision problems where Pseudo-Boolean (PB) constraints may be introduced. In order to identify the most suitable PB constraints, some algorithms (core-guided) analyze the unsatisfiable cores retrieved from the previous SAT problems in the sequence while refining the lower bound. In this paper, we first conduct a comprehensive study on the complete core-guided algorithms Eva and OLL, that inspired the best performing solvers on industrial instances at MSE-2014. Despite of its apparently different foundations, we show how they are intimately related and identify how to improve them. In this sense, we present our complete core-guided algorithm WPM3. We show how to further exploit the analysis of unsatisfiable cores by being aware of their global structure, i.e., how the cores are interrelated. This is used to encode more efficient PB constraints and enables the algorithm to obtain assignments and refine also the upper bound. Therefore, WPM3 can also work as an incomplete algorithm. At MSE-2015, it showed a competitive performance on industrial instances. It got one out of three gold medals at the complete track and dominated at the incomplete track. [ABSTRACT FROM AUTHOR]

Boolean satisfiability (SAT) solving is one of the most competitive research areas of theoretical computer science. The performance of state-of-the-art SAT solvers has been continuously improving in the last decades and has reached a level where SAT solvers can be employed to solve real world problems in fields such as hardware and software verification, automated planning and many others. One of the important driving forces of this progress are the yearly organized (since 2002) SAT competitions. In this paper we describe the 2015 SAT Race that featured the traditional sequential and parallel tracks (with 64 core computers) and introduced the Incremental Library Track, which is particularly interesting for developers of SAT based applications. We describe the 2015 SAT Race and provide a detailed analysis of its results. [ABSTRACT FROM AUTHOR]

Dealing with planning problems with both logical relations and numeric changes in real-world dynamic environments is challenging. Existing numeric planning systems for the problem often discretize numeric variables or impose convex constraints on numeric variables, which harms the performance when solving problems. In this paper, we propose a novel algorithm framework to solve numeric planning problems mixed with logical relations and numeric changes based on gradient descent. We cast the numeric planning with logical relations and numeric changes as an optimization problem. Specifically, we extend syntax to allow parameters of action models to be either objects or real-valued numbers, which enhances the ability to model real-world numeric effects. Based on the extended modeling language, we propose a gradient-based framework to simultaneously optimize numeric parameters and compute appropriate actions to form candidate plans. The gradient-based framework is composed of an algorithmic heuristic module based on propositional operations to select actions and generate constraints for gradient descent, an algorithmic transition module to update states to next ones, and a loss module to compute loss. We repeatedly minimize loss by updating numeric parameters and compute candidate plans until it converges into a valid plan for the planning problem. In the empirical study, we exhibit that our algorithm framework is both effective and efficient in solving planning problems mixed with logical relations and numeric changes, especially when the problems contain obstacles and non-linear numeric effects. [ABSTRACT FROM AUTHOR]

This research note contains an extension of a previous work by Cabalar and Santos (2011) that formalised several spatial puzzles formed by strings and holes. That approach explicitly ignored some configurations and actions that were irrelevant for the studied puzzles but are physically possible and may become crucial for other spatial reasoning problems. In particular, the previous work did not consider the formation of string loops or the situations where a holed object is partially crossed by another holed object. In this paper, we remove these limitations by treating string loops as dynamic holes that can be created or destroyed by a pair of elementary actions, respectively picking or pulling from strings. We explain how string loops can be recognised in a data structure representing the domain states and define a notation to represent crossings through string loops . The resulting formalism is dual in the sense that it also allows understanding any hole as a kind of (sometimes rigid) closed string loop. [ABSTRACT FROM AUTHOR]

Over the last few years, much progress has been made in the theory and practice of solving quantified Boolean formulas (QBF). Novel solvers have been presented that either successfully enhance established techniques or implement novel solving paradigms. Powerful preprocessors have been realized that tune the encoding of a formula to make it easier to solve. Frameworks for certification and solution extraction emerged that allow for a detailed interpretation of a QBF solver's results, and new types of QBF encodings were presented for various application problems. To capture these developments the QBF Gallery was established in 2013. The QBF Gallery aims at providing a forum to assess QBF tools and to collect new, expressive benchmarks that allow for documenting the status quo and that indicate promising research directions. These benchmarks became the basis for the experiments conducted in the context of the QBF Gallery 2013 and follow-up evaluations. In this paper, we report on the setup of the QBF Gallery. To this end, we conducted numerous experiments which allowed us not only to assess the quality of the tools, but also the quality of the benchmarks. [ABSTRACT FROM AUTHOR]

This work proposes a novel high-level paradigm, agent planning programs , for modeling agents behavior, which suitably mixes automated planning with agent-oriented programming. Agent planning programs are finite-state programs, possibly containing loops, whose atomic instructions consist of a guard, a maintenance goal, and an achievement goal, which act as precondition-invariance-postcondition assertions in program specification. Such programs are to be executed in possibly nondeterministic planning domains and their execution requires generating plans that meet the goals specified in the atomic instructions, while respecting the program control flow. In this paper, we define the problem of automatically synthesizing the required plans to execute an agent planning program, propose a solution technique based on model checking of two-player game structures, and use it to characterize the worst-case computational complexity of the problem as EXPTIME-complete. Then, we consider the case of deterministic domains and propose a different technique to solve agent planning programs, which is based on iteratively solving classical planning problems and on exploiting goal preferences and plan adaptation methods. Finally, we study the effectiveness of this approach for deterministic domains through an experimental analysis on well-known planning domains. [ABSTRACT FROM AUTHOR]

While some computational models of intelligence test problems were proposed throughout the second half of the XXth century, in the first years of the XXIst century we have seen an increasing number of computer systems being able to score well on particular intelligence test tasks. However, despite this increasing trend there has been no general account of all these works in terms of how they relate to each other and what their real achievements are. Also, there is poor understanding about what intelligence tests measure in machines, whether they are useful to evaluate AI systems, whether they are really challenging problems, and whether they are useful to understand (human) intelligence. In this paper, we provide some insight on these issues, in the form of nine specific questions, by giving a comprehensive account of about thirty computer models, from the 1960s to nowadays, and their relationships, focussing on the range of intelligence test tasks they address, the purpose of the models, how general or specialised these models are, the AI techniques they use in each case, their comparison with human performance, and their evaluation of item difficulty. As a conclusion, these tests and the computer models attempting them show that AI is still lacking general techniques to deal with a variety of problems at the same time. Nonetheless, a renewed attention on these problems and a more careful understanding of what intelligence tests offer for AI may help build new bridges between psychometrics, cognitive science, and AI; and may motivate new kinds of problem repositories. [ABSTRACT FROM AUTHOR]

Optimal planning and heuristic search systems solve state-space search problems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i.e., without actually finding a solution path of that cost. We present an algorithm, BiSS , which is a hybrid of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. BiSS is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity. We show empirically that BiSS produces accurate predictions in several domains. In addition, we show that BiSS scales to state spaces much larger than can be solved optimally. In particular, we estimate the average solution cost for the 6 × 6 , 7 × 7 , and 8 × 8 Sliding-Tile puzzle and provide indirect evidence that these estimates are accurate. As a practical application of BiSS , we show how to use its predictions to reduce the time required by another system to learn strong heuristic functions from days to minutes in the domains tested. [ABSTRACT FROM AUTHOR]

Symmetry breaking has been a hot topic of research in the past years, leading to many theoretical developments as well as strong scaling strategies for dealing with hard applications. Most of the research has however focused on discrete, combinatorial, problems, and only few considered also continuous, numerical, problems. While part of the theory applies in both contexts, numerical problems have specificities that make most of the technical developments inadequate. In this paper, we present the rlex constraints, partial symmetry-breaking inequalities corresponding to a relaxation of the famous lex constraints extensively studied in the discrete case. They allow (partially) breaking any variable symmetry and can be generated in polynomial time. Contrarily to lex constraints that are impractical in general (due to their overwhelming number) and inappropriate in the continuous context (due to their form), rlex constraints can be efficiently handled natively by numerical constraint solvers. Moreover, we demonstrate their pruning power on continuous domains is almost as strong as that of lex constraints, and they subsume several previous work on breaking specific symmetry classes for continuous problems. Their experimental behavior is assessed on a collection of standard numerical problems and the factors influencing their impact are studied. The results confirm rlex constraints are a dependable counterpart to lex constraints for numerical problems. [ABSTRACT FROM AUTHOR]

This paper presents a meta-objective optimization approach, called Bi-Goal Evolution (BiGE), to deal with multi-objective optimization problems with many objectives. In multi-objective optimization, it is generally observed that 1) the conflict between the proximity and diversity requirements is aggravated with the increase of the number of objectives and 2) the Pareto dominance loses its effectiveness for a high-dimensional space but works well on a low-dimensional space. Inspired by these two observations, BiGE converts a given multi-objective optimization problem into a bi-goal (objective) optimization problem regarding proximity and diversity, and then handles it using the Pareto dominance relation in this bi-goal domain. Implemented with estimation methods of individuals' performance and the classic Pareto nondominated sorting procedure, BiGE divides individuals into different nondominated layers and attempts to put well-converged and well-distributed individuals into the first few layers. From a series of extensive experiments on four groups of well-defined continuous and combinatorial optimization problems with 5, 10 and 15 objectives, BiGE has been found to be very competitive against five state-of-the-art algorithms in balancing proximity and diversity. The proposed approach is the first step towards a new way of addressing many-objective problems as well as indicating several important issues for future development of this type of algorithms. [ABSTRACT FROM AUTHOR]

The study of extension-based semantics within the seminal abstract argumentation model of Dung has largely focused on definitional, algorithmic and complexity issues. In contrast, matters relating to comparisons of representational limits, in particular, the extent to which given collections of extensions are expressible within the formalism, have been under-developed. As such, little is known concerning conditions under which a candidate set of subsets of arguments are “realistic” in the sense that they correspond to the extensions of some argumentation framework af for a semantics of interest. In this paper we present a formal basis for examining extension-based semantics in terms of the sets of extensions that these may express within a single af . We provide a number of characterization theorems which guarantee the existence of af s whose set of extensions satisfy specific conditions and derive complexity results for decision problems that require such characterizations. [ABSTRACT FROM AUTHOR]

When forming the grand coalition is not possible or optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. In this paper, we propose an innovative exact algorithm called CoreD to check core-non-emptiness for coalition structures. A more straightforward exact algorithm based on existing techniques, which we call CoreP , first obtains the value of optimal coalition structure by solving an integer programming problem. Then, it checks whether that value can be divided without making a blocking (dissatisfied) coalition. In contrast, CoreD first finds a minimal value of the optimal coalition structure so that there exists no blocking coalition. Next, it checks whether the optimal value equals the minimal value We empirically show that when the core is empty, CoreD is by far superior to CoreP . Also, to find a second-best payoff vector when the core is empty, we propose a new solution concept called the weak ε -core + , which can utilize the approximate value of the optimal coalition structure. Based on the idea of CoreD , we further develop an algorithm for checking the non-emptiness of the weak ε -core + . [ABSTRACT FROM AUTHOR]

Answer Set Programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many AI problems such as reasoning in a nonmonotonic setting can be directly formulated in ASP. Although the main problems of ASP are of high computational complexity, complete for the second level of the Polynomial Hierarchy, several restrictions of ASP have been identified in the literature, under which ASP problems become tractable. In this paper we use the concept of backdoors to identify new restrictions that make ASP problems tractable. Small backdoors are sets of atoms that represent “clever reasoning shortcuts” through the search space and represent a hidden structure in the problem input. The concept of backdoors is widely used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction. We show that it can be fruitfully adapted to ASP. We demonstrate how backdoors can serve as a unifying framework that accommodates several tractable restrictions of ASP known from the literature. Furthermore, we show how backdoors allow us to deploy recent algorithmic results from parameterized complexity theory to the domain of answer set programming. [ABSTRACT FROM AUTHOR]

Fuzzy description logics (DLs) can be used to represent and reason with vague knowledge. This family of logical formalisms is very diverse, each member being characterized by a specific choice of constructors, axioms, and triangular norms, which are used to specify the semantics. Unfortunately, it has recently been shown that the consistency problem in many fuzzy DLs with general concept inclusion axioms is undecidable. In this paper, we present a proof framework that allows us to extend these results to cover large classes of fuzzy DLs. On the other hand, we also provide matching decidability results for most of the remaining logics. As a result, we obtain a near-universal classification of fuzzy DLs according to the decidability of their consistency problem. [ABSTRACT FROM AUTHOR]

In automated planning, there has been a recent interest in solving a class of problems, where a single solution applies for multiple, possibly infinitely many, instances. This necessitates a generalized notion of plans, such as plans with loops. However, the correctness of such plans is non-trivial to define, making it difficult to provide a clear specification of what we should be looking for. In an influential paper, Levesque proposed a formal specification for analyzing the correctness of such plans. He motivated a logical characterization within the situation calculus that included binary sensing actions. This characterization argued that from each state considered possible initially, the plan should terminate while satisfying the goal. Increasingly, classical plan structures are being applied to stochastic environments such as robotics applications. This raises the question as to what the specification for correctness should look like, since Levesque's account makes the assumption that actions are deterministic. In this work, we aim to generalize Levesque's account to handle actions with nondeterministic outcomes, which may also be accorded probabilities. By appealing to an extension of the situation calculus to handle probabilistic nondeterminism, we will show that Levesque's definition, as well as a notion of goal achievability proposed by Lin and Levesque, have limited appeal under stochastic nondeterminism. In essence, they correspond to one correct execution, which is unlikely to be adequate. Rather, we propose to delineate between goal satisfaction and termination leading to a range of correctness criteria. To better study these criteria, and to position the results in a broader context while still allowing for the generality of the situation calculus, we consider an abstract framework to study the correctness of plans with loops, in domains that are possibly unbounded, and/or stochastic, and/or continuous. Within that framework, we then prove numerous relationships between the criteria, including some impossibility results for categorically satisfying goals. Finally, we show that these notions provide a more granular view than those discussed in the literature, such as strong planning and strong cyclic planning. [ABSTRACT FROM AUTHOR]

In recent years, there has been an increasing interest in extending stream processing engines with rule-based temporal reasoning capabilities. To ensure correctness, such systems must be able to output results over the partial data received so far as if the entire (infinite) stream had been available; furthermore, these results must be streamed out as soon as the relevant data is received, thus incurring the minimum possible delay; finally, due to memory limitations, systems can only keep a limited history of previous facts in memory to perform further computations. These requirements pose significant theoretical and practical challenges since temporal rules can derive new information and propagate it both towards past and future time points; as a result, streamed answers can depend on data that has not yet been received, as well as on data that arrived far in the past. Towards developing a solid foundation for practical rule-based stream reasoning, we propose and study in this paper a suite of decision problems that can be exploited by stream reasoning algorithms to tackle the aforementioned challenges, and provide tight complexity bounds for a core temporal extension of Datalog. All of the problems we consider can be solved at design time (under reasonable assumptions), prior to the processing of any data. Solving these problems enables the use of reasoning algorithms that process the input streams incrementally using a sliding window, while at the same time supporting an expressive rule-based knowledge representation language and minimising both latency and memory consumption. [ABSTRACT FROM AUTHOR]

Abstract: Proteins are chains of simple molecules called amino acids. The three-dimensional shape of a protein and its amino acid composition define its biological function. Over millions of years, living organisms have evolved a large catalog of proteins. By exploring the space of possible amino acid sequences, protein engineering aims at similarly designing tailored proteins with specific desirable properties. In Computational Protein Design (CPD), the challenge of identifying a protein that performs a given task is defined as the combinatorial optimization of a complex energy function over amino acid sequences. In this paper, we introduce the CPD problem and some of the main approaches that have been used by structural biologists to solve it, with an emphasis on the exact method embodied in the dead-end algorithm . The CPD problem is a specific form of binary Cost Function Network (CFN, aka Weighted CSP). We show how DEE algorithms can be incorporated and suitably modified to be maintained during search, at reasonable computational cost. We then evaluate the efficiency of CFN algorithms as implemented in our solver toulbar2, on a set of real CPD instances built in collaboration with structural biologists. The CPD problem can be easily reduced to 0/1 Linear Programming, 0/1 Quadratic Programming, 0/1 Quadratic Optimization, Weighted Partial MaxSAT and Graphical Model optimization problems. We compare toulbar2 with these different approaches using a variety of solvers. We observe tremendous differences in the difficulty that each approach has on these instances. Overall, the CFN approach shows the best efficiency on these problems, improving by several orders of magnitude against the exact approach. The introduction of dead-end elimination before or during search allows to further improve these results. [Copyright &y& Elsevier]

Abstract: Influence diagrams are intuitive and concise representations of structured decision problems. When the problem is non-Markovian, an optimal strategy can be exponentially large in the size of the diagram. We can avoid the inherent intractability by constraining the size of admissible strategies, giving rise to limited memory influence diagrams. A valuable question is then how small do strategies need to be to enable efficient optimal planning. Arguably, the smallest strategies one can conceive simply prescribe an action for each time step, without considering past decisions or observations. Previous work has shown that finding such optimal strategies even for polytree-shaped diagrams with ternary variables and a single value node is NP-hard, but the case of binary variables was left open. In this paper we address such a case, by first noting that optimal strategies can be obtained in polynomial time for polytree-shaped diagrams with binary variables and a single value node. We then show that the same problem is NP-hard if the diagram has multiple value nodes. These two results close the fixed-parameter complexity analysis of optimal strategy selection in influence diagrams parametrized by the shape of the diagram, the number of value nodes and the maximum variable cardinality. [Copyright &y& Elsevier]

Abstract: Evolutionary algorithms (EAs) are increasingly popular approaches to multi-objective optimization. One of their significant advantages is that they can directly optimize the Pareto front by evolving a population of solutions, where the recombination (also called crossover) operators are usually employed to reproduce new and potentially better solutions by mixing up solutions in the population. Recombination in multi-objective evolutionary algorithms is, however, mostly applied heuristically. In this paper, we investigate how from a theoretical viewpoint a recombination operator will affect a multi-objective EA. First, we employ artificial benchmark problems: the Weighted LPTNO problem (a generalization of the well-studied LOTZ problem), and the well-studied COCZ problem, for studying the effect of recombination. Our analysis discloses that recombination may accelerate the filling of the Pareto front by recombining diverse solutions and thus help solve multi-objective optimization. Because of this, for these two problems, we find that a multi-objective EA with recombination enabled achieves a better expected running time than any known EAs with recombination disabled. We further examine the effect of recombination on solving the multi-objective minimum spanning tree problem, which is an NP-hard problem. Following our finding on the artificial problems, our analysis shows that recombination also helps accelerate filling the Pareto front and thus helps find approximate solutions faster. [Copyright &y& Elsevier]

Answer Set Programming (ASP) is a paradigm for modeling and solving problems for knowledge representation and reasoning. There are plenty of results dedicated to studying the hardness of (fragments of) ASP. So far, these studies resulted in characterizations in terms of computational complexity as well as in fine-grained insights presented in form of dichotomy-style results, lower bounds when translating to other formalisms like propositional satisfiability (SAT), and even detailed parameterized complexity landscapes. A generic parameter in parameterized complexity originating from graph theory is the so-called treewidth , which in a sense captures structural density of a program. Recently, there was an increase in the number of treewidth-based solvers related to SAT. While there are translations from (normal) ASP to SAT, no reduction that preserves treewidth or at least keeps track of the treewidth increase is known. In this paper we propose a novel reduction from normal ASP to SAT that is aware of the treewidth, and guarantees that a slight increase of treewidth is indeed sufficient. Further, we show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT (under reasonable assumptions in computational complexity). This also confirms that our reduction probably cannot be significantly improved and that the slight increase of treewidth is unavoidable. Finally, we present an empirical study of our novel reduction from normal ASP to SAT, where we compare treewidth upper bounds that are obtained via known decomposition heuristics. Overall, our reduction works better with these heuristics than existing translations. [ABSTRACT FROM AUTHOR]

Abstract: Mixed multi-unit combinatorial auctions (MMUCAs) are extensions of classical combinatorial auctions (CAs) where bidders trade transformations of goods rather than just sets of goods. Solving MMUCAs, i.e., determining the sequences of bids to be accepted by the auctioneer, is computationally intractable in general. However, differently from classical combinatorial auctions, little was known about whether polynomial-time solvable classes of MMUCAs can be singled out on the basis of their characteristics. The paper fills this gap, by studying the computational complexity of MMUCA instances under structural and qualitative restrictions, which characterize interactions among bidders and types of bids involved in the various transformations, respectively. [Copyright &y& Elsevier]

Abstract: Many industrial optimization problems can be translated to MaxSAT. Although the general problem is NP hard, like SAT, many practical problems may be solved using modern MaxSAT solvers. In this paper we present several algorithms specially designed to deal with industrial or real problems. All of them are based on the idea of solving MaxSAT through successive calls to a SAT solver. We show that this SAT-based technique is efficient in solving industrial problems. In fact, all state-of-the-art MaxSAT solvers that perform well in industrial instances are based on this technique. In particular, our solvers won the 2009 partial MaxSAT and the 2011 weighted partial MaxSAT industrial categories of the MaxSAT evaluation. We prove the correctness of all our algorithms. We also present a complete experimental study comparing the performance of our algorithms with latest MaxSAT solvers. [Copyright &y& Elsevier]

Abstract: Cross-domain analogies are a powerful method for learning new domains. This paper extends the Domain Transfer via Analogy (DTA) method with persistent mappings, correspondences between domains that are incrementally built up as a cognitive system gains experience with a new domain. DTA uses analogies between pairs of textbook example problems, or worked solutions, to create a domain mapping between a familiar and a new domain. This mapping enables the initialization of a new domain theory. Another analogy is then made between the domain theories themselves, providing additional conjectures about the new domain. After these conjectures are verified, the successful mappings are stored as persistent mappings to constrain future analogies between the domains. We show that DTA plus persistent mappings enables a Companion, the first structure mapping cognitive architecture, to learn the equation schemas and control knowledge necessary to solve problems in three domains (rotational mechanics, electricity, and heat) by analogy with linear mechanics. We provide a detailed analysis categorizing transfer failures. As with people, the most difficult step in cross-domain analogy is identifying an appropriate example. Once an analogous example has been found, DTA successfully transfers the domain knowledge necessary to solve the problem in the new domain 78% of the time. Furthermore, we illustrate how persistent mappings assist in retrieval of analogous examples and overcoming two types of mapping failures. [Copyright &y& Elsevier]

Abstract: MinSAT is the problem of finding a truth assignment that minimizes the number of satisfied clauses in a CNF formula. When we distinguish between hard and soft clauses, and soft clauses have an associated weight, then the problem, called Weighted Partial MinSAT, consists in finding a truth assignment that satisfies all the hard clauses and minimizes the sum of weights of satisfied soft clauses. In this paper we describe a branch-and-bound solver for Weighted Partial MinSAT equipped with original upper bounds that exploit both clique partitioning algorithms and MaxSAT technology. Then, we report on an empirical investigation that shows that solving combinatorial optimization problems by reducing them to MinSAT is a competitive generic problem solving approach when solving MaxClique and combinatorial auction instances. Finally, we investigate an interesting correlation between the minimum number and the maximum number of satisfied clauses on random CNF formulae. [Copyright &y& Elsevier]

Abstract: Abstract argumentation frameworks have received a lot of interest in recent years. Most computational problems in this area are intractable but several tractable fragments have been identified. In particular, Dunne showed that many problems can be solved in linear time for argumentation frameworks of bounded tree-width. However, these tractability results, which were obtained via Courcelleʼs Theorem, do not directly lead to efficient algorithms. The goal of this paper is to turn the theoretical tractability results into efficient algorithms and to explore the potential of directed notions of tree-width for defining larger tractable fragments. As a by-product, we will sharpen some known complexity results. [Copyright &y& Elsevier]

Abstract: Security games are gaining significant interest in artificial intelligence. They are characterized by two players (a defender and an attacker) and by a set of targets the defender tries to protect from the attackerʼs intrusions by committing to a strategy. To reach their goals, players use resources such as patrollers and intruders. Security games are Stackelberg games where the appropriate solution concept is the leader–follower equilibrium. Current algorithms for solving these games are applicable when the underlying game is in normal form (i.e., each player has a single decision node). In this paper, we define and study security games with an extensive-form infinite-horizon underlying game, where decision nodes are potentially infinite. We introduce a novel scenario where the attacker can undertake actions during the execution of the defenderʼs strategy. We call this new game class patrolling security games (PSGs), since its most prominent application is patrolling environments against intruders. We show that PSGs cannot be reduced to security games studied so far and we highlight their generality in tackling adversarial patrolling on arbitrary graphs. We then design algorithms to solve large instances with single patroller and single intruder. [Copyright &y& Elsevier]

Abstract: A planning problem is k-dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is of interest because k is a constant for all but a few of the current benchmark domains in planning, and is known to have implications for tractability. In this paper, we present an algorithm for solving planning problems in , the class of k-dependent planning problems with binary variables and polytree causal graphs. We prove that our algorithm runs in polynomial time when k is a fixed constant. If, in addition, the causal graph has bounded depth, we show that plan generation is linear in the size of the input. Although these contributions are theoretical due to the limited scope of the class , suitable reductions from more complex planning problems to could potentially give rise to fast domain-independent heuristics. [Copyright &y& Elsevier]

Abstract: In this paper, we propose the MIML (Multi-Instance Multi-Label learning) framework where an example is described by multiple instances and associated with multiple class labels. Compared to traditional learning frameworks, the MIML framework is more convenient and natural for representing complicated objects which have multiple semantic meanings. To learn from MIML examples, we propose the MimlBoost and MimlSvm algorithms based on a simple degeneration strategy, and experiments show that solving problems involving complicated objects with multiple semantic meanings in the MIML framework can lead to good performance. Considering that the degeneration process may lose information, we propose the D-MimlSvm algorithm which tackles MIML problems directly in a regularization framework. Moreover, we show that even when we do not have access to the real objects and thus cannot capture more information from real objects by using the MIML representation, MIML is still useful. We propose the InsDif and SubCod algorithms. InsDif works by transforming single-instances into the MIML representation for learning, while SubCod works by transforming single-label examples into the MIML representation for learning. Experiments show that in some tasks they are able to achieve better performance than learning the single-instances or single-label examples directly. [Copyright &y& Elsevier]

Abstract: The field of data mining has become accustomed to specifying constraints on patterns of interest. A large number of systems and techniques has been developed for solving such constraint-based mining problems, especially for mining itemsets. The approach taken in the field of data mining contrasts with the constraint programming principles developed within the artificial intelligence community. While most data mining research focuses on algorithmic issues and aims at developing highly optimized and scalable implementations that are tailored towards specific tasks, constraint programming employs a more declarative approach. The emphasis lies on developing high-level modeling languages and general solvers that specify what the problem is, rather than outlining how a solution should be computed, yet are powerful enough to be used across a wide variety of applications and application domains. This paper contributes a declarative constraint programming approach to data mining. More specifically, we show that it is possible to employ off-the-shelf constraint programming techniques for modeling and solving a wide variety of constraint-based itemset mining tasks, such as frequent, closed, discriminative, and cost-based itemset mining. In particular, we develop a basic constraint programming model for specifying frequent itemsets and show that this model can easily be extended to realize the other settings. This contrasts with typical procedural data mining systems where the underlying procedures need to be modified in order to accommodate new types of constraint, or novel combinations thereof. Even though the performance of state-of-the-art data mining systems outperforms that of the constraint programming approach on some standard tasks, we also show that there exist problems where the constraint programming approach leads to significant performance improvements over state-of-the-art methods in data mining and as well as to new insights into the underlying data mining problems. Many such insights can be obtained by relating the underlying search algorithms of data mining and constraint programming systems to one another. We discuss a number of interesting new research questions and challenges raised by the declarative constraint programming approach to data mining. [Copyright &y& Elsevier]

Abstract: Although many techniques for merging conflicting propositional knowledge bases have already been proposed, most existing work is based on the idea that inconsistency results from the presence of incorrect pieces of information, which should be identified and removed. In contrast, we take the view in this paper that conflicts are often caused by statements that are inaccurate rather than completely false, suggesting to restore consistency by interpreting certain statements in a flexible way, rather than ignoring them completely. In accordance with this view, we propose a novel approach to merging which exploits extra-logical background information about the semantic relatedness of atomic propositions. Several merging operators are presented, which are based on different formalizations of this background knowledge, ranging from purely qualitative approaches, related to possibilistic logic, to quantitative approaches with a probabilistic flavor. Both syntactic and semantic characterizations are provided for each merging operator, and the computational complexity is analyzed. [Copyright &y& Elsevier]

Abstract: This paper introduces an axiomatic model for bargaining analysis. We describe a bargaining situation in propositional logic and represent bargainers'' preferences in total pre-orders. Based on the concept of minimal simultaneous concessions, we propose a solution to n-person bargaining problems and prove that the solution is uniquely characterized by five logical axioms: Consistency, Comprehensiveness, Collective rationality, Disagreement, and Contraction independence. This framework provides a naive solution to multi-person, multi-issue bargaining problems in discrete domains. Although the solution is purely qualitative, it can also be applied to continuous bargaining problems through a procedure of discretization, in which case the solution coincides with the Kalai–Smorodinsky solution. [Copyright &y& Elsevier]

Abstract: Case-based planning can take advantage of former problem-solving experiences by storing in a plan library previously generated plans that can be reused to solve similar planning problems in the future. Although comparative worst-case complexity analyses of plan generation and reuse techniques reveal that it is not possible to achieve provable efficiency gain of reuse over generation, we show that the case-based planning approach can be an effective alternative to plan generation when similar reuse candidates can be chosen. In this paper we describe an innovative case-based planning system, called OAKplan, which can efficiently retrieve planning cases from plan libraries containing more than ten thousand cases, choose heuristically a suitable candidate and adapt it to provide a good quality solution plan which is similar to the one retrieved from the case library. Given a planning problem we encode it as a compact graph structure, that we call Planning Encoding Graph, which gives us a detailed description of the topology of the planning problem. By using this graph representation, we examine an approximate retrieval procedure based on kernel functions that effectively match planning instances, achieving extremely good performance in standard benchmark domains. The experimental results point out the effect of the case base size and the importance of accurate matching functions for global system performance. Overall, we show that OAKplan is competitive with state-of-the-art plan generation systems in terms of number of problems solved, CPU time, plan difference values and plan quality when cases similar to the current planning problem are available in the plan library. [ABSTRACT FROM AUTHOR]

When solving a combinatorial problem using propositional satisfiability (SAT), the encoding of the problem is of vital importance. We study encodings of Pseudo-Boolean (PB) constraints, a common type of arithmetic constraint that appears in a wide variety of combinatorial problems such as timetabling, scheduling, and resource allocation. In some cases PB constraints occur together with at-most-one (AMO) constraints over subsets of their variables (forming PB(AMO) constraints). Recent work has shown that taking account of AMOs when encoding PB constraints using decision diagrams can produce a dramatic improvement in solver efficiency. In this paper we extend the approach to other state-of-the-art encodings of PB constraints, developing several new encodings for PB(AMO) constraints. Also, we present a more compact and efficient version of the popular Generalized Totalizer encoding, named Reduced Generalized Totalizer. This new encoding is also adapted for PB(AMO) constraints for a further gain. Our experiments show that the encodings of PB(AMO) constraints can be substantially smaller than those of PB constraints. PB(AMO) encodings allow many more instances to be solved within a time limit, and solving time is improved by more than one order of magnitude in some cases. We also observed that there is no single overall winner among the considered encodings, but efficiency of each encoding may depend on PB(AMO) characteristics such as the magnitude of coefficient values. [ABSTRACT FROM AUTHOR]