NGAH, Umi, Kalthum (School of Electrical and Electronic Engineering, Engineering CampusUniversiti Sains Malaysia,Nibong Tebal, Seri Ampangan, Pulau Pinang, 14300, MY)
ZAINAL ABIDIN, Zulkifli (School of Electrical and Electronic Engineering, Engineering CampusUniversiti Sains Malaysia,Nibong Tebal, Seri Ampangan, Pulau Pinang, 14300, MY)
ARSHAD, Mohd, Rizal (School of Electrical and Electronic Engineering, Engineering CampusUniversiti Sains Malaysia,Nibong Tebal, Seri Ampangan, Pulau Pinang, 14300, MY)
NGAH, Umi, Kalthum (School of Electrical and Electronic Engineering, Engineering CampusUniversiti Sains Malaysia,Nibong Tebal, Seri Ampangan, Pulau Pinang, 14300, MY)
ZAINAL ABIDIN, Zulkifli (School of Electrical and Electronic Engineering, Engineering CampusUniversiti Sains Malaysia,Nibong Tebal, Seri Ampangan, Pulau Pinang, 14300, MY)
| CLAIMS 1. A system for a performing a search within a geographical area comprising of a plurality of swarming agents and a central base station (100), characterized in that the plurality of swarming agents carry out the search based on the behavior and flight path of a fly when in search for food or a mate. 2. A system according to claim 1 , wherein the geographical area is a predefined target area defined on a surface of water of a calm water-body or water column, of a geographical area. 3. A system according to claim 1 , wherein the swarming agents are a plurality of autonomous surface vehicles (800). 4. A system according to claim 1 , wherein the fly includes a Drosophila (fruit fly). 5. A system according to claim 3, wherein the autonomous surface vehicles (800) are cylindrical shaped having a diameter greater than its height. 6. A system according to claim 3, wherein the autonomous surface vehicles (800) are propelled by a plurality of propellers (702, 703). 7. A system according to claim 3, wherein each of the autonomous surface vehicles include a rudder that is oriented longitudinally in the same orientation as the propellers (702, 703). 8. A system according to claim 3, wherein each of the autonomous surface vehicles (800) include: a communications block (300) comprising of a RF transceiver unit (301 ); a control block (200) comprising of a computer (201 ), a Universal Serial Bus to Serial Port Converter (202), and a microcontroller (203); an input block (400) comprising of a communications multiplexer (401 ), a compass (402), a Global Positioning System receiver (403) and a depth/temperature transducer (404); an output block (500) comprising of a relay block (501 ), propeller blocks (502, 503) that contain electronics to drive the propellers (702, 703) and a servo block containing electronics that drive the rudder (701 ); and a power block (600) comprising of a plurality of rechargeable battery modules (601 , 602, 603, 604) that supplies power to the control block (200), the communications block (300), the input block (400) and the output block (500). 9. A system according to claim 1 , wherein the central base station (100) comprises of a computer (101 ), a RF transceiver (102) and a battery module (103). 10. A system according to claim 3, wherein each of the autonomous surface vehicles (800) include a compensator that takes into consideration three degrees of freedom that include yaw, surge and sway to compensate for errors in the rudder angle. 11. A system according to claim 8, wherein within the computer (201 ) resides the following algorithms: a search algorithm that dictates the searching method of a predefined target area based on the biological behavior of a Drosophila (fruit fly) when in search for food or a mate; and a boundary navigation algorithm that dictates the method of movement of the individual autonomous surface vehicles (800) within the predefined target area. 12. A system according to claim 11 , wherein the searching method includes a method of movement of the plurality of autonomous surface vehicles (800) within a predefined target area that comprises of the following: defining the target area by arranging the coordinate points of the target area transmitted from the central base station (100) to the plurality of autonomous surface vehicles (800) in a clockwise or counterclockwise direction based on a sequence of increasing or decreasing angles, wherein these angles are the angles made by an imaginary line that is drawn from a predefined reference point to the individual coordinate points of the target area, with respect to the horizontal; navigation of the autonomous surface vehicles (800) within and never exceeding the perimeter of the defined target area; movement of the autonomous surface vehicle (800) within the defined target area in accordance with the Levy probability distribution function conforming to the flight path of the Drosophila (fruit fly) when in search for food or a mate; and a simple collision avoidance method ensuring that the distance between each of the autonomous surface vehicles (800) are greater than the diameter of an individual autonomous surface vehicle unit (800) in addition to a predetermined tolerance. 13. A method for carrying out a search based on the biological behavior of the Drosophila (fruit fly) when searching for food or a mate, wherein the method comprises the steps of: i. initializing a plurality of autonomous surface vehicles (800) by uploading pre- simulated waypoints that seek to plan the path of the autonomous surface vehicles (800) and coordinate points of a target area in which a target resides that are received via RF transmission from a central base station (100); ii. movement of the plurality of autonomous surface vehicles (800) toward the target area defined by the coordinates received from the central base station (100) during initialization; iii. each individual autonomous surface vehicle (800) of the plurality of autonomous surface vehicles (800) searching for a desired target location in which a desired target resides while concurrently sending, receiving and comparing information from other autonomous surface vehicles (800); iv. each individual autonomous surface vehicle (800) of the plurality of autonomous surface vehicles (800) comparing location information such as GPS coordinates, depth and temperature data with other autonomous surface vehicles (800) to identify a location known as a "good location" that meets a predefined set of criteria known as "attractiveness" wherein the autonomous surface vehicle (800) in question will thus either proceed to the identified "good location" or continue searching for the "good location" (if it has not already been identified) for a predetermined time period; v. each individual autonomous surface vehicle (800) of the plurality of autonomous surface vehicles (800) continue searching for a "good location" for a predetermined time period, that meets the attractiveness criteria if such a location was not already identified in the steps (iii) to (iv); vi. each individual autonomous surface vehicle unit (800) of the plurality of autonomous surface vehicles (800) moving to an identified "good location"; vii. each individual autonomous surface vehicle (800) of the plurality of autonomous surface vehicles (800) verifying the identified "good location" based on an "attractiveness" criteria irrespective of whether the autonomous surface vehicle (800) has found a "good location" wherein, if it is verified that the autonomous surface vehicle (800) in question resides on a "good location", it will proceed to the subsequent step otherwise it will cycle through the steps (iii) to (vi); viii. each individual autonomous surface vehicle (800) comparing location data of the "good location" with a second set of criteria known as " fitness/profitability" upon confirming the identification of a "good location" based on "attractiveness" ; ix. each individual autonomous surface vehicle (800) determining if the "good location" identified closely matches the "fitness/profitability" criteria wherein if the location data closely match the "fitness/profitability" criteria, the autonomous surface vehicle (800) in question will maintain its current location and proceed to the subsequent step, otherwise the autonomous surface vehicle (800) will cycle through preceding steps, steps (iii) to (viii) ; and x. each individual autonomous surface vehicle (800) comparing location data of its currently occupied "good location" with other "good locations" identified by other autonomous surface vehicle units (800) by sending and receiving information with other autonomous surface vehicles (800) before looping back to the last two steps, steps (viii) and (ix). |
ALGORITHM
The present invention relates generally to autonomous surface vehicles and more particularly to a system comprising a fleet of autonomous underwater vehicles that carry out a search related to an underwater region of a geographical area according to an algorithm based on the behavior of a fly.
BACKGROUND OF THE INVENTION
Underwater investigations are conducted for a variety of reasons to include mine hunting, search and rescue operations, bottom mapping, marine life studies, the viewing of maritime accidents and shipwrecks and environmental investigations.
Modern hydrological surveying relies heavily on both software as well as hardware. In suitable shallow water areas Light Detection and Ranging (LIDAR) may be used. Equipment can be installed on inflatable craft, such as Zodiacs, small craft, Autonomous Underwater Vehicles (AUVs), Unmanned Underwater Vehicles (UUV's), Autonomous Surface Vehicles (ASV's) or large ships, and can include side- scan, single beam and multi-beam equipment. At one time different data collection methods and standards were used in collecting hydrographic data for maritime safety and for scientific or engineering bathymetric charts. Increasingly with the aid of improved collection techniques and computer processing the data is collected under one standard and extracted for a specific use.
After data is collected, it has to undergo post-processing. A massive amount of data is collected during the typical Hydrographic survey, often several soundings per square foot. Depending on the final use (navigation charts, Digital Terrain Model, volume calculation for dredging, topography, Bathymetry) this data must be thinned out. It must also be error corrected (bad soundings) and corrected for the effects of tides, waves/heave, water level and water temperature differences (thermo dines.) Usually the surveyor has additional data collection equipment on site to record the data required for correcting the soundings. Final output of charts can be created in a combination of specialty charting software or a CAD package, usually AutoCAD ®. Autonomous Surface Vehicles (ASVs) date back to World War II, though it was not until the 1990's that they reach widespread use. ASVs have found many military applications in the past. These included minesweeping, reconnaissance and surveillance. Apart from military applications ASVs also find use in scientific applications. These applications include collection of samples and oceanographic research.
Until relatively recently, ASVs have been used for a limited number of tasks dictated by the technology available. With the development of more advanced processing capabilities and high yield power supplies, ASVs are now being used for more and more tasks with roles and missions constantly evolving.
Among the recent developments pertaining to the use of ASVs in scientific and military applications, include utilizing a fleet of ASVs for data collection with a higher spatial and temporal resolution. The fleet of ASVs in the aforementioned applications, act to navigate in swarms that utilize physicomimetic or in some cases animal inspired swarm algorithms to navigate towards a predefined area for the purposes of data collection.
The advantages of utilizing a fleet of ASVs that prescribe to a predetermined swarming algorithm to thus form a plurality of swarming agents include the ability of the ASV swarm to provide lake mapping or ocean mapping with a very much higher spatial and temporal resolution as compared to the use of an individual unit of an ASV. Apart from that, Swarming ASVs have the advantage of cooperative tasking i.e. each individual swarming agent or ASV work together to accomplish a predetermined goal in a much shorter time and more reliable manner as compared to a single agent. In addition the cost per-unit of the ASV due to the economics of scale reduces when the ASVs are produced in fleets instead of being manufactured on a per-unit basis.
The cooperation of large numbers of swarming agents dedicated towards a single mission objective allows a particular swarm of ASVs to maintain a robust and fault tolerant formation. If one or even several agents are lost, the mission can still continue, unlike with a single ASV. Redundancy within the group adds strength to this robustness
The most common swarming algorithms that are utilized by ASVs include particle swarming, genetic swarming and insect behavior swarming algorithms based on ant and bee swarming behavior.
Thus far there has yet to be a swarming algorithm based on the biological behavior of the drosophila or fruit-fly's searching behavior that is implemented on a fleet of ASVs.
SUMMARY OF THE INVENTION This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the claimed subject matter.
The present invention is directed to methods and systems for performing a search operation related to an underwater region of a geographical area using one or more swarming agents.
In one aspect of the present invention there is provided a system for performing a search operation based on the swarming meta-heuristic of the Drosophila, the system comprising a fleet of autonomous surface vehicles (ASV) and a central base station.
Each autonomous surface vehicle (ASV) unit of the fleet is a swarming agent that is designed to be in the form of a cylindrical disc of predetermined height and diameter. The autonomous surface vehicles (ASV) unit includes: a first and second propeller disposed at the sides of the underside of the ASV that serve to propel the ASV on a surface of a calm water-body or water column, of a geographical area; a rudder located at the underside of the ASV along the axis of symmetry and is further longitudinally oriented in the same direction as the propellers; an electronic compensator that compensates for any deviation of the rudder angle that may cause the ASV to not reach its intended position at a desired trajectory in a required time frame; a radio frequency transceiver that enables the ASV to communicate with another ASV and a central communications station via a distributed control architecture.; and a Global Positioning System (GPS) receiver to aid the ASV in navigation of a surface of a calm water-body or water column, of a geographical area. The central base station includes a computer that has a communications link to the radio frequency transceiver unit that is powered by a battery module.
Preferably the radio frequency transceiver is a transceiver that transmits and receives radio frequency signals in the range of 915MHz to 928MHz.
Preferably, the battery module is a lithium ion rechargeable battery module.
Each of the plurality of autonomous surface vehicles ASV executes a series of algorithms, which include: a first algorithm that enables the plurality of ASV swarming agents to mimic the biological behavior of a fly from the genus Drosophila (fruit fly), when the fruit fly is in search of food or a mate, to thus enable the efficient searching of an underwater region of a geographical area. a second algorithm that mimics the flight pattern of the Drosophila (fruit fly) when in search for a mate or food in accordance with a Levy probabilistic distribution; and a third algorithm that is a navigation algorithm that enables each individual unit of the plurality of swarming agents, once deployed on the surface of a calm water-body or water column, of a geographical area, to navigate within a predefined boundary.
Preferably, the surface of the calm water-body or water column, of a geographical area includes the surface of a lake, the surface of the water contained in a dam, the surface of a wide river, and the surface of a mining pool. In another aspect of the present invention, there is provided a method for implementing a search operation in an underwater region of a geographical area based on the biological swarming behavior and flight pattern of a fly from the genus Drosophila (fruit fly) in conjunction with the fleet of autonomous surface vehicles (ASVs) of the present invention, the method comprising the steps of: deploying a plurality of swarming agents onto surface of the calm water-body or water column, of a geographical area; transmitting geographical location information of the target area from the central base station to a plurality of swarming agents; the plurality of swarming agents navigating towards the target area upon receipt of position data pertaining to the location of the target area from the central base station; each of the plurality of swarming agents proceeding to search for the desired target within the target area while concurrently communicating with each other via the central base station upon confirmation of arriving at the target area by exchanging and comparing location information such as GPS coordinates, depth and temperature data with other swarming agents. each of the plurality of swarming agents, determining the availability of a "good location" wherein , a "good location" is defined as an "attractive location" based on a first set of predefined criteria; each of the plurality of swarming agents continue searching for a "good location" if such a location was not already identified based on location "attractiveness" criteria in the preceding step. each of the plurality of swarming agents moving to an identified "good location" within the target area such that its trajectory is in accordance with the Levy probabilistic distribution based on the comparison of position data communicated from other swarming agents and its own gathered data; each of the plurality of swarming agents verifying the identified "good location" based on "attractiveness" criteria irrespective of whether a "good location" has been identified or not, wherein, if it is verified that the swarming agent in question resides on a "good location" , it will proceed to the subsequent step otherwise it will cycle through the preceding steps ; each of the plurality of swarming agents comparing location data of the "good location" with a second set of criteria known as " fitness/profitability" upon confirming the identification of a "good location" based on "attractiveness" ; each of the plurality of swarming agents determining if the "good location" identified closely matches the "fitness/profitability" criteria wherein if the location data closely match the "fitness/profitability" criteria, the swarming agent in question will maintain its current location and proceed to the subsequent step, otherwise the swarming agent will cycle through preceding steps; and each of the plurality of swarming agents comparing location data of its currently occupied "good location" with other "good locations" identified by other swarming agents by sending and receiving information with other swarming agents before looping back to the last two steps preceding the current step.
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 is a flowchart of the behavior of Drosophila (fruit fly) from the genus Drosophila while searching for food and a possible mate; Figure 2 is a flowchart of the behavior of fly from the genus Drosophila while searching for food and a possible mate that has each of its blocks correlated to the operation of the swarming agents of the present invention; Figure 3 is a diagram illustrating the top view of the inside of the physical autonomous surface vehicle (ASV) unit according to an embodiment of the present invention;
Figure 4 is a diagram illustrating the bottom view of the physical autonomous surface vehicle (ASV) unit according to an embodiment of the present invention;
Figure 5 is a diagram illustrating the internal modular hardware blocks of an individual autonomous surface vehicle (ASV) unit and base station of the present invention;
Figure 6 is a diagram illustrating an individual (ASV) unit in one embodiment of the present invention; Figure 7 is a diagram illustrating the overview of the system of swarming ASVs of the present invention;
Figure 8 is a diagram illustrating the respective side, front and plan views of a particular embodiment of an individual ASV of the present invention wherein the magnetic compass is mounted above the cylindrical body of the ASVs by a predetermined height.
Figure 9 is a graph of a De Jong benchmarking function, a maximization function; Figure 10 is a graph of a Rosenbrook benchmarking function, a minimization function; Figure 11 is a graph illustrating the route of a single swarming agent with 5 waypoints that moves in accordance with the Levy flight pattern of a fly from the genus Drosophila; and Figure 12 is a graph illustrating the route of 8 individual swarming agents with 5 way points that move in accordance with the Levy flight pattern of a fly from the genus Drosophila.
DETAILED DESCRIPTION OF THE INVENTION
The detailed description set forth below in connection with the appended drawings is intended as a description of exemplary embodiments and is not intended to represent the only forms in which these embodiments may be constructed and/or utilized. The description sets forth the functions and the sequence for constructing the exemplary embodiments. However, it is to be understood that the same or equivalent functions and sequences may be accomplished by different embodiments that are also intended to be encompassed within the scope of this disclosure. The present invention will now be described with reference to figures 1 to 12.
The present invention is a system for performing a search operation based on the swarming meta-heuristic of the Drosophila, the system comprises of a fleet of autonomous surface vehicle (ASV) 800 and a central base station 100.
The fleet of autonomous surface vehicles (ASVs) 800 are utilized to carry out a variety of operations that include lake bed, dam, Wide River, and sand mining area (i.e. calm water geographic regions) underwater topographic mapping with a high spatial and temporal resolution, such that each autonomous surface vehicle (ASV) 800 is pre-installed with a meta-heuristic swarming algorithm in an area of its memory that resides in an "Ultra Mobile Personal Computer" (UMPC) 201 which is nothing more than a small compact personal computer that acts as the central processing unit of the autonomous surface vehicles (ASVs) 800. The UMPC 201 resides in the control block 200. This meta-heuristic swarming algorithm that resides within the UMPC 201 is based on the biological behavior and flight pattern of the Drosophila or fruit fly when in search for a food or a mate.
The fleet of autonomous surface vehicles (ASVs) 800, mimic the swarming behavior of the Drosophila or fruit-fly with the aid of a software algorithm that is preinstalled in an area of memory residing in the control block 200 and communicate with each other and a central base station 100 via a 900Mhz RF transceiver 301 in a distributed control architecture. Navigation data is obtained and transmitted to the central base station 100 with the aid of GPS (Global Positioning System). The accuracy of the GPS can be further increased by using DGPS via a GNSS (Global Satellite Navigation System) infrastructure 900.
Each autonomous surface vehicle (ASV) 800 of the present invention is a cylindrically shaped vehicle of diameter 38cm, and is propelled by two slim line water pumps (Max 8 liter high/12V/1.6 A) that serve as propellers 702, 703. Each ASV unit 800 is further steered by a micro servo rudder (Metal Gear Tower Pro MG90) 701 that is driven by a servo drive 504. Each ASV unit 800 is powered by a plurality of lithium ion battery modules that constitute the power block 600 of the autonomous surface vehicle (ASV) 800.
The plurality of ASVs 800 of the present invention are designed to be cylindrical in shape to enable it to move in an omni-directional manner, based on the motion behavior of the Drosophila while searching for food . This ASVs 800 is a non- holonomic type autonomous robotic platform.
The internal electronic hardware organization of an individual autonomous surface vehicle (ASVs) 800 unit and the central base station block 100 of the present invention will now be described with reference to figures 3 to 6. Each autonomous surface vehicle (ASVs) 800 of the present invention consist of five major blocks, a control block 200, a communications block 300, an input block 400, an output block 500 and a power block 600. The control block 200, is the "brains" of an individual autonomous surface vehicle (ASVs) 800, and comprises of an "Ultra Mobile Personal Computer" (UMPC) 200 which is nothing more than a small compact personal computer that acts as the central processing unit of the autonomous surface vehicle (ASV) 800 and further comprises of a USB 2.0 to RS 232 data converter block 202 and a microcontroller unit 203. The communication block 300 consists of a 900MHz RF transceiver unit 301. This block enables communications between individual autonomous surface vehicle (ASV) units 800 and the base station 100. The input block 400 comprises of a ΝΜΕΞΑ (National Marine Electronics Association serial communications protocol or NMEA 0183) multiplexer 401, a NMEA magnetic compass 402, a NMEA GPS receiver 403 and a depth/temperature transducer 404. The input block 400 serves to collect data pertaining to the GPS location, bearing angle and the local depth and temperature measurement of an underwater surface that the autonomous surface vehicle (ASV) 800 is on, and feeds this information to the UMPC 201 via the microcontroller 203. As has been previously mentioned both the UMPC 201 and the microcontroller 203 reside in the control block 200.
The output block 500 comprises of the actuating components of the autonomous surface vehicle (ASV) 800. It consists of a relay block 501 , two propeller blocks 502 and 503 respectively and a servo block 504. Depending on the input fed by the input block 400 and the inputs from the UMPC block 201 and 900MHz RF transceiver block 301 to the microcontroller unit 203, the microcontroller 203 actuates the propellers 702, 703 via the relay block 501 and propeller blocks 502, 503 and the rudder 701 via the servo block 504. The internal electronic hardware blocks 300, 500 and 400 are powered by the rechargeable lithium ion battery blocks 601, 602, 603 and 604 of the power block 600.
The plurality of autonomous surface vehicles (ASV) 800 act as swarming agents in the system of the present invention in conjunction with a central base station 100 that serves to provide a certain means to coordinate and track the movements of every individual autonomous surface vehicle (ASV) 800 of the fleet of (ASVs) 800.
The central base station 100 simply comprises of a suitable laptop or personal computer 101 that has a communications link to a 900MHz RF transceiver unit 102. The 900 MHz RF transceiver unit 102 of the central base station block 100 is powered by a rechargeable lithium ion battery module 103. The central base station block 100 transmits and receives information to and from the plurality of (ASVs) 800 in the field via the central base station's RF transceiver unit 102. The central base station's 100 and (ASVs) 800 900MHz RF transceivers are capable of enabling communications amongst (ASVs) units 800 and the central base station 100 via a distributed, control architecture with a maximum distance of thirty two kilometers, with clear line of sight. Each individual autonomous surface vehicle (ASV) unit 800 have embedded within the memory of the microcontroller 203 a PID compensation algorithm that compensate for any probable error in rudder 701 angle due to drift by taking into account yaw, surge and sway degree of freedoms. The PID control apparatus of each ASVs unit 800 includes the microcontroller 203, servo drive 504, NMEA compass 402, GPS receiver 403 and rudder 701.
The cylindrical shape of the ASV unit 800 of the present invention has a high sway and surge added mass but no yaw added mass. Hence the ASV unit 800 is not designed for stability in the yaw direction in line with the requirements of the present invention, that the plurality of individual ASV units 800 mimic the flight path of the Drosophila (fruit fly) when in search for food or a mate. With reference to figures 3 to 4, the propellers and the rudder are oriented in the surge direction.
With reference to figures 6 and 8, in a particular embodiment of the present invention, the magnetic compass 402 is mounted on top of the ASV unit 800 by a predetermined height with the aid of an appropriate support bracket.
With reference to figures 1 , 2 and 7, the swarming algorithm of the Drosophila or fruit fly which is mimicked by the plurality of autonomous surface vehicle ASVs 800 of the present invention will be described in detail. The plurality of autonomous surface vehicles ASVs 800 of the present invention serve as swarming agents to implement an animal behavior inspired meta-heuristic swarming algorithm to carry out underwater topographic mapping of a lake-bed or ocean floor with a high temporal and spatial resolution. More particularly the present invention is a meta-heuristic swarming algorithm based on the biological behavior and flight pattern of a Drosophila or fruit fly.
The meta-heuristic algorithm of the Drosophila enables the higher spatial and temporal resolution of mapping an underwater topography because it optimizes the movement of each swarming agent or autonomous surface vehicles ASVs unit 800. Each autonomous surface vehicles ASVs unit 800 that acts as a swarming agent of the present invention tries to optimize the detection of a very faint target and optimize the movements in space confined within the source of the target. In a preferable embodiment of the present invention, the plurality of autonomous surface vehicle ASVs 800, are tasked with the mission of finding the deepest underwater location. Hence the target in our context of mapping the underwater topography of a lake is a point that refers to the deepest location of the lake. The plurality of autonomous surface vehicles (ASVs) 800 that act as swarming agents, inherently collect sufficient data to provide a map of the underwater topography of a certain lake by scanning for a location with the greatest depth within a predefined boundary area. Initially upon deployment of the plurality of autonomous surface vehicles (ASVs) 800, the pre-simulated waypoints that seek to plan the path of a plurality of ASVs 800 or swarming agents are uploaded from the central base station 100 to each of the individual swarming agents of the present invention. Apart from the waypoints, the coordinates of the target area that define the boundary of the area of navigation and the coordinate of a reference point that is used as a reference to arrange the coordinates of the target area received by each of the plurality of ASV units 800 is also uploaded to each of the individual ASV units 800.
The movements of an individual autonomous surface vehicle (ASV) 800, follow the flight pattern of the Drosophila, such that each autonomous surface vehicle (ASV) unit 800 moves according to a trajectory that conforms to a probabilistic distribution called the Levy Flight Path. The surface-water movement of the autonomous surface vehicle (ASVs) 800 of the present invention in accordance with the Levy distribution is characterized by segments of straight trajectory interspersed with transient "spikes" called saccades whenever they turn left or right. The movements of the autonomous surface vehicles (ASVs) 800 in this manner, increases the likelihood of finding the target location within the predefined target area.
The plurality of autonomous surface vehicles (ASVs) 800 act to swarm a particular underwater topography area that is to be mapped. The plurality of ASV units 800, swarm the designated target area, in accordance with the biological behavior of the Drosophila. Initially, upon deployment of the plurality of autonomous surface vehicles (ASVs) 800, onto the surface of a calm water-body or water column, of a geographical area such as the surface of a lake and once the initialization of the ASVs 800 as outlined in a preceding paragraph is complete, each autonomous surface vehicle 800 will navigate to the designated target area. This corresponds to block 1001 as indicated in the flowchart of figures 1 and 2. Upon confirmation of arriving at the target area from the central base station 100, the plurality of swarming agents, proceed to search for the desired target within the target area while concurrently communicating with each other. This corresponds to block 1002 as depicted in the flowchart of figures 1 to 2.
In communicating with one another the plurality of ASVs 800 exchange and compare information with one another to determine a "good location". A "good location" is defined as a location that meets a predefined set of criteria. These criteria are set by the operator of the system and stored in the memory of the UMPC 201 via radio frequency (RF) transmission to the plurality of swarming agents 800 from the central base station 100 during initialization upon deployment. Each swarming agent ASV 800 carrying out the search for the deepest location i.e., the target location, will compare information of an identified location as a result of its own search and other locations identified by other swarming agents 800 within the predetermined boundary area, this corresponds to block 1003 of figure 1 and 2.
The predefined set of criteria for the identification of a "good location" is termed as "attractiveness". If a "good location" has been identified in block 1003 that matches the criteria for "attractiveness" then the swarming agent or individual ASV 800 in question, will move towards the "good location", this corresponds to block 1005 of figures 1 and 2. The ASV unit 800 in question will then proceed to verify that it has found a "good location" based on "attractiveness criteria". This corresponds to block 1006 of the flowchart of figures 1 and 2.
If on the other hand, no "good location" has been identified in block 1003 based on the comparison of location information received from other ASV units 800, the ASV unit 800 in question will proceed by searching for a "good location" based on the "attractiveness" criteria on its own without depending on feedback from the other swarming agents or ASV units 800, this corresponds to block 1004. Subsequently the ASV 800 or swarming agent in question will proceed to verify if its current location is a "good location" based on the "attractiveness" criteria. This again corresponds to block 1006. The ASV unit 800 or swarming agent, depending on whether a "good location" that matches the "attractiveness" criteria has been found, will either cycle through block 1002 to 1006 in the case that no "good location" has been identified or proceed to compare the identified "good location" based on a second set of criteria in the subsequent block, block 1007.
An ASV unit 800 or swarming agent of the present invention, upon verifying that it has identified a "good location" based on attractiveness criteria as in block 1006, the ASV unit will proceed to compare the "good location" identified with a second set of criteria, known as "fitness/profitability", this corresponds to block 1007 of the flowchart of figures 1 and 2.
In block 1008, if the ASV unit 800 in question determines that the identified "good location" matches the "fitness/profitability" criteria closely, the ASV unit 800 in question will proceed to block 1009 in which it will send/receive and compare location information of other "good locations" that have been identified by other swarming agents. If on the other hand, the ASV unit 800 in question determines that its current location does not meet the "fitness/profitability" criteria, it will move to another location and cycle through steps 1002 to 1008.
If based on the comparison of location information that has been sent and received by other swarming agents with regards to other identified "good locations", the ASV unit 800 in question determines that the other "good locations" identified by the other swarming agents more closely match the "fitness/profitability" criteria, the ASV unit 800 in question will move to that location and sequence through blocks 1002 -1009. Otherwise, the ASV unit 800 in question will maintain its current location, as it has determined that its current identified "good location" meets the "fitness/profitability" criteria and is hence the deepest location according to the mission specified in this description (Until a more desirable/deeper location is identified). The ASV unit 800 will however still cycle through blocks 1007 to 1009
The Boundary Navigation Algorithm of the present invention resides in the UMPC 201 of each individual ASV unit 800 of the present invention. Upon deployment to the surface of a calm water geographical underwater region such as on the surface of a lake or wide river, the plurality of ASV units 800 receive the coordinates of the designated target area, via transmission from the 900MHz RF transceiver 102 of the central base station 100. Upon receipt of the coordinates of the target area from the central base station 100, the plurality of swarming agents will navigate toward the target area. Upon arrival at the target area, the plurality of swarming agents will transmit their coordinates to the central base station 100 and thus await confirmation that the target area has been arrived at.
Upon confirmation of arriving at the designated target area, the plurality of ASVs 800, navigate within the target area based on a prescribed boundary navigation algorithm that resides on the UMPC 201 of each individual ASV unit 800.
The boundary navigation algorithm of the present invention comprises of the following: a. ) An algorithm that arranges the coordinate points transmitted from the central base station 100 according to a predetermined order, to define the boundary of the navigation or target area and thus ensure that the plurality of ASV units 800 navigate within and never exceeding the perimeter of the defined boundary of the target area. b. ) An algorithm based on the flight path of the Drosophila (fruit fly) that generates the points for the movement of the ASV's 800 based on the Levy probability distribution function. c.) A simple collision avoidance algorithm that ensures the plurality of AUVs 800 do not collide with each other while navigating within the prescribed target area.
The boundary navigation algorithm upon receipt of the coordinates of the target area from the central base station 100, will arrange the coordinates in a predetermined order such that each coordinate point is arranged in a clockwise or anti clockwise manner according to either the order of increasing angles or decreasing angles wherein these angles are based on the angles made by an imaginary line connecting each individual coordinate (from the set of coordinates that specify the target area) and a predetermined reference point with respect to the horizontal.
The predetermined reference point is provided by the central base station 100. Based on this arrangement of coordinate points each of the points once connected by an imaginary line according to the sequence of arrangement, define the boundary of the target area. Once the on board boundary navigation algorithm has arranged the points according to afore mentioned order such that afore mentioned imaginary lines interconnecting the target area form the boundary of the target area, the boundary navigation algorithm will dictate the movement of the plurality of ASV units 800 within and never exceeding the perimeter of the defined target area.
With reference to figures 11 and 12 the various positions for the movement of the ASVs 800 within the prescribed boundary area are generated based on the Levy probability distribution function. The movement of each individual ASV unit 800 defined by the Levi flight path or Levy probability distribution function is characterized by segments of straight trajectory interspersed with abrupt movements at ninety degree angles whenever the ASVs 800 turn right or left. These transient "spikes" are called saccades.
Each of the individual ASV units 800 of the plurality of ASV units 800 will also have embedded in the memory of the UMPC 201 a simple collision avoidance algorithm. This simple collision avoidance algorithm ensures that the distance between each individual ASV unit 800 denoted here as D, is greater than the diameter of an individual ASV unit 800 in addition to a predetermined tolerance. Each ASV unit 800 will continuously calculate the distance between itself and the other ASV units 800 based on the coordinates transmitted by each individual ASV unit 800 to the other units of the plurality of ASV units 800.
EXPERIMENTAL RESULTS
The Drosophila swarming algorithm that is embedded in the plurality of swarming agents 800 of the present invention enable the individual ASV units 800 to collect data in its path and change its direction according to stochastic conditions. The Drosophila or Fruit Fly swarming algorithm that are embedded in to the plurality of ASV units 800 of the present invention were tested based on an experiment conducted on 16 hypothetical fruit flies or Drosophilla. The experiment was carried out in order to determine the number of evaluations required by the various insect behaviour algorithms to reach the optimum point of the De Jong Maximization Function and the Rosenbrook Minimization Function respectively. Both these functions are benchmark functions that are utilized to determine the number of evaluations required by a particular insect behavior algorithm to locate a specific point.
With reference to figures 9 and 10, the experiments were done on De Jong and Rosenbrook's functions. The De Jong's function is a maximization problem while the Rosenbrook's function is a minimization problem. Both functions have a long ridge and tend to cause initialization yields at points far from the optimums. All the functions have one peak, thus only the best point from the initialization will be chosen for further exploration.
Due to the close difference between the Bee Algorithm and Fly Algorithm there is no superiority between the two algorithms. It is noted that an evaluation of the De Jong function and the Rosenbrook function for a number of insect behavior algorithms are as tabulated in the table below:- Table 1
With reference to table 2 shown below, from the simulated times taken by an ASV unit 800 using a normal random and the Levy probability distribution function to evaluate the optimum point on the benchmark function , it is observed that the time taken to carry out the evaluation is shorter for the Levy probability distribution function.
Table 2
With reference to table 3 and figure 8, the plurality of rechargeable lithium ion battery modules that reside in the power block 600 housed within the body of an individual autonomous surface vehicle unit (ASV) 800 of the present invention, is a source of electromagnetic interference (EMI) and will hence interfere with the readings of the on board NMEA compass 402. As result the NMEA compass 402 was mounted on top of the ASV unit 800 by a predetermined height as determined by experimentation. The result of the experimentation yielded the results tabulated in table 3. From the tabulated results of table 3 it is observed that position C, yielded the best compass 402 readings.
Table 3
Next Patent: MICRO-HOTPLATE BASED GAS SENSOR