# Solving Multi-Robot Task Allocation and Planning in Trans-media Scenarios

Virgile de la Rochefoucauld, Simon Lacroix, Photchara Ratsamee, Haruo Takemura

► To cite this version:

Virgile de la Rochefoucauld, Simon Lacroix, Photchara Ratsamee, Haruo Takemura. Solving Multi-Robot Task Allocation and Planning in Trans-media Scenarios. IEEE/RSJ International Conference on Intelligent Robots and Systems, Oct 2024, Abu Dhabi, United Arab Emirates. hal-04695703v2

HAL Id: hal-04695703

https://laas.hal.science/hal-04695703v2

Submitted on 3 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Solving Multi-Robot Task Allocation and Planning
in Trans-media Scenarios

Virgile de La Rochefoucauld<fnref n="1" />,<fnref n="2" />, Simon Lacroix<fnref n="1" />, Photchara Ratsamee<fnref n="3" /> and Haruo Takemura<fnref n="2" />

**Abstract**— Trans-media robots, capable of operating across diverse environments, add significant complexity for multi-robot task allocation and planning problems. This paper introduces a novel approach to plan missions for such multi-robot systems, that addresses the associated specific complexities and constraints. It streamlines the overall mission planning process by decomposing it into tractable sub-problems, and addresses the issues of coalition formation, path planning, and task scheduling. It provides mission plans in very little computation time and allows to tackle large missions intractable by global planners, with negligible loss in plan optimality.

## I. INTRODUCTION

Trans-media robots, capable of operating across multiple mediums, have garnered significant attention over the past decade due to their potential to enhance versatility in complex environments. Recent studies [1], [2], [3], [4], [5], [6] and comprehensive reviews [7], [8], [9] highlight the growing importance of aerial-aquatic robots in diverse application domains.

Traditionally, missions involving multiple mediums have relied on heterogeneous multi-robot teams [10], [11]. However, utilizing trans-media robots within these missions can significantly enhance autonomy, mission scalability, and operational flexibility. Despite these advantages, the integration of robots that transition between mediums introduces substantial complexities in mission planning, particularly in managing inter-media transitions and ensuring robust supervision.

**Contributions:** This paper presents a novel framework for addressing the challenges of trans-media multi-robot task allocation (MRTA) and mission planning. We decompose the planning problem into solvable sub-problems, resulting in a structured approach that enhances the efficiency and scalability of mission planning. Our methodology utilizes a generalized formalism compatible with standard solvers, enabling the effective handling of specific constraints inherent to trans-media missions. The approach encompasses offline mission planning, including task allocation, scheduling, team formation, and path planning.

We leverage the Planning Domain Definition Language (PDDL 2.1 [12]) to systematically formalize the mission domain and planning problems, facilitating a structured approach to solving complex planning tasks. The OPTIC planer [13] is employed to address the temporal and resource-based complexities inherent in these missions.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Trans-media robots operating in both aerial and aquatic environments in a water ponds sampling scenario</figcaption></figure>

**Considered Scenarios:** Our study focuses on a pollution sampling mission involving multiple water bodies separated by land, as depicted in Figure 1. The mission requires the collection of underwater measurements, which necessitates operator supervision and real-time communication with a base station. This communication is facilitated by a surface robot that converts underwater acoustic signals into radio transmissions.

To transition between aerial and aquatic environments, the trans-media robots perform a "switch" action, enabling controlled landings and launches at designated transition points on the water surface. These critical actions are planned to occur after a preparatory aerial observation, ensuring safe transitions.

Although specific, this context is representative of real-world applications [14], and it allows us to analyze and tackle most of the challenges faced by trans-media multi-robots: large scale concurrences and communication constraints, transitions, and evolution in both mediums.

**Outline:** After a brief review of the state of the art on trans-media robots and planning for multi-medium missions, Section III details our MRTA and planning problem formulation and the associated use case. Section IV presents the problem decomposition and solving approach. Results in Section V highlight the performance of this approach with respect to the direct use of the OPTIC solver, and Section VI concludes the paper and discusses further extensions.

## II. RELATED WORK

Research has been devoted to trans-media (aerial-aquatic) robots for about a decade. [7] provides a comprehensive review of various aerial-aquatic system configurations and the associated challenges that have been tackled since the pioneering proposals (e.g. [6]). Water egress/ingress [1] or

