6 ms·

In the area of Motion Planning (my own area of research), the most that can be said is that practical solutions exist for a tiny subset of cases, workable metho

In the area of Motion Planning (my own area of research), the most that can be said is that practical solutions exist for a tiny subset of cases, workable methods exist for a larger subset, expensive methods exist for a still larger subset, and everthing else might as well be impossible. - If you've got a low-dimensional problem, say 2D or 3D, without uncertainty (or at least bounded enough to pad obstacles and ignore it), search-based planners like A* and its derivatives work. Add uncertainty, complex non-holonomic constraints, limited horizons, etc and it becomes much harder. - If you've got a higher dimensional problem, say a 6/7-DoF arm, even multi-armed or humanoid robots, and you don't have uncertainty and dynamics (or can ignore them), sampling-based planners like RRTs and PRMs and their derivatives will often practically work. Actually useful guarantees of finding a solution or trying to find an optimal solution in useful time are still very much unsolved. - If your problem is basically open, and something approximating the "straight-line" from A to B is in the same local minima as a solution, trajectory optimization will work for a lot of problems. Motion planning is very much non-convex, though, so it's very easy to go from a problem solvable with optimization to a problem that isn't. - Planning with non-rigid objects, significant uncertainty (effectively continuous MDPs or POMDPs), and/or complex dynamics are all very unsolved problems. For motion planning problems in the gray area of "practically solvable", the art is figuring out how to simplify the problem as much as possible to make it tractable - highly optimized collision checking (generally speaking the performance bottelneck), combining search/sampling-based + optimization methods to get an initial solution from a global method and then refining it towards a local minima with optimization, or using special hardware or sensors to bound dynamics and uncertainty so it can be ignored.

alwahi 6y ago
sorry for sidetracking your answer but what actually does convex mean in the context of optimization. I remember looking at a book called convex optimization. Your statement that > Motion planning is very much non-convex, suggests to me that you are very much talking about the same thing. I understand convexity as in a shape. Why is convex good and concave bad in terms of optimization? I don't want you to dumb down the answer too much as I am a trained Mechanical Engineer but then my major isn't math. Hope you understand :)
- fxtentacle 6y ago
  Think of numerical optimization (e.g. gradient decent) as if you're letting a marble run down a hill. Only for some hill shapes can you be sure that the marble will reach the bottom. For other shapes, it'll get stuck on a small flat or in a small hole. Those would be called zero gradient or local minima failures. If your hill has a convex shape, then the marble will always roll up the bottom eventually.
  - cpgxiii 6y ago
    It's generally understood that motion planning for nontrivial problems is very non-convex, and it's basically impossible to predict if a given initial condition can be optimized to the global optima. Even simple convex 3D geometry in the environment projects to very complex non-convex geometry in the configuration space of the robot (the space you're performing optimization in).
    - fxtentacle 6y ago
      While that is true, the critical question is whether it will be locally smooth once you get close enough to your goal. Long-distance planning is generally bad, even for humans. Short-distance planning tends to work well with A-star
      - cpgxiii 6y ago
        The problem is that "distance" here is not necessarily in any intuitive or useful space, and knowing if you are close to the goal may be as hard as finding the full solution. You can be quite "close" to a solution in, say, Euclidean distance over joint angles, while constraints like joint limits and collisions mean that the actual solution path will be quite long.
        fxtentacle 6y ago
        I apologize, I hadn't thought about robot arms. All the planning stuff that I was involved with so far was either quadcopters or slowfliers or buggies, so only cases where the Euclidean norm is useful.
tuatoru 6y ago
But we don't need optimality or even analytic solutions for practical robot motion. Do we?
- cpgxiii 6y ago
  Of course we don't need full optimality for most problems, that's why RRTs and PRMs have proven useful on practical problems despite (RRTs especially) providing obviously suboptimal solutions. The problem is that really suboptimal solutions are bad (take too long, require too much energy, look scary to humans, etc) and we'd often like "OK-quality" solutions that require some sort of smoothing or optimization on top of an otherwise suboptimal solution. There is a class of problems where optimality is super-important, where feasibility isn't a binary yes/no and you must minimize some objective. For example, in surgical robotics, you'd like to plan a path that minimizes deformation of tissue, and that requires some sort of optimality. The perfect solution, of course, is something like A* that is complete and optimal, but that remains out of reach for higher-DoF problems.
  - tuatoru 6y ago
    Thanks for the exegesis!
snovv_crash 6y ago
I discovered when doing something in this space recently that even the simple case of doing optimal planning for a particle under Newtonian dynamics, with limits on eg. velocity and acceleration, is NP-Complete.
- deleted 6y ago
  [deleted]
MaximumYComb 6y ago
Is obtaining optimal solutions a requirement in motion planning for robotics?
- cpgxiii 6y ago
  Generally speaking, no. But there are classes of problems (ex surgical robotics) where solution optimality (or at least near-optimality) is essential to having a usable and safe system.
- froj 6y ago
  In control when you say optimal it usually just means that you solve your problem by defining a cost function which you try to minimize within constraints. For example in motion planning your cost could be distance traveled + time spent + energy used. This cost function would be written as a function of the system state (position, velocity, etc.) and control input (e.g. throttle). The control input that limits the cost function is what you're looking for. Optimal shouldn't be equated to the absolute best way, because it's always a question of definition.

alwahi 6y ago

sorry for sidetracking your answer but what actually does convex mean in the context of optimization. I remember looking at a book called convex optimization. Your statement that > Motion planning is very much non-convex, suggests to me that you are very much talking about the same thing. I understand convexity as in a shape. Why is convex good and concave bad in terms of optimization? I don't want you to dumb down the answer too much as I am a trained Mechanical Engineer but then my major isn't math. Hope you understand :)

