Doppler shift navigation system and method of using same

Abstract

A device, system and method of use for the relative navigation in a fluid medium, the device having a receiver and a controller, the receiver capable of receiving signals through the fluid medium. The signals, produced by a source, are capable of undergoing Doppler shift, and the controller is capable of determining the Doppler shift of the signals and determining the bearing between the device and the source of the signals. The system further having a first vehicle capable of producing the signals and a second vehicle having the device and wherein the device determines the bearing of the second vehicle in relation to the first vehicle.

Claims

1. A non-transient computer readable medium containing program instructions for causing a computer to perform the method of: (a) receiving from a receiver first signals having a first frequency and a second frequency emitted from a source; (b) determining a first frequency shift by comparing said first frequency with a reference frequency; (c) calculating a bearing of said receiver relative to said first frequency's source using said first frequency shift; determining a first and second received signal levels of said first and second frequencies, respectively; estimating a first and second absorptions of said first and said second frequencies; and estimating a range between said receiver and said source using said first and second received signal levels and said first and second absorptions.

2. The non-transient computer readable medium of claim 1 further including the steps of: (d) receiving additional first signals having a first frequency emitted from said source; (e) determining a second frequency shift by comparing said first frequency of said additional first signals with said reference frequency; and (f) determining a maximum frequency shift between said first frequency shift and said second frequency shift; wherein step (c) of calculating said bearing uses said maximum frequency shift in place of said first frequency shift.

3. The non-transient computer readable medium of claim 2 further including the step of: (g) instructing a change in heading of said receiver; and wherein step (g) is performed before step (d).

4. The non-transient computer readable medium of claim 1 wherein said first and second received signal levels are calculated using source a first and second signal level of said emitter, transmission loss and an estimation of noise.

5. The non-transient computer readable medium of claim 1 wherein said range is further estimated using estimates of source signal levels, and noise levels.

6. The non-transient computer readable medium of claim 4 wherein said range is further estimated using a function of errors in noise estimates, and of errors in source level estimates.

7. The non-transient computer readable medium of claim 5 further including the steps of: (k) receiving baseline signals having a first and second frequency from said receiver, wherein said baseline signals are captured during periods said source is not emitting said first signals; and (l) estimating said noise levels using said first and second frequencies of said baseline signals.

8. The non-transient computer readable medium of claim 1 further including the step of: (m) estimating a relative position of said receiver relative to said source using said range and said bearing.

9. The non-transient computer readable medium of claim 8 further including the step of: (n) reconstructing an absolute position of said receiver using said relative position and a known position of said first signals' source.

10. The non-transient computer readable medium of claim 1 further including the step of: (o) receiving, from a heading mechanism, a heading; wherein step (c) of calculating said bearing further comprises a single numerical integrating differential equation describing said first frequency and said heading.

11. A system for relative navigation in a medium, comprising: a first vehicle comprising a first source, said first source configured to produce first signals capable of traveling through the medium; and a second vehicle comprising an interconnected first receiver and first controller, said first receiver configured to detect said first signals in the medium; and wherein said first controller receives information from said first receiver and is configured to determine the Doppler shift of said first signals and wherein said first controller determines the bearing of said second vehicle relative said first vehicle using said Doppler shift; wherein said first signals comprise at least two frequencies and wherein said first controller determines the attenuation of said at least two frequencies to determine the range between said first and second vehicles.

12. The system of claim 11: wherein the first vehicle further comprises an interconnected second receiver and second controller, said second receiver configured to detect signals in the medium; and wherein the second vehicle further comprises a second source, said second source configured to produce a second signals capable of traveling through the medium; and wherein the first vehicles' first controller receives information from said first receiver and is configured to determine the Doppler shift of said second signals and wherein said first controller determines a bearing of said first vehicle relative to said second vehicle.

13. The system of claim 12 further comprising: a third vehicle, comprising an interconnected third receiver and third controller, said third receiver configured to detect said first and second signals in the medium; wherein said third controller receives information from said third receiver and is configured to determine the Doppler shift of said first and second signals; and wherein said third controller is configured to determine a bearing of said third vehicle relative to said second vehicle and a bearing of said third vehicle relative to said first vehicle.

14. The system of claim 11 further comprising a third vehicle comprising a second interconnected receiver and a second controller, said second receiver configured to detect said first signals in the medium; and wherein said second controller receives information from said second receiver and is configured to determine the Doppler shift of said first signals and said second controller determines a bearing of said third vehicle relative said first vehicle.

15. A device for determining the bearing of a signal in a medium, comprising: a receiver, configured to receive first signals having a first frequency in the medium; a controller connected to said receiver, configured to receive information on said first signals from said receiver and configured to determine a first frequency shift of said signals using said first frequency and a reference frequency, and to determine a bearing of said receiver relative to the source of said first signals; and a connector connected to said controller and configured to provide information output from said controller to another device; wherein said first signals comprise a second frequency and wherein said controller determines the attenuation of said first and second frequency to determine a range between said receiver and the source of the first signals.

16. The device of claim 15 wherein said controller is configured to estimate a relative position of said receiver relative the source of said first signals using said range and said bearing, and estimate an absolute position of said receiver using said relative position and a known position of the source of the first signals.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) In what follows, preferred embodiments of the invention are explained in more detail with reference to the drawings, in which:

(2) FIG. 1A is a top-view schematic illustration of the relative position of a leader and a follower vehicle having a navigation package, according to one embodiment of the present invention; leader, follower, and follower's navigation package are simplified and not drawn to scale.

(3) FIG. 1B is an illustration of the relative position between one leader vehicle and three follower vehicles according to one embodiment of the present invention.

(4) FIG. 1C is an illustration of the relative position between two leader vehicles and two follower vehicles according to one embodiment of the present invention.

(5) FIG. 2A is an illustrative view of the velocities and velocity vectors of leader and follower according to one embodiment disclosed herein.

(6) FIGS. 2B and 2C are two illustrative views of the angles associated with Doppler shift between leader and follower according to the embodiment. FIG. 2B shows an angle θ.sub.rel describing the angle between follower and leader and angle θ.sub.r describing an arbitrary relative north and the heading of follower v.sub.ri.

(7) FIGS. 3A and 3B illustrate the sensitivity of estimated angle to precision of frequency measurement versus relative angle for a 100 kHz signal, with a 1.4 m/s follower and a 1.2 m/s leader. Full range of angles are shown in FIG. 3A and zoom between −30 and 30 degrees angle are shown in FIG. 3B.

(8) FIG. 4 illustrates the difference in receive level between two frequencies f.sub.1 and f.sub.2 assuming identical transmission loss over a distance of 100 m.

(9) FIG. 5 illustrates range estimation error for three different frequencies pairs (f.sub.1/f.sub.2), 100 kHz/20 kHz, 60 kHz/20 kHz, and 60 kHz/45 kHz at true ranges of 0 to 500 m for salinity errors. The quantity of range error is small between the different frequency pairs, with a slight increase in range error for the frequencies that are closer together.

(10) FIGS. 6A-6F are illustrative examples of randomly seeded paths with leader marked in dark black and followers marked in lighter, dotted lines, with ε.sub.bhv and σ.sub.bhv results shown in FIGS. 6G and 6H, respectively.

(11) FIGS. 7A and 7B illustrate simulation results for lawnmower virtual experiments with 0 error in frequency. The illustrated amplitude estimation are shown in FIGS. 7C and 7D, with σ.sub.bhv and ε.sub.bhv denoted as dotted lines indicating r.sub.desired=500 m and solid lines indicating r.sub.desired=1000 m. As in the random seeding experiments, the larger offset distance results in greater error at turns but lower variance.

(12) FIGS. 8A-8D represent average reconstruction error and variance of reconstruction error versus σ.sub.bhv and ε.sub.bhv. Units for ε.sub.rec, σ.sub.rec are in meters, σ.sub.f in Hz, and σ.sub.n in dB.

DEFINITIONS

(13) For the purpose of this disclosure, an “absolute navigation mechanism” 114 provides an absolute location, often latitude and longitude coordinates of the current location to an attached vehicle, controller or other object. A GPS system uses satellites to determine a spot with respect to the earth's reference, producing an absolute location and is therefore an example of an absolute navigation mechanism 114.

(14) For the purpose of this disclosure, the term “follow position” abbreviated FP, is used to denote the relative spatial relationship between a leader L and a follower F, meaning the three dimensional position, including distance, orientation (i.e. heading) and the like.

(15) The term “follow” is to be understood as inclusive, the term including maintaining a fixed distance between two vehicles, the approach of one vehicle to an object (stationary or moving slower than the approaching vehicle), relative navigation of a follower F in relation to a leader L without the approach of the follower towards the leader, and even including a follower vehicle moving away from the leader and increasing the distance between the two vehicles.