<footnote n="1">¹ LAAS-CNRS, Université de Toulouse, CNRS, INSA, Toulouse, France</footnote>

<footnote n="2">² Osaka University's Takemura lab, Osaka, Japan.</footnote>

<footnote n="3">³ Department of Robotic and Design at Osaka Institute of Technology, Osaka, Japan</footnote>
trajectory planning [15] remain challenging due to the complexity of the transition between aerial and aquatic media.

But to the best of our knowledge mission planning for teams of aerial-aquatic robots remains an unexplored problem. First solutions to tackle multi-medium missions have used a team of cooperating heterogeneous multi-robot agents: a wide range of problems and missions have been addressed in this context, such as mixed reality team collaboration [16], environmental monitoring [16], [17], [10], [11], energy conservation [18], multi-medium environments [11], multi-roles single environment [19], etc. [11] and [16] present multi-scale data sampling missions, with humans in the monitoring loop. In [20], the robots are identified based on their assigned abstract roles: *Carrier*, *Supplier* and *Observer*. The presence of human helpers in the field is also noted. The authors use roles to generalise the rescue mission problem and formalise multi-robot cooperation through hierarchy of actions.

To address the complexity inherent in planning and scheduling tasks for multi-robot teams, [21] introduces a temporal planner and constraint description methodology aimed at simplifying the search space. The use of descriptive languages such as PDDL and its temporal extension, together with solvers such as OPTIC, increases the flexibility in defining the problems and finding solutions. The proposed strategy exploits the different capabilities of heterogeneous robots to streamline mission planning and improve large problems tractability. However, the unique advantage of trans-media robots lies in their homogeneity and adaptability to different environments, voiding the direct application of such heterogeneity-based simplifications. Nevertheless, constraining the solution space is a viable strategy for solving complex problems.

### III. PROBLEM MODELING

The problem is formalised as a MRTA problem planning tuple $\mathcal{P} = \langle R, A, P, S, M, I, G \rangle$, with:

* $R = \{r_1, r_2, \dots, r_n\}$ the set of robots

* A the set of robot actions

