I am trying to run RRT algorithm for motion planning for a quadrotor. The quadrotor ends up sometimes in corners without reaching the goal. I realized from sources online, that it is due to local minimum occuring. I want to know what is it and why they occur and avoid the quadrotor getting stuck in corners.
Do effective methods exist to overcome local minima in smapling based motion planning algorithms?
Local minima exists, because the shape of the error mountain is unknown. What sampling based planners are doing, is to calculate the outcome of a certain point in the map. For the input value f(x,y)=z the resulting value z is determined. To get the global minimum of the error function not a single point but all possible values for (x,y) have to be calculated which is not possible on standard-hardware.
The answer to the second question (how to overcome local minima) is called knowledge based planning. That means, a sampling planner is combined with domain specific heuristics. In the case of the RRT planner, this can be done with motion primitives which are sampled. A motion primitive is some kind of abstract input value which helps to reduce the possible numbers of (x,y) values down to a small lexicon of meaningful actions like “move forward”, “stop” and “move left”.
Local Minima is a common problem encountered in sampling based planners. In such planners random points(x,y) are generated and are each evaluated by a function. The point generation being completely random there is a possibility that in some cases no points are generated near the global minimum and hence the algorithm converges near a local minimum.
I used GA for path planning and the mutation capability of GA solved this issue. you can see a more detailed explanation here.
