Abstract
Multirotor drones, equipped with sensitive microphones, are being used to measure the ultrasound of bats hunting in the dark, but the bats must first be found.
The Secret Life of Bats is a joint project between the Maersk Mckinney MollerInstitute and the Bioacoustics group of the Biology department, which aims tomeasure the behaviour of wild bats without influencing or affecting them in anyway. Currently, measurement equipment is carried to areas where bats have beenknown to hunt, but this is not a full assessment of their hunting behaviour – only aconfirmation that they hunt this way at this location. Therefore, unbiased search algorithms must be used to measure bats wherever they may be. Go where thebats are, not where they sometimes go.
Automated spatial search algorithms are implemented across many differentfields such as agriculture, inspection of hazardous areas, and search and rescueoperations. Each field, and each different implementation within, has very differenttargets: even in agriculture the targets range from finding ripe fruit to scanning theplants to determine their potential for use as biofuel. The disparity between targetsmeans that there are many specific search algorithms, but this does not mean thatonly one search algorithm will work for one job. The effectiveness of a searchalgorithm at completing its task is directly influenced by many factors including:the type of target, the type of searcher/robot, the amount of time available forthe search, and more. These factors must be properly analysed before an effectivesystem can be designed.
It is, therefore, the aim of this thesis to explore different types of search algorithm to determine what characteristics affect their effectiveness at finding atarget. Specifically, when that target is as fast, agile, and barelyvisible as a bathunting at night.
A simulation was developed in MATLAB to compare two main groups of algorithms: the fixedpath algorithms and the randomisedpath algorithms. As thebehaviour of the search target is critical to understanding the effectiveness of asearch algorithm, a simulated bat was created as a realistic representation of areal bat. The searcher is also a vital part of a search algorithm and so the characteristics of the Secret Life of Bats drone and microphone array were also modeledin simulation. The simulation tested 2 fixed and 2 randomised search algorithms(Sentinel and Lawnmower, Levy and TSP, respectively) each run 100 times perfixed drone speed (1 to 10ms−1). When testing the time it took the algorithmsto find the bat, it was found that the TSP algorithm significantly outperformedall other algorithms: consistently finding the bat within half the time of the otheralgorithms and almost never failing a test. The Levy algorithm was not significantly better than the Lawnmower but did show moderately improved detectiontimes. From these thousands of tests, it was determined that randomisation wasimportant for finding fast targets in large areas. However, a new fixedpath algorithm was created to mimic the characteristics of the TSP and their results weresignificantly similar. It was, thus, proven that it is not the randomisation of a path that improves a spatial search algorithm, but fast expansion away from theorigin with periodic trips towards the centre of the search area. The coverage ofthe search area achieved by the algorithms were also tested, alongside the effectof different battery lives, which ultimately determined that coverage contributesto the effectiveness of an algorithm but not as much as rapid expansion into thearea.
The implications of using a drone in the realworld were also assessed. Theusability, reliability and efficiency of drones were explored in detail to determineif using them to effectively search a large area is practical and safe. This tookthe form of a realworld experiment where an artificial bat chirper, complete withultrasonic transducer and simulated flight path, was created as the target. Thisexperiment did not proceed past the safety testing stage due to significant delays caused by various accidents, public health concerns, and restricted access tohardware. The drone had to be sent for repairs nearly every test, which took aconsiderable amount of time. Ultimately, the use of a drone for autonomouslysearching for bats in large areas at night has been deemed impractical and unsafe,until drones have become more robust, repeatable and more open to third partypath planning.
Beyond the realworld tests, the expansion of the search problem to a multidrone system was also explored. If one searcher is capable of finding a bat withina reasonable time, it is logical to expect that the time will improve with more drones and increase the time spent in the presence of a bat. When more drones are added to make a swarm, there are new considerations that must be addressed, such as whether or not all drones use the same algorithm or if each drone gets a slightly modified version, etc. Therefore, the simulation was modified to test the multidrone searches. The TSP was most effective with one drone and was the most effective all the way up to five drones. The new algorithm, that matched the TSP with one drone, stopped improving at three drones. The use of multiple drones flying each of these algorithms in the realworld was also explored and it was determined that the fixedpath algorithms (the safest with one drone) were significantly more dangerous as more drones are added.
If an algorithm were to be chosen based on the results of the simulations, it would be the TSP. No other tested algorithm shows the same rates of success or the quickest detection times. In theory, it would be perfectly suited for the Secret Life of Bats project. However, the randomised nature of the algorithm makes the real drone unpredictable and thus, unsafe. With one drone, the most commonly used and widely available algorithm (the Lawnmower path) is the safest as it is predictable. However, with more drones the algorithm must converge with other drones which is significantly more dangerous than the other methods. Regardless of how ineffective the algorithm was at finding a bat, the safest is always the Sentinel algorithm. Until drones are safer, the better algorithms will be hard to implement.
The Secret Life of Bats is a joint project between the Maersk Mckinney MollerInstitute and the Bioacoustics group of the Biology department, which aims tomeasure the behaviour of wild bats without influencing or affecting them in anyway. Currently, measurement equipment is carried to areas where bats have beenknown to hunt, but this is not a full assessment of their hunting behaviour – only aconfirmation that they hunt this way at this location. Therefore, unbiased search algorithms must be used to measure bats wherever they may be. Go where thebats are, not where they sometimes go.
Automated spatial search algorithms are implemented across many differentfields such as agriculture, inspection of hazardous areas, and search and rescueoperations. Each field, and each different implementation within, has very differenttargets: even in agriculture the targets range from finding ripe fruit to scanning theplants to determine their potential for use as biofuel. The disparity between targetsmeans that there are many specific search algorithms, but this does not mean thatonly one search algorithm will work for one job. The effectiveness of a searchalgorithm at completing its task is directly influenced by many factors including:the type of target, the type of searcher/robot, the amount of time available forthe search, and more. These factors must be properly analysed before an effectivesystem can be designed.
It is, therefore, the aim of this thesis to explore different types of search algorithm to determine what characteristics affect their effectiveness at finding atarget. Specifically, when that target is as fast, agile, and barelyvisible as a bathunting at night.
A simulation was developed in MATLAB to compare two main groups of algorithms: the fixedpath algorithms and the randomisedpath algorithms. As thebehaviour of the search target is critical to understanding the effectiveness of asearch algorithm, a simulated bat was created as a realistic representation of areal bat. The searcher is also a vital part of a search algorithm and so the characteristics of the Secret Life of Bats drone and microphone array were also modeledin simulation. The simulation tested 2 fixed and 2 randomised search algorithms(Sentinel and Lawnmower, Levy and TSP, respectively) each run 100 times perfixed drone speed (1 to 10ms−1). When testing the time it took the algorithmsto find the bat, it was found that the TSP algorithm significantly outperformedall other algorithms: consistently finding the bat within half the time of the otheralgorithms and almost never failing a test. The Levy algorithm was not significantly better than the Lawnmower but did show moderately improved detectiontimes. From these thousands of tests, it was determined that randomisation wasimportant for finding fast targets in large areas. However, a new fixedpath algorithm was created to mimic the characteristics of the TSP and their results weresignificantly similar. It was, thus, proven that it is not the randomisation of a path that improves a spatial search algorithm, but fast expansion away from theorigin with periodic trips towards the centre of the search area. The coverage ofthe search area achieved by the algorithms were also tested, alongside the effectof different battery lives, which ultimately determined that coverage contributesto the effectiveness of an algorithm but not as much as rapid expansion into thearea.
The implications of using a drone in the realworld were also assessed. Theusability, reliability and efficiency of drones were explored in detail to determineif using them to effectively search a large area is practical and safe. This tookthe form of a realworld experiment where an artificial bat chirper, complete withultrasonic transducer and simulated flight path, was created as the target. Thisexperiment did not proceed past the safety testing stage due to significant delays caused by various accidents, public health concerns, and restricted access tohardware. The drone had to be sent for repairs nearly every test, which took aconsiderable amount of time. Ultimately, the use of a drone for autonomouslysearching for bats in large areas at night has been deemed impractical and unsafe,until drones have become more robust, repeatable and more open to third partypath planning.
Beyond the realworld tests, the expansion of the search problem to a multidrone system was also explored. If one searcher is capable of finding a bat withina reasonable time, it is logical to expect that the time will improve with more drones and increase the time spent in the presence of a bat. When more drones are added to make a swarm, there are new considerations that must be addressed, such as whether or not all drones use the same algorithm or if each drone gets a slightly modified version, etc. Therefore, the simulation was modified to test the multidrone searches. The TSP was most effective with one drone and was the most effective all the way up to five drones. The new algorithm, that matched the TSP with one drone, stopped improving at three drones. The use of multiple drones flying each of these algorithms in the realworld was also explored and it was determined that the fixedpath algorithms (the safest with one drone) were significantly more dangerous as more drones are added.
If an algorithm were to be chosen based on the results of the simulations, it would be the TSP. No other tested algorithm shows the same rates of success or the quickest detection times. In theory, it would be perfectly suited for the Secret Life of Bats project. However, the randomised nature of the algorithm makes the real drone unpredictable and thus, unsafe. With one drone, the most commonly used and widely available algorithm (the Lawnmower path) is the safest as it is predictable. However, with more drones the algorithm must converge with other drones which is significantly more dangerous than the other methods. Regardless of how ineffective the algorithm was at finding a bat, the safest is always the Sentinel algorithm. Until drones are safer, the better algorithms will be hard to implement.
Original language  English 

Awarding Institution 

Supervisors/Advisors 

Publisher  
DOIs  
Publication status  Published  20. Sept 2022 