# Application of On-Board Evolutionary Algorithms to Underwater Robots to Optimally Replan Missions with Energy Constraints

Authors: M. L. Seto
Journal: Journal of Robotics
 (2012)

---

## Abstract

The objective is to show that on-board mission replanning for an AUV sensor coverage mission, based on available energy, enhances mission success. Autonomous underwater vehicles (AUVs) are tasked to increasingly long deployments, consequently energy management issues are timely and relevant. Energy shortages can occur if the AUV unexpectedly travels against stronger currents, is not trimmed for the local water salinity has to get back on course, and so forth. An on-board knowledge-based agent, based on a genetic algorithm, was designed and validated to replan a near-optimal AUV survey mission. It considers the measured AUV energy consumption, attitudes, speed over ground, and known response to proposed missions through on-line dynamics and control predictions. For the case studied, the replanned mission improves the survey area coverage by a factor of 2 for an energy budget, that is, a factor of 2 less than planned. The contribution is a novel on-board cognitive capability in the form of an agent that monitors the energy and intelligently replans missions based on energy considerations with evolutionary methods.


---

## Body

## 1. Introduction

Autonomous underwater vehicles (AUVs) are robots used for underwater tasks that range from surveys, inspection of submerged structures (e.g., pipelines), searching for downed aircraft, tracking oceanographic features, laying undersea cable, undersea mapping, and finding mines, to name a few. Such robots work in an unstructured dynamic environment with uniqueperception, communication, and decision issues compared to land, air, or space robots. Means for perceptionand detection of underwater targets include magnetic, optical, electric field, thermal (infrared), hydrodynamic changes (pressure), and sound (acoustic). Sound is unsurpassed, compared to other means, for detection underwater. As an example, the sonar (sound navigation and ranging) is a popular underwater perception sensor that uses sound for detection, classification, and location of underwater targets. Having said that, there are acoustic propagation difficulties in the highly variable, noisy, and reverberant water medium. The ocean is a nonstationary and dynamic environment where the conductivity, temperature, and density of its water varies temporally and spatially and thus affects the propagation of acoustic signals within it. Add to this multi-path, absorptive losses (high attenuation) [1], and low bandwidth for acoustic signal propagation that also occur in nonpredictable ways. Consequently, underwater communication issues stem from the variability and poorness of acoustic propagation in water.These propagation limitations impact how AUVs are employed since reliable acoustic communications with their operators (or other AUVs) is not easily possible. Consequently, out of the land, ocean, space, and air robot environments, the ocean one is difficult for tasks that require persistent and reliable communications. Robotic autonomy, where the robot makesdecisions and autonomously alters its mission plans in situ without operator intervention, in fulfillment of its mission, is necessary to exploit the potential of underwater robots. Autonomy is one way of coping with the poor underwater communications issue.Autonomy ordecision issues are addressed to make AUVs truly autonomous—able to operate long periods without operator intervention. It is desirable that the AUV have the autonomy for decision making or problem solving to deal with unexpected robot or mission events in a timely fashion. Mission autonomy is the ability to adapt a mission to unanticipated conditions in the environment or in situ intelligence that can be exploited to better perform the mission. For example, in-situ environmental measurements can be applied to collect more optimal sonar images. Robot autonomy addresses issues that increase the robot’s fault tolerance so it can adapt to unexpected robot events (e.g., more energy consumed earlier in the mission than planned precipitating a shortage for the rest of the mission). Wherever possible, if on-board autonomy can replan, or adapt, in light of unexpected events, the mission can be completed or better performed. Otherwise, the mission could be scrubbed (or in a drastic case, the robot is lost) due to an unexpected event. At the root of the required autonomy or decision-making are cognitive abilities for the robot. A timely scenario that would benefit from such autonomy or decision making ability is discussed next.Large AUVs, of which the Explorer class [2] is an example, can have ranges on the order of hundreds of kilometers. Such missions can occur over a week or more which is a long time for an ocean environment to remain stationary. Consequently, energy shortages over long deployments are a real possibility. Energy shortages on missions can occur due to unplanned events, as the AUV travels through stronger currents, goes off-course and requires more energy to finish the survey and be at the recovery point on time, on-board hotel load increased because instrumentation use was higher (e.g., extra sensors employed), or the AUV was not trimmed for the local salinity conditions (final AUV trim only confirmed when AUV is underway) to name a few. The impact of such unplanned events cumulate over the course of long duration missions to the point where the planned mission may not be achievable anymore. Once the AUV is launched and underway, it is not (easily) possible to monitor these conditions in order to be forewarned of critical issues in time to have an operator recover the AUV to replan the survey. As well, the operator is not necessarily nearby on a support ship. With AUVs now used on longer missions, the issue of unexpected energy shortages is timely and relevant. The different types of AUV on-board energy is briefly discussed.Like most mobile robots, AUVs carry all their energy on-board for a mission. This energy powers on-board equipment, sensors, computers, propulsion/locomotion, and so forth. On long-duration surveys, the bulk of the energy is for propulsion/locomotion. The on-board volume allocated to carry energy, in the form of batteries, is fixed, so the objective is to carry batteries of the highest specific energy and density possible. Table1 (not an exhaustive list) shows properties of a few common AUV energy sources. Operating cost and endurance are correlated with the energy source selected. Consequently, endurance is also correlated with AUV size. A fair amount of effort has gone into investigating AUV energy sources [3–5]. They can range from the familiar lead acid battery to modern fuel cells [4, 5]. Fuel cells are an emerging technology that will impact how AUVs are tasked for long survey missions and for allowing on-board computationally intensive calculations. Presently, fuel cells are not commonly used in AUVs. The impact of energy on mission-planning is described next.Table 1
Common energy sources for AUVs.
Battery typeCost  ($/Wh)Energy density (Wh/liter)Specific energy (Wh/kg)Typical cell dimensions (mm)lithium ion4.27300130225 × 212 × 9.5silver zinc1.75240130178 × 161 × 8lead acid0.176530330 × 228 × 152AUV path planning (or mission planning) is an active area of research [6–14]. As in air and land robots, underwater path planning objectives include obstacle (moving or stationary) avoidance [6, 7], optimal area coverage [8], and transiting accurately and safely between points with high variability in the water conditions [9–11]. Most related work considers the energy budget and the desire to minimize energy use [9, 10]. However, there is little work that studies replanning specifically due to an unexpected energy shortage on long survey missions. There is even less work on missions that employ side scan sonars.A mission is planned with the AUV carrying 10% (or more) surplus energy. However, if unexpected events occur, and that surplus is insufficient, there is currently little contingent mission replanning. The usual response is to recover the AUV, replan the mission with an operator, download the mission to the AUV, and redeploy the AUV. Many such survey interruptions are undesirable on long missions as they require additional time, expense, and a nearby support ship. It also detracts from the value of using an AUV to begin with.This paper’s objective is to show that on-board autonomy to replan an AUV side scan sonar mission due to an unexpected AUV energy shortage enhances the mission’s success.This on-board autonomy is in the form of a novel knowledge-based autonomous agent developed to monitor and replan missions due to unexpected energy shortages. The agent replans the mission with a genetic algorithm (GA) that evaluates the fitness of proposed replanned missions to achieve the mission objectives (survey remaining area with less energy than planned and make the recovery schedule). It uses knowledge of the AUV’s nonlinear hydrodynamics, dynamics, and control response to proposed replanned missions. Additionally, it takes into account the AUV’s real-time attitudes, speed through water, hotel load, and so forth, to evaluate a replanned mission’s fitness. The agent continually compares actual energy expended against anticipated energy to expend for the mission. This is achieved through on-line calculations of the remaining energy/endurance to predict and evaluate the AUV likelihood of completing the mission given the measured energy consumption rate. If it appears, at any point in the mission, that the AUV will have insufficient energy to complete its mission as planned, the agent initiates a behavior to replan its mission given the survey area left, the remaining power, and the original mission completion and AUV recovery times.The rest of the paper is organized as follows. Section2 defines the mission configuration followed by an overview of the autonomous agent. Then, details of the AUV model (Sections 2.1–2.3) used in the optimization to evaluate the AUV hydrodynamics, dynamics, control response, and subsequent energy consumption to missions proposed by the genetic algorithm are described. Section 2.4 describes the genetic algorithm implementation and how the aforementioned AUV models are used as the evaluation function for the GA. Section 3 describes the initial validation of the AUV energy model component in the agent. Section 4 analyzes an illustrative case by imposing a range of available energies, time constraints, and survey areas to evaluate optimal solutions proposed by the agent. It then compares the optimal solutions against what would have been achieved without autonomous replanning of the mission to highlight the agent’s effectiveness. Section 5 concludes with a few remarks.


