Arrow Research search

Author name cluster

Vaishak Belle

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

66 papers
2 author rows

Possible papers

66

NAI Journal 2026 Journal Article

A Neurosymbolic Approach to Counterfactual Fairness

  • Xenia Heilmann
  • Chiara Manganini
  • Mattia Cerrato
  • Leonhard Kestel
  • Vaishak Belle

Integrating fairness into machine learning models has been an important consideration for the last decade. Here, neurosymbolic models offer a valuable opportunity, as they allow the specification of symbolic, logical constraints that are often guaranteed to be satisfied. However, research on neurosymbolic applications to algorithmic fairness is still in an early stage. In this work, we bridge this gap by integrating counterfactual fairness into the neurosymbolic framework of logic tensor networks (LTN). We use LTN to express accuracy and counterfactual fairness constraints in first-order logic and employ them to achieve desirable levels of both performance and fairness at training time. Our approach is agnostic to the underlying causal model and data generation technique; for this reason, it may be easily integrated into existing pipelines that generate and extract counterfactual examples. We show, through concrete examples on three benchmark datasets, that logical reasoning about counterfactual fairness has some important advantages, among which its intrinsic interpretability, and its flexibility in handling subgroup fairness. Compared to three recent methodologies in counterfactual fairness, our experiments show that a neurosymbolic, LTN-based approach attains better levels of counterfactual fairness.

Details DOI

AAMAS Conference 2026 Conference Paper

Epistemic Modal Logic Meets Algebraic Model Counting

  • Daxin Liu
  • Vaishak Belle

Algebraicmodelcounting(AMC)generalizesweightedmodelcounting to the semiring setting and supports various types of labels (or weights), including numerical ones as used in weighted model counting, but also sets, boolean formulae, polynomials, and many more. One merit of algebraic model counting is that it can be evaluated efficiently in a succinct form of representation by using knowledge compilation, hence, providing a robust and useful framework that covers many different tasks from a variety of different fields. In this paper, we show that a type of epistemic entailment reasoning in a modal logic of only knowing can be solved by recursively calling a series of algebraic model counting tasks. We show that this approach is not limited to the qualitative setting, but is also applicable to the quantitative modal logic of only-believing. Lastly, we propose an AMC-based regression operator that lifts the approach to even dynamic epistemic reasoning.

PDF

AAAI Conference 2026 Conference Paper

The Future Is Neuro-Symbolic: Where Has It Been, and Where Is It Going?

  • Vaishak Belle
  • Gary Marcus

This report explores the evolution and current state of neuro- symbolic artificial intelligence, an approach that integrates neural network capabilities with symbolic reasoning. We trace the historical context from early AI aspirations to modern implementations and successes, highlighting key paradigms, and other logical and semantical considerations. We argue against the “scaling is all you need” hypothesis, and point to persistent challenges in reliable symbolic reasoning with deep and large models. We conclude by suggesting that despite numerous implementation choices and the ”broad church” nature of neuro-symbolic AI, these approaches offer the most promising path towards AI systems that combine pattern recognition with robust reasoning, particularly for applications requiring structured knowledge, explainability, and trustworthiness.

PDF Details DOI

NeSy Conference 2025 Conference Paper

A Neurosymbolic Approach to Counterfactual Fairness

  • Xenia Heilmann
  • Chiara Manganini
  • Mattia Cerrato
  • Vaishak Belle

Integrating fairness into machine learning models has been an important consideration for the last decade. Here, neurosymbolic models offer a valuable opportunity, as they allow the specification of symbolic, logical constraints that are often guaranteed to be satisfied. However, research on neurosymbolic applications to algorithmic fairness is still in an early stage. With our work, we bridge this gap by integrating counterfactual fairness into the neurosymbolic framework of Logic Tensor Networks (LTN). We use LTN to express accuracy and counterfactual fairness constraints in first-order logic and employ them to achieve desirable levels of both performance and fairness at training time. Our approach is agnostic to the underlying causal model and data generation technique; as such, it may be easily integrated into existing pipelines that generate and extract counterfactual examples. We show, through concrete examples on three real-world datasets, that logical reasoning about counterfactual fairness has some important advantages, among which its intrinsic interpretability, and its flexibility in handling subgroup fairness. Compared to three recent methodologies in counterfactual fairness, our experiments show that a neurosymbolic, LTN-based approach attains better levels of counterfactual fairness.

Details

NeSy Conference 2025 Conference Paper

Exploring Verification Frameworks for Social Choice Alignment

  • Jessica Ciupa
  • Vaishak Belle
  • Ekaterina Komendantskaya

The deployment of autonomous agents that interact with humans in safety-critical situations raises new research problems as we move towards fully autonomous systems in domains such as autonomous vehicles or search and rescue. If autonomous agents are placed in a dilemma, how would they act? The literature in computational ethics has explored the actions and learning methods that emerge in ethical dilemmas. However, our position paper examines how ethical dilemmas are not isolated in a social vacuum. Our central claim in our position paper is that to enable trust among all human users, a neuralsymbolic verification of moral preference alignment is required. We propose that the formal robustness properties be applied to social choice modelling. We outline how robustness properties can help validate the formation of stable social preference clusters in deep neural network classifiers. Our initial results highlight the vulnerabilities of models in moral-critical scenarios to perturbations, suggesting a verification-training loop for improved robustness. We position this work as an inquiry into the viability of verifying moral preference alignment, based on our initial results. Ultimately, we aim to contribute to the broader interdisciplinary effort that integrates formal methods, social choice theory, and empirical moral psychology for interpretable computational ethics.

Details

NAI Journal 2025 Journal Article

On the Relevance of Logic for Artificial Intelligence, and the Promise of Neurosymbolic Learning

  • Vaishak Belle

In this position paper, we examine some of the assumptions held about logic and its relevance to the development of modern artificial intelligence (AI), which is primarily driven by deep learning. The paper aims to address fundamental misunderstandings about logic and ultimately argue for the benefits of symbolic formalisms in modeling uncertain worlds. While it is now recognized that statistical associations learned from data are limited in their ability to understand the world, there is still a great deal of criticism and hesitancy regarding the use of symbolic logic to achieve or support a broader vision for AI. By arguing that symbolic logic is more flexible than nonexperts believe, we make a case for neurosymbolic AI, which offers the best of both worlds.

Details DOI

TMLR Journal 2025 Journal Article

Unreasonable effectiveness of LLM reasoning: a doubly cautionary tale of temporal question-answering

  • Dagmara Panas
  • Ali Payani
  • Vaishak Belle

The remarkable success of Large Language Models in modeling both the syntax and the semantics of language has prompted a body of research into language-adjacent abilities, most notably commonsense reasoning. As LLMs' performance continues to advance on successive benchmarks, we turn to temporal reasoning, which lags somewhat behind other tasks due to its more complex logic. We start from previous work, where authors successfully induce (apparent) reasoning by breaking down the problem into a two-step procedure of temporal graph extraction and subsequent reasoning. Specifically, in the first step an LLM is prompted to parse a natural language description into a semi-structured timeline of events; and in the second step, it is given the extracted timeline and prompted to answer a temporal reasoning question. We conjecture that this procedure presents two separate opportunities for introducing errors and further hypothesise that a Neuro-symbolic approach should help in this matter. We follow the recent trend of using external executors in concert with LLMs to carry out exact reasoning and verification. We see the reasoning step of the original two-step procedure as a natural target for a symbolic solver and design a rule-based solution for Temporal Question-Answering, drawing on ideas from Allen’s Interval Algebra. To our surprise, we find that our rule-based reasoner does not improve beyond the previously reported, purely neural solution. It appears that both our approach and the previous method operate at around the limits of achievable performance, imposed by the correctness of information extraction. Such a result seems to suggest that a non-symbolic LLM is capable of symbolic-level reasoning, although upon further investigation we discover that not to be the case. It is not that the neural solution makes no reasoning mistakes, but rather that the LLM manages to compensate for some of its erroneous replies by `short-cutting' to the correct answer in other questions; a.k.a. not reasoning but guessing. Although the effect is not pronounced performance-wise, we feel it is conceptually important: as we argue, production of correct answers is not a measure of reasoning.

PDF Details

AAMAS Conference 2025 Conference Paper

What Is a Counterfactual Cause in Action Theories?

  • Daxin Liu
  • Vaishak Belle

