Robotic Routers

From RSN
Jump to: navigation, search

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 [3], 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 [1] (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 [2], 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).

Related Papers

2012
6O. 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.
pdf,prelim.version,.bib
2011
5E. 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.
pdf,.bib
2010
4O. Tekdas, W. Yang, V. Isler
Robotic Routers: Algorithms and Implementation
Int. Journal of Robotics Research, 29(1), 2010.
pdf,.bib
2009
3O. 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.
pdf,.bib
2008
2E. Meisner, W. Yang, V. Isler
Network Formation through Coverage and Freeze-Tag
In Eighth International Workshop on the Algorithmic Foundations of Robotics, 2008.
pdf,.bib
1O. Tekdas, V. Isler
Robotic Routers
In Proc. IEEE Int. Conf. on Robotics and Automation, 2008.
pdf,.bib

Acknowledgment

This material is based upon work supported by the National Science Foundation under Grants 0916209 and 0917676.