Automated Path-Planning for Asteroid Tours Using Hybrid Dynamic Programming–Beam Search

Designing multitarget trajectories such as asteroid tours can potentially increase the scientific return achieved by a mission. However, the large catalog of candidate bodies causes the path-planning combinatorial optimization problem to be NP-hard and thus computationally intensive. To tackle the complexity of these problems, this paper reviews the existing search methods, provides a thorough description of the search spaces in terms of graph theory, and delves into their inherent combinatorial and multimodal complexities. A novel deterministic approach based on the exploitation of the optimal substructure property and the application of dynamic programming combined with beam search is proposed to tackle path-planning problems where the number of targets to visit is the subject of the optimization itself. The automated algorithm is tested with the Global Trajectory Optimization Competition 4 (GTOC4) problem, and the results showcase that it is capable of obtaining thousands of high-ranking solutions for all launch dates considered.