ALLEGRO: Belief-Based Programming in Stochastic Dynamical Domains

1 Introduction

High-level program execution, as seen in golog [Levesque et al., 1997] and flux [Thielscher, 2005] among others, o�ers an attractive alternative to automated planning for the control of artificial agents. This is especially true for the dynamic worlds with incomplete information seen in robotics, where planning would have to generate complex behavior that includes branches and loops. One of research goals of the area of cognitive robotics [Lakemeyer and Levesque, 2007] is to understand what sorts of high-level behavior specifications would be both useful and tractable in settings like these.

A major criticism leveled at much of this work, however, is that it makes unrealistic assumptions about the robots themselves, whose sensors and e�ectors are invariably noisy and best characterized by continuous probability distributions [Thrun et al., 2005]. When a robot is executing a golog program involving some condition � about the world, for example, it is unreasonable to expect that it will either know � to be true, know it to be false, or know nothing about it. To remedy this, we [Belle and Levesque, 2013a] proposed a logical account for reasoning about probabilistic degrees of

� Partially funded by the FWO project on Data Cleaning and KU Leuven's GOA on Declarative Modeling for Mining and Learning.

Hector J. Levesque

Dept. of Computer Science University of Toronto Canada

hector@cs.toronto.edu

belief against noise in a continuous setting, building on an earlier discrete model [Bacchus et al., 1999]. In a more recent paper [Belle and Levesque, 2014b], we then presented a system called prego that is able to e�ectively calculate the degree of belief in � as a function of the initial beliefs of the robot, the noisy physical actions that have taken place, and the noisy sensing results that have been obtained. From a logical point of view, prego's handling of probabilistic features goes beyond the capabilities of popular knowledge representation action languages. From a probability point of view, prego allows successor state and sensing axioms that can be arbitrarily complex [Reiter, 2001a], making it significantly more expressive than standard probabilistic formalisms.

The prego system, however, is not a programming formalism. First, it must be given the actual sequence of physical actions and sensing results, so these must be known ahead of time. Second, it works by regression: to calculate belief in � after the actions and sensing, it regresses � to a formula � 0 about the initial state (using the machinery of the situation calculus), and then calculates the initial belief in � 0 . This regression to the initial state leads to an expression involving the integration of a large number of variables (one for each fluent, and one for each noisy action), and so is simply not feasible for an iterative program that has to evaluate belief in � repeatedly after thousands or even millions of actions.

In this paper, we propose a new programming formalism called allegro (= algol in prego) that is intended as an alternative to golog for high-level control in robotic applications. Following prego, the user provides a basic action theory (or BAT) [Reiter, 2001a] to describe the domain in terms of fluents, actions and sensors, possibly characterized by discrete and continuous distributions. Given such a BAT, allegro additionally allows the user to specify iterative programs that appeal to the robot's beliefs, and is equipped with an e�cient methodology for program execution. Overall, the proposal incorporates the following advances in this line of work:

• � Unlike prego, allegro is not just a projection system: it interprets standard golog constructs (e.g., while-loops) while adapting golog's primitive programs for noise and outcome unknowns. An implementation-independent semantic characterization of programs is provided.
• � Unlike prego, which can be used only in an o�ine manner (i.e., knowing sensed outcomes in advance), alle-

gro can be used in o�ine, online (i.e., sense as the robot is acting in an unknown environment) and network (e.g., controlling a robot over TCP) modes.

• � To handle iterative programs involving noisy actions, allegro is realized in terms of an e�cient interpreter based on sampling and progression. Inspired by particle filtering systems [Thrun et al., 2005], the interpreter maintains a database of sampled states corresponding to the agent's initial uncertainty and updates these as the program executes. For one thing, this allows belief-level queries in programs to be evaluated e�ciently in an online setting. For another, sampling admits a simple strategy for handling the nondeterminism in noisy actions. Nonetheless, the interpreter is argued to be correct using limits. To our knowledge, no other golog implementation embodies such techniques, and such a correctness notion is new to the high-level programming literature.
• � Empirical evaluations are then discussed that demonstrate the promise of the system.

