In this paper, we develop a heuristic, progression based conformant planner, called CNF, which represents belief states by a special type of CNF formulae, called CNF CNF-state. We define a transition function φ CNF for computing the successor belief state resulting from the execution of an action in a belief state and prove that it is sound and complete with respect to the complete semantics defined in the literature for conformant planning. We evaluate the performance of CNF against other state-of-the-art conformant planners and identify the classes of problems where CNF is comparable with other state-of-the-art planners or scales up better than other planners. We also develop a technique called oneof relaxation which helps boost the performance of CNF. We characterize the domains where this technique can be applied and validate this idea by proposing a new set of benchmarks that is really difficult for other planners yet easy for CNF.

Research effort, with its emphasis on evaluation and measurable progress, things began to change. Instead SHRDLU (WIN72) is perhaps the canonical example. of systems whose architecture and vocabulary were The rapid growth of efforts to found the next generation of based on linguistic theory (in this case acoustic phonetics), systems on general-purpose knowledge representation languages new approaches based on statistical modelling and Bayesian (I'm thinking of several varieties of semantic nets, probability emerged and quickly spread. "Every time I fire a from plain to partitioned, as well as KRL, KL-ONE and linguist my system's performance improves" (Fred Jellinek, their successors, ending (not yet, of course) with CYC (See head of speech recognition at IBM, c. 1980, latterly repudiated (BRA08) for all these) stumbled to a halt once their failure by Fred but widely attested). As advanced from resolution theorem provers through a number more and more problems are re-conceived as instances of of stages to the current proliferation of a range of Description the noisy channel model, the empiricist paradigm continually Logic'reasoners'; Whereas in the 1970s and 1980s there grew, so did the need to manage the impact of change and was real energy and optimism at the interface between computational conflict: enter'truth maintenance', subsequently renamed and theoretical linguistics, the overwhelming success'reason maintenance'. While still using some of But outflanking these'normal science' advances of AI, the terminology of linguistic theory, computational linguistics the paradigm shifters were coming up fast on the outside: practioners are increasingly detached from theory itself, over the last ten years machine learning has spread from which has suffered a, perhaps connected, loss of energy and small specialist niches such as speech recognition to become sense of progress.

The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearls belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes.

As historically acknowledged in the Reasoning about Actions and Change community, intuitiveness of a logical domain description cannot be fully automated. Moreover, like any other logical theory, action theories may also evolve, and thus knowledge engineers need revision methods to help in accommodating new incoming information about the behavior of actions in an adequate manner. The present work is about changing action domain descriptions in multimodal logic. Its contribution is threefold: first we revisit the semantics of action theory contraction proposed in previous work, giving more robust operators that express minimal change based on a notion of distance between Kripke-models. Second we give algorithms for syntactical action theory contraction and establish their correctness with respect to our semantics for those action theories that satisfy a principle of modularity investigated in previous work. Since modularity can be ensured for every action theory and, as we show here, needs to be computed at most once during the evolution of a domain description, it does not represent a limitation at all to the method here studied. Finally we state AGM-like postulates for action theory contraction and assess the behavior of our operators with respect to them. Moreover, we also address the revision counterpart of action theory change, showing that it benefits from our semantics for contraction.

We propose a new approach to the analysis of Loopy Belief Propagation (LBP) by establishing a formula that connects the Hessian of the Bethe free energy with the edge zeta function. The formula has a number of theoretical implications on LBP. It is applied to give a sufficient condition that the Hessian of the Bethe free energy is positive definite, which shows non-convexity for graphs with multiple cycles. The formula clarifies the relation between the local stability of a fixed point of LBP and local minima of the Bethe free energy. We also propose a new approach to the uniqueness of LBP fixed point, and show various conditions of uniqueness.

We show that an important and computationally challenging solution space feature of the graph coloring problem (COL), namely the number of clusters of solutions, can be accurately estimated by a technique very similar to one for counting the number of solutions. This cluster counting approach can be naturally written in terms of a new factor graph derived from the factor graph representing the COL instance. Using a variant of the Belief Propagation inference framework, we can efficiently approximate cluster counts in random COL problems over a large range of graph densities. We illustrate the algorithm on instances with up to 100, 000 vertices. Moreover, we supply a methodology for computing the number of clusters exactlyusing advanced techniques from the knowledge compilation literature.

We show that an important and computationally challenging solution space feature of the graph coloring problem (COL), namely the number of clusters of solutions, can be accurately estimated by a technique very similar to one for counting the number of solutions. This cluster counting approach can be naturally written in terms of a new factor graph derived from the factor graph representing the COL instance. Using a variant of the Belief Propagation inference framework, we can efficiently approximate cluster counts in random COL problems over a large range of graph densities. We illustrate the algorithm on instances with up to 100, 000 vertices. Moreover, we supply a methodology for computing the number of clusters exactly using advanced techniques from the knowledge compilation literature.

We show that an important and computationally challenging solution space feature of the graph coloring problem (COL), namely the number of clusters of solutions, can be accurately estimated by a technique very similar to one for counting the number of solutions. This cluster counting approach can be naturally written in terms of a new factor graph derived from the factor graph representing the COL instance. Using a variant of the Belief Propagation inference framework, we can efficiently approximate cluster counts in random COL problems over a large range of graph densities. We illustrate the algorithm on instances with up to 100, 000 vertices. Moreover, we supply a methodology for computing the number of clusters exactly using advanced techniques from the knowledge compilation literature.

We study the profit-maximization problem of a monopolistic market-maker who sets two-sided prices in an asset market. The sequential decision problem is hard to solve because the state space is a function. We demonstrate that the belief state is well approximated by a Gaussian distribution. We prove a key monotonicity property of the Gaussian state update which makes the problem tractable, yielding the first optimal sequential market-making algorithm in an established model. The algorithm leads to a surprising insight: an optimal monopolist can provide more liquidity than perfectly competitive market-makers in periods of extreme uncertainty, because a monopolist is willing to absorb initial losses in order to learn a new valuation rapidly so she can extract higher profits later.

Empirical studies have documented cases of belief polarization, where two people withopposing prior beliefs both strengthen their beliefs after observing the same evidence. Belief polarization is frequently offered as evidence of human irrationality, but we demonstrate that this phenomenon is consistent with a fully Bayesian approach to belief revision. Simulation results indicate that belief polarization isnot only possible but relatively common within the set of Bayesian models that we consider. Suppose that Carol has requested a promotion at her company and has received a score of 50 on an aptitude test. Alice, one of the company's managers, began with a high opinion of Carol and became even more confident of her abilities after seeing her test score.