Since the proposal by Halpern and Pearl, reasoning about actual causality has gained increasing attention in artificial intelligence, ranging from domains such as model-checking and verification to reasoning about actions and knowledge. More recently, Batusov and Soutchanski proposed a notion of actual achievement cause in the situation calculus, amongst others, they can determine the cause of quantified effects in a given action history. While intuitively appealing, this notion of cause is not defined in a counterfactual perspective. In this paper, we propose a notion of cause based on counterfactual analysis. In the context of action history, we show that our notion of cause generalizes naturally to a notion of achievement cause.

PDF

NeSy Conference 2024 Conference Paper

Can Large Language Models Put 2 and 2 Together? Probing for Entailed Arithmetical Relationships

  • Dagmara Panas
  • Sohan Seth
  • Vaishak Belle

Abstract Two major areas of interest in the era of Large Language Models regard questions of what do LLMs know, and if and how they may be able to reason, or rather, approximately reason. Since to date these lines of work progressed largely in parallel, we are interested in investigating the intersection: probing for reasoning about the implicitly-held knowledge. Suspecting the performance to be lacking, we use a very simple set-up of comparisons between cardinalities associated with elements of various subjects (e. g. the number of legs of a bird vs. the number of wheels on a tricycle). We empirically demonstrate that although LLMs make steady progress in knowledge acquisition and (pseudo)reasoning with each new GPT release, they remain limited in their capabilities to performing probabilistic retrieval. We argue that pure statistical learning can not cope with the combinatorial explosion inherent in many commonsense reasoning tasks. Further, we emphasise that bigger is not always better and chasing purely statistical improvements is flawed at the core, since it only exacerbates the dangerous conflation of the production of correct answers with genuine reasoning ability.

Details

NeSy Conference 2024 Conference Paper

Ethical Reward Machine

  • Jessica Ciupa
  • Vaishak Belle

Abstract The Ethical Reward Machine investigates reward design involving ethical constraints with reinforcement learning. Designed to promote good behaviour across specific domains, such as simulated driving and search-and-rescue scenarios, the Ethical Reward Machine explores ethical constraints based on Act Deontology and Utilitarianism. Our contribution to the literature is a novel algorithmic pipeline integrating ethical constraints into reinforcement learning through symbolic language. Our findings indicate ethical principles impact the system significantly if there is a dilemma, and that incorporating ethical principles does not increase runtime. Therefore, our results suggest that ethical considerations do not substantially burden computational resources. Ultimately, the overarching objective is to develop and validate a learning framework that ensures AI alignment with human learning and ethical policies.

Details

AAMAS Conference 2024 Conference Paper

Progression with Probabilities in the Situation Calculus: Representation and Succinctness

  • Daxin Liu
  • Vaishak Belle

Progression in the Situation Calculus is perhaps one of the most extensively studied cases of updating logical theories over a sequence of actions. While it generally requires second-order logic, several useful first-order and tractable cases have been identified. Recently, there has been an interest in studying the progression of probabilistic knowledge bases expressed using degrees of belief on first-order formulas. However, although a few results exist, they do not provide much clarity about how this progression can be computed or represented in a feasible manner. In this paper, we address this problem for the first time. We first examine the progression of a probabilistic knowledge base (PKB) in a world-level representation; in particular, we show that such a representation is closed under progression for any localeffect actions with quantifier-free contexts. We also propose a more succinct representation of the probabilistic knowledge base, i. e. factored-representation PKB. For this type of PKB, we study the conditions for progression to remain succinct.

PDF

NeSy Conference 2024 Conference Paper

ToM-LM: Delegating Theory of Mind Reasoning to External Symbolic Executors in Large Language Models

  • Weizhi Tang
  • Vaishak Belle

Abstract Theory of Mind (ToM) refers to the ability of individuals to attribute mental states to others. While Large Language Models (LLMs) have shown some promise with ToM ability, they still struggle with complex ToM reasoning. Our approach leverages an external symbolic executor, specifically the SMCDEL model checker, and fine-tuning to improve the ToM reasoning ability of LLMs. In our approach, an LLM is first fine-tuned through pairs of natural language and symbolic formulation representation of ToM problems and is then instructed to generate the symbolic formulation with a one-shot in-context example. The generated symbolic formulation is then executed by the SMCDEL model checker to perform transparent and verifiable ToM reasoning and give the final result. We demonstrate that our approach, ToM-LM, shows a significant improvement over all the constructed baselines. Our study proposes a novel view about externalizing a particular component of ToM reasoning, mainly reasoning about beliefs, and suggests generalizing it to other aspects of ToM reasoning.

Details

AAMAS Conference 2023 Conference Paper

A Logic of Only-Believing over Arbitrary Probability Distributions

  • Qihui Feng
  • Daxin Liu
  • Vaishak Belle
  • Gerhard Lakemeyer

When it comes to robotic agents operating in an uncertain world, a major concern in knowledge representation is to better relate high-level logical accounts of beliefs and actions to the low-level probabilistic sensorimotor data. Perhaps the most general formalism for dealing with degrees of belief in formulas, and in particular, with how that should evolve in the presence of noisy sensing and acting is the first-order logical account by Bacchus, Halpern, and Levesque. The main advantage of such a logical account is that it allows a specification of beliefs that can be partial or incomplete, in keeping with whatever information is available about the domain, making it particularly attractive for general-purpose cognitive robotics. Recently, this model was extended to handle continuous probability distributions. However, it is limited to finitely many nullary fluents and defines beliefs and integration axiomatically, the latter making semantic proofs about beliefs and meta-beliefs difficult. In this paper, we revisit the continuous model and cast it in a modal language. We will go beyond nullary fluents and allow fluents of arbitrary arity as is usual in the standard situation calculus. This necessitates a new and general treatment of probabilities on possible worlds, where we define measures on uncountably many worlds that interpret infinitely many fluents. We then show how this leads to a fairly simple definition of knowing, degrees of belief, and onlyknowing. Properties thereof will also be analyzed. In this paper, we focus on the static setting and conclude with some thoughts about extending this account to actions as the next step and what challenges might arise.

PDF

AAMAS Conference 2023 Conference Paper

A Web-based Tool for Detecting Argument Validity and Novelty

  • Sandrine Chausson
  • Ameer Saadat-Yazdi
  • Xue Li
  • Jeff Z. Pan
  • Vaishak Belle
  • Nadin Kökciyan
  • Björn Ross

Individuals engage in arguments on an everyday basis as they seek to obtain information about current affairs and engage with social media. While fact-checkers are available to help dispel misinformation, it is almost impossible for users to verify every single claim they encounter. This means that oftentimes, it is left to the user to decide whether a claim is well supported. To address this, we have developed a Web interface that allows users to input an argument, and our developed framework automatically detects its validity (soundness of logical deduction) and novelty (whether the argument is non-circular). Our Web-based tool could be used by social media users who wish to evaluate the information they consume. As part of one of the modules developed at the University of Edinburgh, our tool will be deployed as a teaching tool for the students who study argumentation.

PDF

AAMAS Conference 2023 Conference Paper

Abstracting Noisy Robot Programs

  • Till Hofmann
  • Vaishak Belle

Abstraction is a commonly used process to represent some lowlevel system by a more coarse specification with the goal to omit unnecessary details while preserving important aspects. While recent work on abstraction in the situation calculus has focused on non-probabilistic domains, we describe an approach to abstraction of probabilistic and dynamic systems. Based on a variant of the situation calculus with probabilistic belief, we define a notion of bisimulation that allows to abstract a detailed probabilistic basic action theory with noisy actuators and sensors by a possibly non-stochastic basic action theory. By doing so, we obtain abstract Golog programs that omit unnecessary details and which can be translated to detailed programs for execution. This simplifies the implementation of noisy robot programs, opens up the possibility of using non-stochastic reasoning methods (e. g. , planning) on probabilistic problems, and provides domain descriptions that are more easily interpretable.

PDF

AAMAS Conference 2023 Conference Paper

Actions, Continuous Distributions and Meta-Beliefs

  • Vaishak Belle

In this work, we propose a new modal logical language for reasoning about noisy actions and sensors in an epistemic setting. In the reasoning about actions literature, there are only a few frameworks for modelling probabilistic noise, and even less in dealing with continuous probability distributions. In the first model of its kind, we show how a rich theory of actions with beliefs, meta-beliefs and only knowing can be defined over discrete, continuous and mixed discrete-continuous distributions.

