Exercises

  1. Consider the set $ X=\{1,2,3,4,5\}$. Let $ X$, $ \emptyset$, $ \{1,3\}$, $ \{1,2\}$, $ \{2,3\}$, $ \{1\}$, $ \{2\}$, and $ \{3\}$ be the collection of all subsets of $ X$ that are designated as open sets.
    1. Is $ X$ a topological space?
    2. Is it a topological space if $ \{1,2,3\}$ is added to the collection of open sets? Explain.
    3. What are the closed sets (assuming $ \{1,2,3\}$ is included as an open set)?
    4. Are any subsets of $ X$ neither open nor closed?

  2. Continuous functions for the strange topology:
    1. Give an example of a continuous function, $ f: X \rightarrow X$, for the strange topology in Example 4.4.
    2. Characterize the set of all possible continuous functions.

  3. For the letters of the Russian alphabet, A, B, V, G, D, E, Ë, Zh, Z, I, uI, K, L, M, N, O, P, R, S, T, U, F, H, Ts, Ch, Sh, Shch, , Y, , E1, Yu, Ya, determine which pairs are homeomorphic. Imagine each as a 1D subset of $ {\mathbb{R}}^2$ and draw them accordingly before solving the problem.

  4. Prove that homeomorphisms yield an equivalence relation on the collection of all topological spaces.

  5. What is the dimension of the C-space for a cylindrical rod that can translate and rotate in $ {\mathbb{R}}^3$? If the rod is rotated about its central axis, it is assumed that the rod's position and orientation are not changed in any detectable way. Express the C-space of the rod in terms of a Cartesian product of simpler spaces (such as $ {\mathbb{S}}^1$, $ {\mathbb{S}}^2$, $ {\mathbb{R}}^n$, $ P^2$, etc.). What is your reasoning?

  6. Let $ \tau_1 : [0,1] \rightarrow {\mathbb{R}}^2$ be a loop path that traverses the unit circle in the plane, defined as $ \tau_1(s) =
(\cos(2 \pi s), \sin(2 \pi s) )$. Let $ \tau_2 : [0,1] \rightarrow
{\mathbb{R}}^2$ be another loop path: $ \tau_1(s) = (-2 + 3 \cos(2 \pi s),
\frac{1}{2} \sin(2 \pi s) )$. This path traverses an ellipse that is centered at $ (-2,0)$. Show that $ \tau_1$ and $ \tau_2$ are homotopic (by constructing a continuous function with an additional parameter that ``morphs'' $ \tau_1$ into $ \tau_2$).

  7. Prove that homotopy yields an equivalence relation on the set of all paths from some $ x_1 \in X$ to some $ x_2
\in X$, in which $ x_1$ and $ x_2$ may be chosen arbitrarily.

  8. Determine the C-space for a spacecraft that can translate and rotate in a 2D Asteroids-style video game. The sides of the screen are identified. The top and bottom are also identified. There are no ``twists'' in the identifications.

  9. Repeat the derivation of $ H_A$ from Section 4.3.3, but instead consider Type VE contacts.

  10. Determine the C-space for a car that drives around on a huge sphere (such as the earth with no mountains or oceans). Assume the sphere is big enough so that its curvature may be neglected (e.g., the car rests flatly on the earth without wobbling). [Hint: It is not $ {\mathbb{S}}^2 \times {\mathbb{S}}^1$.]

  11. Suppose that $ {\cal A}$ and $ {\cal O}$ are each defined as equilateral triangles, with coordinates $ (0,0)$, $ (2,0)$, and $ (1,\sqrt{3})$. Determine the C-space obstacle. Specify the coordinates of all of its vertices and indicate the corresponding contact type for each edge.

  12. Show that (4.20) is a valid rotation matrix for all unit quaternions.

  13. Show that $ {\mathbb{F}}[x_1,\ldots, x_n]$, the set of polynomials over a field $ {\mathbb{F}}$ with variables $ x_1,\ldots, x_n$, is a group with respect to addition.

  14. Quaternions:
    1. Define a unit quaternion $ h_1$ that expresses a rotation of $ -\frac{\pi}{2}$ around the axis given by the vector $ [ \frac{1}{\sqrt
3} \;\; \frac{1}{\sqrt 3} \;\; \frac{1}{\sqrt 3} ]$.
    2. Define a unit quaternion $ h_2$ that expresses a rotation of $ \pi $ around the axis given by the vector $ [ 0 \;\; 1 \;\; 0 ]$.
    3. Suppose the rotation represented by $ h_1$ is performed, followed by the rotation represented by $ h_2$. This combination of rotations can be represented as a single rotation around an axis given by a vector. Find this axis and the angle of rotation about this axis.

  15. What topological space is contributed to the C-space by a spherical joint that achieves any orientation except the identity?

  16. Suppose five polyhedral bodies float freely in a 3D world. They are each capable of rotating and translating. If these are treated as ``one'' composite robot, what is the topology of the resulting C-space (assume that the bodies are not attached to each other)? What is its dimension?

  17. Suppose a goal region $ G \subseteq {\cal W}$ is defined in the C-space by requiring that the entire robot is contained in $ G$. For example, a car may have to be parked entirely within a space in a parking lot.
    1. Give a definition of $ {\cal C}_{goal}$ that is similar to (4.34) but pertains to containment of $ {\cal A}$ inside of $ G$.
    2. For the case in which $ {\cal A}$ and $ G$ are convex and polygonal, develop an algorithm for efficiently computing $ {\cal C}_{goal}$.

  18. Figure 4.29a shows the Möbius band defined by identification of sides of the unit square. Imagine that scissors are used to cut the band along the two dashed lines. Describe the resulting topological space. Is it a manifold? Explain.

    Figure 4.29: (a) What topological space is obtained after slicing the Möbius band? (b) Is a manifold obtained after tearing holes out of the plane?
    \begin{figure}\begin{center}
