Continuous State Spaces

This section takes many of the concepts that have been developed in Sections

11.1 and 11.2 and generalizes them to continuous state spaces. This represents an important generalization because the configuration space concepts, on which motion planning was defined in Part II, are all based on continuous state spaces. In this section, the state space might be a configuration space, X = , as defined in Chapter 4 or any other continuous state space. Since it may be a configuration space, many interesting problems can be drawn from robotics.

C

During the presentation of the concepts of this section, it will be helpful to recall analogous concepts that were already developed for discrete state spaces. In many cases, the formulations appear identical. In others, the continuous case is more complicated, but it usually maintains some of the properties from the discrete case. It will be seen after introducing continuous sensing models in Section 11.5.1 that some problems formulated in continuous spaces are even more elegant and easy to understand than their discrete counterparts.

• • 1. Discrete-Stage Information Spaces

Assume here that there are discrete stages. Let X ⊆ Rm be an n-dimensional manifold for n ≤ m called the state space. Let Y ⊆ R be an ny -dimensional manifold for ny ≤ m called the observation space. For each x ∈ X, let Ψ(x) ⊆ Rm

4 m

be an nn-dimensional manifold for nn m called the set of nature sensing actions. The three kinds of sensors mappings, h, defined in Section 11.1.1 are possible, to yield either a state mapping, y = h(x), a state-nature mapping y = h(x, ψ), or a history-based, y = hk(x1, . . . , xk, y). For the case of a state mapping, the preimages, H(y), once again induce a partition of X. Preimages can also be defined for state- action mappings, but they do not necessarily induce a partition of X.

≤

Many interesting sensing models can be formulated in continuous state spaces. Section 11.5.1 provides a kind of sensor catalog. There is once again the choice of nondeterministic or probabilistic uncertainty if nature sensing actions are used. If nondeterministic uncertainty is used, the expressions are the same as the discrete case. Probabilistic models are defined in terms of a probability density function, p : Ψ [0, ), in which p(ψ) denotes the continuous-time replacement for P(ψ). The model can also be expressed as p(y x), in that same manner that P(y x) was obtained for discrete state spaces.

5

| |

→ ∞

The usual three choices exist for the initial conditions: 1) Either x1 ∈ X is

given; 2) a subset X1 X is given; or 3) a probability density function, p(x), is given. The initial condition spaces in the last two cases can be enormous. For example, if X = [0, 1] and any subset is possible as an initial condition, then

∈

I0 = pow(R), which has higher cardinality than R. If any probability density function is possible, then I0 is a space of functions.

6

The I-space definitions from Section 11.1.2 remain the same, with the under-

standing that all of the variables are continuous. Thus, (11.17) and (11.19) serve as the definitions of Ik and I. Let U ⊆ Rm be an nu-dimensional manifold for nu ≤ m. For each x ∈ X and u ∈ U, let Θ(x, u) be an nθ -dimensional manifold for

nθ m. A discrete-stage I-space planning problem over continuous state spaces can be easily formulated by replacing each discrete variable in Formulation 11.1 by its continuous counterpart that uses the same notation. Therefore, the full formulation is not given.

≤

4If you did not read Chapter 4 and are not familiar with manifold concepts, then assume

X = Rn; it will not make much difference. Make similar assumptions for Y , Ψ(x), U , and Θ(x, u).

5Assume that all continuous spaces are measure spaces and all probability density functions are measurable functions over these spaces.

6To appreciate of the size of this space, it can generally be viewed as an infinite-dimensional vector space (recall Example 8.5). Consider, for example, representing each function with a series expansion. To represent any analytic function exactly over [0, 1], an infinite sequence of real-valued coefficients may be needed. Each sequence can be considered as an infinitely long vector, and the set of all such sequences forms an infinite-dimensional vector space. See [346, 836] for more background on function spaces and functional analysis.

• • 1. Continuous-Time Information Spaces

Now assume that there is a continuum of stages. Most of the components of Section 11.4.1 remain the same. The spaces X, Y , Ψ(x), U, and Θ(x, u) remain the same. The sensor mapping also remains the same. The main difference occurs in the state transition equation because the effect of nature must be expressed in terms of velocities. This was already introduced in Section 10.6. In that context, there was only uncertainty in predictability. In the current context there may be uncertainties in both predictability and in sensing the current state.