PDF

KR Conference 2023 Conference Paper

Concerning Measures in a First-order Logic with Actions and Meta-beliefs

  • Daxin Liu
  • Qihui Feng
  • Vaishak Belle
  • Gerhard Lakemeyer

The unification of logic and probability has been seen as a long-standing concern in philosophy and mathematical logic. In this paper, we propose a new general probabilistic modal logic of belief and only-believing in the situation calculus. Our logic can express both continuous and discrete degrees of belief. More importantly, expressing degrees of belief for arbitrary first-order formulas in a dynamic setting is possible for the first time, going well beyond previous proposals where fluents are assumed to be nullary or discrete. We show that our notion of belief retains many of the properties known from the previous related work.

PDF Details DOI

AIJ Journal 2023 Journal Article

Epistemic planning: Perspectives on the special issue

  • Vaishak Belle
  • Thomas Bolander
  • Andreas Herzig
  • Bernhard Nebel

Epistemic planning is the enrichment of automated planning with epistemic notions such as knowledge and belief. In general, single-agent epistemic planning considers the following problem: given an agent's current state of knowledge, and a desirable state of knowledge, how does it get from one to the other? In multi-agent epistemic planning, the current and desirable states of knowledge might also refer to the states of knowledge of other agents, including higher-order knowledge like ensuring that agent A doesn't get to know that agent B knows P. Single-agent epistemic planning is of central importance in settings where agents need to be able to reason about their own lack of knowledge and, e. g. , make plans of how to achieve the required knowledge. Multi-agent epistemic planning is essential for coordination and collaboration among multiple agents, where success can only be expected if agents are able to reason about the knowledge, uncertainty and capabilities of other agents. It is a relatively recent area of research involving several sub-areas of artificial intelligence, such as automated planning, decision-theoretic planning, epistemic logic, strategic reasoning and knowledge representation & reasoning. In order to achieve formalisms and systems for epistemic planning that are both expressive and practically efficient, it is necessary to combine state of the art from several such sub-areas of artificial intelligence that have so far been considered mostly in separation. Application areas of epistemic planning include mobile service robots, explaining planning, game playing, human-robot interaction and social robotics. For this special issue of AIJ, we invited papers on theory, applications, and implemented systems of epistemic planning. In this document, we summarize the accepted papers whilst recapping the essentials of epistemic planning.

Details DOI

JELIA Conference 2023 Invited Paper

Excursions in First-Order Logic and Probability: Infinitely Many Random Variables, Continuous Distributions, Recursive Programs and Beyond

  • Vaishak Belle

Abstract The unification of the first-order logic and probability has been seen as a long-standing concern in philosophy, AI and mathematics. In this talk, I will briefly review our recent results on revisiting that unification. Although there are plenty of approaches in communities such as statistical relational learning, automated planning, and neuro-symbolic AI that leverage and develop languages with logical and probabilistic aspects, they almost always restrict the representation as well as the semantic framework in various ways which do not fully explain how to combine first-order logic and probability theory in a general way. In many cases, this restriction is justified because it may be necessary to focus on practicality and efficiency. However, the search for a restriction-free mathematical theory remains ongoing. In this article, we discuss our recent results regarding the development of languages that support arbitrary quantification, possibly infinitely many random variables, both discrete and continuous distributions, as well as programming languages built on top of such features to include recursion and branching control.

Details

AAMAS Conference 2023 Conference Paper

Learnability with PAC Semantics for Multi-agent Beliefs

  • Ionela G. Mocanu
  • Vaishak Belle
  • Brendan Juba

This work proposes a new technical foundation for demonstrating Probably Approximately Correct (PAC) learning with multiagent epistemic logics, using implicit learning to incorporate observations into the background knowledge. We explore the sample complexity and the circumstances in which the algorithm can be made efficient.

PDF

KR Conference 2023 Conference Paper

Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures

  • Paulius Dilkas
  • Vaishak Belle

First-order model counting (FOMC) is a computational problem that asks to count the models of a sentence in finite-domain first-order logic. In this paper, we argue that the capabilities of FOMC algorithms to date are limited by their inability to express many types of recursive computations. To enable such computations, we relax the restrictions that typically accompany domain recursion and generalise the circuits used to express a solution to an FOMC problem to directed graphs that may contain cycles. To this end, we adapt the most well-established (weighted) FOMC algorithm ForcLift to work with such graphs and introduce new compilation rules that can create cycle-inducing edges that encode recursive function calls. These improvements allow the algorithm to find efficient solutions to counting problems that were previously beyond its reach, including those that cannot be solved efficiently by any other exact FOMC algorithm. We end with a few conjectures on what classes of instances could be domain-liftable as a result.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Transparency in Sum-Product Network Decompilation

  • Ioannis Papantonis
  • Vaishak Belle

Sum-product networks guarantee that conditionals and marginals can be computed efficiently, for a wide range of models, bypassing the hardness of inference. However, this advantage comes at the expense of transparency, since it is unclear how variables interact in sum-product networks. Due to this, a series of decompilation algorithms transform sum-product networks back to Bayesian networks. In this work, we first study the transparency and causal utility of the resulting Bayesian networks. We then propose a novel decompilation algorithm to address the identified limitations.

Details

ECAI Conference 2023 Conference Paper

Verifying Belief-Based Programs via Symbolic Dynamic Programming

  • Daxin Liu 0002
  • Qinfei Huang
  • Vaishak Belle
  • Gerhard Lakemeyer

Belief-based programming is a probabilistic extension of the Golog programming language family, where every action and sensing could be noisy and every test refers to the subjective beliefs of the agent. Such characteristics make it rather suitable for robot control in a partial-observable uncertain environment. Recently, efforts have been made in providing formal semantics for belief programs and investigating the hardness of verifying belief programs. Nevertheless, a general algorithm that actually conducts the verification is missing. In this paper, we propose an algorithm based on symbolic dynamic programming to verify belief programs, an approach that generalizes the dynamic programming technique for solving (partially observable) Markov decision processes, i. e. (PO)MDP, by exploiting the symbolic structure in the solution of first-order (PO)MDPs induced by belief program execution.

Details

AIJ Journal 2022 Journal Article

Analyzing generalized planning under nondeterminism

  • Vaishak Belle

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.

Details DOI

AIJ Journal 2022 Journal Article

Efficient multi-agent epistemic planning: Teaching planners about nested belief

  • Christian Muise
  • Vaishak Belle
  • Paolo Felli
  • Sheila McIlraith
  • Tim Miller
  • Adrian R. Pearce
  • Liz Sonenberg

Many AI applications involve the interaction of multiple autonomous agents, requiring those agents to reason about their own beliefs, as well as those of other agents. However, planning involving nested beliefs is known to be computationally challenging. In this work, we address the task of synthesizing plans that necessitate reasoning about the beliefs of other agents. We plan from the perspective of a single agent with the potential for goals and actions that involve nested beliefs, non-homogeneous agents, co-present observations, and the ability for one agent to reason as if it were another. We formally characterize our notion of planning with nested belief, and subsequently demonstrate how to automatically convert such problems into problems that appeal to classical planning technology for solving efficiently. Our approach represents an important step towards applying the well-established field of automated planning to the challenging task of planning involving nested beliefs of multiple agents.

Details DOI

AAAI Conference 2022 Conference Paper

MultiplexNet: Towards Fully Satisfied Logical Constraints in Neural Networks

  • Nick Hoernle
  • Rafael Michael Karampatsis
  • Vaishak Belle
  • Kobi Gal

We propose a novel way to incorporate expert knowledge into the training of deep neural networks. Many approaches encode domain constraints directly into the network architecture, requiring non-trivial or domain-specific engineering. In contrast, our approach, called MultiplexNet, represents domain knowledge as a quantifier-free logical formula in disjunctive normal form (DNF) which is easy to encode and to elicit from human experts. It introduces a latent Categorical variable that learns to choose which constraint term optimizes the error function of the network and it compiles the constraints directly into the output of existing learning algorithms. We demonstrate the efficacy of this approach empirically on several classical deep learning tasks, such as density estimation and classification in both supervised and unsupervised settings where prior knowledge about the domains was expressed as logical constraints. Our results show that the MultiplexNet approach learned to approximate unknown distributions well, often requiring fewer data samples than the alternative approaches. In some cases, MultiplexNet finds better solutions than the baselines; or solutions that could not be achieved with the alternative approaches. Our contribution is in encoding domain knowledge in a way that facilitates inference. We specifically focus on quantifier-free logical formulae that are specified over the output domain of a network. We show that this approach is both efficient and general; and critically, our approach guarantees 100% constraint satisfaction in a network’s output.

