Path Planning Algorithm for South Pole Lunar Rover Missions

Les astromobiles lunaires auront un rôle crucial pour le retour de l’humanité sur la Lune. En effet, l’environnement lunaire est hostile, hasardeux et dangereux pour les humains. Ainsi, envoyer des astromobiles est une solution viable pour son exploration. avec le Programme d’accélération de l’exploration lunaire (PAEL), l’Agence spatiale canadienne (ASC) supporte l’initiative de retour sur la Lune en offrant divers contrats pour développer les technologies spatiales. Un livrable de ce programme est un astromobile lunaire qui sera lancé au pôle sud de la Lune. Cette zone particulière contient des éléments de réponse en lien avec la présence d’eau et avec la formation du système solaire. Ainsi, l’envoi d’un astromobile lunaire aura des retombées scientifiques importantes tout en minimisant le danger d’exposition aux humains. Malheureusement, la planification de trajectoire pour un astromobile lunaire est difficile et complexe. Tout d’abord, la topographie de la Lune n’est pas propice à la navigation. Elle contient des pentes abruptes qui font en sorte que certaines régions ne sont pas accessibles. De plus, le mouvement relatif entre la Lune et le Soleil, et entre la Lune et la Terre génèrent des zones qui varient dans le temps sur la Lune où l’astromobile n’aura pas accès au Soleil ou à la Terre. Un astromobile lunaire devrait toujours rester dans des zones où ce dernier est exposé au Soleil pour charger ses batteries et en contact avec la Terre pour la communication de commande. Pour ce faire, des données existantes sur la topographie lunaire fournies par la National Aeronautics and Space Administration (NASA) seront utilisées. L’ASC a généré, à partir de ces données, une banque d’information sur les obstacles dynamiques représentant l’état du Soleil et de la Terre par rapport à la Lune. En combinant cette dernière avec la topographie, un modèle adéquat de l’environnement lunaire est généré. Additionnellement, l’astromobile lunaire recevra de nombreux points de cheminement à explorer avec un temps limite. Par conséquent, le problème peut être décomposé en deux étapes: premièrement, l’ordre d’exploration doit être trouvé et deuxièmement, avec cet ordre, une trajectoire faisable et sans obstacle sera générée. Le travail de ce mémoire propose un outil de planification de trajectoire pour un astromobile allant au pôle sud de la Lune en résolvant précisément ce problème. L’outil contient deux composantes: le 2-step genetic algorithm et le Multi-Directional Rapidly-exploring Random Trees (MD-RRT*). La première composante est une variante de l’algorithme génétique qui retourne un ordre d’exploration pour les points de cheminement donnés en entrée. Cette dernière maximise la pertinence scientifique de la trajectoire potentielle et minimise sa distance parcourue. La deuxième composante reprend l’ordre et s’assure qu’une trajectoire faisable existe en tenant compte des obstacles statiques et dynamiques en lien avec la topographie lunaire, l’accès au Soleil et l’accès à la Terre. Puisqu’il n’y a pas de comparatifs disponibles actuellement pour l’outil de planification, le meilleur moyen de valider ses résultats est de comparer avec des trajectoires générées manuellement par des opérateurs de l’ASC. Ces opérateurs ont planifié au meilleur de leurs habiletés et leurs résultats sont utilisés pour évaluer l’outil. En général, l’outil peut trouver des trajectoires plus courtes en termes de distance et de temps de traversée beaucoup plus rapidement que les opérateurs. De plus, ce genre de comparaison a été effectué sur différents sites lunaires, ce qui démontre le potentiel de cet outil pour des missions futures. Malgré cela, plusieurs limitations et aspects de recherche futurs sont identifiés pour améliorer la robustesse de ce planificateur pour des missions d’astromobiles plus complexes et avancées.

Abstract

Lunar rovers will play a crucial role in the initiative of returning humans to the Moon. This is due to the harsh environmental conditions making it hazardous and dangerous for humans. Thus, sending rovers is a viable solution for exploration purposes. Following the Lunar Exploration Accelerator Program (LEAP), Canadian Space Agency (CSA) is supporting the return of humanity by giving out various space contracts for developing spatial technologies. One deliverable of the LEAP is a lunar rover that will go on the South Pole of the Moon. This particular area contains key answer elements about the presence of water and the history of the formation of the solar system. Therefore, sending a rover there will have important scientific relevance while minimizing human exposure. Unfortunately, lunar path planning for a rover is complex and no easy feat. Firstly, the topography of the Moon is not exactly "navigation-friendly". It contains steep slopes and rough edges which makes some areas impossible to access. On top of that, the relative motion of the Moon with respect to the Sun and with respect to Earth creates areas that vary through time on the Moon where there is no access to the Sun or the Earth respectively. A lunar rover should always stay in zones where it can have exposure to sunlight for charging and have contact with our planet for communication purposes. To do so, existing lunar topography datasets provided by NASA will be used. CSA processed those datasets to generate dynamic obstacle information. By combining both, an adequate lunar environment model is created. Furthermore, the lunar rover will receive multiple waypoints to explore given a certain time limit. Thus, the problem becomes two fold: first, the order of exploration needs to be decided, and second, given the order, a feasible obstacle-free path will be generated. This work proposes a path planner tool for a lunar rover going to the South Pole of the Moon by solving precisely this problem. This tool has two components: the 2-step genetic algorithm and the Multi-Directional Rapidly-exploring Random Trees (MD-RRT*). The first component is a variant of the Genetic Algorithm which proposes an order of exploration for the given waypoints. It focuses on maximizing the science score and minimizing the total distance traveled of the resulting trajectories. The second component then takes the order and ensures that a feasible trajectory can be found by taking into account all the static and dynamic obstacles (topography, access to the Sun and access to Earth). Since there are no tools available publicly at the time of writing this thesis that does something similar, the best way to compare is with manual operators from CSA. Indeed, they manually computed trajectories to the best of their abilities, and their results served as a benchmark for the tool. Overall, the latter can generate in a much shorter time trajectories that are shorter in terms of time and distance. Additionally, comparisons were done on different lunar sites, which goes to show that this tool holds promising potential for the future of space exploration. Despite that, several limitations and future research areas can be identified to ensure that this tool will be robust enough for more complex and advanced space rover missions.