\begin{tabular}{ccc}
\psfig{file=figs/cutmobius.idr...
...s/cheese.idr,width=1.7in} \\
(a) & & (b)
\end{tabular}\end{center}
\end{figure}

  19. Consider Figure 4.29b, which shows the set of points in $ {\mathbb{R}}^2$ that are remaining after a closed disc of radius $ 1/4$ with center $ (x,y)$ is removed for every value of $ (x,y)$ such that $ x$ and $ y$ are both integers.
    1. Is the remaining set of points a manifold? Explain.
    2. Now remove discs of radius $ 1/2$ instead of $ 1/4$. Is a manifold obtained?
    3. Finally, remove disks of radius $ 2/3$. Is a manifold obtained?
  20. Show that the solution curves shown in Figure 4.26 correctly illustrate the variety given in (4.73).
  21. Find the number of faces of $ {\cal C}_{obs}$ for a cube and regular tetrahedron, assuming $ {\cal C}$ is $ SE(3)$. How many faces of each contact type are obtained?
  22. Following the analysis matrix subgroups from Section 4.2, determine the dimension of $ SO(4)$, the group of $ 4 \times 4$ rotation matrices. Can you characterize this topological space?

  23. Suppose that a kinematic chain of spherical joints is given. Show how to use (4.20) as the rotation part in each homogeneous transformation matrix, as opposed to using the DH parameterization. Explain why using (4.20) would be preferable for motion planning applications.

  24. Suppose that the constraint that $ c$ is held to position $ (10,10)$ is imposed on the mechanism shown in Figure 3.29. Using complex numbers to represent rotation, express this constraint using polynomial equations.

  25. The Tangle toy is made of $ 18$ pieces of macaroni-shaped joints that are attached together to form a loop. Each attachment between joints forms a revolute joint. Each link is a curved tube that extends around $ 1/4$ of a circle. What is the dimension of the variety that results from maintaining the loop? What is its configuration space (accounting for internal degrees of freedom), assuming the toy can be placed anywhere in $ {\mathbb{R}}^3$?


    Implementations

  26. Computing C-space obstacles:
    1. Implement the algorithm from Section 4.3.2 to construct a convex, polygonal C-space obstacle.
    2. Now allow the robot to rotate in the plane. For any convex robot and obstacle, compute the orientations at which the C-space obstacle fundamentally changes due to different Type EV and Type VE contacts becoming active.
    3. Animate the changing C-space obstacle by using the robot orientation as the time axis in the animation.
  27. Consider ``straight-line'' paths that start at the origin (lower left corner) of the manifolds shown in Figure 4.5 and leave at a particular angle, which is input to the program. The lines must respect identifications; thus, as the line hits the edge of the square, it may continue onward. Study the conditions under which the lines fill the entire space versus forming a finite pattern (i.e., a segment, stripes, or a tiling).

Steven M LaValle 2020-08-14