Overview
Information can be used as a mobile robot localizability metric -- a tool for computing the ability of different regions in an environment to aid in robot localization. In particular, for each region in the environment, the information computes the change in estimation entropy expected for a robot (utilizing Markov Localization) in this area. This project studies the use of combining information and a bandwidth utilization metric into a navigation map for a mobile robot embedded in a wireless sensor network. This approach allows for planning paths that can manage the trade-off between localization accuracy, consumption of shared network bandwidth, and path length. These maps also show promise as a tool for determining deployment topologies and maintenance schemes for ensuring consistent levels of localization in the face of mote failures. We have demonstrated that this technique is effective for generating paths that increase the accuracy of localization while requiring fewer detections.
Setup
Figure setup-1: The robot model: a basic positional kinematic model with Normally distributed input noise.
Figure setup-2: The sensor model: a binary sensor with a circular detection area.
The aim of this project is to develop a way-point navigation controller for a robot navigating in a wireless sensor network. To this end, the robot is required to localized itself using only detections of itself provided by the sensor network. It must be able to localize itself well enough to enable the way-point navigation to be effective. Furthermore, since bandwidth is an expensive commodity for wireless sensor networks, we want a navigation and localization system that minimizes the sensor network bandwidth utilized. Finally, our navigation system should also account for path length -- avoiding long paths between way-points if possible. Of course, even more useful, would be a navigation system that is tunable: allowing the user to manage the trade off between navigation efficiency, bandwidth utilization, and path length.
To begin, we assume a simple kinematic model for the robot (see Figure setup-1). With this model, we assume that any complexities presented by the robot's dynamics can be handled by a lower level control system. We assume that our robot's state lives in the 2-dimensional area of the sensor network, and that our control directly adjusts the robot's position. Furthermore, we assume that our control is bounded (typically, a simple bound on the norm of the control input), and we assume that the control noise is Normally distributed with variance determined as a function of the control magnitude.
For the sensor network, we model each sensor as a binary sensor with a circular detection region. In particular, we assume that each sensor can be located anywhere in the playing field (typically a square area in R^2), and that it will detect a robot with probability of p_s within a detection radius of r_s from the mote's location. Outside this detection area, the robot will not be detected. Finally, for the following simulations, we will take the playing field to be 100m by 100m, the detection diameter of each sensor to be 10m, and the detection probability to be 90%. We will assume the robot starts in the lower-left quadrant of the field and that 30 motes have been Uniformly distributed across the playing area.
Navigation Metrics
Figure navigation-1: An example information map: the color of each region represents how well the region is expected to localize the robot. Mote locations are denoted by outlined white dots and detection radius are indicated by the circular dashed blue lines.
Figure navigation-2: An example detection map: the color of each region represents how many detections the sensor network is expected to emit for a robot in this region. Mote locations are denoted by outlined white dots and detection radius are indicated by the circular dashed blue lines.
Figure navigation-3: A typical method for computing our value metric. Information is converted into a metric that approximates the expected decrease in estimation support area; the detection metric is converted into a metric quantifying expected remaining bandwidth. Finally, region by region, the product of these two quantities is defined as value.
Figure navigation-4: An example value map: the color of each region represents how well this region is expected to localize the robot and how much bandwidth it is expected to conserve. Mote locations are denoted by outlined white dots and detection radius are indicated by the circular dashed blue lines.
In order to develop a navigation system that can manage the efficiency of localization and the utilization of bandwidth, we first need ways to measure these quantities. The ability of a sensor system to localize the robot (called, localizability) can be found in several ways. Our localization system will be utilizing Markov localization to transform the control inputs and sensor network detections into an estimate of the robot's state. To this end, we can take advantage of a technique previously developed by Roy et al (see the paper "Coastal Navigation - Mobile Robot Navigation with Uncertainty in Dynamic Environments") to estimate the localizability of each region in the playing field. In particular, this technique computes localizability of a region as the information of a region -- the expected change in robot's estimation entropy (due to Markov localization). This technique assumes that a robot arrives at the region in question with a predetermined prior (estimate of its location), and once at the region, receives a measurement from its sensors (or sensor network, in our case). Using this measurement (and assuming that the prior accounts for the proprioceptive update step of Markov localization), the Markov localization can then adjust its estimate of the robot's location. The information of this measurement is defined as the change in estimation entropy. Since, the measurement provided by the sensor network is not known a priori, the expectation over all possibly sensor values is taken. This provides us with a localizability metric that we can compute for any point in the playing field. We tessellate the playing field into a regular grid and apply this technique to each grid cell. An example of the resulting region by region information computation, or "information map", is shown in Figure navigation-1.
Next, we need a metric for the bandwidth utilization of our navigation system. Since the robot does not have explicit control over the sensor network detections, we turn to looking at bandwidth utilization by region. Furthermore, since we are focusing only on the bandwidth used for detecting the robot, we will shift from computing bandwidth utilization to computing the number of detection messages. We will define this metric over the same tessellation used for the localizability metric. In particular, for each region, we compute the expectation of the total number of sensor network detections. The number of detections is simply the sum of indicator functions for detections from motes close enough to detect the robot. An example of the resulting detection map is shown in Figure navigation-2.
Finally, to allow our navigation system to process both the information map and the detection map, we combine these into one map. This map, called the value map, represents the value for a robot to be in a particular region, in terms of localizability and bandwidth utilization. This value can be computed in many ways depending on the requirements of the system. In our case, we typically compute the value for a region as the product of the amount of "estimation area decrease" for a region and the "remaining bandwidth" for a region. The meaning of these terms is explained in Figure navigation-3. Finally, an example of the resulting value map is shown in Figure navigation-4.
Path Planners
Figure path-1: A comparison of path planning techniques. A path planner combines a map (information, detection, or value) with a planning technique (grid-based or cluster-based) to generate a path.
At this point, for each region, we have a method of computing 3 quantities: the localizability, the expected number of detections, and a combination of the two quantities. We now require a system that can plan a path between 2 given way points that utilizes these quantities. Dynamic programming is a great solution for this. All that is required for dynamic programming is a graph (representing candidate intermediate way points, the starting point, and the ending point) with non-negative edge weights (representing the "cost to go" from one point to the next). From this, we develop 2 types of path planners: a grid-based planner and a clusters-based planner (see Figure path-1).
The grid-based planner simply supplies the entire tessellated field as the graph, allowing adjacent grid cells to be connected to each other. Then, the cost function is defined as a combination of distance (favoring shorter paths) and one of our previous metrics (information, detections, or value). In the case of information, we call this planner the "information grid" planner; in the case of value, we call it the "value grid" planner.
The clusters-based path planner chooses the vertices for the graph using one of our previous metrics. In particular, it looks for regions (or clusters of regions) that rate high according to one of these metrics. A predetermined number of these regions are chosen such that they are not too close together; these are used as the vertices for the graph. We then assign edges between all vertices based on the exponential of the distance between vertices. This creates a planner that favors lots of little jumps to the destination instead of one big one. In the case that this planner used the information map to generate the vertices, we call it the "information clusters" path planner; in the case that value was used, we call it the "value clusters" planner.
Finally, we generate one more path planning variant. This planner is developed in order to compare our planners with the naive approach that simple drives the robot directly through mote locations along its way to the destination. This idea is captured by applying the clusters path planning approach where the graph vertices are chosen as the mote locations. We call this planner the "node centers" planner.
Simulation
Figure simulation-1: Illustration of the types of path planners used by the simulation.
Figure simulation-2: Simulation results comparing several path planners. Results shown are the mean across trials and simulation sets.
We now have a method for intelligently planning paths in a wireless sensor network. Furthermore, by adding the Markov localization system and wrapping it all with a simple feedback controller, we have a robot control system that can navigate in a sensor network. We compare our path planners in simulation with several naive planners (see Figure simulation-1). In particular, for each run of the simulation, we deploy the nodes Uniformly on the field, we generate an initial position for the robot, we generate 3 way-points, and we plan paths using various techniques. Each simulation is run 100 times. Finally, we run 10 sets of simulations -- each with a new mote deployment topology.
After the simulations, we collect several metrics to compare the different path planning techniques (see Figure simulation-2). From these graphs, we see that all of the naive approaches, save the node centers approach, produce higher estimation error and entropy. This is to be expected; furthermore, had our mote topology been more sparse, these techniques would often fail to even keep the robot from getting lost. Next, we turn to the node centers technique. This technique does better at reducing localization error at the cost of bandwidth utilization in comparison to the other naive approaches. By directing the robot through the mote locations, this technique generates a significantly higher number of detections though.
Next, we turn to the intelligent path planner techniques. We note that these achieve the best localization while using the least amount of bandwidth. They additionally reduce the travel time in comparison to the node centers technique. In particular, we focus on the value clusters planner which reduces localization error by 27.4% and reduces the required number of detections by 65.5% over the node centers planner. The bandwidth reduction is especially favorable for a bandwidth constrained system like a wireless sensor network. Finally, we note that the three intelligent path planners shown offer good performance depending on the designer's requirements. The information clusters planner produces the most accurate localization at the cost of extra bandwidth; the value clusters planner reduces this bandwidth requirement at the cost of localization accuracy; and, the value grid planner gives up some localization accuracy in order to reduce the travel time. Overall, we have demonstrated that the aforementioned intelligent path planning techniques are useful for robots navigating in bandwidth constrained sensor networks.