Hector Levesque

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.

KR Conference 2016 Conference Paper

Decidable Reasoning in a Logic of Limited Belief with Function Symbols

• Gerhard Lakemeyer
• Hector Levesque

A principled way to study limited forms of reasoning for expressive knowledge bases is to specify the reasoning problem within a suitable logic of limited belief. Ideally such a logic comes equipped with a perspicuous semantics, which provides insights into the nature of the belief model and facilitates the study of the reasoning problem. While a number of such logics were proposed in the past, none of them is able to deal with function symbols except perhaps for the special case of logical constants. In this paper we propose a logic of limited belief with arbitrary function symbols. Among other things, we demonstrate that this form of limited belief has desirable properties such as eventual completeness for a large class of formulas and that it serves as a specification of a form of decidable reasoning for very expressive knowledge bases. s = {(p ∨ q), (¬p ∨ q)}. Here q is not believed at level 0, but it is believed at level 1 because we can split on p, which amounts to checking that q is believed at level 0 in the setups s ∪ {p} and s ∪ {¬p}, which is the case by unit propagation and subsumption. With this model of belief in hand, reasoning in the context of a knowledge base can then be phrased in terms of belief implications, that is, as the question which beliefs at any level k follow logically from believing the sentences in the knowledge base at level 0. LLL showed that this problem is decidable and often tractable for a large class of first-order disjunctive knowledge bases called proper+. In our new logic we keep the ideas of setups as semantic primitive and levels of belief corresponding to how much case analysis is allowed. Different from the earlier work we do not deal with predicates except for =, but consider arbitrary functions instead. Moreover, we introduce a new form of case analysis. To get an idea of what we are after, consider the following set of sentences KB, which can be thought of both as the explicit beliefs of an agent and a setup:

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 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.

KR Conference 2014 Conference Paper

Forgetting in Action

• David Rajaratnam
• Hector Levesque
• Maurice Pagnucco
• Michael Thielscher

A further motivation for the concept of forgetting is evident in the formal analysis of security and cryptographic protocols. Cryptographic protocols have previously been analysed using the Situation Calculus equipped with a notion of the knowledge of agents (Delgrande, Hunter, and Grote 2010). However, such an encoding cannot always represent the class of nonmonotonic cryptographic protocols (Rubin and Honeyman 1994), where a notion of forgetting can be important. For example, in the analysis of credit card protocols it is a critical requirement to model vendors that forget (i. e., not retain) customer credit card details. In order to illustrate our approach to forgetting we consider the following running example. A robot needs to enter a room that is protected by a closed door with a keypad lock. When the robot senses that the door is closed, it needs to download the key combination from an external data source (e. g., the cloud or a database). It can then use this key combination to open the door and enter the room. Furthermore, since the door will now be open, the robot no longer needs the key combination, so is free to forget this information. The rest of the paper proceeds as follows. First we introduce the Situation Calculus (McCarthy 1963; Reiter 2001) and its epistemic extension (Lesperance et al. 1995) that allows for knowledge acquisition without forgetting. We then present our approach that handles both knowledge acquisition and forgetting and perform an extensive analysis of its properties and the conditions under which both knowledge acquisition and forgetting can occur. Having established our approach to forgetting, we then place it within the broader context of two of the main models that have been developed within the literature: AGM belief revision (Alchourrón, Gärdenfors, and Makinson 1985) and logical forgetting (Lin and Reiter 1994). In particular, we show that our approach is well-behaved with respect to the AGM belief contraction postulates, but is distinct from that of logical forgetting since knowledge forgetting can provide for more fine-grained control over what is forgotten. Finally, we provide some concluding remarks and discuss directions for future research. In this paper we develop a general framework that allows for both knowledge acquisition and forgetting in the Situation Calculus. Based on the Scherl and Levesque (Scherl and Levesque 1993) possible worlds approach to knowledge in the Situation Calculus, we allow for both sensing as well as explicit forgetting actions. This model of forgetting is then compared to existing frameworks. In particular we show that forgetting is well-behaved with respect to the contraction operator of the well-known AGM theory of belief revision (Alchourrón, Gärdenfors, and Makinson 1985) but that knowledge forgetting is distinct from the more commonly known notion of logical forgetting (Lin and Reiter 1994).

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.

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.

KR Conference 2012 Conference Paper

Belief revision with sensing and fallible actions

• James Delgrande
• Hector Levesque

