Oceanids is a 4-year programme for the technological development of innovative Maritime Autonomous System (MAS) platforms and associated sensors that will include next generation robotic AUVs, sensors and networks to undertake ambitious, long-range, long-endurance deployments in extreme and hazardous environments, such as the deep ocean or under-ice environments. This paper describes the design of two new types of robotic AUVs, the Autosub 2000 Under-Ice and the Autosub Long Range 1500 vehicles that are being developed under the programme. Two key components of the AUVs are described, the autonomy framework and the navigational system, which relies on a newly developed terrain-aided navigation (TAN) system. At-sea results of the TAN are also reported as obtained during long duration operational deployments done in 2017.