Quasi-random algorithms for real-time spacecraft motion planning and coordination

In this paper we address the problem of planning in real time the motion of one or more spacecraft, in the presence of a variety of constraints, including collision avoidance with static obstacles or other maneuvering spacecraft, and plume impingement avoidance. Such problems are very challenging from the computational point of view, and push the limits of currently-available planning algorithms. However, recent advances in the robotics field have provided a new class of algorithms, based on randomization, which provide computational tractability by relaxing the completeness requirement to probabilistic completeness. In this paper we apply to the spacecraft maneuvering problem a set of recently-developed quasi-random algorithms, which, combining optimal orbital maneuvers and deterministic sampling strategies, are able to provide extremely fast and efficient planners. Moreover, the proposed algorithms are able to guarantee the safety of the space system, that is, the satisfaction of collision and plume impingement avoidance constraints, even in the face of finite computation times (i.e., when the planner has to be pre-empted). Examples of orbital maneuvering close to large structures will illustrate the effectiveness of the methods, and a discussion of the results will conclude the paper. (C) 2003 Elsevier Science Ltd. All rights reserved.