With introduction of incremental sampling algorithms, like PRM and RRT planning in higher dimensional spaces in reasonable computation time has become possible though it is PSPACE-hard. But why is a quadrotor motion planning problem still difficult even with simplified quadrotor model?
I was solving a dynamic car problem with OMPL, which produced solution within 10s but I set a planning time of 100s for quadrotor, but it still does not find a solution.
The main problem with motion planning is the time-dimension. Not only that the UAV can move up, down, forward or backward, but the motion is also defined along the time-axis. A motion plan like "up, up, down" is fundamental different then "up, down, up". After few steps, the number of possibilities grows exponential.
Even on simple examples like quadrotor path planning, Sokoban or grasping objects there are more then one million solutions which build a complex RRT graph. For the planner it's unclear which of the RRT nodes are better then the others, so the planner has to evaluate all. On the one hand graph-search with PRM or A* is the most efficent way to find a solution (thats the reason why they are implemented in OMPL), on the other hand, graph-search can not prevent that one million or more nodes has to calculated.
How to speed up the process? The naive answer is to use faster hardware (multi-core-processing, cloud computing) but thats not the way it works (Moores law is over, and doubling of current performance is very hard for Intel or AMD). A better alternative is to use a concept which is called hybrid planning (combination of RRT with PDDL solver): A symbolic planner reduces the search-space, and RRT is used only for local planning. Or more in general: PDDL Solver determines the subgoals and RRT calculates the paths to the subgoals.
One thing you should consider is that the quadrotor is underactuated and has a strong dynamical coupling between translational and rotational dynamics. Hence not all arbitrary trajectories are feasible. You can think about an equivalent problem parallel parking, although the 2 problems are not strictly equivalent.
Based on how your handle that in you planner you might run in the problem described.
