Meyer, Florian (Vienna University of Technology) "Navigation and Tracking in Networks: Distributed Algorithms for Cooperative Estimation and Information-Seeking Control" (2015)

Meyer, Florian (Vienna University of Technology) "Navigation and Tracking in Networks: Distributed Algorithms for Cooperative Estimation and Information-Seeking Control" (2015), Advisor: Hlawatsch, Franz.

Abstract

Navigating unmanned autonomous vehicles (UAVs) and tracking objects are key prerequisites for an effective and safe operation of UAVs in real-world scenarios. To be able to perform complicated tasks autonomously, UAVs are often organized in networked teams. Due to the decentralized structure of the network, the potentially high mobility of the UAVs, and the high accuracy and robustness required for a fully autonomous operation, navigation and tracking in such mobile agent networks are difficult tasks. In large agent networks, centralized algorithms for solving these tasks are impractical since they are typically not scalable and not robust to agent failure. Therefore, to leverage the full potential of agent networks, there is a need for efficient distributed (decentralized) algorithms for navigation and tracking. This thesis presents the following contributions to the art of distributed navigation and tracking.

A powerful technique for cooperative navigation in agent networks is nonparametric belief propagation (NBP) message passing. NBP-based cooperative navigation is highly accurate and fully distributed, but it suffers from a high computational complexity and significant communication requirements. In this thesis, we propose a dimension-augmented reformulation of belief propagation (BP) message passing. This reformulation allows the application of an arbitrary technique for sequential Bayesian estimation (e.g., extended Kalman filter, sigma point filter, cubature Kalman filter, or belief condensation filter) to BP message passing. We use dimension-augmented BP to derive a new improved NBP algorithm. This algorithm differs from the conventional NBP algorithm in that it employs an efficient scheme for particle-based message multiplication whose complexity scales only linearly (rather than quadratically) with the number of particles. In addition, we use dimension-augmented BP to develop the sigma point BP (SPBP) message passing scheme for cooperative navigation. SPBP is a new low-complexity approximation of BP that extends the sigma point filter (aka unscented Kalman filter) to cooperative estimation problems. SPBP is characterized by very low communication requirements, since only a mean vector and a covariance matrix are communicated between neighboring agents. Our simulation results show that for cooperative navigation, SPBP can outperform conventional NBP while requiring significantly less computation and communication.

As a second contribution, we extend BP-based cooperative navigation to the case where some agents in the network are noncooperative in that they do not communicate and perform computations. For this problem of cooperative simultaneous navigation and tracking (CoSNAT), we develop a particle-based BP message passing algorithm. This algorithm is, to the best of the author’s knowledge, the first method for CoSNAT in a fully dynamic setting. A key feature of the proposed CoSNAT algorithm is a bidirectional probabilistic information transfer between the navigation and tracking stages, which allows uncertainties in one stage to be taken into account by the other stage and thereby improves the performance of both stages. The algorithm is fully distributed, i.e., communication is only performed between neighboring agents in the network and no complicated communication protocol is required. Simulation results demonstrate significant improvements in navigation and tracking performance compared to separate cooperative navigation and distributed tracking.

Finally, we present a distributed information-seeking control scheme that aims to move the agents in such a way that their measurements are maximally informative about the parameters (states) to be estimated. For information-seeking control, we define a global (holistic) objective function as the negative joint posterior entropy of all states in the network at the next time step conditioned on all measurements at the next time step. This objective function is optimized jointly by all agents via a gradient ascent. This optimization reduces to the evaluation of local gradients at each agent, which is performed by using Monte Carlo integration. The local gradients are based on particle representations of marginal posterior distributions provided by the estimation stage and a distributed calculation of the joint (networkwide) likelihood function. Simulation results demonstrate intelligent behavior of the agents and excellent estimation performance for cooperative navigation and for CoSNAT. In a cooperative navigation scenario with only one anchor present, mobile agents can localize themselves after a short time with an accuracy that is higher than the accuracy of the performed distance measurements.