Obstacle avoidance is a difficult problem due to the non-convex state constraints. Therefore, the feasible state space needs to be convexified, or split, into convex regions at which point the search for an optimal solution among those convex regions is done. Methods for obstacle avoidance include two mixed integer linear programming (MILP) methods (obstacle related method and path-related method) and a state-constraint convexification method.
For each member of the set of convex regions, i.e. the convex subproblem, this innovation uses custom-built optimization solvers that use the problem structure in order to find the fuel-optimal solution for the local subproblem. This approach is 100 times faster than the general solver. Additionally, branch-and-bound methods are relied upon in order to search through the set of convex regions for the one that leads to a global fuel-optimal solution. These methods include obstacle-related methods, where the constraints are solely defined by the sides of the obstacle; the path-related method, which utilizes the fact that the initial and final position and the direction of the motion are known from one step to another and combine that knowledge with the geometry of the obstacles; and the state-constraint convexification method, which applies the convexification on the state constraints (creates border planes) that, in case of the obstacle avoidance, are non-convex.
This study applies the custom solvers, developed at Stanford University, that greatly improve the speed of solution. The convex optimization solvers can be either standard or custom. Standard optimization solvers for each call need to perform the initialization of the problem from scratch, such as setting up the constraints, KKT (Karush–Kuhn–Tucker) conditions, etc. This is a relatively slow process, as the lack of speed becomes evident once there is a need for solving a large number of problem instances. However, if instances of the problem have the same problem structure, and thus belong to the same family of problems (i.e., same number of KKT conditions, etc.), this can be used to initialize the problem only once for all the subsequent problem instances. A C-based custom solver, which takes advantage of the problem structure, is applied on the obstacle avoidance problem. This greatly improved the speed of solving the convex subproblem instances, and thus the reconfiguration problem as a whole.
This work was done by Behçet Açıkmeşe and Milan Mandic of Caltech for NASA’s Jet Propulsion Laboratory. The software used in this innovation is available for commercial licensing. Please contact Dan Broderick at
This Brief includes a Technical Support Package (TSP).
Obstacle Avoidance Methods
(reference NPO48415) is currently available for download from the TSP library.
Don't have an account?
Overview
The document outlines research conducted by the Jet Propulsion Laboratory (JPL) aimed at enhancing formation reconfiguration guidance capabilities for spacecraft. This research is significant as it extends beyond current state-of-the-art methods, such as those developed by DARPA, and proposes optimal solutions for managing the formation of multiple spacecraft. The advancements could potentially double the observational and fuel efficiency compared to existing technologies.
The primary objective of the research is to develop an optimization-based methodology for fuel-optimal reconfiguration guidance of formation flying spacecraft. The first year of the project produced an analytic methodology for systematically optimizing the formation reconfiguration guidance problem and a ground algorithm capable of automatically generating reconfiguration trajectories for trade studies. In the second year, the focus shifted to maturing the ground algorithm and developing a prototype flight algorithm intended for onboard autonomous optimal guidance in simulation.
The research is particularly relevant for future formation flying missions, which require coordinated maneuvers to change the geometry of spacecraft formations. This capability is essential for missions involving large synthetic apertures, such as space telescopes, which cannot be realized as monolithic structures. The document emphasizes the need for algorithms that can automatically plan and execute safe reconfiguration maneuvers, as existing methods are time-consuming and not suitable for multiple spacecraft operating in proximity.
The significance of the results is underscored by the challenges posed by non-convex collision avoidance constraints, which have historically limited the number of spacecraft that could be managed effectively. The research introduces a Mixed-Integer Linear Programming (MILP) formulation and a Branch-and-Bound (B&B) method, enabling real-time onboard solutions for fuel-optimal formation reconfiguration guidance. This approach not only addresses the specific challenges of formation flying but also opens avenues for solving other real-time decision-making problems, enhancing the level of autonomous decision-making capabilities.
The document also acknowledges contributions from key individuals and references various publications related to the research. Overall, the advancements presented in this research position JPL to better support NASA missions and pursue further funding opportunities from organizations like DARPA and the Department of Defense, thereby reinforcing its leadership in the field of formation flying.
