Reasoning about Probabilities in Unbounded First-Order Dynamical Domains

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

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

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

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.

1. [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):

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