In terms of organization, we first introduce allegro, before turning to its foundations and empirical behavior.

2 The allegro System

The allegro system is a programming language with a simple LISP-like syntax. 1 In this section, we (very briefly) recap domain axiomatizations, introduce the grammar of allegro programs, and discuss how allegro is used.

2.1 Domain Axiomatization

As noted above, a allegro domain is modeled as in prego. As a small example, Figure 2 shows a BAT for the domain illustrated in Figure 1, which can be read as follows: 2

1. The domain has a single fluent h, the distance to the wall, whose initial value is taken by the agent to be drawn from a (continuous) uniform distribution on [2, 12].
2. The successor state axiom for h says that it is a�ected only by the nfwd action. The first argument of nfwd is the amount the agent intends to move, and the second is the amount that is actually moved (which determines how much the value of h is to be reduced).
3. The alt axiom is used to say that if an action of the form (nfwd 2 2.79) occurs, the agent will only know that (nfwd 2 z) happened for some value of z.

1 Like prego, allegro is realized in the racket dialect of the scheme family (racket-lang.org). We use racket arithmetic freely, such as the max function, as well as any other function that can be defined in racket, like GAUSSIAN. However, the technical development does not hinge on any feature unique to that language.

2 For ease of exposition, we limit discussions in the following ways. First, we omit any mention of action preconditions here. Second, fluents are assumed to be real-valued, and moreover, only basic features of the language are explained in the paper. In general [Belle and Levesque, 2014b], fluent values can range over any set, BATs are not limited to any specific family of discrete/continuous distributions, and the language supports notions not usually seen in standard probabilistic formalisms, such as contextual likelihood axioms. (For example, if the floor is slippery, then the noise of a move action may be amplified.) All of these are fully realized in prego and allegro.

