Optimizing a RFID-UAV cattle search tour

2.1 RFID

Radio frequency identification, or RFID, has become an increasingly ubiquitous tool in many inventory tracking applications. The system is composed of two main entities, a tag and an interrogator, or reader. A high level classification of RFID systems places them in one of two categories: passive and active. In both cases the RFID reader (interrogator) generates an electromagnetic field that enables communication with RFID tags. Passive tags require the reader to power the communication, as these tags do not have an internal battery (Dobkin, 2007). Active tags, on the other hand, provide a power source, either internally using a battery or through a connection to a power source (Want, 2006). While more expensive, active tags provide a larger read range, making them better suited for the expansive pastures of the Walters and Escuela Ranches. RFID active tags intended for animal tracking became commercially available as early as 2006 with solutions including health monitoring and a web display of animal history (Voulodimos et al., 2010).

2.2 Animal tracking

Tacking the location of livestock, particularly in the case of cattle, is advantageous for environmental groups as well as ranch owners. Trevarthen and Michael (2008) explain the necessity to identify animals and the related Australian regulations, especially when traceability becomes paramount during disease outbreaks. They also suggest a method for RFID-enabled cattle farm to leverage mobile network infrastructure toward achieving total farm management.

During particularly warm seasons cattle spend more time in wetlands. These wetlands contribute to subsequent bodies of water, and the increased phosphorus loading ultimately pollutes these receiving bodies (Pandey et al., 2009). In other seasons, foraging tendencies are more randomized, as studies indicate that cattle do not graze in the same region for more than two consecutive days (Bailey et al., 1990). Gerrish (2015) recommends Management-Intensive Grazing, a method that rotates the cattle among discrete pasture areas, allowing each area recovery time between consecutive grazing periods. However, frequent cattle movement makes locating the cattle for permit checking and vaccination particularly difficult. In addition, ranchers and their financial supporters track animal location for much the same purpose that other industries track inventories, i.e., asset management. In the case of livestock, movement can be an indication of health if tracked frequently.

2.3 RFID with UAV

Numerous studies have evaluated the advantages of RFID technology in combination with Unmanned Aerial Vehicles, or UAVs, colloquially referred to as drones. Similar to livestock tracking, locating equipment over large construction sites has also been a particular area of interest for the implementation of RFID-UAV systems because of the expedited search times and ease of frequent inventory checks (Hubbard et al., 2015). A key benefit of utilizing UAV is the ability to adjust to a fast-changing warehouse, where stationary readers may not necessarily be able to read tags in all locations should the environment change (Ong et al., 2007). This could also prove beneficial in the natural and changing pasture environment.

Casati et al. (2017) introduces some performance metrics suitable to quantify the capability of an RFID drone to scan a surface equipped with radio-sensors. By using simple propagation models, an optimal drone-surface distance is mathematically derived for the purpose of maximizing the electromagnetic footprint for the specific choice of system parameters, such as the sensor type and position.

Buffi et al. (2017) presents a localization system for objects tagged with passive UHF-RFID tags, where the reader is attached to a drone. The system implements the phase-based SARFID technique to locate static tags with respect to a UHF RFID reader attached to a commercial drone. The reader antenna trajectory is achieved through a Global Positioning System. The bi-dimensional tag position is estimated with centimeter order accuracy. Only one reader antenna is required, without any reference tag. Similarly, Freed at al. (2018) describe an application of UAV-mounted passive UHF RFID system for oilfield equipment.

Due the short battery life (flight time) of currently available commercial UAV it is desirable to use multiple UAV to complete inventory tracking. However, the cost of RFID-UAV systems is relatively high –typically several thousands of US dollars per unit. An organization may not be able to afford purchasing multiple RFID-UAV systems due to financial limitations. Such is the case for the Walters and Escuela Ranches. Therefore, operational optimization of a single RFID-UAV system is the primary focus of this paper.

2.4 UAV path optimization

The RFID-UAV travels above the pastures of the cattle ranch and scans the RFID tags attached to the cattle in order to detect their locations. Since the UAV battery limits the flight time, the UAV path must be segmented, and recharging or battery replacement landing locations must be determined.

