Autonomous navigation of mobile robots represents a challenging task in the field of robotics. This is especially the case when accounting for generic, non-trivial robot dynamics, unstructured, possibly dynamic environments, realistic sensoric assumptions as well as the real-time computation requirements. The thesis addresses this navigation problem by means of Moving Horizon Trajectory Planning (MHTP), an approach that based on dynamic optimization, lying at the boundary between the topics of path planning and control. In such methods, the declarative formulation of the optimization problem is of great importance, as such formulations are succinct, expressive, posses theoretically provable characteristics and result in powerful behaviours. Moreover, they allow a safety analysis of the navigation approach, resulting in formulations of the navigation strategy that can guarantee that the agent will never collide with the environment. The discussed assumptions regarding the environment characteristics range from the simple known, static environment model up to environment models that assume non-trivial sensoric capabilities (allow sensing only in non-occluded surfaces that are within FOV and aximum sensing distances) as well as possessing arbitrary dynamic models with bounded uncertainty. Special care and focus is given also in the practical implementation of the discussed approaches. To this end, an efficient representation of the relaxed optimization problem is being presented, the minimal parametric representation. Non-trivial, PDE-induced metrics used to encode the cost-function of the optimization problem are analysed, aiming for a convexification of the formulation, with the practical benefits of removing local minima and thus guaranteeing that the agent is always reaching its navigation goal. Moreover, the implementation of such methods is addressed assuming an asynchronous system, presenting synchronization approaches and coupling strategies with the other modules within the system such as state observers and lower-level controllers. Simulated and real-world experimental results are presented on three different autonomous platforms (differential drive, independent wheel steering drive as well as a race car) operating in various environment types, illustrating the quality of the proposed approaches.