* $P = \{p_1, p_2, \dots, p_m\}$ the set of points of interests (PoI's)

* $S = \{s_1, s_2, \dots, s_k\}$ the set of water bodies (or “sites”)

* $M = \{\text{aerial}, \text{terrestrial}, \text{aquatic}\}$ the set of mediums

* I and G are respectively the initial and goal states.

PoI's are classified into three categories:

* $P_{spl}$ are the aquatic sampling points,

* $P_{tr}$ are the transition points at the surface of the sites,

* $P_{obs}$ are the aerial observation points above the sites.

Every PoI is associated with a site: the set $P = \bigcup_{i=1}^{k} P_{si}$ is partitioned into sites. Each site contains a series of sampling and transition points, and a single observation point above the site center.

A specific base point $p_b$ denotes the terrestrial position at which all robots are located in the initial state. The mission goal is to have all sampling points visited by a robot, and all robots back at $p_b$. Figure 2 illustrates a multi-site sampling missions.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Representation of a multi-robot mission to sample pollution in multiple bodies of water</figcaption></figure>

The planning problem is modeled using PDDL 2.1, which defines actions by predicates and effects, with an associated duration (cost). The domain's actions and constraints are formalised as follows:

**Navigate:** These actions model the robot motions between two PoI's $p_i, p_j$ belonging to the same medium. The set of navigation actions is:

$$A_{\text{nav}} = \{a_{\text{nav}}(r, p_i, p_j) \mid r \in R, p_i, p_j \in P\}$$

with

$$r \in R, p_i, p_j \in P, p_i \neq p_j, M_{p_i} = M_{p_j}$$

**Observe:** These action model the observation of all the transition points of a site, from the unique observation PoI associated to the site. The set of observation actions is:

$$A_{\text{obs}} = \{a_{\text{obs}}(r, p, s) \mid r \in R, p \in P_{\text{obs}} \cap P_s\}$$

**Switch:** This action represents a medium transition from $m_k$ to $m_l$ for a robot $r$, that can only be executed at one of the transition points of a site. The set of switch actions is:

$$A_{sw} = \{a_{sw}(r, p, m_k, m_l, s) \mid r \in R, p \in P_{tr} \cap P_s, \{m_k \neq m_l\} \in M_p\}$$

This action can only be executed after the transition points of the site $s$ have been observed:

$$\begin{gathered} t_{\text{start}}(a_{\text{sw}}(r, p_i, m_k, m_l, s)) \geq t_{\text{end}}(a_{\text{obs}}(r, p_j, s)) \\ p_i \in P_{tr} \cap P_s, p_j \in P_{obs} \cap P_s \end{gathered} \quad (1)$$

**Takeoff and Land:** these actions only occur at the base point $p_b$:

$$A_{\text{ld}} = \{a_{\text{ld}}(r, p_b) \mid r \in R, p_b \in P, m_r = \text{aerial}\}$$

$$A_{\text{toff}} = \{a_{\text{toff}}(r, p_b) \mid r \in R, p_b \in P, m_r = \text{terrestrial}\}$$

**Convert Underwater Data:** This action enables the online transmission of underwater data to base operators through a robot located at the site surface, converting acoustic transmissions into radio transmissions. The set of data conversion actions is:

$$A_{\text{cvrt}} = \{a_{\text{cvrt}}(r, p, s) \mid r \in R, p \in P_{tr} \cap P_s, m_r = \text{aquatic}\}$$

**Sample:** These actions model underwater data collection, and constitute the mission goal. Their set is:

$$A_{\text{spl}} = \{a_{\text{spl}}(r, p, s) \mid r \in R, p \in P_{\text{spl}} \cap P_s, m_r = \text{aquatic}\}$$
Sampling actions can only be executed when another robot is executing a data conversion on the same site s:

$$
\begin{align}
& \forall r_u, r_v \in R, \forall p_i \in P_{spl} \cap P_s, \forall p_j \in P_{tr} \cap P_s, \nonumber \\
& m_{ru} = m_{rv} = \text{aquatic}, \tag{2} \\
& t_{\text{start}}(a_{\text{spl}}(r_u, p_i, s)) \ge t_{\text{start}}(a_{\text{cvrt}}(r_v, p_j, s)) \nonumber \\
& \wedge t_{\text{end}}(a_{\text{spl}}(r_u, p_i, s)) \le t_{\text{end}}(a_{\text{cvrt}}(r_v, p_j, s)) \nonumber
\end{align}
$$

The goal state G is reached when all sampling points $P_{spl}$ in P have been sampled and the robots are back at the base point $p_b$, the planning problem consists in finding sequences of actions from the initial state I to the goal state G, satisfying communication and observation constraints 2 and 1.

To each action is associated a cost defined by is duration:

* Observe, Sample, Takeoff and Land actions have fixed costs

* Switch actions have two fixed costs, defined by the aquatic/aerial direction

* Convert Data and Navigate actions have a cost defined by their duration, the navigation cost<fnref n="1" /> depending on the distances $D(p_u, p_v)$ between the PoIs ($p_u, p_v$) and the medium $m_r$ in which they are executed:

$$C_{\text{nav}}(r, p_u, p_v) = \frac{D(p_u, p_v)}{V(m_r)}. \quad (3)$$

where $V(m_r)$ is the velocity of the robot r in the medium m.

## IV. PRE-ALLOCATION APPROACH

The planning problem is decomposed into components, which reduces the planner's search space via pre-allocations. The solution focuses on localizing the sampling MRTA and planning problems by pre-allocating teams on sites and assessing paths for robots across them. This approach enables OPTIC to effectively solve the MRTA for sites, while maintaining a degree of optimality. The pre-allocation is divided into three steps: the first involves estimating the cost of sampling the PoIs on sites, followed by a clusterization of the sites. The second step involves creating an allocation cost estimation for different numbers of robots allocated to each site and determining the optimal solution. Finally, the process combines the best robot path scheduling and planning with local solving of the site's sampling plan and planning problem to avoid large-scale multi-robot concurrences. Figure 3 presents the steps of this approach.

### A. Sites clustering and cost estimation

We model the mission by defining each site in S as an individual goal that the robots must visit and complete their assigned tasks at, thereby treating the sites as distinct subgoals within the overall mission framework. To estimate the cost of sampling each site, we employ a Multiple Travelling Salesman Problem (MTSP) approach, which visits all Points of Interest (PoIs) within a site. According to the taxonomy by [22], this problem is classified as a "Single depot, open

<figure><img src="image_4.png" /><figcaption>Fig. 3: Structure of the decomposed Pre-allocation Problem</figcaption></figure>

path MTSP.” The PoIs $P_{sj}$ of a site $s_j$ are divided in a set of Tours, each assigned to a robot, such that $\forall r_i \in R$ and $\forall s_j \in S: \bigcup_{i=0}^{i=n} Tour_{r_i} = P_{sj}$.

The objective is to minimize the site completion time by reducing the cost of the longest tour, defined as a MinMax MTSP. All robots start their journey from the same position $p_0$, the site's center, and visit the assigned points $\{p_1, ..., p_h\}$ in sequence. The goal and cost of a Tour for a robot $r_i$ are:

$$\text{Minimize}(\max(C(Tour_{r_i}))) \quad (4a)$$

$$C(Tour_{r_i}) = C_{\text{nav}}(r_i, p_0, p_1) + \sum_{k=1}^{h-1} C_{\text{nav}}(r_i, p_k, p_{k+1}) \quad (4b)$$

where $Tour_{r_u} \cap Tour_{r_i} = \emptyset, \forall u \neq i, 1 \le u, i \le n$. The $C_{\text{nav}}(r_i, p_0, p_1)$ accounts for the first step of the tour, which is why the summation starts at k=1.

To manage the entire mission planning process, we utilize the K-MEANS clustering method [23] to group sites, with varying robot team sizes. Each robot is assigned a cluster of PoIs to visit in a Tour. Given the need to maintain communication during sampling, a minimum of two robots is required per site. The possible robot team sizes are defined as $N_{\text{team}} = 2, ..., R_i, ..., n$, where $R_i \neq n-1$ and $\bigcup_{R_i \in N_{\text{team}}} R_i = R$ (the exclusion of size $n-1$ prevents single-robot teams).

We define $C(s_j, R_{s_j})$ as the estimated cost for a team $R_{s_j}$ of robots to complete the sampling at site $s_j$, as calculated by equations 4a and 4b $\forall r \in R_{s_j}$. The heuristic cost for each site is based on the average cost across possible team sizes.

<figure><img src="image_5.png" /><figcaption>Fig. 4: Variation of clusterization occur due to changes in sites weights (with fixed locations)</figcaption></figure>

<footnote n="1">¹This version corrects a typographical error in the IEEE proceedings version, where the navigation cost formula was misprinted</footnote>
To optimize the distribution and paths among weighted sites for different team sizes, an initial clustering is performed using the K-MEANS method, focusing on site positions. Let $Cl_{set} = \{cl_1, cl_2, ..., cl_y\}$ be the set of clusters, where each cluster $cl$ contains a set of sites $S_{cl}$, such that the union of all clusters in $Cl_{set}$ covers all sites $S$, represented as $\bigcup_{cl \in Cl_{set}} S_{cl} = S$.

Figure 4 illustrates the significance of considering site weights in clustering outcomes, even when locations are fixed. The weights influence the optimal distribution and paths, showing that varying weights can lead to different cluster formations, thus impacting overall mission planning.

After adjusting the site weights, the clusters are reconfigured to represent a more balanced division of weighted sites. The sites within each cluster are then reordered for optimal visitation, following a 'single depot, closed path MTSP' model based on site positions. The final step includes calculating $C_{nav}(r_i, p_h, p_b)$, the cost of the path from the last visited site back to the starting point, $p_b$ (the base).

## B. Estimation of allocation costs

To estimate the costs associated with different robot assignments to sites and clusters, we adjust the number of robots per site and define two key functions: **Estimation of Site Cost (ESC)** and **Estimation of Assignment Cost (EAC)**.

1) **Estimation of Site Cost (ESC):** The ESC function calculates the cost for all possible team sizes within $N_{Team}$ to complete sampling at a site $s_j$. The result is a cost matrix $C_{mat_j}$, where each element $c_{ij}$ represents the cost of assigning a team $R_i$ to site $s_j$ as presented in Section IV-A:

$$C_{mat_j} \leftarrow ESC(s_j, N_{Team})$$

Similarly, we define $C_{mat_{cl}}$ as the cost matrix for the set of clusters $Cl_{set}$.

2) **Estimation of Assignment Cost (EAC):** To determine the optimal allocation, we explore all possible combinations of team and site assignments. We define $Al(s_j, R_{s_j})$ as the allocation of team $R_{s_j}$ to site $s_j$. For a cluster of sites $cl \in Cl_{set}$, the allocation is expressed as $Al(S_{cl}, R_{cl})$, where $Al(Cl_{set}, R)$ represents the allocation of all robots $R$ across all clusters.

The cost function $C_F(s_j, R_{s_j})$ captures the cost $Al(s_j, R_{s_j})$, taking into account previous assignments of the robots in $R_{s_j}$. Given a site $s_j$, the assigned robots $R_{s_j}$, and the previously visited sites $S_{prev}(r) = \{s_1, ..., s_\sigma\}$ by robot $r$ with cost $C_{prev}$, $C_F(s_j, R_{s_j})$ is defined as:

$$C_F(s_j, R_{s_j}) = C(s_j, R_{s_j}) + C_{prev} \quad (5)$$

$$C_{prev} = \max_{r \in R_{s_j} \cap R_{s_j}} \left( \sum_{s \in S_{prev}(r)} C_F(s, R_s) + C_{nav}(r, p_{s\sigma}, p_{s_j}) \right) \quad (6)$$

