The planar case

For purposes of illustration, suppose that $ {\cal C}= {\mathbb{R}}^2$. A configuration is expressed as $ q = (x,y) \in {\mathbb{R}}^2$, and a velocity is expressed as $ ({\dot x},{\dot y})$. Each $ ({\dot x},{\dot y})$ is an element of the tangent space $ T_q({\mathbb{R}}^2)$, which is a two-dimensional vector space at every $ (x,y)$. Think about the kinds of constraints that could be imposed. At each $ q \in {\mathbb{R}}^2$, restricting the set of velocities yields some set $ U(q) \subset T_q({\mathbb{R}}^2)$. The parametric and implicit representations will be alternative ways to express $ U(q)$ for all $ q \in {\mathbb{R}}^2$.

Here are some interesting, simple constraints. Each yields a definition of $ U(q)$ as the subset of $ T_q({\mathbb{R}}^2)$ that satisfies the constraints.

  1. $ {\dot x}> 0$ : In this case, imagine that you are paddling a boat on a swift river that flows in the positive $ x$ direction. You can obtain any velocity you like in the $ y$ direction, but you can never flow against the current. This means that all integral curves increase monotonically in $ x$ over time.
  2. $ {\dot x}\geq 0$ : This constraint allows you to stop moving in the $ x$ direction. A velocity perpendicular to the current can be obtained (for example, $ (0,1)$ causes motion with unit speed in the positive $ y$ direction).
  3. $ {\dot x}> 0$, $ {\dot y}> 0$ : Under this constraint, integral curves must monotonically increase in both $ x$ and $ y$.
  4. $ {\dot x}= 0$ : In the previous three examples, the set of allowable velocities remained two-dimensional. Under the constraint $ {\dot x}= 0$, the set of allowable velocities is only one-dimensional. All vectors of the form $ (0,{\dot y})$ for any $ {\dot y}
\in {\mathbb{R}}$ are allowed. This means that no motion in the $ x$ direction is allowed. Starting at any $ (x_0,y_0)$, the integral curves will be of the form $ (x_0,y(t))$ for all $ t \in [0,\infty)$, which confines each one to a vertical line.
  5. $ a {\dot x}+ b {\dot y}= 0$ : This constraint is qualitatively the same as the previous one. The difference is that now the motions can be restricted along any collection of parallel lines by choosing $ a$ and $ b$. For example, if $ a = b = 1$, then only diagonal motions are allowed.
  6. $ a {\dot x}+ b {\dot y}+ c = 0$ : This constraint is similar to the previous one, however the behavior is quite different because the integral curves do not coincide. An entire half plane is reached. It also impossible to stop becasue $ {\dot x}= {\dot y}= 0$ violates the constraint.
  7. $ {\dot x}^2 + {\dot y}^2 \leq 1$ : This constraint was used in Chapter 8. It has no effect on the existence of solutions to the feasible motion planning problem because motion in any direction is still allowed. The constraint only enforces a maximum speed.
  8. $ {\dot x}^2 + {\dot y}^2 \geq 1$ : This constraint allows motions in any direction and at any speed greater than $ 1$. It is impossible to stop or slow down below unit speed.
Many other constraints can be imagined, including some that define very complicated regions in $ {\mathbb{R}}^2$ for each $ U(q)$. Ignoring the fact that $ {\dot x}$ and $ {\dot y}$ represent derivatives, the geometric modeling concepts from Section 3.1 can even be used to define complicated constraints at each $ q$. In fact, the constraints expressed above in terms of $ {\dot x}$ and $ {\dot y}$ are simple examples of the semi-algebraic model, which was introduced in Section 3.1.2. Just replace $ x$ and $ y$ from that section by $ {\dot x}$ and $ {\dot y}$ here.

If at every $ q$ there exists some open set $ O$ such that $ (0,0) \in
O$ and $ O \subseteq U(q)$, then there is no effect on the existence of solutions to the feasible motion planning problem. Velocities in all directions are still allowed. This holds true for velocity constraints on any smooth manifold [924].

So far, the velocities have been constrained in the same way at every $ q \in {\mathbb{R}}^2$, which means that $ U(q)$ is the same for all $ q \in {\mathbb{R}}^2$. Constraints of this kind are of the form $ g({\dot x},{\dot y})
\bowtie 0$, in which $ \bowtie$ could be $ =$, $ <$, $ >$, $ \leq$, or $ \geq$, and $ g_i$ is a function from $ {\mathbb{R}}^2$ to $ {\mathbb{R}}$. Typically, the $ =$ relation drops the dimension of $ U(x)$ by one, and the others usually leave it unchanged.

Now consider the constraint $ {\dot x}= x$. This results in a different one-dimensional set, $ U(q)$, of allowable velocities at each $ q \in {\mathbb{R}}^2$. At each $ q = (x,y)$, the set of allowable velocities must be of the form $ (x,{\dot y})$ for any $ {\dot y}
\in {\mathbb{R}}$. This means that as $ x$ increases, the velocity in the $ x$ direction must increase proportionally. Starting at any positive $ x$ value, there is no way to travel to the $ y$-axis. However, starting on the $ y$-axis, the integral curves will always remain on it! Constraints of this kind can generally be expressed as $ g(x,y,{\dot x},{\dot y}) \bowtie 0$, which allows the dependency on $ x$ or $ y$.

Steven M LaValle 2012-04-20