Stochastic Event Capture Using Mobile Sensors Subject to a Quality Metric

Mobile sensors cover more area over a fixed period of time than do the same number of stationary sensors. However, the quality of coverage (QoC) achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed, and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper, we consider the following event capture problem: the events of interest arrive at certain points in the sensor field and disappear according to known arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. We analyze how the QoC scales with velocity, path, and number of mobile sensors. We characterize cases where the deployment of mobile sensors has no advantage over static sensors, and find the optimal velocity pattern that a mobile sensor should adopt. We also present algorithms for two motion planning problems: 1) for a single sensor, what is the sensor trajectory and the minimum speed required to satisfy a bound on the event loss probability and 2) for sensors with fixed speed, what is the minimum number of sensors required to satisfy a bound on the event loss probability. When the robots are restricted to move along a line or a closed curve, our algorithms return the optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor of 2 of the optimal solution. For the case where the events occur at arbitrary points on a plane, we present heuristic algorithms for the aforementioned motion planning problems and bound their performance with respect to the optimal.     

Primal and dual-based algorithms for sensing range adjustment in WSNs

Coverage and tracking of multiple targets, are viewed as important challenges in WSNs, mainly aimed for future ubiquitous and pervasive applications. Target coverage in WSNs with large numbers of sensor nodes and targets, and with a predefined placement of sensors, may be conducted through adjusting the sensing range and considering the energy consumption related to this operation. In this paper, we encounter the problem of multiple target coverage in WSNs by determining the sensing range of each sensor node to maximize the total utility of the network. We solve this Network Utility Maximization (NUM) problem via two approaches, primal and dual decompositions, which result in iterative distributed price-based algorithms. Convergence of sensing ranges to optimal values is proved by means of stability analysis and simulation experiments. Simulation results show convergence to optimal values in few iterations, with near optimal values for the total objective function and energy consumption of nodes. These results show scalability of our algorithm, in terms of the number of iterations needed for convergence when compared with the other two methods. Furthermore, the distributed algorithm based on dual decomposition is used to cover efficiently moving targets in consecutive time intervals.     

Heterogeneous Teams of Modular Robots for Mapping and Exploration

In this article, we present the design of a team of heterogeneous, centimeter-scale robots that collaborate to map and explore unknown environments. The robots, called Millibots, are configured from modular components that include sonar and IR sensors, camera, communication, computation, and mobility modules. Robots with different configurations use their special capabilities collaboratively to accomplish a given task. For mapping and exploration with multiple robots, it is critical to know the relative positions of each robot with respect to the others. We have developed a novel localization system that uses sonar-based distance measurements to determine the positions of all the robots in the group. With their positions known, we use an occupancy grid Bayesian mapping algorithm to combine the sensor data from multiple robots with different sensing modalities. Finally, we present the results of several mapping experiments conducted by a user-guided team of five robots operating in a room containing multiple obstacles.     

Using Sensor Morphology for Multirobot Formations

In formation-maintenance (formation control) tasks, robots maintain their relative position with respect to their peers, according to a desired geometric shape. Previous work has examined formation-maintenance algorithms, based on formation control graphs, that ensure the theoretical stability of the formation. However, an exponential number of stable controllers exists. Thus a key question is how to select (construct) a formation controller that optimizes desired properties, such as sensor usage. We present a novel representation of the sensing capabilities of robots in formations, using a monitoring multigraph. We first show that graph-theoretic techniques can then be used to efficiently compute optimal sensing policies that maintain a given formation, while minimizing sensing costs. In particular, separation-bearing (distance-angle) control targets are automatically constructed for each individual robot in the formation, taking into account its specific sensor morphology. Then, we present a protocol allowing control graphs to be switched on line, to allow robots to adjust to sensory failures. We report on results from comprehensive experiments with physical and simulated robots. The results show that the use of the dynamic protocol allows formations of real robots to move significantly faster and with greater precision, while reducing the number of formation failures, due to sensor limitations. We also evaluate the sensitivity of our approach to communication reliability, and discuss opportunities and challenges raised by our approach.     

