Nonlinear estimation techniques for autonomous navigation in single and multi robot systems

In this work we address different issues arising in mobile robot autonomous navigation. We mainly deal with localization and mapping problems in single and multi robot systems, although some contributions may escape from this classification, involving also decisional processes or more general problems and algorithms. In the first part of the thesis we discuss several approaches for mobile robots Simultaneous Localization and Mapping (SLAM): this problem arises when a mobile robot is deployed in an unknown environment and has to build a model of the environment (map) while estimating its own position and orientation (robot pose). SLAM is essentially a large nonlinear estimation problem, and, in this thesis, we address it using different estimation tools (graph-based approaches, Extended Kalman filter, and particle filters). We start by providing innovative insights on the mathematical structure of graph-based maximum likelihood approaches (pose graph optimization problem). We take advantage from these insights to devise efficient estimation strategies that enhance convergence properties of pose graph optimization while reducing the computational effort. Moreover, we propose a formal convergence analysis that justifies empirical observations of related work and provides non-trivial results on the aspects influencing global convergence of graph-based estimation schema based on Gauss-Newton methods. As a second contribution we study an Extended Kalman filter-based SLAM approach, investigating its observability properties and discussing several applications. A third contribution of the first part of the thesis deals with particle filters-based techniques; we present a multi robot extension of the SLAM problem, which relaxes common assumptions of related work. Moreover, we take advantage from the study of SLAM with particle filters to investigate the problem of autonomous exploration under uncertainty, proposing an innovative approach for exploration. This technique is shown to overcome several limitations of state-of-the-art techniques, thus underlining intrinsic limitations of particle filters-based exploration approaches. The second part of the thesis is more heterogeneous, although a main focus is on distributed algorithms for estimation and optimization in multi agent systems. In several application scenarios the input data (e.g., sensor measurements) for performing estimation or optimization are acquired by different nodes that can be geographically distant. In centralized algorithms, input data are gathered by a central computational unit which is in charge of solving the problem for the entire network. In distributed algorithms, instead, the computation is fractioned among the nodes in a network, which have to exploit local computation and communication, in order to reach consensus on a global solution of the problem (e.g., a single estimate for the variable that network’s sensors are measuring). The distributed setup allows spreading the computation burden and the memory allocation among several processors, reducing inter-nodal communication, and increasing the robustness of the systems with respect to failures of the central computation unit. A first contribution of the second part of the thesis regards a distributed gradient method for multi robot localization from relative distance measurements. The distributed gradient method is proved to converge to the same solution of its centralized counterpart, while providing the benefits of a fully decentralized scheme that can be implemented autonomously by the nodes in the network. Extensive numerical experiments highlight the advantages of using the proposed technique, in terms of convergence speed, computational cost, and communication burden. The algorithm is also suitable for the case in which no synchronization exists among the nodes and it is shown to be scalable in the network size, since it requires inexpensive computation and low memory storage. The last contribution of the thesis is focused on a distributed approach for convex optimization, based on a constraint consensus strategy. We propose an approach, named active constraints consensus, and we show that it is particularly suitable for a specific class of convex programs under uncertainty (random convex programs). In the thesis we prove that, under suitable assumptions, the active constraints consensus algorithm has several desirable properties, including finite-time convergence and limited communication requirements. We also discuss applications of the distributed algorithm, including distributed estimation and classification.