If all animal locations were known, then an algorithm that solves the Traveling Salesman Problem (TSP) efficiently could be used to minimize the UAV route that visits all animal locations. However, animal location certainty cannot be assumed.

Scanning a cattle RFID tag requires the UAV to fly within a certain distance from the animal, as opposed to approaching the animal’s exact location. Therefore, it is possible to model the UAV path optimization problem as a Close Enough Traveling Salesman Problem (CETSP: Gulczynski et al., 2006). Behdani and Smith (2014) develop two types of mixed-integer programming formulations for the CETSP based on a discretization scheme for the problem. Both lower and upper bounds on the optimal CETSP tour length can be derived from the solution of this model, and the quality of the bounds obtained depends on the granularity of the discretization scheme. Their approach first develops valid inequalities that enhance the bound and solvability of this formulation, and then provide two alternative formulations, one that yields an improved lower bound on the optimal CETSP tour length, and one that improves the solvability of the original formulation by recasting it as a two-stage problem amenable to decomposition. Computational results demonstrate the effectiveness of the proposed methods.

The CETSP is similar to the generalized directed rural postman problem (GDRPP), which attempts to find a minimum length tour starting and ending at the same spot (often referred to as depot) and traversing within an arc-length from each location that should be visited. The GDRPP has been recently used for optimizing routes of vehicles that perform RF meter reading of electricity or water consumption (where the meter is of the type that broadcasts its identity and reading.)

Drexl (2014) proved that the GDRPP is NP-hard, and proposed a formulation and a branch-and-cut algorithm with good computational results. Shuttleworth et al. (2008) presented this problem in the context of constructing routes for meter reading and named it the Close Enough Traveling Salesman Problem. The authors then use several heuristics to solve eight instances with an average of 900 customers and 9000 streets each. The read range r used is between 300 and 500 feet (approx. 100–170 meters.) Hà et al. (2014) also studied the GDRPP, named it the Close-Enough Arc Routing Problem, and proposed a new formulation and a branch-and-cut algorithm. Corberan and Laporte (2015) describe various variants of Arc Routing problems, their formulations and solution methods.

Ávila et al. (2015) developed two new formulations and a new branch-and-cut algorithm for the GDRPP and presented a study of the solution polyhedron associated with one of them. Problems where every customer has to be within a certain distance from the route had also been studied for node routing problems, and are known as covering tour problems (Gendreau et al. 1997). Avila et al. (2017) also develop a multi-vehicle version of the GDRPP, naming it the distance-constrained generalized directed rural postman problem (DC-GDRPP). Galceran and Carreras (2013) develop thee Coverage Path Planning (CPP) model for determining a robot’s path that passes over all points of an area or volume of interest while avoiding obstacles.

Carrabs et al. (2017) introduce a new effective discretization scheme to compute both a lower and an upper bound for the optimal solution. A graph reduction algorithm significantly reduces the problem size and speeds up computation of the bounds.

In this paper we selected to use a solution approach that is more intuitive and understandable to most UAV users for inventory management. We divide the grazing area into portions that match the coverage space of the UAV-mounted RFID equipment. We considered four heuristic approaches for this division, including Tiling, Steiner Zone, Sweeping Circle, and Radial Adjacency methods, and selected to use the intuitive tiling approach.

We then identify a supernode set based on the tiles, and solve a Traveling Salesman Problem (TSP) aimed at minimizing the total distance traveled by the UAV.

In summary, our research includes the determination of the most appropriate path optimization method for use across the Walters and Escuela Ranches. Based on the current UAV system configuration and environmental assumptions, the optimal UAV tour allows for the scan of each pasture segment’s animals to be completed within the battery-limited flight time.

3.1 System constraints and assumptions

The RFID-UAV system is subject to several physical constraints, as shown in Table 1.

The UAV payload limit was adjusted to account for the additional payload of the RFID system. For the purpose of this study, we assume these constraints, as well as mild environmental conditions, including limited wind, which are consistent with the projected flight speed.

Boundary information for each pasture was found using ArcGIS software, a cloud-based online mapping platform employed by the ranch to map roads, gates, water-troughs, and other pasture features. The outline of each of the 43 pastures is shown in Fig. 1.

