Message Passing Neural Network Versus Message Passing Algorithm for Cooperative Positioning

Cooperative Positioning (CP) relies on a network of connected agents equipped with sensing and communication technologies to improve the positioning performance of standalone solutions. In this paper, we develop a completely data-driven model combining Long Short-Term Memory (LSTM) and Message Passing Neural Network (MPNN) for CP, where agents estimate their states from inter-agent and ego-agent measurements. The proposed LSTM-MPNN model is derived by exploiting the analogy with the probability-based Message Passing Algorithm (MPA), from which the graph-based structure of the problem and message passing scheme are inherited. In our solution, the LSTM block predicts the motion of the agents, while the MPNN elaborates the node and edge embeddings for an effective inference of the agents’ state. We present numerical evidence that our approach can enhance position estimation, while being at the same time an order of magnitude less complex than typical particle-based implementations of MPA for non-linear problems. In particular, the presented LSTM-MPNN model can reduce the error on agents’ positioning to one third compared to MPA-based CP, it holds a higher convergence speed and better exploits cooperation among agents.

SECTION I. Introduction

A. Contextualization and Background

Signal processing techniques operating over centralized or distributed network architectures have been largely studied in the past, especially for Situation Awareness (SA) applications [1], [2], [3], [4]. The main application domains include Internet of Things (IoT) [5], Connected Autonomous Vehicles (CAVs) [6], [7] and Maritime Situational Awareness (MSA) [8], [9]. These applications are critical as they require sensors (hereafter generally referred as agents) monitoring and perceiving their surroundings and making informed decisions based on the perceived information. The key aspect is the cooperation among agents which enables Cooperative Positioning (CP) techniques and enhances the perception of the environment.

The Message Passing Algorithm (MPA), also known as Belief Propagation (BP) or Sum-Product Algorithm (SPA) [10], [11], is a probabilistic iterative technique which has gained a lot of interest in the field of CP [12] given its ability of linearly scaling with the number of agents [13]. MPA has been largely employed in a different number of SA frameworks, mainly addressing the Multiple Object Tracking (MOT) problem with static or mobile sensing agents [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], embedding or not the measurement to target association problem [25], [26], [27], [28].

B. Related Works

MPA attains optimal performances in case of linear models and Gaussian processes, where the iteratively computed marginal posterior belief converges to the exact marginal posterior distribution. When the conditions of linearity and Gaussianity are not met, particle-based MPA can be employed, although this typically results in a notable increase of computational and communication expenses (i.e., due to particles’ sharing and aggregation). Some works tried to improve performances of particle-based MPA implementations by reducing the particle degeneracy in dense and large networks [29], [30] or by auto-tuning the parameters of time-varying system models [31]. However, they did not resolve the main issue of MPA, which is related to the convergence of the beliefs.

Since MPA involves a repeated exchange of information (i.e., an iterative message passing) over a graph that is representative of the considered problem, the intrinsic cyclic structure of graphs leads the MPA‘s outcome to be only an approximation of the true marginal posterior distribution as the algorithm converges to a local optimum [32], [33], [34], [35]. Specifically, the approximation of beliefs can be considered satisfactory if the optimization problem is locally convex. To improve the performances, Neural Enhanced Belief Propagation (NEBP) have been recently proposed [36], [37], [38], [39], wherein MPA and Message Passing Neural Network (MPNN) are combined to rectify errors caused by cycles and model mismatch.

The MPNN [40], [41] is an extension of Neural Network (NN) customized to work on graph structures. Indeed, in conventional MPNN, a NN is present in each node and edge of the graph, elaborating the input features through an iterative message passing scheme. The elaborated features, i.e., node and edge embeddings, are usually taken as input to perform a specific task, like node/edge regression or classification. Given their similarity with the message passing in MPA, they have been used within the NEBP framework to address the problems of Data Association (DA) [39], CP [37] and also MOT [38], as well as with the implicit cooperative positioning framework [42]. However, NEBP approaches require performing both iterations of MPNN and MPA, increasing the already high computational time of particle-based methods. Furthermore, it has been demonstrated that in cases where sufficient training data are available, MPNN exhibit superior performance to MPA on cyclic graphs [43], while at the same time being scalable and able to learn non-linear dependencies.

C. Contribution

In this paper, we propose an MPNN solution that can be used as an efficient alternative of MPA in high-complexity problems. We made a first attempt in this direction in [44] where we employed MPNN for solving DA in sensor networks. Here we generalize the analysis by investigating the parallelism between MPA and MPNN, and comparing their performances in the challenging context of dynamic CP.

Mobile CP systems rely on a dynamic model for describing the temporal evolution of the agent locations and a graph model for modeling the inter-agent measurements. Here we propose an NN architecture that combines a Long Short-Term Memory (LSTM) for dynamics modeling and an MPNN for the computation of the marginal likelihoods. The LSTM learns the motion model of agents in time, while the iterative update of estimates based on measurements is obtained with the MPNN.

The main contributions of this paper are as follows:

• definition of a theoretical framework based on the analogy between MPA and MPNN, with focus on the definition of exchanged messages, iterative processing steps and inference prediction;

• proposal of an LSTM-MPNN model which completely replaces MPA for the task of CP. The model is trained using a centralized approach, while it is able to perform a completely distributed inference after deployment;

• comparison with the conventional particle-based MPA, with particular focus on positioning performances and generalization properties.

D. Paper Organization

This paper is organized as follows. Section II is devoted to the description of the adopted system model. Section III first describes the MPA for CP, giving the main steps of the algorithm, and then defines the proposed LSTM-MPNN model with a one-to-one parallelism with MPA. Lastly, it provides insights on distributed inference and centralized training procedures. Section IV presents the simulation scenario and implementation details, followed by simulation results, while Section V draws the conclusions.

SECTION II. System Model

