SUMMARY
Understanding of the organization of animal societies often requires knowledge of the identity of group members and their spatial location. We propose an original experimental design to track automatically the position of individuals using radio frequency identification technology (RFID). Ants equipped with passive transponders were detected by a reader mounted on a mobile arm moving across the nest surface. We developed an algorithm to accurately extract the positions of individuals moving in two dimensions. Our method was validated on synthetic test cases and then used for characterization of the spatial distribution of ants within nests. This approach provides an amenable system for monitoring large populations of individuals over long periods of time.
INTRODUCTION
In a wide variety of contexts and across several taxa, knowledge of the identity and spatial location of individuals is crucial for understanding the organization of animal groups. In arthropods, external marking techniques – such as the use of numbered tags (Monnin and Peeters, 1999), dots of paints (SendovaFranks and Franks, 1993) or wire loops tied around body parts (Mirenda and Vinson, 1979) – are routinely used to individually tag animals within groups. Alternatively, the position of individuals within groups can be automatically extracted from digitalized pictures, but at the cost of losing identity (Cole and Cheshire, 1996). The knowledge of both identity and position usually requires photographing nests of marked animals and analyzing pictures afterwards. These processes are fastidious and slow down the survey of large groups of individuals over long periods of time. Commercial software can automatically track the positions of several individuals. However, this method usually requires light, which prevents monitoring animal activity in total darkness and is inefficient when individuals enter dark places (e.g. nests). Radio frequency identification (RFID) technology represents a powerful alternative. Animals can be equipped with passive tags consisting of an antenna and a semiconductor chip. The power required for reading the unique identification number of each tag is provided by an external device. Passive tags are of particular interest because of their miniaturized size and their virtually infinite operational life (Want, 2006). This technology has been successfully employed in different taxa (Molet et al., 2008; Robinson et al., 2009; Sumner et al., 2007). In these studies, however, the reader was immobile and the identity of an individual was read whenever it passed underneath the reader or through a circular antenna. Although this methodology can provide valuable information on activity levels or foraging rate, it does not accurately inform on the spatial location of individuals. To overcome this limitation, an option is to use as many readers as spatial domains of interest but this method can quickly become expensive due to the cost of a reader.
We propose an alternative solution that consists of mounting an RFID reader on a mobile arm moving along two orthogonal axes to scan the domain of interest. We developed an algorithm to extract the position of the ant and to discriminate multiple detections of a motionless individual from a true displacement. As a case study, we studied the spatial distribution and mapped the network of social interactions in the ant Odontomachus hastatus.
MATERIALS AND METHODS
Animals
We used one colony of the ant Odontomachus hastatus Fabricius, containing one queen, 55 workers and brood (eggs, larvae and pupae) collected in French Guiana in February 2009. These ants form colonies comprising up to a few hundred monomorphic workers (worker length, 1.5 mm). During the experiment, ants were introduced into an experimental setup (see below) placed in a climate room (25°C; 40% RH) under a 12 h:12 h light:dark cycle. The colony was surveyed for seven consecutive days and fed twice a week with live house flies (Lucilia sericata) and vitaminenriched food (Dussutour and Simpson, 2008).
Experimental setup
RFID tags and reader were purchased from Lutronic (http://www.nonatec.net). The tags were encapsulated in resin, were 6 mm long and weighed ∼6 mg (about onethird of the mass of an ant). The frequency of RFID is 13.56 MHz. Tags were glued onto the thorax of each ant, including the queen, with Superglue©. Tagged ants were gently introduced into the foraging area of an artificial nest (height=1 cm, width=18 cm, length=24 cm), which was divided with a plastic strip into two compartments (Fig. 1). Each compartment was covered with a transparent plastic plate to prevent ants from escaping. One compartment (18 cm×12 cm) formed the foraging area. This area was connected to the second compartment (18 cm×12 cm), which was further partitioned into two interconnecting chambers (inner nest chamber and hall nest chamber) covered with a red film filter (Fire #19; Rosco, London, UK). The floor of all compartments was covered with plaster, and a layer of moistened dirt was added.
RFID scanner
The detection field of the RFID reader was 35 mm, and the reading distance was approximately 1 cm. An apparatus, hereafter referred to as RFID scanner, was specifically designed to move the reader across the surface of the nest. The reader is cylindrical in shape (18 cm×3.5 cm) and was mounted on a device moving on a rail along the xaxis. This rail can move independently on a second rail along the yaxis. Movements along each rail were driven by stepper motors (TECO Electric & Machinery Co. Ltd, Taipei, Taiwan) piloted by a microcontroller (Microchip Technology Inc., Chandler, AZ, USA) via motor drivers (STMicroelectronics, Geneva, Switzerland). The step displacement along the xaxis was chosen to allow an overlap of the detection field of the reader (Fig. 1). For each detection of a tag, the mobile arm stopped for a duration of 35 ms, which corresponds to the time required for sending information to the computer. Each scan (i.e. forward and backward path of the reader) lasted ∼500 s (∼1200 scans/week).
Detection algorithm and extraction of each ant's positions
When the reader detected a tag, the microcontroller sent its number, the spatial coordinates of the reader and the time to a computer. Tags were rarely associated with a unique location but were detected several times during each scan. Multiple detections resulted either from the displacement of the reader above a motionless ant and the overlap of the reader detection field or from the true displacement of an individual between distinct locations (supplementary material Fig. S1). We developed an algorithm to discriminate both situations and to extract the spatial coordinates of each individual.
We aimed to extract each ant's position (X_{n}) from a series of M discrete reader positions (R_{m}) obtained at time t_{R}_{m}. This corresponds to a multidimensional optimization problem, i.e. the maximization of the nonlinear function S_{R}(X_{n}) (Eqn A10 in Appendix) in a 2N dimension space, where N is the number of positions of the ant during a scan (i.e. forward and backward path). S_{R}(X_{n}) is the number of detections associated with at least one ant's position. To determine the number of positions, we solved Eqn A10 for values of N ranging from 1 to N_{max}. Put simply, the algorithm aims to maximize the number of detections within a circle of radius L. One position is randomly drawn from M (X_{1}=R_{m}, with mϵ[1,M]), and S_{R}(X_{n}) (Eqn A10) was maximized. If S_{R}(X_{n})≥M, the extraction of a position was successful. If not, a supplementary position was randomly drawn from M (X_{N}=R_{m}, with mϵ[1,M]), and S_{R}(X_{n}) was maximized. This algorithm was applied successively for each tag and across scans.
All the computations were done using R statistical software (http://www.Rproject.org).
RESULTS
Validation of the algorithm for position reconstruction
We considered two theoretical test cases to assess the performance of the algorithm to reconstruct positions. A position, X_{e}, was randomly sampled in the domain, and M positions (R_{m}) were randomly drawn within a radius L of X_{e} either uniformly or along the paths followed by the reader (Fig. 2A). The mean distance between the exact and reconstructed positions of X_{e} was used to estimate the performance of the algorithm. We determined the mean Euclidean distance error (n=5000) as a function of M (Fig. 2B). For the first case, the error converges uniformly to zero with increasing M. This demonstrates that the algorithm can precisely reconstruct the position. For the second case, the error reached a plateau value of 0.3L. This asymptotic behaviour results from the constraints imposed by the path followed by the reader, which reduces the spatial resolution. In our experiments (see below), the length 0.3L=4.5 mm was smaller than the size of an ant; the algorithm was thus sufficiently accurate to locate ants within the domain.
We assessed the performance of the algorithm for discriminating positions of moving ants. Two positions, X_{1} and X_{2}, separated by a constant distance, were randomly drawn within the domain. A number of detections, M_{1} and M_{2}, were sampled randomly either uniformly or along the paths followed by the reader within a radius L of X_{1} and X_{2}, respectively (Fig. 3A,B). Theoretically, the algorithm should discriminate both positions if there exists at least two detections that satisfy the condition ∥R_{i}–R_{j}∥>2L. We calculated a discrimination rate as the proportion of cases where the algorithm discriminates both positions accurately (Fig. 3C,D). As expected, the discrimination rate increased with the number of detections, M, for each position and with the distance between positions. In addition, the algorithm discrimination rate closely matches the theoretical prediction (broken lines, Fig. 3C,D). This means that the algorithm can satisfactorily distinguish discrete positions of a mobile individual.
Application of the algorithm for position reconstruction in ants
We assessed the efficiency of detection as the number of detections for each tag divided by the total number of scans (1200 scans). Across tags, the median efficiency equalled 0.97 (1st quartile=0.95; 3rd quartile=0.99). This indicates that tags were detected at almost every scan. We then determined the number of distinct positions extracted for each tag during each scan and calculated the distance between the two furthest locations when multiple positions occurred (i.e. true displacement). The median number of detections for each tag was six (1st quartile=3, 3rd quartile=9). This indicates that, on average, each position was reconstructed from six detections. On average, a unique ant's position was extracted in 50% of cases. Two positions (i.e. true displacement) were obtained for 35% of ants, and 14% had three or more positions (supplementary material Fig. S2). When two positions were obtained, the average distance equalled 4.3 cm (supplementary material Fig. S2).
Spatial distribution in ant colonies and social network
We used the coordinates of each ant to examine how colony members were spatially distributed in the experimental setup. Fig. 4 shows representative patterns obtained for three workers. Qualitatively, some individuals displayed a fidelity to spatial zones and remained mostly in the foraging area or in the nest. By contrast, some ants were mobile and shared their time more evenly between both zones. From the positions of individuals, we mapped the network of social interactions among ants. We considered that two individuals were interacting if their interindividual distance was ≤14 mm. We considered all possible pairs of ants and determined whether they met the distance criterion to build an adjacency matrix of interactions. The network obtained is highly connected, with an average degree of 26, indicating that ants were directly interacting with half of the colony (Fig. 5).
DISCUSSION
In this study, we proposed an original design to track the position of ants within groups. Individuals equipped with RFID passive transponders were detected by a reader mounted on a mobile arm moving across the nest surface. We developed an algorithm for extracting the positions of each ant, which was first validated on theoretical test cases and then used for characterizing the spatial distribution of individuals within nests. In our system, the temporal and spatial resolution allowed the characterization of spatial patterns in ant colonies and the ability to build a network of social interactions among ants. This system provides a valuable tool for addressing several questions including the influence of colony size on the rate of social interactions or the impact of variations in environmental conditions on task allocation. These issues are currently under investigation.
Our methodology can easily be adapted to any system where individuals evolve in two dimensions. Depending on biological models, there is no restriction in enlarging the size of the domains to monitor and changing the frequency of scanning. The number of readers can also be augmented and/or the overlap of their detection field increased to improve spatial resolution. Finally, the speed of the mobile arm can be boosted to enhance temporal resolution. Our system, which is suitable for organisms of reduced size, offers a promising method for collecting automatically large amounts of data relative to the identity and spatial positions of individuals.
APPENDIX
Problem statement
In a continuum point of view, the form of the distribution function of measurements r(x, t) during one scan is: (A1) where R_{m} is the position vector of the reader, t_{R}_{m} is the time at which the tag is detected, M is the number of detections of an ant during one scan and δ stands for the Dirac function. Multiple detections can occur for two reasons. First, the reader can detect a motionless tag at a distance L. Second, an ant can move within the domain and can be detected in distinct locations (supplementary material Fig. S1). The algorithm should discriminate both origins.
The distribution function of ant positions f(x, t) is defined such that f(x, t)=1 if the ant is present at position x at time t and null elsewhere. We define the detection field (i.e. the area where an ant can be detected) by a space filtering of f(x, t): (A2) where G_{L} (x′) is a top hat filter in physical space: (A3)
We introduce the scalar function: (A4) The value of S_{R}(f) varies, by construction, between 0 and M. For S_{R}(f)=M, all detections are associated with ant position.
The process of detection consists of finding the function f(x, t) that maximizes S_{R}(f). To achieve this, some assumptions on the form of f(x, t) are needed. Assuming that during one scan an ant occupies successively N discrete positions, X_{n}, and instantaneously changes position at time t_{n}, the distribution function of ant positions is: (A5) where H(t) is the Heaviside step function. Using this model, equation A4 reduces to: (A6) With (R_{m}, t_{R}_{m}) given, the process of position extraction consists of finding the minimum number N of points, (X_{n}, t_{n})_{n}_{=1,}_{N}, that maximize S_{R}. The problem then reduces to an optimization problem in 3N dimensions, the number of ant discrete positions N being unknown.
Numerical implementation
Due to the large number of dimensions and the discontinuous nature of Eqn A6, resolving the optimization problem needs specific tools and can be numerically expensive. For simplicity, we used two approximations.
First, we reduce the dimension number. By construction, each measure (R_{m}, t_{R}_{m}) can only be associated with a single ant position (X_{n}, t_{n}). We use this property to discard time dimension from Eqn A6: (A7) where the function T_{R}_{,}_{X}(m, n) ensures that each detection contributs once to S_{R}(X_{n}) and is defined by: (A8) The dimension number of the problem is then reduced from 3N to 2N.
Second, we replace the discontinuous Heaviside functions H(x) by the hyperbolic tangents function, introducing a numerical smoothing parameter, s. According to numerical tests (not presented here), the smoothing parameter s is set to s=L/15: (A9) Finally, the continuous IR^{2}^{N}→IR function to maximize for determining the positions (X_{n}) of an ant is given by: (A10)
This optimization problem, Eqn A10, is solved in two steps: a stochastic global optimization method (Belisle, 1992) coupled with an ad hoc resampling process followed by a simplex algorithm method (Nelder and Mead, 1965). Eqn A10 is used to test the convergence of the algorithm for position reconstruction.
FOOTNOTES

Supplementary material available online at http://jeb.biologists.org/lookup/suppl/doi:10.1242/jeb.050526//DC1
LIST OF ABBREVIATIONS
 L
 radius of the detection field of the reader
 m
 integer varying from 1 to M
 M
 the number of detections of an ant during one scan
 n
 integer varying from 1 to N
 N
 number of positions of the ant during a scan
 R_{m}
 position vector (X and Ycoordinates) of the reader for the detection m
 S_{R}(X_{n})
 number of detections associated with ant position X_{n}
 t_{R}_{m}
 time at which the tag was detected
 X_{n}
 position vector of the ant
 © 2011.