## 2. Autonomous Agent Description

The objective of this section is to define the mission configuration, provide an overview of the knowledge-based agent, and then detail the AUV models (dynamics, hydrodynamics, controls, energy) to be used in the GA. This Section concludes with an overview description of the GA implementation.The AUV mission is to survey an area using long straight transits capped by 180-degree turns which put the AUV on a reciprocal heading—the “lawn mower tracks” whose lane spacing defines the mission geometry or configuration (Figure1). Highlighted in yellow is the swath scanned by the AUV’s side-scan sonar on a constant heading. Side-scan sonars scan from both sides to a specific sonar range (shown as 100 m). The objective is to survey/scan an area through side-by-side swaths (strips) with overlap between the swaths (similar to lawn mowing). The overlap is required to co-register features in the images, perform feature-based navigation, and so forth. These constraints govern operation with side scan sonars. For the case study of Figure 1, a projected AUV energy shortage is detected at (X,Y)=(0,0) m with the AUV recovery point at (X,Y)=(2000,-2000) m to occur no later than tR of 30,000 seconds later. The arrows show the AUV travel direction.Figure 1
AUV side scan sonar survey mission (—) with 200 m lane spacing and 2 km survey leg lengths. Arrow heads indicate AUV travel direction (start point▸; recovery point •).The swath width relative to the lane spacing determines the amount of area overlap across neighboring swaths,Aoverlap. The area surveyed is the total area scanned by the sonar as it passes through. If all the area is scanned from the start to recovery point, then a total of 4 km2 of area has been surveyed (area in turns do not contribute to area surveyed).When the agent replans a mission, it calculates the energy to transit directly to the recovery point from every point along the mission. The optimal replanned mission surveys until there is just enough energy to branch off and transit to the recovery point. If the mission is optimally planned, the branch off to the recovery point occurs near the end of the survey area.The components of the agent are shown in Figure2. Upon detection of a projected energy shortage, the agent replans a new mission by first determining dimensions of the remaining area to survey (agent knows survey area corners and AUV location within it) and checks the actual power on-board, and the time left to do the rest of the survey. These parameters are inputs to the genetic algorithm to generate the nominal optimal mission, [MIS]o.  [MIS]o consists of the desired AUV speed vo, turn diameter Do, and the total time to, to complete this mission. However, this is only a nominal optimal mission as it may or may not be realizable by the AUV. Function, N, takes vo and Do and uses them as set point values for the robot to achieve. Speed achieved, vA, is determined based on the AUV propulsion, dynamics, hydrodynamics, and control as well as the water currents. vA is then used to determine area surveyed in time tA with the available energy. Note that there are three different time values, tR, to, and tA. The way the agent is implemented the recovery time, tR is the largest of the three.Figure 2
Overview of autonomous agent to replan AUV mission upon detection of an energy shortage.Finally, objective function,F, is applied to AUV response, R, to determine the fitness value, f, for proposed mission [MIS]o. The details of the dynamic and control models used in the on-line evaluation of the AUV’s response to a mission are briefly discussed next. This is followed by a description of the genetic algorithm implementation used.


### 2.1. Hydrodynamic and Dynamic Model

