--- title: "Reasoning about Probabilities in Unbounded First-Order Dynamical Domains" authors: - "Vaishak Belle" - "Gerhard Lakemeyer" doi: "10.24963/ijcai.2017/115" url: "https://ijcai.org/proceedings/2017/115" pdf: "https://ijcai.org/proceedings/2017/0115.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "828-836" track: "Main track" keywords: - "Uncertainty in AI: Uncertainty Representations" - "Knowledge Representation, Reasoning, and Logic: Reasoning about Knowlege and Belief" - "Knowledge Representation, Reasoning, and Logic: Action, Change and Causality" - "Uncertainty in AI: Uncertainty in AI" --- # Reasoning about Probabilities in Unbounded First-Order Dynamical Domains Vaishak Belle, Gerhard Lakemeyer *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 828-836. DOI: [10.24963/ijcai.2017/115](https://doi.org/10.24963/ijcai.2017/115) ## Abstract 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. ## Full text - We assume the sensor action is always executable, and the move action is executable provided the argument does not cause the robot the hit the wall: 6 - Similar to BHL, noisy actions are retrofitted in successor state axioms by postulating that the effects of an action are against the actual argument: - Clearly, all instances of move with an intended argument of x are observationally indistinguishable from each other. A sonar action is only observationally indistinguishable to itself, as the agent sees the actual argument corresponding to the reading on the sensor: - We assume the noise model of a sensor to depend on the true value of h, and that for the effector to depend on how much the actual argument diverges from the intended argument: where, So, observing a value z on the sonar means that it is very likely the true value, and at most it is off by a unit. 7 Analogously, for the move action. We lump these axioms together as Σ. Example 20: We begin by assuming a standard discrete uniform distribution on h, say, on the range {2, 3, 4} . In particular, we will consider the entailments of the following theory: The following are entailments of (1): 1. B(h(5) : 0) By means of defining a probability distribution over 3 possible values for h, other values are impossible. 2. [sonar(2)]B(h(4) : 0) ∧ [sonar(2)]B(h(2) : 8/9) Obtaining a reading of 2 on the sensor means that being 4 units away is no longer possible, whereas the agent's confidence in being 2 units away from the wall increases. 3. [sonar(2)][move(1, 1)]B(h(2) : 8/45) Consider that, in case of an exact move, the probability of being 2 units away would have been 0. See Figure 2 for the degrees of belief in other values of h. 6 Free variables are assumed to be implicitly quantified from the outside. 7 It is also possible to handle discrete approximations of Gaussians, for example. Figure 2: distribution on h values in Example 20 | h values | 2 | 3 | 4 | 5 | |-----------------|------|-----|-------|------| | initially | 1/3 | 1/3 | 1/3 | 0 | | after sonar(2) | 8/9 | 1/9 | 0 | 0 | | after move(1,1) | 8/45 | 5/9 | 11/45 | 1/45 | Example 21: We now assume the same dynamic axioms as above (given by Σ), but imagine the agent to only have qualitative uncertainty about h's value. Consider: 8 So, the agent considers infinitely many h values possible. The following are entailed by (2): 1. B(h(1) : 0) ∧¬B(h(4) : 0) Values for h > 1 cannot be ruled out. Here, only know- ing allows us to infer non-beliefs. 2. [sonar(2)]B(h(4) : 0) The nature of the likelihood axioms for the sensor is such that obtaining a reading of 2 eliminates infinitely many possibilities. The following is not entailed by (2): 3. [sonar(2)]∃u, v B(h(2) : u) ∧B(h(3) : v) ∧ u > v A sensor reading of 2 means that the robot is either 2 or 3 units away from the wall, as the prior on being 1 unit away is 0. Despite the reading favoring the case for the robot being two units away from the wall, qualitative uncertainty about h's value means there are distributions where h(2) has a low or even 0 prior probability, and therefore, it does not follow that the degree of belief in - h(2) necessarily trumps that in h(3). ## 5 RelatedWork Reasoning about probabilities is widely studied in the logical literature - see, for example, [Gaifman, 1964; Nilsson, 1986; Halpern, 2003]; we briefly survey the major camps below. At the outset, we remark that a key feature of our work is only knowing, 9 which has not been considered for probabilistic specifications, except for OBL that we build on. The inspiration for our work, and perhaps the one closest in spirit, is the work of BHL on degrees of belief in the situation calculus. It is an axiomatic proposal with a conceptually attractive definition of belief in a first-order setting. The thrust of our work is in providing a semantic basis for that proposal, and as we noted, without constructions like ∼w and ≈oi, metabeliefs do not work right away in the BHL framework. BHL also do not consider only knowing. In less restrictive settings than full first-order OL, Gabaldon and Lakemeyer [2007] consider a logic of only knowing and probability by meta-linguistically enforcing finitely many equivalence classes for possible worlds. Consequently, quantification also ranges over a finite set. In a game theory context, Halpern and Pass [2009] have considered a (propositional) version of only knowing with probability distributions. 8 For expressions such as u > 1, it is implicitly assumed that we are quantifying over the rationals, which can be accomplished by adding sorts to the language. This is left out of the semantics for simplicity. 9 Only knowing is related to notions such as minimal knowledge [Halpern and Moses, 1984] and total knowledge [Pratt-Hartmann, 2000]. See [Levesque and Lakemeyer, 2001] for discussions. Reasoning about knowledge and probability has appeared in a number of works prior to BHL, of course, in computer science [Nilsson, 1986; Fagin and Halpern, 1994], game theory [Monderer and Samet, 1989; Heifetz and Mongin, 2001], among others [Halpern, 2003]. Properties discussed in this paper, such as introspection and additivity, are also well studied [Aumann, 1999]. Notably, the work of Fagin and Halpern [1994] can be seen to be at the heart of BHL (and our work). The Fagin-Halpern scheme is a general one formulated for Kripke frames [Fagin et al., 1995], but it is propositional. We also consider the simple case where a set of global distributions apply to W as seen at every world; in theirs, the probability spaces can differ arbitrarily across the worlds. The Fagin-Halpern scheme shares some similarity with probabilistic logics for programs [Kozen, 1981] and variants thereof [Halpern and Tuttle, 1993; Van Benthem et al., 2009]. There are many previous first-order accounts of probabilities, such as [Bacchus, 1990] and [Halpern, 1990]; see [Ognjanovic and Raˇskovic, 2000] for a comprehensive list. Limited versions of probabilistic logics have also become popular in the machine learning literature [Poole, 2003; Domingos and Webb, 2012; Getoor and Taskar, 2007], with things like a finite domain assumption built-in. In these latter formalisms, the logical syntax is mostly used to succinctly represent large probabilistic graphical models with many interacting random variables over classes and hierarchies, and as such, the knowledge base is assumed to be equivalent to a single joint distribution over these variables. First-order accounts such as [Halpern, 1990] allow logical connectives over beliefs, as a result of which, like in BHL and DS, beliefs may not correspond to any single distribution. However, our emphasis on a first-order theory of actions and only knowing distinguishes us from much of this work. ## 6 Conclusions We proposed a first-order modal logic of subjective probabilities, noisy acting and sensing, and explored its formal properties. The language allows us to express BHL-style basic action theories, albeit in a crisp semantical framework, with introspection and only knowing. Bridging logical representations and probabilistic data is becoming a central problem in cognitive robotics and much of artificial intelligence; so, having a general specification language for analyzing systems and high-level programs is vital. For the future, we think the following directions seem promising. From a reasoning viewpoint, it would be interesting to consider how to implement a possibly restricted (perhaps, even propositional) version of DS as a reasoning service. For starters, this would undoubtedly need an automated way to reason about actions, so that queries after actions can be reduced to purely static ones. Our sense is that earlier results for the BHL scheme [Belle and Levesque, 2013b; 2014] can be reformulated for DS with some effort. From the representational viewpoint, the most immediate extension would be to allow both discrete and continuous probabilities, similar to [Belle and Levesque, 2013a]. This would allow the logic to capture the sorts of realistic sensor models seen in practice [Thrun et al., 2005]. But even when limited to discrete probabilistic variables, there is an important limitation with the current syntax. Our belief operators were inherited from OBL, which take the form B(α, r), where r is a rational. But suppose we are interested in characterizing discrete probabilistic variables taking values from infinite sets. A simple case is a geometric distribution: imagine that the probabilistic variable h from our examples can take values from N, and the probability of taking the value u ∈ N is (1 - θ) u × θ for a given θ ∈ [0, 1]. For example, if θ = .5, then the value 0 is accorded a probability of .5, the value 1 a probability of .25, and so on. Although we could use an infinite theory such as {B(h(0) : .5),B(h(1) : .25), . . .}, it would be nice to be able to represent the distribution as a formula, perhaps in the context of O. At first glance, this would require the second argument of B to possibly taking on variables of the rational sort rather than just rational constants, but how to design such a language and specify a semantics for it is an open question. ## Appendix We briefly review the non-dynamic and non-probabilistic counterparts of DS: the logics OL [Levesque and Lakemeyer, 2001], OBL [Belle et al., 2016], and ES [Lakemeyer and Levesque, 2004]. ## The Logic OL The non-modal fragment of OL consists of standard firstorder logic with = (that is, connectives {∧, ∀, ¬} and a countably infinite set of standard names N, which, as usual, includes the set of rationals as a subsort. (Unlike DS, where we needed to consider k-ary rigid function symbols for building action terms, OL can be limited to nullary rigid terms, making the account simpler.) As before, we let P be the set of ground atoms. Finally, as one would surmise, OL has two epistemic operators: K and O. The semantics of OL, given using possible worlds, is defined over the set of mappings from the ground atoms in P to {0, 1}. By an epistemic state e, we mean any set of worlds. By a model, we mean a pair (e, w). Given α ∈ OL and a model (e, w), the definition of truth is defined inductively. We omit the logical connectives, and discuss the case for atoms and modalities: 10 - e, w |= p iff w[p] = 1; - e, w |=Kα iff for all w ′ ∈ e, e, w ′ |= α; - e, w |= Oα iff for all w ′ , w ′ ∈ e iff e, w ′ |= α. 10 Readers familiar with the generic approach of accessibility relations between worlds in Kripke frames [Hughes and Cresswell, 1972] will realize that our notion of an epistemic state offers a simplified account, essentially corresponding to weak S5. That is, knowing α amounts to α being true in all worlds in e, and only-knowing α amounts to e being precisely those worlds where α holds. A definition for entailment is given as we would for DS. The K modality in OL exhibits the usual properties of introspection, as well as the universal and existential versions of the Barcan formula; for example: - |=Kα ⊃KKα; - |= ∃xKα ⊃K∃xα but ̸ |= K∃xα ⊃ ∃xKα. The new modality here in comparison to classical epistemic logic is O, and in that regard, only knowing implies knowing, but also not believing what does not logically follow from the knowledge base: - |= Oα ⊃Kα - |= Oϕ ⊃Kψ iff |= ϕ ⊃ ψ - |= Op ⊃ ¬Kq for distinct atoms p and q. Clearly, the last property is not true in classical epistemic logic, because knowing p does not preclude knowing p ∧ q. ## The Logic OBL From a syntax point of view, OBL is essentially identical to OL except for including modalities B(α: r) and O(α1 : r1, . . . , αk : rk), with Kα and Oα serving as abbreviations as in DS. Given the set of ground atoms P and the set of worlds W, which are mappings from P to {0, 1}, a distribution d is understood as a function fromW to the set of non-negative reals R≥0 . An epistemic state e is defined as a set of distributions. By a model, we mean a pair (e, w). For the epistemic operators to be well-defined, we define conditions Bnd, Eq and Norm as in DS, but these conditions now take the signature (d,V, r) where V ⊆ W. (That is, we are not considering world and action pairs, since there are no actions in the language.) For example: Bnd(d,V, r) iff there is no k, w1, . . . , wk ∈ V such that With that, the semantic rules can be defined using (once again, omitting the connectives): - e, w |= p iff w[p] = 1; - e, w |= B(α: r) iff for all d ∈ e, Norm(d, {w ′ | e, w ′ |= α} , r); - e, w |= O(α1 : r1, . . . , αk : rk) iff for all d, d ∈ e iff Norm(d, {w ′ | e, w ′ |= α1} , r1), . . . ,Norm(d, {w ′ | e, w ′ |= αk} , rk). Incidentally, ¬Ktrue is satisfiable, which means that while positive introspection holds unconditionally, negative introspection needs to be predicated on believing true: 11 11 Since B(true : 1) is not valid, the authors in [Belle et al., 2016] consider the notion of measurable epistemic states, which are precisely those that satisfy B(true: 1). All of this carries over to DS, but for space reasons we will not pursue the topic here. - |= B(α: r) ⊃KB(α: r) for arbitrary r; - so, |=Kα ⊃KKα is then a special case; - Ktrue |= ¬B(α: r) ⊃K¬B(α: r) for arbitrary r. Moreover, B admits additivity and equivalence properties; for example: - |= B(α ∧ β: r) ∧B(α ∧¬β: r ′ ) ⊃ B(α: r + r ′ ); - if |= α ≡ β, then |= B(α: r) ≡ B(β: r). Finally, regarding O, the properties already discussed in the context of OL also hold in OBL. ## The Logic ES The logic ES semantically reconstructs the situation calculus in a logic of only knowing. To allow for action terms, as we have in DS, one assumes k-ary rigid function terms. The set of atoms P are then obtained by applying all ground terms R to the predicates in the language. Worlds in ES are no longer static entities that understand the (current) state of affairs. That is, a world maps P and Z to {0, 1}, where the set of action sequences Z is defined as we have for DS. By a model, we mean a triple (e, w, z) where z ∈ Z. To account for how knowledge changes after (noise-free) sensing, one defines w ′ ∼z w, which is to be read as saying "w ′ and w agree on the sensing for z", as follows: - if z = ⟨⟩, w ′ ∼z w for every w ′ ; - w ′ ∼z·a w iff w ′ ∼z w, w[poss(a), z] = 1 and w ′ [SF(a), z] = w[SF(a), z]. The truth rules are (omitting connectives, as usual): - e, w, z |= p iff p is an atom and w[p, z] = 1; - e, w, z |=Kα iff for all w ′ ∼z w, if w ′ ∈ e, e, w ′ , z |= α; - e, w, z |= Oα iff for all w ′ ∼z w, w ′ ∈ e iff e, w ′ , z |= α. Properties of knowledge and only-knowing take on the same form as in OL, with the addition that introspection holds for all action sequences; for example: - |= □(Kα ⊃KKα); - |= □(Oα ⊃Kα). Action theories for ES are similar to DS, except that acting and sensing is assumed to be noise-free. Among other things, there are no likelihood and observational indistinguishability axioms, and noise-free sensing is axiomatized by means of a distinguished predicate SF. In the context of moving towards a wall, for example, we might have: which says that SF is true on executing isClose only when the robot is within 5 units of the wall, and is false otherwise. Semantically, then, given worlds w ′ and w, we would have w ′ ∼isClose w only when the robot is within 5 units from the wall in both worlds. ## References 1. [Aumann, 1999] R. J. Aumann. Interactive epistemology II: proba- bility. Int. J. Game Theory, 28(3):301-314, 1999. 2. [Bacchus et al., 1999] F. Bacchus, J. Y. Halpern, and H. J. Levesque. Reasoning about noisy sensors and effectors in the situation calculus. Artificial Intelligence, 111(1-2):171 -208, 1999. 3. [Bacchus, 1990] F. Bacchus. Representing and Reasoning with Probabilistic Knowledge. MIT Press, 1990. 4. [Belle and Levesque, 2013a] V. Belle and H. J. Levesque. Reason- ing about continuous uncertainty in the situation calculus. In Proc. IJCAI, 2013. 5. [Belle and Levesque, 2013b] V. Belle and H. J. Levesque. Reason- ing about probabilities in dynamic systems using goal regression. In Proc. UAI, 2013. 6. [Belle and Levesque, 2014] V. Belle and H. J. Levesque. How to progress beliefs in continuous domains. In Proc. KR, 2014. 7. [Belle and Levesque, 2015] V. Belle and H. J. Levesque. A logical theory of localization. In Studia Logica. 2015. 8. [Belle et al., 2016] V. Belle, G. Lakemeyer, and H. J. Levesque. A first-order logic of probability and only knowing in unbounded domains. In Proc. AAAI, 2016. 9. [Domingos and Webb, 2012] P. Domingos and W. A. Webb. A tractable first-order probabilistic logic. In AAAI, 2012. 10. [Fagin and Halpern, 1994] R. Fagin and J. Y. Halpern. Reasoning about knowledge and probability. J. ACM, 41(2):340-367, 1994. 11. [Fagin et al., 1995] R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning About Knowledge. MIT Press, 1995. 12. [Gabaldon and Lakemeyer, 2007] A. Gabaldon and G. Lakemeyer. ESP: A logic of only-knowing, noisy sensing and acting. In Proc. AAAI, pages 974-979, 2007. 13. [Gaifman, 1964] H. Gaifman. Concerning measures in first order calculi. Israel Journal of Mathematics, 2(1):1-18, 1964. 14. [Getoor and Taskar, 2007] L. Getoor and B. Taskar, editors. An In- troduction to Statistical Relational Learning. MIT Press, 2007. 15. [Halpern and Moses, 1984] J. Y. Halpern and Y. Moses. Towards a theory of knowledge and ignorance: Preliminary report. In Proc. NMR, pages 125-143, 1984. 16. [Halpern and Pass, 2009] J. Y. Halpern and R. Pass. A logical char- acterization of iterated admissibility. In Proc. TARK, pages 146- 155, 2009. 17. [Halpern and Tuttle, 1993] J. Y. Halpern and M. R. Tuttle. Knowl- edge, probability, and adversaries. J. ACM, 40:917-960, 1993. 18. [Halpern, 1990] J.Y. Halpern. An analysis of first-order logics of probability. Artificial Intelligence, 46(3):311-350, 1990. 19. [Halpern, 2003] J. Y. Halpern. Reasoning about Uncertainty. MIT Press, 2003. 20. [Heifetz and Mongin, 2001] A. Heifetz and P. Mongin. Probability logic for type spaces. Games and Economic Behavior, 35(1-2):31 -53, 2001. 21. [Hughes and Cresswell, 1972] G. E. Hughes and M. J. Cresswell. An introduction to modal logic. Methuen London, 1972. 22. [Kozen, 1981] D. Kozen. Semantics of probabilistic programs. Journal of Computer and System Sciences, 22(3):328 -350, 1981. 23. [Lakemeyer and Levesque, 2004] G. Lakemeyer and Hector J. Levesque. Situations, Si! situation terms, No! In Proc. KR, pages 516-526, 2004. 24. [Lakemeyer and Levesque, 2007] G. Lakemeyer and H. J. Levesque. Cognitive robotics. In Handbook of Knowledge Representation, pages 869-886. Elsevier, 2007. 25. [Lakemeyer and Levesque, 2009] G. Lakemeyer and H. J. Levesque. A semantical account of progression in the presence of defaults. In IJCAI, pages 842-847, 2009. 26. [Lakemeyer and Levesque, 2011] G. Lakemeyer and H. J. Levesque. A semantic characterization of a useful frag- ment of the situation calculus with knowledge. Artificial Intelligence, 175:142-164, 2011. 27. [Levesque and Lakemeyer, 2001] H. J. Levesque and G. Lake- meyer. The logic of knowledge bases. The MIT Press, 2001. 28. [Lin and Reiter, 1997] F. Lin and R. Reiter. How to progress a database. Artificial Intelligence, 92(1-2):131-167, 1997. 29. [Monderer and Samet, 1989] D. Monderer and D. Samet. Approx- imating common knowledge with common beliefs. Games and Economic Behavior, 1(2):170-190, June 1989. 30. [Nilsson, 1986] N. J. Nilsson. Probabilistic logic. Artificial intelli- gence, 28(1):71-87, 1986. 31. [Ognjanovic and Raškovic, 2000] Z. Ognjanovic and M. Raškovic. Some first-order probability logics. Theoretical Computer Sci- ence, 247(1-2):191 -212, 2000. 32. [Poole, 2003] D. Poole. First-order probabilistic inference. In Proc. IJCAI, pages 985-991, 2003. 33. [Pratt-Hartmann, 2000] I. Pratt-Hartmann. Total knowledge. In Proc. AAAI, pages 423-428, 2000. 34. [Reiter, 2001] R. Reiter. Knowledge in action: logical foundations for specifying and implementing dynamical systems. MIT Press, 2001. 35. [Russell, 2015] S. J. Russell. Unifying logic and probability. Com- mun. ACM, 58(7):88-97, 2015. 36. [Sardina et al., 2004] S. Sardina, G. De Giacomo, Y. Lespérance, and H. J. Levesque. On the semantics of deliberation in indigolog-from theory to implementation. Annals of Mathe- matics and Artificial Intelligence, 41(2-4):259-299, 2004. 37. [Thrun et al., 2005] S. Thrun, W. Burgard, and D. Fox. Probabilis- tic Robotics. MIT Press, 2005. 38. [Van Benthem et al., 2009] J. Van Benthem, J. Gerbrandy, and B. Kooi. Dynamic update with probabilities. Studia Logica, 93(1):67-96, 2009.