(16) The term “follower” is used herein generically to refer to a movable object that is capable of detecting signals traveling through the fluid medium and determining the signals' Doppler shift. The follower is not required to move towards the source of the detected signals, but in almost all embodiments the follower is capable of such approaches.

(17) The term “leader” is used herein generically to refer to an object capable of creating signals that travel through the medium. In some embodiments the leader is mobile, however in other embodiments the leader is stationary, or unable to move by itself. The leader is not required to lead other vehicles or objects through the medium, but in many embodiments the leader is capable of such action.

(18) The term “hybrid” is used herein to refer to an object that may act as either a leader L or follower F. A hybrid H vehicle may alternate between acting as a leader L and follower F or may act as both leader L and follower F simultaneously.

(19) For the purpose of this disclosure, the term “vehicle” is any controllable object that can physically move through the desired medium, including floating on top of the medium, or navigating through the medium (i.e. submerged). The vehicle can be any appropriate object, as commonly known in the art, including but not limited to a ship, boat, barge, or other human-occupied vehicle, AUV, ROV, UUV, submarine, or other submerged craft.

(20) The term “reference frequency” as used herein refers to a known or determined source frequency that has not been affected by the Doppler effect. The reference frequency may be a predetermined source frequency, either set manually or algorithmically. The reference frequency may be algorithmically identified or estimated through a method disclosed herein or known in the art. The reference frequency may be a steady tone or a pattern of tones of a passive source or predetermined and known to change in frequencies, and the like.

DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED EMBODIMENTS

(21) Overview

(22) This invention may be accomplished by a system capable of exploiting the physical property of Doppler shift of energy waves (e.g. sound), and in some embodiments, the frequency-dependent absorption of energy (e.g. sound) in a medium, most often a fluid medium (e.g. water). One such system includes a first vehicle, a leader L, having a source 112, most often a transducer or pinger that is configured to produce a plurality of first signals S that travel through the medium (a body of fluid, most often the ocean), and a second vehicle, a follower F, having a receiver 152 and controller 154. The receiver 152 serves to detect at least some of the signals S transmitted through the medium, and the controller 154 is connected to and receives information from the receiver 152. The controller 154 then determines Doppler shift, attenuation, or both Doppler-shift and attenuation of the detected signals S, to determine at least one of the heading and range of first vehicle L relative to second vehicles F.

(23) The Doppler Effect (referred herein as Doppler shift) describes the perceived frequency shift that occurs when a sound source and a receiver experience relative motion. The present invention provides vehicles that receive or detect signals S through the medium at the received frequency f.sub.r of sound arriving from a source 112 with a source frequency of f.sub.s, from a leader L. f.sub.r varies based on the relative velocities of the leader L, denoted as v.sub.s and the follower's velocity, denoted v.sub.r, as well as the normal vector connecting the leader and follower, denoted {circumflex over (n)}.sub.rel. The present invention takes advantage of these phenomena to provide an inexpensive, relative navigation system for the submerged environment (i.e. fluid medium). A full description of the mathematical relationship between leader L and follower F is described below in the Doppler Shift Derivation section.

(24) System 100, as illustrated in FIG. 1A, has at least one source or leading vehicle, referred herein as a leader L, and at least one receiving or following vehicle, referred herein as a follower F. A desired and adaptable relative spatial relationship is configured for the follower F to maintain between it and the leader L, referred herein as a follow position FP and a representable line between vehicles as distance d. One or both leader L and follower F may be moving objects, each with a defined velocity and velocity vector (velocity including direction). Electromagnetic energy is used to determine Doppler shift and therefore relative bearing between follower F and leader L. The electromagnetic energy, referred herein as signals S, is emitted by leader L and detected by follower F. Signals S are often emitted as a defined frequency, a set of frequencies, or sets of frequencies. Signals S are typically sound waves or, in some cases, light waves, and the follower F may maintain or adjust the follow position FP by monitoring the Doppler shift of the leader's signals S.

(25) Doppler shift informed navigation has several advantages over current navigation systems, including but not limited to, Doppler shift of signals is not affected by salinity or by reflection or refraction off of a boundary layer in the medium, the medium surface or the medium bottom (e.g. the ocean bottom, or the bottom of a tank). The processing, or derivation, of the signals S by the follower F to establish the proper velocity and heading to maintain the follow position FP as at least one of the follower F and the leader L moves through the medium is describe in detail in the Derivation section below. In addition, follower F and leader L may switch between roles, or may act as both leader and follower simultaneously; such vehicles are referred herein as hybrid H vehicles.

(26) Leader L

(27) In the present invention, the leader L may be any suitable object that is capable producing signals S for a follower F to receive, through a liquid medium. Typically, the leader has a source 112 for producing signals S. In many embodiments the leader L is capable of movement or being moved through a medium. In some embodiments, leader L function as both a leader L and a follower F, either simultaneously or in turns; this ability allows another vehicle (typically a follower F) to become the leader L when the original leader L switches to follower F status. Simultaneous leading and following enables swarms within swarms, or subgroups of vehicles to follow a leader L who in turn follows another leader, which may have more than one following subgroup following a ‘master’ leader.

(28) Typically, leader L will have an absolute navigation mechanism 114 (e.g. GPS) to determine where it is in absolute units. The leader L must have a mechanism to send signals S out into the medium and those signals must be capable of undergoing Doppler shift. The origin of signals S that undergo perceived Doppler shift is referred herein as the source 112, which enables the followers F to determine bearing of leader L relative to itself and to execute their defined navigation pattern in response to this determination. The source 112 will be discussed in more detail below herein.

(29) The leader L may be any suitable object; several non-limiting examples include an AUV, an autonomous surface vehicle (ASV), a manned surface vehicle (e.g. a boat), an autonomous underwater glider (AUG), a buoy, a mooring, a towed streamer, and a submarine.

(30) In the currently preferred embodiment, leader L comprises an AUV, comprising a watertight housing 116, an absolute navigation mechanism 114 (typically a GPS receiver), a source 112, a controller 118 (e.g. a computer board), and a propulsion mechanism 120 (e.g. a motor). The absolute navigation mechanism may be any suitable device as known in the art, including GPS receivers, acoustic positioning systems (e.g. a long baseline LBL system), INS-DVL systems (inertial navigation system with Doppler velocity log) or the like.

(31) Source 112

(32) Each vehicle capable of performing as a leader L comprises a source mechanism 112 configured to produce signals S that propagate through the medium and are perceived to undergo Doppler shift when detected. Typically, source 112 is an acoustic source designed for submerged operation, producing sound waves that propagate though water, undergoing Doppler shift if the relative vectors of leader L and follower F are not identical. In the currently preferred embodiment, source 112 comprises a narrow band acoustic pinger, using constant waveform output, connected to the leader's controller 118, and configured to send out periodic signals (i.e. pings) at a rate, preferably a defined rate, and at a relatively constant tone over time. In one embodiment, the source is configured to produce signals S with defined frequency or frequencies. Typically, the source 112 is capable of emitting signals S in at least one frequency best suited for the embodiment. In one embodiment, a commercially available fish pinger, with an acoustic range of 100 to 500 meters underwater (this range is only true for one emitted frequency; at other frequencies, the underwater range will either extend or decrease, depending on the frequency or frequencies used to generate the signals). In another embodiment source 112 operates at around the 15 kHz frequency range, with a range of approximately 1 to 3 kilometers. In yet another embodiment, source 112 operates at around the 25 kHz frequency range, with a shift for vehicle movement.

(33) The exact frequency or frequencies chosen for source depends on many factors, including swarm size throughout a 3D space, vehicle speed, and the surrounding environment (e.g. saltwater vs fresh water). Source 112 power also depends on the specific embodiment, the level of decibel (dB) output is often selectable (either by a user or an autonomous algorithm), and may increase range of signal S, while increasing power consumption. The rate at which source 112 generates signals is embodiment dependent; signal generation rate may be anywhere within one signal per fraction of a second to a fraction of a minute, or once over a period of multiple minutes. Typically, the at least one signal S frequency is relatively fixed during a deployment or other specific period for an embodiment. The frequency or frequencies of signal S are preferably relatively fixed over the time scale of an adaptation. Here an adaptation is defined as the time it takes for a follower F to home in on the maximum Doppler shift, typically a time of several minutes. The at least one frequency produced by source 112 may be changed on a pre-determined basis, such that the follower is informed to which frequency a particular leader L is using. In embodiments with multiple leaders, each source will use a different frequency or set of frequencies.