For the discrete-stage case, the history I-states were based on action and ob- servation sequences. For the continuous-time case, the history instead becomes a function of time. As defined in Section 7.1.1, let T denote a time interval, which

may be bounded or unbounded. Let y˜t : [0, t] → Y be called the observation

history up to time t T . Similarly, let u˜t : [0, t) U and x˜t : [0, t] X be called the action history and state history, respectively, up to time t T .

∈

∈ → →

Thus, the three kinds of sensor mappings in the continuous-time case are as follows:

• • • 1. A state-sensor mapping is expressed as y(t) = h(x(t)), in which x(t) and y(t) are the state and observation, respectively, at time t ∈ T .
      2. A state-nature mapping is expressed as y(t) = h(x(t), ψ(t)), which implies that nature chooses some ψ(t) ∈ Ψ(x(t)) for each t ∈ T .
      3. A history-based sensor mapping, which could depend on all of the states obtained so far. Thus, it depends on the entire function x˜t. This could be denoted as y(t) = h(x˜t, ψ(t)) if nature can also interfere with the observation.

If u˜t and y˜t are combined with the initial condition η0, the history I-state at time t is obtained as

ηt = (η0, u˜t, y˜t). (11.53)

The history I-space at time t is the set of all possible ηt and is denoted as It. Note that It is a space of functions because each ηt ∈ It is a function of time. Recall that in the discrete-stage case, every Ik was combined into a single history I-space, Ihist, using (11.18) or (11.19). The continuous-time analog is obtained as

Ihist = It, (11.54)

I

t∈T

which is an irregular collection of functions because they have different domains; this irregularity also occurred in the discrete-stage case, in which hist was com- posed of sequences of varying lengths.

I

A continuous-time version of the cost functional in Formulation 11.1 can be given to evaluate the execution of a plan. Let L denote a cost functional that may be applied to any state-action history (x˜t, u˜t) to yield

r t

L(x˜t, u˜t) =

l(x(t′), u(t′))dt′ + lF (x(t)), (11.55)

0

0

L(x˜t, u˜t) =

l(x(t′), u(t′))dt′ + lF (x(t)), (11.55)

in which l(x(t′), u(t′)) is the instantaneous cost and lF (x(t)) is a final cost.

• • 1. Derived Information Spaces

For continuous state spaces, the motivation to construct derived I-spaces is even stronger than in the discrete case because the I-space quickly becomes unwieldy.

• • • 1. Nondeterministic and probabilistic I-spaces for discrete stages

The concepts of I-maps and derived I-spaces from Section 11.2 extend directly to continuous spaces. In the nondeterministic case, κndet once again transforms the initial condition and history into a subset of X. In the probabilistic case, κprob yields a probability density function over X. First, consider the discrete-stage case.

The nondeterministic I-states are obtained exactly as defined in Section 11.2.2, except that the discrete sets are replaced by their continuous counterparts. For ex- ample, F(x, u) as defined in (11.28) is now a continuous set, as are X and Θ(x, u). Since probabilistic I-states are probability density functions, the derivation in Sec- tion 11.2.3 needs to be modified slightly. There are, however, no important con- ceptual differences. Follow the derivation of Section 11.2.3 and consider which parts need to be replaced.

The replacement for (11.35) is

p(xk

|yk

p(yk|xk)p(xk)

r

) = , (11.56)

X

p(yk|xk)p(xk)dxk

X

p(yk|xk)p(xk)dxk

which is based in part on deriving p(yk xk) from p(ψk xk). The base of the induc- tion, which replaces (11.36), is obtained by letting k = 1 in (11.56). By following the explanation given from (11.37) to (11.40), but using instead probability density functions, the following update equations are obtained:

| |

and

p(xk+1|ηk, uk) = r

X

=

r

X

p(xk+1|xk, uk, ηk)p(xk|ηk)dxk

p(xk+1|xk, uk)p(xk|ηk)dxk,

(11.57)

p(x

k+1

|yk+1

, ηk

, uk

p(yk+1|xk+1)p(xk+1|ηk, uk)

r

) = . (11.58)

X

p(yk+1|xk+1)p(xk+1|ηk, uk)dxk+1

X

p(yk+1|xk+1)p(xk+1|ηk, uk)dxk+1

• • • 1. Approximating nondeterministic and probabilistic I-spaces