fxtentacle 6y ago
Think of numerical optimization (e.g. gradient decent) as if you're letting a marble run down a hill. Only for some hill shapes can you be sure that the marble will reach the bottom. For other shapes, it'll get stuck on a small flat or in a small hole. Those would be called zero gradient or local minima failures. If your hill has a convex shape, then the marble will always roll up the bottom eventually.
- cpgxiii 6y ago
  It's generally understood that motion planning for nontrivial problems is very non-convex, and it's basically impossible to predict if a given initial condition can be optimized to the global optima. Even simple convex 3D geometry in the environment projects to very complex non-convex geometry in the configuration space of the robot (the space you're performing optimization in).
  - fxtentacle 6y ago
    While that is true, the critical question is whether it will be locally smooth once you get close enough to your goal. Long-distance planning is generally bad, even for humans. Short-distance planning tends to work well with A-star
    - cpgxiii 6y ago
      The problem is that "distance" here is not necessarily in any intuitive or useful space, and knowing if you are close to the goal may be as hard as finding the full solution. You can be quite "close" to a solution in, say, Euclidean distance over joint angles, while constraints like joint limits and collisions mean that the actual solution path will be quite long.
      - fxtentacle 6y ago
        I apologize, I hadn't thought about robot arms. All the planning stuff that I was involved with so far was either quadcopters or slowfliers or buggies, so only cases where the Euclidean norm is useful.

tuatoru 6y ago

But we don't need optimality or even analytic solutions for practical robot motion. Do we?

cpgxiii 6y ago
Of course we don't need full optimality for most problems, that's why RRTs and PRMs have proven useful on practical problems despite (RRTs especially) providing obviously suboptimal solutions. The problem is that really suboptimal solutions are bad (take too long, require too much energy, look scary to humans, etc) and we'd often like "OK-quality" solutions that require some sort of smoothing or optimization on top of an otherwise suboptimal solution. There is a class of problems where optimality is super-important, where feasibility isn't a binary yes/no and you must minimize some objective. For example, in surgical robotics, you'd like to plan a path that minimizes deformation of tissue, and that requires some sort of optimality. The perfect solution, of course, is something like A* that is complete and optimal, but that remains out of reach for higher-DoF problems.
- tuatoru 6y ago
  Thanks for the exegesis!

snovv_crash 6y ago

I discovered when doing something in this space recently that even the simple case of doing optimal planning for a particle under Newtonian dynamics, with limits on eg. velocity and acceleration, is NP-Complete.

deleted 6y ago
[deleted]

MaximumYComb 6y ago

Is obtaining optimal solutions a requirement in motion planning for robotics?

cpgxiii 6y ago
Generally speaking, no. But there are classes of problems (ex surgical robotics) where solution optimality (or at least near-optimality) is essential to having a usable and safe system.
froj 6y ago
In control when you say optimal it usually just means that you solve your problem by defining a cost function which you try to minimize within constraints. For example in motion planning your cost could be distance traveled + time spent + energy used. This cost function would be written as a function of the system state (position, velocity, etc.) and control input (e.g. throttle). The control input that limits the cost function is what you're looking for. Optimal shouldn't be equated to the absolute best way, because it's always a question of definition.