A Bayesian exploration-exploitation approach for optimal online sensing and planning with a visually guided mobile robot

We address the problem of online path planning for optimal sensing with a mobile robot. The objective of the robot is to learn the most about its pose and the environment given time constraints. We use a POMDP with a utility function that depends on the belief state to model the finite horizon planning problem. We replan as the robot progresses throughout the environment. The POMDP is high-dimensional, continuous, non-differentiable, nonlinear, non-Gaussian and must be solved in real-time. Most existing techniques for stochastic planning and reinforcement learning are therefore inapplicable. To solve this extremely complex problem, we propose a Bayesian optimization method that dynamically trades off exploration (minimizing uncertainty in unknown parts of the policy space) and exploitation (capitalizing on the current best solution). We demonstrate our approach with a visually-guide mobile robot. The solution proposed here is also applicable to other closely-related domains, including active vision, sequential experimental design, dynamic sensing and calibration with mobile sensors.     

Efficient terrain coverage for deploying wireless sensor nodes on multi-robot system

Coverage and connectivity are the two main functionalities of wireless sensor network. Stochastic node deployment or random deployment almost always cause hole in sensing coverage and cause redundant nodes in area. In the other hand precise deployment of nodes in large area is very time consuming and even impossible in hazardous environment. One of solution for this problem is using mobile robots with concern on exploration algorithm for mobile robot. In this work an autonomous deployment method for wireless sensor nodes is proposed via multi-robot system which robots are considered as node carrier. Developing an exploration algorithm based on spanning tree is the main contribution and this exploration algorithm is performing fast localization of sensor nodes in energy efficient manner. Employing multi-robot system and path planning with spanning tree algorithm is a strategy for speeding up sensor nodes deployment. A novel improvement of this technique in deployment of nodes is having obstacle avoidance mechanism without concern on shape and size of obstacle. The results show using spanning tree exploration along with multi-robot system helps to have fast deployment behind efficiency in energy.     

Coordinated multi-robot exploration

In this paper, we consider the problem of exploring an unknown environment with a team of robots. As in single-robot exploration the goal is to minimize the overall exploration time. The key problem to be solved in the context of multiple robots is to choose appropriate target points for the individual robots so that they simultaneously explore different regions of the environment. We present an approach for the coordination of multiple robots, which simultaneously takes into account the cost of reaching a target point and its utility. Whenever a target point is assigned to a specific robot, the utility of the unexplored area visible from this target position is reduced. In this way, different target locations are assigned to the individual robots. We furthermore describe how our algorithm can be extended to situations in which the communication range of the robots is limited. Our technique has been implemented and tested extensively in real-world experiments and simulation runs. The results demonstrate that our technique effectively distributes the robots over the environment and allows them to quickly accomplish their mission.     

Robotic data mules for collecting data over sparse sensor fields

We present a robotic system for collecting data from wireless devices dispersed across a large environment. In such applications, deploying a network of stationary wireless sensors may be infeasible because many relay nodes must be deployed to ensure connectivity. Instead, our system utilizes robots that act as data mules and gather the data from wireless sensor network nodes. We address the problem of planning paths of multiple robots so as to collect the data from all sensors in the shortest time. In this new routing problem, which we call the data gathering problem (DGP), the total download time depends on not only the robots' travel time but also the time to download data from a sensor and the number of sensors assigned to the robot. We start with a special case of DGP in which the robots' motion is restricted to a curve that contains the base station at one end. For this version, we present an optimal algorithm. Next, we study the two‐dimensional version and present a constant factor approximation algorithm for DGP on the plane. Finally, we present field experiments in which an autonomous robotic data mule collects data from the nodes of a wireless sensor network deployed over a large field. © 2011 Wiley Periodicals, Inc.     

RANGE–Robust autonomous navigation in GPS‐denied environments

