For two of the ideas below (you pick), do some reading and thinking. Then for each of those ideas, type about one single-spaced page answering the following questions:
What’s your understanding of the problem? Are there variants of the problem you can phrase that you think is more interesting, practical, or solvable? What are some approaches you can imagine using to attack one of the variants of the problem? What are potential obstacles to each approach, and what approaches do you think are most promising? What is an extremely simplified version of the problem that you might solve first, if you attacked this problem?
If you ask Google Maps for a path from Hanover to New York City, it might give you multiple paths. Why? I think the assumption is that different humans might have different objective functions (e.g. minimize time, minimize fuel use, minimize tolls) and Maps wants to give you a path that makes you happy, without being sure of your objective.
Path diversity is interesting and has been studied. Some of the approaches seem ad-hoc to me: a metric for diversity is proposed and then an algorithm is proposed. But why is diversity good? What metric is right?
It seems to me that diversity is most interesting when it is the solution to a problem (survival of the fittest, across an unknown measure of fitness), rather than something sought for itself. I hope you will not take the comment out of context – this is a comment about robot motion or design, not a system for ethical behavior.
For example, given a graph \(G\) (discrete for now) with vertices \(V\), and \(n\) cost functions each expressed as a set of (possibly infinite) edge weights, find a set of \(k\) paths that minimizes the worst-case cost over the cost functions.
There might be other better ways to phrase this problem, or you might be more interested in some other formulation of the path diversity problem. Any formulation that you can argue is useful and interesting is worth studying.
A roadmap like one generated by PRM has some advantages: it allows simple graph search to connect existing points, and might be fairly small if we don’t care too much about optimality (PRM* places many samples).
Is there a continuous equivalent of a graph that we might represent with less memory, and which would still give near-optimal paths?
Consider the example of a point robot in \(R^2\), with no obstacles and a Euclidean distance metric. Representing optimal paths with PRM* would require infinitely many samples if we don’t bound the motion, and many samples even if we bound the space. But we already know the answer and it is simple: the cost function is \(L_2\), Euclidean distance, and gradient descent gives straight-line path that are optimal.
Can we aproximate the graph itself (in \(R^2\) continouly) or the cost function (which takes four numbers, a start and a goal) using a continuous function? How do we discover this approximation given things we can compute over the space (local planner, or collisions)? Is it memory efficient? When we have the representation, how do we extract paths, and how computationally expensive is that?
I think this problem is best attacked in very simple example spaces (e.g. a point robot with some polygonal obstacles). Here’s a very short first attempt. I think the idea is ok but it’s very incomplete, and there might be much better approaches. I think machine learning approaches might have been tried for similar problems, and may be effective.
How can we design blocks that fit together in such a way as to be interlocked without relying on friction or glue?
A broader question: given a collection of very many rigid bodies, what is the free motion of the system? Can the system escape its current local region of configuration space (caging)? Can we design the system so it cannot?
I think the Puzzleflex paper below could be extended to 3D rigid bodies; the Sniffen thesis makes an approach, but we might also look at a simplified translation-only model.