Tag Archives: reachability sets

Intelligent Exploration of Reachability Sets

Space mission trajectories require extensive and careful planning due to limited fuel budgets and the complexity of gravitational dynamics. For many applications, planners decompose the problem into smaller segments and solve each one using a simplified version of the dynamics. This works well for maneuvers such as gravity assists and in systems with dominant single bodies that can be approximated by point masses, but it fails in systems with highly irregular bodies. To automatically plan trajectories in these systems, one must model the full nonlinear dynamics, and do so ‘on the fly,’ in order to handle unpredictable effects due to orbit uncertainty and the complex nonlinear dynamics of gravitation. However, the full set of possible trajectories is infinite, and is often chaotic, meaning that the evolution of any two trajectories, no matter how close, will diverge exponentially in finite time. Exploration must then be done by looking ahead intelligently.

NASA - Pluto and Charon as seen by New Horizons. The Pluto-Charon system is a multi-body system with nonlinear dynamics.
NASA – Pluto and Charon as seen by New Horizons. The Pluto-Charon system is a multi-body system with nonlinear dynamics.

My colleagues and I developed the Reachable Set Explorer, an AI technique that randomly explores the space of possible maneuvers for a spacecraft for a finite time horizon. The set of simulated trajectories is subdivided into ‘interesting’ regions (where ‘interesting’ can be any metric of the user’s choice), which contribute a higher weight for the next round of random choices. The result is an approximate reachability set that is more precise and detailed around the more interesting regions. The cost of simulating each trajectory is the driving factor in time, so the explorer must find a good approximation using a fixed number of trajectories.

In our published research, ‘interesting’ trajectories are those that straddle the boundary between impacting a body and skimming the surface. Given the chaotic nature of gravitational systems in general, finding orbits that make multiple low passes over the various bodies while minimizing fuel expenditure can potentially produce highly useful data.

Conceptually, the RSE algorithm can be thought of as a mixture between mesh refinement algorithms and shooting methods for nonlinear control systems. Given a fixed number of trajectories to create an approximate mesh, the algorithm seeds the space of possible trajectories randomly with a small fraction of the desired total. A mesh is built using a Delaunay triangulation of the seeds. Using weighted random sampling, the algorithm picks simplices whose vertices have different fates with a higher likelihood, then inserts new trajectories randomly into the simplices, and rebuilds the mesh. This process continues until the total number of trajectories has been calculated. Our research explored the parameter space – how to seed, how to choose places to add new meshes (e.g. random sampling and placement is more likely to find hidden regions), and so on.

Exploring the reachability set randomly shows low detail on the boundaries and excessive exploration of impact zones (red and green) and escape zones (yellow). Blue indicates trajectory survival over a finite time horizon.
Exploring the reachability set randomly shows low detail on the boundaries and excessive exploration of impact zones (red and green) and escape zones (yellow). Blue indicates trajectory survival over a finite time horizon.
A mesh made by the RSE algorithm uses the same number of vertices, but better reveals the details of the boundary between impact and continuation.
A mesh made by the RSE algorithm uses the same number of vertices, but better reveals the details of the boundary between impact and continuation.
Zooming in on the spiral in the lower right of the full set reveals additional detail.
Zooming in on the spiral in the lower right of the full set reveals additional detail.

One of the interesting things to become visible through our explorations is the fractal nature of orbital mechanics. The best meshes concentrate points in areas where the trajectories take highly variable paths before terminating. In the plots shown here, these areas look like condensed colored zones – slight changes result in escape, impacting the green body, or the red body. Zooming in reveals more of the same, and I conjecture that one will se similar formations at arbitrary zoom levels – the key feature of a fractal. In chaotic systems, an infinite number of periodic trajectories exist, including orbits that visit one body X times, followed by another Y times, and so on.

My involvement in this research ended after the foundational stage. It has since been picked up by David Surovik, a fellow NSTRF fellow, under Dan Scheeres in the Celestial and Spaceflight Mechanics Laboratory.

Our published papers are below:

Intelligent Computation of Reachability Sets for Space Missions, IAAI, 2012

Download (PDF, 588KB)

Efficiently Locating Impact and Escape Scenarios in Spacecraft Reachability Sets, AIAA Astrodynamics Specialists, 2012

Download (PDF, 4.75MB)

Efficiently Evaluating Reachable Sets in the Circular Restricted 3-Body Problem, IEEE Transactions on Aerospace and Electronic Systems, 2014

Download (PDF, 6.21MB)