(34) It is within the scope of this invention for the source 112 to be a passively generated source. That is, an object that produces energy while performing another task (e.g. the noise of an engine-driven propeller) is a passive source 112. In this way, a ship may be a leader L and the propeller may represent the source producing signals S, or a tone, for a follower F to determine the Doppler-shift and to use to establish a follow position FP. A vehicle may further be a hybrid H, or leader L, and its source 112 may be passive if a component of that vehicle, for example the propeller is configured to emit suitable signals S.

(35) Second Source 113

(36) It is within the scope of the invention for a vehicle to have a second source, most often emitting a different wavelength or wavelengths on the electromangic energy spectrum, referred generically herein as wavelengths to distinguish these signals from signals S. In one embodiment, the second source 113 emits wavelengths of visible light into the medium. Visible light is rapidly absorbed in fluid mediums, however, this absorption (i.e. attenuation) can be used to calculate shorter ranges, when two vehicles are in close approach. Most often the second source 113 is accompanied by an appropriate second receiver 153 adapted to detect the wavelengths emitted by the second source 113. The second receiver 153 is typically connected to its vehicle's controller 154. Like source 112 and receiver 152, second source 113 and second receiver 153 may be in a follower F, leader L, or hybrid H vehicle.

(37) Movement

(38) One of the leader F or follow F must undergo relative movement for the generation of perceived Doppler shift of signals S. The motive force may be provided by any suitable means as known in the art. In one embodiment, at least one of the leader L and the follower F is moved by a motor, in another embodiment at least one of the leader L and the follower F is towed behind a separate vehicle and that separate vehicle is moving. In yet another embodiment, at least one of the leader L and the follower F is free-floating and is moved through the medium by currents, a sail, or a buoyancy engine.

(39) Follower F

(40) The present invention provides for at least one follower F, which may follow at a prescribed distance, with a prescribed vector in three-dimensional space, in relation to the leader L. For simplicity this space, or position, is referred herein as the follow position FP (illustrated as a solid grey circle in FIGS. 1A and 1B), and includes the distance d in 3D space between follower F and leader L, and the vector {right arrow over (v)}.sub.r (i.e. heading) of the follower (i.e. angle of movement the follower F is set on). In embodiments with more than one leader L, a follower F will have a follow position FP that is relative to both leaders L1 and L2. Establishing follow position FP velocity, broadly stated to correct for range, and heading, broadly stated to correct for angle, are described in detail in the Derivation section. Follow position FP may be static in relation to the leader L over time (i.e. following a moving leader) or may change over time. Follow positions FP that change as a unit of time are useful for the follower F to do many different tasks, for example surveying a region of space relative to the leader (i.e. doing a ‘mow-the-lawn’ operation, FP will change as the follower F mows), or may be cha to conduct a mission step, for example approach a stationary leader L.

(41) Followers F comprise a self-propelled vehicle, typically an AUV, with at least one receiver 152 (e.g. a hydrophone), a controller 154, and propulsion mechanism 155. The follower F inherently have a heading (i.e. velocity vector) {right arrow over (v)}.sub.r resulting from its movement. Typically, followers F may rely on a single receiver 152 to determine Doppler shift of the received signal S, and therefore the system described herein is advantageous over other systems known in the art that require a multiplicity (e.g. more than one) of receivers to determine the direction in 3D space of a source. Furthermore, the currently preferred embodiment relies only on one-way signal S travel, from leader L to follower F. No signal is required to be produced or reflected from the follower F and sent to the leader L, enabling a vehicle swarm to be larger in number because only one signal is needed per leader L. Systems with two-way signals have limited bandwidth of frequencies available to each follower, and the leader would need to have a receiving mechanism capable discerning each follower's signals.

(42) Velocity Mechanism

(43) Some embodiments of the present invention include at least one means to determine vehicle velocity or, in some instances speed, referred herein as the velocity mechanism. The velocity mechanism determines information pertaining to the movement or speed of the vehicle, referred herein as velocity information, and typically relays that information to a controller. The controller may be controller 154 or a separate vehicle controller, interconnected to controller 154. In some cases, the velocity mechanism is a GPS device, a mechanism tracking propulsion mechanism action, or other means as known in the art. In some embodiments the velocity information is estimated or modeled though computer programming, including a search of possible vehicle or navigation package (i.e. ‘device’) speeds, or using a model of vehicle or navigation package speeds. In some, less preferred cases, the velocity mechanism is an acoustic Doppler current profiler ADCP which determines a vehicles' velocity and position relative to the ocean floor or fluid boundary layer.

(44) Heading Mechanism

(45) In some embodiments, a vehicle or navigation package 150 comprises a means of determining a heading, referred herein as the heading mechanism. The heading mechanism may be any solution as known in the art, for example, in one embodiment the heading mechanism comprises an electronic compass connected to a controller.

(46) Navigation Package 150

(47) In one embodiment of the present invention, a follower is modified to include a navigation package 150, comprising a receiver 152, for example a RESON hydrophone commercially available from Teledyne Marine. The hydrophone is then connected to a controller; most often a dedicated controller 154 located within navigation package 150, but in some, less preferred embodiments, to the follower's main controller. In either case, the controller is programmed, in part, according to the Derivation section disclosed below herein, and is in communication with the follower's F movement control software and hardware, as known in the art.

(48) The navigation package 150 may be incorporated into the follow's flooded or pressurized compartments, as known in the art. In another embodiment, illustrated in FIG. 1A, the navigation package 150 comprises a housing 156 containing a controller 154 and supporting a receiver 152, which may have portions within and without housing 156. In this embodiment, navigation package 150 further comprises a connection 158 enabling the navigation package to connect, at least informationally, to follower F, or another object; As an example, connection 158 may be a standard RS-322 connection. Connection 158 is adapted to transfer any information and commands, referred generically as information output, available to controller 154 to the attached object. Connection 158 may also accept commands and information from the attached object, and its controller, and transfer those commands and information to controller 154. Additionally, connection 158 may be configured to provide power to the navigation package 150 if the navigation package does not include an independent power source 160. The navigation package 150 may then inform the attached vehicle or another device, of the received signals S as they propagate from one or more leaders L through the medium. Such a package would be widely adaptable for many different types of vehicles and could be made to be plug-and-play with standardized connections and output data.

(49) In yet other embodiments, navigation package 150 may comprise an interconnected source 112, enabling the connected vehicle to alternate between leader L and follower F functions, referred herein as a hybrid H vehicle, and discussed in more detail below.

(50) Controller

(51) The present invention provides for a digital control device, referred herein as the controller 154. In some embodiments, the controller is within a vehicle (and may be included in followers, leaders and hybrid vehicles), or within a navigation package device 150. The controller is configured to perform many of the determinations, estimations and calculations disclosed elsewhere herein. The controller may be any control device as known in the art. Often the controller is a single board computer. Controllers are referred generically herein, and their function may pertain to a controller in any vehicle or package.

(52) In some embodiments the controller 154 has information and programing stored on computer readable medium (abbreviated CRM). The CRM is most often non-transitory, that is the information is not encoded on transitory signals. The CRM may be encoded onto a physical piece of memory, for example a CD-rom, a flash drive, a single board computer, and the like, as long as it is substantially permanent that the information encoded therein (i.e. programmed steps or firmware) may be carried out on an applicable navigation package device 150, or system 100. The mathematical equations and steps disclosed herein to determine relative bearing between a receiver 152 and source 112, determine range between receiver 152 and source 112, and other calculations disclosed herein may be executed by a computer that accesses or retrieves code stored in a non-transient computer readable medium of a computer program product.

