The International Journal of Robotics Research

In indoor or urban applications, a moving robot with wireless communications will experience multipath fading. This causes rapid signal strength variations due to interfering reflections of the radio signal. By making short stops at positions with high signal-to-noise ratio (SNR), the robot can trade trajectory tracking accuracy for increased link quality. This represents a type of opportunistic communication-aware motion planning. We propose two novel strategies for improving the link capacity or throughput when either the robot has full knowledge of how the SNR varies along the trajectory, or when only the SNR distribution is known or can be estimated. In the latter case, this leads to an optimal stopping problem over a finite horizon. Both cases are analyzed for independent as well as correlated SNR samples, and a bounded maximum trajectory tracking error. We derive the resulting SNR distributions for the proposed strategies and use them to show how the expected capacity and throughput vary with the allowed tracking error. The results are confirmed by simulations and experiments. Experiments in six different locations validate the communication model and show that the proposed motion planning is robust to non-static fading and can yield throughput improvements of more than 100%.

Deploying a multi-robot team in confined environments poses multiple challenges that involve task and motion planning, localization and mapping, safe navigation, coordination of robots and also communications among all of them. In recent years, increasing attention has been paid to these challenges by the robotics community, but many problems remain unresolved. In this paper we address a technique for planning the deployment of a robot team in so-called fading environments, such as tunnels or galleries, where signal propagation presents specific characteristics. In order to maintain constant connectivity and high signal quality in the communication network formed by the robots and the base station, the robot deployment is driven by real-time signal measurements. First, an analysis of the signal propagation to obtain the general characteristic parameters of the signals in this kind of environment is carried out. Second, a technique which uses these parameters to drive the deployment is developed. A general strategy for this kind of environment in which the signals exhibit similar behavior is implemented. A complete system involving all of the above-mentioned robotics tasks has been developed. Finally, the system has been evaluated by means of simulation and in a real scenario.

Many applications of autonomy are significantly complicated by the need for wireless networking, with challenges including scalability and robustness. Radio accomplishes this in a complex environment, but suffers from rapid signal strength variation and attenuation typically much worse than free space loss. In this paper, we propose and test algorithms to autonomously discover the connectivity area for a base station in an unknown environment using an average of received signal strength (RSS) values and a RSS threshold to delineate the goodness of the channel. We combine region decomposition and RSS sampling to cast the problem as an efficient graph search. The nominal RSS in a sampling region is obtained by averaging local RSS samples to reduce the small-scale fading variation. The RSS gradient is exploited during exploration to develop an efficient approach for discovery of the base station connectivity boundary in an unknown environment. Indoor and outdoor experiments demonstrate the proposed techniques. The results can be used for sensing and collaborative autonomy, building base station coverage maps in unknown environments, and facilitating multi-hop relaying to a base station.

To accomplish cooperative tasks, robotic systems are often required to communicate with each other. Thus, maintaining connectivity of the communication graph is a fundamental issue in the field of multi-robot systems. In this paper we present a completely decentralized control strategy for global connectivity maintenance of the communication graph. Considering the disk communication model, we describe a gradient-based control strategy that exploits decentralized estimation of the algebraic connectivity. Unlike previous approaches available in the literature, the proposed control algorithm solves the global connectivity problem in a decentralized manner providing theoretical guarantees, without requiring maintenance of the local connectivity between robotic systems. Moreover, results obtained with simulations and experiments on real robots are described for demonstrating the efficacy of the proposed algorithm.

Mixed Wireless Sensor Network (WSN) is a network that consists of static and mobile sensor nodes. This article presents a collaborative framework where a team of autonomous mobile sensor nodes navigate through a sparse network with static sensors to improve the overall area coverage and search for events that may have occurred in areas not monitored by the static network. The mobile sensor nodes have limited communication and sensing ranges and collaborate to autonomously and dynamically decide their trajectories to enhance the area coverage, avoiding obstacles and collisions and adapting to new information such as failures of static nodes. In the context of the proposed framework, one can address various trade-offs. Examples include the trade off between the area coverage and the energy cost in terms of traveled distance and the one between the area coverage and information exchange among the mobile nodes. Furthermore, the proposed framework can be used to address spatially adaptive sampling. Finally, the proposed framework has been evaluated under different scenarios and has been shown to perform very well.

We design persistent surveillance strategies for the quickest detection of anomalies taking place in an environment of interest. From a set of predefined regions in the environment, a team of autonomous vehicles collects noisy observations, which a control center processes. The overall objective is to minimize detection delay while maintaining the false-alarm rate below a desired threshold. We present joint (i) anomaly detection algorithms for the control center and (ii) vehicle routing policies. For the control center, we propose parallel cumulative sum (CUSUM) algorithms (one for each region) to detect anomalies from noisy observations. For the vehicles, we propose a stochastic routing policy, in which the regions to be visited are chosen according to a probability vector. We study stationary routing policy (the probability vector is constant) as well as adaptive routing policies (the probability vector varies in time as a function of the likelihood of regional anomalies). In the context of stationary policies, we design a performance metric and minimize it to design an efficient stationary routing policy. Our adaptive policy improves upon the stationary counterpart by adaptively increasing the selection probability of regions with high likelihood of anomaly. Finally, we show the effectiveness of the proposed algorithms through numerical simulations and a persistent surveillance experiment.

