Hybrid mixed-logical linear programming algorithm for collision-free optimal path planning

Methods to solve collision-free fuel-optimal path- and motion-planning problems for the reconfiguration of spacecraft formations are presented. First, the motion-planning problem is formulated as a parameter optimisation problem in which the spacecraft are represented by unrotated cubes and the trajectory followed by each spacecraft is discretised in time using cubic splines. In other words, the trajectory is parameterised by the spacecraft positions and velocities at a set of waypoints. Big-M relaxation is then used to formulate the parameter optimisation as a mixed-integer linear program (MILP) whose solution can be obtained using standard MILP solvers. Several concepts are subsequently introduced to obtain the solutions more efficiently and reliably. In particular, the concept of a sequential linear program is introduced in which a sequence of closely-related linear programs are solved until a better local minimum cannot be found without 'bifurcation', that is, without qualitatively changing the nature of the solution. An example of such a change is making one spacecraft move in front of an obstacle instead of behind it. To handle these bifurcation points efficiently, the concept of a feasibility MILP (FMILP) is introduced in which the following question is answered: is there a feasible solution whose objective function value is better than that of the current bifurcation point. This is achieved by simply appending a single linear constraint to the set of constraints. A bisection search can be applied to the cost using FMILPs to further speed the proposed method. The method was applied to two standard tests of motion planning with collision avoidance such as swapping (using minimum fuel and along the major diagonals) the positions of eight spacecraft located at the corners of a cube. Preliminary simulations show significant improvement in efficiency by at least one order of magnitude.