We study the computational complexity of finding the next most preferred solution in some common formalisms for representing constraints and preferences. The problem is computationally intractable for CSPs, but is polynomial for tree-shaped CSPs and tree-shaped fuzzy CSPs. On the other hand, it is intractable for weighted CSPs, even under restrictions on the constraint graph. For CP-nets, the problem is polynomial when the CP-net is acyclic. This remains so if we add (soft) constraints that are tree-shaped and topologically compatible with the CP-net.

A general game player automatically learns to play arbitrary new games solely by being told their rules. For this purpose games are specified in the game description language GDL, a variant of Datalog with function symbols and a few known keywords. In its latest version GDL allows to describe nondeterministic games with any number of players who may have imperfect, asymmetric information. We analyse the epistemic structure and expressiveness of this language in terms of epistemic modal logic and present two main results: The operational semantics of GDL entails that the situation at any stage of a game can be characterised by a multi-agent epistemic (i.e., S5-) model; (2) GDL is sufficiently expressive to model any situation that can be described by a (finite) multi-agent epistemic model.

In this paper, we extend the progression semantics for first-order disjunctive logic programs and show that it coincides with the stable model semantics. Based on it, we further show how disjunctive answer set programming is related to Satisfiability Modulo Theories.

MAPP has been previously shown as a state-of-the-art multi-agent path planning algorithm on criteria including scalability and success ratio (i.e., percentage of solved units) on realistic game maps. MAPP further provides a formal characterization of problems it can solve, and low-polynomial upper bounds on the resources required. However, until now, MAPP's solution quality had not been extensively analyzed. In this work we empirically analyze the quality of MAPP's solutions, using multiple quality criteria such as the total travel distance, the makespan and the sum of actions (including move and wait actions). We also introduce enhancements that improve MAPP's solution quality significantly. For example, the sum of actions is cut to half on average. The improved MAPP is competitive in terms of solution quality with FAR and WHCA*, two successful algorithms from the literature, and maintains its advantages on different performance criteria, such as scalability, success ratio, and ability to tell apriori if it will succeed in the instance at hand. As optimal algorithms have limited scalability, evaluating the quality of the solutions provided by suboptimal algorithms is another important topic. Using lower bounds of optimal values, we show that MAPP's solutions have a reasonable quality. For example, MAPP's total travel distance is on average 19% longer than a lower bound on the optimal value.

Evolutionary Algorithms (EA) are a branch of heuristic population-based optimization tools that is growing in popularity (especially for combinatorial and other problems with poorly understood landscapes). Despite their many uses, there are no proofs that an EA will always converge to the global optimum for any general problem.

Bagging is a simple yet effective design which combines multiple single learners to form an ensemble for prediction. Despite its popular usage in many real-world applications, existing research is mainly concerned with studying unstable learners as the key to ensure the performance gain of a bagging predictor, with many key factors remaining unclear. For example, it is not clear when a bagging predictor can outperform a single learner and what is the expected performance gain when different learning algorithms were used to form a bagging predictor. In this paper, we carry out comprehensive empirical studies to evaluate bagging predictors by using 12 different learning algorithms and 48 benchmark data-sets. Our analysis uses robustness and stability decompositions to characterize different learning algorithms, through which we rank all learning algorithms and comparatively study their bagging predictors to draw conclusions. Our studies assert that both stability and robustness are key requirements to ensure the high performance for building a bagging predictor. In addition, our studies demonstrated that bagging is statistically superior to most single base learners, except for KNN and Naïve Bayes (NB). Multi-layer perception (MLP), Naïve Bayes Trees (NBTree), and PART are the learning algorithms with the best bagging performance.

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.

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.

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 (σ

When mobile robots perform tasks in environments with humans, it seems appropriate for the robots to rely on such humans for help instead of dedicated human oracles or supervisors. However, these humans are not always available nor always accurate. In this work, we consider human help to a robot as concretely providing observations about the robot's state to reduce state uncertainty as it executes its policy autonomously. We model the probability of receiving an observation from a human in terms of their availability and accuracy by introducing Human Observation Providers POMDPs (HOP-POMDPs). We contribute an algorithm to learn human availability and accuracy online while the robot is executing its current task policy. We demonstrate that our algorithmis effective in approximating the true availability and accuracy of humans without depending on oracles to learn, thus increasing the tractability of deploying a robot that can occasionally ask for help.