use of the notion of plausibility, taken from ranking functions (or ordinal conditional functions) [Spohn, 1988]. This work generalises previous work in that it integrates possibly-fallible actions, belief revision (via informing actions), and sensing. The overall approach is one that has received extensive treatment in the belief revision community: we associate with an agent a belief state that consists not just of a set of contingent beliefs, but also a plausibility ordering over other potential beliefs, expressed in terms of an ordering over situations. Consequently, if an agent discovers that its beliefs are incorrect, then the plausibility ordering provides a principled means for modifying its beliefs. Our approach is based on the situation calculus, which provides a full account of reasoning about action. Actions are described in terms of their preconditions and their effects, exploiting Reiter’s solution to the frame problem [Reiter, 2001]. We augment this by including the case where an agent may intend to execute one action but inadvertently executes another. (For example the agent may accidentally press a wrong button.) Consequently we allow that the agent’s beliefs may evolve according to one sequence of actions (the actions it believes that it executed) while the world evolves in a different direction (according to the actions that the agent actually executes). This also has an epistemic component, in that the agent may be aware of such alternatives, and so in executing an action will keep track of such (according to the agent, counterfactual) possibilities. If this was all there were to the story, then the agent’s beliefs would simply diverge more and more from the real situation. However, the agent may carry out sensing actions; such actions are, by definition, with respect to the actual situation, and so via sensing the agent may correct incorrect beliefs. As well, we also allow that an agent may be informed of some fact. The idea here is that if the agent is informed that φ, it will amend its beliefs so that it accepts φ. This operation is exactly that of belief revision [Gärdenfors, 1988; Peppas, 2008]. A key point is that an agent may be informed of some formula, φ, and later of some other formula ψ that conflicts with φ; in this case the agent would nonetheless maintain a consistent set of beliefs (except in the limiting case where ψ is inconsistent). This approach extends previous work in several respects. It provides a complete integration of an account of reasoning about action with belief revision. In so doing, it allows arbi- An agent will generally have incomplete and possibly inaccurate knowledge about its environment. In addition, such an agent may receive erroneous information, perhaps in being misinformed about the truth of some formula. In this paper we present a general approach to reasoning about action and belief change in such a setting. An agent may carry out actions, but in some cases may inadvertently execute the wrong one (for example, pushing an unintended button). As well, an agent may sense whether a condition holds, and may revise its beliefs after being told that a formula is true. Our approach is based on an epistemic extension to basic action theories expressed in the situation calculus, augmented by a plausibility relation over situations. This plausibility relation can be thought of as characterising the agent’s overall belief state; as such it keeps track of not just the formulas that the agent believes to hold, but also the plausibility of formulas that it does not believe to hold. The agent’s belief state is updated by suitably modifying the plausibility relation following the execution of an action. We show that our account generalises previous approaches, and fully handles belief revision, sensing, and erroneous actions.

KR Conference 2012 Conference Paper

The Winograd Schema Challenge

• Hector Levesque
• Ernest Davis
• Leora Morgenstern

ing the presence of thinking (or understanding, or intelligence, or whatever appropriate mental attribute), we assume that typed English text, despite its limitations, will be a rich enough medium. In this paper, we present an alternative to the Turing Test that has some conceptual and practical advantages. A Winograd schema is a pair of sentences that differ only in one or two words and that contain a referential ambiguity that is resolved in opposite directions in the two sentences. We have compiled a collection of Winograd schemas, designed so that the correct answer is obvious to the human reader, but cannot easily be found using selectional restrictions or statistical techniques over text corpora. A contestant in the Winograd Schema Challenge is presented with a collection of one sentence from each pair, and required to achieve human-level accuracy in choosing the correct disambiguation. 1 2 The trouble with Turing The Turing Test does have some troubling aspects, however. First, note the central role of deception. Consider the case of a future intelligent machine trying to pass the test. It must converse with an interrogator and not just show its stuff, but fool her into thinking she is dealing with a person. This is just a game, of course, so it’s not really lying. But to imitate a person well without being evasive, the machine will need to assume a false identity (to answer “How tall are you? ” or “Tell me about your parents. ”). All other things being equal, we should much prefer a test that did not depend on chicanery of this sort. Or to put it differently, a machine should be able to show us that it is thinking without having to pretend to be somebody or to have some property (like being tall) that it does not have. We might also question whether a conversation in English is the right sort of test. Free-form conversations are no doubt the best way to get to know someone, to find out what they think about something, and therefore that they are thinking about something. But conversations are so adaptable and can be so wide-ranging that they facilitate deception and trickery. Consider, for example, ELIZA (Weizenbaum 1966), where a program (usually included as part of the normal Emacs distribution), using very simple means, was able to fool some people into believing they were conversing with a psychiatrist. The deception works at least in part because we are extremely forgiving in terms of what we will accept as legitimate conversation. A Rogerian psychiatrist may say very little except to encourage a patient to keep on talking, but it may be enough, at least for a while. Consider also the Loebner competition (Shieber 1994), a restricted version of the Turing Test that has attracted considerable publicity. In this case, we have a more balanced conversation taking place than with ELIZA. What is striking about transcripts of these conversations is the fluidity of the responses from the subjects: elaborate wordplay, puns, jokes, quotations, clever asides, emotional outbursts, points of order. Everything, it would seem, except clear and direct