The on-board AUV hydrodynamics, dynamics and control models were implemented, and validated using the DRDCTheseus underwater vehicle [15] used in Arctic missions for laying cable under ice. The AUV equations of motion (1) for three rotational (yaw, pitch, roll) and three translational degrees-of-freedom are integrated. The notation used is shown in Figure 3.Figure 3
Nomenclature for AUV motion in body frame axes.X, Y, and Z, are the external forces due to the added masses, hydrodynamics, statics, and control fins. The control fin damping, natural frequency, and maximum rates are described with a second order model as part of the fin response to commanded deflections (where δbp = bow port fin, δss = stern starboard fin, and δr = rudder). K, M, and N are the moments of the roll, pitch, and yaw external forces. For brevity, only the X external forces are detailed in (2) as it is most relevant to propulsive power (4). The other 5 external forces [16] are omitted here for brevity. Note ρ = water density, and the following pertain to the AUV: l = length, m = mass, W = vehicle weight, B = buoyancy, and Xprop = propulsive thrust. A more detailed description of the hydrodynamic terms is available [16]. The propulsion model, captured through  Xprop, was validated to adequately capture the AUV behavior in level flight, diving, rising, and so forth [15]. (1)X=m[u.-vr+wq-xG(q2+r2)+yG(pq-r.)+zG(pr+q.)],Y=m[v.-wp+ur-yG(r2+p2)+zG(qr-p.)+xG(qp+r.)],Z=m[w.-uq+vp-zG(p2+q2)+xG(rp-q.)+yG(rq+p.)],K=Ixp.+(Iz-Iy)qr-(r.+pq)Ixz+(r2-q2)Iyz+(pr-q.)Ixy+m[yG(w.-uq+vp)-zG(v.-wp=ur)],M=Iyq.+(Ix-Iz)rp-(p.+qr)Ixy+(p2-r2)Izx+(qp-r.)Iyz+m[zG(u.-vr+wq)-xG(w.+uq+vp)],N=Izr.+(Iy-Ix)pq-(q.+rp)Iyz+(q2-p2)Ixy+(rq-p.)Izx+m[xG(v.-wp+ur)-yG(u.-vr+wq)];(2)X=-12ρl4[Xppp2+Xrrr2+Xqqq2+Xq|q|q|q|]+12ρl3[Xu.u.+Xv.v.+Xw.w.]+12ρl4[Xp.p.+Xq.q.+Xr.r.]+12ρl3[Xvrvr+Xwqwq]+12ρl2[12Xuuu2+Xvvv2+Xwww2+Xδrδru2(δr)2+12Xδbδbu2(δbp2+δbs2)+12Xδsδsu2(δsp2+δss2)+Xprop]+(W-B)sin⁡θ.


### 2.2. AUV Control Model

The AUV in this study has two bow fins and a cruciform (+) stern fin configuration. The horizontal fins are used for pitch, roll, and depth control. Yaw (heading) control is achieved through the stern fins in the vertical plane. Both vertical stern fins are deflected together and constituteδr. This horizontal control is directly relevant to the mission/path-planning work in this study.The fins are under closed-loop PID (proportional-integral-differential) control. Corrective fin deflections to minimize the attitude, heading, and depth errors are determined by applying the PID gains matrix to the AUV state vector:[ψ,θ,φ,ψ.,θ.,φ.,z,z.]  (yaw, pitch, roll, yaw rate, pitch rate, roll rate, depth, and depth rate) as shown in (3). [ψ,θ,φ] are the Euler angles that relate inertial frame axes to the body frame axes shown in Figure 3. The PID gains are arrived at through a combination of vehicle dynamic simulations and tuning during sea trials. In both cases, the AUV is commanded to do a variety of maneuvers that include holding and changing course, diving and rising, and turning at different speeds and rudder deflections, and so forth. In the case of the dynamic simulations, the AUV’s hydrodynamic derivatives were both predicted and measured [17]. This controller has been studied in some detail and is near optimal in its control authority distribution to maintain the attitude and heading set points [18]:(3)δ=[δbsδbpδssδspδr]=[PIDGAINSMATRIX]×[ψθϕ⋅ψ⋅θ⋅ϕZ⋅Z].


### 2.3. AUV Energy Consumption Model

