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 email address is being protected from spambots. You need JavaScript enabled to view it.. Refer to NPO-48415.


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? Sign up here.



NASA Tech Briefs Magazine

This article first appeared in the November, 2015 issue of NASA Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.