Cooperative, range-based localization for mobile sensors

Thesis

This thesis describes the development of an offline, cooperative, range-based localization algorithm for use in settings where there is limited or no access to a positioning infrastructure. Motivating applications include underground animal tracking and indoor pedestrian localization. It is assumed that each sensor performs dead reckoning to estimate its current position, relative to a starting point. Each measurement adds error, causing the position estimate to drift further from the truth with time. The key idea behind the proposed algorithm is to use opportunistic radio contacts to mitigate this drift, and hence localize with greater accuracy.

The proposed algorithm first fuses radio and motion measurements into a compact graph. This graph encodes key positions along sensor trajectories as vertices, and distance measurements as edges. In so doing, localization is cast as the graph realization problem: assigning coordinates to vertices, in such a way that satisfies the observed distance measurements. The graph is first analysed to certify whether it defines a localization problem with a unique solution. Then, several algorithms are used to estimate the vertex coordinates. These vertex coordinates are then used to apply piecewise corrections to each sensor's dead reckoning trajectory to mitigate drift. Finally, if sufficient anchors are available, the corrected trajectories are then projected into a global coordinate frame.

The proposed algorithm is evaluated in simulation for the problem of indoor pedestrian tracking, using realistic error models. The results show firstly that 2D and 3D problems become provably more localizable as more anchors are used, and as the experiment duration increases. Secondly, it is shown that widely-used graph realization algorithms cannot be used for localization, as the complexity of these algorithms scales polynomially or greater with graph vertex count. Thirdly, it is shown a novel piecewise drift correction algorithm typically works well compared to a competing approach from the literature, but rare and identifiable graph configurations may cause the method to underperform.

Authors: Symington, AC

• Publication date: 2013
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: mobile; cooperative; tracking; localization; sensor
• Subjects: Robotics; Applications and algorithms; Communications engineering (optical,microwave and radio)