1. INTRODUCTION
Prior research, reported in Banks et al., (Reference Banks, Vincent and Phalp2008a), indicated that a swarm of Unmanned Aerial Vehicles (UAV) might be controlled to defend effectively a given airspace by utilising a stochastic algorithm based on notions drawn from Particle Swarm Optimisation (PSO). Performance gains were made either when target vehicles moved stochastically or used a deterministic search pattern, although the stochastic, cooperative swarm did suffer difficulties in achieving initial target detection. This paper reports promising research utilising nature inspired search strategies that could be used in the initial search phases of operations to control the autonomous UAV swarm. The search element is uncoordinated to increase systemic robustness and minimise communication. The latter point is particularly desirable, since the environment of target applications for autonomous vehicles often have restricted communication due to limited bandwidth or high levels of electro-magnetic interference. Although the original inspiration for the work was found in considering the potential of autonomous UAVs in air-defence roles, it is recognised that the techniques and findings are more generally applicable; hence, we refer not to UAVs but to ‘agents’ as generic terms that might encompass a wide range of autonomous air or ground vehicles, in a range of military and civilian roles. The emphasis is therefore on the utility of various nature-inspired search techniques, rather than specific applications.
The remainder of this paper is organised as follows. Section 2 provides a brief introduction to the biological inspiration behind the selected search strategies. Section 3 examines issues surrounding their implementation and the simulation environment used for the experiments. Section 4 outlines the experiments conducted in order to evaluate the utility of the various search strategies. Section 5 presents results and findings. Section 6 concludes.
2. NATURAL SEARCH PATTERNS
The natural world abounds with differing search strategies; it is not within the scope of this work to review these in detail. A broad review of techniques (including those explored in this paper) can be found in Banks et al., (Reference Banks, Vincent and Phalp2008b). For the feasibility of this research, significant representative search patterns have been selected from those observed in the natural world: five generalised strategies (Brownian motion, Lévy path, straight line, saltatory and Area Concentrated Search (ACS)) and two species-specific strategies (bacterial foraging and fruit fly). Two deterministic patterns (systematic and spiral) and random patterns were used as benchmarks for comparison.
2.1. Random Walks
The first three strategies (Brownian motion, Lévy path, and straight line) are generally termed random walks. They represent the range of movements possible between stationary, ambush style predation and continuous movement without turning. The movement patterns can be described by the probability (P) of path leg length (l j) described as:
where μ⩾3 for Brownian motion, μ≈2 for Lévy paths and μ⩽1 for straight line search (Viswanathan et al., Reference Viswanathan, Buldyrev, Havlin, Da Luz, Raposo and Stanley1999). This inverse power law not only dictates the rate at which a predator will turn but also the extent to which it will range across a given search area. Thus, given a constant speed, an agent using Lévy search will range across a given area more widely than one moving at the same speed but following Brownian motion. The increased ranging of Lévy path searches make it more attractive for animals that need to search relatively large areas for their size, for example bumblebees (Reynolds, Reference Reynolds2005) and Brownian motion can been identified in animals such as zooplankton (Garcia et al., 2007).
Straight line search (sometimes referred to as cruise search) assumes that there is just as much chance of encountering prey anywhere in the search space and turning is generally less efficient. Agents using this strategy must decide when continuing in an unproductive direction is less attractive than turning, although such behaviour can still be modelled using Equation (1). Further, turning is often alternated between left and right hand turns with a mean of 35° to reduce the possibility of covering the same area twice (Bell, Reference Bell1991). A classic example of this type of search can be seen in the Buller's albatross (Stahl and Sagar, Reference Stahl and Sagar2000) that can forage over thousands of kilometres in a single trip lasting several days; of note was the evidence that the birds gained more weight on the longer foraging trips that also exhibited lower turn-rates than at times when foraging trips were short and had higher turn-rates.
2.2. Saltatory Search
The next two patterns can be termed bi-phase searches and utilise switches between random walk patterns following a given trigger. Saltatory search is the process of intermittent searching where the agent pauses at a location, and searches intensely before moving on. The technique is used where sensory acuity is reduced during the movement phase and/or targets are hidden such that they could be overlooked (Benichou et al., Reference Benichou, Coppey, Moreau, Suet and Voituriez2005). The trigger for the switch would depend on the environment; for example, where visual acuity is generally good but prey items could be hiding in sporadic areas of dense vegetation then the predator would move between them searching intensely at each location. Conversely, where the environment was not patchy, the predator may use a time based trigger, intensely searching an area for a certain period before moving on should no prey be located. Animals do not always utilise the same movement and may switch between movement patterns given differing environmental factors; O'Brien et al. (Reference O'Brien, Browman and Evans1990) argued that all animals utilise a form of saltatory search, where each animal's search behaviour can be placed somewhere on a movement scale, and that the move/pause ratio varied within individual species depending on the prey items being sought. To illustrate this they compared earlier research into the movement of white crappies and arctic grayling when searching for different prey items. Both species always utilised much shorter pauses, travelled farther and adopted larger turn angles when pursuing large prey items than small items.
2.3. Area Concentrated Search
Area Concentrated Search (ACS) is a further example of a bi-phase search; initially the predator searches using a strategy at the straight-line end of the random walk spectrum, but, when a target is encountered, an intensive search phase is entered. This maximises the efficiency of the search where there is a possibility of target clustering (Krakauer and Rodríguez-Gironés, Reference Krakauer and Rodríguez-Gironés1995). Hill et al. (Reference Hill, Burrows and Hughes2000) investigated the ACS-based search of the juvenile plaice and noted that on discovering a prey patch (bivalves) they adjusted their search from the explorative search to the exploitive search by shortening pause time by 15%; increasing move duration by 14% and reducing speed by 22%. Interestingly, time spent exploiting a patch was not dictated by prey density but rather by the increased risk of predation due to environmental disturbance during the capture phase.
Where animals adopt a search strategy that contains a decision to change mode, for example to move on following unsuccessful sit-and-wait or to leave a prey patch during ACS, they must adopt some kind of giving-up strategy. These can be triggered environmentally, for example following prey depletion as modelled by Charnov's marginal value theorem (1976) or increased likelihood of predation (as in the juvenile plaice, Hill et al., Reference Hill, Burrows and Hughes2000), or chronologically, as modelled by Nishimura (1999) and observable in animals such as the sidewinder (Secor, 1992).
2.4. Bacterial Foraging
Bacteria use a wide variety of search behaviours. The bacterial search for this work was based on E. coli, which has two main movement types: swimming and tumbling. Swimming consists of Brownian motion movement that enables the bacteria to move about the environment, whilst tumbling changes movement direction (Passino, Reference Passino2002). When placed in an environment with a neutral or negative nutrient gradient, the bacteria perform swim and tumble phases of equal duration. When a positive nutrient gradient is discovered, the mean speed and turn length increase at the cost of the tumble phase duration. Despite all bacteria moving independently, the overall effect of the strategy is that the bacteria always look for, and move up, positive nutrient gradients, in such a manner that they have the appearance of coordinated swarming.
2.5. Fruit Fly Searches
Foraging fruit flies, Drosophila melanogaster, in free flight perform their search through a combination of straight line flight and rapid turn phases (the latter known as saccades). The relative duration of these phases is random and the switch between them may be triggered by several sources such as a mechano-sensory or optomotory equilibrium systems. When saccades are performed they have fixed amplitude with an approximate angle of ±90° (Tammero and Dickinson, Reference Tammero and Dickinson2002). On locating an odour source, the flies switch to a behaviour known as crosswind casting (Budick and Dickinson, Reference Budick and Dickinson2006). This behaviour is outside the scope of this work since it relies on the presence of prey information, whilst in our search application we assume that such information may not be readily available.
2.6. Foraging Components
Also relevant to this work are the components of foraging. O'Brien et al. (Reference O'Brien, Browman and Evans1990) discuss the three main components of foraging: search and locate prey; pursue and attack prey and handle and ingest prey. This last component is not within the scope of this work. The first element is often the most important phase of predation and larger amounts of energy are expended in the search where prey items are smaller than the predator. Where prey items are larger, greater energy is often required to catch and handle the prey and thus the initial search phase is less energetic. The former two components are related to this work, although agents and targets will be assumed to be of equal size. Some of the strategies are what could be termed bi-phase; that is, they switch behaviour following a given trigger (event based or chronological). Such strategies depend on entering the pursuit phase for the systemic gains from the switch to be realised.
3. SEARCH IMPLEMENTATION
Each of the search strategies outlined in Section 2 were implemented in a simplified model constructed in Ada 95 using the John English Windows Library (JEWL) (English, Reference English2000) and AdaCore's Gnat Programming System (AdaCore, 2005), along similar lines as that used in Banks at al. (Reference Banks, Vincent and Phalp2008a). To aid replication of the experimental results, the agent and environment properties are defined in this section, although the exact details are not particularly critical to the overall findings. The search area was a two-dimensional representation of an area measuring 400×300 units; within this were two distant, non-central defended positions. The agents travelled at a constant speed of 0·8 units per step (unless the search strategy dictated otherwise), had a sensor range of 40 units, a Field Of View (FOV) angle of 40° and all strategies had the same maximum turn rates (10° per step) applied. This latter constraint was applied to ensure a fair comparison; in the natural world search strategies are often physiologically limited and the same would apply to physical implementations of naturally inspired systems.
Figures 1 to 5 illustrate the search patterns and were taken directly from the simulation environment. The shaded line shows the agent's path over a given duration, the period of time spent in each square is indicted by its shade, darker squares indicating more time spent in that area. Note this illustrates agent location and not sensor coverage.
Each natural search pattern was implemented such that it reflected the natural strategy it was inspired by. Random walks followed Equation (1) with leg lengths being set by truncating (removing fractions of a unit) the result of −μ√rand, where rand is a uniformly distributed random number in the range [0,1]. As an exception, for straight line search only, the random numbers were drawn from the range 0·0005 <rand ⩾1 in order to constrain for pragmatic reasons the leg lengths, values less than 0·0005 resulting in excessively large legs. Additionally, in keeping with the literature (Bell, Reference Bell1991), the mean turn angle of straight line searching was restricted to 35°. The raw leg lengths, for all three random walks, were then scaled up to suit the search area by a factor of 10 in keeping with agent sensory and speed capabilities. As can be seen in Figure 1 (left and right), the resulting paths were similar for Brownian motion and Lévy paths (which accounts for the similarity in their performance, as presented in Section 5). A typical path of an agent applying straight line search is shown in Figure 2 (left); this algorithm was further utilised in the extensive phase of the ACS search.
Figure 1. Typical movement pattern produced by, left: Brownian movement search and ACS (intensive phase); right: Lévy path search.
Figure 2. Typical movement pattern produced by, left: straight line search and ACS (extensive phase); right: saltatory search (note: dark points on route highlight points where the agent paused and searched intensely).
Saltatory search also applied Equation (1), with μ=2, but extended the leg length by a scaling factor of 100 (rather than 10). This was necessary to prevent the intensive search phases from overlapping and ensured the resulting behaviour (Figure 2, right) replicated its natural world counterpart. A further modification to the parameters provided in the literature was the reduction in the Giving Up Time (GUT) of the intensive search, this was made in acknowledgement of the environment, the targets were not hidden and to linger for too long (where there was plainly no target) would not have mimicked natural predators. In applications where targets could hide, for example in dense vegetation, GUT times would be expected to be extended accordingly.
Prior to target detection, bacterial search slowed the agent down by 50% and maintained exceptionally high turn-rate turning (tumbling) and Brownian motion (swimming) for equal periods of time. Figure 3 (left), illustrates the limiting effect this had on the explorative aspect of the strategy. Upon target detection the whole group sped up and switched to an unequal turn and movement pattern (ratio of 2:1). This mimicked the behaviour of bacteria in the presence of a positive nutrient gradient as illustrated in Figure 3 (right).
Figure 3. Typical movement pattern produced by bacterial search, left: no targets detected; right: targets detected.
Fruit fly search utilised representative movement patterns since the systems and stimuli to switch between phases of flight described in the literature were absent in this application. To reproduce the required behaviour the agent applied repeated two phase movement consisting of a long, straight movement followed by a series of saccades; the saccades being short legs separated by turns of 90° ±5°. The resulting movement pattern is shown in Figure 4 (left).
Figure 4. Typical movement pattern produced by, left: fruit fly search; right: random search.
Both deterministic patterns were implemented by presenting the agents with different outbound and return routes, as illustrated in Figure 5. Both began in the top left hand corner of the search space and followed a series of waypoints to a final destination; in the systematic pattern this was the bottom right of the space and in the spiral it was the centre. Both strategies then took an alternative route back to the start. To ensure complete space coverage it was necessary for the sensor coverage to overlap. This was essential when searching for static targets and was identified as a weakness of the strategies: if an error in the pattern, or an obstacle, rendered an area occluded from the sensor's field of view, then a target at that location could remain undetected.
Figure 5. Deterministic search patterns (left: spiral, right: systematic grid).
The random search pattern was implemented, without the use of turn rate probabilities as utilised by naturally occurring random walks, to provide a relatively stable movement whilst maintaining sensory coverage. This was achieved by setting a stochastic leg length (limited to 20 steps) prior to turning with a random heading change of maximum ±20°; Figure 4 (right) shows a typical movement path.
4. EXPERIMENTS
Experiments were based on the two relevant search components, locate-only (for static targets only) and locate-and-attack. In locate-only assessment the target was removed immediately on detection whilst locate-and-attack required the agent to move to within 10 units of the target before it could be removed; both types of experiment were performed to allow assessment of whether the period between detection and ‘capture’ was influential on the systemic performance of any of the strategies. Targets could either be static (clustered or uniformly distributed) or dynamic (deterministic or non-deterministic movement). Swarming was not enabled against static targets because the cooperative behaviour would not provide any benefits.
Experiments using static targets were set up where small and large groups of agents (5 and 20 respectively) were tasked with detecting and ‘destroying’ low and high numbers of targets (4 and 20 respectively) that were either uniformly distributed or arranged in clusters of four. Larger agent group sizes were tested but were found to mask the effect of the search strategy, i.e. since there were so many agents that the targets were being detected regardless of strategy, with results dictated by the random initial positions of the agents.
Dynamic targets either represented non-deterministic intruders looking for targets of opportunity or deterministic attackers following pre-set attack profiles against two, non-central defended positions. Opportunistic attackers could assume three representative movement patterns based on those available to the defenders; these were Brownian motion (to represent targets with high turn-rates), the fruit fly inspired pattern (to represent strategies that ranged further) and random. To assess performance across a range of agent/target speed relationships, dynamic experiments were repeated for targets at constant relative speeds in the range 0·1 to 2·0 times the maximum agent speeds. During dynamic testing the small defensive group size was increased to 10 agents since 5 agents were too few for the large search space and target encounters were more through random chance than engineered by the search strategies. Swarming with the dynamic neighbourhood developed by Banks et al. (Reference Banks, Vincent and Phalp2008) was enabled for these experiments, allowing the agents to cooperate on the interception of detection targets.
Finally, to assess the relative fuel efficiency of the strategies 20 agents were initialised in a fixed pattern across the search area (Figure 6). All agents were moved for 1000 moves without the presence of a target and the energy requirements recorded, the lowest requirement being the most efficient. Efficiency information is important since the agents could be required to defend the search space for long periods without the presence of targets and more efficient strategies would enable agents to remain operational for longer before returning to base for refuelling.
Figure 6. Efficiency test initialisation.
To evaluate the relative performance, two metrics were adopted:
• Time. Time was a relative metric used to compare strategy effectiveness against static and dynamic targets; it did not represent chronological time but was calculated as the number of stepwise movements made by an agent between commencement and the last target being destroyed. In dynamic environments targets that were destroyed earlier would have spent less time in defended space and thus would have been less likely to cause damage.
• Energy. Fuel efficiency is important in many vehicular applications. To assess the comparative impact of movement strategies on fuel efficiency a standard consumption of 1 unit per straight move was implemented. This was calculated as reducing pro rata with speed, i.e. 10% slower saved 10% fuel, and increasing at 1% per degree turned.
Experiments were repeated 200 times per strategy (2000 for each configuration); to ensure repeatability, representative experiments were also performed using larger sample sizes (2000 per strategy) and results were found to be consistent.
5. RESULTS AND DISCUSSION
Initial statistical analysis of the time based results, using Kolmogorov-Smirnov normality tests, indicated that they were not normally distributed, so Kruskal-Wallis mean rankings were used to compare performance. This approach was validated statistically by calculating the Pearson correlation between time and the number of times targets successfully attacked the defended positions using deterministic attack profiles. The energy based results were found to have normal distribution allowing mean values to be compared meaningfully. This Section begins with the presentation and discussion of strategy performance using the time metric to locate static targets. This is followed in Section 5.2 by the same experiments repeated with agents having to locate and destroy static targets. Section 5.3 investigates performance against dynamic targets, and Section 5.4 reviews the energy requirements of the strategies to assess whether the more successful behaviours are higher energy consumers.
5.1. Static Targets, Locate-only
Against uniformly distributed targets (see Figure 7Footnote 1) strategies that ranged more extensively outperformed those with high turn-rates; this was most significant where small numbers of agents were searching for large numbers of targets because in scenarios where the targets and agents were not initialised in proximity to each other the high turn-rate agents took longer to move to the regions containing targets, a problem that was less likely where agent numbers were large enough to increase the likelihood of agents being dispersed across the search area.
Figure 7. Locate only strategies against static uniformly distributed targets.
Where targets were clustered and agent density was low, the findings described above generally held (see Figure 8), although, somewhat surprisingly, the expected improvement in comparative performance of ACS did not occur; this was due to the targets being removed immediately upon detection. Under normal conditions, i.e. when the ACS-driven agent discovers a target, it will track it until destruction, after which it will enter an intensive search phase. In this scenario, of locate-only experimentation, the agent will often be located some way from the cluster centre (due to the range of sensory perception) when entering the intensive search phase and therefore may not reach other targets in the cluster. Also notable in this series of experiments was the contrast between the spiral strategy's excellent performance when few agents were seeking large numbers of targets and its poor performance where agent numbers were high and target numbers low. The former being due to the efficient manner in which small numbers of agents eventually cover the whole search area whilst the latter was a result of the agents rarely turning within a cluster, so targets were passed by despite agents discovering others nearby.
Figure 8. Locate only strategies against static clustered targets.
5.2. Static Targets, Locate and Destroy
Generally, the results for uniformly distributed targets held when agents were required to move close enough to the target to destroy it (compare Figure 7 and Figure 9). Bacterial search may have been expected to improve its relative performance since its agents would switch to a wider ranging search during systemic target detection (Figure 3). This failure to improve was relative to other strategies using mean rankings, its actual performance improved significantly; for example comparing the mean time (20 agents against 20 targets) the performance improved by 23·6% whilst all other strategies remained at similar levels (the next largest change was Brownian motion, with 6·5% improvement).
Figure 9. Locate and destroy strategies against static uniformly distributed targets.
The improvement expected from the ACS strategy against clustered targets was evident when the agents were required to move close enough to destroy the target (see Figure 10). This was because the switch to intensive search generally occurred closer to the cluster centre and, therefore, provided the agent had sufficient sensory acuity, increased the likelihood of other localised targets being detected. Where a priori knowledge exists regarding the level of likely clustering then strategic decisions can be made regarding the intensive search; for example, if clustering is wider than can be detected by normal sensor range then more speed could be maintained to allow the agents to range further whilst having the high turn rate required to cover the area. The two-phase approach of bacterial search also paid dividends in the clustered environment; this time with sufficient improvement to markedly improve comparative performance provided sufficient agents were present to achieve an initial detection.
5.3. Dynamic Targets
In the dynamic environment where targets followed deterministic routes, the results presented in Figure 11Footnote 2 show that as the targets speed up the ranging search techniques become less effective whilst those with higher turn rates become more attractive. This was most notable with Brownian and bacterial making large gains in relative performance at the expense of spiral and random searches. All three of the highest turn rate strategies generally outperform the ranging strategies, except at the slowest target speeds where the target movement is insufficient to bring the opposing individuals to close proximity. As target speed increases beyond agent speed, the performance difference once again reduces as target–agent encounters become more inevitable through chance; although, the strategy remained influential, as can be seen from the generally better performance at the fastest target speeds.
Figure 10. Locate and destroy strategies against static clustered targets.
Figure 11. Mean rankings of 10 agents against 4 targets moving deterministically.
Where the targets moved randomly (Figure 12), the increased performance of the high turn rate strategies was less pronounced, and advantages over ranging strategies did not occur until the targets were moving faster than the agents, after which relative performance generally held steady regardless of speed. Once again, this was because the ranging behaviour of the targets had increased such that encounters were partially a result of chance, with the likelihood increased due to the high turn rates of Brownian bacterial and Lévy searches.
Figure 12. Mean rankings of 10 agents against 4 targets moving randomly.
The movement of Brownian motion targets was such that even at high speeds the targets ranged very little across the search space (Figure 13). This impacted on the bacterial search because its reduced speed under ‘no-target-detection’ scenarios reduces its ranging behaviour. The low rate of performance gains of the high turn rate strategies can also be attributed to this phenomenon; the rate is proportional to the increase in the Brownian targets' movement across the search area.
Figure 13. Mean rankings of 10 agents against 4 Brownian motion targets.
Performance against targets that utilise fruit fly type movement (Figure 14) was similar to that of random movement (Figure 12); this was due to the similarities in the overall ranging properties of the movement (compare Figure 4 left and right). However, actual performance against both movements were the not the same, Figure 15 illustrates that, with the exception of spiral search, all strategies took less time to destroy fruit fly targets; this was because the two phase nature of the fruit fly movement made it more susceptible to both the high and low turn rate search types (inter-saccade and saccade phases respectively).
Figure 14. Mean rankings of 10 agents against 4 fruit fly targets.
Figure 15. Mean time for 10 agents to destroy 4 targets moving at maximum agent speed.
Where 20 agents were used (Figure 16 through to Figure 19) the same performance patterns generally held, indicating that the effect was independent of agent density; although logic dictates that too few or too many agents render the search strategy irrelevant since in the former case encounters would be more coincidental and in the latter inevitable.
Figure 16. Mean rankings of 20 agents against 4 targets moving deterministically.
Figure 17. Mean rankings of 20 agents against 4 targets moving randomly.
Figure 18. Mean rankings of 20 agents against 4 Brownian motion targets.
Figure 19. Mean rankings of 20 agents against 4 fruit fly targets.
5.4. Energy Consumption
In search energy efficiency tests (without the presence of targets), bacterial and saltatory search dominate due to the reduction in velocity (Table 1). Aside from those two cases, all other strategies maintained a constant speed, and, therefore, the high turn rates of Lévy and Brownian predictably had the highest energy requirements. The saccade phase of the fruit fly search imposed heavy energy needs when compared with the two deterministic patterns that were the only other strategies to include in-built straight legs. Whilst ACS and straight line searches were almost identical due to ACS utilising straight line searching during pre-detection search. Conversely, spiral and random search requirements were coincidental since, although random search turned more frequently, all other things being equal, it had a smaller mean turn angle. Standard deviations were all similar with the exception of saltatory search whose increased deviation was due to the stochastic, chronological switch between low and high turn rates.
Table 1. Mean energy consumption.
It should be borne in mind that this test covers a limited period, and as search times increase, the differences would grow wider. Furthermore, in a target-laden environment ACS efficiency would increase on detection since although an agent increases its turn-rate, it decreases its speed at the same time.
6. CONCLUSIONS
Several nature-inspired search strategies have been examined alongside deterministic and random approaches in a simplified sensor based agent simulation. Performance against static targets was shown to be dependent on target distribution, swarm size and, to a lesser extent, target density. Furthermore, there are conditions upon which the type of search becomes irrelevant, such as where defensive groups are oversized and target speeds are too fast; it could be argued that under these circumstances it would be most profitable to use the most fuel efficient strategy.
Against uniformly distributed static targets, agents that apply strategies to cover unchecked space performed best (i.e. spiral for small groups and straight line for large groups). Somewhat surprisingly, the systematic grid pattern did not perform well; this was considered to be due to the amount of path crossing, and, hence, overlapping search effort.
Where items were clustered, ACS dominated due to its switch to intensive search following target destruction, supporting previous results from research in ecological modelling (Baum and Grant, Reference Baum and Grant2001). There are two areas of this search that could be modified to further improve its effectiveness. In the interests of fair experimentation, the initial ACS search phase was implemented as the ranging straight line search, in keeping with its natural inspiration (hence the two strategies had similar performance against uniformly distributed targets). However, where the goal is to produce the most effective overall strategy, initial target detection for small groups would be more expedient using the spiral search, as discussed above. Indeed, the bi-phase strategy could be employed by all the strategies where a priori information indicated that target clustering was likely. GUT was fixed for this implementation and was based on time after last target detection. GUT in the natural world can be based on other factors such as, inter alia, likelihood of predation upon the predator, as in the juvenile plaice (Hill et al., Reference Hill, Burrows and Hughes2000) or seasonal prey abundance, as in European polecats (Lode, Reference Lode2000).
GUT is important when implementing a bi-phase intensive/extensive strategy, since whilst fruitless intensive search is temporally inefficient and, conversely, insufficient intensive search in a patchy environment can also be detrimental to performance (see Figure 20). GUT is not the only factor in a bi-phase strategy's success and, although generally competitive, saltatory search was not as successful as may have been expected, since it is designed to work where targets are hidden, it could have been improved by including a switch to intensive search based on experience as well as time. Nature does provide examples of this (e.g. harbour seals utilising a combination of tidal pattern and ocean topography to switch foraging strategy (Zamon, Reference Zamon2001)). A priori information is useful in such situations, although long term searches in stable environments could implement a learning strategy based on experience. Krakauer and Rodríguez-Gironés (Reference Krakauer and Rodríguez-Gironés1995) indicated that such an approach was possible using a Bayesian learning rule.
Figure 20. Effect of GUT on destroying 20 uniformly distributed and clustered targets by 5 agents employing ACS strategy.
Consistently high turn rates are not good in search of uniformly distributed static targets because they tend to re-cover search space. Bacterial search particularly suffers due to its low effective speed. This effect is not so problematic against clustered targets since the low turn rate strategies tend to miss targets, whereas higher turn rates will usually result in the destruction of the whole cluster.
In dynamic environments the increase in sensor coverage caused by the increased turn rates of some strategies made them more effective. As target speed increased with respect to the agents' maximum speed this became more important since the targets were more likely to move into sensor FOV. Where targets were slower, i.e. less than the agents' speed, the agents' speed was also influential, since it increased the likelihood of the agent moving to an area containing a target. Across all ranging target movement strategies it can be seen that high turn rate search strategies improved their relative performance rapidly, and dominance was maintained though to target speeds that were twice that of the agents. Saltatory search, with its time based bi-phase search, maintained good performance across all target types and speeds. In addition, it was noted that this strategy conserved energy through slower search speed, and, therefore, could increase efficiency with minimal loss of effectiveness.
Notably, none of the search strategies discussed make use of pre-detection cooperation (cooperation is only used post-target detection, through the swarming mechanism discussed in Banks et al. (Reference Banks, Vincent and Phalp2008a)). Searching cooperatively could improve the effectiveness of the search but relies on adequate communication. If cooperative modifications were applied the results from this work could be used to identify effective reversionary strategies for situations in which inter-agent communication was lost through environments that were subject to heavy jamming, other intense levels of electro-magnetic noise, or other causes of practical communications difficulties.
It should also be noted that this study was not intended to be exhaustive in its exploration of natural search strategies. For example, it could be beneficial to model local enhancement (Hinde, Reference Hinde1956), in which animals monitor other animals (not necessarily conspecific) for successful foraging in environments where prey is dense but patchy and those patches are widely dispersed, to improve the systemic reaction to the location of clustered targets.
In summary, the strategies can be divided broadly into high turn rate searches that do not explore the search area widely and low turn rate strategies that range the area with less repeated coverage. The results from the sensor based agent simulations concur with the findings from ethological research: agents employing high turn rate strategies were more effective against faster targets that had low turn rates, and agents using low turn rate strategies were more effective against targets that were slower or had high turn rates (ranged less). Further, agents that applied multiple strategies, switching between them based on environment knowledge could harness the benefits of each. For example, against static targets the agent may search for an initial target using a low turn rate strategy before switching to a high turn rate where target clustering was suspected; this behaviour could be adjusted dynamically based on experience.
