The traditional approach to provide network connectivity is to deploy a network of stationary wireless routers which covers the entire area of interest. We can use the mobility and communication capabilities of mobile robots to provide appealing solutions where stationary networks might be costly if not infeasible.
One such scenario is when the user who requests connectivity service is a mobile entity (e.g. a human, a robot). Robotic routers (mobile robots with wireless communication capabilities) can create an adaptive wireless network and provide communication services for mobile users on-demand. Robotic routers are especially appealing for applications in which there is a single user whose connectivity to a base station must be maintained in an environment which is large compared to the wireless range. Following video shows three simulations where 1 (at most 2) robotic routers provide a continuous communication for a mobile user where stationary network solution requires at least 4 routers.
In , we presented motion strategies of robotic routers such that a mobile user is continuously connected to a static base station while minimizing the number of robotic routers required. Communication model tells us whether two points in the environment are connected or not and our solutions work for any given communication model. We considered two motion models for the mobile user. In the first model, we assume that the trajectory of the mobile user is known. This assumption is valid, for example, when the mobile user is a controlled entity whose trajectory is pre-programmed. In the second model, we considered a worst case scenario in which the mobile user is an adversarial entity who tries to break the communication as soon as possible. For both models, we presented optimal solutions and a proof of concept implementation in  (See also the following videos.).
The results above work for any environment and communication model. However, when the number of routers is large, the algorithms become computationally expensive. To address this, we are currently working on obtaining polynomial time algorithms for a geometric version of the robotic routers problem. We focus on a communication model where two points are connected if the geodesic-distance is less than a threshold. For this version, we have the following results so far:
- If the environment is simply-connected, we can obtain the optimal solution.
- If there is a single obstacle, we present a constant factor approximation.
- For the general case where there are h obstacles, we present an O(h)-approximation.
We are currently working on improving the approximation factor of the O(h)-approximation algorithm.
Building Communication Bridges
Another scenario when mobile robots can be helpful is when a communication bridge between two locations is needed and an underlying communication infrastructure does not exist. For example, when fighting forest fires, a high capacity connection between the command center and a temporary base may be needed. We can use robots as mobile hubs to create this communication bridge between command center and the base. In a recent paper , we studied a new bi-criteria optimization problem where the objectives are (i) minimizing the number of hubs on the bridge, and (ii) either the maximum or the total distance traveled by the hubs. For a geometric version of the problem where the hubs must move onto the line segment between two locations, we presented algorithms which achieve the minimum number of hubs while remaining within a constant factor of the given motion constraint (maximum or total distance).
|6||O. Tekdas, Y. Kumar, V. Isler, R. Janardan|
Building a Communication Bridge With Mobile Hubs
IEEE Tran. on Automation Science and Engineering, 9(1): 171--176, 2012.
|5||E. Stump, N. Michael, V. Kumar, V. Isler|
Visibility-Based Deployment of Robot Formations for Communication Maintenance.
In Proc. IEEE Int. Conf. on Robotics and Automation, 2011.
|4||O. Tekdas, W. Yang, V. Isler|
Robotic Routers: Algorithms and Implementation
Int. Journal of Robotics Research, 29(1), 2010.
|3||O. Tekdas, Y. Kumar, V. Isler, R. Janardan|
Building a Communication Bridge with Mobile Hubs
In 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), 2009.
|2||E. Meisner, W. Yang, V. Isler|
Network Formation through Coverage and Freeze-Tag
In Eighth International Workshop on the Algorithmic Foundations of Robotics, 2008.
|1||O. Tekdas, V. Isler|
In Proc. IEEE Int. Conf. on Robotics and Automation, 2008.
This material is based upon work supported by the National Science Foundation under Grants 0916209 and 0917676.