Many other derived I-spaces extend directly to continuous spaces, such as the limited-memory models of Section 11.2.4 and Examples 11.11 and 11.12. In the

present context, it is extremely useful to try to collapse the I-space as much as

possible because it tends to be unmanageable in most practical applications. Recall that an I-map, κ : Ihist → Ider, partitions Ihist into sets over which a constant

action must be applied. The main concern is that restricting plans to der does not inhibit solutions.

I

Consider making derived I-spaces that approximate nondeterministic or prob- abilistic I-states. Approximations make sense because X is usually a metric space in the continuous setting. The aim is to dramatically simplify the I-space while trying to avoid the loss of critical information. A trade-off occurs in which the quality of the approximation is traded against the size of the resulting derived I-space. For the case of nondeterministic I-states, conservative approximations are formulated, which are sets that are guaranteed to contain the nondeterministic I-state. For the probabilistic case, moment-based approximations are presented, which are based on general techniques from probability and statistics to approxi- mate probability densities. To avoid unnecessary complications, the presentation will be confined to the discrete-stage model.

X_1(η1) _X_2(η2) _X_3(η_3)

Figure 11.9: The nondeterministic I-states may be complicated regions that are difficult or impossible to compute.

Xˆ1

Xˆ2

Xˆ3

Figure 11.10: The nondeterministic I-states can be approximated by bounding spheres.

Conservative approximations Suppose that nondeterministic uncertainty is used and an approximation is made to the nondeterministic I-states. An I-map,

κapp : Indet → Iapp, will be defined in which Iapp is a particular family of subsets

of X. For example, app could represent the set of all ball subsets of X. If

I

X = R2, then the balls become discs, and only three parameters (x, y, r) are needed to parameterize Iapp (x, y for the center and r for the radius). This implies

that app R3; this appears to be much simpler than ndet, which could be a complicated collection of regions in R2. To make app even smaller, it could be required that x, y, and r are integers (or are sampled with some specified

I

I ⊂ I

dispersion, as defined in Section 5.2.3). If app is bounded, then the number of derived I-states would become finite. Of course, this comes an at expense because

I

Indet may be poorly approximated.

For a fixed sequence of actions (u1, u2, . . .) consider the sequence of nondeter- ministic I-states:

u ,y u ,y u ,y

X (η ) X (η ) X (η ) · · · , (11.59)

1 2 2 3 3 4

1 1 −→ 2 2 −→ 3 3 −→

which is also depicted in Figure 11.9. The I-map app must select a bounding

I

region for every nondeterministic I-state. Starting with a history I-state, η, the nondeterministic I-state Xk(ηk) can first be computed, followed by applying Iapp

to yield a bounding region. If there is a way to efficiently compute Xk(ηk) for any

ηk, then a plan on Iapp could be much simpler than those on Indet or Ihist.

If it is difficult to compute Xk(ηk), one possibility is to try to define a de- rived information transition equation, as discussed in Section 11.2.1. The trouble,

however, is that Iapp is usually not a sufficient I-map. Imagine wanting to com-

pute κapp(Xk+1(ηk+1)), which is a bounding approximation to Xk+1(ηk+1). This can be accomplished by starting with Xk(ηk), applying the update rules (11.30)

and (11.31), and then applying κapp to Xk+1(ηk+1). In general, this does not pro- duce the same result as starting with the bounding volume Iapp(Xk(ηk)), applying

(11.30) and (11.31), and then applying κapp.

Thus, it is not possible to express the transitions entirely in app without some further loss of information. However, if this loss of information is tolerable, then an information-destroying approximation may nevertheless be useful. The general idea is to make a bounding region for the nondeterministic I-state in each iter-

I

ation. Let Xˆk denote this bounding region at stage k. Be careful in using such

approximations. As depicted in Figures 11.9 and 11.10, the sequences of derived

I-states diverge. The sequence in Figure 11.10 is not obtained by simply bounding each calculated I-state by an element of Iapp; the entire sequence is different.

Initially, Xˆ1 is chosen so that X1(η1) ⊆ Xˆ1. In each inductive step, Xˆk is

treated as if it were the true nondeterministic I-state (not an approximation).

Using (11.30) and (11.31), the update for considering uk and yk+1 is

Xˆk′ +1 = （

I

xk ∈Xˆk

F(xk, uk)＼ ∩ H(yk+1). (11.60)

