Robust motion planning is a complicated NP-hard problem that is considered as an essential characteristic of autonomy. This multi-objective problem considers the environmental disturbances and the possibilities for vehicles deployment during a mission. Although the recent advancements in embedded processors and sensor technology have opened new opportunities in underwater motion planning and facilitated AUVs to handle long-range operations, the inaccuracy of existing knowledge on uncertain spatiotemporal environment extends the complexity of motion planning problem. The class of underwater vehicles still have major challenges in dealing with uncertain ocean current variability that can strongly affect their motion, battery usage and mission duration. Current variations can also drift moving objects across the vehicle’s trajectory; therefore, the planned path may turn to be invalid or inefficient. Another challenge is that having a precise estimation of the behaviour of such an uncertain/dynamic environment in long-range operations, outside the vehicle’s sensor coverage, is usually unreliable and impractical. The robustness of a vehicle’s path planning to this strong environment variability is a crucial consideration in vehicle’s safety and mission performance. No polynomial time algorithm exists to solve an NP-hard problem of even moderate size. On the other hand, obtaining an absolute optimum solution is only applicable in fully known and certain environments. The modelled underwater environment in this chapter corresponds to a highly dynamic uncertain environment. To address the challenges associated with the path planning across a dynamic large-scale geographical area, which has been discussed precisely in Chaps. 3 and 4, this chapter aims to develop an online real-time motion planning strategy that enhances a vehicle’s ability to cope with variations of surroundings and render a reliable trajectory for vehicle’s transmission. The following objectives are introduced to furnish the mentioned above expectations: Avoid colliding static and uncertain mobile-motile objects;Avoid entering no-flying zones (e.g., coastal shallow areas and strong turbulence);Detecting anomalies and adapting/coping adverse current flow;Using accordant water current for saving energy;Prompt re-planning when an anomaly is detected; To address these objectives, this study employs meta-heuristics of DE, PSO, and BBO in the core of the proposed local motion planner and investigates their performance of guiding the vehicle from an initial loitering point towards the destination through a comprehensive simulation study. To emulate a realistic ocean environment, the operating field in this study is modelled to be matched with real-world concerns and possibilities.