Abstract:
A swarming agent architecture provides a distributed, decentralized, agent-based computing environment applicable to ground-based surveillance. The approach, called Sensor Network Integration through Pheromone Fusion, or “SNIPF,” provides an end-to-end demonstration that integrates self-contained sensor/communication nodes with novel swarming algorithms to detect foot and vehicular movement through a monitored area with minimal configuration and maintenance. A plurality of computational nodes distributed within the environment and, depending upon the way in which they are deployed, the various nodes are operative to sense the local environment, receive a message from a neighboring node, and transmit a message to a neighboring node. Given these capabilities, the nodes can collectively determine the presence and/or movement of a target and communicate this information to a user. Though not required, the system may include nodes that are capable of collectively determining the speed and heading of a target, and the gathered intelligence may be communicated to users within, and external to, the environment. A particularly useful configuration may include one or more ‘free’ nodes having relatively limited communications and computational power, and one or more anchor nodes equipped with GPS and/or long-distance communications capabilities.

Description:
REFERENCE TO RELATED APPLICATION 
     This application claims priority from U.S. Provisional Patent Application Ser. No. 60/386,688, filed Jun. 6, 2002; and is a continuation-in-part of U.S. patent application Ser. No. 10/352,288, filed Jan. 27, 2003. The entire content of each application is incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     This invention relates generally to person and object tracking and, in particular, to a distributed, decentralized agent-based computing environment applicable to maintaining surveillance over a geographic region. 
     BACKGROUND OF THE INVENTION 
     Modern military engagements require detecting and monitoring the movement of people and resources, both military and civilian, in real time over a wide area with little direct human supervision. This problem poses a number of challenges to conventional sensing and data processing technologies. In the context of such behavior, it has become increasingly difficult to automatically detect such movements, since the relevant patterns may exist on many disparate levels. In some situations, combinations of geographical movement of personnel, vehicles and objects may need to be analyzed simultaneously. Currently this is a very human-intensive operation, typically requiring numerous individuals. 
     Active monitoring of human and non-human movement involves the detection and classification of spatio-temporal patterns across a large number of real-time data streams. Approaches that analyze data in a central computing facility tend to be overwhelmed with the amount of data that needs to be transferred and processed in a timely fashion. Also, centralized processing raises proprietary and privacy concerns that may make many data sources inaccessible. 
     The detection and classification of subtle changes in an activity requires the integration of a wide variety of non-specific real-time data sources into the operation of the tracking system. Furthermore, to guarantee the early detection of a suspicious or critical movement, the system must operate on real-time data that is continuously updated. As a result, there is an immense amount of data that needs to be processed in a timely fashion. 
     Our co-pending U.S. patent application Ser. No. 10/352,288, entitled “Swarming Agents For Distributed Pattern Detection and Classification,” incorporated herein by reference, describes a swarming agent architecture for the distributed detection and classification of spatio-temporal patterns in a heterogeneous real-time data stream. The invention is not limited to geographic structures or patterns in Euclidean space, and is more generically applicable to non-Euclidean patterns such as topological relations in abstract graph structures. According to this disclosure, large populations of simple mobile agents are deployed in a physically distributed network of processing nodes. At each such node, a service agent enables the agents to share information indirectly through a shared, application-independent runtime environment. The indirect information sharing permits the agents to coordinate their activities across entire populations. The architecture may be adapted to the detection of various spatio-temporal patterns and new classification schemes may be introduced at any time through new agent populations. The system is scalable in space and complexity due to the consequent localization of processing and interactions. The system and method inherently protect potentially proprietary or private data through simple provable local processes that execute at or near the actual source of the data. The fine-grained agents, which swarm in a large-scale physically distributed network of processing nodes, may be designed to perform three major tasks: 1) they may use local sensors to acquire data and guide its transmission; 2) they may fuse, interpolate, and interpret data from heterogeneous sources, and 3) they may make or influence command and control decisions. In contrast to previous approaches involved with command and control, or data acquisition and transmission, such an approach facilitates a swarming agent architecture for distributed pattern-detection and classification. 
     SUMMARY OF THE INVENTION 
     This invention extends the concept of a swarming agent architecture to provide a distributed, decentralized agent-based computing environment applicable to ground-based surveillance. The approach, called Sensor Network Integration through Pheromone Fusion, or “SNIPF,” provides an end-to-end demonstration that integrates self-contained sensor/communication nodes with novel swarming algorithms to detect foot and vehicular movement through a monitored area with minimal configuration and maintenance. 
     In the preferred embodiment, a decentralized tracking system according to the invention includes a plurality of computational nodes distributed within an environment. Depending upon the way in which they are deployed, the various nodes are operative to sense the local environment, receive a message from a neighboring node, and transmit a message to a neighboring node. Given these capabilities, the nodes can collectively determine the presence and/or movement of a target and communicate this information to a user. 
     Though not required, the system may include nodes that are capable of collectively determining the speed and heading of a target, and the gathered intelligence may be communicated to users within, and external to, the environment. A particularly useful configuration may include one or more ‘free’ nodes having relatively limited communications and computational power, and one or more anchor nodes equipped with GPS and/or long-distance communications capabilities. 
     Important characteristics of the system and method are summarized in Table 1. 
     
       
         
               
             
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 SNIPF Characteristics 
               
             
          
           
               
                 Challenge 
                 SNTPF 
               
               
                   
               
               
                 Logistics footprint is critical if 
                 SNIPF nodes are &lt;200 g, &lt;100 cm 3 , 
               
               
                 sensors must cover large area 
                 &lt;$200 each 
               
               
                 and cannot be retrieved. 
               
               
                 Network must be configured 
                 SNIPF configures itself. 
               
               
                 once in place. 
               
               
                 Maintenance on in situ nodes 
                 SNIPF is robust to failure of individual 
               
               
                 is impossible. 
                 nodes. Battery life is months to a year. 
               
               
                   
                 Network has self-replenishment 
               
               
                   
                 capability to reinforce weakened areas. 
               
               
                 Long-haul communications is 
                 SNIPF processes data in the network 
               
               
                 a power drain and introduces 
                 rather than at a central location. 
               
               
                 data latency. 
               
               
                 Communications among nodes 
                 SNIPF messages are meaningful only in 
               
               
                 may be intercepted by enemy 
                 the context of the whole system, and are 
               
               
                   
                 useless to an interceptor. 
               
               
                 Different targets require 
                 SNIPF can integrate multiple sensory 
               
               
                 different sensors 
                 modalities (e.g., acoustical, magnetic, 
               
               
                   
                 vibration), and run on different plat- 
               
               
                   
                 forms with minimal reconfiguration, de- 
               
               
                   
                 pending on mission requirements. 
               
               
                 Fire support requires precise 
                 SNIPF can achieve a circular error 
               
               
                 and unbiased Tactical Target 
                 probable on the order of tens of meters. 
               
               
                 Location (TTL) 
               
               
                 Information from a sensor 
                 SNTPF can report to a central 
               
               
                 network may be used in 
                 command, coordinate unmanned 
               
               
                 different ways 
                 vehicles for target verification 
               
               
                   
                 and attack, and guide SOF personnel 
               
               
                   
                 on the ground. 
               
               
                   
               
             
          
         
       
     
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a single node in an environment according to the invention; 
         FIG. 2  shows how nodes are distributed randomly over a battlespace or other environment of interest; 
         FIG. 3  shows simulated raw sensor readings on a 20×20 grid; 
         FIG. 4  shows nodes whose sensors individually exceed the threshold; 
         FIG. 5  shows the detecting neighborhood produced by applying neighbor corroboration to the sensor readings in  FIG. 3 ; 
         FIG. 6  illustrates a result with edge nodes, gray and central nodes; and 
         FIG. 7  shows a multi-frequency Hausdorff antenna applicable to the invention for channelizing ambient electromagnetic radiation. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     As discussed in the Background of the Invention, SNIPF is based on swarm intelligence [1,3], a new approach to information processing that uses the interactions among processors as well as computation within processors to detect, analyze, and respond to sensory input. This approach contrasts with other approaches in common use. 
     SNIPF processes sensory data in situ, not centrally, in contrast to data mining and data warehousing approaches. In contrast to conventional artificial intelligence approaches, processing is numerical, utilizing insect-inspired digital “pheromones,” and not symbolic implementations. Spatial reasoning draws on each node&#39;s location and the limited neighborhood induced by short radio range, rather than using an explicit representation of space, thus different from traditional signal processing. 
     Each node interacts with its environment in three ways. It reads its local sensors, receives messages broadcast by nearby neighbors, and broadcasts messages that can be received by nearby neighbors. Such a sensor field can detect the presence of a target, localize it, determine its velocity (speed and heading), and communicate this information to users, both external to the sensor field and within it, using only a few thousand bytes of software and requiring only a few hundred bytes per second of bandwidth.  FIG. 1  is a block diagram of a single SNIPF node, the operation of which is explained in the following sections. 
     Network Configuration 
     A SNIPF network has two kinds of nodes. Most nodes (˜95%) are free, with only limited communications and computational power. The nodes are inexpensive and they can run for a long time on small batteries. A few nodes are anchors, with GPS and long-haul communications (e.g., satellite) to transmit the net&#39;s findings to commanders. Each node has a unique identifier. 
     Both kinds of nodes are distributed randomly over the battlespace or other environment of interest ( FIG. 2 ). Their density depends on the range of the sensors deployed, their communications range, the nature of the targets, and the type of tracking required. Continuous tracking in SNIPF depends on the target&#39;s being visible to several nodes at a time. With hardware currently available, densities between 1/10 m 2  and 1/100 m 2  are appropriate, and smaller densities are possible when detecting but not tracking targets. These figures are given by way of example and not restriction; other hardware might permit the use of a wider range of densities without departing from the essence of this invention. 
     Once on the ground (or in water), the nodes self-configure and construct gradients to the anchors. These activities repeat periodically (e.g., daily) to account for lost nodes. To reduce message size, nodes define locally unique identifiers. In the preferred implementation, 6 bits are adequate for these identifiers. Each anchor broadcasts its identity and a hop count (initially zero). Every receiving node ( FIG. 1 , “Gradients”) checks whether it has heard a higher hop count from the same anchor. If not, it is on the expanding front of messages, so it increments the hop count and broadcasts the modified message. Each node remembers its minimum hop count from each anchor. Hop counts ( FIG. 2 ) define a gradient to route target reports to the anchor, and locate each node if there are at least three non-colinear anchors. 
     Once in place, the nodes interact in a sensing cycle whose frequency depends on the expected rate of change in the environment. For example, to track vehicles moving on the order of 30 km/h=8.3 m/sec, nodes spaced on average 10 m apart need a sensing cycle of 0.5 sec to guarantee that they see the target when it is in their zone. For pedestrians, cycles of 10 sec suffice, while monitoring construction of a stationary facility could use cycles of several minutes or even hours. 
     Detecting a Target 
     For discussion, we assume that a node&#39;s sensor responds to targets in its environment by generating a signal σ∈[0,1]. σ may be a primary sensor reading, the output of a “sensor fusion function” that combines readings from multiple sensors, the time rate of change of a sensor instead of its absolute reading, or other derivative data that will be obvious to one skilled in the art of sensor processing. In the preferred implementation, σ is normalized to fall in the range ∈[0,1], but the method here taught may be applied to other ranges as well.  FIG. 3  shows simulated raw sensor readings on a 20×20 grid. The eye can detect a bright area just NE of center where the target is located. If all sensor readings were piped to a central processor, conventional signal processing techniques could also detect this region, but such a data pipe is unrealistic under our power constraints. 
     The node translates σ (a real number) to a binary detection indication, using a threshold θ that falls in the open interval corresponding to the range of σ (in the preferred implementation, θ∈(0,1)). If σ≧θ, the node concludes that it sees a target; if σ&lt;θ, it ignores the signal.  FIG. 4  shows (in white) nodes whose sensors individually exceed the threshold. Local sensor anomalies such as noise result in an obscure picture. 
     SNIPF uses neighbor corroboration ( FIG. 1 , “Detection”). Each node periodically receives a message from each nearby node indicating whether or not the neighbor senses a target. Proximity among nodes makes it unlikely that only one node would see a target. A node&#39;s threshold for mapping its sensor signal to a detection decision varies with the percentage of its neighbors that sense a target, according to a sigmoid function. An example of such a function is θ+δ−2δ/1+e −r(p−0.5) , where p is the percentage of neighbors that detect the target, r adjusts steepness, and δ is the maximum deviation from the base threshold, but one skilled in the art will recognize that other sigmoid functions may be used without departing from the essence of this invention. If all neighbors detect a target, the node&#39;s threshold drops to θ−δ, accepting signals that would otherwise be rejected. If no other neighbors detect a target, the threshold rises to θ+δ, rejecting readings that would otherwise trigger detection. This neighborhood interaction improves the sensitivity of the network while reducing false alarms. 
       FIG. 5  shows the detecting neighborhood produced by applying neighbor corroboration to the sensor readings in  FIG. 3 . It clearly identifies the bright region in the original data and suppresses spurious readings. In spite of the power of this technique, it requires each node to transmit only one bit per sensing cycle, and to receive only n bits, where n is the number of neighbors within communication range. 
     Table 2 compares SNIPF&#39;s detection algorithm with other common data fusion architectures. 
                               TABLE 2                   Common Distributed Detection Architectures [6]            Architecture   Comparison with SNIPF               Parallel Fusion   Requires Data Fusion Center that can communicate       Network   with all nodes       Serial Network   Assumes fixed node order; result not locally known       Tree Network   Assumes fixed node arrangement; result not locally           known       Feedback Network   Requires Data Fusion Center and global           communications       Neighborhood   Nodes must exchange real #&#39;s instead of single bits       Medians/Avgs   Iteration reduces effective dynamic range of sensors       SNIIPF   No fusion center; low-power local communications;           arbitrary relation of nodes to targets;           result locally known (e.g., to coordinate mobile           units); uses full dynamic range of sensors                    