PDF Details

IJCAI Conference 2021 Conference Paper

Learning Implicitly with Noisy Data in Linear Arithmetic

  • Alexander Rader
  • Ionela G Mocanu
  • Vaishak Belle
  • Brendan Juba

Robust learning in expressive languages with real-world data continues to be a challenging task. Numerous conventional methods appeal to heuristics without any assurances of robustness. While probably approximately correct (PAC) Semantics offers strong guarantees, learning explicit representations is not tractable, even in propositional logic. However, recent work on so-called “implicit" learning has shown tremendous promise in terms of obtaining polynomial-time results for fragments of first-order logic. In this work, we extend implicit learning in PAC-Semantics to handle noisy data in the form of intervals and threshold uncertainty in the language of linear arithmetic. We prove that our extended framework keeps the existing polynomial-time complexity guarantees. Furthermore, we provide the first empirical investigation of this hitherto purely theoretical framework. Using benchmark problems, we show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice.

PDF Details DOI

UAI Conference 2021 Conference Paper

Lifted reasoning meets weighted model integration

  • Jonathan Feldstein
  • Vaishak Belle

Exact inference in probabilistic graphical models is particularly challenging in the presence of relational and other deterministic constraints. For discrete domains, weighted model counting has emerged as an effective and general approach in a variety of formalisms. Weighted first-order model counting, which allows relational atoms and function-free first order logic has pushed the envelope further, by exploiting symmetry properties over indistinguishable groups of objects, and by extension avoids the need to perform inference on the exponential ground theory. Given the limitation to discrete domains, the formulation of weighted model integration was proposed as an extension to weighted model counting for mixed discrete-continuous domains over both symbolic and numeric weight functions. While that formulation has enjoyed considerable attention in recent years, there is very little understanding on whether the task can be solved at a lifted level, that is, whether we can reason with relational models by avoiding grounding. In this paper, we consider this question. We show how to generalize algorithmic ideas known in the circuit compilation for function-free lifted inference to functions with a continuous range.

Details

UAI Conference 2021 Conference Paper

Weighted model counting with conditional weights for Bayesian networks

  • Paulius Dilkas
  • Vaishak Belle

Weighted model counting (WMC) has emerged as the unifying inference mechanism across many (probabilistic) domains. Encoding an inference problem as an instance of WMC typically necessitates adding extra literals and clauses. This is partly so because the predominant definition of WMC assigns weights to models based on weights on literals, and this severely restricts what probability distributions can be represented. We develop a measure-theoretic perspective on WMC and propose a way to encode conditional weights on literals analogously to conditional probabilities. This representation can be as succinct as standard WMC with weights on literals but can also expand as needed to represent probability distributions with less structure. To demonstrate the performance benefits of conditional weights over the addition of extra literals, we develop a new WMC encoding for Bayesian networks and adapt a state-of-the-art WMC algorithm ADDMC to the new format. Our experiments show that the new encoding significantly improves the performance of the algorithm on most benchmark instances.

Details

SAT Conference 2021 Conference Paper

Weighted Model Counting Without Parameter Variables

  • Paulius Dilkas
  • Vaishak Belle

Abstract Weighted model counting (WMC) is a powerful computational technique for a variety of problems, especially commonly used for probabilistic inference. However, the standard definition of WMC that puts weights on literals often necessitates WMC encodings to include additional variables and clauses just so each weight can be attached to a literal. This paper complements previous work by considering WMC instances in their full generality and using recent state-of-the-art WMC techniques based on pseudo-Boolean function manipulation, competitive with the more traditional WMC algorithms based on knowledge compilation and backtracking search. We present an algorithm that transforms WMC instances into a format based on pseudo-Boolean functions while eliminating around 43 % of variables on average across various Bayesian network encodings. Moreover, we identify sufficient conditions for such a variable removal to be possible. Our experiments show significant improvement in WMC-based Bayesian network inference, outperforming the current state of the art.

Details

ECAI Conference 2020 Conference Paper

Logical Interpretations of Autoencoders

  • Anton Fuxjaeger
  • Vaishak Belle

The unification of low-level perception and high-level reasoning is a long-standing problem in artificial intelligence, which has the potential to not only bring the areas of logic and learning closer together but also demonstrate how abstract concepts might emerge from sensory data. Precisely because deep learning methods dominate perception-based learning, including vision, speech, and linguistic grammar, there is fast-growing literature on how to integrate symbolic reasoning and deep learning. Broadly, efforts seem to fall into three camps: those focused on defining a logic whose formulas capture deep learning, ones that integrate symbolic constraints in deep learning, and others that allow neural computations and symbolic reasoning to co-exist separately, to enjoy the strengths of both worlds. In this paper, we identify another dimension to this inquiry: what do the hidden layers really capture, and how can we reason about that logically? In particular, we consider variational autoencoders that are widely used for dimensionality reduction and inject a symbolic generative framework onto the feature layer. This allows us, among other things, to generate example images for a class to get a sense of what was learned. Moreover, the modular structure of the proposed model makes it possible to learn relations over multiple images at a time, as well as handle noisy labels. Our empirical evaluations show the promise of this inquiry.

Details

ECAI Conference 2020 Conference Paper

Polynomial-Time Implicit Learnability in SMT

  • Ionela G. Mocanu
  • Vaishak Belle
  • Brendan Juba

To deploy knowledge-based systems in the real world, the challenge of knowledge acquisition must be addressed. Knowledge engineering by hand is a daunting task, so machine learning has been widely proposed as an alternative. However, machine learning has difficulty acquiring rules that feature the kind of exceptions that are prevalent in real-world knowledge. Moreover, it is conjectured to be impossible to reliably learn representations featuring a desirable level of expressiveness. Works by Khardon and Roth and by Juba proposed solutions to such problems by learning to reason directly, bypassing the intractable step of producing an explicit representation of the learned knowledge. These works focused on Boolean, propositional logics. In this work, we consider such implicit learning to reason for arithmetic theories, including logics considered with satisfiability modulo theory (SMT) solvers. We show that for standard fragments of linear arithmetic, we can learn to reason efficiently. These results are consequences of a more general finding: we show that there is an efficient reduction from the learning to reason problem for a logic to any sound and complete solver for that logic.

Details

AIJ Journal 2020 Journal Article

Regression and progression in stochastic domains

  • Vaishak Belle
  • Hector J. Levesque

Reasoning about degrees of belief in uncertain dynamic worlds is fundamental to many applications, such as robotics and planning, where actions modify state properties and sensors provide measurements, both of which are prone to noise. With the exception of limited cases such as Gaussian processes over linear phenomena, belief state evolution can be complex and hard to reason with in a general way, especially when the agent has to deal with categorical assertions, incomplete information such as disjunctive knowledge, as well as probabilistic knowledge. Among the many approaches for reasoning about degrees of belief in the presence of noisy sensing and acting, the logical account proposed by Bacchus, Halpern, and Levesque is perhaps the most expressive, allowing for such belief states to be expressed naturally as constraints. While that proposal is powerful, the task of how to plan effectively is not addressed. In fact, at a more fundamental level, the task of projection, that of reasoning about beliefs effectively after acting and sensing, is left entirely open. To aid planning algorithms, we study the projection problem in this work. In the reasoning about actions literature, there are two main solutions to projection: regression and progression. Both of these have proven enormously useful for the design of logical agents, essentially paving the way for cognitive robotics. Roughly, regression reduces a query about the future to a query about the initial state. Progression, on the other hand, changes the initial state according to the effects of each action and then checks whether the formula holds in the updated state. In this work, we show how both of these generalize in the presence of degrees of belief, noisy acting and sensing. Our results allow for both discrete and continuous probability distributions to be used in the specification of beliefs and dynamics.

Details DOI

NeurIPS Conference 2019 Conference Paper

