Examples for Continuous State Spaces
- Sensor Models
A remarkable variety of sensing models arises in applications that involve continu- ous state spaces. This section presents a catalog of different kinds of sensor models that is inspired mainly by robotics problems. The models are gathered together in one place to provide convenient reference. Some of them will be used in upcoming sections, and others are included to help in the understanding of I-spaces. For each sensor, there are usually two different versions, based on whether nature sensing actions are included.
Linear sensing models Developed mainly in control theory literature, linear sensing models are some of the most common and important. For all of the sensors in this family, assume that X = Y = Rn (nonsingular linear transformations allow the sensor space to effectively have lower dimension, if desired). The simplest case in this family is the identity sensor, in which y = x. In this case, the state is immediately known. If this sensor is available at every stage, then the I-space collapses to X by the I-map κsf : hist X.
I →
Now nature sensing actions can be used to corrupt this perfect state observation to obtain y = h(x, ψ) = x + ψ. Suppose that y is an estimate of x, the current
state, with error bounded by a constant r ∈ (0, ∞). This can be modeled by assigning for every x ∈ X, Ψ(x) as a closed ball of radius r, centered at the origin:
Ψ = {ψ ∈ Rn | IψI ≤ r}. (11.67)
Figure 11.11 illustrates the resulting nondeterministic sensing model. If the obser- vation y is received, then it is known that the true state lies within a ball in X of radius r, centered at y. This ball is the preimage, H(y), as defined in (11.11). To make the model probabilistic, a probability density function can be defined over Ψ. For example, it could be assumed that p(ψ) is a uniform density (although this model is not very realistic in many applications because there is a boundary at which the probability mass discontinuously jumps to zero).
X
- (b)
Figure 11.11: A simple sensing model in which the observation error is no more than r: (a) the nature sensing action space; (b) the preimage in X based on observation y.
A more typical probabilistic sensing model can be made by letting Ψ(x) = Rn and defining a probability density function over all of Rn. (Note that the nondeterministic version of this sensor is completely useless.) One of the easiest
choices to work with is the multivariate Gaussian probability density function,
1
p(ψ) =
e− ψ Σψ , (11.68)
2
1 T
/
(2π)n|Σ|
in which Σ is the covariance matrix (11.64), Σ is its determinant, and ψ Σψ is a quadratic form, which multiplies out to yield
T
| |
n n
ψT Σψ = - - σi,j ψiψj . (11.69)
i=1
j=1
i=1
j=1
If p(x) is a Gaussian and y is received, then p(y x) must also be Gaussian under this model. This will become very important in Section 11.6.1.
|
The sensing models presented so far can be generalized by applying linear transformations. For example, let C denote a nonsingular n n matrix with real- valued entries. If the sensor mapping is y = h(x) = Cx, then the state can still be determined immediately because the mapping y = Cx is bijective; each H(y)
×
contains a unique point of X. A linear transformation can also be formed on the nature sensing action. Let W denote an n × n matrix. The sensor mapping is
y = h(x) = Cx + W ψ. (11.70)
In general, C and W may even be singular, and a linear sensing model is still obtained. Suppose that W = 0. If C is singular, however, it is impossible to infer the state directly from a single sensor observation. This generally corresponds to
a projection from an n-dimensional state space to a subset of Y whose dimension is the rank of C. For example, if
C = 0 1 , (11.71)
（ ＼
0 0
then y = Cx yields y1 = x2 and y2 = 0. Only x2 of each (x1, x2) X can be observed because C has rank 1. Thus, for some special cases, singular matrices can measure some state variables while leaving others invisible. For a general sin- gular matrix C, the interpretation is that X is projected into some k-dimensional subspace by the sensor, in which k is the rank of C. If W is singular, this means that the effect of nature is limited. The degrees of freedom with which nature can distort the sensor observations is the rank of W . These concepts motivate the next set of sensor models.
∈
Simple projection sensors Several common sensor models can be defined by observing particular coordinates of X while leaving others invisible. This is the continuous version of the selective sensor from Example 11.4. Imagine, for exam- ple, a mobile robot that rolls in a 2D world, = R2, and is capable of rotation.
×
W
The state space (or configuration space) is X = R2 S1. For visualization pur-
poses, it may be helpful to imagine that the robot is very tiny, so that it can be
interpreted as a point, to avoid the complicated configuration space constructions of Section 4.3.7 Let p = (p1, p2) denote the coordinates of the point, and let s S1 denote its orientation. Thus, a state in R2 S1 is specified as (p1, p2, s) (rather than (x, y, θ), which may cause confusion with important spaces such as X, Y ,
×
∈
and Θ).
Suppose that the robot can estimate its position but does not know its orienta- tion. This leads to a position sensor defined as Y = R2, with y1 = p1 and y2 = p2 (also denoted as y = h(x) = p). The third state variable, s, of the state remains
unknown. Of course, any of the previously considered nature sensing action mod- els can be added. For example, nature might cause errors that are modeled with Gaussian probability densities.
A compass or orientation sensor can likewise be made by observing only the final state variable, s. In this case, Y = S1 and y = s. Nature sensing actions can be included. For example, the sensed orientation may be y, but it is only known that s y ǫ for some constant ǫ, which is the maximum sensor error. A Gaussian model cannot exactly be applied because its domain is unbounded and S1 is bounded. This can be fixed by truncating the Gaussian or by using a more
| − | ≤
appropriate distribution.
The position and orientation sensors generalize nicely to a 3D world, = R3. Recall from Section 4.2 that in this case the state space is X = SE(3), which can be represented as R3 RP3. A position sensor measures the first three coordinates, whereas an orientation sensor measures the last three coordinates. A physical
W
×
7This can also be handled, but it just adds unnecessary complication to the current discussion.
sensor that measures orientation in R3 is often called a gyroscope. These are usually based on the principle of precession, which means that they contain a spinning disc that is reluctant to change its orientation due to angular momentum. For the case of a linkage of bodies that are connected by revolute joints, a point in the
state space gives the angles between each pair of attached links. A joint encoder
is a sensor that yields one of these angles.
Dynamics of mechanical systems will not be considered until Part IV; how- ever, it is worth pointing out several sensors. In these problems, the state space will be expanded to include velocity parameters and possibly even acceleration parameters. In this case, a speedometer can sense a velocity vector or a scalar speed. Sensors even exist to measure angular velocity, which indicates the speed with which rotation occurs. Finally, an accelerometer can be used to sense accel- eration parameters. With any of these models, nature sensing actions can be used to account for measurement errors.
- (b) (c)
Figure 11.12: Boundary sensors indicate whether contact with the boundary has occurred. In the latter case, a proximity sensor may indicate whether the boundary is within a specified distance.
Boundary sensors If the state space has an interesting boundary, as in the case of free for motion planning problems, then many important boundary sensors can be formulated based on the detection of the boundary. Figure 11.12 shows several interesting cases on which sensors are based.
C
Suppose that the state space is a closed set with some well-defined boundary. To provide a connection to motion planning, assume that X = cl(Cfree), the closure
of free. A contact sensor determines whether the boundary is being contacted. In this case, Y = 0, 1 and h is defined as h(x) = 1 if x ∂X, and h(x) = 0 otherwise. These two cases are shown in Figures 11.12a and 11.12b, respectively. Using this sensor, there is no information regarding where along the boundary the contact may be occurring. In mobile robotics, it may be disastrous if the robot is in contact with obstacles. Instead, a proximity sensor is often used, which yields h(x) = 1 if the state or position is within some specified constant, r, of ∂X, and h(x) = 0 otherwise. This is shown in Figure 11.12.
{ } ∈
C
In robot manipulation, haptic interfaces, and other applications in which phys- ical interaction occurs between machines and the environment, a force sensor may be used. In addition to simply indicating contact, a force sensor can indicate the
magnitude and direction of the force. The robot model must be formulated so that it is possible to derive the anticipated force value from a given state.
Landmark sensors Many important sensing models can be defined in terms of landmarks. A landmark is a special point or region in the state space that can be detected in some way by the sensor. The measurements of the landmark can be used to make inferences about the current state. An ancient example is using stars to navigate on the ocean. Based on the location of the stars relative to a ship, its orientation can be inferred. You may have found landmarks useful for trying to find your way through an unfamiliar city. For example, mountains around the perimeter of Mexico City or the Eiffel Tower in Paris might be used to infer your heading. Even though the streets of Paris are very complicated, it might be possible to walk to the Eiffel Tower by walking toward it whenever it is visible. Such models are common in the competitive ratio framework for analyzing on-line algorithms [674].
Landmark
Figure 11.13: The most basic landmark sensor indicates only its direction.
In general, a set of states may serve as landmarks. A common model is to make xG a single landmark. In robotics applications, these landmarks may be instead considered as points in the world, . Generalizations from points to landmark regions are also possible. The ideas, here, however, will be kept simple to illustrate the concept. Following this presentation, you can imagine a wide variety of generalizations. Assume for all examples of landmarks that X = R2, and let a state be denoted by x = (x1, x2).
W
For the first examples, suppose there is only one landmark, l ∈ X, with coor-
dinates (l1, l2). A homing sensor is depicted in Figure 11.13 and yields values in Y = S1. The sensor mapping is h(x) = atan2(l1 x1, l2 x2), in which atan2 gives the angle in the proper quadrant.
− −
Another possibility is a Geiger counter sensor (radiation level), in which Y = [0, ) and h(x) = x l . In this case, only the distance to the landmark is reported, but there is no directional information.
∞ I − I
A contact sensor could also be combined with the landmark idea to yield a sensor called a pebble. This sensor reports 1 if the pebble is “touched”; otherwise, it reports 0. This idea can be generalized nicely to regions. Imagine that there is a landmark region, Xl X. If x Xl, then the landmark region detector reports 1; otherwise, it reports 0.
⊂ ∈
Many useful and interesting sensing models can be formulated by using the ideas explained so far with multiple landmarks. For example, using three homing
sensors that are not collinear, it is possible to reconstruct the exact state. Many interesting problems can be made by populating the state space with landmark regions and their associated detectors. In mobile robotics applications, this can be implemented by placing stationary cameras or other sensors in an environment. The sensors can indicate which cameras can currently view the robot. They might also provide the distance from each camera.
- (b)
Figure 11.14: (a) A mobile robot is dropped into an unknown environment. (b) Four sonars are used to measure distances to the walls.
Depth-mapping sensors In many robotics applications, the robot may not have a map of the obstacles in the world. In this case, sensing is used to both learn the environment and to determine its position and orientation within the environment. Suppose that a robot is dropped into an environment as shown in Figure 11.14a. For problems such as this, the state represents both the position of the robot and the obstacles themselves. This situation is explained in further detail in Section 12.3. Here, some sensor models for problems of this type are given. These are related to the boundary and proximity sensors of Figure 11.12, but they yield more information when the robot is not at the boundary.
One of the oldest sensors used in mobile robotics is an acoustic sonar, which emits a high-frequency sound wave in a specific direction and measures the time that it takes for the wave to reflect off a wall and return to the sonar (often the sonar serves as both a speaker and a microphone). Based on the speed of sound and the time of flight, the distance to the wall can be estimated. Sometimes, the wave never returns; this can be modeled with nature. Also, errors in the distance estimate can be modeled with nature. In general, the observation space Y for a single sonar is [0, ], in which indicates that the wave did not return. The interpretation of Y could be the time of flight, or it could already be transformed into estimated distance. If there are k sonars, each pointing in a different direction,
∞ ∞
then Y = [0, ∞]k, which indicates that one reading can be obtained for each sonar.
For example, Figure 11.14b shows four sonars and the distances that they can measure. Each observation therefore yields a point in R4.
(a) (b)
Figure 11.15: A range scanner or visibility sensor is like having a continuum of sonars, even with much higher accuracy. A distance value is provided for each
s ∈ S1.
Modern laser scanning technology enables very accurate distance measurements with very high angular density. For example, the SICK LMS-200 can obtain a distance measurement for at least every 1/2 degree and sweep the full 360 degrees at least 30 times a second. The measurement accuracy in an indoor environment is often on the order of a few millimeters. Imagine the limiting case, which is like
having a continuum of sonars, one for every angle in S1. This results in a sensor called a range scanner or visibility sensor, which provides a distance measurement for each s S1, as shown in Figure 11.15.
∈
A weaker sensor can be made by only indicating points in S1 at which dis-
continuities (or gaps) occur in the depth scan. Refer to this as a gap sensor; an
example is shown in Figure 11.16. It might even be the case that only the circular
Figure 11.16: A gap sensor indicates only the directions at which discontinuities in depth occur, instead of providing distance information.
ordering of these gaps is given around S1, without knowing the relative angles between them, or the distance to each gap. A planner based on this sensing model is presented in Section 12.3.4.
Odometry sensors A final category will be given, which provides interesting examples of history-based sensor mappings, as defined for discrete state spaces in Section 11.1.1. Mobile robots often have odometry sensors, which indicate how far the robot has traveled, based on the amount that the wheels have turned. Such measurements are often inaccurate because of wheel slippage, surface imper-
fections, and small modeling errors. For a given state history, x˜t, a sensor can
estimate the total distance traveled. For this model, Y = [0, ∞) and y = h(x˜t), in
which the argument, x˜t, to h is the entire state history up to time t. Another way to model odometry is to have a sensor indicate the estimated distance traveled since the last stage. This avoids the dependency on the entire history, but it may be harder to model the resulting errors in distance estimation.
In some literature (e.g., [350]) the action history, u˜k, is referred to as odometry. This interpretation is appropriate in some applications. For example, each action might correspond to turning the pedals one full revolution on a bicycle. The number of times the pedals have been turned could serve as an odometry reading. Since this information already appears in ηk, it is not modeled in this book as part of the sensing process. For the bicycle example, there might be an odometry sensor that bases its measurements on factors other than the pedal motions. It would be appropriate to model this as a history-based sensor.
Another kind of history-based sensor is to observe a wall clock that indicates how much time has passed since the initial stage. This, in combination with other information, such as the speed of the robot, could enable strong inferences to be made about the state.
- Simple Projection Examples
This section gives examples of I-spaces for which the sensor mapping is y = h(x) and h is a projection that reveals some of the state variables, while concealing others. The examples all involve continuous time, and the focus is mainly on the nondeterministic I-space ndet. It is assumed that there are no actions, which means that U = . Nature actions, Θ(x), however, will be allowed. Since there are no robot actions and no nature sensing actions, all of the uncertainty arises from the fact that h is a projection and the nature actions that affect the state transition equation are not known. This is a very important and interesting class of problems in itself. The examples can be further complicated by allowing some control from the action set, U; however, the purpose here is to illustrate I-space concepts. Therefore, it will not be necessary.
∅
I
Example 11.20 (Moving on a Sine Curve) Suppose that the state space is
Y X
Figure 11.17: The state space is the set of points traced out by a sine curve in R2.
Y X
Figure 11.18: The preimage, H(y), of an observation y is a countably infinite set of points along X.
the set of points that lie on the sine curve in the plane:
X = {(x1, x2) ∈ R2 | x2 = sin x1}. (11.72)
Let U = ∅, which results in no action history. The observation space is Y = [−1, 1] and the sensor mapping yields y = h(x) = x2, the height of the point on the sine curve, as shown in Figure 11.17.
The nature action space is Θ = {−1, 1}, in which −1 means to move at unit
speed in the x1 direction along the sine curve, and 1 means to move at unit speed in the x1 direction along the curve. Thus, for some nature action history θ˜t, a state trajectory x˜t that moves the point along the curve can be determined by
−
integration.
A history I-state takes the form ηt = (X0, y˜t), which includes the initial condi- tion X0 X and the observation history y˜t up to time t. The nondeterministic I-states are very interesting for this problem. For each observation y, the preimage H(y) is a countably infinite set of points that corresponds to the intersection of X with a horizontal line at height y, as shown in Figure 11.18.
⊆
The uncertainty for this problem is always characterized by the number of intersection points that might contain the true state. Suppose that X0 = X. In this case, there is no state trajectory that can reduce the amount of uncertainty. As the point moves along X, the height is always known because of the sensor, but the x1 coordinate can only be narrowed down to being any of the intersection points.
Suppose instead that X0 = x0 , in which x0 is some particular point along X. If y remains within (0, 1) over some any period of time starting at t = 0, then x(t) is known because the exact segment of the sine curve that contains the state is known. However, if the point reaches an extremum, which results in y = 0 or y = 1, then it is not known which way the point will travel. From this point, the
{ }
Y X
Figure 11.19: A bifurcation occurs when y = 1 or y = 1 is received. This irreversibly increases the amount of uncertainty in the state.
−
X
X
Y
h(x)
Y
h(y)
- (b)
Figure 11.20: (a) Imagine trying to infer the location of a point on a planar graph while observing only a single coordinate. (b) This simple example involves a point moving along a graph that has four edges. When the point is on the rightmost edge, there is no uncertainty; however, uncertainty exists when the point travels along the other edges.
sensor cannot disambiguate moving in the x1 direction from the x1 direction. Therefore, the uncertainty grows, as shown in Figure 11.19. After the observation y = 1 is obtained, there are two possibilities for the current state, depending on which action was taken by nature when y = 1; hence, the nondeterministic I-state contains two states. If the motion continues until y = 1, then there will be four states in the nondeterministic I-state. Unfortunately, the uncertainty can only
−
−
grow in this example. There is no way to use the sensor to reduce the size of the nondeterministic I-states. ．
The previous example can be generalized to observing a single coordinate of a point that moves around in a planar topological graph, as shown in Figure 11.20a. Most of the model remains the same as for Example 11.20, except that the state space is now a graph. The set of nature actions, Θ(x), needs to be extended so that if x is a vertex of the graph, then there is one input for each incident edge. These are the possible directions along which the point could move.
Example 11.21 (Observing a Point on a Graph) Consider the graph shown
Figure 11.21: Pieces of the nondeterministic I-space ndet are obtained by the different possible sets of edges on which the point may lie.
I
in Figure 11.20b, in which there are four edges.8 When the point moves on the interior of the rightmost edge of the graph, then the state can be inferred from the sensor. The set H(y) contains a single point on the rightmost edge. If the point moves in the interior of one of the other edges, then H(y) contains three points, one for each edge above y. This leads to seven possible cases for the nondeterministic I-state, as shown in Figure 11.21. Any subset of these edges may be possible for the nondeterministic I-state, except for the empty set.
The eight pieces of ndet depicted in Figure 11.21 are connected together in an interesting way. Suppose that the point is on the rightmost edge and moves left. After crossing the vertex, the I-state must be the case shown in the upper right of Figure 11.21, which indicates that the point could be on one of two edges. If the point travels right from one of the I-states of the left edges, then the I-state shown in the bottom right of Figure 11.20 is always reached; however, it is not necessarily possible to return to the same I-state on the left. Thus, in general, there are directional constraints on ndet. Also, note that from the I-state on the lower left of Figure 11.20, it is impossible to reach the I-state on the lower right by moving straight right. This is because it is known from the structure of the
I
I
graph that this is impossible. ．
The graph example can be generalized substantially to reflect a wide variety of problems that occur in robotics and other areas. For example, Figure 11.22 shows a polygon in which a point can move. Only one coordinate is observed, and the resulting nondeterministic I-space has layers similar to those obtained for Example 11.21. These ideas can be generalized to any dimension. Interesting models can be constructed using the simple projection sensors, such as a position sensor or compass, from Section 11.5.1. In Section 12.4, such layers will appear in a pursuit-evasion game that uses visibility sensors to find moving targets.
8This example was significantly refined after a helpful discussion with Rob Ghrist.
Y h(x)
Figure 11.22: The graph can be generalized to a planar region, and layers in the nondeterministic I-space will once again be obtained.
(a) (b)
Figure 11.23: (a) It is always possible to determine whether the state trajectory went above or below the designated region. (b) Now the ability to determine whether the trajectory went above or below the hole depends on the particular observations. In some cases, it may not be possible.
- Examples with Nature Sensing Actions
This section illustrates the effect of nature sensing actions, but only for the nonde- terministic case. General methods for computing probabilistic I-states are covered in Section 11.6.
Example 11.22 (Above or Below Disc?) This example involves continuous time. Suppose that the task is to gather information and determine whether the state trajectory travels above or below some designated region of the state space, as shown in Figure 11.23.
Let X = R2. Motions are generated by integrating the velocity (x˙ , y˙), which is expressed as x˙ = cos(u(t) + θ(t)) and y˙ = sin(u(t) + θ(t)). For simplicity, assume
u(t) = 0 is applied for all time, which is a command to move right. The nature action θ(t) ∈ Θ = [−π/4, π/4] interferes with the outcome. The robot tries to
make progress by moving in the positive x1 direction; however, the interference of nature makes it difficult to predict the x2 direction. Without nature, there
x
Figure 11.24: Nature interferes with the commanded direction, so that the true state could be anywhere within a circular section.
should be no change in the x2 coordinate; however, with nature, the error in the x2 direction could be as much as t, after t seconds have passed. Figure 11.24 illustrates the possible resulting motions.
Sensor observations will be made that alleviate the growing cone of uncertainty; use the sensing model from Figure 11.11, and suppose that the measurement error r is 1. Suppose there is a disc in R2 of radius larger than 1, as shown in Figure
- a. Since the true state is never further than 1 from the measured state, it
is always possible to determine whether the state passed above or below the disc. Multiple possible observation histories are shown in Figure 11.23a. The observa- tion history need not even be continuous, but it is drawn that way for convenience. For a disc with radius less than 1, there may exist some observation histories for which it is impossible to determine whether the true state traveled above or below the disc; see Figure 11.23b. For other observation histories, it may still be possible to make the determination; for example, from the uppermost trajectory shown in
Figure 11.23b it is known for certain that the true state traveled above the disc. ．
Example 11.23 (A Simple Mobile Robot Model) In this example, suppose that a robot is modeled as a point that moves in X = R2. The sensing model is the same as in Example 11.22, except that discrete stages are used instead of
continuous time. It can be imagined that each stage represents a constant interval of time (e.g., 1 second).
To control the robot, a motion command is given in the form of an action
uk ∈ U = S1. Nature interferes with the motions in two ways: 1) The robot
tries to travel some distance d, but there is some error ǫd > 0, for which the true distance traveled, d′, is known satisfy d′ d < ǫd; and 2) the robot tries to move in a direction u, but there is some error, ǫu > 0, for which the true direction u′ is known to satisfy u u′ < ǫu. These two independent errors can be modeled by
| − |
| − |
defining a 2D nature action set, Θ(x). The transition equation is then defined so that the forward projection F(x, u) is as shown in Figure 11.25.
Some nondeterministic I-states will now be constructed. Suppose that the
F (x, u)
Figure 11.25: A simple mobile robot motion model in which the sensing model is as given in Figure 11.11 and then nature interferes with commanded motions to yield an uncertainty region that is a circular ring.
H(_y_2)
_y_2
X_2(η1, u_1)
X_2(η_2)
X_2(η2) _X_2(η2, u_2)
- (b) (c)
Figure 11.26: (a) Combining information from X2(η1, u1) and the observation y2;
- the intersection must be taken between X2(η1, u1) and H(y2). (c) The action
u2 leads to a complicated nondeterministic I-state that is the union of F(x2, u2) over all x2 ∈ X2(η2).
initial state x1 is known, and history I-states take the form
ηk = (x1, u1, . . . , uk−1, y1, . . . , yk). (11.73)
The first sensor observation, y1, is useless because the initial state is known. Equa- tion (11.29) is applied to yield H(y1) x1 = x1 . Suppose that the action u1 = 0 is applied, indicating that the robot should move horizontally to the right. Equa- tion (11.30) is applied to yield X2(η1, u1), which looks identical to the F(x, u) shown in Figure 11.25. Suppose that an observation y2 is received as shown in Figure 11.26a. Using this, X2(η2) is computed by taking the intersection of H(y2) and X2(η1, u1), as shown in Figure 11.26b.
∩{ } { }
The next step is considerably more complicated. Suppose that u2 = 0 and that (11.30) is applied to compute X3(η2, u2) from X2(η2). The shape shown in Figure 11.26c is obtained by taking the union of F(x2, u2) for all possible x2 X2(η2). The resulting shape is composed of circular arcs and straight line segments (see Exercise 13). Once y3 is obtained, an intersection is taken once again to yield
∈
X3(η3) = X3(η2, u2) ∩H(y3), as shown in Figure 11.27. The process repeats in the
_u_3)
H(_y_3)
X_3(η_3)
- (b)
Figure 11.27: After the sensor observation, y3, the intersection must be taken between X3(η2, u2) and H(y3).
same way for the desired number of stages. The complexity of the region in Figure 11.26c provides motivation for the approximation methods of Section 11.4.3. For example, the nondeterministic I-states could be nicely approximated by ellipsoidal
regions. ．
11.5.4 Gaining Information Without Sensors
For some problems, it is remarkable that uncertainty may be reduced without even using sensors. Recall Example 11.17. This is counterintuitive because it seems that information regarding the state can only be gained from sensing. It is possible, however, to also gain information from the knowledge that some actions have been executed and the effect that should have in terms of the state transitions. The example presented in this section is inspired by work on sensorless manipulation planning [321, 396], which is covered in more detail in Section 12.5.2. This topic underscores the advantages of reasoning in terms of an I-space, as opposed to requiring that accurate state estimates can be made.
Example 11.24 (Tray Tilting) The state space, X R2, indicates the position of a ball that rolls on a flat surface, as shown Figure 11.28. The ball is confined to roll within the polygonal region shown in the figure. It can be imagined that the ball rolls in a tray on which several barriers have been glued to confine its motion
⊂
(try this experiment at home!). If the tray is tilted, it is assumed that the ball rolls in a direction induced by gravity (in the same way that a ball rolls to the bottom of a pinball machine).
The tilt of the tray is considered as an action that can be chosen by the robot. It is assumed that the initial position of the ball (initial state) is unknown and there are no sensors that can be used to estimate the state. The task is to find some tilting motions that are guaranteed to place the ball in the position shown in Figure 11.28, regardless of its initial position.
Figure 11.28: A top view of a tray that must be tilted to roll the ball into the desired corner.
The problem could be modeled with continuous time, but this complicates the design. If the tray is tilted in a particular orientation, it is assumed that the ball rolls in a direction, possibly following the boundary, until it comes to rest. This can be considered as a discrete-stage transition: The ball is in some rest state, a tilt action is applied, and a then it enters another rest state. Thus, a discrete-stage state transition equation, xk+1 = f(xk, uk), is used.
To describe the tilting actions, we can formally pick directions for the upward normal vector to the tray from the upper half of S2; however, this can be reduced to a one-dimensional set because the steepness of the tilt is not important, as long
as the ball rolls to its new equilibrium state. Therefore, the set of actions can be considered as U = S1, in which a direction u S1 indicates the direction that the ball rolls due to gravity. Before any action is applied, it is assumed that the tray
∈
is initially level (its normal is parallel to the direction of gravity). In practice, one should be more careful and model the motion of the tray between a pair of actions; this is neglected here because the example is only for illustrative purposes. This extra level of detail could be achieved by introducing new state variables that indicate the orientation of the tray or by using continuous-time actions. In the latter case, the action is essentially providing the needed state information, which
means that the action function would have to be continuous. Here it is simply assumed that a sequence of actions from S1 is applied.
The initial condition is X1 = X and the history I-state is
ηk = (X1, u1, u2, . . . , uk−1). (11.74)
Since there are no observations, the path through the I-space is predictable. There- fore, a plan, π, is simply an action sequence, π = (u1, u2, . . . , uK ), for any desired K.
It is surprisingly simple to solve this task by reasoning in terms of nondeter- ministic I-states, each of which corresponds to a set of possible locations for the ball. A sequence of six actions, as shown in Figure 11.29, is sufficient to guarantee
1: down 2: down-left 3: down-right
4: up 5: up-left 6: down-left
Figure 11.29: A plan is shown that places the ball in the desired location using a sequence of six tilts, regardless of its initial position and in spite of the fact that there are no sensors. The thickened black lines and black dots indicate the possible locations for the ball: the nondeterministic I-states. Under each picture, the direction that the ball rolls due to the action is written.
that the ball will come to rest at the goal position, regardless of its initial position.
．