We denote with $\mathcal {I}_{n} = \{1, \ldots, I_{n}\}$ a set of connected agents at timestep $n$ . The connectivity graph between agents is denoted with $\mathcal {G}_{n}=(\mathcal {V}_{n}, \mathcal {E}_{n})$ , where each node $i \in \mathcal {V}_{n}$ corresponds to an agent, while the edge (${i}$ , ${j}$ ), with $i\neq j$ , indicates the presence of a communication link from agent ${i}$ to agent ${j}$ . Note that the graph is directed, i.e., edges (${i}$ , ${j}$ ) and (${j}$ , ${i}$ ) differ, and might not necessarily be contemporary present. Each agent $i \in \mathcal {I}_{n}$ communicates with the set $\mathcal {N}_{i,n}$ of its neighbors and it is described by the state $\mathbf {x}_{i,n}$ , which includes kinematic parameters such as posiDon and velocity.. The motion model of agent ${i}$ from time $n\,\,-1$ to time $n$ is described by: $$\begin{equation*} \mathbf {x}_{i,n} = f^{\left ({\mathbf {x}}\right)} \left ({\mathbf {x}_{i,n-1},\mathbf {w}_{i,n-1}^{\left ({\mathbf {x}}\right)} }\right), \tag{1}\end{equation*}$$ where $\mathbf {w}_{i,n-1}^{(\mathbf {x})}$ is the driving noise process that accounts for motion uncertainty. The derived state-transition probability density function (pdf) is indicated with $p(\mathbf {x}_{i,n}| \mathbf {x}_{i,n-1})$ , which, at time $n$ = 0, coincides with the prior pdf $p(\mathbf {x}_{i,0})$ .

Each agent has access to two types of measurements: a partial and noisy observation ${\mathbf {z}_{i,n}^{(\mathrm {A})} = f^{(\mathrm {A})}(\mathbf {x}_{i,n}, \mathbf {w}_{i,n}^{(\mathrm {A})})}$ of its own state vector, and an inter-agent measurement ${\mathbf {z}_{j \to i,n}^{(\mathrm {A2A})} = f^{(\mathrm {A2A})}(\mathbf {x}_{j,n}, \mathbf {x}_{i,n}, \mathbf {w}_{i,n}^{(\mathrm {A2A})})},\,\,\forall j \in \mathcal {N}_{i,n}$ , where $\mathbf {w}_{i,n}^{(\mathrm {A})}$ and $\mathbf {w}_{i,n}^{(\mathrm {A2A})}$ are the state and inter-agent measurement noises, respectively. The functions $f^{(\mathrm {A})}(\cdot)$ and $f^{(\mathrm {A2A})}(\cdot)$ , jointly with the statistics of noises $\mathbf {w}_{i,n}^{(\mathrm {A})}$ and $\mathbf {w}_{i,n}^{(\mathrm {A2A})}$ , define the likelihood functions $p(\mathbf {z}_{i,n}^{(\mathrm {A})}| \mathbf {x}_{i,n})$ and $p(\mathbf {z}_{j \to i, n}^{(\mathrm {A2A})}| \mathbf {x}_{j,n}, \mathbf {x}_{i,n})$ , respectively. The driving processes and measurement noises are assumed to be independent across agent pairs $(i,j)$ and over time $n$ . We indicate with $\mathbf {x}_{n} = \{ \mathbf {x}_{i,n}\}_{i=1}^{I_{n}}$ the set of state vectors of all agents at time $n$ , while the two set of measurements are indicated with ${\mathbf {z}_{n}^{(\mathrm {A})} = \{\mathbf {z}_{i,n}^{(\mathrm {A})} \}_{i \in \mathcal {I}_{n}}}$ and ${\mathbf {z}_{n}^{(\mathrm {A2A})} = \{\mathbf {z}_{j \to i,n}^{(\mathrm {A2A})} \}_{i \in \mathcal {I}_{n}, j \in \mathcal {N}_{i,n}}}$ . The overall set of measurements at time $n$ is ${\mathbf {z}_{n} = \{\mathbf {z}_{i,n}^{(\mathrm {A})}, \mathbf {z}_{i,n}^{(\mathrm {A2A})} \}}$ .

CP aims at estimating the states of agents from all the aggregated measurements up to time $n$ , i.e., $\mathbf {z}_{1:n}^{(\mathrm {A})}$ and $\mathbf {z}_{1:n}^{(\mathrm {A2A})}$ . The estimated state is indicated with $\widehat {\mathbf {x}}_{n}$ . Probabilistic Bayesian methods, such as MPA, use the marginal posterior pdf $p(\mathbf {x}_{i,n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})})$ to estimate $\widehat {\mathbf {x}}_{n}$ , e.g., through the Minimum Mean Square Error (MMSE) estimator ${\widehat {\mathbf {x}}_{i,n}^{(\mathrm {MMSE})} = \int \mathbf {x}_{i,n} \, p(\mathbf {x}_{i,n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})}) \, \mathrm {d}\mathbf {x}_{i,n}}$ [18]. On the other hand, discriminative probabilistic approaches, like Deep Learning (DL), directly define the posterior pdf with parametric model, i.e., ${p(\mathbf {x}_{i,n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})}) = p(\mathbf {x}_{i,n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})}, \boldsymbol {\theta })}$ , and try to find the parameter vector $\boldsymbol {\theta }$ that maximizes ${\widehat {\mathbf {x}}_{i,n} = \mathbb {E}_{\mathbf {x}_{i,n}} [p(\mathbf {x}_{i,n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})}, \boldsymbol {\theta })] }$ [45]. This is done using as input a training dataset ${\mathcal {S}^{\mathrm {train}} = \{(\mathbf {x}_{n}, \mathbf {z}_{n}^{(\mathrm {A})}, \mathbf {z}_{n}^{(\mathrm {A2A})})\}_{n=1}^{N_{\mathrm {train}}}}$ and minimizing the negative log-likelihood, i.e., ${\boldsymbol {\theta } = \arg \min _{\boldsymbol {\theta }}[{-}\log (p(\mathbf {x}_{i,n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})}, \boldsymbol {\theta }))] }$ .