(define-fluents h) (define-ini-p-expr '(UNIFORM h 2 12)) (define-ss-exprs h (nfwd x y) '(max 0 (- h ,y)) (define-alts (nfwd x y) (lambda (z) '(nfwd ,x ,z))) (define-l-exprs (nfwd x y) '(GAUSSIAN ,y ,x 1.0) (sonar z) '(GAUSSIAN ,z h 4.0))

1. The likelihood axiom for nfwd says that the actual amount moved by nfwd will be expected by the agent to be centered (wrt a normal distribution) around the intended amount with a standard deviation of 1.0.
2. The likelihood axiom for sonar says that sonar readings are noisy but will be expected to be centered around the true value of h with a standard deviation of 4.0.

The idea here is that starting with some initial beliefs, executing (sonar 5) does not guarantee that the agent is actually 5 units from the wall, although it should serve to increase the robot's confidence in that fact. Analogously, performing a noisy move with an intended argument 2 means that the robot may end up moving (say) 2.79 units. Nevertheless, its degree of belief that it is closer to the wall should increase.

2.2 Belief-based Programs

The BAT specification describes the noise in actions and sensors wrt the actual outcomes and values observed. But a robot executing a program need not know these outcomes and values. For this reason, the primitive programs of allegro are actions that suppress these parameters. So for the actions (nfwd x y) and (sonar z) appearing in a BAT, the primitive programs will be (nfwd x) and (sonar).

The basic allegro language uses five program constructs: prim primitive programs; (begin prog 1 . . . prog n ) sequence; (if form prog1 prog2) conditional; (let ((var1 term1) . . . (varn termn)) prog) assignments; (until form prog) until loop.

Here form stands for formulas built from this grammar:

form ::= ( � term1 term2) j ( � form1 form2) j (not form)

where � 2 f<; >; =g and � 2 fand; org : Here term stands for terms built from the following grammar:

term ::= (exp term) j number j fluent j var j (� term1 term2) j (if form term1 term2)

where � is any arithmetic operator (e.g., + and -). The primary "epistemic" operator in allegro is exp: (exp term)

refers to the expected value of term. (Reasoning about the expected value about a fluent allows the robot to monitor how it changes with sensing, for example.) The degree of belief in a formula form can then be defined in terms of exp as follows:

(bel form) � (exp (if form 1:0 0:0))

For our purposes, it is convenient to also introduce (conf term number), standing for the degree of confidence in the value of a term, as an abbreviation for:

(bel(> number (abs (- term (exp term)))))

For example, given a fluent f that is normally distributed, (conf f .1) is higher when the curve is narrower.

2.3 Usage

The allegro system allows programs to be used in three ways: in online mode � the system displays each primitive program as it occurs, and prompts the user to enter the sensing results; in network mode � the system is connected to a robot over TCP, the system sends primitive programs to the robot for execution, and the robot sends back the sensing data it obtains; and finally, in o�ine mode � the system generates ersatz sensing data according to the given error model. In all cases, the system begins in an initial belief state, and updates this belief state as it runs the program.

As a simple illustration, imagine the robot from Figure 2 would like to get within 2 and 6 units from the wall. It might proceed as follows: sharpen belief about current position (by sensing), (intend to) move by an appropriate amount, adjust beliefs for the noise of the move, and repeat these steps until the goal is achieved. This intuition is given as a program in Figure 3: here, conf is used to first become confident about h and then exp is used to determine the distance for getting midway between 2 and 6 units. (An arbitrary threshold of .8 is used everywhere wrt the robot's beliefs.) For an online execution of this program prog in allegro, we would do:

> (online-do prog) Execute action: (sonar) Enter sensed value: 4.1 Enter sensed value: 3.4 Execute action: (nfwd 1.0) Enter sensed value: 3.9 Enter sensed value: 4.2 Execute action: (nfwd 0.0)

We see the robot first applying the sonar sensor, for which the user reports a value of 4.1. After updating its beliefs for this observation, the robot is not as confident as required by prog, and so, a second sensing action is executed for which 3.4 is read. Then the robot attempts a (noisy) move, but its confidence degrades as a result. So these steps are repeated once more, after which the program terminates. On termination, the required property can be tested in allegro using:

> (bel (and (>= h 2) (<= h 6))) 0.8094620133032484

3 Mathematical Foundations

The formal foundation of allegro is based on the situation calculus [Reiter, 2001a]. Basically, the interpretation of

(until (> (bel (and (>= h 2) (<= h 6))) .8) (until (> (conf h .4) .8) (sonar)) (let ((diff (- (exp h) 4))) (nfwd diff)))

prego-style BATs is as in [Belle and Levesque, 2014b], which we can only summarize here. The interpretation of programs is based on the online version of golog [Sardina et al., 2004].

3.1 BAT Semantics

In a nutshell, the situation calculus is a many-sorted dialect of predicate logic, with sorts for actions, situations and objects. Situations are basically histories in that initial situations correspond to the ways the world might be initially, and successor situations are obtained by applying a distinguished binary symbol do. That is, do(a1 � � � ak; s) denotes the situation resulting from performing actions a1 through ak at situation s: We let the constant S0 denote the actual initial situation.

Fluents capture changing properties about the world. Here we assume that nullary functions f1; : : : ; fk are all the fluents in the language, and that these take no arguments other than a single situation term. When writing formulas, we often suppress the situation argument in a logical expression � or use a distinguished variable now, and we let �[s] denote the formula with that variable replaced by s. In this sense, the BAT syntax of prego (and allegro) is to be seen as a situationsuppressed fragment of the situation calculus language. 3

The situation calculus has been extended over the years, and here, we appeal to our prior account on reasoning about probabilistic degrees of belief and noise [Belle and Levesque, 2013a; 2014b]. It is based on three distinguished fluents: p; l and alt: Using these, a BAT D consists of (free variables are implicitly assumed to be quantified from the outside):

• � Initial theory D0: an axiom of the form p(s; S0) = �[s] to specify the agent's initial uncertainty, where � is a situation-suppressed expression using the fluents. Roughly, the p fluent acts as a numeric version of the accessibility relation in modal logic [Bacchus et al., 1999].
• � Likelihood and alternate actions axioms of the form l(a(~x); s) = lha(~x)[s] and alt(a; u) = a 0 . These formalize the noise and outcomes of noisy sensors and e�ectors.
• � Successor state axioms of the form 8a; s: f (do(a; s)) = ssa f (a)[s]: the values of fluents may change after actions as determined by these axioms, which appeal to Reiter's [2001a] solution to the frame problem. A domainindependent successor state axiom is provided for the p fluent that functions as follows: the p-value of the successor situation do(a; s) is obtained by multiplying the p-value of s with the likelihood of action a:

Example 1: The sonar's noise model, move action's nondeterminism and initial beliefs of the robot from Figure 2

3 Non-logical symbols, such as fluent and action symbols, in the situation calculus are italicized; e.g., fluent h in prego/allegro is h in the language of the situation calculus.

can be mapped to the following situation calculus formulas: l(sonar(z); s) = Gaussian(z; h; 4)[s]; alt(nfwd(x; y); z) = nfwd(x; z) and p(s; S0) = Uniform(h; 2; 12)[s]:

Given a BAT D, the degree of belief in any situationsuppressed � at s is defined using:

where the normalization factor � is obtained by replacing � with true, and if s = do(a1 � � � an; S0) then s � = do(alt(a1; u1) � � � alt(an; un); S0): We do not expand the Density term here, except note that it applies the successor state axiom for p to all ground situation terms that are obtained as a result of noisy actions. (That is, possible outcomes for a are given by alt(a; u) wrt the integration variable u:) Given an argument �; then, the Density term returns the p-value of the situation if � holds, and 0 otherwise. This definition of Bel can be shown to subsume Bayesian conditioning [Belle and Levesque, 2013a]. (Note also that for discrete distributions, we would replace the appropriate integral with a sum.)

Analogously, the expected value of a situation-suppressed term t at s can be defined as:

where the denominator � replaces t with 1, and s and s � are as before. This is to be read as considering the t-values across situations and multiplying them by the p-values of the corresponding situations. So, if a space of situations is uniformly distributed, then we would obtain the average t-value.

3.2 Program Semantics

allegro implements a deterministic fragment of golog over online executions [Sardina et al., 2004]. In general, golog programs are defined over the following constructs:

standing for primitive programs, tests, sequence, nondeterministic branch, nondeterministic choice of argument and nondeterministic iteration respectively. The constructs used in allegro can then be defined in terms of these:

(Here � would mention Bel or Exp.) Unlike standard golog, however, the smallest programs in our setting are not atomic actions, but new symbols called primitive programs (Section 2.2), which serve as placeholders for actual actions on execution. So for every a(~x; y) in the logical language, where y corresponds to the actual outcome/observation, there are primitive programs a(~x) that suppress the latter argument.

A semantics for the online execution of allegro programs over noisy acting and sensing can be given in the very same style as [Sardina et al., 2004]. Two special predicates Trans and Final are introduced to define a single-step transition semantics for allegro programs: Trans(�; s; � 0 ; s 0 ) means that by executing program � at s; one can get to s 0 with an elementary step with the program � 0 remaining, whereas Final(�; s) holds when � can successfully terminate in situation s:

The predicates Trans and Final are defined axiomatically, precisely as in [Sardina et al., 2004], with the exception of the definition for primitive programs:

• � if a(~x) is a primitive program in allegro, and on doing this action we obtain a value c (either an observation or the outcome of a noisy action) then

The definitions are lumped here as a set E; along with an encoding of programs as first-order terms for quantificational purposes as a set F [Sardina et al., 2004]. Putting it all together, we say that the online execution of a program � successfully terminates after a sequence of actions � if

where Do(�; s; s 0 ) � 9� 0 [Trans � (�; s; � 0 ; s 0 )^Final(� 0 ; s 0 )] and Trans � denotes the reflexive transitive closure of Trans.

4 A Sampling-based Interpreter

We now present pseudo-code for the interpreter of allegro and argue for its correctness relative to the specification above. The interpreter is based on sampling [Murphy, 2012], and its correctness is defined using limits.

The overall system is described using three definitions: an evaluator of expressions eval, an epistemic state e, and an interpreter of programs int. In what follows, we let a world state w be a vector of fluent values (i.e., w[i] is the value of the i-th fluent) and an epistemic state e is a finite set of pairs (w; q) where w is a world state and q 2 [0; 1]. Intuitively, w is a world considered possible by the agent, and q is the probabilistic weight attached to that world.

The Evaluator

The interpreter relies on an evaluator eval that takes three arguments: a term or a formula, a world state, an epistemic state, and returns a value (corresponding to the value of the term or the truth value of a formula):

Definition 2: eval[�; w; e] is defined inductively over a term t or formula d by

1. eval[u; w; e] = u, when u is a number or a variable.
2. eval[ f; w; e] = w[i], when f is the i-th fluent.
3. eval[(notd); w; e] = 1 � eval[d; w; e], and similarly for other logical connectives over formulas.
4. eval[(+ t1 t2); w; e] = eval[t1; w; e] + eval[t2; w; e], and similarly for other arithmetic operators over terms.
5. eval[(if d t1 t0); w; e] = eval[ti; w; e], where we obtain i = eval[d; w; e].

We write eval[t; e] when w is not used (because all the fluents in t appear in the scope of an exp), and eval[t; w] when e is not used (because t contains no exp terms).

Epistemic State

To relate the evaluator to a BAT specification, we first obtain the initial epistemic state e0. To get the idea, suppose the values of the fluents fi were to range over finite sets dom( fi). Given any D0 of the form 8s(p(s; S0) = �[s]), we let: 4

By construction, e0 is the set of all possible worlds in a finite domain setting. However, in continuous domains, dom( fi) is R, leading to infinitely many possible worlds. Nonetheless, this space can be approximated in terms of a finite epistemic state by sampling: assume we can randomly draw elements (and vectors) of R : Suppose the BAT is defined using k fluents, and let n be a large number. Then:

When actions occur, the interpreter below also depends on a progression procedure prog that takes an epistemic state and an action instance as arguments and returns a new state:

Definition 3: Suppose a(c) is a noisy sensor. Then prog[e, a(c)] = f (w 0 ; q 0 ) j (w; q) 2 e; w 0 [ j] = eval[ssa f j (a(c)); w] and q 0 = q�eval[lha(c); w] g

where ssa and lh refer to the RHS of successor state and likelihood axioms in D instantiated for a(c).

Intuitively, for (w; q) 2 e, standing for some current situation and its density, we use the given BAT to compute the fluent values and the density of the successor situation. In particular, for a noisy sensor, the successor density incorporates the likelihood of the observed value c:

Definition 4: Suppose a(c; c 0 ) is a noisy action. Then

The notion of progression is more intricate for noisy actions because for any ground action term a(c; c 0 ), the agent only knows that a(c; y) happened for some y 2 R : (For ease of exposition, assume alt(a(c; x); y) = a(c; y).) Among other things, this means that the progression would need to account for all possible instantiations of the variable y, which are infinitely many. Sampling, however, permits a simple strategy: assume we can randomly draw n elements of R ; once for each world state in e, the idea being that the value drawn is applied as an argument to action a for the corresponding world. Consequently, for any e and a; jej = jprog[e; a(c; c 0 )]j, and the sampling limit is still shown to converge. In essence, we needed to appeal to sampling for each occurrence of an integration variable in Exp: for every fluent and for the argument of every noisy action.

4 We can evaluate the RHS of axioms in D wrt a world state using Definition 2. These are simply formulas (with a single situation term) of the logical language, and in the allegro syntax, they correspond to expressions mentioning the fluents. For example, evaluating the function (UNIFORM h 2 12) at a world state where h is 10 would yield .1, but in one where it is 15 would yield 0.

The Interpreter

Finally, we describe the interpreter for allegro, called int. It takes as its arguments a program and an initial epistemic state and returns as its value an updated epistemic state:

Definition 5: int[�; e] is defined inductively over � by

1. int[(a),e] = prog[e, a(c)], where c is observed on doing noisy-sensor primitive program a.
2. int[(a t),e] = prog[e, a(c; c)], where c = eval[t; e], after doing noisy-action primitive program a for argument c. (Since the second argument of a is irrelevant for e; we simply set it also to c.)
3. int[(begin�1. . . �n),e]=int[�n,int[(begin�1. . . �n�1),e]].
4. int[(if��1 �0), e] = int[�i, e], where i = eval[�; e].
5. int[(let ((x t)) �), e] = int[� x v , e], where v = eval[t; e].
6. int[(until��), e] = e if eval[�; e] = 1, and otherwise, int[(until��), int[�; e]].

The interpreter's correctness is established by the following:

Theorem 6: Suppose D is a BAT with e0 (of size n) as above, � is any program, and t is any term. Suppose there is an action sequence � such that D[E[F j= Do(�; S0; do(�; S0)): Then,

Proof sketch: Proof by induction on �, and only primitive programs are presented here. Suppose � is empty. Since D0 defines a k-variable density function and e0 draws n samples from R k ; standard notions of convergence readily apply [Murphy, 2012]. Suppose � is a noisy sensor a(c); in which case the k-variable density function simply takes the likelihood of the sensing into account, and the argument follows easily. Suppose � is a noisy action a(c; c 0 ). Then Exp(t; do(a(c; c 0 ); S0)) is seen to define a (k + 1)-variable density function. Although our notion of progression considers (only) a single instance of the noisy action for each of the n world states, this is essentially seen as actually drawing n samples from R k+1 : Thus, the desired convergence is also obtained.

5 Evaluations

We consider the empirical behavior of allegro in this section. Mainly, we argue for progression rather than regression, test its scalability, and investigate the e�ect of noise on program termination tasks. We set the sample size je0j = 100000: Experiments were run on Mac OS X 10.9 using a system with 1.4 GHz Intel Core 2 Duo processor, 2 GB RAM, and racket v6.1. CPU time is measured in milliseconds (ms).

Regression and Progression

The prego system was shown in [Belle and Levesque, 2014b] to exhibit reasonable empirical behavior on projection tasks. Here, we are interested in contrasting the two systems. As discussed, regressing to the initial state leads to an expression involving the integration of a large number of variables, and calculating probabilities with such expressions would simply not be feasible in iterative programs over many actions. (We note that the regression simplification itself is unproblematic, but the integration is challenging.) So, progression seems like a better choice for the interpreter in long-lived agents.

We test this intuition as follows. Imagine the robot from Figure 1 has performed 50 noisy actions: (nfwd 2 2.1)(sonar 5)(nfwd 1 2.1) : : : , after which we query the robot's beliefs, both in the current situation and future ones, e.g., (expt h), (bel (< h 2)), (nfwd 3 3.05)(expt h), (nfwd 3 3.05)(bel (< h 2)), and so on. In other words, we test static and projection queries against prego and allegro in Figure 4a. (For allegro, we consider its online behavior where given an action sequence �; and the time � for computing prog[e0; �], we plot �=j�j.) We observe that evaluation by regression grows exponentially in the number of queries considered in the experiments. Thus, even purely sequential programs over hundreds of actions will be di�cult to handle. In contrast, with progression, the increased e�ort for more queries is insignificant (as needed for iterative programs), mainly because the states are updated after actions and queries are evaluated in the current situation. Moreover, in a separate evaluation for scaling behavior in Figure 4b, allegro is tested for action sequences of length up to 500; prego runs out of memory on sequences of that length.

We can further contrast the online performance of allegro to the total accumulated time for progressing e0 wrt the 50 actions, also plotted in Figure 4a. In this context, however, we see progressing the database is more expensive than regression provided the number of queries is small. In other words, when the agent simply needs to test a property of the future (e.g., in planning), regression is preferable. In sum, in continuous domains, regression is the right choice for testing plan validity, and progression for long-running programs.

Scalability

Here, allegro's online performance is tested for domains of increasing sizes over long action sequences. The BAT from Figure 2 is a domain of size 1, and for size n, we axiomatize domains with n fluents and n noisy actions.

Taking into account the increased e�ort needed to maintain larger domains (that is, the world states correspond to lengthier vectors), we observe in Figure 4b that the implemented allegro interpreter performs exactly as one would require for prolonged sequences of actions: the progression e�ort is constant. In sum, the implementation scales well relative to domain size in long-lived systems.

From Noise To Termination

For our final evaluation, we test the sensitivity of the termination of the program from Figure 3 to the standard deviation in the noise of the robot's e�ectors and sensors. (Basically, a lower standard deviation means a more accurate device.) The plot in Figure 4c gives an indication of what one should expect regarding the program's time for success wrt this noise. At one extreme, an accurate sensor with an inaccurate e�ector would mean that the robot gets confident about h quickly but takes longer to move to the desired position. At the other extreme, an accurate e�ector would mean that reaching the desired position is easily accomplished, but only after getting confident about h that takes longer with an inaccurate sensor.

6 RelatedWork and Discussions

We first relate allegro to high-level agent programming proposals, and then to planning proposals.

The allegro system is a programming model based on the situation calculus, and so is a new addition to the golog family of high-level programming languages [Levesque et al., 1997; Sardina et al., 2004]. In particular, it follows in the tradition of knowledge-based golog with sensing in an online context [Reiter, 2001b; Claßen and Lakemeyer, 2006; Fan et al., 2012], but generalizes this in the sense of handling degrees of belief and probabilistic noise in the action model.

The golog family has been previously extended for probabilistic nondeterminism, but there are significant di�erences. For example, in the pGolog model [Grosskreutz and Lakemeyer, 2003], the outcome of a nondeterminism action is immediately observable after doing the action, and continuous distributions are not handled. This is also true of the notable dtgolog approach [Boutilier et al., 2000] and its variants [Ferrein and Lakemeyer, 2008]. In this sense, the allegro model is more general where the agent cannot observe the outcomes and sensors are noisy. Moreover, these proposals do not represent beliefs explicitly, and so do not include a query language for reasoning about nested belief expressions.

Outside of the situation calculus, an alternative to golog, called flux [Thielscher, 2004; 2005], has been extended for knowledge-based programming with noisy e�ectors in [Thielscher, 2001; Martin and Thielscher, 2009]; continuous probability distributions and nested belief terms are, however, not handled. The concept of knowledge-based programming was first introduced in [Fagin et al., 1995]. These have been extended for Spohn-style [1988] ordinal functions in [Laverny and Lang, 2005]. For discussions on how high-level programming relates to standard agent programming [Shoham, 1993], see [Sardina and Lesp´erance, 2010].

Programs, broadly speaking, generalize sequential and tree-like plan structures, but can also be used to limit plan search [Baier et al., 2007]; we refer interested readers to [Lakemeyer and Levesque, 2007] for discussions. There are, of course, many planning approaches in online contexts, including knowledge-based planning [Petrick and Bacchus, 2004; Van Ditmarsch et al., 2007], decision-theoretic proposals [Puterman, 1994; Kaelbling et al., 1998], corresponding relational abstractions [Sanner and Kersting, 2010; Zamani et al., 2012], and belief-based planning [Kaelbling and Lozano-P´erez, 2013]. See [Lang and Zanuttini, 2012] on viewing knowledge-based programs as plans.

In the same vein, let us reiterate that the BAT syntax is based on prego, and from the viewpoint of a representation language, see [Belle and Levesque, 2014b] for discussions on its expressiveness relative to other formalisms, such as probabilistic planning languages [Sanner, 2011], action formalisms [Van Benthem et al., 2009; Thielscher, 2001; Iocchi et al., 2009], and related e�orts on combining logic and probability [Bacchus, 1990; Richardson and Domingos, 2006]. Notably, its support for continuous distributions and arbitrary successor state axioms makes it a tractable but expressive language.

In the context of probabilistic models, we remark that there are other realizations of program-based probabilistic behavior, such as probabilistic programming [Milch et al., 2005; Goodman et al., 2008]. These are formal languages that provide program constructs for probabilistic inference. While they are expressive enough to capture dynamical probabilistic models [Nitti et al., 2013], they belong to a tradition that is di�erent from the golog and flux families. For example, atomic programs in golog are actions taken from a basic action theory whereas in [Milch et al., 2005], atomic constructs can be seen as random variables in a Bayesian Network. In other words, in golog, the emphasis is on high-level control, whereas in many probabilistic programming proposals, the emphasis is on inference. So, a direct comparison is di�cult; whether these traditions can be combined is an open question.

Before wrapping up, let us emphasize two issues concerning our interpreter. First, regarding Theorem 6, it is worth relating this result to the notion of progression of BATs [Reiter, 2001a]. In prior work [Belle and Levesque, 2014a], we investigated this latter notion of progression for continuous domains. Progression is known to come with strong negative results, and in continuous domains, we noted that further restrictions to invertible basic action theories may be necessary. In a nutshell, invertible theories disallow actions such as the max function (used in Figure 2) because they have the e�ect of transforming a uniform continuous distribution on h to one that is no longer purely continuous. (See [Belle and Levesque, 2014a] for examples.) In contrast, no such limitations are needed here: roughly, this is because our notion of an epistemic state is a discrete model of a continuous function, leading to a possible world-based progression notion. Consequently, however, we needed to appeal to limits here, while the progression formulation in that prior work does not [Belle and Levesque, 2014a, Corollary 12].

Second, our discussion on regression and progression in Section 5 assumes an interpreter based entirely on one of these approaches. However, a direction pursued by Erwin et al. [2014] maintains the sequence of performed actions and processes these via regression to progress e�ectively. (For example, the progression of a database wrt an action whose e�ects are undone by another action in the future can be avoided.) Moreover, interpreters may appeal to regression when some form of plan search is necessary within programs [Lakemeyer and Levesque, 2007]. The consideration of such ideas in the allegro context would lead to useful extensions, and is left for the future. (For example, if the performed noisy actions are characterized by normal distributions, then their conjugate property can be exploited via regression [Belle and Levesque, 2013b].)

7 Conclusions

This paper proposes an online account of belief-based programs that handles discrete and continuous probability distributions. It is intended as an alternative to golog in stochastic dynamical domains where sensors and e�ectors are noisy.

Beginning with the expressive logical language of the situation calculus, we presented and implemented allegro using the BAT syntax of prego. This fragment is interesting because it embodies the desirable features of logic-based action languages, such as non-trivial successor state and likelihood axioms. The latter property together with the rich query mechanism and program syntax in allegro suggests that it could be seen as a basis for relating high-level agent programming and probabilistic robotics [Thrun et al., 2005] in a general way.

There are many interesting avenues for future work, such as relating belief-based programs to decision-theoretic highlevel programming [Boutilier et al., 2000], particle filters [Thrun et al., 2005], and probabilistic programming [Goodman et al., 2008], among others. Demonstrating how the allegro system can lead to robust behavior in robots, in the sense of [Lakemeyer and Levesque, 2007], is also planned for the future.