where:

* $C(s_j, R_{s_j})$ is an element $c_{ij}$ of $C_{mat_j}$, from section IV-A.

* $\sum_{s \in S_{prev}(r)} C_F(s, R_s)$ is the sum of the cost of the previous site assessment allocated to the robots.

* $C_{nav}(r, p_{s\sigma}, p_{s_j})$ is the distance cost between the last and current sites for a robot $r \in R_s \cap R_{s_j}$.

The cost of $Al(S_{cl}, R_{cl})$ is defined as the maximum cost to be minimized for all team size and site pairs within a cluster:

$$C_F(S_{cl}, R_{cl}) = \max(C_F(s_j, R_{s_j})_{s_j \in S_{cl}}, R_{s_j \in R_{cl}}) \quad (7)$$

where:

* $R_{cl} = \{R_{s_j}\}_{R_{s_j} \in R_{cl}}$

* $Al(S_{cl}, R_{cl}) = \{Al(s_j, R_{s_j})\}_{s_j \in S_{cl}}, R_{s_j \in R_{cl}}$

The EAC function returns the estimated cost of all possible team/site assignments for $|R_{s_j}| \in N_{Team}$, computing the optimal allocation and associated cost for a given number of robots $R_S$ across a set of sites $S$, utilizing the team/site pair assignments $Al_{set}(S, R_S)$ and the cost matrix $C_{mat}$.

**Algorithm 1 Optimal pre-allocation of Teams Assignment**
**Input** A set of sites $S$ within clusters $Cl_{set}$, possible robot team sizes $N_{Team}$ from a robot set $R$, and two sets of possible team/site and team/cluster assignments $Al_{set}(S, N_{Team})$ and $Al_{set}(Cl, N_{Team})$ **Output:** An optimal assignment $Al(Cl_{set}, R)$ of team sizes to clusters, covering all sites $S$ in $Cl_{set}$ for all robots in $R$.

1: **for** $s_j \in S$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp; $C_{mat} \leftarrow ESC(s_j, N_{Team})$

3: **end for**

4: **for** $cl \in Cl_{set}$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp; **for** $R_{s_{cl}} \in N_{Team}$ **do**

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $C_F(S_{cl}, R_{s_{cl}}) \leftarrow EAC(S_{cl}, R_{s_{cl}}, C_{mat}, Al_{set}(S_{cl}, R_{s_{cl}}))$

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $C_{mat_{cl}} \leftarrow C_F(S_{cl}, R_{s_{cl}})$

8: **end for**

9: **end for**

10: **for** $cl \in Cl_{set}$ **do**

11: &nbsp;&nbsp;&nbsp;&nbsp; $C_F(Cl, R) \leftarrow EAC(Cl, R, C_{mat_{cl}}, Al_{set}(Cl, N_{Team}))$

12: **end for**

13: $Al(Cl_{set}, R) = \text{argmin}(C_F(Cl, R))$

