The project will research and develop high-performance motion planners for dynamic tensegrity structures, which can be used as robotic mobility and manipulation platforms for space exploration purposes. Tensegrity is an exciting principle for developing impact tolerant and lightweight planetary rovers, which can achieve arbitrary forms and locomotion gaits. They can effectively adapt to highly unstructured environments, such as the uneven terrains of planetary bodies, and result in more affordable missions due to the reduced payload. Despite their benefits, controlling tensegrity robots with traditional control methods is challenging due to high-dimensionality, dependence on non-linear dynamics and significant uncertainty. As a result, most existing solutions limit the reasoning of the underlying dynamics and provide only quasi-static paths. This project aims to provide new algorithmic, mathematical and software tools that overcome this challenge and provide dynamically feasible trajectories for purposeful long-term navigation of tensegrity robots in uneven terrain . The focus is on advancing the state-of-the-art when planning in belief space for high-dimensional robots with significant dynamics, especially when these dynamics arise from the presence of soft contacts between a tensegrity structure and a highly unstructured, uneven terrain. The objective is for computational efficiency as well as a way to formally argue about the robustness of the computed trajectories. The solutions will be evaluated first in physics-based simulation and then on real tensegrity platforms that are of interest to NASA.