Implicitly learning to reason in first-order logic

  • Vaishak Belle
  • Brendan Juba

We consider the problem of answering queries about formulas of first-order logic based on background knowledge partially represented explicitly as other formulas, and partially represented as examples independently drawn from a fixed probability distribution. PAC semantics, introduced by Valiant, is one rigorous, general proposal for learning to reason in formal languages: although weaker than classical entailment, it allows for a powerful model theoretic framework for answering queries while requiring minimal assumptions about the form of the distribution in question. To date, however, the most significant limitation of that approach, and more generally most machine learning approaches with robustness guarantees, is that the logical language is ultimately essentially propositional, with finitely many atoms. Indeed, the theoretical findings on the learning of relational theories in such generality have been resoundingly negative. This is despite the fact that first-order logic is widely argued to be most appropriate for representing human knowledge. In this work, we present a new theoretical approach to robustly learning to reason in first-order logic, and consider universally quantified clauses over a countably infinite domain. Our results exploit symmetries exhibited by constants in the language, and generalize the notion of implicit learnability to show how queries can be computed against (implicitly) learned first-order background knowledge.

PDF Details

IJCAI Conference 2018 Conference Paper

Efficient Symbolic Integration for Probabilistic Inference

  • Samuel Kolb
  • Martin Mladenov
  • Scott Sanner
  • Vaishak Belle
  • Kristian Kersting

Weighted model integration (WMI) extends weighted model counting (WMC) to the integration of functions over mixed discrete-continuous probability spaces. It has shown tremendous promise for solving inference problems in graphical models and probabilistic programs. Yet, state-of-the-art tools for WMI are generally limited either by the range of amenable theories, or in terms of performance. To address both limitations, we propose the use of extended algebraic decision diagrams (XADDs) as a compilation language for WMI. Aside from tackling typical WMI problems, XADDs also enable partial WMI yielding parametrized solutions. To overcome the main roadblock of XADDs -- the computational cost of integration -- we formulate a novel and powerful exact symbolic dynamic programming (SDP) algorithm that seamlessly handles Boolean, integer-valued and real variables, and is able to effectively cache partial computations, unlike its predecessor. Our empirical results demonstrate that these contributions can lead to a significant computational reduction over existing probabilistic inference algorithms.

PDF Details

AAMAS Conference 2018 Conference Paper

On Plans With Loops and Noise

  • Vaishak Belle

In an influential paper, Levesque proposed a formal specification for analysing the correctness of program-like plans, such as conditional plans, iterative plans, and knowledge-based plans. He motivated a logical characterisation within the situation calculus that included binary sensing actions. While the characterisation does not immediately yield a practical algorithm, the specification serves as a general skeleton to explore the synthesis of program-like plans for reasonable, tractable fragments. 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 sensing is exact and actions are deterministic. Building on a situation calculus theory for reasoning about degrees of belief and noise, we revisit the execution semantics of generalised plans. The specification is then used to analyse the correctness of example plans.

PDF

AIJ Journal 2018 Journal Article

Reasoning about discrete and continuous noisy sensors and effectors in dynamical systems

  • Vaishak Belle
  • Hector J. Levesque

Among the many approaches for reasoning about degrees of belief in the presence of noisy sensing and acting, the logical account proposed by Bacchus, Halpern, and Levesque is perhaps the most expressive. While their formalism is quite general, it is restricted to fluents whose values are drawn from discrete finite domains, as opposed to the continuous domains seen in many robotic applications. In this work, we show how this limitation in that approach can be lifted. By dealing seamlessly with both discrete distributions and continuous densities within a rich theory of action, we provide a very general logical specification of how belief should change after acting and sensing in complex noisy domains.

Details DOI

IJCAI Conference 2017 Conference Paper

Logic meets Probability: Towards Explainable AI Systems for Uncertain Worlds

  • Vaishak Belle

Logical AI is concerned with formal languages to represent and reason with qualitative specifications; statistical AI is concerned with learning quantitative specifications from data. To combine the strengths of these two camps, there has been exciting recent progress on unifying logic and probability. We review the many guises for this union, while emphasizing the need for a formal language to represent a system's knowledge. Formal languages allow their internal properties to be robustly scrutinized, can be augmented by adding new knowledge, and are amenable to abstractions, all of which are vital to the design of intelligent systems that are explainable and interpretable.

PDF Details

AAAI Conference 2017 Conference Paper

Open-Universe Weighted Model Counting

  • Vaishak Belle

Weighted model counting (WMC) has recently emerged as an effective and general approach to probabilistic inference, offering a computational framework for encoding a variety of formalisms, such as factor graphs and Bayesian networks. The advent of large-scale probabilistic knowledge bases has generated further interest in relational probabilistic representations, obtained by according weights to first-order formulas, whose semantics is given in terms of the ground theory, and solved by WMC. A fundamental limitation is that the domain of quantification, by construction and design, is assumed to be finite, which is at odds with areas such as vision and language understanding, where the existence of objects must be inferred from raw data. Dropping the finite-domain assumption has been known to improve the expressiveness of a first-order language for open-universe purposes, but these languages, so far, have eluded WMC approaches. In this paper, we revisit relational probabilistic models over an infinite domain, and establish a number of results that permit effective algorithms. We demonstrate this language on a number of examples, including a parameterized version of Pearl’s Burglary-Earthquake-Alarm Bayesian network.

PDF Details

IJCAI Conference 2017 Conference Paper

Reasoning about Probabilities in Unbounded First-Order Dynamical Domains

  • Vaishak Belle
  • Gerhard Lakemeyer

When it comes to robotic agents operating in an uncertain world, a major concern in knowledge representation is to better relate high-level logical accounts of belief and action to the low-level probabilistic sensorimotor data. Perhaps the most general formalism for dealing with degrees of belief and, in particular, how such beliefs should evolve in the presence of noisy sensing and acting is the account by Bacchus, Halpern, and Levesque. In this paper, we reconsider that model of belief, and propose a new logical variant that has much of the expressive power of the original, but goes beyond it in novel ways. In particular, by moving to a semantical account of a modal variant of the situation calculus based on possible worlds with unbounded domains and probabilistic distributions over them, we are able to capture the beliefs of a fully introspective knowledge base with uncertainty by way of an only-believing operator. The paper introduces the new logic and discusses key properties as well as examples that demonstrate how the beliefs of a knowledge base change as a result of noisy actions.

PDF Details

IJCAI Conference 2017 Conference Paper

Solving Probability Problems in Natural Language

  • Anton Dries
  • Angelika Kimmig
  • Jesse Davis
  • Vaishak Belle
  • Luc De Raedt

The ability to solve probability word problems such as those found in introductory discrete mathematics textbooks, is an important cognitive and intellectual skill. In this paper, we develop a two-step end-to-end fully automated approach for solving such questions that is able to automatically provide answers to exercises about probability formulated in natural language. In the first step, a question formulated in natural language is analysed and transformed into a high-level model specified in a declarative language. In the second step, a solution to the high-level model is computed using a probabilistic programming system. On a dataset of 2160 probability problems, our solver is able to correctly answer 97. 5% of the questions given a correct model. On the end-to-end evaluation, we are able to answer 12. 5% of the questions (or 31. 1% if we exclude examples not supported by design).

PDF Details

AAAI Conference 2017 Conference Paper

The Symbolic Interior Point Method

  • Martin Mladenov
  • Vaishak Belle
  • Kristian Kersting

Numerical optimization is arguably the most prominent computational framework in machine learning and AI. It can be seen as an assembly language for hard combinatorial problems ranging from classification and regression in learning, to computing optimal policies and equilibria in decision theory, to entropy minimization in information sciences. Unfortunately, specifying such problems in complex domains involving relations, objects and other logical dependencies is cumbersome at best, requiring considerable expert knowledge, and solvers require models to be painstakingly reduced to standard forms. To overcome this, we introduce a rich modeling framework for optimization problems that allows convenient codification of symbolic structure. Rather than reducing this symbolic structure to a sparse or dense matrix, we represent and exploit it directly using algebraic decision diagrams (ADDs). Combining efficient ADD-based matrix-vector algebra with a matrix-free interior-point method, we develop an engine that can fully leverage the structure of symbolic representations to solve convex linear and quadratic optimization problems. We demonstrate the flexibility of the resulting symbolic-numeric optimizer on decision making and compressed sensing tasks with millions of non-zero entries.