OPEN IN VIEWER

Fig. 1

ArcGIS pasture outlines of the Walters and Escuela Ranches.

Due to the intensive grazing practice employed by the ranch, during a given period all cattle are located within one of the pastures shown. From the pasture acreage found on ArcGIS (a complete listing in Table 2), the largest pasture is Pasture E9 at 118.6 hectares or 1.186 km² (see Fig. 2). This becomes the primary pasture of interest because it will take the longest to scan. Therefore, success scanning this pasture yields a solution that can successfully scan all pastures. Given the ability of the RFID interrogator to scan 35753 m² from one location, it would require a minimum of 33 scanning locations to scan pasture E9. Assuming the distance between locations is equal to the read diameter, 213 m, the theoretical fastest time the system can scan the pasture flying at 16 m/s is 7.4 minutes, accounting for the ascent and descent time. This is within the allotted flight time, but assumes the shortest tour is taken, without repeating any portion of the tour.

OPEN IN VIEWER

Fig. 2

ArcGIS boundary of pasture E9.

In order to ensure that the region is fully scanned in the allotted time, a number of alternatives were considered, including increasing the UAV flight time, enhancing the RFID read range, and reducing the flight path.

In order to increase flight time, the system could employ a larger battery, offering more ampere hours per charge. Depending on the battery purchased, this could also increase the payload and slow down the UAV. Another option is investing in a second RFID-UAV system. While the ascent and descent times are fixed in the total tour time, this cuts the scanning time in half. These options were not considered due to the additional investment required.

Increasing the RFID interrogator’s read range was also considered. The RFID interrogator used was an active RF Code Mantis II reader which is no longer available for sale but was donated to PolyGAIT by RF Code’s founder. There are similar commercially available systems, from companies such as Danbit and SkyRFID.

A more powerful interrogator may increase the read range. However, it will likely be heavier, consuming battery power faster, thus decreasing the UAV flight time. Using more powerful antennas may also increase the scanning distance. However, these antennas are also likely to be heavier, as well as affected by the orientation of the RFID active tag relative to the antennas.

Other technologies such as GPS locators and cellular technologies have been considered for this application. However, currently available systems are cost-prohibitive (hundreds of thousands of dollars for a small herd of cattle).

Another problem of GPS and cellular systems is that the tags attached to the livestock are large, heavy, and tend to get tangled in bushes. The livestock may not be able to release themselves and end up dying of chocking or starvation.

The cost of a drone similar to PolyGAIT’s is approximately $7000. An active reader can be purchased or manufactured for $2000. Tags can be purchased or manufactured for $10 each. Therefore, the total cost of the PolyGAIT UAV-RFID system was lower than $10,000 for a herd of 50 animals.

Another possibility to decrease the system weight is to use light casing instead of hard metal housing for the reader. Flight time could be positively affected by this choice.

Multiple experiments with plastic encasing of the reader electronics were conducted. However, drone landing gear sometimes breaks under windy conditions or due to electromechanical failure of the drone control system. In such cases a plastic-encased reader may be irreversibly damaged.

We are also working on flight duration extension through development of new types of power supplies and batteries for drones, but none of these devices was ready for use during the experiments.

Based on the preliminary calculations confirming that the theoretical shortest path does fall within the allotted flight time, tour optimization is the best option as it requires no additional equipment investment. For this design, an integer programming model of CETSP was considered, but a variant of the Traveling Salesman Problem (TSP) was selected. The solution allows for the surveillance of the entire area and takes into consideration the read range of the RFID interrogator and active tags. The route directs the UAV to fly close enough to the point of interest to detect the tag, while not requiring the tour to include the exact location of the tag. There are variations of this model, but based on the unknown location of the cattle within the ranch and the solution objective to cover the entire region, this solution starts by using a Tiling approach to identify the tour’s nodes.

3.3 Close enough traveling salesman problem

In utilizing the TSP a number of heuristic approaches may be used. Most methods, including the use of Steiner Zones, are best suited for circumstances where the target location is known. As the objective of this problem is finding the location of the targets, the Tiling method is best suited because it creates a supernode set that covers the entire region.