This paper addresses the problem of autonomous navigation of a micro air vehicle (MAV) in GPS‐denied environments. We present experimental validation and analysis for our system that enables a quadrotor helicopter, equipped with a laser range finder sensor, to autonomously explore and map unstructured and unknown environments. The key challenge for enabling GPS‐denied flight of a MAV is that the system must be able to estimate its position and velocity by sensing unknown environmental structure with sufficient accuracy and low enough latency to stably control the vehicle. Our solution overcomes this challenge in the face of MAV payload limitations imposed on sensing, computational, and communication resources. We first analyze the requirements to achieve fully autonomous quadrotor helicopter flight in GPS‐denied areas, highlighting the differences between ground and air robots that make it difficult to use algorithms developed for ground robots. We report on experiments that validate our solutions to key challenges, namely a multilevel sensing and control hierarchy that incorporates a high‐speed laser scan‐matching algorithm, data fusion filter, high‐level simultaneous localization and mapping, and a goal‐directed exploration module. These experiments illustrate the quadrotor helicopter's ability to accurately and autonomously navigate in a number of large‐scale unknown environments, both indoors and in the urban canyon. The system was further validated in the field by our winning entry in the 2009 International Aerial Robotics Competition, which required the quadrotor to autonomously enter a hazardous unknown environment through a window, explore the indoor structure without GPS, and search for a visual target. © 2011 Wiley Periodicals, Inc.     

Robot Motion Planning: A Game-Theoretic Foundation

Analysis techniques and algorithms for basic path planning have become quite valuable in a variety of applications such as robotics, virtual prototyping, computer graphics, and computational biology. Yet, basic path planning represents a very restricted version of general motion planning problems often encountered in robotics. Many problems can involve complications such as sensing and model uncertainties, nonholonomy, dynamics, multiple robots and goals, optimality criteria, unpredictability, and nonstationarity, in addition to standard geometric workspace constraints. This paper proposes a unified, game-theoretic mathematical foundation upon which analysis and algorithms can be developed for this broader class of problems, and is inspired by the similar benefits that were obtained by using unified configuration-space concepts for basic path planning. By taking this approach, a general algorithm has been obtained for computing approximate optimal solutions to a broad class of motion planning problems, including those involving uncertainty in sensing and control, environment uncertainties, and the coordination of multiple robots. Received November 11, 1996; revised March 13, 1998.     

Robot Formations Using a Single Camera and Entropy-based Segmentation

This work presents a new problem along with our new algorithm for a multi-robot formation with minimally controlled conditions. For multi-robot cooperation, there have traditionally been prevailing assumptions in order to collect the necessary information. These assumptions include the existence of communication systems among the robots or the use of specialized sensors such as laser scanners or omnidirectional cameras. However, they are not always valid, especially in emergency situations or with miniature robots. We, therefore, need to deal with the conditions that have received less attention in research regarding a multi-robot formation. There are several challenges: (1) less information is available than the well-known formation algorithms assume, (2) following strategies for deformable shapes in a formation with only local information available are needed, and (3) target segmentation without any markers is required. This work presents a formation algorithm based on a visual tracking algorithm, including how to process the image measurements provided by a single monocular camera. Through several experiments with real robots (developed at the University of Minnesota), we show that the proposed algorithms work well with minimal sensing information.     

Distributed algorithms for barrier coverage using relocatable sensors

We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study a barrier coverage problem in the distributed and discrete setting. We assume that we have n identical sensors located at grid positions on the barrier, and that each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within \(\varTheta (n^2)\) steps with the barrier fully covered, while the constant-memory algorithm is shown to take \(\varTheta (n)\) steps to terminate in the worst case. Since any algorithm in which a sensor can only move a constant distance in one step requires \(\varOmega (n)\) steps on some inputs, our second algorithm is asymptotically optimal.     

Intelligent and Efficient Strategy for Unstructured Environment Sensing Using Mobile Robot Agents

In field environments it is not usually possible to provide robots in advance with valid geometric models of its task and environment. The robot or robot teams need to create these models by scanning the environment with its sensors. Here, an information-based iterative algorithm to plan the robot's visual exploration strategy is proposed to enable it to most efficiently build 3D models of its environment and task. The method assumes mobile robot (or vehicle) with vision sensors mounted at a manipulator end-effector (eye-in-hand system). This algorithm efficiently repositions the systems' sensing agents using an information theoretic approach and fuses sensory information using physical models to yield a geometrically consistent environment map. This is achieved by utilizing a metric derived from Shannon's information theory to determine optimal sensing poses for the agent(s) mapping a highly unstructured environment. This map is then distributed among the agents using an information-based relevant data reduction scheme. This method is particularly well suited to unstructured environments, where sensor uncertainty is significant. Issues addressed include model-based multiple sensor data fusion, and uncertainty and vehicle suspension motion compensation. Simulation results show the effectiveness of this algorithm.     