KR Conference 2010 Conference Paper

A Completeness Result for Reasoning about One-Dimensional Planning Problems

• Yuxiao Hu
• Hector Levesque

A plan with rich control structures like branches and loops can usually serve as a general solution that solves multiple planning instances in a domain. However, the correctness of such generalized plans is non-trivial to define and verify, especially when it comes to whether or not a plan works for all of the infinitely many instances of the problem. In this paper, we give a precise definition of a generalized plan representation called an FSA plan, with its semantics defined in the situation calculus. Based on this, we identify a class of infinite planning problems, which we call one-dimensional (1d), and prove a correctness result that 1d problems can be verified by finite means. We show that this theoretical result leads to a practical algorithm that does this verification practically, and a planner based on this verification algorithm efficiently generates provably correct plans for 1d problems.

IJCAI Conference 2007 Conference Paper

• Stavros Vassos
• Hector Levesque

In this paper, we propose a new progression mechanism for a restricted form of incomplete knowledge formulated as a basic action theory in the situation calculus. Specifically, we focus on functional fluents and deal directly with the possible values these fluents may have and how these values are affected by both physical and sensing actions. The method we propose is logically complete and can be calculated efficiently using database techniques under certain reasonable assumptions.

AAMAS Conference 2007 Conference Paper

Towards a Logical Theory of Coordination and Joint Ability

• Hojjat Ghaderi
• Hector Levesque
• Yves Lespérance

The coordination of teams of cooperating but autonomous agents is a core problem in multiagent systems research. A team of agents is jointly able to achieve a goal if despite any incomplete knowledge or even false beliefs that they may have about the world or each other, they still know enough to be able to get to a goal state, should they choose to do so. Unlike in the single-agent case, the mere existence of a working plan is not sufficient since there may be several incompatible working plans and the agents may not be able to choose a share that coordinates with the others'.

KR Conference 2006 Conference Paper

On the Limits of Planning over Belief States under Strict Uncertainty

• Sardina Sebastian
• Hector Levesque
• Giuseppe De Giacomo
• Yves Lesperance

A recent trend in planning with incomplete information is to model the actions of a planning problem as nondeterministic transitions over the belief states of a planner, and to search for a plan that terminates in a desired goal state no matter how these transitions turn out. We show that this view of planning is fundamentally limited. Any plan that is successful by this criteria has an upper bound on the number of actions it can execute. Specifically, the account will not work when iterative plans are needed. We also show that by modifying the definition slightly, we obtain another account of planning that does work properly even for iterative plans. Although the argument is presented in an abstract form, we illustrate the issues using a simple concrete example.

KR Conference 2004 Conference Paper

A Logic of Limited Belief for Reasoning with Disjunctive Informatiion

• Gerhard Lakemeyer
• Hector Levesque
• Yongmei Liu

The goal of producing a general purpose, semantically motivated, and computationally tractable deductive reasoning service remains surprisingly elusive. By and large, approaches that come equipped with a perspicuous model theory either result in reasoners that are too limited from a practical point of view or fall off the computational cliff. In this paper, we propose a new logic of belief called SL which lies between the two extremes. We show that query evaluation based on SL for a certain form of knowledge bases with disjunctive information is tractable in the propositional case and decidable in the first-order case. Also, we present a sound and complete axiomatization for propositional SL.

KR Conference 2004 Conference Paper

Situations, si! Situation terms, no!

• Gerhard Lakemeyer
• Hector Levesque

The situation calculus, as proposed by McCarthy and Hayes, and developed over the last decade by Reiter and co-workers, is reconsidered. A new logical variant is proposed that captures much of the expressive power of the original, but where certain technical results are much more easily proven. This is illustrated using two existing non-trivial results: the regression theorem and the determinacy of knowledge theorem of Reiter. We also obtain a regression theorem for knowledge, and show how to reduce reasoning about knowledge and action to non-epistemic non-dynamic reasoning about the initial situation.