Task allocation and path planning in wireless sensor and robot networks

There is a growing trend in integrating Mobile (Tele-) Robotics and Wireless Sensor Networks (WSNs), leading to a network which we define as a Wireless Sensor and Robot Network (WSRN). Integrating these complementary fields has motivated researchers to envision various applications that can go beyond passive monitoring and allow operators to actually interact with the environment through autonomous and teleoperated robots. Such applications can be extensively used in medicine, science, military, industry, nuclear power stations, underwater and space explorations. There are many challenging issues in realizing WSRN applications and fully utilizing their potential benefits. In this dissertation, we consider this idea at the high level, and specifically focus on two key problems--namely task allocation and path-planning. As an example, we consider monitoring and surveillance applications where simple sensors trigger requests for robots to perform additional monitoring and data collection tasks at certain locations. We begin with the path planning problem, specifically, how to plan paths for robots with the inability to make sharp turns. To do this, we adjust a straight line TSP path to fit the constraints of the given mobile robot. We then extend this to consider the data at each location and finally look into algorithms to balance the loads among multiple mobile robots. Next, we look at the task allocation problem. We investigate how to efficiently determine which robots would be best to take care of each request. In this regard, we propose a location prediction based movement strategy and compared it with other movement strategies. We also analyzed these approaches mathematically and included service times to see if we could predict some performance metrics based on our analysis. The previous solution was developed under the assumption that the robots have the ability to directly communicate with the base station. However, this might not be the case in large scale applications. So, we investigated how to maintain connectivity when assigning tasks to mobile robots. In order to do this, we began by formulating the problem in the single event case and then proceeded to extend this to the multi-event case. We provided heuristics for each problem and compared it to a Virtual Forces algorithm. Through extensive simulations we were able to show that our smooth path planning algorithm outperformed a traditional Dubins' curve approach and our clustering algorithm was better in terms of response time over solutions to the equivalent Vehicle Routing Problem (VRP). Our mathematical analysis and simulations of the deployment problem show no statistical difference in the different tested strategies, but when testing collection strategies we found a much larger difference in performance and our proposed location prediction strategy performed the best. Finally, our simulations and analysis show our proposed heuristics for the task allocation problem with connectivity constraints was able to perform better than previous approaches.