Monte Carlo tree search for autonomous goal-oriented path planning around small bodies

Exploration missions towards small bodies have grown in popularity in recent years thanks to their invaluable contribution to our knowledge of the solar system, the possibility of exploiting them for material extraction and the interest in planetary protection from the asteroid impact hazard. However, the environment of small bodies is characterized by high perturbations and their initial knowledge before the spacecraft approach is limited to ground observations. For this reason, it would be optimal to develop autonomous techniques to plan and update trajectories directly onboard as new information about the body is discovered. This thesis aims to develop an algorithm that employs Monte Carlo Tree Search, a path planning approach popular in the robotic field, for goal-oriented path planning in the asteroid environment. In particular, Monte Carlo Tree Search is chosen due to its foresighted nature, meaning that it doesn't always choose the immediate best action in a greedy way but it plans in order to obtain the best cumulative reward in a receding horizon fashion. The problem is modeled as a Partially Observable Markov Decision Process, where the partial observability lies in the knowledge of the spacecraft state only by its mean and covariance, estimated through an Extended Kalman Filter. The reference trajectory has to balance the mapping of the asteroid, the completion of tasks related to the some features distributed along the surface and the maintaining of low uncertainty on the spacecraft state. Finally, the Monte Carlo Tree Search planning method is tested in a Monte Carlo analysis with 500 different initial conditions and the obtained score is confronted with a greedy approach, which instead always chooses the immediate best action, to demonstrate the superior performances of the proposed strategy. The chosen test case is an ellipsoidal model of asteroid 433 Eros divided into a triangular mesh, with features and landmarks distributed along the surface. The approach shows on average better results with respect to the greedy approach method both in terms of score obtained and number of failures, making it a promising solution for path planning in asteroid exploration. However it is characterized by an higher computational cost which is a major critical issue for autonomous guidance algorithms.

Le missioni di esplorazione verso piccoli corpi hanno acquisito popolarità negli ultimi anni grazie al loro prezioso contributo alla nostra conoscenza del sistema solare, alla possibilità di sfruttarli per l'estrazione di materiali e all'interesse per la protezione planetaria dal pericolo di impatto con gli asteroidi. Tuttavia l'ambiente dei piccoli corpi è caratterizzato da elevate perturbazioni e le conoscenze iniziali prima dell'avvicinamento delle sonde sono limitate alle osservazioni da terra. Per questo motivo, sarebbe ottimale sviluppare tecniche autonome per pianificare e aggiornare le traiettorie direttamente a bordo, man mano che nuove informazioni sul corpo vengono scoperte. Questa tesi mira a sviluppare un algoritmo che impiega la ricerca ad albero di Monte Carlo, un approccio di pianificazione di percorso molto diffuso nel campo della robotica, per la pianificazione di traiettorie orientate ad obiettivi nell'ambiente degli asteroidi. In particolare, la ricerca ad albero di Monte Carlo è stata scelta per la sua natura lungimirante, nel senso che non sceglie sempre l'azione immediatamente migliore in modo "avaro", ma pianifica in modo da ottenere la migliore ricompensa cumulativa in un orizzonte temporale recedente. Il problema è modellato come un processo decisionale di Markov parzialmente osservabile, dove la parziale osservabilità risiede nella conoscenza dello stato della sonda solo attraverso la sua media e la sua covarianza, stimate attraverso un filtro di Kalman esteso. La traiettoria di riferimento deve bilanciare la mappatura dell'asteroide, il completamento di alcuni compiti relativi a punti di interesse distribuiti lungo la superficie e il mantenimento di una bassa incertezza sullo stato stimato. Infine, il metodo di pianificazione di ricerca ad albero di Monte Carlo viene testato in un'analisi Monte Carlo con 500 diverse condizioni iniziali e il punteggio ottenuto viene confrontato con l'approccio "avaro", che sceglie invece sempre l'azione immediatamente migliore, per dimostrare le prestazioni superiori della strategia proposta. Il caso di test scelto è un modello ellissoidale dell'asteroide 433 Eros suddiviso in una maglia triangolare, con caratteristiche e punti di interesse distribuiti lungo la superficie. Questo approccio mostra risultati migliori in media rispetto all'approccio "avaro" sia in termini di punteggio ottenuto che nel numero di fallimenti, rendendolo una soluzione promettente per la pianificazione di traiettorie nell'esplorazione di asteroidi. Tuttavia è caratterizzato da un costo computazionale più elevato, che è una criticità importante per sistemi di guida autonomi.