The energy consumption of the AUV is modeled as [19]: (4)et=(ps+pp+pv)×r3600×V,
such that: et = total energy on-board (kWh) [fixed for mission], r = survey range (km) [changes with mission geometry, e.g., in Figure 1], V = AUV speed through water (m/s), pv = on-board vehicle equipment power (W) [hotel load #1, changes with control plane usage, sensors on different power settings, use of ballast system, intensity of computations, etc. over mission], ps = sonar power, (W) [hotel load #2, changes with sonar, sonar range, and mission geometry in step function manner], pp = propulsion power (W) [~AUV resistance (2) × AUV water speed, predict to change as per (1)–(3)]. AUV propulsion power, pp, is captured through time-varying models based on (1)–(3) which calculate the hydrodynamic resistance in order to predict energy requirements for the remaining mission. As shown in Figure 2, the inputs to these equations are the measured on-board AUV speeds (both speed through water and speed over ground), steady-state yaw, pitch, and roll angles, angular rates, and so forth. The on-board equipment and sensor energy usage is described in terms pv and ps, respectively. A running average of the hotel loads are used as measures of pv and ps for input into the autonomous agent.As the AUV speed increases so does the AUV’s hydrodynamic resistance (~v2) and, consequently, the energy is consumed at a higher rate. This could result in a shorter mission time if it does not consume all the energy before the mission is complete. On long deployments, the propulsion power is often the largest term of the three. It varies as  ~velocity3 × time. If the AUV speed is fast, it consumes energy quickly and may not survey much area before having to transit to the recovery point—thus mission success is limited by energy. If the AUV speed is slow, it may also not cover much area before it has to transit to the recovery point (mission success limited by time). The optimal solution is somewhere in between.Thus, the agent uses knowledge of the robot performance through the dynamic, hydrodynamic, and controller models with input from measured on-board AUV states, to monitor and predict energy usage to detect an energy shortfall. The energy consumption prediction is performed everyτ seconds. Typically, τ is the time to complete 90% of a survey leg which is just prior to the AUV changing heading. It is a good point in a mission to replan and change a mission if required. These energy projections are also compared against a time-dependent battery energy-consumption curve since the consumption rate is nonlinear and specific to a battery.


### 2.4. Genetic Algorithm Implementation

The application to path-planning of a search procedure based on Darwin’s theories of natural selection and survival has been recognized [20]. In these methods, referred to as genetic algorithms, a population of possible solutions is maintained and the paths are iteratively transformed by genetic operations like cross-over and mutation [20]. GAs are applied to a variety of path-planning problems [6, 10, 13]. They are especially adept at solving problems with objective functions that are not continuous, differentiable, or possessing a closed tractable form.This is exactly the case for the AUV energy problem here. The objective function acts on quantities that are obtained through integration of differential equations. As well, the propulsion energy varies as ~v3×time so the three quantities are inextricably linked, yet they are optimized for a calculated quantity, the area surveyed. The application of genetic algorithms for the posed AUV energy problem, over other methodologies, is quite appropriate.The optimization objective is to concurrently(1)
maximize area surveyed as shown in Figure1 (or maximize range, r, in (4)) and(2)
stay within energy budget.The optimizing parameters are(i)
AUV speed (AUV performance),(ii)
swath width overlap (or turn diameter for a given sonar range) (AUV sensor performance), and(iii)
replanned mission time (mission requirement).Bounds over which the optimizing parameters can vary are imposed to confine the GA to search space regions with feasible solutions. This is so the agent does not waste time looking in regions that are known tonot yield physically achievable solutions.The bounds on the optimizing parameters are shown in Table 2. They are based on at-sea best practices. The speed bounds 0.5 m/s < AUV speed <2 m/s are achievable for the AUV used.Table 2
Bounds on optimizing parmeters. (sonar range = 50 m on one side→ survey swath width = 100 m).
Optimizing parameterBounds imposedSpeed over ground[0.5–2.0] meters/secondAUV performanceTurn diameter[50–80] m ~ [50–20] % overlap of neighbour swathssensor performanceTime[80–100] % of max timemission requirementThe lane spacing is a function of the sonar swath width and the area overlap between neighboring swaths. While high overlap is conducive to good target detection with side scan sonars, it does not make for an efficient survey. From just geometrical considerations (Figure1) between overlapping rectangles, the lane spacing = sonar range ×2×(1-Aoverlap).The time to complete the survey and be at the recovery point is a mission requirement. It is desirable that the AUV be at the recovery point more-or-less on time where possible to meet the ship to ensure successful recovery of the AUV and data.Formally, the multiple objectives are to optimize maximum coverage and to stay within the energy budget and time constraints. The optimization problem is thus posed asgiven:
objective functionF:A → ℜ from some set A of real numbers ℜfind:
[MIS]o∈A:F([MIS]o)≥F([MIS])∀[MIS]inA,where:
A is the solution space spanned by solutions, [MIS]to F. [MIS]o is the optimal solution and ℜ is the set of real numbers.Applying functionN takes mission parameter vector [MIS]o as input to the AUV nonlinear equations of motion (1)–(3) to determine AUV response R, that is,(5)R=N([MIS]o)⟶[speedareatimeenergyachievedsurveyedneededused].
Then, objective function F (6) assigns value, f, to response vector, R, as a measure of a proposed [MIS]o  fitness to achieve the mission objectives. Weights wi reflect the relative priorities of the different objectives and vary with mission, sensors, AUV, environmental conditions, and so forth:(6)F(R)=f=w1(areasurveyed)+w2(timerequired)+w3(energyleft-energyused)+w4(hotelload)+w5(speedachieved-speeddesired).
Search space A is pruned to include solutions [MIS] whose:(i)
time for a complete area survey (based on proposed speed, lane spacing, etc.) is less thantR, and(ii)
whose energy for a complete area survey (based on proposed speed, lane spacing, etc.) is less thanet (4).To account for operational requirements, the following heuristic constraints are imposed:(i)
energy consumed for a proposed solution (given proposed speed, lane spacing, and time) is less than 0.85 × remaining power (though weightw3)—as in practice, this saves energy for the AUV to get to the recovery point, and(ii)
the proposed mission time is less than 0.95 × total time allocated (tR), for the mission (through weight w2),  which ensures the AUV does not arrive at the recovery point too early.With this scheme, the agent does not produce solutions exceeding energy budgetet or maximum time tR.The genetic algorithm creates a population of solutions,[MIS] and uses cross-over and mutation [20] to generate better solutions. Then, it propagates the evolution of the better solutions by choosing the best solutions as parent solutions. Poor solutions, as in nature, can evolve and propagate. However, if sufficient generations are calculated, poor solutions do not survive. A reasonable solution that minimizes (or maximizes) the objective function is an optimal solution. Often there are several objectives to optimize, as in this case.The genetic algorithm simulates the evolution of an[MIS] solution towards the optimal one where “survival of the fittest” is applied to a population of solutions. The steps in the genetic algorithm implementation are as follows:(1)
initialize spaceA spanned by a population of acceptable solutions, [MIS]—(5);(2)
evaluate each solution, performF(N[MIS])—(6);(3)
select a new population from the old population based on the fitness of the solutions;(4)
apply genetic operators cross-over and mutations to the new population to create new solutions;(5)
evaluate the newly-created solutions by applyingF(N[MIS]), and(6)
repeat steps 3–6 until termination criteria which is convergence of the fitness valuef.The initial solution space is seeded with similar historical in-water missions (i.e., good combinations of AUV velocity and swath spacing/turn diameter that surveyed a rectangular area within a prescribed time limit) that worked in the past. The GA achieves solutions with an initial population size of 40 solutions and a maximum 25 generations of evolution.The chromosome representation to describe members of the solution population was real-valued over binary due to the greater (order of magnitude) computational efficiency of real valued representations [21]. This impacts the implementation of the GA and especially the way the nonuniform mutation and arithmetic cross-over operators are applied. Define parent solutions as vectors X̅={x1,…,xi,…,xn}andY̅={y1,…,yi…,yn}. The parameters of these vectors are AUV speed, swath spacing/turn diameter, and mission completion time. Nonuniform mutation changes one of the parameters of the parent solution based on a non-uniform probability distribution. This Gaussian distribution starts wide and narrows to a point distribution as the current generation approaches the maximum number of generations. Nonuniform mutation randomly selects one of the three (in this case) parameters, and sets it equal to a nonuniform random number:(7)xi′={xi+(bi-xi)f(G)ifr1<0.5xi-(xi+ai)f(G)ifr1≥0.5xi,otherwise,f(G)=(r2(1-GGmax⁡))b,r1,r2
= uniform random numbers in range[0,1]G
= the current generation numberGmax
= maximum number of generations (set by user)b
= shape parameter (set by user)ai
= minimum possible value for parameterxibi
= maximum possible value for parameterxi.Note, there are two possibilities for the nonuniform random number depending on the value of random numberr1.Arithmetic cross-over produces two complimentary linear combinations of the parent solutions(X̅,Y̅) where r=a uniform random number between 0 and 1. The children of the cross-over operation, (X̅′,Y̅′), are:(8)X̅′=rX̅+(1-r)Y,̅Y̅′=(1-r)X̅+rY.̅
Normalizations on the new (children) solutions are not required—the results are immediately usable.The posed optimization problem sets up the possibility of local extrema in solution spaceA. Given the objective is to survey as much area as possible with a fixed energy budget and to arrive at the recovery point by a given time, the optimization can be driven by energy, time, or both. The next section briefly discusses the validation of the AUV energy model.


## 2.1. Hydrodynamic and Dynamic Model

The on-board AUV hydrodynamics, dynamics and control models were implemented, and validated using the DRDCTheseus underwater vehicle [15] used in Arctic missions for laying cable under ice. The AUV equations of motion (1) for three rotational (yaw, pitch, roll) and three translational degrees-of-freedom are integrated. The notation used is shown in Figure 3.Figure 3
Nomenclature for AUV motion in body frame axes.X, Y, and Z, are the external forces due to the added masses, hydrodynamics, statics, and control fins. The control fin damping, natural frequency, and maximum rates are described with a second order model as part of the fin response to commanded deflections (where δbp = bow port fin, δss = stern starboard fin, and δr = rudder). K, M, and N are the moments of the roll, pitch, and yaw external forces. For brevity, only the X external forces are detailed in (2) as it is most relevant to propulsive power (4). The other 5 external forces [16] are omitted here for brevity. Note ρ = water density, and the following pertain to the AUV: l = length, m = mass, W = vehicle weight, B = buoyancy, and Xprop = propulsive thrust. A more detailed description of the hydrodynamic terms is available [16]. The propulsion model, captured through  Xprop, was validated to adequately capture the AUV behavior in level flight, diving, rising, and so forth [15]. (1)X=m[u.-vr+wq-xG(q2+r2)+yG(pq-r.)+zG(pr+q.)],Y=m[v.-wp+ur-yG(r2+p2)+zG(qr-p.)+xG(qp+r.)],Z=m[w.-uq+vp-zG(p2+q2)+xG(rp-q.)+yG(rq+p.)],K=Ixp.+(Iz-Iy)qr-(r.+pq)Ixz+(r2-q2)Iyz+(pr-q.)Ixy+m[yG(w.-uq+vp)-zG(v.-wp=ur)],M=Iyq.+(Ix-Iz)rp-(p.+qr)Ixy+(p2-r2)Izx+(qp-r.)Iyz+m[zG(u.-vr+wq)-xG(w.+uq+vp)],N=Izr.+(Iy-Ix)pq-(q.+rp)Iyz+(q2-p2)Ixy+(rq-p.)Izx+m[xG(v.-wp+ur)-yG(u.-vr+wq)];(2)X=-12ρl4[Xppp2+Xrrr2+Xqqq2+Xq|q|q|q|]+12ρl3[Xu.u.+Xv.v.+Xw.w.]+12ρl4[Xp.p.+Xq.q.+Xr.r.]+12ρl3[Xvrvr+Xwqwq]+12ρl2[12Xuuu2+Xvvv2+Xwww2+Xδrδru2(δr)2+12Xδbδbu2(δbp2+δbs2)+12Xδsδsu2(δsp2+δss2)+Xprop]+(W-B)sin⁡θ.


## 2.2. AUV Control Model

The AUV in this study has two bow fins and a cruciform (+) stern fin configuration. The horizontal fins are used for pitch, roll, and depth control. Yaw (heading) control is achieved through the stern fins in the vertical plane. Both vertical stern fins are deflected together and constituteδr. This horizontal control is directly relevant to the mission/path-planning work in this study.The fins are under closed-loop PID (proportional-integral-differential) control. Corrective fin deflections to minimize the attitude, heading, and depth errors are determined by applying the PID gains matrix to the AUV state vector:[ψ,θ,φ,ψ.,θ.,φ.,z,z.]  (yaw, pitch, roll, yaw rate, pitch rate, roll rate, depth, and depth rate) as shown in (3). [ψ,θ,φ] are the Euler angles that relate inertial frame axes to the body frame axes shown in Figure 3. The PID gains are arrived at through a combination of vehicle dynamic simulations and tuning during sea trials. In both cases, the AUV is commanded to do a variety of maneuvers that include holding and changing course, diving and rising, and turning at different speeds and rudder deflections, and so forth. In the case of the dynamic simulations, the AUV’s hydrodynamic derivatives were both predicted and measured [17]. This controller has been studied in some detail and is near optimal in its control authority distribution to maintain the attitude and heading set points [18]:(3)δ=[δbsδbpδssδspδr]=[PIDGAINSMATRIX]×[ψθϕ⋅ψ⋅θ⋅ϕZ⋅Z].


## 2.3. AUV Energy Consumption Model

The energy consumption of the AUV is modeled as [19]: (4)et=(ps+pp+pv)×r3600×V,
such that: et = total energy on-board (kWh) [fixed for mission], r = survey range (km) [changes with mission geometry, e.g., in Figure 1], V = AUV speed through water (m/s), pv = on-board vehicle equipment power (W) [hotel load #1, changes with control plane usage, sensors on different power settings, use of ballast system, intensity of computations, etc. over mission], ps = sonar power, (W) [hotel load #2, changes with sonar, sonar range, and mission geometry in step function manner], pp = propulsion power (W) [~AUV resistance (2) × AUV water speed, predict to change as per (1)–(3)]. AUV propulsion power, pp, is captured through time-varying models based on (1)–(3) which calculate the hydrodynamic resistance in order to predict energy requirements for the remaining mission. As shown in Figure 2, the inputs to these equations are the measured on-board AUV speeds (both speed through water and speed over ground), steady-state yaw, pitch, and roll angles, angular rates, and so forth. The on-board equipment and sensor energy usage is described in terms pv and ps, respectively. A running average of the hotel loads are used as measures of pv and ps for input into the autonomous agent.As the AUV speed increases so does the AUV’s hydrodynamic resistance (~v2) and, consequently, the energy is consumed at a higher rate. This could result in a shorter mission time if it does not consume all the energy before the mission is complete. On long deployments, the propulsion power is often the largest term of the three. It varies as  ~velocity3 × time. If the AUV speed is fast, it consumes energy quickly and may not survey much area before having to transit to the recovery point—thus mission success is limited by energy. If the AUV speed is slow, it may also not cover much area before it has to transit to the recovery point (mission success limited by time). The optimal solution is somewhere in between.Thus, the agent uses knowledge of the robot performance through the dynamic, hydrodynamic, and controller models with input from measured on-board AUV states, to monitor and predict energy usage to detect an energy shortfall. The energy consumption prediction is performed everyτ seconds. Typically, τ is the time to complete 90% of a survey leg which is just prior to the AUV changing heading. It is a good point in a mission to replan and change a mission if required. These energy projections are also compared against a time-dependent battery energy-consumption curve since the consumption rate is nonlinear and specific to a battery.


## 2.4. Genetic Algorithm Implementation

The application to path-planning of a search procedure based on Darwin’s theories of natural selection and survival has been recognized [20]. In these methods, referred to as genetic algorithms, a population of possible solutions is maintained and the paths are iteratively transformed by genetic operations like cross-over and mutation [20]. GAs are applied to a variety of path-planning problems [6, 10, 13]. They are especially adept at solving problems with objective functions that are not continuous, differentiable, or possessing a closed tractable form.This is exactly the case for the AUV energy problem here. The objective function acts on quantities that are obtained through integration of differential equations. As well, the propulsion energy varies as ~v3×time so the three quantities are inextricably linked, yet they are optimized for a calculated quantity, the area surveyed. The application of genetic algorithms for the posed AUV energy problem, over other methodologies, is quite appropriate.The optimization objective is to concurrently(1)
maximize area surveyed as shown in Figure1 (or maximize range, r, in (4)) and(2)
stay within energy budget.The optimizing parameters are(i)
AUV speed (AUV performance),(ii)
swath width overlap (or turn diameter for a given sonar range) (AUV sensor performance), and(iii)
replanned mission time (mission requirement).Bounds over which the optimizing parameters can vary are imposed to confine the GA to search space regions with feasible solutions. This is so the agent does not waste time looking in regions that are known tonot yield physically achievable solutions.The bounds on the optimizing parameters are shown in Table 2. They are based on at-sea best practices. The speed bounds 0.5 m/s < AUV speed <2 m/s are achievable for the AUV used.Table 2
Bounds on optimizing parmeters. (sonar range = 50 m on one side→ survey swath width = 100 m).
Optimizing parameterBounds imposedSpeed over ground[0.5–2.0] meters/secondAUV performanceTurn diameter[50–80] m ~ [50–20] % overlap of neighbour swathssensor performanceTime[80–100] % of max timemission requirementThe lane spacing is a function of the sonar swath width and the area overlap between neighboring swaths. While high overlap is conducive to good target detection with side scan sonars, it does not make for an efficient survey. From just geometrical considerations (Figure1) between overlapping rectangles, the lane spacing = sonar range ×2×(1-Aoverlap).The time to complete the survey and be at the recovery point is a mission requirement. It is desirable that the AUV be at the recovery point more-or-less on time where possible to meet the ship to ensure successful recovery of the AUV and data.Formally, the multiple objectives are to optimize maximum coverage and to stay within the energy budget and time constraints. The optimization problem is thus posed asgiven:
objective functionF:A → ℜ from some set A of real numbers ℜfind:
[MIS]o∈A:F([MIS]o)≥F([MIS])∀[MIS]inA,where:
A is the solution space spanned by solutions, [MIS]to F. [MIS]o is the optimal solution and ℜ is the set of real numbers.Applying functionN takes mission parameter vector [MIS]o as input to the AUV nonlinear equations of motion (1)–(3) to determine AUV response R, that is,(5)R=N([MIS]o)⟶[speedareatimeenergyachievedsurveyedneededused].
Then, objective function F (6) assigns value, f, to response vector, R, as a measure of a proposed [MIS]o  fitness to achieve the mission objectives. Weights wi reflect the relative priorities of the different objectives and vary with mission, sensors, AUV, environmental conditions, and so forth:(6)F(R)=f=w1(areasurveyed)+w2(timerequired)+w3(energyleft-energyused)+w4(hotelload)+w5(speedachieved-speeddesired).
Search space A is pruned to include solutions [MIS] whose:(i)
time for a complete area survey (based on proposed speed, lane spacing, etc.) is less thantR, and(ii)
whose energy for a complete area survey (based on proposed speed, lane spacing, etc.) is less thanet (4).To account for operational requirements, the following heuristic constraints are imposed:(i)
energy consumed for a proposed solution (given proposed speed, lane spacing, and time) is less than 0.85 × remaining power (though weightw3)—as in practice, this saves energy for the AUV to get to the recovery point, and(ii)
the proposed mission time is less than 0.95 × total time allocated (tR), for the mission (through weight w2),  which ensures the AUV does not arrive at the recovery point too early.With this scheme, the agent does not produce solutions exceeding energy budgetet or maximum time tR.The genetic algorithm creates a population of solutions,[MIS] and uses cross-over and mutation [20] to generate better solutions. Then, it propagates the evolution of the better solutions by choosing the best solutions as parent solutions. Poor solutions, as in nature, can evolve and propagate. However, if sufficient generations are calculated, poor solutions do not survive. A reasonable solution that minimizes (or maximizes) the objective function is an optimal solution. Often there are several objectives to optimize, as in this case.The genetic algorithm simulates the evolution of an[MIS] solution towards the optimal one where “survival of the fittest” is applied to a population of solutions. The steps in the genetic algorithm implementation are as follows:(1)
initialize spaceA spanned by a population of acceptable solutions, [MIS]—(5);(2)
evaluate each solution, performF(N[MIS])—(6);(3)
select a new population from the old population based on the fitness of the solutions;(4)
apply genetic operators cross-over and mutations to the new population to create new solutions;(5)
evaluate the newly-created solutions by applyingF(N[MIS]), and(6)
repeat steps 3–6 until termination criteria which is convergence of the fitness valuef.The initial solution space is seeded with similar historical in-water missions (i.e., good combinations of AUV velocity and swath spacing/turn diameter that surveyed a rectangular area within a prescribed time limit) that worked in the past. The GA achieves solutions with an initial population size of 40 solutions and a maximum 25 generations of evolution.The chromosome representation to describe members of the solution population was real-valued over binary due to the greater (order of magnitude) computational efficiency of real valued representations [21]. This impacts the implementation of the GA and especially the way the nonuniform mutation and arithmetic cross-over operators are applied. Define parent solutions as vectors X̅={x1,…,xi,…,xn}andY̅={y1,…,yi…,yn}. The parameters of these vectors are AUV speed, swath spacing/turn diameter, and mission completion time. Nonuniform mutation changes one of the parameters of the parent solution based on a non-uniform probability distribution. This Gaussian distribution starts wide and narrows to a point distribution as the current generation approaches the maximum number of generations. Nonuniform mutation randomly selects one of the three (in this case) parameters, and sets it equal to a nonuniform random number:(7)xi′={xi+(bi-xi)f(G)ifr1<0.5xi-(xi+ai)f(G)ifr1≥0.5xi,otherwise,f(G)=(r2(1-GGmax⁡))b,r1,r2
= uniform random numbers in range[0,1]G
= the current generation numberGmax
= maximum number of generations (set by user)b
= shape parameter (set by user)ai
= minimum possible value for parameterxibi
= maximum possible value for parameterxi.Note, there are two possibilities for the nonuniform random number depending on the value of random numberr1.Arithmetic cross-over produces two complimentary linear combinations of the parent solutions(X̅,Y̅) where r=a uniform random number between 0 and 1. The children of the cross-over operation, (X̅′,Y̅′), are:(8)X̅′=rX̅+(1-r)Y,̅Y̅′=(1-r)X̅+rY.̅
Normalizations on the new (children) solutions are not required—the results are immediately usable.The posed optimization problem sets up the possibility of local extrema in solution spaceA. Given the objective is to survey as much area as possible with a fixed energy budget and to arrive at the recovery point by a given time, the optimization can be driven by energy, time, or both. The next section briefly discusses the validation of the AUV energy model.


## 3. Validation

A basic validation of the energy model in the agent was performed against sea trials data collected with DRDC’sTheseus AUV [17]. The runs from that trial are maneuvers that are geometrically similar to those in Figure 1. While the resistance of the AUV in straight and level flight is understood and previously validated [17], the energy consumption from propulsion, in turn was not validated until this work. Energy consumption depends on whether the AUV is commanded to maintain closed-loop control over speed or power. In the validation runs, it maintained constant power which means the AUV decreased speed in a turn. The energy consumed was monitored and logged. With all the main components of the autonomous agent described the next section analyzes an illustrative example that highlights the agent’s effectiveness.


## 4. AUV Path Planning Driven by Energy

To assess the agent behaviour, the dimensions of the survey area (X km × Y km) and the mission time, tR, until recovery were fixed and the energy budget varied, from insufficient, to a surplus at the time the agent projects an energy shortage. The suspected appearance of local extrema in the solution space did materialize. Its manifestation depended on the energy budget. For the illustrative case, 300 kWh is known to be roughly enough to survey the area based on knowledge of the AUV from sea trials.


### 4.1. Agent Results and Discussions

The analysis on a representative case is used to highlight the agent’s capabilities. The optimal mission parameters for a 2 km × 2 km survey area (sum of total distance travelled =r from (4)) is shown in Table 3. Around the AUV’s known, energy budget of 300 kWh (et of (4)) is a solution, not necessarily optimal, that can survey the whole area which is both power and time limited. As the energy budget increases, the optimal solution becomes time-limited, as desired. As the energy budget decreases, it can be time limited without all the energy consumed (150 kWh case) or it can be neither energy or time limited (200 kWh case).Table 3
Optimized missions to survey 2 km × 2 km area with variable energy and time = 30,000 seconds until recovery.
Area surveyedLane spacingAUV speedEnergy usedEnergy availTime-max 30 k sec(%)(m)(m/s)(kWh)(kWh)(10 k sec)76.3478.291.46133.015029.83783.5879.831.59179.320028.11291.6180.001.72231.025028.60094.9879.221.86290.930029.40298.5975.911.92335.935029.74198.7676.051.95270.340029.652The lane spacing is bound to have between a 20%–50% area overlap with neighboring swaths given the range of the sonar. Obviously, minimal overlap area is desired for a survey since it takes less time. However, a lane spacing that achieves that overlap may or may not give an optimal survey energy-wise given the AUV speed and time constraints. The agent does produce lane spacing that creates overlaps close to the minimum 20% as shown in Table4.Table 4
Optimized sonar lane spacing and resulting overlap with neighboring lanes (50 m Sonar Range).
Area surveyedLane spacingSurvey area overlap(%)(m)(%)76.3478.2921.7183.5879.8320.1791.6180.0020.0094.9879.2220.7898.5975.9124.0998.7676.0523.95As shown in Table3, even with generous energy budgets, the agent surveys no more than 98% of the area. This is due to the way the optimizer works. 98% of the area surveyed is a completed survey of the area. From the results shown in Table 3, if an energy shortage is declared by the agent with less than 300 kWh of energy and only 30,000 seconds left for the remaining mission, the area will not be surveyed completely. However, the AUV will be at the recovery point having achieved the optimal maximal coverage possible shown in column 1 of Table 3.The fitness values from a proposed[MIS]can congregate around two main values depending on whether the GA pursues a time, or energy-limited solution. The fitness f values from these two “sets” of solutions can be different by an order of magnitude (not shown). In that case, the agent is designed to choose the energetically favorable solution.The trends observed in this case do not change with proportionately different sized survey areas or mission times (not shown). As a benchmark for the agent’s performance, the AUV dynamic response component can be computed eight times faster than real time. When the genetic algorithm and energy model components are accounted for, the time to compute a solution is about three times faster than real time. Convergence to a solution typically takes less than 25 generations. Time wise, this is only a little (15%) slower than real-time. These are reasonable responses from an on-board-the-vehicle agent.The effectiveness of these new cognitive capabilities was evaluated by comparing results of replanned missions against that achieved with a mission that did not adapt to energy shortfalls. The agent effectiveness was measured against the case of the optimal solution at 300 kWh in Table3. Specifically, a mission speed of 1.86 m/s and a turn diameter of 79.22 m. Normally, the operator will use this mission for the speed, energy, and time constraints.As shown in Figure4, the autonomous agent effectiveness is apparent as the available energy budget drops. The area surveyed with the fixed inflexible mission, near optimal for 300 kWh,  and decreases rapidly with decreased available energy (blue plot). The replanned missions (red plot) which optimizes the speed and turn diameter for the available energy perform better. At the lowest energy considered (factor of 2 below sufficient), the surveyed area improves over the near optimal 300 kWh mission, by almost a factor of 2.Figure 4
Effectiveness of the autonomous agent to replan AUV missions to adapt to an energy shortage.


### 4.2. Current Work

Encouraged by the results, the current work is implementing the autonomous agent within the DRDC Multi-Agent System framework designed for collaborative underwater vehicles [22]. New developments include collaborative vehicles replanning a mission given a vehicle(s) has an energy shortage. Parallel work uses the agent to replan a mission in the presence of currents measured with an on-board current profiler. At-sea trials are on-going for all developments.


## 4.1. Agent Results and Discussions

The analysis on a representative case is used to highlight the agent’s capabilities. The optimal mission parameters for a 2 km × 2 km survey area (sum of total distance travelled =r from (4)) is shown in Table 3. Around the AUV’s known, energy budget of 300 kWh (et of (4)) is a solution, not necessarily optimal, that can survey the whole area which is both power and time limited. As the energy budget increases, the optimal solution becomes time-limited, as desired. As the energy budget decreases, it can be time limited without all the energy consumed (150 kWh case) or it can be neither energy or time limited (200 kWh case).Table 3
Optimized missions to survey 2 km × 2 km area with variable energy and time = 30,000 seconds until recovery.
Area surveyedLane spacingAUV speedEnergy usedEnergy availTime-max 30 k sec(%)(m)(m/s)(kWh)(kWh)(10 k sec)76.3478.291.46133.015029.83783.5879.831.59179.320028.11291.6180.001.72231.025028.60094.9879.221.86290.930029.40298.5975.911.92335.935029.74198.7676.051.95270.340029.652The lane spacing is bound to have between a 20%–50% area overlap with neighboring swaths given the range of the sonar. Obviously, minimal overlap area is desired for a survey since it takes less time. However, a lane spacing that achieves that overlap may or may not give an optimal survey energy-wise given the AUV speed and time constraints. The agent does produce lane spacing that creates overlaps close to the minimum 20% as shown in Table4.Table 4
Optimized sonar lane spacing and resulting overlap with neighboring lanes (50 m Sonar Range).
Area surveyedLane spacingSurvey area overlap(%)(m)(%)76.3478.2921.7183.5879.8320.1791.6180.0020.0094.9879.2220.7898.5975.9124.0998.7676.0523.95As shown in Table3, even with generous energy budgets, the agent surveys no more than 98% of the area. This is due to the way the optimizer works. 98% of the area surveyed is a completed survey of the area. From the results shown in Table 3, if an energy shortage is declared by the agent with less than 300 kWh of energy and only 30,000 seconds left for the remaining mission, the area will not be surveyed completely. However, the AUV will be at the recovery point having achieved the optimal maximal coverage possible shown in column 1 of Table 3.The fitness values from a proposed[MIS]can congregate around two main values depending on whether the GA pursues a time, or energy-limited solution. The fitness f values from these two “sets” of solutions can be different by an order of magnitude (not shown). In that case, the agent is designed to choose the energetically favorable solution.The trends observed in this case do not change with proportionately different sized survey areas or mission times (not shown). As a benchmark for the agent’s performance, the AUV dynamic response component can be computed eight times faster than real time. When the genetic algorithm and energy model components are accounted for, the time to compute a solution is about three times faster than real time. Convergence to a solution typically takes less than 25 generations. Time wise, this is only a little (15%) slower than real-time. These are reasonable responses from an on-board-the-vehicle agent.The effectiveness of these new cognitive capabilities was evaluated by comparing results of replanned missions against that achieved with a mission that did not adapt to energy shortfalls. The agent effectiveness was measured against the case of the optimal solution at 300 kWh in Table3. Specifically, a mission speed of 1.86 m/s and a turn diameter of 79.22 m. Normally, the operator will use this mission for the speed, energy, and time constraints.As shown in Figure4, the autonomous agent effectiveness is apparent as the available energy budget drops. The area surveyed with the fixed inflexible mission, near optimal for 300 kWh,  and decreases rapidly with decreased available energy (blue plot). The replanned missions (red plot) which optimizes the speed and turn diameter for the available energy perform better. At the lowest energy considered (factor of 2 below sufficient), the surveyed area improves over the near optimal 300 kWh mission, by almost a factor of 2.Figure 4
Effectiveness of the autonomous agent to replan AUV missions to adapt to an energy shortage.


## 4.2. Current Work

Encouraged by the results, the current work is implementing the autonomous agent within the DRDC Multi-Agent System framework designed for collaborative underwater vehicles [22]. New developments include collaborative vehicles replanning a mission given a vehicle(s) has an energy shortage. Parallel work uses the agent to replan a mission in the presence of currents measured with an on-board current profiler. At-sea trials are on-going for all developments.


## 5. Conclusions

With AUVs used on increasingly long deployments, the issue of unexpected energy shortages is timely and relevant. Scripteda priori missions based on subsumption architecture [23] cannot adapt to the unstructured dynamic ocean environment and evolving changes within the AUV. This is especially true for AUVs on long deployments. The paper objective was to show that on-board mission replanning for an AUV sensor coverage mission, based on available energy, increases mission success in the event of an energy shortage.This objective was successfully achieved through on-board cognitive abilities in the form of a novel knowledge-based autonomous agent that replans its missions underway using on-line evolutionary methods to optimize the replanned mission. The replanned missions take into account the AUV dynamic, hydrodynamic, and control performance, AUV-projected energy consumption, amount of survey area left, amount of available energy, time left for mission completion and AUV recovery, and amount of overlap desired in the side scan sonar images. The agent also makes use of on-line measurements of the AUV attitudes, speed through water, hotel load, and so forth and performs an on-going assessment of the AUV’s ability to fulfil the mission energy wise.This agent was tested on scenarios that varied the energy budget from below sufficient to well-above sufficient. With energy budgets that are insufficient to perform the survey mission, the agent can be either time- or energy-limited. With sufficient energy, the agent uses most of the energy and the time. With surplus energy, the agent is time limited. These are acceptable solutions for the replanned mission. For the illustrative case studied, the replanned mission can improve the survey area coverage by a factor of 2 for an energy budget that is a factor of 2 less than planned.An effective on-board knowledge-based agent that can autonomously replan an optimal mission to intelligently adapt to an unexpected energy shortage has not been previously reported—especially one with considerations for side scan sonar requirements.



---

*Source: 542124-2012-04-10.xml*