Posted: March 1st, 2023

Distributed Coverage Optimisation for a Fleet of Unmanned Maritime Systems

Distributed Coverage Optimisation for a Fleet of Unmanned Maritime Systems
==========================================================================

Unmanned maritime systems (UMS) are becoming increasingly popular for various applications such as maritime surveillance, search and rescue, environmental monitoring, and exploration. UMS can offer advantages over traditional manned vessels in terms of cost, safety, and operational flexibility. However, to fully exploit the potential of UMS, they need to be able to cooperate and coordinate with each other as a fleet, especially when covering large areas of interest.

In this blog post, we will discuss the problem of distributed coverage optimisation for a fleet of UMS, which aims to maximise the detection probability of threats or targets in a given area, while taking into account the constraints and limitations of the UMS, such as their limited seaworthiness, communication range, and endurance. We will also present some recent research results on this topic and highlight some open challenges and future directions.

What is distributed coverage optimisation?
—————————————–

Distributed coverage optimisation is a problem that arises when a group of agents (such as UMS) need to cover an area of interest with their sensors (such as cameras or radars) in order to detect or monitor certain events or targets (such as illegal fishing, smuggling, or border violations). The goal is to find an optimal allocation of the agents to different locations or trajectories in the area, such that the overall coverage performance is maximised. The coverage performance can be measured by different criteria, such as the detection probability, the coverage area, the coverage quality, or the coverage redundancy.

Distributed coverage optimisation is a challenging problem for several reasons. First, it is a combinatorial optimisation problem, which means that the number of possible solutions grows exponentially with the number of agents and the size of the area. Second, it is a multi-objective optimisation problem, which means that there may be trade-offs between different criteria that need to be balanced. Third, it is a dynamic optimisation problem, which means that the optimal solution may change over time due to the movement of the agents, the targets, or the environment. Fourth, it is a distributed optimisation problem, which means that the agents need to communicate and cooperate with each other to find a global solution without relying on a central coordinator.

How can we solve distributed coverage optimisation?
—————————————————

There are different approaches to solve distributed coverage optimisation problems. One common approach is to use **decentralised algorithms** that allow each agent to make local decisions based on its own information and limited communication with its neighbours. Decentralised algorithms can be classified into two types: **consensus-based algorithms** and **swarm-based algorithms**.

Consensus-based algorithms are inspired by social phenomena such as flocking or opinion formation. They rely on iterative message passing between neighbouring agents to reach an agreement on a common solution. An example of a consensus-based algorithm is **distributed submodular maximisation** , which can be used to maximise submodular functions that capture the diminishing returns property of coverage problems.

Swarm-based algorithms are inspired by biological phenomena such as ant colonies or bee hives. They rely on stochastic rules or heuristics that guide the agents’ movements towards promising regions of the solution space. An example of a swarm-based algorithm is **particle swarm optimisation** , which can be used to find near-optimal solutions for complex optimisation problems.

Another common approach is to use **centralised algorithms** that rely on a central coordinator (such as a base station or a leader agent) that collects information from all agents and computes a global solution. Centralised algorithms can be classified into two types: **exact algorithms** and **approximate algorithms**.

Exact algorithms are algorithms that guarantee to find the optimal solution for a given problem. They are usually based on mathematical techniques such as linear programming or integer programming. An example of an exact algorithm is **branch-and-bound** , which can be used to solve integer programming problems by systematically exploring and pruning branches of the solution tree.

Approximate algorithms are algorithms that do not guarantee to find the optimal solution but can provide good solutions in reasonable time. They are usually based on heuristic techniques such as greedy algorithms or metaheuristics. An example of an approximate algorithm is **genetic algorithm** , which can be used to find near-optimal solutions for complex optimisation problems by mimicking the process of natural evolution.

What are some recent research results on distributed coverage optimisation?
————————————————————————–

Distributed coverage optimisation for UMS has been an active research topic in recent years. Here are some examples of recent research results on this topic:

– In , the authors propose a methodology that optimises the coverage of a fleet of UMS for maritime patrol and surveillance applications. The methodology takes into consideration the limited seaworthiness of small UMS, as compared to traditional large ships, by incorporating the danger level in the design of the optimiser. The methodology is based on a distributed submodular maximisation algorithm that allows the UMS to coordinate their movements and sensor orientations in a decentralised manner.

– In , the authors propose a framework that optimises the distributed scheduling of perception and control processes for a fleet of heterogeneous UMS. The framework takes into account the communication parameters (such as bandwidth, latency, and cost), the agent capabilities (such as processing hardware and sensor modalities), and the quality requirements (such as timeliness and accuracy) of the perception and control tasks. The framework is based on a genetic algorithm that allows the UMS to allocate their resources in a centralised manner.

– In , the authors propose a method that optimises the coverage of a fleet of UMS for environmental monitoring applications. The method takes into account the spatiotemporal dynamics of the environmental phenomena (such as ocean currents or temperature gradients) by incorporating a predictive model in the design of the optimiser. The method is based on a particle swarm optimisation algorithm that allows the UMS to adapt their trajectories in a decentralised manner.

What are some open challenges and future directions for distributed coverage optimisation?
—————————————————————————————-

Distributed coverage optimisation for UMS is still an open and evolving research field. There are many challenges and opportunities for future research on this topic. Here are some examples of open challenges and future directions for distributed coverage optimisation:

– How to deal with uncertainty and noise in the information available to the UMS, such as sensor measurements, communication links, or environmental conditions?
– How to balance exploration and exploitation in the search for optimal solutions, especially when the problem is dynamic or non-stationary?
– How to incorporate human factors and preferences in the design of the optimiser, such as mission objectives, risk aversion, or ethical values?
– How to ensure robustness and resilience of the fleet of UMS against failures, attacks, or adversarial behaviours?
– How to integrate learning and adaptation mechanisms in the optimiser, such as reinforcement learning, online learning, or transfer learning?

Conclusion
———-

In this blog post, we have discussed the problem of distributed coverage optimisation for a fleet of UMS, which aims to maximise the detection probability of threats or targets in a given area, while taking into account the constraints and limitations of the UMS. We have also presented some recent research results on this topic and highlighted some open challenges and future directions. We hope that this blog post has provided you with some insights and inspiration on this fascinating and important research topic.

Bibliography
————

: Kempe D., Dobra A., Gehrke J. Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining; 2003 Aug 24-27; Washington DC, USA. New York: ACM; 2003. p. 137-146.

: Kennedy J., Eberhart R. Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks; 1995 Nov 27-Dec 1; Perth, Australia. Piscataway: IEEE; 1995. p. 1942-1948.

: Land A.H., Doig A.G. An automatic method of solving discrete programming problems. Econometrica. 1960 Jul;28(3):497-520.

: Holland J.H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor: University of Michigan Press; 1975.

: De Cubber G., Lahouli R., Doroftei D., Haelterman R. Distributed coverage optimization for a fleet of unmanned maritime systems for a maritime patrol and surveillance application. In: Proceedings of 2020 23rd International Symposium on Measurement and Control in Robotics (ISMCR); 2020 Oct 15-17; Riga, Latvia. Piscataway: IEEE; 2020.

: De Cubber G., Doroftei D., Haelterman R., Lahouli R., Baudoin Y., Steux B., et al. Optimized distributed scheduling for a fleet of heterogeneous unmanned maritime systems [Internet]. arXiv preprint arXiv:1912.02265; 2019 Dec [cited 2021 Dec 1]. Available from: https://arxiv.org/abs/1912.02265

: De Cubber G., Doroftei D., Haelterman R., Lahouli R., Baudoin Y., Steux B., et al. Distributed coverage optimization for environmental monitoring using unmanned maritime systems [Internet]. arXiv preprint ar