A compact representation of the temporal evolution of the system model is reported in Fig. 1, where two different network topologies (i.e., different measurement availability) at time $n$ and $n$ + 1 are illustrated. The purpose of the figure is to highlight the temporal sequence of CP and visualize different combinations of the graph $\mathcal {G}_{n}$ .

Fig. 1.

Illustration of the working principle of CP, with highlighted state vectors and measurement sets for two consecutive time instants. The figure highlights the variation of the graph $\mathcal {G}_{n}$ due to varied network topology and sets of measurements.

SECTION III. Cooperative Positioning Methods

In this section, we first review the MPA Bayesian solution for CP and then we perform a one-to-one comparison with our newly proposed LSTM-MPNN model. Lastly, a description of the inference and training procedure is given.

A. MPA-Based CP

The agent’s marginal posterior probability ${p(\mathbf {x}_{i,n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})})}$ can be obtained by marginalizing the joint posterior pdf ${p(\mathbf {x}_{0:n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})})}$ , where $\mathbf {x}_{0:n} = \{\mathbf {x}_{n^{\prime }}\}_{n^{\prime }=0}^{n}$ . Assuming statistical independence across agents at timestep $n$ = 0 and adopting Bayes’ rule, the joint posterior pdf is: $$\begin{align*} p\left ({\mathbf {x}_{0:n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})}}\right) \propto \prod _{i=1}^{I_{n}} p\left ({\mathbf {x}_{i,0}}\right) \prod _{n^{\prime }=1}^{n} p\left ({\mathbf {x}_{i,n^{\prime }}| \mathbf {x}_{i,n^{\prime }-1}}\right)& \\ p\left ({\mathbf {z}_{i,n^{\prime }}^{(\mathrm {A})}| \mathbf {x}_{i,n^{\prime }}}\right) \prod _{j \in \mathcal {N}_{i,n^{\prime }}} p\left ({\mathbf {z}_{j \to i, n^{\prime }}^{(\mathrm {A2A})}| \mathbf {x}_{j,n^{\prime }}, \mathbf {x}_{i,n^{\prime }}}\right).&\tag{2}\end{align*}$$ Since computing the marginalization of (2) can be unfeasible or extremely complex, the MPA addresses this issue by approximating the marginal posterior with an iterative message passing scheme over a factor graph which factorizes the joint posterior pdf in (2). Denoting the beliefs of agent ${i}$ at timestep $n$ and message passing iteration $t \in \{1, \ldots, T\}$ with ${\mathbf {b}_{i,n}^{(t)} \triangleq \mathbf {b}_{i}^{(t)}(\mathbf {x}_{i,n}) \approx p(\mathbf {x}_{i,n}|\mathbf {z}_{1:n}^{(\mathrm {A})}, \mathbf {z}_{1:n}^{(\mathrm {A2A})})}$ , the MPA-based CP performs the following operations in parallel for each agent.

1. Prediction message: The predicted state of agent ${i}$ is represented by the message: $$\begin{equation*} \mu _{i, \overrightarrow {n}}\left ({\mathbf {x}_{i,n}}\right) \propto \int p\left ({\mathbf {x}_{i,n}| \mathbf {x}_{i,n-1}}\right) \, \mathbf {b}_{i,n-1}^{(T)} \mathrm {d}\mathbf {x}_{i,n-1}, \tag{3}\end{equation*}$$ where $\mathbf {b}_{i,n-1}^{(T)}$ is the agent’s belief computed at previous time $n -1$ after ${T}$ message passing steps. Note that the beliefs are initialized at time $n$ = 0 as $\mathbf {b}_{i,0}^{(T)} \triangleq p(\mathbf {x}_{i,0})$ .

2. Beliefs exchange: During message passing iteration ${t \in \{1, \ldots, T\}}$ , each agent ${i}$ broadcasts $\mathbf {b}_{i,n}^{(t-1)}$ and receives $\mathbf {b}_{j,n}^{(t-1)}$ from its neighbors $j \in \mathcal {N}_{i,n}$ . At $t$ = 1, the exchanged beliefs are $\mathbf {b}_{i,n}^{(0)} = \mu _{i, \overrightarrow {n}}(\mathbf {x}_{i,n})$ .

3. Measurement messages computation: During message passing iteration $t \in \{1, \ldots, T\}$ , each agent ${i}$ computes two measurements messages (one for each type of measurement) as: $$\begin{align*}&\mu _{i, n}^{(t)\left ({\mathrm {A}}\right)}\left ({\mathbf {x}_{i,n}}\right) \triangleq p\left ({\mathbf {z}_{i,n}^{\left ({\mathrm {A}}\right)}| \mathbf {x}_{i,n}}\right), \tag{4}\\&\mu _{j \to i, n}^{(t)\left ({\mathrm {A2A}}\right)}\left ({\mathbf {x}_{i,n}}\right) \!\propto \!\! \int p\left ({\mathbf {z}_{j \to i, n}^{\left ({\mathrm {A2A}}\right)}| \mathbf {x}_{j,n}, \mathbf {x}_{i,n}}\right) \mathbf {b}_{j,n}^{(t-1)} \mathrm {d}\mathbf {x}_{j,n} \\&\;\qquad \qquad \qquad \qquad \qquad \qquad \qquad \forall j \in \mathcal {N}_{i,n}. \tag{5}\end{align*}$$

4. Beliefs update: At message passing iteration ${t \in \{1, \ldots, T\}}$ , the beliefs are updated as: $$\begin{equation*} \mathbf {b}_{i,n}^{(t)} \propto \mu _{i,\overrightarrow {n}}\left ({\mathbf {x}_{i,n}}\right) \, \mu _{i, n}^{(t)\left ({\mathrm {A}}\right)}\left ({\mathbf {x}_{i,n}}\right) \prod _{j \in \mathcal {N}_{i,n}} \mu _{j \to i, n}^{(t)\left ({\mathrm {A2A}}\right)}\left ({\mathbf {x}_{i,n}}\right). \tag{6}\end{equation*}$$