In general, Xˆk′ +1(ηk+1) might not lie in Iapp. Therefore, a bounding region, Xˆk+1 ∈ app, must be selected to approximate Xˆ ′ under the constraint that Xˆk′ +1 Xˆk+1. This completes the inductive step, which together with the base case yields a

I ⊆

sequence

Xˆ u_1,y_2 Xˆ

1 −→

2 −→

u_2,y_3 Xˆ

u ,y

3 −→ · · · , (11.61)

3 4

which is depicted in Figure 11.10.

Both a plan, π : Iapp → U, and information transitions can now be defined over

Iapp. To ensure that a plan is sound, the approximation must be conservative. If in

some iteration, Xˆk+1(ηk+1) Xˆk′ +1(ηk+1), then the true state may not necessarily be included in the approximate derived I-state. This could, for example, mean that a robot is in a collision state, even though the derived I-state indicates that

⊂

this is impossible. This bad behavior is generally avoided by keeping conservative

approximations. At one extreme, the approximations can be made very conserva- tive by always assigning Xˆk+1(ηk+1) = X. This, however, is useless because the only possible plans must apply a single, fixed action for every stage. Even if the

approximations are better, it might still be impossible to cause transitions in the approximated I-state. To ensure that solutions exist to the planning problem, it is therefore important to make the bounding volumes as close as possible to the derived I-states.

This trade-off between the simplicity of bounding volumes and the computa- tional expense of working with them was also observed in Section 5.3.2 for collision detection. Dramatic improvement in performance can be obtained by working with simpler shapes; however, in the present context this could come at the expense of failing to solve the problem. Using balls as described so far might not seem to pro- vide very tight bounds. Imagine instead using solid ellipsoids. This would provide tighter approximations, but the dimension of app grows quadratically with the dimension of X. A sphere equation generally requires n + 1 parameters, whereas the ellipsoid equation requires (n) + 2n parameters. Thus, if the dimension of X is high, it may be difficult or even impossible to use ellipsoid approximations. Nonconvex bounding shapes could provide even better approximations, but the re-

I

2

quired number of parameters could easily become unmanageable, even if X = R2. For very particular problems, however, it may be possible to design a family of

shapes that is both manageable and tightly approximates the nondeterministic I-states. This leads to many interesting research issues.

Moment-based approximations Since the probabilistic I-states are functions, it seems natural to use function approximation methods to approximate prob. One possibility might be to use the first m coefficients of a Taylor series expansion. The derived I-space then becomes the space of possible Taylor coefficients. The quality of the approximation is improved as m is increased, but also the dimension of the derived I-space rises.

I

Since we are working with probability density functions, it is generally prefer- able to use moments as approximations instead of Taylor series coefficients or other generic function approximation methods. The first and second moments are the familiar mean and covariance, respectively. These are preferable over other approximations because the mean and covariance exactly represent the Gaussian density, which is the most basic and fundamental density in probability theory. Thus, approximating the probabilistic I-space with first and second moments is equivalent to assuming that the resulting probability densities are always Gaus-

sian. Such approximations are frequently made in practice because of the conve- nience of working with Gaussians. In general, higher order moments can be used to obtain higher quality approximations at the expense of more coefficients. Let

κmom : Iprob → Imom denote a moment-based I-map.

The same issues arise for κmom as for κapp. In most cases, κmom is not a sufficient I-map. The moments are computed in the same way as the conservative approx- imations. The update equations (11.57) and (11.58) are applied for probabilistic I-states; however, after each step, κmom is applied to the resulting probability density function. This traps the derived I-states in mom. The moments could be computed after each of (11.57) and (11.58) or after both of them have been applied (different results may be obtained). The later case may be more difficult to compute, depending on the application.

I

First consider using the mean (first moment) to represent some probabilistic I-state, p(x|η). Let xi denote the ith coordinate of x. The mean, x¯i, with respect

to xi is generally defined as

x¯i = r xi p(x|η)dx. (11.62)

X

I

This leads to the vector mean x¯ = (x¯1, . . . , x¯n). Suppose that we would like to construct mom using only the mean. Since there is no information about the covariance of the density, working with x¯ is very similar to estimating the state. The mean value serves as the estimate, and mom = X. This certainly helps to simplify the I-space, but there is no way to infer the amount of uncertainty associated with the I-state. Was the probability mass concentrated greatly around x¯, or was the density function very diffuse over X?

