Viable path planning for data collection robots in a sensing field with obstacles

Introducing mobile robots into wireless sensor networks to collect data can balance the energy dissipation through the entire network and then improve the network lifetime. In this context, path management is a crucial problem since it impacts on the system performance such as data delivery delay and energy consumption. In this paper, we consider the problem of planning paths for unicycle robots (with constant speed and bounded angular velocity) to visit a set of sensor nodes in a sensing field with obstacles while minimizing the path lengths. Several practical issues that have not been sufficiently addressed so far are taken into account. As the combination of concerns from robotics and sensor networks, a viable path is defined, which is smooth, collision free with sensor nodes and obstacles, closed and let the robot to read all the data from sensor nodes. To design the shortest viable path for the underlying robots, a Shortest Viable Path Planning (SVPP) algorithm is first developed for single robot. Due to the physical speed, using single robot to collect data in a large scale network may result in a long collection time. Then, a k-Shortest Viable Path Planning (k-SVPP) algorithm to construct k paths of approximately equal lengths is proposed. Through extensive simulations, we demonstrate the effectiveness of the proposed algorithms and show their advantages over the alternatives.