💻 computer science

Routing and Control for Marine Oil-Spill Cleanup with a Boom-Towing Vessel Fleet

This paper presents a scalable, holistic framework for coordinating fleets of autonomous surface vehicle duos to respond to large-scale marine oil spills, integrating a hybrid optimization algorithm for risk-weighted multi-spill routing with stable feedback-linearization and PID controllers for precise boom-towing execution.

Original authors: Snir Carmeli, Adir Morgan, Kiril Solovey

Published 2026-03-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Snir Carmeli, Adir Morgan, Kiril Solovey

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the ocean is a giant, busy kitchen, and someone just knocked over a massive bucket of motor oil. It's spreading everywhere, threatening to ruin the food (the fish), the countertops (the beaches), and the whole ecosystem.

This paper is about a new, high-tech way to clean up that mess using a fleet of robot boats. But instead of just sending one boat to mop it up, the authors figured out how to coordinate a whole team of them to work together efficiently, even if there are multiple oil spills happening at once.

Here is the breakdown of their solution, explained simply:

1. The Problem: Too Much Oil, Too Many Spills

Usually, when oil spills, humans send big ships to try to contain it. But if there are ten different spills happening at the same time, or if the weather is tricky, human crews get overwhelmed. They might arrive too late at the worst spill, or they might waste time driving back and forth inefficiently.

The authors propose using Autonomous Surface Vehicles (ASVs). Think of these as self-driving boats. Specifically, they use them in pairs.

The "Boom" Metaphor: Imagine two people holding a long, flexible garden hose between them. They walk around a puddle of oil, keeping the hose taut to create a circle. This hose is called a boom. It traps the oil inside so it doesn't spread. Once the oil is trapped in a small circle, a pump (a skimmer) sucks it up.
The Challenge: If you have 50 oil spills and only 10 robot pairs, how do you decide which pair goes to which spill, and in what order, to save the most time and the most fish?

2. The Brain: The "Traffic Cop" Algorithm

The first big part of the paper is the Routing Algorithm. This is the "brain" that tells the robots where to go.

The Analogy: Imagine you are a pizza delivery driver, but instead of delivering pizza, you are delivering "cleanup crews" to 50 different houses where fires are starting. Some houses are in dangerous neighborhoods (high risk), and some are far away. You want to put out the fires in the most dangerous neighborhoods first, but you also don't want to drive 100 miles just to put out a tiny candle.
The Solution: The authors created a math formula that acts like a super-smart traffic cop. It calculates the "risk" of each spill (how bad it is) and the "travel time" to get there. It then draws a map for every robot pair, telling them exactly which spill to visit next to minimize the total damage.
The Result: They built a computer program that can solve this puzzle for 100 different spills in just a few minutes on a regular laptop. It's fast enough to be used in a real emergency.

3. The Body: The "Dance" of the Robot Pairs

The second part of the paper is about Control. Once the "brain" tells a robot pair where to go, how do they actually move without breaking the boom (the hose)?

The Problem: If the two boats move too fast or turn too sharply, the hose between them might snap, or it might get tangled. They have to move like a perfectly synchronized dance team.
The Solution: The authors designed two different "dance instructors" (controllers) for the robots:
1. The PID Controller: This is the "old reliable" method. It's like a strict teacher who constantly checks the distance between the boats and makes tiny adjustments. It works well but requires a lot of tuning.
2. The Feedback Linearization Controller: This is the "math wizard" method. It uses complex physics equations to predict exactly how the water and the hose will react, allowing the boats to move smoothly and naturally.
The Result: They tested both in a computer simulation. Both worked great! The "math wizard" was slightly more efficient and needed fewer settings to tune, but the "strict teacher" was very steady. Both kept the "hose" intact while chasing the oil.

4. Why This Matters

This isn't just about robots; it's about saving money and nature.

Speed: By using robots that don't get tired and a computer brain that plans the perfect route, we can get to the worst spills faster.
Scale: Humans struggle to manage 50 spills at once. This system can handle it effortlessly.
Safety: It keeps humans out of dangerous, oil-covered waters.

The Bottom Line

The authors have built a complete "operating system" for cleaning up oil spills.

The Planner: A smart algorithm that figures out the best route for a fleet of robot pairs.
The Pilot: A control system that makes sure the two robots in each pair move together perfectly, keeping the containment boom safe.

It's like giving the ocean a team of highly trained, self-driving cleanup crews that never get tired, never argue about who goes where, and always know the fastest way to save the day.

1. Problem Statement

Marine oil spills cause severe ecological and economic damage. While mechanical recovery using booms and skimmers is the standard response, current manual or isolated autonomous approaches struggle to scale to realistic disaster scenarios involving multiple, spatially separated oil slicks.

The paper addresses two coupled challenges in coordinating a fleet of Autonomous Surface Vehicle (ASV) duos (two vessels towing a single containment boom):

Strategic Routing: How to assign multiple ASV duos to multiple oil spills to minimize cumulative environmental damage, considering spill risk factors, travel times, and cleaning durations.
Physical Execution: How to control the coupled dynamics of a two-vessel system towing a flexible boom to accurately track the generated reference paths without violating the physical constraints of the boom (e.g., length limits).

