PaperlayerView exact revision on arXiv

Source-linked AI summary

Marine Autonomous Vehicle Fleet Scheduling to Maximise Scientific Impact

Mehdi El Krari, Jonathan Smith, Maria Fox

arXiv:2608.27271v1math.OCcs.RO

TL;DR

Growing MAV fleets make manual marine-mission planning increasingly complex, motivating an automated approach. The paper develops a constrained MILP model with ship integration, evaluates its planning capabilities, and uses it for simulation and explainable decision support. Its case studies show that the model generates complex multi-vehicle plans while supporting diverse operational constraints, although the evaluations assume static planning conditions and may leave some tasks incompletely covered.

  • Problem

    Growing autonomous fleets make manual routing and deployment planning increasingly complex for continuous marine data collection.

  • Method

    The paper formulates a MILP model that maximises science-task coverage while optimising fleet and battery usage under operational constraints.

  • Results

    The case studies demonstrate that MILP planning can generate complex, multi-vehicle marine science plans while flexibly representing diverse constraints and priorities.

  • Takeaways & Limitations

    The framework is intended as decision support for marine operations teams managing plans that are costly to produce manually.

  • Takeaways & Limitations

    The case studies assume static science requirements, environmental conditions, and route costs, leaving dynamic replanning as an extension.

Abstract

from arXiv · show

The marine science community increasingly relies on Marine Autonomous Vehicles (MAVs) to collect the critical environmental data required to understand global ocean systems. However, as these operations scale, manually routing and planning large autonomous fleets becomes exponentially complex and time-consuming. To address this, we propose a mixed-integer linear programming (MILP) model designed to automate and optimise MAV deployment schedules. The model accounts for strict operational constraints, including battery capacities and time windows for data collection, while aiming to maximise total data collection and minimise both the number of deployed vehicles and their energy consumption. A key novelty of this framework is integrating conventional ship itineraries, allowing MAVs to support vessels with mid-mission battery swapping or accelerated transit between waypoints. Computational experiments demonstrate that the model is highly scalable, solving routing problems for fleets of dozens of MAVs in seconds, and scaling to hundreds of vehicles in only a few minutes. Beyond operational scheduling, the framework serves as a robust simulation tool for evaluating 'what-if' scenarios and analysing the impact of varying parameters on deployment strategies. Finally, the solution generates a suite of visualisations designed to enhance explainability and support strategic decision-making for stakeholders.

1 Introduction

Marine science depends on continuous, high-fidelity ocean observations, while expanding MAV fleets make manual mission planning increasingly complex. The paper proposes a MILP framework to optimise feasible fleet deployment and integrate ship support.

  • Motivation: Continuous high-fidelity measurements support marine protection, climate-change analysis, and higher-resolution ocean models.The motivating examples include temperature, salinity, and conductivity measurements, with particular urgency in polar regions.
  • Operational challenge: Expanding MAV fleets make manual mission routing and planning exponentially more complex.
  • Proposed framework: The proposed MILP model optimises large-fleet routing and deployment while enforcing asset- and environment-specific operational constraints.Its primary objective is maximising the total volume of scientific data collected.
  • Ship integration: Pre-existing ship itineraries can support MAV battery swapping or provide transit corridors.
  • Decision support: The framework supports what-if simulation and produces textual and visual outputs to improve plan explainability.Researchers can vary parameters such as battery capacities or deployment periods before physical deployment.
  • Paper structure: The paper presents related literature, formalises the problem, introduces the mathematical model, evaluates three use cases, and concludes with findings and future work.

2 Introduction

The paper motivates scalable MAV planning through the need for continuous marine observations and the growing complexity of manual fleet operations. It presents a constrained MILP framework with ship integration, simulation capabilities, and explainable outputs.

  • Motivation: Continuous high-fidelity marine data underpin environmental protection, climate-change analysis, and higher-resolution ocean models.The need is especially urgent in sensitive environments such as polar regions.
  • Operational challenge: MAVs provide improved carbon efficiency compared with conventional research vessels, but expanding fleets make manual mission planning exponentially more complex.
  • Proposed framework: The proposed MILP model optimises large-fleet routing and deployment while targeting feasible solutions and maximising collected scientific data.
  • Ship integration: The framework integrates pre-existing ship itineraries for MAV battery swapping or transit corridors.
  • Decision support: Textual and visual outputs highlight critical aspects of deployment strategies to improve explainability.The framework also supports what-if analysis before physical deployment.
  • Paper structure: The paper reviews literature, defines the problem, presents the mathematical model, evaluates three use cases, and discusses conclusions and future work.

