Monthly Archives: January 2019

You are browsing the site archives by month.

Interesting mathematical study of the properties of graphs for graph-based SLAM and other graph-based estimation problems

Khosoussi, K., Giamou, M., Sukhatme, G. S., Huang, S., Dissanayake, G., & How, J. P., Reliable Graphs for SLAM, The International Journal of Robotics Research, 2019, DOI: 10.1177/0278364918823086.

Estimation-over-graphs (EoG) is a class of estimation problems that admit a natural graphical representation. Several key problems in robotics and sensor networks, including sensor network localization, synchronization over a group, and simultaneous localization and mapping (SLAM) fall into this category. We pursue two main goals in this work. First, we aim to characterize the impact of the graphical structure of SLAM and related problems on estimation reliability. We draw connections between several notions of graph connectivity and various properties of the underlying estimation problem. In particular, we establish results on the impact of the weighted number of spanning trees on the D-optimality criterion in 2D SLAM. These results enable agents to evaluate estimation reliability based only on the graphical representation of the EoG problem. We then use our findings and study the problem of designing sparse SLAM problems that lead to reliable maximum likelihood estimates through the synthesis of sparse graphs with the maximum weighted tree connectivity. Characterizing graphs with the maximum number of spanning trees is an open problem in general. To tackle this problem, we establish several new theoretical results, including the monotone log-submodularity of the weighted number of spanning trees. We exploit these structures and design a complementary greedy–convex pair of efficient approximation algorithms with provable guarantees. The proposed synthesis framework is applied to various forms of the measurement selection problem in resource-constrained SLAM. Our algorithms and theoretical findings are validated using random graphs, existing and new synthetic SLAM benchmarks, and publicly available real pose-graph SLAM datasets.

SLAM based on submap joining that achieves linear cost through a novel choice of the reference frame of each submap, and an interesting related works on map joining, i.e., considering submaps as observations

Liang Zhao, Shoudong Huang, Gamini Dissanayake, Linear SLAM: Linearising the SLAM problems using submap joining, Automatica, Volume 100, 2019, Pages 231-246, DOI: 10.1016/j.automatica.2018.10.037.

The main contribution of this paper is a new submap joining based approach for solving large-scale Simultaneous Localization and Mapping (SLAM) problems. Each local submap is independently built using the local information through solving a small-scale SLAM; the joining of submaps mainly involves solving linear least squares and performing nonlinear coordinate transformations. Through approximating the local submap information as the state estimate and its corresponding information matrix, judiciously selecting the submap coordinate frames, and approximating the joining of a large number of submaps by joining only two maps at a time, either sequentially or in a more efficient Divide and Conquer manner, the nonlinear optimization process involved in most of the existing submap joining approaches is avoided. Thus the proposed submap joining algorithm does not require initial guess or iterations since linear least squares problems have closed-form solutions. The proposed Linear SLAM technique is applicable to feature-based SLAM, pose graph SLAM and D-SLAM, in both two and three dimensions, and does not require any assumption on the character of the covariance matrices. Simulations and experiments are performed to evaluate the proposed Linear SLAM algorithm. Results using publicly available datasets in 2D and 3D show that Linear SLAM produces results that are very close to the best solutions that can be obtained using full nonlinear optimization algorithm started from an accurate initial guess. The C/C++ and MATLAB source codes of Linear SLAM are available on OpenSLAM.

Detection of qualitative behaviours in signals

Ying Tang, Alessio Franci, Romain Postoyan, On-line detection of qualitative dynamical changes in nonlinear systems: The resting-oscillation case, Automatica, Volume 100, 2019, Pages 17-28, DOI: 10.1016/j.automatica.2018.10.058.

Motivated by neuroscience applications, we introduce the concept of qualitative detection, that is, the problem of determining on-line the current qualitative dynamical behavior (e.g., resting, oscillating, bursting, spiking etc.) of a nonlinear system. The approach is thought for systems characterized by i) large parameter variability and redundancy, ii) a small number of possible robust, qualitatively different dynamical behaviors and, iii) the presence of sharply different characteristic timescales. These properties are omnipresent in neurosciences and hamper quantitative modeling and fitting of experimental data. As a result, novel control theoretical strategies are needed to face neuroscience challenges like on-line epileptic seizure detection. The proposed approach aims at detecting the current dynamical behavior of the system and whether a qualitative change is likely to occur without quantitatively fitting any model nor asymptotically estimating any parameter. We talk of qualitative detection. We rely on the qualitative properties of the system dynamics, extracted via singularity and singular perturbation theories, to design low dimensional qualitative detectors. We introduce this concept on a general class of singularly perturbed systems and then solve the problem for an analytically tractable class of two-dimensional systems with a single unknown sigmoidal nonlinearity and two sharply separated timescales. Numerical results are provided to show the performance of the designed qualitative detector.