PDF Details

UAI Conference 2017 Conference Paper

Weighted Model Counting With Function Symbols

  • Vaishak Belle

Probabilistic relational languages lift the syntax of relational logic for the specification of large-scale probabilistic graphical models, often admitting concise descriptions for interacting random variables over classes, hierarchies and constraints. The emergence of weighted model counting as an effective and general approach to probabilistic inference has further allowed practitioners to reason about heterogeneous representations, such as Markov logic networks and ProbLog programs, by encoding them as a logical theory. However, much of this work has been limited to an essentially propositional setting: the logical model is understood in terms of ground formulas over a fixed and finite domain; no infinite domains, and certainly no function symbols (other than constants). On the one hand, this is not surprising, because such features are very problematic from a decidability viewpoint, but on the other, they turn out to be very attractive from the point of view of machine learning applications when there is uncertainty about the existence and identity of objects. In this paper, we reconsider the problem of probabilistic reasoning in a logical language with function symbols, and establish some key results that permit effective algorithms.

Details

AAAI Conference 2016 Conference Paper

A First-Order Logic of Probability and Only Knowing in Unbounded Domains

  • Vaishak Belle
  • Gerhard Lakemeyer
  • Hector Levesque

Only knowing captures the intuitive notion that the beliefs of an agent are precisely those that follow from its knowledge base. It has previously been shown to be useful in characterizing knowledge-based reasoners, especially in a quanti- fied setting. While this allows us to reason about incomplete knowledge in the sense of not knowing whether a formula is true or not, there are many applications where one would like to reason about the degree of belief in a formula. In this work, we propose a new general first-order account of probability and only knowing that admits knowledge bases with incomplete and probabilistic specifications. Beliefs and non-beliefs are then shown to emerge as a direct logical consequence of the sentences of the knowledge base at a corresponding level of specificity.

PDF Details

AAAI Conference 2016 Conference Paper

Component Caching in Hybrid Domains with Piecewise Polynomial Densities

  • Vaishak Belle
  • Guy Van den Broeck
  • Andrea Passerini

Counting the models of a propositional formula is an important problem: for example, it serves as the backbone of probabilistic inference by weighted model counting. A key algorithmic insight is component caching (CC), in which disjoint components of a formula, generated dynamically during a DPLL search, are cached so that they only have to be solved once. In the recent years, driven by SMT technology and probabilistic inference in hybrid domains, there is an increasing interest in counting the models of linear arithmetic sentences. To date, however, solvers for these are block-clause implementations, which are nonviable on large problem instances. In this paper, as a first step in extending CC to hybrid domains, we show how propositional CC systems can be leveraged when limited to piecewise polynomial densities. Our experiments demonstrate a large gap in performance when compared to existing approaches based on a variety of block-clause strategies.

PDF Details

KR Conference 2016 Conference Paper

Foundations for Generalized Planning in Unbounded Stochastic Domains

  • Vaishak Belle
  • Hector Levesque

up Generalized plans, such as plans with loops, are widely used in AI. Among other things, they are straightforward to execute, they allow action repetition, and they solve multiple problem instances. 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. Proposals in the literature, such as strong planning, are universally adopted by the community, but were initially formulated for finite state systems. There is yet to emerge a study on the sensitivity of such correctness notions to the structural assumptions of the underlying plan framework. In this paper, we are interested in the applicability and correctness of generalized plans in domains that are possibly unbounded, and/or stochastic, and/or continuous. To that end, we introduce a generic controller framework to capture different types of planning domains. Using this framework, we then study a number of termination and goal satisfaction criteria from first principles, relate them to existing proposals, and show plans that meet these criteria in the different types of domains. 1 down chop stop Figure 1: controller for the tree chop problem comes. The attractiveness, then, of iterative/loopy plan structures like the one in Figure 1 is threefold: (a) their memoryless nature is ideal for systems with limited resources (e. g. mobile robots (Matarić 2007)), (b) they allow action repetition, as needed in the presence of nondeterminism, and (c) they behave like conditional plans for a large (possibly infinite) number of problem instances (e. g. tree thickness). While early work in this area identified major computational challenges (Manna and Waldinger 1980; Biundo 1994; Stephan and Biundo 1996), significant progress has been made on synthesizing loopy plans in recent years (Cimatti et al. 2003; Levesque 2005; Bonet, Palacios, and Geffner 2009; Srivastava 2010; Hu and De Giacomo 2013). Unfortunately, the correctness of such generalized plans is non-trivial to define: that is, what precisely are they generalizing and in which sense are they reasonable for a planning problem? In the absence of a precise specification, it is difficult to identify what we should be looking for. An early proposal due to Levesque (1996) argued that such a plan should be tested for termination and correctness for all possible initial states of a planning problem. Although formulated in the expressive language of the situation calculus (Reiter 2001), nondeterministic outcomes for actions was not considered. In that vein, Cimatti et al. (2003) later argued that there are conceptual difficulties in understanding the correctness of plans when actions have nondeterministic outcomes. They defined the notions of weak, strong and strong cyclic solutions formulated in terms of action histories that reach the goal state. An informal probabilistic interpretation for these notions was also suggested: weak plans, for example, reach the goal with a non-zero probability. Nonetheless, although nondeterminism is addressed in their work, Cimatti et al. assume a finite state system. Despite the almost universal adoption of these notions

IJCAI Conference 2016 Conference Paper

Hashing-Based Approximate Probabilistic Inference in Hybrid Domains: An Abridged Report

  • Vaishak Belle
  • Guy Van den Broeck
  • Andrea Passerini

In recent years, there has been considerable progress on fast randomized algorithms that approximate probabilistic inference with tight tolerance and confidence guarantees. The idea here is to formulate inference as a counting task over an annotated propositional theory, called weighted model counting (WMC), which can be partitioned into smaller tasks using universal hashing. An inherent limitation of this approach, however, is that it only admits the inference of discrete probability distributions. In this work, we consider the problem of approximating inference tasks for a probability distribution defined over discrete and continuous random variables. Building on a notion called weighted model integration, which is a strict generalization of WMC and is based on annotating Boolean and arithmetic constraints, we show how probabilistic inference in hybrid domains can be put within reach of hashing-based WMC solvers. Empirical evaluations demonstrate the applicability and promise of the proposal.

PDF Details

IJCAI Conference 2015 Conference Paper

ALLEGRO: Belief-Based Programming in Stochastic Dynamical Domains

  • Vaishak Belle
  • Hector Levesque

High-level programming languages are an influential control paradigm for building agents that are purposeful in an incompletely known world. GOLOG, for example, allows us to write programs, with loops, whose constructs refer to an explicit world model axiomatized in the expressive language of the situation calculus. Over the years, GOLOG has been extended to deal with many other features, the claim being that these would be useful in robotic applications. Unfortunately, when robots are actually deployed, effectors and sensors are noisy, typically characterized over continuous probability distributions, none of which is supported in GOLOG, its dialects or its cousins. This paper presents ALLEGRO, a belief-based programming language for stochastic domains, that refashions GOLOG to allow for discrete and continuous initial uncertainty and noise. It is fully implemented and experiments demonstrate that ALLEGRO could be the basis for bridging high-level programming and probabilistic robotics technologies in a general way.

PDF Details

UAI Conference 2015 Conference Paper

Hashing-Based Approximate Probabilistic Inference in Hybrid Domains

  • Vaishak Belle
  • Guy Van den Broeck
  • Andrea Passerini

In recent years, there has been considerable progress on fast randomized algorithms that approximate probabilistic inference with tight tolerance and confidence guarantees. The idea here is to formulate inference as a counting task over an annotated propositional theory, called weighted model counting (WMC), which can be partitioned into smaller tasks using universal hashing. An inherent limitation of this approach, however, is that it only admits the inference of discrete probability distributions. In this work, we consider the problem of approximating inference tasks for a probability distribution defined over discrete and continuous random variables. Building on a notion called weighted model integration, which is a strict generalization of WMC and is based on annotating Boolean and arithmetic constraints, we show how probabilistic inference in hybrid domains can be put within reach of hashing-based WMC solvers. Empirical evaluations demonstrate the applicability and promise of the proposal.

Details

IJCAI Conference 2015 Conference Paper