2. Methodology

The authors propose an integrated framework consisting of a Damage-Aware Routing Layer and a Trajectory Tracking Control Layer.

A. System Modeling

Environment: A planar workspace with static obstacles and $p$ oil spills, each modeled as a region with a known volume and a risk weight ( $R_i$ ).
Fleet: $k$ homogeneous ASV duos starting from a depot. Each duo consists of two vessels towing a boom of fixed length $L$ .
Damage Model: Environmental damage is modeled as a linear function of time. The total damage is the sum of risk weights multiplied by the time until each spill is fully cleaned ( $t_{clean}$ ).
Graph Abstraction: The continuous routing problem is abstracted into a directed graph where edge costs represent the time to transit between spills plus the time required for containment and cleaning.

B. Damage-Minimizing Routing (Problem A)

The routing problem is formulated as a Weighted Multi-Agent Traveling Repairman Problem (w-MTRP), which is NP-hard.

Optimization Approach: The authors develop a hybrid solver combining:
1. Mixed-Integer Linear Programming (MILP): An edge-centric formulation that minimizes the weighted sum of completion times.
2. Warm-Start Heuristic: To accelerate the MILP solver, a three-stage heuristic is used:
  - Greedy Assignment: Assigns spills to agents based on a risk-to-travel-time ratio.
  - Dynamic Programming (DP): Optimizes the visiting order for each agent independently (optimal for small subsets).
  - Iterated Local Search (ILS): Refines the solution by swapping spills between agents.
Performance: This hybrid approach generates near-optimal routing plans for scenarios with up to 100 spills and 10 agents within minutes on commodity hardware.

C. Trajectory Tracking Control (Problem B)

Once a route is generated, each ASV duo must execute the path while maintaining the boom's integrity.

Dynamics Model: The system models the coupled dynamics of the two vessels and the boom (treated as an articulated chain of rigid links with spring-damper joints). The boom exerts a measurable tension load on the vessels.
Control Strategies: Two controllers are designed and compared:
1. Baseline PID: A standard Proportional-Integral-Derivative controller tuned for surge velocity and yaw orientation.
2. Feedback Linearization (FBL): A model-based approach that decouples the nonlinear 3-DOF vessel dynamics into linear surge and yaw subsystems. It treats the boom tension as a known disturbance.
Theoretical Guarantees: The FBL controller is proven to be asymptotically stable, guaranteeing that tracking errors converge to zero as $t \to \infty$ , even in the presence of bounded disturbances.

3. Key Contributions

Integrated Framework: The first holistic approach combining high-level multi-spill routing optimization with low-level coupled dynamics control for boom-towing ASV duos.
Scalable Routing Solver: A hybrid MILP and heuristic solver capable of handling realistic multi-spill instances (tens of spills) efficiently, outperforming pure MILP or pure greedy approaches.
Control Theory Application: The application of feedback linearization to the specific dynamics of a boom-towing duo, providing theoretical stability guarantees that are often missing in prior boom-control literature.
Comprehensive Evaluation: Extensive simulations validating both the routing efficiency (damage minimization) and the tracking accuracy (path following) under coupled vessel-boom dynamics.

4. Experimental Results

Routing Evaluation

Scenarios: Tested on synthetic datasets with 25, 50, and 100 spills and 1–10 agents.
Findings:
- The MILP + Warm-Start approach consistently achieved near-optimal solutions, often matching the theoretical lower bounds.
- For difficult instances (e.g., 100 spills with few agents), the warm-start heuristic reduced the total accumulated damage by more than 50% compared to running MILP without a warm start.
- The standalone heuristic (Greedy + DP + ILS) provided high-quality solutions in under a minute, making it viable for time-critical responses.

Control Evaluation

Setup: Simulations using a 40-link boom model and realistic vessel parameters in calm water.
Findings:
- PID vs. FBL: Both controllers achieved stable path tracking.
- Performance: PID generally exhibited slightly lower steady-state errors (better tracking precision) but required tuning 8 parameters per vessel.
- FBL Efficiency: The FBL controller achieved comparable performance with only 4 tuning parameters per vessel and provided theoretical guarantees of zero steady-state error.
- Error Margins: Both controllers showed increased error at high speeds and tight curvatures, but errors remained small relative to the scale of typical oil slicks.

5. Significance and Future Work

This work bridges the gap between high-level mission planning and low-level physical execution for marine robotics. It demonstrates that autonomous fleets can effectively scale to complex, multi-spill disasters while adhering to the strict mechanical constraints of boom towing.

Future Directions:

Real-World Validation: Testing on real oil-spill data and physical hardware.
Environmental Robustness: Incorporating wind, currents, and wave disturbances into the control and routing models.
Routing Refinement: Updating the routing model to allow vessels to pass through cleaned spills (rather than around them) to further optimize paths.

In conclusion, the paper provides a robust, scalable, and theoretically grounded solution for rapid, risk-aware robotic response to large-scale marine oil spills.