5. State inference: Lastly, after ${T}$ message passing steps, the state of agent ${i}$ is estimated with the MMSE estimator as: $$\begin{equation*} \widehat {\mathbf {x}}_{i,n} =\mathbb {E}\left [{\mathbf {b}_{i,n}^{(t)}}\right]. \tag{7}\end{equation*}$$

Step 1) is indicated as prediction step and it is computed once per timestep $n$ . On the contrary, steps 2), 3) and 4) are called update steps as they involve the measurements available at current timestep $n$ and they are performed for all ${T}$ message passing iterations per each timestep $n$ .

For graphs with a tree structure, the MPA provides exact approximation of the beliefs, which coincide with the true marginal posterior pdf [10]. However, for cyclic graphs, MPA only provides a reasonably accurate approximation of the marginal posterior with a computational complexity that linearly scales with the number of agents $I_{n}$ and message passing iterations ${T}$ . Moreover, in case of non-linear motion or measurement models, particle-based methods are recommended, despite incurring in a significant increase of communication and computational costs.

In comparison, MPNN holds the same time scalability [46], it has fewer parameters and it is able to catch any linear or non-linear relationship between input-output data, outperforming BP on loopy graphs if there is a sufficient amount of training data [43]. However, MPNN does not have the knowledge of features relation between time instants, i.e., each message passing iteration $t$ at timestep $n$ is completely independent with respect to the previous timestep $n -1$ . To solve this issue, we propose an LSTM-MPNN model which combines the time-dependent capabilities of the recurrent network as well as the flexibility and scalability of the message passing over NNs.

B. LSTM-MPNN-Based CP

The idea behind the proposed solution is to build an equivalent DL-based model of the MPA-based CP described in Section III-A. We start describing the overall model structure, shown in Fig. 2, and then we analyze each single model block. The proposed architecture is composed of two main components, an LSTM block and an MPNN block. Adopting the same logic of the MPA at prediction step, the LSTM at time $n$ receives in input the output of the MPNN $\widehat {\mathbf {x}}_{i,n-1}$ and predicts the most likely change of feature state according to the learned motion model of the agent. This is done by forwarding the hidden states of the LSTM throughout the timesteps. Therefore, the LSTM represents the equivalent block of (3) in the MPA. On the other hand, the MPNN block is performed over ${T}$ message passing steps, exactly as the message passing in the MPA, and, at last iteration ${T}$ , it returns the update of feature states, i.e., $\widehat {\mathbf {x}}_{i,n}$ . We remark that, by analogy with MPA, we adopt the MPNN in place of a Graph Neural Network (GNN) since the final prediction in the inference step (7) is a direct function of only the beliefs.

Fig. 2.

Block representation of the proposed LSTM-MPNN model.

The MPNN runs on the same physical graph of the agent network, i.e., $\mathcal {G}_{n}$ . It does not create a different graph abstraction, thus it can be computed among the physically connected agents. An MPNN considers two types of features: node embeddings, i.e., $\mathbf {v}_{i,n}^{(t)}$ , and edge embeddings, i.e., $\mathbf {e}_{j\to i,n}^{(t)}$ . The embeddings, also called attributes, contain elaborated latent information that propagates throughout $\mathcal {G}_{n}$ at each message passing step $t$ . We can see an analogy between MPA update step and MPNN if we consider the node embeddings $\mathbf {v}_{i,n}^{(t)}$ as elaborated versions of the beliefs $\mathbf {b}_{i,n}^{(t)}$ , and the edge embeddings $\mathbf {e}_{j\to i,n}^{(t)}$ as the corresponding measurement messages between agents $\mu _{j \to i, n}^{(t)(\mathrm {A2A})}$ .

The proposed MPNN model is composed of NNs for three different functions, encoding of input features $(g_{v}^{(\mathrm {A})}(\cdot)$ and $g_{e}^{(\mathrm {A2A})}(\cdot))$ , update of node and edge embeddings $(g_{v}(\cdot)$ and $g_{e}(\cdot))$ and inference regression $(g_{v}^{(\mathrm {regres})})$ . The encoding of input features is used to extract the most effective representation of measurements $\mathbf {z}_{i,n}^{(\mathrm {A})}$ and $\mathbf {z}_{j \to i, n}^{(\mathrm {A2A})}$ to accomplish the regression task, i.e., agent state estimation. The update of the node and edge embeddings takes the role of (4), (5) and (6), preparing the node embeddings $\mathbf {v}_{i,n}^{(t)}$ for the inference prediction computed by the regressor $g_{v}^{(\mathrm {regres})}$ .

The complete proposed LSTM-MPNN algorithm is shown in Fig. 3 and it is computed by each agent ${i}$ in parallel.

1. Prediction LSTM: The LSTM model in agent ${i}$ predicts the node embeddings $\mathbf {v}_{i,n}^{(t)}$ at time $n$ as: $$\begin{equation*} \mathbf {v}_{i,n}^{(0)} = g_{v}^{\left ({\mathrm {LSTM}}\right)}\left ({\widehat {\mathbf {x}}_{i,n-1}}\right), \tag{8}\end{equation*}$$ where $g_{v}^{(\mathrm {LSTM})}$ is the LSTM model. At $n$ = 0, the inference is initialized as $\widehat {\mathbf {x}}_{i,n-1} \triangleq \mathbb {E}[p(\mathbf {x}_{i,0})]$ . Note that the output of the LSTM coincides with the initialization of the node embeddings at message passing iteration $t$ = 0. Observing the parallelism with MPA, the belief estimate $\mathbf {b}_{i,n-1}^{(T)}$ is replaced by the state estimate $\widehat {\mathbf {x}}_{i,n-1}$ , while the state-transition probability pdf $p(\mathbf {x}_{i,n}| \mathbf {x}_{i,n-1})$ is learned by the LSTM.

