The goal of testing is to discriminate between multiple hypotheses about a system - for example, different fault diagnoses - by applying input patterns and verifying or falsifying the hypotheses from the observed outputs. Definitely discriminating tests (DDTs) are those input patterns that are guaranteed to discriminate between different hypotheses of non-deterministic systems. Finding DDTs is important in practice, but can be very expensive. Even more challenging is the problem of finding a DDT that minimizes the cost of the testing process, i.e., an input pattern that can be most cheaply enforced and that is a DDT. This paper addresses both problems. We show how we can transform a given problem into a Boolean structure in decomposable negation normal form (DNNF), and extract from it a Boolean formula whose models correspond to DDTs. This allows us to harness recent advances in both knowledge compilation and satisfiability for efficient and scalable DDT computation in practice. Furthermore, we show how we can generate a DNNF structure compactly encoding all DDTs of the problem and use it to obtain a cost-optimal DDT in time linear in the size of the structure. Experimental results from a real-world application show that our method can compute DDTs in less than 1 second for instances that were previously intractable, and cost-optimal DDTs in less than 20 seconds where previous approaches could not even compute an arbitrary DDT.

Policy search is a successful approach to reinforcement learning. However, policy improvements often result in the loss of information. Hence, it has been marred by premature convergence and implausible solutions. As first suggested in the context of covariant policy gradients, many of these problems may be addressed by constraining the information loss. In this paper, we continue this path of reasoning and suggest the Relative Entropy Policy Search (REPS) method. The resulting method differs significantly from previous policy gradient approaches and yields an exact update step. It can be shown to work well on typical reinforcement learning benchmark problems.

Conjunctive query answering is a key reasoning service for many ontology-based applications. In order to improve scalability, many Semantic Web query answering systems give up completeness (i.e., they do not guarantee to return all query answers). It may be useful or even critical to the designers and users of such systems to understand how much and what kind of information is (potentially) being lost. We present a method for generating test data that can be used to provide at least partial answers to these questions, a purpose for which existing benchmarks are not well suited. In addition to developing a general framework that formalises the problem, we describe practical data generation algorithms for some popular ontology languages, and present some very encouraging results from our preliminary evaluation.

Modern complex games and simulations pose many challenges for an intelligent agent, including partial observability, continuous time and effects, hostile opponents, and exogenous events. We present ARTUE (Autonomous Response to Unexpected Events), a domain-independent autonomous agent that dynamically reasons about what goals to pursue in response to unexpected circumstances in these types of environments. ARTUE integrates AI research in planning, environment monitoring, explanation, goal generation, and goal management. To explain our conceptualization of the problem ARTUE addresses, we present a new conceptual framework, goal-driven autonomy, for agents that reason about their goals. We evaluate ARTUE on scenarios in the TAO Sandbox, a Navy training simulation, and demonstrate its novel architecture, which includes components for Hierarchical Task Network planning, explanation, and goal management. Our evaluation shows that ARTUE can perform well in a complex environment and that each component is necessary and contributes to the performance of the integrated system.

Auction processes have been a well-established research Different from one-shot combinatorial auctions, the main theme in economics and recently become an emerging research issue of a dynamic auction is whether the procedure can lead topic in AI due to a set of related computational challenges to an equilibrium state (Walrasian equilibrium) at which all (Cramton et al. 2006). It is well-known that the problem the selling items are effectively allocated to the buyers (equilibrium of winner determination in a combinatorial auction is allocation) and the price of each bundle of items NPcomplete (Rothkopf et al. 1998; Sandholm 2002). However, gives the buyers their best values (equilibrium price). It most of the discussions on the computational issues has been observed that without certain assumptions on buyers' of combinatorial auctions are based on one-shot sealed-bid value functions, there is no guarantee for a dynamic mechanisms. This paper aims to make a contribution towards auction to converge toward an equilibrium (Gul and Stacchetti the discussions on dynamic procedures of combinatorial 1999). Kelso and Crawford (1982) proposed a condition, auctions.

An optimization variant of a problem of path planning for multiple robots is addressed in this work. The task is to find spatial-temporal path for each robot of a group of robots such that each robot can reach its destination by navigating through these paths. In the optimization variant of the problem, there is an additional requirement that the makespan of the solution must be as small as possible. A proof of the claim that optimal path planning for multiple robots is NP‑complete is sketched in this short paper.

Answering queries posed over knowledge bases is a central problem in knowledge representation and database theory. In the database area, checking query containment is an important query optimization and schema integration technique. In knowledge representation it has been used for object classification, schema integration, service discovery, and more. In the presence of a knowledge base, the problem of query containment is strictly related to that of query answering; indeed, the two are reducible to each other; we focus on the latter, and our results immediately extend to the former.

Answer Set Programming (ASP) has been deployed in many applications, thanks to the availability of efficient solvers. Most programs encountered in practice have an important property: Their predicate arities are bounded by a constant, and in this case it is known that the relevant computations can be done using polynomial space. However, all competitive ASP systems rely on grounding, due to which they may use exponential space for these programs. We present three evaluation methods that respect the polynomial space bound and a generic framework architecture for realization. Experimental results for a prototype implementation indicate that the methods are effective. They show not only benign space consumption, but interestingly also good runtime compared to some state of the art ASP solvers.

The selection of the action to do next is one of the central problems faced by autonomous agents. In AI, three approaches have been used to address this problem: the programming-based approach, where the agent controller is given by the programmer, the learning-based approach, where the controller is induced from experience via a learning algorithm, and the model-based approach, where the controller is derived from a model of the problem. Planning in AI is best conceived as the model-based approach to action selection. The models represent the initial situation, actions, sensors, and goals. The main challenge in planning is computational, as all the models, whether accommodating feedback and uncertainty or not, are intractable in the worst case. In this article, I review some of the models considered in current planning research, the progress achieved in solving these models, and some of the open problems.

Finite-state controllers represent an effective action selection mechanisms widely used in domains such as video-games and mobile robotics. In contrast to the policies obtained from MDPs and POMDPs, finite-state controllers have two advantages: they are often extremely compact, and they are general, applying to many problems and not just one. A limitation of finite-state controllers, on the other hand, is that they are written by hand. In this paper, we address this limitation, presenting a method for deriving controllers automatically from models. The models represent a class of contingent problems where actions are deterministic and some fluents are observable. The problem of deriving a controller is converted into a conformant problem that is solved using classical planners, taking advantage of a complete translation into classical planning introduced recently. The controllers derived are ‘general’ in the sense that they do not solve the original problem only, but many variations as well, including changes in the size of the problem or in the uncertainty of the initial situation and action effects. Several experiments illustrating the automatic derivation of controllers are presented.