Target Location ( FIG. 1 , “Location”)
 
     Once detected, a target must be located geographically. Of all the nodes that detect the target, those closest to it must recognize that they are the closest. The percentage p of a node&#39;s neighbors that detect the target will be higher for a node closer to the target than for one far away. An “edge node” is one that detects the target and whose p is less than φ∈(0,1). Nodes that detect the target but are not edge nodes must be one step closer to the target, and so forth. Nodes already know whether they are edge nodes as a result of target detection. To locate the target, detecting nodes construct a gradient using a small integer (four bits in the preferred implementation) indicating their distance from the edge. A detecting node that hears no edge distance greater than its own knows that it is farthest from the edge, and thus that it is a nearest node.  FIG. 6  shows the result, with edge nodes (edge distance  1 ) colored gray and central nodes (edge distance  2 ) colored white. Since sensor location is our main estimator of target location, precision and bias of tactical target location (TTL) are directly dependent on sensor density and its relation to sensor range (that is, the number of sensors that detect a given target). 
     Determining Target Velocity ( FIG. 1 , “Velocity”) 
     A node estimates target velocity by maintaining a short history (ten steps in the preferred implementation) of its edge distance and measuring how fast it changes. A node in line with the target&#39;s vector sees the highest rate of change in its edge distance, while a node on the edge of the detecting range at the maximum distance from the line of movement sees the slowest. A gradient mechanism identifies the nodes of highest change. Their rate of change estimates the target&#39;s speed, and their position estimates its direction. 
     Communications 
     The sensor net must communicate information about the presence, location, and velocity of the target to other blue units. SNIPF provides two mechanisms for this communication. First, messages can diffuse up gradients to the nearest anchor, whose higher-power radio can pass the information on to a remote headquarters. Second, SNIPF can use target information locally to attract mobile resources, such as SOF personnel or unpiloted robotic vehicles. The mobile entity listens to broadcasts from the nodes. A node that determines that it is closest to the target generates a gradient. Mobile entities climb this gradient to reach the target. 
     Multiple Target Types 
     For simplicity, this discussion has assumed a single type of target with a single sensor configuration. It will be apparent to one skilled in the art that SNIPF can handle multiple target types requiring different sensor configurations, by adding a tag to each message indicating the target type with which the message is concerned. Required bandwidth is linear in the number of different sensor configurations. 
     Hardware Platform 
     The SNIPF algorithms are extremely robust and economic of processor and communications resources. An anticipated prototype will use a multi-sensor board that includes an acoustic sensor with tone decoder with a range of 6 m@60 db, a magnetometer that can sense a truck at 10 m, and a 2-axis accelerometer with 2 mg sensitivity. Other sensors can be interfaced for additional sensing tasks (e.g., chem./bio sensors, or the multi-frequency Hausdorff antenna shown in  FIG. 7  to channelize ambient electromagnetic radiation for ELINT and SIGINT. 
     SNIPF can track any entity for which a sensor exists that can function at a range on the order of the communication range. The prototype&#39;s sensor suite will be sensitive to targets such as light trucks, talking humans, and animal-drawn carts as well as more traditional military forces and equipment. The HW supports any sensor, and SNIPF (unlike conventional AI or data mining algorithms) makes no assumptions about the nature of the sensors, so the system can be extended easily. One skilled in the art will appreciate that the hardware details described here are by way of example and not restriction, and that the essence of the invention can be applied to other hardware platforms. 
     Replenishment 
     The inventive system may optionally repair a net when some nodes die or are removed. If a node detects that the number of its neighbors has dropped, it generates a gradient leading to itself. A lightweight unpiloted robotic vehicle equipped with a new node drops the new node in the area of the attracting node, thus increasing the net&#39;s local density and repairing the breach. Refinements of this scheme are possible. For example, if the net detects increased activity in an area previously quiescent the density of nodes in that area can be increased to provide finer resolution of sensing. 
     Potential users of SNIPF include SOF (via handheld computers with SNIPF-compatible radios), central command (using information exported from the network to identify events requiring further attention), and local commands (who will be interested in exported information, and in addition may deploy unpiloted vehicles such as UAV&#39;s or UGV&#39;s to move within the sensor field in response to detected targets). SNIPF can also be used by security personnel for perimeter monitoring in military and civilian applications. 
     REFERENCES 
     
         
         [1] E. Bonabeau, M. Dorigo, and G. Theraulaz.  Swarm Intelligence: From Natural to Artificial Systems . New York, Oxford University Press, 1999. 
         [2] Crossbow. MICA Wireless Measurement System. 2002. PDF file, http://www.xbow.com/Products/Product_pdf_files/MICA%20data%20sheet.pdf. 
         [3] H. V. D. Parunak. ‘Go to the Ant’: Engineering Principles from Natural Agent Systems.  Annals of Operations Research,  75:69-101, 1997. URL http://www.erim.org/˜vparunak/gotoant.pdf. 
         [4] K. Pister. UCB/MLB 29 Palms UAV-Dropped Sensor Network Demo. 2001. Web page, http://www-bsac.eecs.berkeley.edu/˜pister/29Palms0103/. 
         [5] U.C. Berkeley. TinyOS Home Page. 2002. Web page, http://today.cs.berkeley.edu/tos/. 
         [6] P. K. Varshney.  Distributed Detection and Data Fusion . New York, Springer, 1997.