Overview
In July 2003, we demonstrated a mobile robot pursuit-evasion game on a medium-scale wireless sensor network. On an outdoor field, we deployed 100 motes in an 10 by 10 regular grid with 2 meter spacing for tracking a unmanned ground vehicle (UGV). Using landmark routing and periodic beacons from the robots, the sensor network provided the capability of wirelessly routing messages amongst motes and mobile robots. A human controlled evader robot driving in the field was detected by nearby motes using magnetometers. These detections were aggregated and relayed to the pursuer robot. Using these detections and an onboard D-GPS system, the pursuer localized itself and the evading robot and followed an intercept course to the evader. In all runs (about half a dozen), the pursuer successfully captured the evader.
The video below shows a few typical runs of our demonstration. The pursuer robot, the robot with a safety cone attached, is autonomously chasing the evader. The evader robot is controlled remotely by a human operator. Several of the motes can also be seen in the video.
Hardware
Figure hardware-2: A Pioneer mobile robot next to a mote.
Figure hardware-1: A Mica2Dot mote in the field.
We used 100 Mica2Dot motes (see Figure hardware-1) distributed on a regular grid -- 2 meters to a side. The Mica2Dot is equipped with an 8-bit 4MHz Atmel ATMEGA128L CPU with 128kB of instruction memory and 4kB of RAM. Additionally, it contains a low-power Chipcon CC1000 wireless radio for communicating with other motes. The Mica2Dot mote has an ultrasonic transceiver for self-localization and a magnetometer to detect vehicles. The mobile robots we utilized (see Figure hardware-2) are Pioneer robots from ActivMedia. Each robot has an on-board Linux computer with a 266MHz Pentium2 CPU, 128MB of RAM, a 20GB hard drive, and a 802.11 wireless radio. Additionally, the robots are equipped with a D-GPS system capable of localizing the robot to within 2cm every 0.1 seconds. Additionally, we equipped the robots with a mote so they may send and receive messages from the sensor network.
Software
Figure software-1: The software services utilized by the robot and sensor network.
The various software services used for our demonstration are shown in Figure software-1. Services can be divided into those executing on the mote (written in NesC running on TinyOS) and those running on the robot (written in Python, Java, and C++ running on Linux). The mote has services for interacting with its environment, such as (ultrasonic) ranging and (magnet) sensing. It also has network level services for sharing and routing information (see Routing), reprogramming, and on-the-fly configuration. Finally, the mote has application-level services, such as those for choosing local detection leaders and aggregating several detections into a single message. The pursuer robot has services for estimating the state of the game, such as estimating its location (from D-GPS) and estimating the evader's location (from sensor network detection messages). Finally, the pursuer has services for chasing the evader such as navigation and path following.
Information Flow
Figure info-1: The flow of information during the pursuit-evasion game.
In order for the pursuer to chase the evader, the pursuer needs information about the location of the evader. This is accomplished in several steps (see Figure info-1). First, the robots are detected by individual motes using their onboard magnetometers. Then, motes nearby each other (those contained in a "neighborhood") share their detections. One of these motes will be elected the leader and will aggregate all the detections into one message that is routed to the pursuer (see Routing). Once the pursuer receives this message, it process the detections (removing noisy detections, removing detections of itself, running an estimation routine, etc) to localize the evader. With the location of the evader known (and knowledge of its own location -- see Control), the pursuer can plan an route to intercept the evader robot. Finally, the pursuer uses a navigation routine to follow the planned intercept course.
Routing
Figure routing-1: The network spanning tree used by the mote network to route messages during the pursuit-evasion game. Shown next to each mote is its location and the number of hops it is from the root node, located at (8,8).
For this project, the networking requirements were that (1) motes could share magnetometer detections locally, (2) aggregated detections could be routed to a single node for logging, and (3) that aggregated detections could be routed to the pursuer robot for tracking the evader robot. The first requirement was satisfied by the broadcast routing method built into TinyOS. The final two requirements were satisfied simultaneously. First, the network built a spanning tree (see the Figure routing-1) by flooding the network. This tree was used to route aggregated detections from any mote to the root node where they could be collected. To send the messages reaching the root node out to the pursuer, the root node needs to find a route to a mote next to the pursuer (which can broadcast the message directly to the pursuer). To this end, the mote onboard the pursuer robot would periodically emit "crumb trail" messages that nearby motes would collect and route back to the root node. Then, the root node would reverse the path of recent crumb trail messages to route detection messages to the pursuer.
Control
Figure control-1: The pursuer control architecture. A dividing line separates a high-speed self-localization system (on the left-hand side) from a slower speed evader estimation system (on the right-hand side).
The control system used for the pursuer robot is shown in Figure control-1. This system can be thought of as two communicating control systems: a high-speed self-localization system (left hand side in the figure), and a low-speed evader tracking system (right hand side in the figure). The high-speed system utilizes D-GPS readings to estimate the pursuer's state within the sensor network -- a simple coordinate transformation and a Kalman filter sufficed. The low-speed side receives aggregated magnetometer detections from the sensor network, filters out detections not related to the evader, and uses the remaining detections to estimate the evader's state. Detections are filtered out by a simple classification scheme: pursuer detections (those nearby the pursuer's current estimated position), evader detections (those nearby the evader's current estimated position), and noise (those far from either robot's current estimated position). State estimation of the evader was accomplished with a Kalman filter provided with an unknown, but bounded input. Given the estimates of the pursuer's and evader's states, the control system can now plan a path to intercept the evader. The generated intercept path is then followed (point-wise) using a point navigation controller. Finally, the control required by the point navigation controller is achieved with a simple motor controller that interfaces directly with the wheel motors.
Results
Figure results-1: Explanation of the annotations used on our robot path figures. Stars represent leader nodes that were selected to route aggregated messages to the pursuer. Dashed lines connect the position of the mobile robot when it received a message with the node that sent the message.
Figure results-2: Example run of the robot driving in the sensor network. The robot begins moving at around (0,8) and stops at around (0,10).
Figure results-3: Failing motes during the trial run. Three motes far from the robot had noisy magnetometers and erroneously reported detections. Additionally, two motes failed to report magnetometer detections with the robot nearby and failed to route messages within the network.
Figure results-4: Comparison of robot path estimation via D-GPS (solid black line) and via the filtered sensor network detections (solid orange line).
Figure results-5: Comparison of several key detection characteristics between the raw detections and the filtered detections.
During half a dozen runs, the pursuer was able to successfully capture the evader. In order to more specifically characterize the sensor network, however, we redeployed a 7 by 7 grid (with 2 meter grid cell sides) of motes to run several more experiments. In particular, a single mobile robot was driven through the sensor network and recorded both the sensor network messages and the D-GPS readings that were generated. From this, we were better able to characterize the ability of the sensor network to localize a robot.
We illustrate the results in several of the figures in this section using an overhead depiction of the events during an example trial. To understand our figures and accompanying annotations, we provide an explanatory figure (see Figure results-1). In this figure, we illustrate the D-GPS measured path of the robot using a solid black line with the robot starting position demarcated with a square. Here, we show a small initial portion of the path the robot takes, and we label the sequence of events as they occurred during this portion. First, the robot begins to move, starting around (0,8). Next, the robot is detected by nearby motes, who share there magnetometer detections with each other. One of these motes, denoted by the star, chooses itself as the leader. As the leader, it aggregates all the nearby detections into a single packet and sends this packet to the mobile robot. Finally, at some point later, the robot receives this message. The point along the robot's path when the message is received is denoted by the dashed line connecting the leader mote (star) to the robot's path (solid black line). This style of figure is used throughout this section.
Figure results-2 shows an entire example trial run for the robot driving in the sensor network. We see that the robot receives several messages over its path. However, the stream of detections is quite noisy: sometimes motes far away report detections and sometimes nearby motes fail to report. In particular, looking at Figure results-3, we have highlighted the far away motes that were reporting detections and the nearby motes that were failing. According to our logs, the failing motes not only refused to detect the robot, but also failed to route messages within the network. Here, we see that 5 of our 49 (10.2%) motes are failing. A approximately 10% fail rate was typical during our deployments.
Using our robot position estimation algorithm -- an algorithm designed to remove erroneous detections, compensate for network latency, and adjust for robot control actions -- we can track the robot through the field using only the sensor network detections. Figure results-4 shows the comparison of D-GPS readings (black line) with those of our estimate using sensor network data (orange line). Visually, we can see the robot was tracked very crudely. We quantify these observations in Figure results-5. In particular, we tabulate the estimation characteristics for the raw detections versus those of the filtered detections. Furthermore, we can compare this to the D-GPS sensor which provides measurements at 10Hz with less than 2cm of error. We see that raw detections arrived about every 3.0 seconds with 1.75 seconds mean latency and with a detection error larger than a grid cell side. Furthermore, we notice that the raw estimation error is around 2.0 meters where as the filter one is around 1.5 meters. This demonstrates both that the filtering is effective and that the sensor network is a challenging sensor to use for control systems given its relatively low frequency, large lag, and large error nature. However, even with these challenges, we were able to utilize the sensor network as an effective sensor for tracking an evading robot in our network. Additionally, given the multi-rate control system, we were able to successful navigate the pursuer robot to capture the evader robot in all trials.
Acknowledgments
This was joint work by the NEST Team under the supervision of David Culler, Eric Brewer, David Wagner, and Shankar Sastry. The lead team was Cory Sharp, Shawn Schaffert, Alec Woo, Naveen Sastry, Chris Karlof, Shankar Sastry, and David Culler. We would like to thank everyone who worked on PEG, including: Phoebus Chen, Fred Jiang, Jaein Jong, Sukun Kim, Phil Levis, Neil Patel, Joe Polastre, Robert Szewczyk, Terrence Tong, Rob von Behren, and Kamin Whitehouse. This work is funded in part by the DARPA NEST contract F33615-01-C-1895 and Intel Research.
References
- Cory Sharp, Shawn Schaffert, Alec Woo, Naveen Sastry, Chris Karlof, Shankar Sastry, David Culler, Design and Implementation of a Sensor Network System for Vehicle Tracking and Autonomous Interception, In the Proceedings of the European Workshop on Wireless Sensor Networks 2005, Jan-Feb 2005.