The first step is dividing the E9 pasture into areas with radii equivalent to the scanning radius of the RFID equipment. Because tangent circles result in only 78.5%coverage of the total rectangular area, a hexagonal lattice with diagonal lengths equal to the circle diameter is employed instead (Fig. 3). Specifically, approximately 20%overlap in coverage is required using the discretization method of hexagonal tiling when the RFID interrogator’s reading area is assumed to be circular.

OPEN IN VIEWER

Fig. 3

Hexagonal lattice & length of circle diameter (770 ft = 213.36 m).

The lattice is expanded to include area boundaries such that the number of partial hexagons is minimized. The result is shown in Fig. 4. Per the TSP, the midpoint of each hexagon becomes the desitnation node in the tour. A coordinate system is then overlayed to identify the midpoints. These are the nodes included in the tour. The calculation of the distance between adjacent midpoints is shown in Fig. 5.

OPEN IN VIEWER

Fig. 4

Hexagonal tiling over Walters and Escuela Ranches.

OPEN IN VIEWER

Fig. 5

Calculation of distance between adjacent hexagonal midpoints (303.1 ft = 92.38 m; 606.22 ft = 184.76 m; 525 ft = 160.02 m).

With the tour nodes identified, the tour is then optimized using the traditional Traveling Salesman Problem formulation, shown below. This is an integer programming model minimizing the total distance traveled, cij, for all tour connections selected, xij. This is subject to constraints that enable each node to be selected once and only once. The final constraint set eliminates subtours. minimize ∑ i = 1 n ∑ j ≠ i , j = 1 n c ij x ij where x = { 1 if the path from i to j is selected 0 otherwise subject to the constraints 0 ≤ x ij ≤ 1 ∑ i = 1 , i ≠ j n x ij = 1 ∑ j = 1 , j ≠ i n x ij = 1 u i - u j + n x ij ≤ n - 1 , ∀ i , j ∈ N - { 1 } , i ≠ j

Assuming constant velocity throughout the flight, the velocity may be multiplied by the total distance traveled along the optimized path. If, however, the assumption about the environmental conditions changed and wind or other factors were to affect a paricular section of the pasture, the varied speeds must be included in the TSP, where cij would be the time to travel from node i to node j.

4.1 Gurobi optimization solver

The TSP is solved using Gurobi’s optimization software with Python interface. The script used is shown in Fig. 6, and calls on the coordinate values listed in a.csv file. The model utilizes an iterative process where feasible solutions are compared to a predetermined best solution. Should the solution involve a subtour, a LazyConstraint parameter will be added to eliminate that particular subtour, and the model will run again until all constraints are satisfied and a best solution is identified. The model for 60 nodes in one pasture takes less than a minute to solve, as compared to 20–30 minutes for the 350 nodes of the entire ranch.

OPEN IN VIEWER

Fig. 6

Traveling Salesman Problem Python Script with pasture coordinates for Gurobi optimizer.

Complete enumeration was used as the problem size was manageable (due to the pre-discretization of the pasture), and since this problem may have to be solved real time in future applications.

With the optimal route defined in the output of the Gurobi model, the tour distance is then multiplied by the flight speed and added to the ascent and decent time to find the total tour time. At 16 m/s, the total tour can be accomplished in one battery charge, and the UAV searches the pasture 11.93 times faster than an employee. Should the travel time take longer than the allotted 15 minutes, this approach will not suffice in the effective implemenation of the current RFID-UAV system, and an additional investment in equipment previously discussed in the alternatives considered is required.

To verify the feasibility of the model, the Gurobi output is mapped on the pasture. An example of the results for Pasture E9 is shown in Fig. 7. This utilized 9 LazyConstraints, meaning 9 iterations of the solution resulted in subtours before the final tour was found. Note that the output labels tour nodes by their line sequence within the.csv file, which may not match the label given to the points, and must be considered to properly identify each node. Figure 8 shows the tour mapped on Pasture E9.

OPEN IN VIEWER

Fig. 7

Gurobi output for pasture E9.

OPEN IN VIEWER

Fig. 8

Output tour mapped on Pasture E9.

OPEN IN VIEWER

Fig. 9

PolyGAIT RFID-UAV System.