Mobile robots can be used as mobile hubs to provide communication services on-demand. This capability is especially valuable in disaster response scenarios where there is no communication infrastructure. In such scenarios, mobile hubs can provide a communication infrastructure in a dynamic fashion. In this paper, we study the problem of building a communication bridge between a source s and a destination t with mobile robots. Given a set of robots P and their initial locations, our goal is to find a subset S of robots and their final locations such that the robots in S create a communication bridge between s and t in their final locations. We introduce a new optimization problem for building communication bridges. The objective is to minimize the number of hubs (i.e., |S|), while simultaneously minimizing the robots' motion. The two mobility measures studied in this paper are: (i) maximum travel distance and (ii) total travel distance of the robots. For a geometric version of the problem where the robots must move onto the line segment [s, t], we present polynomial time algorithms which use the minimum number of hubs while remaining within a constant factor of a given motion measure.

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 mobile user whose connectivity to a base station must be maintained in an environment that is large compared to the wireless range. In this paper, we study the problem of computing motion strategies for robotic routers in such scenarios, as well as the minimum number of robotic routers necessary to enact our motion strategies. Assuming that the routers are as fast as the user, we present an optimal solution for cases where the environment is a simply-connected polygon, a constant factor approximation for cases where the environment has a single obstacle, and an O(h) approximation for cases where the environment has h circular obstacles. The O(h) approximation also holds for cases where the environment has h arbitrary polygonal obstacles, provided they satisfy certain geometric constraints - e.g. when the set of their minimum bounding circles is disjoint.

Robots operating in a workspace can localize themselves by querying nodes of a sensor-network deployed in the same workspace. This paper addresses the problem of computing the minimum number and placement of sensors so that the localization uncertainty at every point in the workspace is less than a given threshold. We focus on triangulation-based state estimation, where measurements from two sensors must be combined for an estimate. This problem is NP-hard in its most general from. For the general version, we present a solution framework based on integer linear programming and demonstrate its application in a fire-tower placement task. Next, we study the special case of bearing-only localization and present an approximation algorithm with a constant factor performance guarantee.

Mobile robots equipped with wireless networking capabilities can act as robotic routers and provide network connectivity to mobile users. Robotic routers provide cost efficient solutions for deployment of a wireless network in a large environment with limited number of users. In this paper, we present motion planning algorithms for robotic routers to maintain the connectivity of a single user to a base station. We consider two motion models for the user. In the first model, we assume that the target's motion is known in advance. In the second model, user moves in an adversarial fashion and tries to break the connectivity.

Robots operating in a workspace can localize themselves by querying nodes of a sensor-network deployed in the same workspace. This paper addresses the problem of computing the minimum number and placement of sensors so that the localization uncertainty at every point in the workspace is less than a given threshold. We focus on triangulation based state estimation where measurements from two sensors must be combined for an estimate. We show that the general problem for arbitrary uncertainty models is computationally hard. For the general problem, we present a solution framework based on integer linear programming and demonstrate its practical feasibility with simulations. Finally, we present an approximation algorithm for a geometric uncertainty measure which simultaneously addresses occlusions, angle and distance constraints.