(53) Some of the commands stored on the CRM indirectly instruct a change in heading or orientation of a competent, for example receiver 152 or source 112. In most embodiments, the command is enacted through the vehicle by changing control surface altitude or orientation (e.g. a vehicle's control fins), or propulsion mechanism 120, which in turn induces the desired change in the component. It is to be understood that a command instructing a change in heading or position of a navigation package 150 or receiver 152, will act on other components as would be readily understood by one skilled in the art.

(54) Swarm Compositions

(55) The present invention may be performed as a simple single leader L, single follower F relative navigation system, where an informed leader L (here informed refers to the leader knowing its absolute location or is in the correct location) is located in a fluid medium and enables a follower F to establish at least one desired follow position FP relative to said leader L. In a variation of this simple implementation, the leader L may be fixed in position and the follower F may have a route or set of follow positions set relative to the leader L that it executes. Routing of the follower F may be performed by determining the leader's location over time, with the follower F moving to obtain different degrees of Doppler shift for each follow position FP, in turn.

(56) This invention, however, is especially well suited for more complex vehicle arrangements, defined herein as swarms. Vehicle swarms may comprise a single leader L with a single source 112 enabling multiple (2 or more) vehicles to navigate relative the leader L, each vehicle (followers) following at a prescribed follow position FP. Illustrated in FIG. 1B is a simple swarm system 100 comprising a single leader L and three followers F1-F3, each follower with a set follow position FP1-FP3 set in relation to leader L and each having a distance d1-d3 in three dimensional space between itself and leader L. The present invention enables many followers to follow a single leader L, and it is to be understood that the illustrations provided herein depict limited numbers of followers and leaders for simplicity and that there is almost no theoretical limit to the number of vehicles in a swarm. Preferably more than two to several hundred followers could be incorporated into a swarm.

(57) Another simple swarm is illustrated in FIG. 1C, the swarm having two leaders L1 and L2 and two followers F1 and F2. In swarms with more than one leader L, each follower may have set headings and therefore a follow position relative to more than one leader L. For example, follower F2 has a follow position of FP2, with a distance d3 to leader L1 and a distance 1:14 to leader L2. Likewise, as disclosed in the derivation section below, follower F2 would have a heading and vector that maintains its relationship at FP2 to both leader L1 and leader L2, as the swarm performs relative movement through the medium. Not illustrated but enabled by the present invention are larger swarms with more than two leaders and more than two followers. Such swarms are possible as long as the leader's source 112 has the frequency and output power for a signal S to travel the distance to the farthest follower F that must maintain a follow position FP to that particular leader L. It is possible for some followers in a swarm to maintain a follow position FP to only a subset of leaders, enabling a swarm to spread out over an area (e.g. a long linear line) were portions of the swarm's followers are not receiving signals S from the leaders on other side of the swarm. It is also within the scope of the invention for a hybrid vehicle H to follow a leader or multiple leaders in a swarm, while simultaneously producing signals S for other followers to navigate relatively to at least the hybrid H in the same swarm. The followers that follow the at least one hybrid H can be thought of as a subswarm within the greater swarm.

(58) It should be noted the term “follow” as used herein includes the approach to a stationary object, for example a follower F approaching a stationary leader L. The term “follow” further includes relative navigation of a follower F in relation to a leader L, therefore when a follower is said to follow a leader that includes moving to a set of waypoints that does not necessarily lead to or follow along with a leader L.

(59) In many embodiments, a single vehicle may be a hybrid H vehicle, configured to act as either a leader L or follower F. And a plurality of vehicles in a single swarm may be configured have this switching ability. A hybrid H vehicle must comprise the components of both leader L and follower F, typically comprising a receiver 152 connected to a controller 154 as well as a source 112, either as individual components or as a single package 150.

(60) Hybrids H may start out during a swarm performing one role (e.g. a follower F), but on a cue convert to a leader L. The cue may be predetermined (e.g. timed) and other vehicles in the swarm pre-programmed to recognize the new leader. Alternatively, only the original leader L need to convert to a follower F and allow the remaining followers automatically move to follow positions FP relative to the new leader. In some embodiments, a hybrid H may convert a swarm with one leader L to a swarm with two leaders L, or swarm with a plurality of leaders L to a swarm with a plurality of leaders plus one additional leader.

(61) Hybrid switching between leader L and follower F and visa-versa may include, but is not limited to, time, depth, new absolute location acquisition, sensor data, battery state, and an external communication. One example of a swarm comprising two or more hybrids H is when a first vehicle comes to the ocean surface, obtains a GPS fix, gets over-the-air commands from a human-occupied vehicle (e.g. a mother-ship), and becomes the leader L. Once the first vehicle is a leader L, it begins to produce signals S from its source 112, and may begin movement, and either remain surfaced or dive. The remaining vehicles follow, then a second vehicle, typically pre-determined, may surface after a given period of time, or after a different cue is obtained, get a GPS fix, receive over-the-air communications from the human-occupied vehicle and become the leader L. The first vehicle may be pre-programmed to switch to follower F status after the pre-determined time (or other cue), or may monitor for signals S at a given frequency such that it is informed when the second vehicle transitions to leader L status. The first vehicle then becomes a follower F. Alternatively the swarm could be programed to transition to a two-leader swarm, typically with a pre-determined spacing between leaders.

(62) Doppler Shift Derivation

(63) As illustrated in FIGS. 2A-2C, follower's F heading is described by vector v.sub.r, and the leader L has a heading described by vector n.sub.s. For each follower F, Math 1 expresses the calculation of the received frequency f.sub.r based on source frequency f.sub.s (the reference frequency) from leader L, a velocity of the follower {right arrow over (v)}.sub.r and a velocity of the leader {right arrow over (v)}.sub.s, and a unit vector {circumflex over (n)}.sub.rel connecting leader L and follower F. The unit vector {circumflex over (n)}.sub.rel may be defined in terms of an angle between the receiver velocity vector v.sub.r and the normal vector connecting source 112 (and therefore leader L) and receiver 152 (and therefore follower F) as {right arrow over (v)}.sub.r.Math.{circumflex over (n)}.sub.rel=|{right arrow over (v)}.sub.r|cos(θ.sub.rel). A controller, either a controller commonly present in a follower F, or a dedicated controller 154, may then perform the following calculations disclosed herein.

(64) $\begin{array}{cc}{f}_r=\frac{f_s\left(c+{\stackrel{.fwdarw.}{v}}_r.Math.{\hat{n}}_{\mathrm{rel}}\right)}{c+{\stackrel{.fwdarw.}{v}}_s.Math.{\hat{n}}_{\mathrm{rel}}}=\frac{f_s\left(c+.Math.{\stackrel{.fwdarw.}{v}}_r.Math.\cos \left({\theta }_{\mathrm{rel}}\right)\right)}{c+{\stackrel{.fwdarw.}{v}}_s.Math.{\hat{n}}_{\mathrm{rel}})}& \mathrm{Math}1\end{array}$

(65) A follower senses a maximum in f.sub.r (and therefore a maximum frequency shift) when v.sub.r is in the same direction as {circumflex over (n)}.sub.rel or when cos(θ.sub.rel)=1, meaning that without knowing its own position, speed, leader L position, or leader velocity, each follower can control heading based on this received signal S frequency to choose the vector moving towards the leader with Math 2. While following or moving through the medium (i.e. fluid environment), the follower F continues to receive signals S through the medium, when additional signals S are received and those signals S may have a different frequency and therefore frequency shifts, these signals are referred herein as “additional signals” to distinguish their altered frequency properties.

(66) $\begin{array}{cc}{f}_r,\max =\frac{f_s\left(c+.Math.{\stackrel{.fwdarw.}{v}}_r.Math.\right)}{\left(c+{\stackrel{.fwdarw.}{v}}_s.Math.n_{\mathrm{rel}}\right)}.& \mathrm{Math}2\end{array}$

(67) Alternatively, for any value of v.sub.s, argmax f.sub.r occurs when the follower F is moving directly towards the source 112 (and therefore leader L), and can be expressed with Math 3. The maxima (of maximum frequency shift) for follower F may be found by changing heading in a mechanical gradient ascent algorithm, where the heading is changed and additional Doppler shift or frequency is measured and when higher values are found, the heading is moved more towards that direction, taking the ‘accent’.
|{right arrow over (v)}.sub.r|={right arrow over (v)}.sub.r.Math.{circumflex over (n)}.sub.rel  Math 3

(68) By adapting vehicle heading based on f.sub.r, the follower finds the heading that corresponds to the direction towards the leader (f.sub.r=r.sub.r,max or θ.sub.rel=0), without explicitly requiring {right arrow over (v)}.sub.s.

(69) If the source velocity {right arrow over (v)}.sub.s is known, bearing θ.sub.rel from each follower F to the leader L may be reconstructed directly from this known Doppler shift. This would occur when the source is fixed, for example, in the deployment/recovery mission parts, when data is being analyzed in post-processing, or if source position and velocity are communicated in real time. Alternately, a vehicle may experimentally determine f.sub.r,max if the velocity of the leader L could be assumed constant.

(70) The sensitivity of this angle estimate to precision in the frequency estimate for a 100 kHz signal S is shown in FIGS. 3A and 3B, showing difference versus θ.sub.rel for magnitude assuming a source velocity vector of v.sub.s=<1.2,0> and a receiver velocity vector of v.sub.r=<1:4 cos θ.sub.rel, 1:4 sin θ.sub.rel> where the first part of the vector is along the line between receiver 152 and source 112 in the direction indicated by {circumflex over (n)}.sub.rel in FIGS. 2A-2C, and the second part is perpendicular to {circumflex over (n)}.sub.rel, as shown in Math 4. FIG. 3A shows the full range of angles and FIG. 3B is the section of FIG. 3A between angles −30 to 30 degrees angle.