2. Measurements encoding: At each time $n$ , before starting the message passing, the agent and inter-agent measurements are encoded as: $$\begin{align*} \mathbf {z_{h}}_{i, n}^{\left ({\mathrm {A}}\right)}=&g_{v}^{\left ({\mathrm {A}}\right)}\left ({\mathbf {z}_{i, n}^{\left ({\mathrm {A}}\right)}}\right), \tag{9}\\ \mathbf {z_{h}}_{j \to i, n}^{\left ({\mathrm {A2A}}\right)}=&g_{e}^{\left ({\mathrm {A2A}}\right)}\left ({\mathbf {z}_{j \to i, n}^{\left ({\mathrm {A2A}}\right)}}\right), \quad \forall j \in \mathcal {N}_{i,n}. \tag{10}\end{align*}$$ The encoding is necessary to elaborate the input features, it transforms the input measurements into a hidden representation. This is important since all features within the message passing should not belong to the original feature space, but to the hidden space for data privacy reasons. At message passing iteration $t$ = 1, the edge embeddings are initialized as: ${\mathbf {e}_{j\to i,n}^{(0)} = \mathbf {z_{h}}_{j \to i, n}^{(\mathrm {A2A})}}$ .

3. Node embeddings exchange: At message passing iteration ${t \in \{1, \ldots, T\}}$ , each agent ${i}$ broadcasts $\mathbf {v}_{i,n}^{(t-1)}$ and receives $\mathbf {v}_{j,n}^{(t-1)}$ from its neighbors $j \in \mathcal {N}_{i,n}$ . Here, the analogy with MPA is straightforward if we compare the beliefs exchange with the node embeddings exchange.

4. Edge and node embeddings update: At message passing iteration ${t \in \{1, \ldots, T\}}$ , the edge embeddings are updated as: $$\begin{align*}&\mathbf {e}_{j\to i,n}^{(t)} =g_{e}\left ({\mathbf {e}_{j\to i,n}^{(t-1)}, \mathbf {z_{h}}_{j \to i, n}^{\left ({\mathrm {A2A}}\right)}, \mathbf {v}_{j,n}^{(t-1)}, \mathbf {v}_{i,n}^{(t-1)}}\right), \\&\; \qquad \qquad \qquad \qquad \qquad \qquad \qquad \forall j \in \mathcal {N}_{i,n}.\quad \tag{11}\end{align*}$$ Note that (11) is the analogous of (5). Subsequently, the node embeddings are updated as: $$\begin{equation*} \mathbf {v}_{i,n}^{(t)} = g_{v}\left ({\mathbf {v}_{i,n}^{(t-1)}, \mathbf {v}_{i,n}^{(0)}, \mathbf {z_{h}}_{i, n}^{\left ({\mathrm {A}}\right)}, \Phi \left ({\left \{{\mathbf {e}_{j\to i,n}^{(t)}}\right \}_{j \in \mathcal {N}_{i,n} }}\right)}\right),\quad \tag{12}\end{equation*}$$ where $\Phi (\cdot)$ is called aggregation function, i.e., a function invariant to permutations of its inputs (e.g., element-wise summation, mean, maximum). In the node embeddings update, exactly as in the beliefs update in (6), the initial node embeddings $\mathbf {v}_{i,n}^{(0)}$ are used as a short-connection from the output of the LSTM, i.e., prediction step.

5. State inference: Lastly, after ${T}$ message passing steps, the regressor NN predicts the state of agent ${i}$ as: $$\begin{equation*} \widehat {\mathbf {x}}_{i,n} = \widehat {\mathbf {x}}_{i,n}^{(T)} = g_{v}^{\left ({\mathrm {regres}}\right)}\left ({\mathbf {v}_{i,n}^{(T)}}\right). \tag{13}\end{equation*}$$ The MMSE estimator in (7) is substituted here by the node regressor $g_{v}^{(\mathrm {regres})}(\cdot)$ which has the objective of extracting the state prediction from the compact node embeddings.

An interesting fact to point out is that the dimension of the node and edge embeddings, as well as the dimension of the encoded measurements, can be changed according to the problem. As an example, for the case of a state vector described in terms of 2D position and 2D velocity, we need a dimension of eight for the encoding of the node vector, i.e., corresponding to a propagation of a Gaussian belief distribution which holds only two parameters (mean and variance). Increasing the latent feature size leads to a higher complexity of the model which becomes able to learn more complex non-linear dependencies. On the contrary, in particle-based BP, each agent has to exchange a number of parameters equal to the number of adopted particles, each of them with a dimension of the state space, which overall is order of magnitudes higher than the dimension of the latent features in MPNN.

Fig. 3.

LSTM-MPNN algorithm for CP. (a) Graph representation of the agent network with agent states and measurements. (b) LSTM prediction at time $n$ and initialization of node and edge embeddings at message passing iteration $t$ = 0. (c) Exchange of node embeddings among agents. (d) Update of edge embeddings according to (11). (e) Update of node embeddings according to (12). (f) State inference at time $n$ after ${T}$ message passing iteration according to (13).

C. Inference and Training Procedure

The proposed LSTM-MPNN model for CP, as the MPA-based CP, is suited for distributed inference as each agent $i$ can rely on a local NNs, i.e., $g_{v}^{(\mathrm {LSTM})}(\cdot)$ , $g_{v}^{(\mathrm {A})}(\cdot)$ , $g_{e}^{(\mathrm {A2A})}(\cdot)$ , $g_{v}(\cdot)$ , $g_{e}(\cdot)$ and $g_{v}^{(\mathrm {regres})}(\cdot)$ . The physical exchange of embeddings only happens at step 3) of the message passing algorithm (iteration $t$ ) and each agent predicts its own state update according to (13). However, for convergence, each NN at each agent should retain the same parameters, as in classical MPNN. This permits a scalable solution to a non-predetermined number of edges, i.e., measurements, and nodes, i.e., agents.