Collaborative Robot Exploration and Rendezvous: Algorithms, Performance Bounds and Observations

We consider the problem of how two heterogeneous robots can arrange to meet in an unknown environment from unknown starting locations: that is, the problem of arranging a robot rendezvous. We are interested, in particular, in allowing two robots to rendezvous so that they can collaboratively explore an unknown environment. Specifically, we address the problem of how a pair of exploring agents that cannot communicate with one another over long distances can meet if they start exploring at different unknown locations in an unknown environment.We propose several alternative algorithms that robots could use in attempting to rendezvous quickly while continuing to explore. These algorithms exemplify different classes of strategy whose relative suitability depends on characteristics of the problem definition. We consider the performance of our proposed algorithms analytically with respect to both expected- and worst-case behavior. We then examine their behavior under a wider set of conditions using both numerical analysis and also a simulation of multi-agent exploration and rendezvous. We examine the exploration speed, and show that a multi-robot system can explore an unknown environment faster than a single-agent system, even with the constraint of performing rendezvous to allow communication.We conclude with a demonstration of rendezvous implemented on a pair of actual robots.     

Motion strategies for exploration and map building under uncertainty with multiple heterogeneous robots

In this paper, we present a multi-robot exploration strategy for map building. We consider an indoor structured environment and a team of robots with different sensing and motion capabilities. We combine geometric and probabilistic reasoning to propose a solution to our problem. We formalize the proposed solution using stochastic dynamic programming (SDP) in states with imperfect information. Our modeling can be considered as a partially observable Markov decision process (POMDP), which is optimized using SDP. We apply the dynamic programming technique in a reduced search space that allows us to incrementally explore the environment. We propose realistic sensor models and provide a method to compute the probability of the next observation given the current state of the team of robots based on a Bayesian approach. We also propose a probabilistic motion model, which allows us to take into account errors (noise) on the velocities applied to each robot. This modeling also allows us to simulate imperfect robot motions, and to estimate the probability of reaching the next state given the current state. We have implemented all our algorithms and simulations results are presented.     

Evaluation of Sensors and Mapping Approaches for Disasters in Tunnels

Ground or aerial robots equipped with advanced sensing technologies, such as three‐dimensional laser scanners and advanced mapping algorithms, are deemed useful as a supporting technology for first responders. A great deal of excellent research in the field exists, but practical applications at real disaster sites are scarce. Many projects concentrate on equipping robots with advanced capabilities, such as autonomous exploration or object manipulation. In spite of this, realistic application areas for such robots are limited to teleoperated reconnaissance or search. In this paper, we investigate how well state‐of‐the‐art and off‐the‐shelf components and algorithms are suited for reconnaissance in current disaster‐relief scenarios. The basic idea is to make use of some of the most common sensors and deploy some widely used algorithms in a disaster situation, and to evaluate how well the components work for these scenarios. We acquired the sensor data from two field experiments, one from a disaster‐relief operation in a motorway tunnel, and one from a mapping experiment in a partly closed down motorway tunnel. Based on these data, which we make publicly available, we evaluate state‐of‐the‐art and off‐the‐shelf mapping approaches. In our analysis, we integrate opinions and replies from first responders as well as from some algorithm developers on the usefulness of the data and the limitations of the deployed approaches, respectively. We discuss the lessons we learned during the two missions. These lessons are interesting for the community working in similar areas of urban search and rescue, particularly reconnaissance and search.     

Efficient Algorithms for p-Self-Protection Problem in Static Wireless Sensor Networks