3) **Optimal pre-allocation:** Using the **ESC** and **EAC** functions, Algorithm 1 identifies the optimal assignment of sites within each cluster by minimizing the maximum Tour cost across team sizes. This approach is extended to determine the best allocation of teams to clusters $Al(Cl_{set}, R)$, further minimizing overall assignment costs. By applying clustering and assignment heuristics, the algorithm efficiently allocates robot paths, balancing sampling completion time and resource usage while reducing computational complexity.

## C. Robot assignment and local planning

Figure 5 illustrates the approach applied to a typical mission scenario (for clarity and ease of understanding, we have excluded the final step of the robots returning to the base). As presented in Section IV-B, robots are allocated to various clusters of sites, and the paths for visiting these sites are determined by calculating the optimal team size and site
<figure><img src="image_6.png" /><figcaption>(a) Distribution of robots across sites over time with waiting time due to team switching of robot 2</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Clustering of sites and the different paths taken by robots.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(c) Robot allocation on a topological graph: Robot 2 switches teams after Site 1 to join Robots 0 and 1 at Site 7.</figcaption></figure>

<caption>Fig. 5: Flexible team composition and scheduling for mission scenario with 7 robots and 7 sites</caption>

allocation, along with the cost calculation for each robot, as described in Equation 5.

Robots following identical paths during the mission are grouped into the same team, as shown Figure 5b. Yet, our methodology allows for a flexible team composition, as illustrated in Figure 5c: a robot can leave its initial team upon completing a site task to assist another team at a more complex site with a higher associated cost. In such scenarios, the association of the robot with its new team and the corresponding waiting time at the new site are scheduled, as shown Figure 5a. The comprehensive mission plan is created by merging the robot paths with the MRTA plan for each site, resolved using the OPTIC planner.

The flexibility and efficiency of our solution are markedly improved by allowing robots to switch teams within the same cluster. This adaptability can lead to a more optimal allocation of resources, ensuring tasks are completed efficiently and effectively. Despite this, our approach streamlines the scheduling process, significantly enhancing the manageability and scalability of solutions for intricate, multi-robot, trans-media missions. Through careful planning and dynamic allocation, our methodology addresses the challenges of complex missions, facilitating a more coordinated and flexible response to varying task demands.

## V. RESULTS

We report results established on averages defined by 20 different scenarios, each with 15 randomly generated instances. The mission area is 1 km<fnref n="2" />, and contains randomly placed water sites of size varying from 100 to 2500 m<fnref n="2" />, the number of sampling and transition points for sites being directly related to their surface. Table I compares results for scenarios with 4 robots, and a number of sites varying from 1 to 18 sites, for the “global planning” OPTIC approach (GP) and pre-allocation approach (PA). Both approaches are stopped when either a 360 s timeout or a 32GB memory allocation is attained. OPTIC can only solve the smaller problems, rapidly reaching the maximum time or memory allowed, whereas our approach solves the most complex problems in a couple of seconds. Figure 6 shows how the time to find a solution is partitioned into the various steps

<table><caption>TABLE I: Elapsed time and solution percentages over 20 scenarios with 4 robots, varying site numbers (Intel E5-2695 v3, 2.3GHz 32GB RAM)</caption><thead><tr><th>Metric</th><th>GP</th><th>PA</th><th>Number of sites</th></tr></thead><tbody><tr><td rowspan="5">Elapsed Time (s)</td><td>0.08</td><td>0.03</td><td>1</td></tr><tr><td>0.2</td><td>0.05</td><td>2</td></tr><tr><td>1.15</td><td>0.13</td><td>3</td></tr><tr><td>Timeout</td><td>0.17</td><td>4</td></tr><tr><td>...</td><td>...</td><td>...</td></tr><tr><td>Timeout</td><td>7.16</td><td>18</td></tr><tr><td rowspan="5">Coverage of found solutions in %</td><td>95</td><td>100</td><td>1</td></tr><tr><td>35</td><td>100</td><td>2</td></tr><tr><td>10</td><td>100</td><td>3</td></tr><tr><td>0</td><td>100</td><td>4</td></tr><tr><td>...</td><td>...</td><td>...</td></tr><tr><td>...</td><td>0</td><td>100</td><td>18</td></tr></tbody></table>

