A. Multi-Agent Informative Path Planning

We address the problem of multi-agent informative path planning (IPP) optimising an information-theoretic criterion 我：Ψ否→R+ over all 否 UAV paths ψ = {ψ1，… ，ψ否}, where Ψ is the set of all possible individual UAV paths:

View Source\begin{equation*} \psi^{*}=\underset{\psi \in \Psi^{N}}{\arg\max} \ \mathrm{I}(\psi), \text{s.t.} \ \mathrm{C}(\psi_{i}) \leq B \ \forall \ i \in\{1, \ldots, N\}. \tag{1} \end{equation*}

Each set of UAV paths ψ is composed of individual paths ψ我= (页0我，… ，页乙我) ∈ Ψ of length 乙 with 3D measurement positions 页吨我∈R3 in an equi-distant grid P of resolution r磷 over multiple altitudes above the terrain. The function C :Ψ→R+ maps a UAV path ψ我 to its associated execution cost; in our work, a maximum number B∈​否+ of measurements taken along a path ψ我.

B. Terrain Mapping

The UAVs map the terrain by taking images using downward-facing cameras. The image information is processed, e.g. by semantic segmentation, communicated, and fused into a terrain map. A measurement 是吨我 taken by UAV 我 at time step 吨 is a likelihood estimate projected onto the flat terrain. We consider binary per-pixel classification and sequentially fuse 是吨我 using probabilistic occupancy grid mapping [27]. Each UAV 我 stores a local posterior map belief 米我 discretised into 米 grid cells 米杰我 of resolution r米. The altitude of the current measurement position 页吨我 determines the mapped field of view and the mapping resolution. We align r米 with the mapping resolution at the lowest altitude and upsample higher-altitude measurements to r米 to fuse heterogeneous mapping resolutions together in 米我. Similar to Popović et al. [21], we leverage an altitude-dependent sensor model specifying 对(是吨我|米杰我，页吨我） to account for non-uniform sensor measurement noise and update a UAV's local posterior map belief over each 米杰我 at time step 吨.

Fig. 2 visualises the inter-UAV communication protocol. All UAVs 我 send their measurements 是吨我 to another UAV 钾 and receive measurements 是吨钾 to update the individual local map beliefs over 米我. UAVs 我 and 钾 share measurements, if ∥页吨我−页吨钾∥2≤D​, where D∈​R+ is a radius approximating a range-limited communication channel. The communication message contains the UAV identifier 我, its position 页吨我, and its collected measurement 是吨我. The receiving UAV 钾 utilises 是我我 and 页吨我 to update its local map belief over 米钾.

C. Utility Definition for Adaptive Terrain Monitoring

Our goal is to plan future measurement positions ψt + 1我= (页t + 1我，… ，页乙我） for each UAV 我 at time step 吨 from which the next measurements {是t + 1我，… ，是乙我} maximally reduce the uncertainty of the current posterior belief over a global map M. The global map M contains measurements z0:ti taken by the N UAVs up to the current time step t. We quantify the uncertainty reduction of a set of measurements zt+1={zt+11,…,zt+1N} taken at the next time step t+1 by computing the entropy reduction over M after fusing zt+1. Then, the information criterion I(ψt+1) is computed as the summed entropy reduction along paths ψt+1:

View Source\begin{align*} \mathrm{I}(\psi^{t+1})= & \sum_{m=0}^{B-t-1}H(\mathcal{M}\vert z^{0:t+m},\boldsymbol{p}^{0:t+m})-\\ & \qquad H(\mathcal{M}\vert z^{0:t+m+1},\boldsymbol{p}^{0:t+m+1}). \tag{2} \end{align*}

We consider adaptive mapping with one interesting target class, i.e. one class that holds information value, and a complement class. Thus, the map entropy H(M|z0:tp0:t) at time step t is weighted by the importances of the interesting and the uninteresting classes:

View Source\begin{align*} & H(\mathcal{M} \vert z^{0:t}, \boldsymbol{p}^{0:t})=\sum_{j=1}^{M} H(\mathcal{M}^{j} \vert z_{0:t}, \boldsymbol{p}_{0:t})\\ = & -\sum_{j=1}^{M} \mathrm{W}(\mathcal{M}^{j}) p(\mathcal{M}^{j} \vert z^{0:t}, \boldsymbol{p}^{0:t}) \log (p(\mathcal{M}^{j} \vert z^{0:t}, \boldsymbol{p}^{0: t})\\ & + \mathrm{W}(\overline{\mathcal{M}^{j}}) p(\overline{\mathcal{M}^{j}} \vert z^{0:t}, \boldsymbol{p}^{0:t}) \log (p(\overline{\mathcal{M}^{j}} \vert z^{0: t}, \boldsymbol{p}^{0:t})), \tag{3} \end{align*}

W(Mj)=⎧⎩⎨⎪⎪w1w20.5if p(Mj|z0:t, p0:t)>0.5,if p(Mj|z0:t,p0:t)<0.5,else,(4)

View Source\begin{equation*} W(\mathcal{M}^{j})=\begin{cases} w_{1} & \text{if} \ p(\mathcal{M}^{j}\vert z^{0:t},\ \boldsymbol{p}^{0:t}) > 0.5,\\ w_{2} & \text{if} \ p(\mathcal{M}^{j} \vert z^{0:t},\boldsymbol{p}^{0:t}) < 0.5,\\ 0.5 & \text{else},\end{cases} \tag{4} \end{equation*}

A. Rl for Sequential Decision-Making

We formulate the multi-UAV IPP task as a sequential decision-making problem for a team of agents and train it using RL. The UAVs execute missions, where at each time step t each UAV i simultaneously plans its next measurement position pt+1i based on the current local on-board state ωti. The local state ωti includes the local map belief Mi that sequentially fuses past (communicated) measurements z0:t encoding the measurement history. This way, we account for partial observability induced by communication constraints and noisy sensor measurements. At each time step, all UAV actions, i.e. next measurement positions, define the joint action ut=(ut1,…,utN)∈UN. The UAVs receive one global team reward Rt:S×UN×S→R quantifying the joint information value of mapped measurements zt+1={zt1,…,ztN}. The discounted return Gt=∑B−tk=0γkRt+k, where γ∈ [0,1) is a discount factor, measures the information value of the team's paths from t until the mission budget is spent. Although each UAV chooses actions in a decentralised way based on ωti, we evaluate the performance of the team as a whole to enforce cooperative IPP behaviour.

Reward

We explicitly design the reward function R to reflect the information criterion defined in Eq. (2) to adaptively and quickly reduce map uncertainty in target areas:

Rt(st,ut,st+1)=αH(Mt+1)−H(Mt)H(Mt)+β.(5)

View Source\begin{equation*} R^{t}(s^{t}, u^{t}, s^{t+1})=\alpha\frac{H(\mathcal{M}^{t+1})-H(\mathcal{M}^{t})}{H(\mathcal{M}^{t})}+\beta. \tag{5} \end{equation*}

We reward the weighted map entropy reduction from the current to the next map state Mt+1 after mapping new measurements zt+1. We normalise the reward by the current map entropy to keep its magnitude approximately constant during the mission and apply affine scaling factors α and β to improve training stability. Note that, for γ=1, the return Gt resembles the IPP criterion in Eq. (2) up to the normalisation and scaling factors.

B. Algorithm

Our goal is to learn a policy enabling cooperative UAV team behaviour for the adaptive monitoring task. To do this, we build upon the COMA RL algorithm of Foerster et al. [20] to address our IPP task for UAV teams. COMA is an actor-critic algorithm using a centralised critic network to evaluate each agent's behaviour, described by the policy π(⋅|ωti) and parameterised by an actor network, and to optimise the policy accordingly. The critic evaluates the current policy π by estimating the agent's i state-action value Qπ(st,(ut1,…,uti,…,utN)) given the other agents' actions ut−i. The critic network is trained on-policy via TD (λ) [28] to estimate the discounted return Gt, introduced in Sec. IV-A, for taking the joint action ut from the current state st and following the current policy π afterwards. The critic uses global information st during training, while the actor utilises only on-board information ωti to predict the next-best measurement position decentralised during both training and deployment. We leverage the counterfactual baseline to assign credit to individual agents according to their contribution to the team performance, which fosters cooperative team behaviour. The advantage Ati for agent i taking action uti in the team's action ut is:

View Source\begin{equation*} A_{i}^{t}(s^{t}, \boldsymbol{u}^{t})=Q_{\pi}(s^{t}, \boldsymbol{u}^{t})-\sum_{u_{i}^{\prime t} \in U} \pi(u_{i}^{\prime t} \vert \omega_{i}^{t}) Q_{\pi}(s^{t},(\boldsymbol{u}_{-i}^t, u_{i}^{\prime t})). \tag{6} \end{equation*}

The contribution of agent i to the joint state-action value Qπ(st,ut) of the team's action ut=(ut1,…,uti,…,utN) by taking action uti is estimated by marginalising over all possible individual actions u′ti∈U while keeping the other agents' actions ut−i fixed. For optimising π(⋅|ωti), we apply the policy gradient theorem using Eq. (6) and minimise:

View Source\begin{equation*} \mathcal{L}=-\log\pi(u_{i}^{t}\vert \omega_{i}^{t})A_{i}^{t}(s^{t},\boldsymbol{u}^{t}), \tag{7} \end{equation*}

C. Network Architecture & Feature Design

We propose new actor and critic representations to exploit COMA in 3D robotic applications. As shown in Fig. 4, actor and critic are represented by neural networks fθπ and fθc, parameterised by θπ and θc. The actor network is conditioned on the agent i and its local state ωti. Feature inputs are the agent's identifier i, the remaining mission budget b, and the following spatial inputs: (a) a position map centred around the agent's position encoding the map boundaries and the communicated other agents' positions, where the values represent the agent altitudes; (b) the local map state Mi; (c) the weighted entropy of the local map state H(Mi|z0:tp0:t) in Eq. (3); (d) the weighted entropy of the measurement H(zti|pti); and (e) the map cells currently spanned by all agents‘ fields of view within the communication range (’ footprint map’).

Our critic network receives the same input (a)-(e) and, in addition, global environment information accessible during training. Specifically, it further receives: (f) a global position map encoding all agent positions pt1:N; (g) the global map state M; (h) its weighted entropy H(M|z0:tp0:t); (i) the map cells currently spanned by all agents' fields of view; and, to enable learning the counterfactual baseline in Eq. (6), (j) the other agents' actions. Inputs are provided in the position grid resolution rP. We downsample the map resolution rM by rPrM to align both resolutions. The scalar inputs i and b are expanded to constant-valued 2D feature maps.

To handle spatial information necessary for the terrain monitoring task, the networks consist of convolutional encoders and multilayer perceptron heads predicting the policy π and Q-values Qπ, respectively. Fig. 4-Top illustrates the architecture of both networks. The actor's logits fθπ(xti) given a collection xti of feature maps (a)-(e) above, are passed through a bounded softmax function π(ui|xti)=(1−ϵ) softmax (fθπ(xti))+ϵ|U| to predict the stochastic policy. The hyperparameter ϵ∈[0,1] fosters exploration during training and is set to 0 at deployment. The critic outputs Q-values Qπ(st,(ut1,…,uti,…,utN)) for each action uti∈U of agent i after the last linear layer.

D. Network Training

We train an actor and a critic network offline and utilise the trained actor online at deployment. We simulate UAV missions and learn from rewards received after fusing measurements z into the global map M. Before each mission, we generate a new terrain of resolution rM. The terrains are split into interesting and uninteresting regions. The split is randomly oriented and interesting regions cover between 30% to 60% of the terrain to foster generalisation. We fix the initial UAV positions and execute a mission until budget B is spent. During training, actions are sampled from the actor's policy as described in Sec. IV-C, where ϵ is linearly decreased from 0.5 to 0.02 over the first 10, 000 missions.

We alternate between generating 3, 000 environment interactions on-policy and policy optimisation using Eq. (7). Both networks are optimised via stochastic mini-batch gradient descent for 5 epochs using the Adam optimiser with learning rates of 1e−5 (actor) and 1e−4 (critic), and a batch size of 600. The critic network is trained to estimate the expected return Gt applying TD (λ) with λ=0.8 and γ=0.99 using a target critic network copying the critic network each 30, 000 environment interactions.

Fig. 4:

Architecture and inputs for our actor and critic. Both networks consist of convolutional encoders and linear layers in the prediction head. For the actor, the output is produced by a softmax layer (grey). Both actor and critic receive local inputs (,Actor input’). The critic also receives global inputs for centralised training (‘Critic input’). All inputs (a)-(j) are detailed in Sec IV-C.

Show All

A. Experimental Setup

For each experiment, we train for 1e6 environment interactions. Then, we execute 50 terrain monitoring missions with changing regions of interest as described in Sec IV-D. The terrains are of size 50m×50m with a map resolution of rM=10 cm. We set the planning resolution to rP=5m, bound altitudes between 5 m and 15 m, and use camera field of views of 60°, so that adjacent measurements do not overlap when taken from the lowest altitude. To account for increased sensor noise at higher altitudes, we simulate p(zti|Mji,pti) to be {0.99, 0.735, 0.625} at

Fig. 5:

Feature input ablations. We systematically add (left) and remove (right) components of our approach and show the map entropy reduction over the mission time. The results show that the entropy map input has the largest impact, while the footprint map only contributes to a better performance at the end of a mission. Our full proposed network input (green) performs best.

Show All

B. Ablation Study of Network Feature Design

In this section, we provide ablations to show that our proposed network input representation is effective for multi-agent IPP for UAVs in a 3D workspace. Our ablation studies systematically add and remove single input feature maps to assess their effect on the overall planning performance.

Fig. 5 shows the mean map entropy reduction and standard deviation during the mission with varying network input features. Steeper falling curves indicate better planning performance. In Fig. 5-Left, we add single input feature maps to base input features (a)-(d), as described in Sec. IV-C, which are necessary to model the IPP problem. In Fig. 5-Right, we remove single input feature maps.

As expected, the proposed full input (green) performs best, i.e. leads to the lowest final map entropy. The entropy map feature (blue) is most beneficial for planning performance, suggesting that it holds most relevant information for learning informative paths. Interestingly, adding the footprint map (pink) slightly harms planning performance, but leads to worse final performance when removed from the input. This indicates that, when combined with the other inputs, the footprint map has a larger contribution at the end of the mission. Intuitively, this is because identifying the currently observed map cells, which is essential for planning the next measurement positions, becomes harder as more measurements are mapped. Adding the current measurement's en-tropy (red) decreases uncertainty faster during the first ∼12 mission time steps but harms final performance, presumably since this local feature causes myopic planning bias. As part of the full input with enough global features, however, this feature is significant for planning performance providing additional map information in close proximity. Additionally, not masking invalid actions (light green) and not centring the agents‘ position map (orange) impairs performance since this removes valuable spatial information for planning. In sum, the results confirm that our network input features (‘Full’) are most effective for multi-agent IPP for UAVs in a 3D workspace, leading to superior planning performance of our proposed RL-based approach compared to possible variants.

Fig. 6:

Credit assignment study. We compare our COMA-approach (green) with variants that do not explicitly tackle the credit assignment problem in terms of map entropy (left) and F1-score (right). Later in mission when the environment is largely explored, our approach enables better cooperation for adaptive mapping.

Show All

C. Credit Assignment Mechanism Study

The experiments in this section show that accounting for the credit assignment problem results in improved planning performance, which verifies the need for explicit credit assignment mechanisms in cooperative RL-based multi-agent IPP. We perform a systematic study comparing the UAV team's IPP performance with varying advantage functions in Eq. (6) and thus changing policy gradient updates in Eq. (7). To this end, we compare our proposed approach (Sec. IV-B) against three variants of itself, as described in the following.