What is an intuitive understanding for homotopy? At what stage is homotopy (I understand it as stretching or bending of path) in a planning algorithm? Is homotopy involved, for example, while implementing an algorithm like RRT?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Let me put homotopy into the context of planning algorithms
Suppose you want to get from point A to point B. Clearly, the easiest way is to traverse a straight line. But if there is an obstacle in the way of this straight line path, what should you do? If you want to obtain the "optimal" path (e.g. traversing the least total distance to the goal), you need only to travel in straight lines around the convex hull of the obstacle. This forms a non-smooth, piecewise linear path.
However, sometimes the "path of least traversal" is not the best path to take or may even be infeasible. For example, what if you don't have omni-directional wheels or it's just impossible to pivot in place (e.g. you have ackermann steering). Then, instead of traversing the straight line path along the convex hull, you need find some other optimal way to move around the obstacle. By using homotopy, you can continuously move away from the optimal straight line path (around the obstacle) to a smoother path around the obstacle that your robot can actually take.
More generally, homotopy allows you to relax the constraints of the original problem so that you can solve an easier problem that almost gives the best solution to the original problem. The key "trick" is to parameterize the problem so that in the limit as the parameter approaches zero, you get closer and closer to the original problem such that for any non-zero choice of the parameter, the "perturbed" problem is easier to solve. This is a very powerful tool for many problems, especially optimization problems where discreteness or non-smoothness make it very difficult to solve.