The Path Not Taken...

Being my first blog post, I wanted to start of with a topic that was the very reason why I fell in love with robotics...

I also felt the need to be able to convey my research (or something I try to do in my spare time) a bit more effectively, hence this blogging format. A bit of embedded magic via Deepnote...

A lot of the concepts, ideas and algorithms have been inspired from Lavalle , Redrake and Boyd.

A brief introduction..

Wikipedia defines Motion Planning as shown below,

Although the above definition appears to be mostly accurate and straightforward, it’s important to clarify beforehand that the source (and destination) doesn’t necessarily have to be points in the real world (R² and R³). Motion planning can be performed in higher dimensions and for various spaces, such as the joint spaces in manipulators or belief spaces for SLAM.)

For this blog, I wanted to briefly discuss the different categories of algorithms used in motion planning and highlight their distinctions. As far as I understand, motion planners can be broadly categorized into four types. (Apologies for the Notes app writing.)

Sampling based planners

It's futile to talk about motion planning in higher dimensions without actually understanding configuration spaces.

Without entering into deep mathematical concepts, one could understand topological spaces in simple terms..

A set X is called a topological space if there is a collection of subsets of X called open sets for which the following axioms hold:

1. The union of any number of open sets is an open set.
2. The intersection of a finite number of open sets is an open set.
3. Both X and ∅ are open sets.

Think about the set R, of real numbers. It definitely contains subsets such that their union leads to an open set, and subsequently their intersection could also lead to an open set (take (1,2) U (1,4) as an example). And of course, X itself is open in the sense of being unbounded....

One could extend this branch and claim that X = Rⁿ for any integer n, leads to a topological space. Considering most of the practical applications work in these spaces, this is a useful idea to acknowledge.

A homeomorphism is a special type of mapping between two topological spaces.

Two spaces are homeomorphic if:
1. You can continuously deform one space into the other
2. You do not tear, glue, or create holes
3. The mapping works in both directions (it has a continuous inverse)

A commonly used example is the donut and coffee cup example...

Imagine the space of a 🍩 and another space of its close accomplice, ☕. Both have exactly one hole, and one could imagine stretching the donut till it forms a handle like a mug...so one isn't really creating nor gluing to make holes...

Contradictorily, take the example of a donut 🍩 and a sphere 🎾...they aren't homeomorphic because the 🎾 has no holes but the 🍩 does. One cannot create a hole without tearing....

This leads to the definition of manifolds..,

A topological space M ⊆R^m is a manifold if for every x ∈ M, an open set O ⊂ M exists such that: 1) x ∈ O, 2) O is homeomorphic to Rⁿ, and 3) n is fixed for all x ∈M.

The key idea to remember here is that for any manifold, on zooming into any point, the space in and around it must look like a simple euclidean space...

Take a look at the image below. The left space locally follows the rule mentioned earlier, resembling Rⁿ. However, the space at the tip of the two cones appears to be two cones intersecting, which technically cannot be flattened into a Rⁿ without tearing or merging operations. Therefore, it violates the rules of a manifold.

Lavalle also contains some interesting cases of 2D spaces with manifold violating spaces...

Note that a convenient way to generate new topological space is by taking their cartesian product, simply X × Y.

This leads us to discuss about some important manifolds, namely, R¹, R² and the S¹. R¹ is a simple space that could be understood by a line, R² by a plane and S¹ is where things get interesting. S¹ is the manifold of a circle, namely,

S¹ = {(x,y) ∈ R² | x² + y² = 1}

A common way one could represent this space is by parametrizing it using θ →(cos θ, sin θ). Run up θ from 0 to 2π and we complete our space..again, notice the open set definition.
 
Now comes a really interesting idea... what happens if we apply cartesian products for R² x S¹, we get a cylinder! But cylinders are not the only manifold possible.....

Lavalle once again lists a good chunk of famous 2D manifolds...

We can finally define a configuration space. If the robot has n degrees of freedom, the set of transformations is usually a manifold of dimension n. This manifold is called the configuration space of the robot, and its name is often shortened to C-space.

To be continued .....🙃


References

1. Steven M. LaValle, "Planning Algorithms", Cambridge University Press , 2006.
2. Russ Tedrake (2024). Robotic manipulation: Perception, planning, and control (MIT 6.421 course notes). Retrieved from http://manipulation.mit.edu
3. Stephen Boyd, & Lieven Vandenberghe (2004). Convex optimization. Cambridge University Press.