3 Literature Review

Prior work addresses MAV navigation, energy management, and maritime optimisation, but commonly separates autonomous fleets from conventional maritime infrastructure. This paper positions a scalable MILP model as a bridge between fleet routing and ship-supported logistics.

  • MAV coordination: MAV operations face limited communication, dynamic currents, strict energy constraints, and unresolved fleet-level coordination challenges.
  • Path planning: Path-planning research spans sampling-based, optimisation-based, bio-inspired, and geometric model-search methods.
  • Path planning: Optimisation-based studies address efficient routing, complex underwater conditions, and uncertain flow fields.
  • Mission planning: Mission-planning research combines task allocation and path planning through decision-support, integrated algorithms, and evolutionary approaches.
  • MAV coordination: Early and recent studies increasingly address multi-MAV coordination, but much prior work treats deployments as isolated small-scale endeavours.
  • Maritime logistics: Maritime logistics research demonstrates MILP applications for fleet management and routing under complex operational constraints.
  • Research gap: Existing MAV MILP studies address energy-constrained path planning or adaptive sampling but generally neglect fleet-scale optimisation and joint ship-MAV planning.
  • Energy constraints: Battery management is a primary limiting factor for persistent MAV operations, motivating runtime, rendezvous, docking, and energy-aware optimisation studies.

4 Problem Formulation

The problem formulation represents MAVs, tasks, routes, battery states, and ship itineraries within a constrained planning model. It accommodates task windows, energy variation, and ship-enabled battery replacement or transit.

  • 4 Problem Formulation: The framework jointly routes autonomous fleets and scheduled support vessels for battery swapping and accelerated transit.
  • 4 Problem Formulation: The problem defines research stations, MAVs, and MAV types whose capabilities determine which task requirements they can perform.
  • 4 Problem Formulation: Assigned MAVs must depart from their mobilisation bases and recover at pickup locations within specified deployment and recovery windows.
  • 4.1 Task Requirements: Each task requirement maps a research station to a compatible MAV type and specifies required vehicles, uninterrupted duration, start and finish limits, and scientific weight.Scientific weights prioritise missions under resource and vessel-availability constraints.
  • 4.2 Battery constraints: Battery levels vary over time from deployment to recovery, with consumption depending on MAV type and environmental conditions.
  • 4.2 Battery constraints: Each MAV type specifies separate average consumption rates for active and idle states, plus a minimum battery threshold.
  • 4.2 Battery constraints: Location-specific energy factors adjust battery consumption for research stations and route segments to reflect environmental variation such as currents.
  • 4.3 Ship integration: Ship itineraries contain mooring locations with arrival and departure windows, enabling MAV assignment for full recharging or transit.Transit via a ship can address time-window or battery-resource constraints.

5 Summary of notations

The notation reference defines the sets, entities, routes, task requirements, timing parameters, battery parameters, and decision variables used by the mathematical model.

  • Sets and entities: The model represents MAV types, individual vehicles, research stations, mobilisation and demobilisation ports, time windows, and ship locations.These sets distinguish fleet composition, eligible stations, operational endpoints, and ship availability periods.
  • Routes: Routes connect bases, stations, pickup ports, and ship locations, while ship routes specifically use a ship as one endpoint.Static routes are indexed by origin and destination, which may include research stations, ports, or ship time-window locations.
  • Task requirements: Task requirements specify station, MAV type, required vehicle count, and task weight for prioritising science missions.The notation distinguishes the complete task set, station- and type-specific subsets, individual tasks, and their weights.
  • Parameters: Operational parameters describe travel duration, energy factors, task duration, vehicle requirements, deployment and recovery windows, and ship dwell time.Battery parameters include active and idle consumption, thresholds, initial levels, and maximum battery level.
  • Decision and state variables: Binary variables encode task assignments, route use, ship stays, ship arrivals and departures, while continuous variables record task starts, route arrivals, and battery levels.The variables collectively represent deployment decisions and the timing and energy state of each MAV throughout its plan.

6 Mathematical Model