for the scenarios of Table I. Figure 7 shows how this time evolves with the number of robots and sites for the PA approach: our approach can clearly address much larger problems than OPTIC<fnref n="2" />.

Given that OPTIC does not scale with problem complexity, we can not statistically assess to what extent our approach loses solution optimality (mission plan makespan). However, on a small scale scenario (4 sites from 100 to 200 m<fnref n="2" /> on a 25 000 m<fnref n="2" /> terrain), the first solution found by OPTIC in 40.6 s has a makespan of 2530 s, and the optimal solution (makespan of 2391 s) is found in 48 s, whereas our approach finds a solution in 0.11 s, with a plan makespan of 2425 s. The loss of optimality is negligible with respect to the reduction of time to find a solution.

## VI. CONCLUSION

We introduced the problem of mission planning and MRTA for trans-media multi-robot teams and a solution to mission planning for such systems in representative water sites sampling scenarios with realistic constraints. Our approach demonstrates excellent performances with respect to classical PDDL solvers, and can in particular solve much larger scale problems.

<footnote n="2">²or other PDDL solvers – for instance POPF</footnote>
<figure><img src="image_9.png" /><figcaption>Fig. 6: Time comparison for pre-allocation steps as site numbers increase with 4 robots.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 7: Scale coverage of our approach for a variety of problems and parameters</figcaption></figure>

Nearly snapshot planning time is very relevant for the kind of systems considered: given the complexity of operation of trans-media robots, the plan executions are expected to often call for re-planning. In this sense, this work paves the way for effective deployments of trans-media multi-robot systems. Future work will focus on the consideration of human supervision operations at mission planning time and on developing a wholesome planning and supervision framework with the human operator in the loop.

REFERENCES

[1] W. Weisler, W. Stewart, M. B. Anderson, K. J. Peters, A. Gopalarath- nam, and M. Bryant, "Testing and Characterization of a Fixed Wing Cross-Domain Unmanned Vehicle Operating in Aerial and Underwater Environments," *IEEE Journal of Oceanic Engineering*, vol. 43, no. 4, pp. 969-982, Oct. 2018.

[2] A. A. Pedroso, A. C. Da Silva, P. M. Pinheiro, and P. L. J. Drews, "Prototyping and Construction of a Hybrid Unmanned Aerial Underwater Vehicles," in *2022 Latin American Robotics Symposium (LARS), 2022 Brazilian Symposium on Robotics (SBR), and 2022 Workshop on Robotics in Education (WRE)*. São Bernardo do Campo, Brazil: IEEE, Oct. 2022, pp. 61-66.

[3] A. C. Horn, P. M. Pinheiro, C. B. Silva, A. A. Neto, and P. L. J. Drews Jr, "A Study on Configuration of Propellers for Multirotor-like Hybrid

Aerial-Aquatic Vehicles," in *2019 19th International Conference on Advanced Robotics (ICAR)*. Belo Horizonte, Brazil: IEEE, Dec. 2019.

[4] H. Alzu'bi, I. Mansour, and O. Rawashdeh, "Loon Copter: Implementation of a hybrid unmanned aquatic-aerial quadcopter with active buoyancy control," *Journal of Field Robotics*, vol. 35, no. 5, pp. 764-778, Aug. 2018.

[5] Y. H. Tan and B. M. Chen, "Design of a Morphable Multirotor Aerial-Aquatic Vehicle," in *OCEANS 2019 MTS/IEEE SEATTLE*. Seattle, WA, USA: IEEE, Oct. 2019, pp. 1-8.

[6] J. Liang, X. Yang, T. Wang, G. Yao, and W. Zhao, "Design and Experiment of a Bionic Gannet for Plunge-Diving," *Journal of Bionic Engineering*, vol. 10, no. 3, pp. 282-291, Sep. 2013.

[7] G. Yao, Y. Li, H. Zhang, Y. Jiang, T. Wang, F. Sun, and X. Yang, "Review of hybrid aquatic-aerial vehicle (HAAV): Classifications, current status, applications, challenges and technology perspectives," *Progress in Aerospace Sciences*, vol. 139, May 2023.

[8] X. Yang, T. Wang, J. Liang, G. Yao, and M. Liu, "Survey on the novel hybrid aquatic-aerial amphibious aircraft: Aquatic unmanned aerial vehicle (AquaUAV)," *Progress in Aerospace Sciences*, vol. 74, pp. 131-151, Apr. 2015.

