Cooperative Simultaneous Localization and Mapping by Exploiting Multipath Propagation

ABSTRACT

An affordable and reliable indoor positioning is a highly needed service. Moreover, maps of the indoor environment are vital to many applications. In this paper, a method for joint localization and mapping using multipath delay estimates is developed. Required high-resolution estimates of multipath delays may be obtained using radio frequency or acoustic measurements among a set of nodes in a network. In this paper, the problem is modeled in two-dimensional space with arbitrary node configuration and assuming a convex polygonal room shape. Joint localization and mapping is formulated as an optimization problem. It is subdivided and relaxed into two convex subproblems, which can be solved in an alternating manner. A method for data association and a low-complexity mapping algorithm stemming from Hough transform are proposed. Both the estimation performance and identifiability of the indoor localization problem are improved. Moreover, a basic map of the propagation environment is produced.

INTRODUCTION

Service that utilize user’s location are an integral part of wireless technology [1]. Conventional positioning systems employing radio-frequency measurements, such as global positioning system (GPS), may not be available in indoor environments or they suffer from multipath propagation of radio signals. However, it is possible to exploit the multipath propagation to improve the performance of indoor localization [2]. Such a technique requires a map of the environment. In this paper, a map describes the geometry of the reflecting objects in a propagation environment. Geometrical models and maps of the indoor environment are vital to many applications such as robot navigation and first responders in emergency services. The specular components of multipath propagation can be exploited to create such a map [3]. The problem addressed in this paper is to simultaneously estimate the locations of the network nodes and create a map of the environment given delay/distance estimates corresponding to line-of-sight (LOC) and single-bounce reflection (SBR) paths among network nodes. An SBR path is a ray between two nodes that is bounced from a reflector once, i.e., a first-order reflection. Multipath distances may be estimated using radio frequency, ultra wide band (UWB), or acoustic measurements employing high resolution time delay estimation techniques [4]. In this paper, the problem is modeled in 2D space with arbitrarynode configuration and assuming a convex polygonal room shape. However, the proposed method can be extended to 3D space and non-convex polygonal rooms.

Performance bounds for multipath-aided localization and multipath exploitation radar (MER) were presented in [5]–[7]. Single-target multipath-aided localization algorithms were developed based on ray-tracing [8], message passing [9]–[11], and radar principles [12]. The problem of cooperative network localization is a non-convex problem. The only exception is the case of unconstrained localization using squared distances [13, chap. 7], which is addressed by the multi-dimensional scaling with map matching (MDS-MAP) algorithm [14]. Convex relaxation for the network localization problem was first proposed in [15], [16], with further improvements in [17]–[20].

IDENTIFIABILITY

 The problem formulation in this paper and the proposed methods do not require all LOS and SBR distances to be estimated. However, the problem in (5) may not have a unique solution with error-free data if some of the distance estimates are missing. A localization problem is called uniquely localizable, i.e., identifi- able, if it has a unique optimal solution with error-free distance estimates. In a uniquely localizable problem with a given map and true data association, the SDP relaxation (11) finds the exact solution, i.e., G = XTX. This can be shown with an analysis similar to that given in [44]. The identifiability of a network localization problem is closely related to the rigidity of the network graph. This concept has been extensively discussed in the literature [9], [44]–[46]. However, The existing theory for network localization does not incorporate SBR distances or virtual nodes. The question of identifiability becomes even more complex for the mapping problem. The position and orientation of a reflector can be found unambiguously if the error-free lengths of three SBR paths corresponding to that reflector and among three different nodes are given. The nodes should not lie on a single line, and their positions should be known. Given a true assignment between delays and reflectors, the mapping problem has a unique solution if the above condition is satisfied for all the reflectors. Moreover, if these conditions are satisfied then the results of this paper can be extended to any non-convex polygonal room shape. If the mapping problem has a unique solution, the SDP relaxation (11) finds that exact solution with error-free delay estimates. However, the Hough detector does not require error-free delay estimates to find a unique solution. It typically converges to the true solution if there are sufficient number of SBR distance estimates, e.g., eight paths per each reflector, among some randomly distributed nodes. In practice, the number of SBR paths increase quadratically with the number of the nodes. In Section II, it has been assumed that the reflector line segments (if extended) from a convex shape. That is, the reflectors are the edges of a convex polygon with an empty interior. Although the algorithm was not exclusively developed for convex rooms, the impact of concave shapes and complex geometries is not studied in this paper. The identifiability analysis for the SLAM problem is more complex. If the localization problem is identifiable with only LOS distances, and the mapping problem is identifiable given the locations, and the true data association is known, then the SLAM problem has a unique solution. However, the true data association is not known a priori. More studies are needed to establish uniqueness conditions for data association, i.e., a set V2 that minimizes the objective in (9). However, the uniqueness of the index set V2 is not necessary for having unique localization and mapping solutions.

CONCLUSION

An affordable and accurate positioning system for indoor environments is a highly needed tool. Maps of the indoor environment are needed for multipath-aided localization. Such maps are also vital to many other applications. The problem of joint localization and mapping using multipath distance estimates was studied in this paper. The contributions of this paper are summarized as follows.

 1) The problem of cooperative joint localization and mapping was formulated as an optimization problem and then relaxed to two separate convex sub-problems. This relaxation enabled us to apply a well-established theory of convex optimization to study the problem, and apply computationally-efficient numerical methods to find a solution.

2) A novel indoor mapping algorithm, called Hough detector, was proposed for detecting reflectors and estimating their geometry. The method helps to avoid the combinatorial complexity of assigning distance estimates to re- flectors. The algorithm was improved compared to our preliminary work by designing new filtration and detection stages.

3) A novel algorithm called MCLAM was proposed to simultaneously estimate the locations of the nodes and build a map of the environment. The algorithm also provides a reliable mechanism for detection and labeling of SBR delays without the complexity of a combinatorial search.

The algorithms proposed in this paper improve both the estimation performance and identifiability of the indoor localization problem, while lowering the sensitivity to node configuration.