Marine Autonomous Vehicles (MAVs) are integral to future marine research infrastructure. Driven by the UKRI Environmental Sustainability Strategy to achieve net-zero by 2040, these vehicles offer vastly improved carbon efficiency compared to conventional research vessels, making them increasingly prominent in data collection efforts. Consequently, the FMRI programme is driving a significant expansion of the national autonomous fleet. However, as the number of deployed MAVs grows, the manual planning of their missions becomes exponentially more complex. This process cannot scale effectively without the integration of advanced, automated decision-support tools.
A mixed integer linear programming (MILP) model optimises routing and deployment planning for large MAV fleets. The model accounts for numerous asset- and environment-specific operational constraints to ensure that every generated solution is practically feasible, with the primary objective of maximising the total volume of scientific data collected. The framework integrates pre-existing ship itineraries, allowing conventional vessels to be used for MAV battery swapping or as transit corridors.
The framework can also serve as a simulation tool: researchers can evaluate “what-if” scenarios, such as varying battery capacities or extending deployment periods, before physical deployment. To improve the explainability of these complex plans, textual and visual outputs derived from the model’s solutions highlight the most critical aspects of the overarching deployment strategy.
MAV Path and Mission Planning
Path planning is fundamental to MAV operations, and early work established route-planning techniques for underwater environments. Modern approaches address increasingly complex scenarios, including sampling-based, optimisation-based, bio-inspired, and geometric model search algorithms.
Mission planning for MAVs involves both high-level task allocation and low-level path planning, which is particularly challenging in dynamic ocean environments. Decision-support systems have combined multi-criteria analysis and fuzzy sets to address uncertainty in MAV operations. Other integrated algorithms address mission assignment and path planning in ocean current environments. Evolutionary algorithms have also shown promise for mission planning by decomposing the problem into vantage-point selection and path optimisation.
MAV Fleet Coordination
Historically, the literature has treated MAV deployments as isolated, small-scale scientific endeavours rather than integrated components of a broader maritime logistics network. Consequently, a significant gap remains: existing autonomous coordination models almost universally assume MAVs operate independently of conventional maritime infrastructure.
These models rarely account for ship support, such as mid-mission battery swaps or assisted transits. This omission stems from the traditional divide between micro-level robotic path planning and macro-scale maritime logistics.
The MILP model bridges these two fields by addressing this operational reality and reflecting the logistical demands of modern marine research.
Energy Constraints and Fleet Scalability
Battery management is the primary limiting factor for persistent MAV operations. Previous research has estimated runtime energy and optimised rendezvous strategies with stationary recharge stations. Other work has demonstrated the importance of battery and energy management through docking operations, developing real-time trajectory optimisation that minimises both mission time and energy expenditure while accounting for hydrodynamic effects.
Evolutionary algorithms and particle swarm methods can handle energy-aware task allocation, but they lack the rigorous mathematical guarantees of MILP for optimality. Prior research has also largely avoided exact MILP formulations for joint ship–MAV routing because of the exponential computational complexity introduced by combining continuous autonomous operations with discrete maritime vessel schedules.
Within next-generation, large-scale marine research infrastructure, the model provides a scalable solution that mirrors actual deployment constraints. It bridges the gap between theoretical multi-agent routing and applied maritime logistics, ensuring strict operational feasibility for hundreds of MAVs while explicitly incorporating moving support vessels.
Task Requirements
The problem has a set of task requirements, denoted by TR. Every single task maps a research station, rs, with an MAV type, vt, that can cover the task. These requirements are defined by the following characteristics:
- Earliest start time for the task.
- Latest time for finishing the task.
Ship Integration
The model can include a pre-existing ship itinerary, denoted by sh. The itinerary is made of different mooring or stationary locations, each characterised by a time window when the ship arrives and leaves that location.
Each MAV can be assigned to the ship via its waypoints in one of the following situations:
- Have a fully recharged battery: This occurs when the new battery will lead to better coverage of the remaining science missions. The minimum duration spent at the ship is defined by the model.
- Use the ship for transiting: The ship is generally faster and safer in challenging environmental conditions. MAVs can transit via the ship to reach their destinations faster when the proposed route would not allow them to arrive within the specified time window or would lead to a battery resource constraint.
Summary of Notations
The mathematical notations transition the conceptual problem formulation to the mixed-integer linear programming model. This reference is organised into three primary modules.
AUVs
MV: the set of all available MAVs, of any type.- The set of MAVs of type
vt. mv: a single MAV inMV.
Time Windows
- A single time window, starting at its defined beginning and ending at its defined conclusion.
Locations
RS: the set of all research stations.- The set of research stations to which MAVs of type
vtcan be assigned. BS: the set of all ports of mobilisation forMV.- The port of mobilisation for
mv. PL: the set of all ports of demobilisation forMV.- The port of demobilisation for
mv. - The ship location within a time window.
- The set of ship locations in each time window.
Routes
RT: the set of all routes available for MAV movements.- The set of ship routes where the ship is one of the route endpoints.
TR: the set of all task requirements to be completed.- The set of task requirements to be completed at research station
rsby MAVs of typevt. - A single task at
rsrequiring typevt. - The weight of the task requirement.
Model Input Parameters
- Average battery consumption per time unit when an MAV of type
vtis active. - Average battery consumption per time unit when an MAV of type
vtis idle. - Battery-level threshold for each MAV of type
vt.
Case Studies and Results
All four case studies are solved using SCIP, a non-commercial solver for mixed-integer programming and mixed-integer nonlinear programming.
Inputs and Outputs
The case studies are inspired by real-world science missions taken from the Marine Facilities Planning platform. The platform provides records of Ship time and Marine Equipment applications, as well as Autonomous Deployment forms, which provide the basis for the case studies.
Task Requirements
Autonomous Deployment forms contain the set of task requirements, the locations of mobilisation and demobilisation ports, pickup locations or rendezvous points, and the research stations. The form specifies the MAV type, the number of vehicles required, and the planned deployment and recovery dates.
Ship Itinerary
Ship time and Marine Equipment applications are used to build a ship itinerary that matches the task requirements and allows MAVs to be assigned to the ship to cover additional task requirements. As the model contains a single ship, these use cases focus on applications operated by the Royal Research Ship Sir David Attenborough.
AUVs and Their Types
The model considers the use and deployment of a fleet composed of Slocum Glider and Autosub Long Range 1500 (ALR1500) MAVs. These two vehicles were selected because their characteristics are available within the organisation and through other partners, supporting better route-cost estimations.
An MAV type is considered to be a combination of either the Slocum Glider or the ALR1500 with different sensor configurations.
Route Costs
Although the Autonomous Deployment forms provide the locations needed to solve each case study, they do not include route costs between origins and destinations. PolarRoute, an AI- and data-driven maritime route-planning software, is used to generate travel time and battery consumption for the entire set of routes, including ship routes.
Costs are generated for the Slocum Glider and ALR1500, as well as for generating ship itineraries in some case studies.
Discussion and Conclusions
A MILP model was developed for planning marine science missions using a fleet of MAVs. The model is expected to serve as a decision-support tool for marine operations teams generating complex plans as manual planning becomes increasingly expensive.
The model maximises the number of science tasks covered while optimising fleet and battery usage. Although ship resource constraints are not considered, each MAV can be assigned to the ship only if doing so improves science coverage.
Three case studies inspired by existing marine science missions are solved. Each differs in location, science requirements, ship integration, or fleet size. This diversification helps identify and highlight the different constraints represented by the model.
Overall, the model and case studies demonstrate that MILP-based planning can generate complex, multi-vehicle marine science plans that would be costly to produce manually, while remaining flexible enough to capture the diverse constraints and priorities of real marine operations.
The proposed extensions, including richer resource and multi-ship modelling, dynamic replanning driven by forecasts, and uncertainty-aware replanning, provide a path towards a decision-support tool capable of supporting marine science missions throughout their execution, as well as at the planning stage.
Declaration of AI-Assisted Tools in the Writing Process
During the writing of this paper, the authors used Grammarly for grammar checking and language editing. While using this tool, the authors reviewed the suggested changes to take full responsibility for the publication’s content.
Frequently Asked Questions
What is the primary objective of the MAV fleet scheduling model? The primary objective is to maximise the total volume of scientific data collected by increasing the number of science tasks covered.
Why is battery management important for MAV operations? Battery management is the primary limiting factor for persistent MAV operations and affects routing, task completion, and the need for ship-supported battery swaps.
How can ships support marine autonomous vehicles? Ships can provide fully recharged batteries or help MAVs transit through challenging conditions and reach destinations within required time windows.
Which MAV types are considered in the case studies? The model considers Slocum Glider and Autosub Long Range 1500 MAVs with different sensor configurations.