Multi-Agent Only Knowing on Planet Kripke

  • Guillaume Aucher
  • Vaishak Belle

The idea of only knowing is a natural and intuitive notion to precisely capture the beliefs of a knowledge base. However, an extension to the many agent case, as would be needed in many applications, has been shown to be far from straightforward. For example, previous Kripke frame-based accounts appeal to proof-theoretic constructions like canonical models, while more recent works in the area abandoned Kripke semantics entirely. We propose a new account based on Moss’ characteristic formulas, formulated for the usual Kripke semantics. This is shown to come with other benefits: the logic admits a group version of only knowing, and an operator for assessing the epistemic entrenchment of what an agent or a group only knows is definable. Finally, the multi-agent only knowing operator is shown to be expressible with the cover modality of classical modal logic, which then allows us to obtain a completeness result for a fragment of the logic.

PDF Details

IJCAI Conference 2015 Conference Paper

Only Knowing Meets Common Knowledge

  • Vaishak Belle
  • Gerhard Lakemeyer

Only knowing captures the intuitive notion that the beliefs of an agent are precisely those that follow from its knowledge base. While only knowing has a simple possible-world semantics in a single agent setting, the many agent case has turned out to be much more challenging. In a recent paper, we proposed an account which arguably extends only knowing to multiple agents in a natural way. However, the approach was limited in that the semantics cannot deal with infinitary notions such as common knowledge. In this work, we lift that serious limitation to obtain a first-order language with only knowing and common knowledge, allowing us to study the interaction between these notions for the very first time. By adding a simple form of public announcement, we then demonstrate how the muddy children puzzle can be cast in terms of logical implications given what is only known initially.

PDF Details

AAAI Conference 2015 Conference Paper

Planning Over Multi-Agent Epistemic States: A Classical Planning Approach

  • Christian Muise
  • Vaishak Belle
  • Paolo Felli
  • Sheila McIlraith
  • Tim Miller
  • Adrian Pearce
  • Liz Sonenberg

Many AI applications involve the interaction of multiple autonomous agents, requiring those agents to reason about their own beliefs, as well as those of other agents. However, planning involving nested beliefs is known to be computationally challenging. In this work, we address the task of synthesizing plans that necessitate reasoning about the beliefs of other agents. We plan from the perspective of a single agent with the potential for goals and actions that involve nested beliefs, non-homogeneous agents, co-present observations, and the ability for one agent to reason as if it were another. We formally characterize our notion of planning with nested belief, and subsequently demonstrate how to automatically convert such problems into problems that appeal to classical planning technology. Our approach represents an important first step towards applying the well-established field of automated planning to the challenging task of planning involving nested beliefs of multiple agents.

PDF Details

IJCAI Conference 2015 Conference Paper

Probabilistic Inference in Hybrid Domains by Weighted Model Integration

  • Vaishak Belle
  • Andrea Passerini
  • Guy Van den Broeck

Weighted model counting (WMC) on a propositional knowledge base is an effective and general approach to probabilistic inference in a variety of formalisms, including Bayesian and Markov Networks. However, an inherent limitation of WMC is that it only admits the inference of discrete probability distributions. In this paper, we introduce a strict generalization of WMC called weighted model integration that is based on annotating Boolean and arithmetic constraints, and combinations thereof. This methodology is shown to capture discrete, continuous and hybrid Markov networks. We then consider the task of parameter learning for a fragment of the language. An empirical evaluation demonstrates the applicability and promise of the proposal.

PDF Details

EWRL Workshop 2015 Workshop Paper

Sample-based abstraction for hybrid relational MDPs

  • Davide Nitti
  • Vaishak Belle
  • Tinne De Laet
  • Luc De Raedt

We study planning in relational Markov Decision Processes involving discrete and continuous states and actions. This combination of hybrid relational domains has so far not received a lot of attention. While several symbolic approaches have been proposed for hybrid and relational domains separately, they generally do not provide an integrated approach and they often make restrictive assumptions to make exact inference possible. Removing those restrictions requires approximations such as Monte-Carlo methods. We propose HyBrel: a sample-based planner for hybrid relational domains that combines model-based approaches with state abstraction. HyBrel samples episodes and uses the previous episodes as well as the model to approximate the Q-function. Abstraction is performed for each sampled episode, this removes typical restrictions of symbolic approaches. In our empirical evaluations, HyBrel is shown to have a wide applicability, confirming the advantage of sampled-based abstraction.

Details

AIJ Journal 2015 Journal Article

Semantical considerations on multiagent only knowing

  • Vaishak Belle
  • Gerhard Lakemeyer

Levesque introduced the notion of “only knowing” to precisely capture the beliefs of a knowledge base. He also showed how only knowing can be used to formalize nonmonotonic behavior within a monotonic logic. Levesque's logic only deals with a single agent, and therefore, a number of attempts have been made to generalize only knowing to the many agent case. However, all these attempts have some undesirable features. Most significantly, these attempts are propositional and it is not clear how they are to be extended to the first-order case. In this work, we propose a new semantical account of multiagent only knowing which, for the first time, has a natural possible-world semantics for a quantified language with equality. Among other things, properties about Levesque's logic generalize faithfully to the many agent case with this account. For the propositional fragment, we also provide a sound and complete axiomatization. Finally, we obtain a multiagent first-order version of the nonmonotonicity exhibited by the logic of only knowing.

Details DOI

AAAI Conference 2014 Conference Paper

Computing Contingent Plans via Fully Observable Non-Deterministic Planning

  • Christian Muise
  • Vaishak Belle
  • Sheila McIlraith

Planning with sensing actions under partial observability is a computationally challenging problem that is fundamental to the realization of AI tasks in areas as diverse as robotics, game playing, and diagnostic problem solving. Recent work on generating plans for partially observable domains has advocated for online planning, claiming that offline plans are often too large to generate. Here we push the envelope on this challenging problem, proposing a technique for generating conditional (aka contingent) plans offline. The key to our planner’s success is the reliance on state-of-the-art techniques for fully observable non-deterministic (FOND) planning. In particular, we use an existing compilation for converting a planning problem under partial observability and sensing to a FOND planning problem. With a modified FOND planner in hand, we are able to scale beyond previous techniques for generating conditional plans with solutions that are orders of magnitude smaller than previously possible in some domains.

PDF Details

KR Conference 2014 Conference Paper

How To Progress Beliefs in Continuous Domains

  • Vaishak Belle
  • Hector Levesque

When Lin and Reiter introduced the progression of basic action theories in the situation calculus, they were essentially motivated by long-lived robotic agents functioning over thousands of actions. However, their account does not deal with probabilistic uncertainty about the initial situation nor with effector or sensor noise, as often needed in robotic applications. In this paper, we obtain results on how to progress continuous degrees of belief against continuous effector and sensor noise in a semantically correct fashion. Most significantly, and perhaps surprisingly, we identify conditions under which our account is not only as efficient as the filtering mechanisms commonly used in robotics, but considerably more general. 1. We introduce a property of basic action theories called invertibility, closely related to invertible functions in real analysis (Trench 2003). We identify syntactic restrictions on basic action theories that guarantee invertibility. 2. For our central result, we show a first-order progression of continuous degrees of belief against continuous noise in effectors and sensors for action theories that are invertible. 3. Finally, we prove that this account of progression is efficient. Perhaps surprisingly, under the additional assumption of context-completeness (Liu and Levesque 2005), it is as efficient as commonly used filtering mechanisms in the robotics literature, while considerably more general.

ICAPS Conference 2014 Conference Paper

Non-Deterministic Planning With Conditional Effects

  • Christian J. Muise
  • Sheila A. McIlraith
  • Vaishak Belle

Recent advances in fully observable non-deterministic (FOND) planning have enabled new techniques for various applications, such as behaviour composition, among others. One key limitation of modern FOND planners is their lack of native support for conditional effects. In this paper we describe an extension to PRP, the current state of the art in FOND planning, that supports the generation of policies for domains with conditional effects and non-determinism. We present core modifications to the PRP planner for this enhanced functionality without sacrificing soundness and completeness. Additionally, we demonstrate the planner's capabilities on a variety of benchmarks that include actions with both conditional effects and non-deterministic outcomes. The resulting planner opens the door to models of greater expressivity, and does so without affecting PRP's efficiency.

Details

KR Conference 2014 Short Paper