The MILP uses lexicographically weighted objectives and feasibility constraints to prioritise science coverage while controlling fleet use, ship support, battery consumption, and mission duration.

  • Objective function: The primary objective maximises weighted MAV assignments to task requirements, allowing higher-priority science missions when full coverage is impossible.Coverage may be limited by fleet size, time windows, or MAV requirements.
  • Objective function: The remaining objectives minimise deployed MAVs, ship assignments, battery usage, and arrival time at the pickup location.Ship use is penalised, battery usage is represented through arrival battery levels, and timespan is reduced by early recovery within the allowed window.
  • Objective function: The combined objective uses weight parameters to impose priority among the five objectives and vehicle/task identifiers to avoid symmetries.The formulation is expressed as a weighted maximisation combining science, deployment, docking, battery, and timespan terms.
  • Assignment and routing constraints: Assignment and route constraints limit departures and recoveries, cap task assignments, and require incoming and outgoing routes for assigned tasks or ship stays.They also prevent MAVs from traversing locations when they are not assigned there.
  • Time constraints: Time constraints enforce deployment and recovery windows, calculate route arrivals, restrict ship movements to ship availability windows, and place task starts within feasible task windows.A task’s start time equals the MAV’s station arrival time and must allow completion by the latest permitted end.
  • Battery constraints: Battery constraints bound battery levels after tasks and routes and calculate consumption for departures from stations, ships, and bases.The model applies battery-level bounds to both task and route states.

7 Case studies and Results

Four case studies evaluate the MILP across varied missions, requirements, locations, and fleet sizes using real-world planning data and generated route costs, with textual and interactive visual outputs.

  • Case-study design: The case studies deliberately scale fleet sizes and science commitments to test planning scenarios where manual construction of feasible deployment plans becomes impractical.The scenarios are inspired by real MAV science missions but expanded with additional task requirements and fleet assets.
  • Data sources: Case-study inputs come from Marine Facilities Planning records, including ship-time applications, marine-equipment applications, and autonomous-deployment forms.ADF forms provide task requirements, locations, MAV types, vehicle counts, and deployment and recovery dates.
  • Data sources: Ship itineraries are built from marine-equipment applications to match task requirements and support additional MAV assignments to the ship.The use cases consider a single ship, the RRS Sir David Attenborough.
  • Fleet composition: The model uses Slocum Glider and Autosub Long Range 1500 MAVs, with an MAV type defined by vehicle platform and sensor configuration.These vehicle characteristics support route-cost estimation for the case studies.
  • Route costs: PolarRoute generates travel-time and battery-consumption costs for MAV and ship routes because the source forms lack origin-to-destination route costs.Costs are generated for both MAV types and, in some studies, ship itineraries.
  • Model outputs: Outputs include per-MAV activity plans, task completion rates, unused-vehicle lists, activity timelines, science-data histograms, completion heatmaps, and plan maps.Interactive Plotly visualisations provide more information than the paper screenshots.

7.2 Case studies

The case studies show the MILP model producing feasible, lean MAV deployment plans for shoreside and hybrid ship-supported operations. Ship itineraries enable battery swapping and transit assistance, while fleet limitations and idle time reveal practical trade-offs and opportunities.

  • Rothera deployment: Every one of the 11 Rothera task requirements is satisfied while one Slocum MAV is left ashore.The solver identifies a leaner fleet without reducing scientific output.
  • Rothera deployment: Idle periods between Rothera activities arise because vehicles can reach assignments before their time windows open.These intervals could support opportunistic science sampling.
  • South Georgia and the Falklands: Around South Georgia and the Falklands, the solver finds a solution in around 10 seconds for a hybrid shoreside-and-ship deployment.The scenario includes 12 task requirements and requires all autonomous assets to rendezvous with the ship before it heads north.
  • South Georgia and the Falklands: Ship interactions support either battery swapping or transit shortcuts, distinguished by whether MAVs remain aboard within the same or a later ship window.Some vehicles use the ship despite shoreside deployment and recovery.
  • South Georgia and the Falklands: One Slocum glider is retained aboard the ship because deploying it would not increase achieved task coverage.The model therefore avoids deploying every available MAV.
  • South Georgia and the Falklands: With an infeasible number of science tasks, one S1 task reaches only half of its required coverage despite full initial batteries.The optimal shortfall reflects fleet limits relative to demand and could require additional assets or reprioritisation.
  • South Georgia and the Falklands: Removing the ship while resetting every MAV to 100% charge still produces lower overall science coverage than the ship-assisted plan.This comparison isolates the material contribution of ship support.