(71) $\begin{array}{cc}\Delta {\theta }_{\mathrm{rel}}={\theta }_{\mathrm{rel}}-\frac{c\left(f_r+\Delta f_r-f_s\right)}{f_s.Math.\stackrel{.fwdarw.}{u}.Math.}.& \mathrm{Math}4\end{array}$

(72) Lower accuracy has a particular impact on small angles θ.sub.rel, as the total Doppler shift is smaller in that region per degree of differential angle. Precise frequency estimation is therefore critical to the accuracy of bearing reconstruction: while 1 Hz frequency estimation accuracy would make it possible for a follower F to remain with the leader L due to the feedback nature of the autonomy, 0.05 Hz accuracy makes 5 degree estimation theoretically possible at 100 kHz, equivalent to the accuracy attained by other, known in the art systems (e.g. the OWTT iUSBL system).

(73) Even as {circumflex over (n)}.sub.rel changes due to changes in v.sub.r and v.sub.s,f.sub.r,max corresponds to the follower F moving directly towards the leader L. If follower F heading is described by direction in v.sub.r, the heading that corresponds to {circumflex over (n)}.sub.rel can be found based on the minimum of the derivative of the received frequency with respect to heading, as illustrated in Math 1 and Math 2.

(74) Defining the angles that describe the above equations are illustrated in FIGS. 2A-2C, θ.sub.r is the angle of heading of the follower F in East-North-up coordinates and, θ.sub.rel is bearing to the leader L. Differentiating the received frequency at the follower F relative to the heading of the follower F is shown in Math 5, Math 6, and Math 7. Of note, the method disclosed herein contains only one integration to solve a differential equation, meaning the method inherently has less error introduced by the operations than methods requiring more than one integration.