[9] Y. H. Tan and B. M. Chen, "Survey on the Development of Aerial-Aquatic Hybrid Vehicles," *Unmanned Systems*, vol. 09, no. 03, pp. 263-282, Jul. 2021.

[10] A. Vasilijevic, D. Nad, F. Mandic, N. Miskovic, and Z. Vukic, "Coordinated Navigation of Surface and Underwater Marine Robotic Vehicles for Ocean Sampling and Environmental Monitoring," *IEEE/ASME Transactions on Mechatronics*, vol. 22, no. 3, Jun. 2017.

[11] F. Shkurti, A. Xu, M. Meghjani, J. C. Gamboa Higuera, Y. Girdhar, P. Giguère, B. B. Dey, J. Li, A. Kalmbach, C. Prahacs, K. Turgeon, I. Rekleitis, and G. Dudek, "Multi-domain monitoring of marine environments using a heterogeneous robot team," in *2012 IEEE/RSJ International Conference on Intelligent Robots and Systems*. IEEE, Oct. 2012, pp. 1747-1753, ISSN: 2153-0866.

[12] M. Fox and D. Long, "PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains," *Journal of Artificial Intelligence Research*, vol. 20, pp. 61-124, Dec. 2003.

[13] J. Benton, A. Coles, and A. Coles, "Temporal Planning with Preferences and Time-Dependent Continuous Costs," *Proceedings of the International Conference on Automated Planning and Scheduling*, vol. 22, pp. 2-10, May 2012.

[14] M. Kumar and K. P. Pratap, "Environmental Perspectives of Pond Ecosystems: Global Issues, Services and Indian Scenarios," Dec. 2015.

[15] P. M. Pinheiro, A. A. Neto, R. B. Grando, C. B. d. Silva, V. M. Aoki, D. S. Cardoso, A. C. Horn, and P. L. J. Drews, "Trajectory Planning for Hybrid Unmanned Aerial Underwater Vehicles with Smooth Media Transition," *Journal of Intelligent & Robotic Systems*, vol. 104, no. 3, p. 46, Mar. 2022.

[16] T. Salam and M. A. Hsieh, "Heterogeneous robot teams for modeling and prediction of multiscale environmental processes," Feb. 2022, arXiv:2103.10383 [cs].

[17] B. Bayat, N. Crasta, A. Crespi, A. M. Pascoal, and A. Ijspeert, "Environmental monitoring using autonomous vehicles: a survey of recent searching techniques," *Current Opinion in Biotechnology*, vol. 45, pp. 76-84, Jun. 2017.

[18] B. Li, B. R. Page, B. Moridian, and N. Mahmoudian, "Collaborative Mission Planning for Long-Term Operation Considering Energy Limitations," *IEEE Robotics and Automation Letters*, vol. 5, no. 3, pp. 4751-4758, Jul. 2020.

[19] S. Manjanna, A. Q. Li, R. N. Smith, I. Rekleitis, and G. Dudek, "Heterogeneous Multi-Robot System for Exploration and Strategic Water Sampling," in *2018 IEEE International Conference on Robotics and Automation (ICRA)*. Brisbane, QLD: IEEE, May 2018.

[20] Q. Yang and R. Parasuraman, "Needs-driven Heterogeneous Multi-Robot Cooperation in Rescue Missions," in *IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR)*, Nov. 2020.

[21] Y. Carreno, E. Pairet, Y. Petillot, and Ronald P. A. Petrick, "Task Allocation Strategy for Heterogeneous Robot Teams in Offshore Missions," Auckland, New Zealand, 2020, IFAAMAS, May 2020.

[22] O. Cheikhrouhou and I. Khoufi, "A Comprehensive Survey on the Multiple Travelling Salesman Problem: Applications, Approaches and Taxonomy," *Computer Science Review*, vol. 40, p. 100369, May 2021, arXiv:2102.12772 [cs].

[23] J. MacQueen, "Some methods for classification and analysis of multivariate observations," in *Proceedings of the fifth Berkeley symposium*
*on mathematical statistics and probability*, vol. 1, no. 14. Oakland,
CA, USA, 1967, pp. 281–297.