Optimization of Non-Differentiable Travelling Salesman Problem for Space Trajectory Design with Non-branching Operation

Paper number

IAC-23,C1,7,10,x76496

Author

Prof. Liqiang Hou, Shanghai Jiaotong University, China

Coauthor

Prof. Arun Misra, McGill Univeristy, Canada

Coauthor

Prof. Shufan Wu, Shanghai Jiaotong University, China

Coauthor

Mr. Zilong Zhuang, McGill University, Canada

Year

2023

Abstract

A complex yet important design problem with mixed integer and graph-related optimization, the Travelling Salesman Problem (TSP) for space trajectory design, is considered and studied. The path planning problem associated with TSP is complicated by its mixed integer characteristics. The dimension of the sub-design spaces to be explored increases exponentially with the number of nodes to be visited. In the previous works, we reformulated the TSP into a continuous gradient optimziation using the Gaussian mapping technique, where an objective function of the accumulated differentiable travelling cost of the sequence is considered. This work further considers the path planning problem with the non-differentiable objective function beyond the differentiable Euclidean distance. 

Instead of the Gaussian mapping to measure the decision branching uncertainty impact, we further introduce the metric with a radial basis. The new design space consists of the expected value of the nodes conditioned on the preceding node and scale parameters of the radial basis function. A Markov process equation is used to describe the decision uncertainties, and the posterior of decision-making on the node is modelled and propagated to the next node to be visited. The non-differentiable TSP is then modelled as a parameter estimation problem. Finally, an equation for determining the new candidate with maximum likelihood is developed in the space expressed using a radial basis. No branch operation is implemented during the path planning.


With this method, the objective of the non-differential TSP is rewritten into a cost function with a quadratic form of accumulated log-likelihood, and a gradient-based optimizer is used to search the optimal sequence. The numerical simulation of the method to a classic TSP with 100 nodes shows promising results and could converge to a near-optimal solution in only dozens of iterations. Furthermore, the method is extended to space trajectory design of a TSP related to the orbital debris removal, whose objective function considers not only the fuel to rendezvous a set of debris, but also the size of each debris.

Abstract document

IAC-23,C1,7,10,x76496.brief.pdf

Manuscript document

IAC-23,C1,7,10,x76496.pdf (🔒 authorized access only).

To get the manuscript, please contact IAF Secretariat.