(75) $\begin{array}{cc}\frac{d{f}_r}{d{\theta }_h}=\frac{f_s}{c-.Math.{\stackrel{.fwdarw.}{v}}_s.Math.n_s.Math.n_{rel}}\frac{d}{d{\theta }_h}\left[c+.Math.{\stackrel{.fwdarw.}{v}}_r{n}_r.Math.n_{\mathrm{rec}}.Math.\right]& \mathrm{Math}5\\ n_s.Math.n_{\mathrm{rel}}=\cos \left({\theta }_r\right)& \mathrm{Math}6\\ \frac{d{f}_r}{d{\theta }_h}=\frac{f_s}{c-.Math.{\stackrel{.fwdarw.}{v}}_s.Math.n_s.Math.n_{\mathrm{rel}}}\frac{d}{d{\theta }_h}[c+.Math.{\stackrel{.fwdarw.}{v}}_t.Math.\cos \left({\theta }_r\right).& \mathrm{Math}7\end{array}$

(76) The angle θ.sub.r can be defined in terms of θ.sub.h (the heading of the follower in East-North-up coordinate frame) and some angle γ, and the angle of the line (labeled d in FIG. 1A) connecting leader and follower (θ.sub.r=γ−θ.sub.h). When a follower F is pointed directly at leader L (γ=θ.sub.h), the maximum Doppler shift will occur. This substantiates the intuition that the Doppler shift will have a maximum when the follower's velocity vector is moving it on a direct interception course to the leader L, regardless of the velocity vector for the follower F. Therefore, by modifying the heading of the follower θ.sub.h we can mechanically find the maximum frequency as the heading that gives the follower the maximum rate of approach to the leader, regardless of the leader speed and characteristics.

(77) Estimating Range

(78) It is within the scope of the present invention for some embodiments to also estimate range between leader L and follower F. Range estimation is approximated by exploiting absorption differences of the medium (e.g. water) at different frequencies, especially when the velocity vector of the source 112 is unknown. Assuming deep water and a mid-water-column sound source, the basic sonar equation can be used to describe the received level of signal RL based on the source level SL and the transmission loss TL and the noise N, as expressed in Math 6. It is within the scope of the present invention for the received level of signals to be sound, or a different section of the electromagnetic spectrum, however, the RL is still referred herein as received level of sound or sound level. The transmission loss TL has two contributing factors, (i) geometric spreading TL.sub.geom and (ii) absorption α by water, where absorption is a strongly frequency-dependent term in units of dB/km, as shown in Math 9.
RL=SL−TL+N  Math 8
TL=TL.sub.geom+αr  Math 9

(79) Geometric spreading TL.sub.geom is not frequency-dependent, but absorption α is highly frequency dependent. High frequencies are absorbed at much greater rates than low frequencies. Three regimes that contribute to absorption of sound in seawater are (i) viscous absorption generated by particle motion (dominant in frequencies above 100 kHz), (ii) absorption due to boric acid (dominant in frequencies below 10 kHz), and (iii) magnesium sulfate (dominant in frequencies 10-100 kHz). The general equation for absorption is complex and based on commonly known empirical studies. Equations, tables, and figures for finding α can be found in most ocean acoustic or physical oceanography textbooks. An approximation for the absorption versus frequency can be estimated by combining terms due to the viscous, relaxation of boric acid, and relaxation of magnesium sulfate in dB/km.

(80) Using geometric transmission loss plus absorption to estimate range based on a single frequency is ineffective due to the environmental variability and background noise. Background noise may be captured during times that source 112 is not emitting signals S and referred herein as baseline signals. Signals S are often time-defined pulses or pings, and the times lacking a signal ping may be thought of as baseline signals or periods of time. However, the frequency-dependence of this phenomena, especially across decades in frequency, is very large. Over short ranges (<1 km) in deep water, paths for separated frequencies can be assumed to be close together, leading geometric transmission loss TL.sub.geom that may be treated as frequency-independent. This means that the difference between the amplitude of two frequencies is due to difference in absorption, and this difference may be used as feedback to control the follower F range to the leader L, as expressed in Math 10 and Math 11.

(81) High frequencies attenuate much more rapidly than low frequencies and this effect can be exploited to estimate approximate range. For example, a 1 kHz signal travelling 100 m will have a TL value of 40 dB, whereas a 100 kHz signal travelling the same distance will have a TL value of 43 dB. This 3 dB difference describes a factor of two in amplitude. Increasing the spread in frequencies increases the effect further, and more than two frequencies may be used to improve the solution on range versus attenuation. This frequency-dependent difference in absorption can be used to directly estimate range.

(82) It is within the scope of the present invention to provide more than one set of frequencies for the use of attenuation range-finding. In one embodiment one set of frequencies is used to determine long-distance range, for example sound waves, and a second set of frequencies is used to determine short-distance range, for example light waves. Because light attenuates significantly faster than sound waves, precise ranging for in-close operations is possible by providing this second set of frequencies, typically from a second source mechanism. The first set is preferably included, due to the second set's (e.g. light waves) inability to travel long distances in a medium (e.g. water).

(83) In practice, there is uncertainty in this estimate caused by variations with properties such as sound speed profile. 3D acoustic effects, interaction with the surface, and interaction with the bottom can also cause variation in the signal. Variable, frequency-dependent noise in the medium is also an issue. RL is the actual measurement, so the estimate obtained will look as shown in Math 10 and Math 11.
ΔRL=(SL.sub.f1−TL.sub.f1+N.sub.f1)−(SL.sub.f2−TL.sub.f2+N.sub.f2)  Math 10
ΔRL=SL.sub.f1−SL.sub.f2+(α(f.sub.2)−α(f.sub.1))R+N.sub.f1−N.sub.f2.  Math 11

(84) This difference in measured receive level may directly estimate range {tilde over (r)} given estimates of source levels , noise levels Ñ and vales for a at each frequency, as illustrated in Math 12.

(85) $\begin{array}{cc}\tilde{r}=\frac{\Delta \mathrm{RL}-{f1}_{}+{f2}_{}+{\tilde{N}}_{f1}-{\tilde{N}}_{f2}}{\tilde{\alpha }\left(f_1\right)-\tilde{\alpha }\left(f_2\right)}.& \mathrm{Math}12\end{array}$

(86) Where is the estimate of the difference in received level in dB between frequencies f.sub.1 and f.sub.2 from series measurements, .sub.f1 is the estimated source level at frequency f.sub.1, .sub.f2 is the estimated source level at frequency f.sub.2, and Ñ.sub.f1 and Ñ.sub.f2 are estimates of noise properties at the frequencies of interest based on sensing when there is no sound signal. The estimate of r can then be calculated as a function of errors in noise estimates ϵ.sub.N=N−Ñ, source level estimates ϵ.sub.SL=SL−, and estimates of a as shown in Math 13.

(87) $\begin{array}{cc}\tilde{r}=\frac{\begin{array}{c}{ϵ}_{SL}\left(f_1\right)-{ϵ}_{SL}\left(f_2\right)+\\ {ϵ}_N\left(f_1\right)-{ϵ}_N\left(f_2\right)+(\alpha \left(f_2\right)-\alpha \left(f_1\right)\end{array}}{\tilde{\alpha }\left(f_1\right)-\tilde{\alpha }\left(f_2\right)}.& \mathrm{Math}13\end{array}$

(88) Two important factors to the practicality of using the measurement of ΔRL to find {tilde over (r)}: the level differences in ΔRL need to be measurable and the sensitivity of {tilde over (r)} to different factors must be understood. For the first factor, pairs of frequencies were compared to estimate ΔRL at 100 m of range, as shown in FIG. 4. ΔRL at 100 m is grayscale-coded in decibels in FIG. 4 assuming identical transmission losses of a first frequency f.sub.1 and a second frequency f.sub.2.

(89) Noise values of first and second frequencies Ñ.sub.f2 and Ñ.sub.f1 may be estimated in real-time when the source 112 is not transmitting (i.e. baseline signals), and source levels may be established a priori, which means that the main source of error is in mismatch between true frequency-dependent absorption α(f) and estimate of absorption {tilde over (α)}(f). All errors in estimates for everything except α are collected in a single term, η, so that the sensitivity of r−{tilde over (r)} to α alone may be analyzed, with Math 14.

(90) $\begin{array}{cc}r-\tilde{r}=r-\eta +\frac{\alpha \left(f_1\right)-\alpha \left(f_2\right)}{\tilde{\alpha }\left(f_1\right)-\tilde{\alpha }\left(f_2\right)}.& \mathrm{Math}14\end{array}$

(91) The precision of the range estimate is limited by these curves: using two closely spaced frequencies decreases signal to noise ratio on the measurement, therefore requiring longer ranges for an estimate of range. A ΔRL of 3 dB (see contour lines numbered 3 in FIG. 4) represent a factor of 2 in magnitude is assumed to be easily measured in field data.

(92) To evaluate the sensitivity to mis-estimation or variation of factors including pH, salinity, temperature, and depth, an analysis was performed on the impact on of error in a priori estimate of those parameters with frequency pair of 100 kHz and 20 kHz, to determine sensitivity. “True” salinity SA was varied between 25 and 40, with an “assumed” salinity of 35. “True” temperature was assumed to be between 0° C. and 40° C., with an “assumed” temperature estimated T of 20° C. “True” pH was varied between 7.1 and 9.1, with “assumed” pH of 8.1. Depth was assumed known.

(93) Salinity mismatch was found to dominate the error in, with a difference in α(f.sub.1)−α(f.sub.2) of up to 40 dB/km with a salinity difference of +5/−10 PSU. In comparison, the difference for 20 degrees of temperature error is only 4 dB/km, and a difference in pH of 1 resulted in an error of only 0.1 dB/km. Salinity was therefore taken as dominant, and used to estimate the range estimation error δr={tilde over (r)}−r for different salinity mismatch at three pairs of frequencies, with results shown in FIG. 5. The three frequency pairs are shown as frequency pair 1 (fp1) of f.sub.1 of 100 kHz and f.sub.2 of 20 kHz (solid black line), frequency pair 2 (fp2) of f.sub.1 of 60 kHz and f.sub.2 of 20 kHz (dashed grey line), and frequency pair 3 (fp3) of f.sub.1 of 60 kHz and f.sub.2 of 45 kHz (dotted black line). The quantity of range error is small between the different frequency pairs, with a slight increase in range error for the frequencies that are closer together. Each frequency pair is shown for true ranges of zero to 500 meters and for salinity errors of +0 (labeled as S=35 in FIG. 5) to −10 PSU (labeled as S=25). Range error increases with increased negative salinity error. Some increments of salinity error are not shown for simplicity.

(94) Extremes in salinity are unusual outside of near-shore areas near river outflows; ocean water is between 37 and 34 PSU. For ±2 PSU, the total error for the projected mission would be less than 5%, corresponding to a range error of 50 m/km. This error is proportional only to relative range r between leader L and follower F, it does not drift with total distance travelled.

(95) By using multiple frequencies widely separated and choosing a desired ΔRL as a control parameter for selecting vehicle speed in the autonomy code, an approximately constant follower F range to the leader L is maintained any errors in environmental estimates may result in a different range than the desired especially if desired range is less than 500 m, but by feeding back on the differential attenuation approximately constant range is maintained. The range estimate r may furthermore be used along with {tilde over (θ)}.sub.rel to reconstruct follower F position in post processing.

(96) Position Reconstruction

(97) Once estimated range (from absorption difference estimated ) and bearing {tilde over (θ)}.sub.rel (from frequency estimate f.sub.r) are known, relative x and y position can be estimated to the leader L using follower F heading θ.sub.h, as shown in Math 15.
dx=r sin {tilde over (θ)}.sub.rel+θ.sub.h, dy=r cos {tilde over (θ)}.sub.rel+θ.sub.h.  Math 15
x.sub.r=x.sub.s+dx, y.sub.r=y.sub.s+d.sub.y.  Math 16

(98) The absolute position of the follower, x.sub.r, y.sub.r can be reconstructed using known leader position, x.sub.s, y.sub.s approximated in Math 16.

(99) The accuracy of such reconstructions are dependent on the following factors: (i) accuracy and precision in estimates of f.sub.r that impact the estimate of θ.sub.rel and (ii) accuracy of estimate of {right arrow over (v)}.sub.r and including speed estimate and heading estimate.

(100) A possible complication to reconstruction based on the differential attenuation method is that when the sound source 112 or receivers 152 are near to the surface, multipath interference occurs, where destructive/constructive interference can result in variations as followers increase horizontal range to the leader (multipath fading). This interference is frequency dependent, and would be dealt with in the real world by keeping vehicles close to vertical in the water column where the effect is minimal, and by using more than 2 frequencies so that different combinations may be combined to cancel out the multi path fading and improve position reconstruction.

(101) Simulation Experiments

(102) Simulation experiments had the objective of testing multi-vehicle swarming behaviors for AUVs. In all simulations, the leader L was equipped with a non-time-synchronized source 112 (in this embodiment, a pinger) with a set frequency. The leader L is given a set speed of 1.2 m/s, and all followers are simulated to have a speed of 1.3 m/s. This allows followers to catch up to the leader L and the behavior adaptation parameter was set as described in the previous section. At each time step, a simulated Doppler shift estimator outputs for each follower the current received frequency f.sub.r based Doppler shift from Math 1. Based on the Doppler shift, the simulated vehicles adapt heading with a turn to port or starboard. Each follower F was given a different depth in 10 m increments, and the leader L is assumed to have a known, constant depth. The turn radius of all followers as set to 15 m, and the leader L was assumed to have a worst-case turn radius of 0 m (instantaneous turning).

(103) Two sets of virtual experiments were run to demonstrate the efficacy of the Doppler-based swarming system to keep vehicles together and reconstruct the absolute navigation of the followers in post-processing: a randomly seeded leader path and a conventional lawnmower leader path. For both cases, vertical formations of 50 virtual vehicles were tested. For each virtual experiment, three AUV autonomy schemes were used: Doppler-shift and differential-frequency-attenuation for relative position autonomy method were tested. The virtual experiments all assumed a leader L speed of 1.2 m/s, a follower F speed of between 1 and 1.5 m/s and a follower F turn radius of 15 m. The measured receive level and the estimated frequency were modeled as given in Math 17 and Math 18, respectively.
=ΔRL+N(0,σ.sub.n.sup.2)  Math 17
{tilde over (f)}.sub.1=f.sub.1+N(0,σ.sub.f.sup.2).  Math 18

(104) Vehicle behavior performance relative to the leader L were evaluated for both random seed and lawnmower virtual experiments. Position of followers relative to the leader L were used to compare desired and actual vehicle behavior based on the position of a follower i at a step k, as shown in Math 19.
δ.sub.r,bhv(k,i)=r.sub.desired−r.sub.k,i.  Math 19

(105) For each time step k, the standard deviation was evaluated between all follower positions to assess how tightly the vehicles remain grouped, as shown in Math 20. And mean and standard deviation of δ.sub.r,bhv(m, i) were also used to get general statistics for behavior performance, as shown in Math 21 and Math 22.

(106) $\begin{array}{cc}{\sigma }_{\mathrm{bhv}}\left(k\right)=st{d}_{\left(r_{k,i}-r_{\mathrm{desired}}\right)}& \mathrm{Math}20\\ {\sigma }_{\mathrm{bhv}}=\mathrm{std}\left(1/K\underset{k=0}{\overset{K-1}{.Math.}}\left(r_{k,i}-r_{\mathrm{desired}}\right)\right)& \mathrm{Math}21\\ {ϵ}_{\mathrm{bhv}}=1/N\underset{i=0}{\overset{N-1}{.Math.}}1/M\underset{k=0}{\overset{K-1}{.Math.}}.Math.{\delta }_{r,\mathrm{bh\nu }}.Math.& \mathrm{Math}22\end{array}$

(107) Where the above Nis the number of followers, K is the number of samples or steps along the vehicle trajectory, and the true location for the follower i consists of point (r.sub.k,i, θ.sub.rel).

(108) Reconstruction accuracy was also evaluated based on mean and standard deviation of the reconstruction error, as shown in Math 23 and Math 24.

(109) $\begin{array}{cc}{ϵ}_{\mathrm{rec}}=1/N\underset{i=0}{\overset{N-1}{.Math.}}1/K\underset{k=0}{\overset{K-1}{.Math.}}{\left({\left({\tilde{x}}_{k,i}-x_{k,i}\right)}^2+{\left({\tilde{y}}_{k,i}-y_{k,i}\right)}^2\right)}^{1/2}& \mathrm{Math}23\\ {\sigma }_{\mathrm{rec}}=\mathrm{std}(1/K\underset{k=0}{\overset{\kappa -1}{.Math.}}{\left({\left({\tilde{x}}_{k,i}-x_{k,i}\right)}^2+{\left({\tilde{y}}_{k,i}-y_{k,i}\right)}^2\right)}^{1/2}.& \mathrm{Math}24\end{array}$

(110) Two desired ranges r.sub.desired were tested: 1000 m and 500 m. Adaptation in range is achieved only through measurement of attenuation difference: when the value of Δ falls more than 1 dB below the desired value, the follower F may slow down to increase range. When the value of Δ is more than 1 dB above the desired value, the follower F may speed up to decrease the range.

(111) For each randomly seeded virtual experiment, a random set of 4 waypoints were selected for the leader L in an area 10 km by 10 km to assess the performance of the swarming technique to turning. The 50 followers were randomly initialized at a location a maximum of 100 m from the leader L initial location, oriented with a random heading emulating the “Wait” mode. One hundred and twenty leader paths were tested per virtual experiment. Pseudo-random seeding was used so that the same leader paths are directly compared between different adaptation parameters. FIGS. 6A-6F shows several examples of leader L and follower paths resulting from a random seeding. For simplicity only a subset of the 50 followers are shown. FIGS. 6A-6C illustrates the r.sub.desired of 1000 m and FIGS. 6D-6F the r.sub.desired of 500 m. The scatter plot in FIG. 6G shows leader-follower distance error ε.sub.hbv and the scatter plot in FIG. 6H shows leader-follower standard deviation σ.sub.bhv in meters for desired distances of 500 (x's) and 1000 m (circles).

(112) The 1000 m distance had a larger magnitude error versus the desired distance and a smaller variance than the 500 m standoff distance. This behavior results because in the r.sub.desired=1000 m case the followers hang back, adjusting their speed to remain further away, but with a slower response to changes in heading.

(113) A conventional lawnmower pattern cover a 10 km×10 km test area was used to assess the performance of the swarming technique to more standard AUV operations, as well as to determine the impact of error in δ and r on behavior and reconstruction errors. Two stand-off distances were used: 1000 m and 500 m. FIGS. 7A-7D shows example lawnmower patterns including a leader and followers with the two distances, along with the behavior error versus navigation step along the follower paths for σ.sub.f and σ.sub.n of 0.

(114) Introducing error was found to have limited impact on general follower F behavior, with the general follower F pattern remaining consistent, with the followers trailing the leader L with frequency errors of up to 1 Hz and ΔRL errors of up to 3 dB. Increasing σ.sub.f resulted in increased variance in the behavior error, as followers attempted to maintain θ.sub.rel=0 in the presence of frequency noise. Increasing σ.sub.n resulted in increased variance as well. Since the mean was taken to be 0 due to the assumption that environmental noise is characterized in real time, there was no significant effect on the average range between leader and followers or the general follower F behavior.

(115) The greatest impact of errors in frequency estimate and amplitude estimate are the accuracy of reconstruction: when either parameter in incorrect, error is introduced to the calculation of position. The mean and standard deviation of reconstruction error for a range of σ.sub.f and σ.sub.n values is shown in FIGS. 8A-8D as mean and variance of reconstructed error in meters. FIGS. 8A and 8B show a r.sub.desired of 1000 m and FIGS. 8C and 8D show a r.sub.desired of 500 m. FIGS. 8A and 8C show E mean of reconstruction error and FIGS. 8B and 8D show a standard deviation of reconstruction error. Errors in frequency and amplitude estimation have generally expected impact on reconstruction: increased error, particularly in estimation of amplitude, results in reconstruction errors of greater than 100 m. Since the error does not grow versus distance travelled, these simulation results can be used as a metric to determine the required accuracy in amplitude difference estimation for a given standoff range r.sub.desired: to achieve an average reconstruction error of less than 50 m with a 1 km r.sub.desired, for example, requires σ.sub.n<1 dB if the standard deviation of the frequency estimation error σ.sub.f=0.1 Hz, both achievable with the prototype system with characterization of source parameters and ambient noise.

Example 1

(116) The problems of low-cost AUV swarming will now be considered herein with a specific example. The problems having several criteria of (i) keeping a scalably large number of AUVs together in the ocean, with all vehicles knowing their position relative to some common reference (leader L), (ii) reconstructing AUV absolute locations on the earth for post processing/assimilation of data into maps, (iii) meeting criteria (i) and (ii) while being low-cost (<5% of vehicle cost), low- to medium-power-draw (<2 W), and fitting on a small (e.g. 4.875 inch diameter) AUV, and finally (iv) being robust to the loss of individual agents in the group.

(117) The reason for this set of required criteria is to have a solution that can be broadly adoptable as multi-AUV systems become realized. The solution to the scalable underwater formation problem must address these challenges such that vehicles remain together with a common reference frame, and that logged data across the group is sufficient to reconstruct global navigation (i.e. absolute navigation). The required accuracy of this global reconstruction depends on the application: for most oceanographic sensing, accuracy in tens to hundreds of meters is sufficient, whereas for image-based mapping more accurate navigation is required.

(118) “Scalable” is defined here as an approach that works for arbitrarily large numbers of vehicles within a sampling area—for example 100 AUVs within a 1 km area through the water column. An example of a solution that would not be considered scalable would be conventional two-way acoustic communications such as the commonly known Micromodem: the number of vehicles is limited by frequency and time sharing required by the channel. “Low-cost” translates to a production payload cost preferably of less than $500, which correspond to about 5% of the minimum cost of current low-cost AUV models such as the Riptide, and Bluefin SandShark vehicles. This eliminates chip scale atomic clock-type timing solutions and many array and lower-frequency transducer options.

(119) One-way communication with leader-follower-based architecture provides a means to have common reference between the underwater vehicles and deals with the scalability issues with two-way or multi-way communication networks. As high-frequency acoustic and optic modem technologies increase underwater bandwidth, certain embodiments of the present invention are well suited to incorporate such underwater communications improvements into the Doppler-based solution presented herein.

(120) In this example, the leader L is assumed to have reliable navigation, and could one of many solutions, including an AUV with an INS/DVL or a surface vehicle with GPS towing an acoustic source 112. Alternate configurations not explored here, but are within the scope of the present invention, would include a homogeneous group of low-cost vehicles taking turns surfacing and becoming the leader L, or using multiple leaders to further collapse follower F localization.

(121) Follower F adaptation is dependent on one of two, or both measurements: frequency of the incoming signals S, and amplitude of the incoming signals S at two or more frequencies. Frequency changes due to Doppler shift, in which relative motion causes a frequency shift. By adapting heading to maximize the Doppler shift, each follower F remains pointing towards the leader L in a swarming-type behavior. Speed may also be varied adaptively based on the received amplitudes of two or more transmitted frequencies, which provide an approximation for range. Attenuation of frequency can be thought of as the difference between received frequency level (i.e. amplitude) with a reference frequency level (i.e. amplitude), with the reference frequency being the known or determined source frequency and/or amplitude, depending on the embodiment. With frequency-dependent attenuation of sound acting as a stand-in for range in some embodiments and Doppler shifted frequency acting as a stand-in for bearing, relative AUV behaviors can be constructed in a range-bearing space similar to that explored for relative one way time-travel (OWTT)-inverted USBL (iUSBL), as described in U.S. patent application publication US-2019/0204430-A1, but with one tenth the system parts cost.

(122) A mission profile for such a system typically includes three parts: deployment, sampling, and recovery. In deployment and recovery, a fixed beacon (i.e. source 112) on a ship or mooring would be used as a fixed reference frame to build up the AUV (i.e. follower F) formation for deployment, and to collapse it and bring the vehicles safely back in recovery. In fixed-beacon mode, Doppler shift may be used on each AUV to estimate bearing directly in real time, and with adaptation make recovery possible. For sampling, a leader L carries a dual-frequency acoustic beacon, and follower AUVs use estimates of Doppler shift and frequency-differences in attenuation to approximate range and bearing, which are used in different swarming behaviors.

(123) Three possible electronic controller set ups were compared during this example, (i) an Ardunio-type microcontroller without analog electronics (referred to as Ardunio only), a DAQ-based microcontroller (DAQ Design) and a DAQ-based microcontroller with a custom analog front-end (Analog Front). The Ardunio Only microcontroller is flexible, requires only about 0.8 A at 5 V and about 0.4 W power, and has a theoretical accuracy of approximately 10 Hz for 1 second of data. However, the Ardunio Only did not achieve sufficient frequency resolution in this example. The DAQ-based undersampling resulted in a accuracy of only 1 Hz, which is still too low for accurate angle reconstruction, while requiring 1.5 A and 7.5 W power, resulting in a system well suited for collecting raw data, but not processing. The Analog Front microcontroller requires 0.1 A at 5V and 0.5 W for power, is still flexible requiring hardware tuning, but is still applicable and was determined to meet frequency estimation and power requirements of about 0.1 A at 5 volts and about 0.5 W, while providing about 0.01 Hz frequency resolution. This configuration enables flexible hardware using required but applicable hardware.

(124) The resulting prototype analog electronics hardware front end uses a sample and hold with undersampling and bandpass filtering, producing an undersampled wave that is filtered to obtain a clean aliased tone. A Schmitt trigger then converts the sinusoidal signal to a square wave, and frequency and amplitude are then estimated using an Arduino MkrZero microcontroller with an interrupt-based period detection method. With an oscillator frequency of 48 kHz on the Arduino MkrZero and an aliased tone around 1 kHz, the frequency accuracy is 0.02 Hz. This uncertainty compounds with the Cramer-Rao lower bound with a variance of around 0.015 Hz. These two sources of error combined for an error of 0.035 Hz, meeting the frequency estimation requirement for position reconstruction. The prototype analog boards were tested using a Teledyne Reson TC4013 hydrophone element, and were experimentally shown to estimate frequency within this bound in short-range field tests using a moving source at ranges up to 20 m for 20 kHz, 36 kHz, 45 kHz and 100 kHz tones. Preliminary tank and dock tests were sufficiently promising to begin systems integration of the prototype with a JetYak ASV and SandShark AUV for further long-range field trials. The great advantage of this system over the other options in the design matrix come from size, power requirements, and accuracy.

Example 2

(125) Bearing and or heading estimation from Doppler shift. In this example, the concepts described above herein are applied conceptually and mathematically in three situations that may be easier to understand. Here a heading to a source 112 based on Doppler shift estimation, spanning the scenarios of whether {right arrow over (v)}.sub.s is one of (1) zero (i.e. not moving), (2) known, or (3) unknown and whether f.sub.s is known or unknown.

(126) In the first scenario, when source 112 velocity is zero, the bearing from the receiver 152 to the source 112 (θ.sub.rel) can be estimated directly based on the received frequencyf for a case where the source velocity |v.sub.s|=0 and the source frequency f.sub.s is known, and represented as in Math 25.

(127) 0$\begin{array}{cc}\cos \left({\theta }_{\mathrm{rel}}\right)=\frac{c\left(f_r-f_s\right)}{.Math.v_r.Math.f_s}.& \mathrm{Math}25\end{array}$

(128) If f.sub.s is unknown but the source 112 is known to be stationary, source frequency must first be estimated. This is done by setting receiver 152 velocity to 0, i.e. {right arrow over (v)}={right arrow over (0)}, in which case f.sub.r=f.sub.s. Once f.sub.s is known, Math 25 may be used. In addition, zero source 112 velocity makes it possible to simplify the relationship between source 112 and receiver 152 frequencies further by describing the received frequency as the source frequency plus a Doppler shift f.sub.d as represented in Math 26 and Math 27.

(129) $\begin{array}{cc}{f}_r=\frac{f_s\left(c+{\stackrel{.fwdarw.}{v}}_r.Math.{\hat{n}}_{\mathrm{rel}}\right)}{c},& \mathrm{Math}26\\ f_r=f_s+\frac{f_s.Math.{\stackrel{.fwdarw.}{r}}_r.Math.\cos \left({\theta }_{rel}\right)}{c}=f_s+f_d.& \mathrm{Math}27\end{array}$

(130) In the second scenario, when source velocity is non zero: If the source velocity is non-zero, and frequency is known, receiver 152 adaptation is used to first estimate the magnitude of the source velocity along the relative normal vector, i.e. {right arrow over (v)}.sub.r.Math.{circumflex over (n)}.sub.rel. To do this, the receiver stops, so that the frequency shift may be measured, as represented in Math 28 and Math 29.

(131) $\begin{array}{cc}{f}_r\left({\stackrel{.fwdarw.}{v}}_r=0\right)=f_s\frac{c}{c-{\stackrel{.fwdarw.}{v}}_s.Math.{\hat{n}}_{\mathrm{rel}}}& \mathrm{Math}28\\ {\stackrel{.fwdarw.}{v}}_s.Math.{\hat{n}}_{\mathrm{rel}}=c-\frac{f_s}{f_r\left({\stackrel{.fwdarw.}{v}}_r=0\right)}& \mathrm{Math}29\end{array}$

(132) The receiver 152 may then begin moving with constant velocity {right arrow over (v)}.sub.r so that bearing may be directly estimated, as represented in Math 30.

(133) $\begin{array}{cc}\cos \left({\theta }_{\mathrm{rel}}\right)=\frac{f_r/f_s\left(c-{\stackrel{.fwdarw.}{v}}_s.Math.{\hat{n}}_{\mathrm{rel}}\right)-c}{.Math.{\stackrel{.fwdarw.}{\nu }}_r.Math.}& \mathrm{Math}30\end{array}$

(134) This process would need to be repeated as {right arrow over (v)}.sub.r.Math.{circumflex over (n)}.sub.rel changes because the source 112 is approaching/departing from the receiver 152, or as {right arrow over (v)}.sub.s changes.

(135) In the third scenario, unknown source frequency: If f.sub.s is unknown, the frequency associated with the velocity of the source 112 relative to the receiver 152 (f.sub.a for aggregate frequency) can be used instead from a “stop” adaptation, and represented in Math 31.

(136) $\begin{array}{cc}{f}_a=f_s\frac{C}{c-{\stackrel{.fwdarw.}{v}}_s.Math.{\hat{n}}_{\mathrm{rel}}}& \mathrm{Math}31\end{array}$

(137) Constant-velocity receiver 152 motion is then used to estimate θ.sub.rel, as shown in Math 32.

(138) $\begin{array}{cc}\cos \left({\theta }_{\mathrm{rel}}\right)=\frac{f_r/f_a-c}{.Math.{\stackrel{.fwdarw.}{v}}_r.Math.}.& \mathrm{Math}32\end{array}$

(139) An alternative adaptation to the stop-and-then-resume constant velocity behavior is to circle, estimating received frequency f.sub.r versus heading h (also referred herein as θ.sub.rel and illustrated in FIG. 2B). The maximum frequency f.sub.r max during a 360-degree revolution at constant speed corresponds to the heading to the sound source; f.sub.a corresponds to the mean of the minimum and maximum received frequencies and is represented in Math 33.

(140) $\begin{array}{cc}{f}_r=\frac{f_s\left(c+{\stackrel{.fwdarw.}{v}}_r.Math.{\hat{n}}_{\mathrm{rel}}\right)}{\left(c-{\stackrel{.fwdarw.}{v}}_s.Math.{\hat{n}}_{\mathrm{rel}}\right)}.& \mathrm{Math}33\end{array}$

(141) Although specific features of the present invention are shown in some drawings and not in others, this is for convenience only, as each feature may be combined with any or all of the other features in accordance with the invention. While there have been shown, described, and pointed out fundamental novel features of the invention as applied to a preferred embodiment thereof, it will be understood that various omissions, substitutions, and changes in the form and details of the devices illustrated, and in their operation, may be made by those skilled in the art without departing from the spirit and scope of the invention. For example, it is expressly intended that all combinations of those elements and/or steps that perform substantially the same function, in substantially the same way, to achieve the same results be within the scope of the invention. Substitutions of elements from one described embodiment to another are also fully intended and contemplated. It is also to be understood that the drawings are not necessarily drawn to scale, but that they are merely conceptual in nature.

(142) It is the intention, therefore, to be limited only as indicated by the scope of the claims appended hereto. Other embodiments will occur to those skilled in the art and are within the following claims.