A Position and Area Localization Algorithm for Obstacles in the Environment of Sparsely-Deployed Sensors

Abstract

Measuring the space area of obstacles is one of the important problems in obstacle localizing fields. Most of the existing research works on the localization of obstacles focus on where the obstacles are, and few of them measure both the positions and the areas of the obstacles. In this paper, we propose a Minimum convex bounding Polygon localizing algorithm based on Visible light Tracking (MPVT) in order to rapidly and accurately locate the position and area of a 2D obstacle in the environment of sparsely-deployed sensors. MPVT first determines the initial localization light by Visible Light Tracing method (VLT). Second, it searches for the first side of the Minimum Convex Bounding Polygon (MCBP) of the obstacle. Third, MPVT calculates the subsequent other sides and the vertexes of MCBP until the next side coincides with the first side. In order to evaluate the approximation degree between the actual values and the localization values in terms of areas, positions and shapes, we propose two performance evaluation indexes, i.e., the area ratio and the ratio of equivalent radius. We conducted experiments on the influence of obstacle orientation and sparseness of sensor deployment, the accuracy comparison with the existing methods, and the time complexity. Experiment results show that MPVT can accurately locate the position and area of the obstacle in the environment of sparsely-deployed sensors with low time overhead, and is suitable for low-cost obstacle localization applications.

Keywords

• Minimum convex bounding polygon
• obstacle localization
• ratio of equivalent radius
• sparse environment
• visible light tracking