Challenging new space missions and the increasing number of satellites both necessitate more autonomous spacecraft operations. Autonomy is often required when a satellite must react quickly such as when operating in proximity to another spacecraft or a small celestial body. Autonomy can also significantly reduce mission costs by limiting the use of human operators and ground-based resources. For deep space missions, autonomy is especially beneficial due to light time delay and limited facilities for tracking and communicating with distant spacecraft. However, autonomous operations require algorithms that are robust enough to operate dependably without human oversight and that are computationally efficient enough for onboard execution. Onboard computational resources are typically limited, especially for small spacecraft. To enable more autonomous operations in Earth orbit and deep space, new algorithms are developed in this dissertation to significantly increase the robustness and computational efficiency of spacecraft navigation and celestial body shape reconstruction. The proposed algorithms are then leveraged in the preliminary design of a novel multi-spacecraft mission concept to autonomously characterize an asteroid, including its gravity field, 3D shape, and rotational motion. Each contribution is validated numerically and compared to the state of the art. Some of the individual algorithms have also been validated through hardware in the loop simulation. The first contribution of this dissertation is new analytical process noise covariance models. The process noise covariance captures dynamics modeling deficiencies. Realistic modeling of this covariance is essential for accurate and reliable navigation through Kalman filtering, and it improves satellite conjunction analysis. In particular, analytical process noise models are desirable due to their computational efficiency. State noise compensation (SNC) is a common approach to process noise covariance modeling for spacecraft states that treats the process noise as zero-mean Gaussian white noise unmodeled accelerations. In order to address the lack of analytical SNC models in the literature, this work derives new analytical SNC process noise covariance models for absolute and relative spacecraft states parameterized using both Cartesian coordinates and orbital elements. The proposed process noise models can be accurately applied to closed orbits of arbitrary eccentricity and are guaranteed to produce a positive semi-definite process noise covariance, which is required for direct integration in a Kalman filter. These SNC models are then leveraged in the development of new algorithms to accurately estimate the process noise covariance of spacecraft states online in a Kalman filter for robust navigation. Although there are many state of the art process noise models, it may not be possible to accurately tune the model parameters if the dynamical environment is poorly known a priori, which is typical for small body missions. Furthermore, any a priori model tuning is invalidated when the process noise statistics change, which can occur due to changing space weather and spacecraft properties, a transition to a different orbit, or contingencies like a malfunctioning thruster. Alternatively, the process noise covariance can be estimated online through adaptive filtering techniques. This work takes a novel approach to adaptive filtering by fusing SNC with covariance matching adaptive filtering. The resulting algorithm is called adaptive SNC (ASNC). This framework is extended to unmodeled accelerations that are correlated in time, yielding another new algorithm called adaptive dynamic model compensation (ADMC). In contrast to many current adaptive filtering algorithms, ASNC and ADMC are well suited for onboard orbit determination because they are computationally efficient and do not rely on restrictive assumptions such as that of a linear time invariant system. Furthermore, the new techniques take into account the underlying spacecraft dynamics, easily incorporate a priori knowledge of the process noise, extrapolate over irregular measurement intervals, and guarantee a positive semi-definite process noise covariance without reliance on ad hoc methods. Next, a novel technique called exploiting triangular structure (ETS) is developed that can significantly reduce the computation time of an unscented Kalman filter (UKF) with no loss of accuracy. Although the more commonly used extended Kalman filter is more computationally efficient than the UKF, there is increased interest in the UKF for space applications because it more accurately captures the effects of system nonlinearities. The proposed ETS technique decreases UKF computation time by exploiting the lower triangular structure of the matrix square root to reduce dynamics and measurement model computations. This contribution facilitates onboard use of the UKF to improve estimation accuracy and robustness. Subsequently, a new approach is developed to reconstruct a 3D spherical harmonic shape model of a celestial body from a set of surface point position estimates. For deep space missions, a shape model of the target body is essential for both mission operations and science objectives. Although stereo-photoclinometry is commonly used to construct shape models of celestial bodies, it is not well suited to autonomous operations because it requires significant computational resources and human oversight. Moreover, the standard least squares approach used in literature to estimate a spherical harmonic shape model from a 3D point cloud often over fits the data, resulting in large, false protrusions in the reconstructed shape. In order to prevent over fitting and increase shape reconstruction accuracy, this work estimates the spherical harmonic shape coefficients through a regularized weighted least squares optimization. The novel regularization incorporates a priori empirical knowledge of the shape characteristics of celestial bodies. Techniques are also derived to compute the error covariance of the estimated shape coefficients, validate the shape reconstruction, update the shape coefficient estimates sequentially as more data become available, and perform ray tracing. Finally, the proposed algorithms are utilized to enable the preliminary design of a new autonomous mission concept for asteroid characterization called Autonomous Nanosatellite Swarming (ANS). There is considerable interest in asteroids as evidenced by many completed and ongoing missions. However, these missions heavily rely on human oversight and Earth-based resources such as the NASA Deep Space Network. Such an approach is not sustainable in the long term due to cost and oversubscribed Earth-based resources. In contrast, ANS comprises multiple small spacecraft that operate autonomously after a brief ground in the loop initialization. While in closed orbits about the target asteroid, the satellites record visible-light images of the body as well as intersatellite radio-frequency (RF) pseudorange and Doppler measurements. The images and RF measurements are fused in a novel algorithmic pipeline to simultaneously estimate the spacecraft states and relative clock offsets as well as the asteroid gravity field, 3D shape, and rotational motion. This pipeline includes a UKF, which is made significantly more computationally efficient and robust through the new ETS and ASNC techniques. Furthermore, the shape modeling contributions of this dissertation considerably improve the robustness and accuracy of the asteroid 3D shape reconstruction. Numerical simulations including the most relevant sources of uncertainty demonstrate that ANS provides accurate navigation and asteroid characterization without any a priori shape model and using only low size, weight, power, and cost avionics. Thus, ANS has the potential to increase the number of future asteroid missions by reducing mission operation costs and alleviating the burden on ground-based resources.