In the recent decade, we witnessed a remarkable proliferation of spacecraft orbiting around Earth and venturing farther into our Solar system. As the number of operated spacecraft increases, the complexity of managing multiple missions escalates, along with the associated costs. Deep space missions will require spacecraft to navigate through challenging trajectories with limited and delayed communications. This makes autonomy crucial for ensuring the success of these missions. Convex optimization has emerged as a promising technique for autonomous guidance and navigation algorithms thanks to its computational speed and convergence properties. Only recently convex optimization has been adopted to solve non-linear optimization problems thanks to the introduction of successive convex programming (SCVX) enabling its application to a wide range of astrodynamics problems. In this research, differential algebra techniques are applied to improve the performances of SCVX by introducing a novel state-dependent trust region that enhances the robustness and optimality of SCVX techniques. The application of SCVX is then successfully expanded to operations around small celestial bodies. Furthermore, to improve the targeting of periodic and quasi-periodic orbits a new methodology based on the representation of these trajectories with their Fourier series is introduced. As spacecraft trajectories are susceptible to various sources of errors, the covariance of the state is included in the optimal control problem to obtain covariance robust trajectories that enable the containing of the expansion of the uncertainties. At the same time, differential algebra is applied to include the effects of the measurements in the optimization process. Finally, a novel convex-based autonomous guidance and navigation algorithm based on high-order Taylor expansions is presented. The new guidance and navigation algorithm enables the exploration of different penalty functions for the estimation process. At the same time, using high-order polynomials allows for the improvement of the computational efficiency of the guidance and navigation algorithm.