To this aim, we propose a centralized training procedure in which the NNs are firstly trained to learn the CP task and then deployed in an agent network. To compute the training loss and perform back-propagation, we employ the Residual Sum of Squares (RSS) that is estimated at each timestep $n$ and at the end of each message passing iteration $t$ after the regressor prediction $\widehat {\mathbf {x}}_{i,n}^{(t)}$ as: $$\begin{equation*} \mathcal {L} = \frac {1}{N}\sum _{n = 1}^{N} \frac {1}{|\mathcal {V}_{n}|} \sum _{t = 1}^{T} \sum _{i \in \mathcal {V}_{n}} \left \|{\widehat {\mathbf {x}}_{i,n}^{(t)}-\mathbf {x}_{i,n} }\right \|_{2}^{2},\tag{14}\end{equation*}$$ where ${N}$ is the time sequence length on which the LSTM is trained for tracking. For performance evaluation, we analyze the Root Mean Square Error (RMSE) on the position and velocity of agents.

SECTION IV. Simulation Experiments

A. Dataset

We consider a 2D scenario in which $I_{n} = 16$ connected agents move in an area of $200\times200$ m for 100 timesteps of 1 s. The agent trajectories form a star shape moving from the origin outwards the area (see Fig. 4a), and the graph $\mathcal {G}_{n}$ is fully connected. The state of the agents is $\mathbf {x}_{i,n} = [\mathbf {p}_{i,n}^{\mathrm {T}} \dot {\mathbf {p}}_{i,n}^{\mathrm {T}}]^{\mathrm {T}}$ , where $\mathbf {p}_{i,n} \in \mathbb {R}^{2}$ and $\dot {\mathbf {p}}_{i,n} \in \mathbb {R}^{2}$ are the 2D position and velocity, respectively. The measurements are defined as ${\mathbf {z}_{i,n}^{(\mathrm {A})} = \mathbf {x}_{i,n} + \mathbf {w}_{i,n}^{(\mathrm {A})} }$ and ${\mathbf {z}_{j \to i,n}^{(\mathrm {A2A})} = \|\mathbf {p}_{j,n} - \mathbf {p}_{i,n}\|_{2} + \mathbf {w}_{i,n}^{(\mathrm {A2A})} }$ . Unless otherwise specified, a constant velocity model is used, while the state measurements and inter-agent measurements are zero-mean Gaussian distributed, i.e., $\mathbf {w}_{i,n}^{(\mathrm {A})} \sim \mathcal {N}(\mathbf {0}_{4}, \mathbf {C}_{\mathbf {w}^{(\mathrm {A})}})$ , with $\mathbf {C}_{\mathbf {w}^{(\mathrm {A})}} = \mathrm {diag}(\sigma ^{2}_{\mathbf {p,w}^{(\mathrm {A})}}, \sigma ^{2}_{\mathbf {p,w}^{(\mathrm {A})}}, \sigma ^{2}_{\mathbf {\dot {p},w}^{(\mathrm {A})}}, \sigma ^{2}_{\mathbf {\dot {p},w}^{(\mathrm {A})}})$ , and $\mathbf {w}_{i,n}^{(\mathrm {A2A})} \sim \mathcal {N}(0, \sigma _{\mathbf {w}^{(\mathrm {A2A})}}^{2})$ , with standard deviations $\sigma _{\mathbf {p,w}^{(\mathrm {A})}} = 5 {\mathrm{ m}}$ , $\sigma _{\mathbf {\dot {p},w}^{(\mathrm {A})}}=1 {\mathrm{ m/s}}$ and $\sigma _{\mathbf {w}^{(\mathrm {A2A})}} = 2 {\mathrm{ m}}$ .

Fig. 4.

Performance evaluation of the proposed LSTM-MPNN for CP. (a) Scenario with 16 moving agents. (b) RMSE of position and velocity over time for the non-cooperative Kalman and particle filters, the cooperative MPA and the proposed LSTM-MPNN.

For both MPA and MPNN, we consider ${T}$ = 10 message passing iterations. The proposed LSTM-MPNN model has been trained on 10000 instances of constant velocity trajectories, varying $\dot {\mathbf {p}}_{i,n} \in [{-}10, 10] {\mathrm{ m/s}}$ . In order to enhance model convergence and prevent biases, we standardized all the samples by performing a min-max scaler so that each feature lies in [0, 1]. This is done by having a prior knowledge on the agent position, i.e., $\mathbf {p}_{i,n} \in [{-}100, 100] {\mathrm{ m}}$ , and velocity, i.e., $\dot {\mathbf {p}}_{i,n} \in [{-}10, 10] {\mathrm{ m/s}}$ . We highlight that this is not a strong assumption, since to cover higher areas we just need to enlarge the maximum range of the state features. We trained the LSTM-MPNN model for a total of 300 epochs, using a batch size of 32 samples and randomizing the order of the dataset at the beginning of each epoch. Here a sample refers to an instance of trajectories composed of ${N}$ = 10 timesteps, i.e., the training sequence length of the LSTM model.

For the training and testing phases of the model, we used PyTorch version 1.12 and Python version 3.7.11. These operations were conducted on a workstation equipped with an Intel Xeon Silver 4210R CPU, which operates at a frequency of 2.40 GHz. The workstation was also supported by 96 GB of RAM and a Quadro RTX 6000 GPU with 24 GB of memory. For what concerns the optimizer, we used the Adam optimization algorithm [47] with an initial learning rate of 0.0001, and momentum values of 0.9 and 0.999 for $\beta _{1}$ and $\beta _{2}$ , respectively.

B. Model and Implementation Details

The LSTM architecture has been inspired by [48], but here we reduced its complexity such that it is constituted by two LSTM layers and a hidden output dimension, i.e., node embeddings, of 16. The complexity reduction is motivated by considering that the state estimation in CP comprises two steps (i.e., prediction and update). For the measurement encoding, update of node and edge embeddings, and state inference, we use Multi-Layer Perceptrons (MLPs) with linear layers and Gaussian Error Linear Unitss (GELUs) activation functions [49]. The complete LSTM and Multi-Layer Perceptrons (MLPs) model structures are reported in Table I.

