Algorithms for Collision Avoidant Formation Flying

A report discusses algorithms for realtime planning of translation paths of multiple spacecraft flying in formation. The algorithm takes account of requirements to avoid collisions while operating within resource constraints (e.g., not calling for an acceleration greater than maximum possible) and striving for optimality (e.g., completing a change of formation in minimum time or at minimum energy cost). The optimality/collision- avoidance problem is formulated as a parameter-optimization problem, in which the translation path of each spacecraft is parameterized by polynomial functions of time. It is shown that this parameterization is the key to the solution of the parameter-optimization problem in that it enables decoupling of the collision-avoidance and accelerationlimit constraints, thereby making it possible to solve the problem in two stages. In the first stage, one constructs feasible paths that satisfy only the collision-avoidance constraints subject to certain optimality criteria. It is shown that the acceleration- limit constraints can be imposed a posteriori to compute the required maneuver duration such that at least one acceleration component is saturated. This also enables construction of paths that require minimum time in the class of solutions being considered.