Summary: The work described in this paper is motivated by the need to develop efficient and robust estimation filters with application to terrain-aided navigation of underwater robotic vehicles. One of the main problems addressed is the development of navigation particle filters that can deal with the scarcity of landmarks and the terrain ambiguity that characterize vast regions of the ocean floor. As a contribution to solve this problem, the paper proposes three novel particle filter algorithms and assesses their estimation efficiency and robustness to non-informative measurements using two well-known benchmarking tests. The performance of the new filters in these tests demonstrates their potential to solve a class of nonlinear problems that include, but are not limited to, the type of underwater navigation problem that motivated the present work. Our study concludes by examining the performance of the filters in terms of determining the position and velocity of an autonomous underwater vehicle in the presence of unknown ocean currents. When applied to terrain-aided navigation, the novel particle filter formulations formulations mitigate filter divergence issues frequently caused by terrain symmetries and are more robust than other well-known versions when used in scenarios with poor terrain information. The theoretical developments presented and the results obtained in simulations are validated using real data acquired during tests with an autonomous marine robot.