Wireless sensor networks have been widely used in many surveillance applications. Due to the importance of sensor nodes in such applications, certain level of protection need to be provided to them. We study the self protection problem for static wireless sensor networks in this paper. Self protection problem focuses on using sensor nodes to provide protection to themselves instead of the target objects or certain target area, so that the sensor nodes can resist the attacks targeting on them directly. A wireless sensor network is p-self-protected, if at any moment, for any wireless sensor (active or non-active), there are at least p active sensors that can monitor it. The problem finding minimum p-self-protection is NP-complete and no efficient self protection algorithms have been proposed. In this paper, we provide efficient centralized and distributed algorithms with constant approximation ratio for minimum p-self-protection problem in sensor networks with either homogeneous or heterogeneous sensing radius. In addition, we design efficient distributed algorithms to not only achieve p-self-protection but also maintain the connectivity of all active sensors. Our simulation confirms the performances of proposed algorithms.     

Cellular automaton-based algorithms for the dispersion of mobile wireless sensor networks

Due to the advent of sensor technology and its applications, mobile wireless sensor networks (MWSNs) have gained a significant amount of research interest. In a typical MWSN, sensors can move within the network. We develop a set of probabilistic and deterministic cellular automaton (CA)-based algorithms for motion planning problems in MWSNs. First, we consider a scenario where a group of sensors are deployed and they need to disperse in order to maximise the area covered by the network. In this variant of the problem we do not explicitly consider that the sensors should maintain the connectivity of the network while they move. Second, we consider a scenario where the sensors are initially randomly distributed and they need to disperse autonomously to both maximise the coverage of the network and maintain its connectivity. We carry out extensive simulations of both deterministic and randomised variants of the algorithms. For the first variant of the problem we compare our algorithms with one previous algorithm and find that our algorithm yields better network coverage than the earlier algorithm. We also find that probabilistic algorithms have better overall performance for the second variant. CA algorithms rely only on local information about the network and, hence, they can be used in practice for MWSN problems. On the other hand, locality of the algorithm implies that maintaining connectivity becomes a non-trivial problem.     

An efficient cooperative exploration strategy for wireless sensor network

Wireless sensor networks (WSNs) are used in several applications such as healthcare devices, aerospace systems, automobile industry, security monitoring. However, WSNs have several challenges to improve the efficiency, robustness, failure tolerance and reliability of these sensors. Thus, cooperation between sensors is an important deal that increases sensor trust. Cooperative WSNs can be used to optimize the exploration of an unknown area in a distributed way. In this paper, the distributed Markovian model strategy that is used due to their past state-dependent reasoning. Moreover, the exploration strategy depends totally on the wireless communication protocol. Hence, in this paper, we propose an efficient cooperative strategy based on cognitive radio and software-defined radio which are promising technologies that increase spectral utilization and optimize the use of radio resources. We implement a distributed exploration strategy (DES) in mobile robots, and several experiments have been performed to localize targets while avoiding obstacles. Experiments were performed with several exploration robots. A comparison with another exploration strategy shows that DES improves the robots exploration.     

Sector-based maximal online coverage of unknown environments for cleaning robots with limited sensing

Although cleaning robots have been increasingly popular in home environments, their coverage rate and performance has not been very impressive to their users, thus often hampering their user acceptance. Many complete coverage algorithms developed so far usually mandate the robot to have a sophisticated navigation system for precise localization. This requires the use of high-cost sensors as well as high computational power — thus not suitable for home environments. This paper presents a novel integrated coverage strategy for low-cost cleaning robots, yet demonstrating respectable coverage performance in most unknown environments. The proposed algorithm can efficiently cope with hardware limitations ranging from low computational power to numerous sensing problems arising from limited range, sparse data, and detection uncertainty. To facilitate a viable solution that can cope with these limitations, we first make two assumptions on the home environment — rectilinear and closed, which seems to be met in most of our home environments. Next, in order to effectively circumvent poor localization (low precision positioning), we decompose the space into sectors, with each sector being small enough to have reasonable localization accuracy within itself. Overall, the final outcome is a novel online coverage strategy that performs simultaneous exploration, incremental sector creation, sector cleaning, and localization, with the intention of maximizing performance with minimal sensing. Both simulation and real-world experiments validate the efficiency of our approach.