7.5 United Kingdom Large Scale Deployment

The United Kingdom large-scale case study tests coordinated scheduling for 100 MAVs from three organisations across dispersed locations. The model returns a plan in around 10 minutes and coordinates independent transits with ship-assisted movements without manual intervention.

  • Large-scale deployment: Around 10 minutes are required to solve the 100-MAV United Kingdom deployment while minimising battery usage and deployed assets and maximising science delivery.Five Slocum gliders provide no additional science delivery and are excluded from deployment.
  • Large-scale deployment: The 100-vehicle plan is visualised through geographic snapshots with coloured asset positions and trailing paths over the preceding 30 days.This representation replaces activity-by-activity inspection of the highly complex schedule.
  • Large-scale deployment: As the ship itinerary advances, MAVs fan out from the North Sea into the Atlantic, with several rendezvousing with the ship for transit before redeployment toward Scotland.Other Atlantic assets independently return toward Scotland for recovery.

7.6 Worldwide Fleet Coordination

The worldwide fleet case study applies the model to seven independent deployments coordinated through three physical fleets, demonstrating extensive vehicle reuse and scenario-based fleet-design analysis.

  • Portfolio scope: Seven independent deployments are planned across a worldwide portfolio, with fleet sizes ranging from 10 to 20 vehicles and completed science tasks from 6 to 92.The deployments span sites including Walvis Bay, Appledore, Cornwall-France, REBELS-2, and BIO-Carbon ADF.
  • Portfolio scope: 105 MAVs complete 173 science tasks over 443 deployments, with six of seven deployments using every available asset.The eSWEETS3 deployment omits six surplus Slocum gliders.
  • Fleet coordination: 99 active MAV deployments reduce to 59 distinct physical vehicles reused across fleets, averaging nearly two consecutive deployments per vehicle.The three fleets contain 20, 24, and 15 physical vehicles, respectively.
  • Fleet coordination: The coordinated schedule combines inter-site logistics with recurring passage/review cycles, science activities, and idle periods when vehicles finish assigned tasks early.Figure 9 also overlays battery levels across the activity timeline.
  • Operational implications: The fleet arrangement is compared with a conventional single-ship mission, where the research vessel conducts surveys directly rather than primarily transporting MAV fleets.The comparison estimates roughly 7,500–8,000 tCO2 annually for the conventional vessel scenario, based on stated fuel-use assumptions.
  • Fleet-design analysis: Fleet-design what-if analysis compares 10% battery-capacity, 10% transit-speed, and combined upgrades against the standard fleet configuration.Additional science-day gains concentrate in CTD, UVP6, and O2, while some sensors show negligible or no improvement because other constraints limit them.

8 Discussion and Conclusions

The paper presents a MILP decision-support model for complex MAV mission planning and evaluates it across diverse case studies. It concludes that the approach can represent varied operational priorities, while identifying resource, static-environment, and task-representation limitations for future extensions.

  • Contributions: The proposed MILP model plans marine science missions by maximising covered science tasks while optimising fleet and battery usage.Three case studies vary in location, science requirements, ship integration, and fleet size.
  • Future work: Additional ship-assignment resource constraints are identified as a future improvement, alongside support for multiple ships in collaborative missions.The current discussion specifically highlights the need for richer ship-resource modelling.
  • Limitations: The case studies assume a static planning environment with fixed science requirements, environmental conditions, and route costs when plans are generated.Proposed extensions include rapid replanning using newly collected data and telemetry.
  • Limitations: Science tasks are currently represented as discrete point locations, whereas area and transect missions require coverage and partial or ongoing survey representations.Generalising task representation would broaden the range of missions represented by the model.
  • Conclusion: MILP-based planning generates complex multi-vehicle marine science plans while remaining flexible enough to capture diverse operational constraints and priorities.The authors position richer resource, multi-ship, dynamic, and uncertainty-aware replanning as the path toward execution-stage decision support.

Declaration of AI-assisted tools in the writing process

The authors report using Grammarly for grammar checking and language editing, while reviewing suggested changes and retaining responsibility for the publication’s content.

  • AI-assisted tools: Grammarly was used for grammar checking and language editing, with the authors reviewing its suggested changes.The statement assigns responsibility for the publication’s content to the authors.
Loading 2608.27271v1…