We propose scale-free coordinates as an alternative coordinate system for multi-robot systems with large robot populations. Scale-free coordinates allow each robot to know, up to scaling, the relative position and orientation of other robots in the network. We consider a weak sensing model where each robot is only capable of measuring the angle, relative to its own heading, to each of its neighbors. Our contributions are three-fold. First, we derive a precise mathematical characterization of the computability of scale-free coordinates using only bearing measurements, and we describe an efficient algorithm to obtain them. Second, through simulations we show that even in graphs with low average vertex degree, most robots are able to compute the scale-free coordinates of their neighbors using only two-hop bearing measurements. Finally, we present an algorithm to compute scale-free coordinates that is tailored to low-cost systems with limited communication bandwidth and sensor resolution. Our algorithm mitigates the impact of sensing errors through a simple yet effective noise sensitivity model. We validate our implementation with real-world robot experiments using static accuracy measurements and a simple scale-free motion controller.

Many multi-robot scenarios involve navigation of a set of networked robots through a constrained environment to achieve coverage, maintain a predefined shape, sense at predefined locations, or to satisfy some other distance-defined property. When new robots and tasks are added to a network of already deployed interchangeable robots, a trade-off arises in seeking to minimize cost to execute the tasks and the level of disruption to the system. This paper examines a navigation-oriented variant of this problem in which robots are physically routed through an existing network. We propose a parametrizable method to tune emphasis between minimizing global travel cost (or energy, or distance), minimizing interruption (i.e. obtaining the fewest number of robot reassignments), reducing travel distance per robot, and completing all operations as soon as possible. Since these are related optimization criteria, a single parameter provides sufficient flexibility to balance between them.

Paths through the network are computed via a task-allocation formulation in which destination locations of newly deployed robots are added as tasks to an existing allocation. We adapt the graph matching variant of the Hungarian Algorithm—originally designed to solve the optimal assignment problem in complete bipartite graphs—to construct routing paths in sparse networks. We do this by constructing a three-dimensional graph that incorporates logical aspects of the Hungarian bipartite graph, and spatial elements of the Euclidean graph. The approach has several useful features including being particularly effective at generating multiple simultaneous, non-interfering paths. When new agent–task pairs are inserted, the assignment is globally reallocated in an incremental fashion so that it requires only linear time when the robots’ traversal options have bounded degree. The algorithm is studied systematically in simulation and also validated with physical robots.

Task allocation is an important aspect of many multi-robot systems. The features and complexity of multi-robot task allocation (MRTA) problems are dictated by the requirements of the particular domain under consideration. These problems can range from those involving instantaneous distribution of simple, independent tasks among members of a homogenous team, to those requiring the time-extended scheduling of complex interrelated multi-step tasks for members of a heterogenous team related by several constraints. The existing widely used taxonomy for task allocation in multi-robot systems was designed for problems with independent tasks and does not deal with problems with interrelated utilities and constraints. While that taxonomy was a ground-breaking contribution to the MRTA literature, a survey of recent work in MRTA reveals that it is no longer a sufficient taxonomy, due to the increasing importance of interrelated utilities and constraints in realistic MRTA problems under consideration. Thus, in this paper, we present a new, comprehensive taxonomy, iTax, that explicitly takes into consideration the issues of interrelated utilities and constraints. Our taxonomy maps categories of MRTA problems to existing mathematical models from combinatorial optimization and operations research, and hence draws important parallels between robotics and these fields.

Human-Machine Collaborative Systems for Microsurgical Applications by D. Kragic, P. Marayong, M. Li, A.M. Okamura, and G.D.Hager

The International Journal of Robotics Research, 24: 9, (September 2005), p. 731. doi:10.1177/0278364905057059

Publisher’s Statement

The Publisher wishes to include a reference to Dr. Rajesh Kumar’s Ph.D. thesis, entitled “An Augmented Steady Hand System for Precise Micromanipulation,” Johns Hopkins University, Baltimore MD (April 2001), which describes a framework for task level control on the Steady Hand Robot at JHU and which reports demonstrations of several representative tasks, including retinal cannulation, on dry lab and ex-vivo phantoms. The Publisher also refers to Figure 5 of the Article and wishes to reference the depiction of retinal cannulation in Dr. Kumar’s thesis, which reflects a task sequence that was performed for Dr. Kumar’s thesis and is depicted in the thesis as Figure 5.13.