Andrew Bylard
Stanford University
Unlocking the next generation of complex missions for autonomous spacecraft will require significant advances in robust motion planning. The aim of motion planning is to generate a sequence of control inputs which navigates a vehicle from a set of initial states to a specified goal region while minimizing cost (e.g. time and fuel) and avoiding obstacles. In future missions, unmanned spacecraft interacting with asteroids, comets, or distant moons or in proximity operations with debris or other spacecraft will need to plan feasible trajectories which satisfy the mission objectives with a guaranteed margin of safety. Therefore, motion planning systems must be equipped to navigate dynamic, cluttered environments while actively assessing risk by accounting for uncertainty. In addition, trajectories must be computed in real-time under the tight computational constraints of space-qualified hardware.
This research seeks to combine and build on recent developments in sampling-based motion planning algorithms and chance constrained optimal control to address these challenges. Chance constrained optimal control allows the user to explicitly set risk bounds, guaranteeing a desired probability of safety. By extending chance constraint optimization to sampling-based motion planning algorithms, we will have an algorithmic tool that enables the real-time computation of feasible paths with certifiable safety guarantees. Additionally, we will explore parallel computational strategies and heuristics relevant to spacecraft dynamics for fast computation of near-optimal and provably-safe trajectories.
The project builds on recent work by the Autonomous Systems Lab at Stanford University on sampling-based motion planning algorithms, including the Fast Marching Tree (FMT*) algorithm, which is designed to scale up to high-dimensional configuration spaces and to be efficient for kinodynamic constraints, both characteristic of spacecraft maneuvering.
The three proposed milestones of this research are as follows: (1) Extend chance constraints to sampling-based motion planning in the case of kinodynamic constraints and for time-varying obstacles, (2) Increase computational efficiency through parallelization of the algorithms and by applying heuristics specific to spacecraft maneuvering, (3) Validate the algorithms on an experimental testbed which replicates spacecraft motion.