TABLE I Details About the Layer Structure of LSTM and MLP Models

The selected final architecture of our model was derived upon experimentation, including varying the number of layers and neurons. However, the main rationale behind the general structures is the following. First, the NN encoders $g_{v}^{(\mathrm {A})}(\cdot)$ and $g_{e}^{(\mathrm {A2A})}(\cdot)$ , despite their small input sizes of $1\times1$ and $4\times1$ , are characterized by a higher computational complexity when normalized by input size in comparison to the node and edge embedding updates. Second, between $g_{v}(\cdot)$ and $g_{e}(\cdot)$ , the latter is more complex given its primary role at the initial step of each iteration and the need of processing non-linear inter-agent measurements $\mathbf {z}_{j \to i,n}^{(\mathrm {A2A})}$ . Finally, the state inference regressor $g_{v}^{(\mathrm {regres})}(\cdot)$ is the most challenging task and thus it requires an additional linear layer (4 in total) to effectively predict the state.

C. Simulation Results

1) Tracking Performances:

The first test aims at assessing the performances of the proposed LSTM-MPNN model and highlighting the advantages of adopting a data-driven solution. The comparison includes two non cooperative algorithms, i.e., a Kalman Filter (KF) and a Particle Filter (PF), which only use the agent state measurements $\mathbf {z}_{i,n}^{(\mathrm {A})}$ , and the cooperative MPA described in Section III-A, which uses the agent state measurements $\mathbf {z}_{i,n}^{(\mathrm {A})}$ and the inter-agent ones $\mathbf {z}_{j\to i,n}^{(\mathrm {A2A})}$ , and it is implemented following a particle based approach.

For the particle-based methods, the number of particles is set to $N_{\mathrm {PF}} = 1000$ . We would like to point out that the KF represents the optimal non-cooperative case since all noises are Gaussian and all models, i.e., motion and agent state measurements, are linear. On the contrary, the MPA results to be sub-optimal given the non-linearity of inter-agent measurements and the full connectivity of the agent graph.

The results of the comparison are reported in Fig. 4, where we show a realization of the scenario (Fig. 4a) and the RMSE of the position and velocity for each timestep (Fig. 4b) (averaged over 30 simulations). Starting from non-cooperative methods, we notice that the KF is well approximated by the particle-based MPA and reaches a positioning error of 1.62 m while tracking. The cooperative MPA permits to increase the performances by reaching an RMSE on position of 89 cm at convergence. Lastly, the proposed LSTM-MPNN method outperforms all the other methods, achieving an RMSE of 21 cm on the position. Concerning the velocities, all the methods converge at about 0.05 m/s of RMSE. Apart from regime performances, an additional important aspect to consider is the model convergence. Indeed, the LSTM-MPNN method is able to converge after few timesteps, while BP-based algorithms require more time. This feature allows the LSTM-MPNN model to fast react in case of track initialization and recovery after a sudden trajectory variation as it rapidly forgets the previous estimates, updating the state knowledge through LSTM hidden states.

2) Generalization Capabilities:

This experiment compares the performances of MPA and LSTM-MPNN under different validation conditions. In particular, we test different intensities of driving process and state-measurement noises. The MPA retains inside the true value of the motion and measurement noises, while the LSTM-MPNN has been trained with noise-free driving processes and measurement models. This is done in order to prove the efficacy of the method with a full-calibrated MPA and a completely miscalibrated LSTM-MPNN.

In a first test, we consider a zero-mean Gaussian-distributed driving noise, i.e., $\mathbf {w}_{i,n}^{(\mathbf {x})} \sim \mathcal {N}(\mathbf {0}_{4}, \mathbf {C}_{\mathbf {w}^{(\mathbf {x})}})$ , with $\mathbf {C}_{\mathbf {w}^{(\mathbf {x})}} = \mathrm {diag}(\sigma ^{2}_{\mathbf {p,w}^{(\mathbf {x})}}, \sigma ^{2}_{\mathbf {p,w}^{(\mathbf {x})}}, \sigma ^{2}_{\mathbf {\dot {p},w}^{(\mathbf {x})}}, \sigma ^{2}_{\mathbf {\dot {p},w}^{(\mathbf {x})}})$ . In Fig. 5, we compare the MPA and LSTM-MPNN in terms of RMSE on position, with $\sigma _{\mathbf {p,w}^{(\mathbf {x})}} = 0 {\mathrm{ m}}$ and varying $\sigma _{\mathbf {\dot {p},w}^{(\mathbf {x})}} \in [{0, 10}] {\mathrm{ m/s}}$ . From the results, we notice that when $\sigma _{\mathbf {\dot {p},w}^{(\mathbf {x})}} < 0.5 {\mathrm{ m/s}}$ , the proposed LSTM-MPNN outperforms the particle-based MPA. On the contrary, increasing the noise intensity leads to a faster degradation of performances with respect to the MPA. This is justified by two main factors. Firstly, the model has been trained using error-free trajectories, leading it to anticipate motion models that adhere to the distribution of the training trajectories. Secondly, the increased noise raises the likelihood of encountering an agent with a speed beyond the training range of [−10, 10] m/s, potentially leading to inaccurate predictions.

Fig. 5.

Analysis of the impact of driving noise standard deviation on the position accuracy for MPA and LSTM-MPNN.

In a second test, we consider a constant motion model and a varying state-measurement noise, i.e., $\sigma _{\mathbf {p,w}^{(\mathrm {A})}} \in [{0, 10}] {\mathrm{ m}}$ . This time, analyzing the results in Fig. 6, we observe that the LSTM-MPNN achieves a lower RMSE across all considered values of state measurement noise. This confirms the trend that on peak performances, i.e., with same noises and within the same area of cooperation, the proposed LSTM-MPNN model outperforms the cooperative MPA method by reducing the error to one third. Moreover, even with unfavorable conditions, i.e., training on absence of noise, the LSTM-MPNN model better generalizes against noisy state-measurements.