Using second moments helps to alleviate this problem. The covariance with respect to two variables, xi and xi, is

I

σi,j = r xi_x_j p(x|η)dx. (11.63)

X

Since σij = σji, the second moments can be organized into a symmetric covariance matrix,

σ1,_1 σ1,2 · · · σ1,n_

 

σ2,_1 σ2,2 · · · σ2,n_

Σ =  ... ... ... 

 

(11.64)

σn,_1 σ_n,_2 · · · σ_n,n

for which there are (n) + n unique elements, corresponding to every xi,i and every way to pair xi with xj for each distinct i and j such that 1 ≤ i, j ≤ n. This

2

implies that if first and second moments are used, then the dimension of mom is (n) + 2n. For some problems, it may turn out that all probabilistic I-states are indeed Gaussians. In this case, the mean and covariance exactly capture the probabilistic I-space. The I-map in this case is sufficient. This leads to a powerful tool called the Kalman filter, which is the subject of Section 11.6.1.

I

2

Higher quality approximations can be made by taking higher order moments.

The rth moment is defined as

xi_1 x_i_2 · · · x_ir p(x|η)dx, (11.65) in which i1, i2, . . ., ir are r integers chosen with replacement from 1, . . . , n .

rX

{ }

The moment-based approximation is very similar to the conservative approxi-

mations for nondeterministic uncertainty. The use of mean and covariance appears very similar to using ellipsoids for the nondeterministic case. The level sets of a Gaussian density are ellipsoids. These level sets generalize the notion of confidence intervals to confidence ellipsoids, which provides a close connection between the nondeterministic and probabilistic cases. The domain of a Gaussian density is

Rn, which is not bounded, contrary to the nondeterministic case. However, for a given confidence level, it can be approximated as a bounded set. For example,

an elliptical region can be computed in which 99.9% of the probability mass falls. In general, it may be possible to combine the idea of moments and bounding vol- umes to construct a derived I-space for the probabilistic case. This could yield the guaranteed correctness of plans while also taking probabilities into account. Unfortunately, this would once again increase the dimension of the derived I-space.

• • • 1. Derived I-spaces for continuous time

The continuous-time case is substantially more difficult, both to express and to compute in general forms. In many special cases, however, there are elegant ways to compute it. Some of these will be covered in Section 11.5 and Chapter 12. To help complete the I-space framework, some general expressions are given here. In general, I-maps and derived I-spaces can be constructed following the ideas of Section 11.2.1.

Since there are no discrete transition rules, the derived I-states cannot be expressed in terms of simple update rules. However, they can at least be expressed

as a function that indicates the state x(t) that will be obtained after u˜t and θ˜t

are applied from an initial state x(0). Often, this is obtained via some form

of integration (see Section 14.1), although this may not be explicitly given. In general, let Xt(ηt) ⊂ X denote a nondeterministic I-state at time t; this is the

replacement for Xk from the discrete-stage case. The initial condition is denoted as X0, as opposed to X1, which was used in the discrete-stage case.

More definitions are needed to precisely characterize Xt(ηt). Let θ˜t : [0, t) Θ denote the history of nature actions up to time t. Similarly, let ψ˜t : [0, t] Ψ

→

→

denote the history of nature sensing actions. Suppose that the initial condition is

X0 ⊂ X. The nondeterministic I-state is defined as

Xt(ηt) = {x ∈ X | ∃x′ ∈ X0, ∃θ˜t, and ∃ψ˜t such that

x = Φ(x′, u˜t, θ˜t) and ∀t′ ∈ [0, t], y(t′) = h(x(t′), ψ(t′))}.

(11.66)

In words, this means that a state x(t) lies in Xt(ηt) if and only if there exists an initial state x′ X0, a nature history θ˜t, and a nature sensing action history, ψ˜t

∈

such that the transition equation causes arrival at x(t) and the observation history

y˜t agrees with the sensor mapping over all time from 0 to t.

It is also possible to derive a probabilistic I-state, but this requires technical details from continuous-time stochastic processes and stochastic differential equa- tions. In some cases, the resulting expressions work out very nicely; however, it is difficult to formulate a general expression for the derived I-state because it depends on many technical assumptions regarding the behavior of the stochastic processes. For details on such systems, see [567].