Improving the Efficiency of Rapidly-exploring Random Trees Using a Potential Function Planner

This paper presents an improvement of the standard randomized path planning algorithm, and uses this new approach to design reconfiguration maneuvers for large formations of spacecraft. A spacecraft reconfiguration maneuver is a difficult 6 DOF trajectory design problem with nonlinear attitude dynamics and non-convex constraints. In addition, some of the constraints couple the positions and attitudes of the spacecraft, which makes the problems high-dimensional. A key step in the overall design is to find a feasible trajectory using a randomized path planner, which typically requires a large fraction of the total computation time. This paper presents an improvement to the path planner that greatly reduces the solution time and enables the solution of very large problems. The primary modification is to change the function that connects two points, which is a key component of the randomized planner. The standard approach is to use a simple and fast function, which is changed here to one that is slower, but much more effective in linking two points. The new connection function finds a link between the points by minimizing a distance function to the target point with a feasible optimizer that accounts for the constraints. The examples presented demonstrate the significant speed improvement of the new planner and that the algorithm can solve problems with up to 16 spacecraft with numerous constraints.