Fig. 6.

Comparison of the impact of state-measurement noise error in terms of RMSE of the position between MPA and LSTM-MPNN.

3) Impact on Different Number of Agents:

For this last assessment, we evaluate how the different number of cooperative agents affects the performances of the two methods. To this aim, in Fig. 7, we plot the RMSE on the position varying the number of connected agents $I_{n} \in [{2, 22}]$ . As expected, we observe that, for a low number of agents, the two methods tend to converge to the RMSE achieved for the non-cooperative case, i.e., about 1.5 m. This confirms that with a decreasing number of agents, the LSTM-MPNN model converges to the optimal case of single-agent KF. Increasing $I_{n}$ , the cooperation plays a crucial role in improving CP, especially for the proposed LSTM-MPNN model. As a matter of fact, in LSTM-MPNN with only 6 cooperative agents the same RMSE of 20 agents for the MPA method is achieved.

Fig. 7.

Comparison of the impact of varying number of cooperative agents in terms of RMSE of the position between MPA and LSTM-MPNN.

4) Computational Complexity:

Given the same graph structure and same number of message passing iterations between MPA and LSTM-MPNN models, the major difference in computational complexity lies in the computation of the prediction and update steps. In order to compare one-to-one the two methods, we define with $N_{\mathrm {PF}}$ and $N_{h}$ the number of particles in MPA and the dimension of the node and edge embeddings, respectively. These variables drive the computational complexity since they tune the trade-off between performances and efficiency. Indeed, $N_{\mathrm {PF}}$ and $N_{h}$ are the dimension of the messages exchanged during each message passing step. Moreover, in MPA, $N_{\mathrm {PF}}$ regulates the capability of the model of approximating the distributions according to the importance sampling principle. In LSTM-MPNN, $N_{h}$ has the same function of $N_{\mathrm {PF}}$ in MPA, but with the fundamental difference that here the exchanged vector, i.e., node embedding, does not represent an approximation of the distributions using a sampling mechanism. On the contrary, it represents an effective combination of distribution parameters, e.g., moments, in order to accomplish the CP task.

To this aim, in Fig. 8 we show the whole prediction time of an instance of agent trajectories, i.e., 16 agents moving as shown in Fig. 4a, varying $N_{\mathrm {PF}}$ or $N_{h}$ according to the model. Note that here the time required to exchange the particles and the node embeddings are not considered. Moreover, for a fair comparison, all agent predictions are computed on CPU and in a sequential manner. Observing the results, we notice that the LSTM-MPNN is very efficient for a number of latent dimension $N_{h} < 100$ , performing the whole inference in less than 1 s. On the contrary, the MPA is slower even with $N_{\mathrm {PF}} = 100$ particles. Comparing the two methods for $N_{\mathrm {PF}}=N_{h}$ , we note that, from a pure inference time point of view, it is more convenient to adopt the LSTM-MPNN if ${N_{\mathrm {PF}} = N_{h} < 1000}$ . However, we would like to point out that, comparing the two methods with the previously adopted $N_{\mathrm {PF}} = 1000$ and $N_{h} = 16$ , we obtain an inference time of 600 ms and 11 s for the LSTM-MPNN and MPA, respectively. Thus, with the proposed method, we reach one third of the error at 1/18 of the time.

Fig. 8.

Comparison of the impact of varying number of particles $N_{\mathrm {PF}}$ and node embedding dimension $N_{h}$ in terms of inference time between MPA and LSTM-MPNN.

SECTION V. Conclusion

This paper addressed the problem of CP by proposing an innovative LSTM-MPNN model that can be considered as a promising alternative to conventional probabilistic MPA. Besides providing for the first time a one-to-one parallelism with respect to MPA, we demonstrated the improved performance of a fully DL-based model. We detailed each part of the proposed model, starting from the need of temporal-dependence solved using an LSTM block, up to the message passing structure. The MPNN runs on the same physical graph created by the network of connected agents and it is able to perform inference in a completely distributed way. Mirroring the MPA, the messages, i.e., node embeddings, are exchanged between agents until convergence. Finally, as opposed to the MMSE estimator in MPA, the state inference is carried out through a NN at the node.

We validated the proposed approach in a synthetic network of cooperative agents moving in a scenario over straight trajectories. Numerical results showed that the proposed approach is able to address the problem of CP in an efficient and effective way by outperforming particle-based MPA in a different number of aspects. First, under peak performances point of view, the LSTM-MPNN model reaches a lower RMSE on the position by a factor of 3. Second, the LSTM-MPNN model holds a much higher speed of convergence, an order of magnitude lower computational complexity. As an example, in our experiments, the dimension of the messages exchanged by the MPNN is 16, while the number of particles exchanged by the BP is 1000. Moreover, the proposed model better handles different state-measurement noises, as well as driving noises if trained on all ranges of state feature values. Finally, the LSTM-MPNN model better exploits the power of cooperation, giving a huge improvement even with small number of cooperating agents.

The value of cooperative positioning is foreseen to dramatically grow over the next several years, especially in the context of automated and connected mobility, where dense networks of agents have to handle complex and dynamic environments. It results that an effective data-driven approach is of paramount importance to enhance positioning capabilities. Our method makes a step toward this direction, by enabling distributed and efficient cooperative inference. Future developments could be implementing not only a distributed inference but also a distributed training, maintaining at the same time the agent’s local data privacy. Moreover, applications of fully DL-based methods are foreseen for the major fields of target detection and tracking.

Code Availability Statement

The GitHub repository with the dataset and the Python code for the model, training and inference is available upon request to the corresponding author.

NOTE

Open Access provided by 'Politecnico di Milano' within the CRUI CARE Agreement