On the Progression of Knowledge in Multiagent Systems

  • Vaishak Belle
  • Gerhard Lakemeyer

#2: Empty #1: Gold In a seminal paper, Lin and Reiter introduced the progression of basic action theories in the situation calculus. In this paper, we study the progression of knowledge in multiagent settings, where after actions, an agent updates her beliefs but also updates what she believes other agents know given what has occurred. By appealing to the notion of only knowing, we are able to avoid limitations of earlier work on multiagent progression, and obtain a new general account: we show that after an action, knowledge bases are updated in a Lin and Reiter fashion at every nesting of modalities. Consequently, recent results on the first-order definability of progression carry over to a multiagent setting without too much effort. a b Figure 1: Agents a and b look for a room with gold. given that these actions have occurred. 1 Imagine, for example, a simple domain, involving agents a and b looking for gold (Figure 1). When a observes b moving to Room 2 and looking through its window, her beliefs would be as follows: • she still does not know where the gold is; • a knows that b knows whether Room 2 has the gold, but cannot say what b now knows. In general, then, progression should say precisely how a’s knowledge and a’s beliefs about b’s knowledge would be updated after any sequence of physical and sensing actions. 2 The progression of knowledge in the single agent case is considered in (Liu and Wen 2011), but under syntactic restrictions to the initial theory, such as limitations on quantifying-in, and that knowledge does not appear negatively. The progression of knowledge is also considered in (Lakemeyer and Levesque 2009). The results here are general. By appealing to Levesque’s (1990) logic of only knowing, they obtain a simple specification: given an agent who only knows an action theory, the result of doing an action is that the agent only knows the LR progression of this theory. The progression of knowledge in the multiagent case is also considered in (Liu and Wen 2011). In addition to the above limitations, formulas such as Ki p, where p is objective, can be progressed, but not Ki Kj Ki p. That is, among other things, they cannot deal with an agent’s beliefs about what others believe about her. In this work, we substantially improve and extend these results. We provide a new general account of the progression of knowledge in multiagent systems that is essentially equivalent to the results in (Lakemeyer and Levesque 2009) when only a single agent is concerned. As a simple consequence of this work, earlier advances on tractable progression apply easily to our results.

AAAI Conference 2014 Conference Paper

PREGO: An Action Language for Belief-Based Cognitive Robotics in Continuous Domains

  • Vaishak Belle
  • Hector Levesque

The area of cognitive robotics is often subject to the criticism that the proposals investigated in the literature are too far removed from the kind of continuous uncertainty and noise seen in actual real-world robotics. This paper proposes a new language and an implemented system, called prego, based on the situation calculus, that is able to reason effectively about degrees of belief against noisy sensors and effectors in continuous domains. It embodies the representational richness of conventional logic-based action languages, such as contextsensitive successor state axioms, but is still shown to be efficient using a number of empirical evaluations. We believe that prego is a powerful framework for exploring real-time reactivity and an interesting bridge between logic and probability for cognitive robotics applications.

PDF Details

IJCAI Conference 2013 Conference Paper

Reasoning about Continuous Uncertainty in the Situation Calculus

  • Vaishak Belle
  • Hector J. Levesque

Among the many approaches for reasoning about degrees of belief in the presence of noisy sensing and acting, the logical account proposed by Bacchus, Halpern, and Levesque is perhaps the most expressive. While their formalism is quite general, it is restricted to fluents whose values are drawn from discrete countable domains, as opposed to the continuous domains seen in many robotic applications. In this paper, we show how this limitation in their approach can be lifted. By dealing seamlessly with both discrete distributions and continuous densities within a rich theory of action, we provide a very general logical specification of how belief should change after acting and sensing in complex noisy domains.

PDF Details DOI

UAI Conference 2013 Conference Paper

Reasoning about Probabilities in Dynamic Systems using Goal Regression

  • Vaishak Belle
  • Hector J. Levesque

Reasoning about degrees of belief in uncertain dynamic worlds is fundamental to many applications, such as robotics and planning, where actions modify state properties and sensors provide measurements, both of which are prone to noise. With the exception of limited cases such as Gaussian processes over linear phenomena, belief state evolution can be complex and hard to reason with in a general way. This paper proposes a framework with new results that allows the reduction of subjective probabilities after sensing and acting, both in discrete and continuous domains, to questions about the initial state only. We build on an expressive probabilistic first-order logical account by Bacchus, Halpern and Levesque, resulting in a methodology that, in principle, can be coupled with a variety of existing inference solutions.

Details

AAAI Conference 2011 Conference Paper

A Semantical Account of Progression in the Presence of Uncertainty

  • Vaishak Belle
  • Gerhard Lakemeyer

Building on a general theory of action by Reiter and his colleagues, Bacchus et al. give an account for formalizing degrees of belief and noisy actions in the situation calculus. Unfortunately, there is no clear solution to the projection problem for the formalism. And, while the model has epistemic features, it is not obvious what the agent’s knowledge base should look like. Also, reasoning about uncertainty essentially resorts to second-order logic. In recent work, Gabaldon and Lakemeyer remedy these shortcomings somewhat, but here too the utility seems to be restricted to queries (with action operators) about the initial theory. In this paper, we propose a fresh amalgamation of a modal fragment of the situation calculus and uncertainty, where the idea will be to update the initial knowledge base, containing both ordinary and (certain kinds of) probabilistic beliefs, when noisy actions are performed. We show that the new semantics has the right properties, and study a special case where updating probabilistic beliefs is computable. Our ideas are closely related to the Lin and Reiter notion of progression.

PDF Details

IJCAI Conference 2011 Conference Paper

On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols

  • Vaishak Belle
  • Gerhard Lakemeyer

In a seminal paper, Lin and Reiter introduced the notion of progression of basic action theories. Unfortunately, progression is second-order in general. Recently, Liu and Lakemeyer improve on earlier results and show that for the local-effect and normal actions case, progression is computable but may lead to an exponential blow-up. Nevertheless, they show that for certain kinds of expressive first-order knowledge bases with disjunctive information, called proper+, it is efficient. However, answering queries about the resulting state is still undecidable. In this paper, we continue this line of research and extend proper+ to include functions. We prove that their progression wrt local-effect, normal actions, and range-restricted theories, is first-order definable and efficiently computable. We then provide a new logically sound and complete decision procedure for certain kinds of queries.

PDF Details DOI

KR Conference 2010 Conference Paper

) Multi-Agent Only-Knowing Revisited

  • Vaishak Belle
  • Gerhard Lakemeyer

Levesque introduced the notion of only-knowing to precisely capture the beliefs of a knowledge base. He also showed how only-knowing can be used to formalize non-monotonic behavior within a monotonic logic. Despite its appeal, all attempts to extend only-knowing to the many agent case have undesirable properties. A belief model by Halpern and Lakemeyer, for instance, appeals to proof-theoretic constructs in the semantics and needs to axiomatize validity as part of the logic. It is also not clear how to generalize their ideas to a first-order case. In this paper, we propose a new account of multi-agent only-knowing which, for the first time, has a natural possible-world semantics for a quantified language with equality. We then provide, for the propositional fragment, a sound and complete axiomatization that faithfully lifts Levesque’s proof theory to the many agent case. We also discuss comparisons to the earlier approach by Halpern and Lakemeyer.

AAAI Conference 2010 Conference Paper

Reasoning about Imperfect Information Games in the Epistemic Situation Calculus

  • Vaishak Belle
  • Gerhard Lakemeyer

Approaches to reasoning about knowledge in imperfect information games typically involve an exhaustive description of the game, the dynamics characterized by a tree and the incompleteness in knowledge by information sets. Such specifications depend on a modeler’s intuition, are tedious to draft and vague on where the knowledge comes from. Also, formalisms proposed so far are essentially propositional, which, at the very least, makes them cumbersome to use in realistic scenarios. In this paper, we propose to model imperfect information games in a new multi-agent epistemic variant of the situation calculus. By using the concept of only-knowing, the beliefs and non-beliefs of players after any sequence of actions, sensing or otherwise, can be characterized as entailments in this logic. We show how de re vs. de dicto belief distinctions come about in the framework. We also obtain a regression theorem for multi-agent beliefs, which reduces reasoning about beliefs after actions to reasoning about beliefs in the initial situation.

PDF Details
v2026.09.13