Выделить слова: 

Патент США №

7613553

Автор(ы)

Benjamin

Дата выдачи

03 ноября 2009 г.

Unmanned vehicle control system



РЕФЕРАТ

A method for autonomously controlling a vehicle includes establishing decision variables for maneuvering the vehicle. Behavior functions are established for behaviors of the vehicle as a function of at least one of the established decision variables. These behavior function give a score which may be weighted, indicating the desirability of engaging in the associated behavior. A summation of the weighted behavior functions can be solved while the vehicle is operating to determine the values of the decision variables giving the highest summation of scores. In a preferred method, an optimal structure for the behavior functions and summation solution is taught. The method then guides the vehicle in accordance with the determined decision variable values.

Авторы:

Michael R. Benjamin (Boston, MA)

Заявитель:

The United States of America as represented by the Secretary of the Navy (Washington, DC)

ID семейства патентов

41227481

Номер заявки:

10/911,765

Дата регистрации:

30 июля 2004 г.

Отсылочные патентные документы США

Application NumberFiling DatePatent NumberIssue Date
60491489Jul 31, 2003

Класс патентной классификации США:

701/26; 700/250; 700/253; 701/27; 701/301

Класс совместной патентной классификации:

G08G 5/0069 (20130101); G08G 5/045 (20130101)

Класс международной патентной классификации (МПК):

G08G 9/02 (20060101); G01C 22/00 (20060101); G05B 19/18 (20060101)

Область поиска:

;701/26,27,300,301 ;700/253,248,246,250 ;235/400

Использованные источники

[Referenced By]

Патентные документы США

4862373August 1989Meng
4947350August 1990Murray et al.
6175803January 2001Chowanic et al.
6650965November 2003Takagi et al.
6711467March 2004Inoue et al.
2004/0162638August 2004Solomon

Другие источники


Michael R. Benjamin, Underwater Vehcile Control: Minimum Requirements for a Robust Decision Space, Jun. 2000, Command & Control Research & Technology Symposium 2000, Monterey, CA. cited by examiner .
Julio K. Rosenblatt, Maximising Expected Utility for Behaviour Arbitration, 1999, Lecture Notes in Computer Science; vol. 1747, Proceedings of the 12th Australian Joint Conference on Artificial Intelligence: Advanced Topics in Artificial Intelligence. cited by examiner .
Paolo Pirjanian, Mutiple Objective Action Selection and Behavior Fusion Using Voting, PhD Dissertation, 1998, Aalborg University, Denmark. cited by other .
Julio K. Rosenblatt, DAMN: a Distributed Architecture for Mobile Navigation, Techanical paper, Carnegie Mellon University, USA. cited by other .
Jukka Riekki, Reactive Task Execution of A Mobile Robot, Dissertation, 1999, pp. 40-60, University of Oulu, Finland. cited by other.

Главный эксперт: Black; Thomas G
Assistant Examiner: Behncke; Christine M
Уполномоченный, доверенный или фирма: Kasischke; James M. Stanley; Michael P. Nasser; Jean-Paul A.

Интересы правительства



STATEMENT OF GOVERNMENT INTEREST

The invention described herein may be manufactured and used by or for the Government of the United States of America for governmental purposes without the payment of any royalties thereon or therefor.

Текст решения-прецедента



This application claims the benefit of U.S. Provisional Application No. 60/491,489, filed Jul. 31, 2003 and which is entitled MULTI OBJECTIVE OPTIMIZATION MODEL FOR VEHICLE CONTROL by Michael R. Benjamin.

ФОРМУЛА ИЗОБРЕТЕНИЯ



What is claimed is:

1. A method for autonomously controlling a vehicle comprising: establishing decision variables for maneuvering the vehicle; establishing behavior functions associated with a behavior of the vehicle including at least two of safest path, shortest path, quickest path, boldest path, and steadiest path as a function of at least one of the established decision variables, each behavior function giving a score indicating the desirability of engaging in the associated behavior wherein said established behavior functions are piecewise defined functions, each behavior function being dependent on at least one of the established decision variables, said behavior function being based on an underlying expression, each behavior function having a plurality of pieces, each piece relatable to an interior function having a piece maximum value, each behavior function having only one piece for each combination of decision variable values; establishing weights of the established behavior functions to give weighted behavior functions; solving a summation of the weighted behavior functions while the vehicle is operating to determine the values of the decision variables giving the highest summation; and guiding the vehicle in accordance with the determined decision variable values.

2. The method of claim 1 further comprising the step of obtaining previously recorded variables from a database while the vehicle is operating, and at least one of said established behavior functions being dependent on said previously recorded variables.

3. The method of claim 1 wherein said step of solving a summation further comprises searching through the decision variable values to find the values of the decision variables that maximize the summation of the weighted behavior functions.

4. The method of claim 1 wherein the vehicle is an unmanned underwater vehicle.

5. The method of claim 1 further comprising the step of obtaining environmental variables while the vehicle is operating, and at least one of said established behavior functions being dependent on said obtained environmental variables.

6. The method of claim 5 wherein the step of obtaining environmental variables includes detecting other vehicles and the established behavior functions are responsive to detected vehicles.

7. The method of claim 6 wherein the established behavior functions includes safest path.

8. The method of claim 7 wherein calculation of the safest path behavior function includes: determining the time of the closest point of approach between the vehicle and detected other vehicle; determining the closest point of approach between the vehicle and the detected other vehicle; and applying a utility metric to the closest point of approach distance to give the score for the safest path behavior function.

9. The method of claim 1 wherein said decision variables include course, speed and action duration.

10. A method for autonomously controlling a vehicle comprising: establishing decision variables for maneuvering the vehicle, said decision variables including course, speed and action duration; establishing behavior functions associated with a behavior of the vehicle including at least two of safest path, shortest path, quickest path, boldest path, and steadiest path as a function of at least one of the established decision variables, each behavior function giving a score indicating the desirability of engaging in the associated behavior; establishing weights of the established behavior functions to give weighted behavior functions; solving a summation of the weighted behavior functions while the vehicle is operating to determine the values of the decision variables giving the highest summation; and guiding the vehicle in accordance with the determined decision variable values.

11. The method of claim 10 wherein the vehicle is an unmanned underwater vehicle.

12. The method of claim 10 further comprising the step of obtaining environmental variables while the vehicle is operating, and at least one of said established behavior functions being dependent on said obtained environmental variables.

13. The method of claim 12 wherein the step of obtaining environmental variables includes detecting other vehicles and the established behavior functions are responsive to detected vehicles.

14. The method of claim 13 wherein the established behavior functions includes safest path.

15. The method of claim 14 wherein calculation of the safest path behavior function includes: determining the time of the closest point of approach between the vehicle and detected other vehicle; determining the closest point of approach between the vehicle and the detected other vehicle; and applying a utility metric to the closest point of approach distance to give the score for the safest path behavior function.

16. The method of claim 12 further comprising the step of obtaining previously recorded variables from a database while the vehicle is operating, and at least one of said established behavior functions being dependent on said previously recorded variables.

17. The method of claim 16 wherein said established behavior functions are piecewise defined functions, each behavior function being dependent on at least one of the established decision variables such that each behavior function corresponds to a goal, said behavior function being based on an underlying expression, each behavior function having a plurality of pieces, each piece relatable to an interior function having a piece maximum value, each behavior function having only one piece for each combination of decision variable values.

18. The method of claim 17 wherein said step of solving a summation further comprises searching through the decision variable values to find the values of the decision variables that maximize the summation of the weighted behavior functions.


ОПИСАНИЕ




ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ



(1) Field of the Invention

The invention relates to a vehicle control system for autonomously piloting a vehicle utilizing a multi-objective optimization method that evaluates a plurality of objective functions to determine the best decision variables satisfying those objectives.

(2) Description of the Prior Art

The mission assigned to an underwater vehicle strongly shapes the navigation complexity and criteria for success. While many problems are similar between commercial and military AUVs, there is a stronger emphasis in military vehicles in reasoning about other nearby moving vessels. Military AUVs (more commonly referred to as unmanned underwater vehicles (UUVs)) are typically designed to operate in congested coastal situations, where a near-collision or mere detection by another vessel can jeopardize the AUV. The scenario considered in this application therefore centers around the need to consider preferred relative positions to a moving contact, while simultaneously transiting to a destination as quickly and directly as possible. By "preferred relative position", we primarily mean collision avoidance, but use this term also in reference to other objectives related to relative position. These include the refinement of a solution on a detected contact, the avoidance of detection by another contact, and the achievement of an optimal tactical position should an engagement begin with the contact.

Other researchers have submitted material in the art of autonomous vehicle navigation.

Rosenblatt in "DAMN: A Distributed Architecture for Mobile Navigation," PhD thesis, Carnegie Mellon University, 1997 teaches the use of behavior functions voting on a single decision variable with limited variation. Multiple behavior functions provide votes for an action having five different possibilities. Additional control is provided by having a mode manager that dynamically adjusts the weights of the behavior functions. While Rosenblatt indicates that decision variables for turns and speed are desirable, coupling of these two decision variables into a single control system at the same time is not provided.

Riekki in "Reactive Task Execution of a Mobile Robot," PhD Thesis, University of Oulu, 1999, teaches action maps for each behavior that can be combined to guide a vehicle using multiple decision variables. Riekki discloses action maps for obstacle avoidance and velocity.

These publications fail to teach the use of multiple decision variables having large numbers of values. No method is taught for determining a course of action in real time from multiple behavior functions. Furthermore, these publications do not teach the use of action duration as a decision variable.


СУЩНОСТЬ ИЗОБРЕТЕНИЯ



This invention provides a method for autonomously controlling a vehicle. This includes comprising establishing decision variables for maneuvering the vehicle and behavior functions associated with the decision variables. The behavior functions give a score indicating the desirability of engaging in the associated behavior. The behavior functions are weighted. A summation of the weighted behavior functions is solved while the vehicle is operating to determine the values of the decision variables giving the highest summation of scores. In a preferred method, an optimal structure for the behavior functions and summation solution is taught. The vehicle is then guided in accordance with the determined decision variable values.


КРАТКОЕ ОПИСАНИЕ РИСУНКОВ



A more complete understanding of the invention and many of the attendant advantages thereto will be readily appreciated as the same becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings wherein:

FIG. 1 is a diagram of the basic vehicle navigation problem;

FIG. 2 is a flow chart of the vehicle navigation system;

FIG. 3 is a diagram showing the vehicle navigation problem applied to marine vehicles;

FIG. 4 is a diagram illustrating aspects of the closest point aspect of the shortest path behavior function; and

FIG. 5 is the algorithm for finding the shortest path.

DESCRIPTION OF THE PREFERRED EMBODIMENT

This invention sets up a control system for a vehicle 10 moving through time and space, where periodically, at fixed time intervals, a decision is made as to how to next control the vehicle. FIG. 1 shows the vehicle 10 traveling along a path 12 at times T.sub.m-1 to T.sub.m. Before expiration of the time interval between T.sub.m-1 and T.sub.m, vehicle 10 must decide its next course and speed. Some of the multiplicity of course choices are represented by dashed lines 14A, 14B and 14C.

The vehicle control loop 20 is shown as FIG. 2. At the start of the control loop 20, the vehicle receives environmental and database inputs as identified in step 22. This information is transferred to a plurality of behavior functions 24 that are set up as interval programming (IvP) functions for each individual behavior of the vehicle. Each behavior function 24 has access to the information in the environment from step 22 that is relevant in building its IvP function. Each IvP function is defined over a common decision space, where each decision precisely spells out the next action for the vehicle 10 to implement starting at time T.sub.m. The behavior functions 24 can be weighted to give preferences to certain behaviors. In step 26, the behavior functions are solved. Each iteration of this control loop involves the building interval programming functions in step 24 and solving this interval programming problem in step 26. Generic solution of an interval programming problem is discussed in U.S. patent application Ser. No. 10/631,527, A MULTI-OBJECTIVE OPTIMIZATION METHOD, which is incorporated by reference herein. Solution can be performed by formulating the problem as a summation of the weighted behavior functions. Solutions to the behavior functions are known, so the control system can find the optimal control variables by searching through the variables to find the maximum of this summation. This solution results in control variables for vehicle navigation. These control variables are assigned to the vehicle for navigation in step 28. The algorithm is then iterated in loop 30.

In the following text and as shown in FIG. 3, the environment, decision space, and behaviors are described for the application of this technology to marine vehicle navigation. The rationale for using the decision variables chosen here is also discussed. The information that composes the vehicle's relevant environment can be divided into the following four groups: a) bathymetry data, b) destination information, c) ownship position information, and d) contact position information. The bathymetry data represents an assumed map of the environment, telling us what is reachable from where, and at which depths. This includes land 40, ocean 42 and a destination 43. Destination 43 is simply given as latitude, longitude pair, d.sub.LAT, d.sub.LON. The vehicle of interest 44 is hereinafter referenced as ownship 44. The position information for ownship 44 is given by the terms as.sub.LAT and os.sub.LON. This is the expected vehicle 44 position at time T.sub.m, based on its position at time T.sub.m-1 and the choice of course 46 and speed executed at T.sub.m-1. Likewise, the position for a contact 48 is given by cn.sub.LAT and cn.sub.LON, based on the contact's observed course 50 and speed at time T.sub.m-1. In addition, the terms cn.sub.CRS and cn.sub.SPD indicate the expected course 52 and speed of the contact 48 at time T.sub.m, which is simply the previous course and speed.

During the time interval [T.sub.m-1; T.sub.m], the contact 48 is assumed to be on a straight linear track. The calculated ownship maneuver 54A, 54B or 54C would still be carried out regardless of a change in course or speed made by the contact 48 in this time interval. Should such a change occur, the new cn.sub.CRS and cn.sub.SPD would be noted, the next cn.sub.LAT and cn.sub.LON calculated, and the process of determining the maneuver at time T.sub.m+1 begun. The implementation of a tight control loop, and the willingness to repeatedly reconsider the next course of action, ensures that the vehicle 44 is able to quickly react to changes in its perceived environment.

In application to a marine vehicle, the following three decision variables are used to control the vehicle 44: x.sub.c=course, x.sub.s=speed, and x.sub.t=time. They are summarized, with their corresponding domains and resolutions in the Table, below.

TABLE-US-00001 Name Meaning Domain Resolution x.sub.c Ownship course starting at time T.sub.m [0; 359] 1 degree x.sub.s Ownship speed starting at time T.sub.m [0; 30] 1 knot x.sub.t Intended duration of the next [1; 90] 1 minute ownship leg

The selection of these three decision variables, and the omission of others, reflects a need to present both a sufficiently simple scenario here, as well as a sufficiently challenging motion planning problem. The omission of variables for controlling vehicle depth, for example, may seem strange since we are focusing on marine vehicles. However, the five objective functions focus on using the interval programming to solve the particularly challenging problem of shortest/quickest path navigation in the presence of moving obstacles.

Although reasoning about vehicle depth is critically important for successful autonomous undersea vehicle operation, none of the objective functions we implement here involve depth because of the added processing complexity. In the scenario described, it is assumed that the depth remains fixed at a preset level. The same holds true for other important control variables, namely the ones that control the rate of change in course, speed or depth. Again for the sake of simplicity, it is assumed that a course or speed change will take place at some reasonable rate. Alternatively, we can regard such maneuvers as happening instantaneously, and include the error that results from this erroneous assumption into general unpredictability of executing an action in a world with limited actuator precision. Certainly, the decision space will grow in size and complexity as more realistic scenarios are considered.

Even when limited to the three variables above, with their domains and resolutions, the decision space contains 360.times.31.times.90=1,004,400 elements. By comparison, none of the decision spaces considered by the prior art contained more than 1,000 elements, even if those decision spaces were composed as the Cartesian product of their variable domains. Future versions of this invention may consider depth, course change rate, speed change rate, and other decision variables.

Accordingly, this invention provides behaviors for: Safest Path, Shortest Path, Quickest Path, Boldest Path, and Steadiest Path. Other behaviors may be developed for this application taking into account other system information.

The objective of the safest path behavior is to prevent ownship 44 from coming dangerously close to a particular contact 48, and is defined over the three decision variables x.sub.c, x.sub.s, and x.sub.t. We describe how to build an IvP function, f.sub.IvP(x.sub.c; x.sub.s; x.sub.t), based on an underlying function, f.sub.CPA(x.sub.c; x.sub.s; x.sub.t). The latter function is based on the closest point of approach, (CPA), between the two vehicles during a maneuver, [x.sub.c; x.sub.s; x.sub.t], made by ownship 44. This function is calculated in a three step process: [1] Determine the point in time when the closest point of approach occurs, x'.sub.t. [2] Calculate the distance between vehicles at this time x'.sub.t. [3] Apply a utility metric to this distance.

After discussing how f.sub.CPA(x.sub.c; x.sub.s; x.sub.t) is calculated, the creation of f.sub.IvP(x.sub.c; x.sub.s; x.sub.t) from this function is discussed.

To calculate f.sub.CPA(x.sub.c; x.sub.s; x.sub.t), we first need to find the point in time, x'.sub.t, in the interval [0; x.sub.t], when the CPA occurs. To do this, we need expressions telling us where ownship 44 and the contact 48 are at any point in time, as well as an expression for their relative distance. Recall that at time, T.sub.m, ownship will be at a certain relative position to the contact, and after a particular maneuver, given by [x.sub.c; x.sub.s; x.sub.t], will be at a new point in the ocean and at a new relative position. For ownship, the new latitude and longitude position is given by: f.sub.LAT(x.sub.c;x.sub.s;x.sub.t)=(x.sub.s)(x.sub.t)cos(x.sub.c)+OS.sub.- LAT (1) f.sub.LON(x.sub.c;x.sub.s;x.sub.t)=(x.sub.s)(x.sub.t)sin(x.sub.c)- +OS.sub.LON (2) The resulting new contact position is similarly given by the following two functions: g.sub.LAT(x.sub.t)=cos(cn.sub.CRS)(cn.sub.SPD)(x.sub.t)+cn.sub.LAT (3) g.sub.LON(x.sub.t)=sin(cn.sub.CRS)(cn.sub.SPD)(x.sub.t)+cn.sub.LON (4) The latter two functions are defined only over x.sub.t since the contact's course and speed are assumed not to change from their values of cn.sub.CRS and cn.sub.SPD. Note these four functions ignore earth curvature. The distance between ownship and the contact, after a maneuver [x.sub.c; x.sub.s; x.sub.t] is expressed as: dist.sup.2(x.sub.c;x.sub.s;x.sub.t)=(f.sub.LAT(x.sub.c;x.sub.s;x.sub.t)-g- .sub.LAT(x.sub.t)).sup.2+(f.sub.LON(x.sub.c;x.sub.s;x.sub.t)-g.sub.LON(x.s- ub.t)).sup.2. (5) Barring the situation where the two vehicles are at identical course and speed, the CPA is at a unique minimum point in the above function. We find this stationary point by expanding this function, collecting like terms, and taking the first derivative with respect to x.sub.t, setting it to zero, and solving for x.sub.t. By expanding and collecting like terms we get: dist.sup.2(x.sub.c;x.sub.s;x.sub.t)=k.sub.2x.sub.t.sup.2+k.sub.1x.sub.t+k- .sub.0 (6) where k.sub.2=cos.sup.2(x.sub.c)x.sub.s.sup.2-2 cos(x.sub.c)x.sub.scos(cn.sub.CRS)cn.sub.SPD+cos.sup.2(cn.sub.CRS)cn.sub.- SPD.sup.2+sin.sup.2(x.sub.c)x.sub.s.sup.2-2 sin(x.sub.c)x.sub.ssin(cn.sub.CRS)cn.sub.SPD+sin.sup.2(cn.sub.CRS)cn.sub.- SPD.sup.2 k.sub.1=2 cos(x.sub.c)x.sub.sos.sub.LAT-2 cos(x.sub.c)x.sub.scn.sub.LAT-2os.sub.LATcos(cn.sub.CRS)cn.sub.SPD+2 cos(cn.sub.CRS)cn.sub.SPDcn.sub.LAT+2 sin(x.sub.c)x.sub.sos.sub.LON-2 sin(x.sub.c)x.sub.scn.sub.LON-2os.sub.LONsin(cn.sub.CRS)cn.sub.SPD+2 sin(cn.sub.CRS)cn.sub.SPDcn.sub.LON (7) k.sub.0=os.sub.LAT.sup.2-2os.sub.LATcn.sub.LAT+cn.sub.LAT.sup.2-2os.sub.L- ONcn.sub.LON+cn.sub.LON.sup.2 From this we have: diSt.sup.2(x.sub.c;x.sub.s;x.sub.t)'=2k.sub.2x.sub.t+k.sub.1. (8) We note that the distance between two objects cannot be negative, so the point in time, x.sub.t', when dist.sup.2(x.sub.c; x.sub.s; x.sub.t) is at its minimum is the same point where dist(x.sub.c; x.sub.s; x.sub.t) is at its minimum. Also, since there is no "maximum" distance between two objects, a point in time, x.sub.t', where 2k.sub.2x.sub.t+k.sub.1=0 must represent a minimum point in the function dist(x.sub.c; x.sub.s; x.sub.t). Therefore x.sub.t' is given by:

'.times. ##EQU00001## If x.sub.t'<0, meaning the closest point of approach occurred prior to the present, we set x.sub.t=0, and if x.sub.t'>x.sub.t, we set x.sub.t'=x.sub.t. When ownship and the contact have the same course and speed, i.e., x.sub.c=cn.sub.CRS and x.sub.s=cn.sub.SPD, then k.sub.1 and k.sub.2 equal zero, and x.sub.t' is set to zero, since their relative distance will not change during the time interval [0; x.sub.t].

Having identified the time, x.sub.t', at which the closest point of approach occurs, calculating this corresponding distance is a matter of applying the distance function, given above, to x.sub.t'. cpa(x.sub.c;x.sub.s;x.sub.t)=dist(x.sub.c;x.sub.s;x.sub.t'). (10) The actual objective function reflecting the safest-path behavior, f.sub.CPA(x.sub.c; x.sub.s; x.sub.t), depends on both the CPA value and a utility metric relating how good or bad particular CPA values are with respect to goals of the safest-path behavior. Thus f.sub.CPA(x.sub.c; x.sub.s; x.sub.t) will have the form: f.sub.CPA(x.sub.x;x.sub.s;x.sub.t)=metric(cpa(x.sub.c;x.sub.s;x.sub.t)). (11) We first consider the case where f.sub.CPA(x.sub.c; x.sub.5; x.sub.t) represents a "collision-avoidance" objective function. In a world with perfect knowledge and perfectly executed actions, a constraint-based approach to collision avoidance would be appropriate, resulting in metric.sub.a(d) below, where d is the CPA distance, and -M is a sufficiently large negative number acting as -1. Allowing for error, one could instead use

.function..times..times..times..times..times..times. ##EQU00002## or,

.function..times..times..times..times..ltoreq..times..times. ##EQU00003## use metric.sub.b(d) where maneuvers that result in CPA distances of less than 300 yards are treated as "collisions" to allow room for error, or a buffer zone.

Instead, we use a metric that recognizes that this collision safety zone is gray, or fuzzy. Under certain conditions, distances that would otherwise be avoided, may be allowed if the payoff in other goals is high enough. Of course, some distances remain intolerable under any circumstance. Having specified a function to compute the CPA distance and a utility metric based on the CPA distance, the specification of f.sub.CPA(x.sub.c; x.sub.s; x.sub.t) is complete. Based on this function, we then build the function f.sub.IVP(x.sub.c; x.sub.s; x.sub.t).

Now that f.sub.CPA(x.sub.c; x.sub.s; x.sub.t) has been defined, we wish to build a version of f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) that closely approximates this function. It is desirable to create as accurate a representation as possible, as quickly as possible, using as few pieces as possible. This in itself is a non-trivial multi-objective problem. Fortunately, fairly naive approaches to building this function appear to work well in practice, with additional room for doing much better given more thought and design effort. To begin with, we create a piecewise uniform version of f.sub.IVP(x.sub.c; x.sub.s; x.sub.t). This function gives a score for every possible course, x.sub.c; speed, x.sub.s; and duration, x.sub.t. The score gives a desirability of following these variables in view of potential collision with the contact.

The questions of acceptable accuracy, time, and piece-count are difficult to respond to with precise answers. The latter two issues of creation time and piece-count are tied to the tightness of the vehicle control loop. This makes it possible to work backward from the control loop requirements to bound the creation time and piece-count. However, the control loop time is also application dependent. The most difficult issue is knowing when the function f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) is an acceptably accurate representation of f.sub.CPA(x.sub.c; x.sub.s; x.sub.t). Although it is difficult to pinpoint, at some point the error introduced in approximating f.sub.CPA(x.sub.c; x.sub.s; x.sub.t) with f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) becomes overshadowed by the subjectivity involved in f.sub.CPA(x.sub.c; x.sub.s; x.sub.t).

Characteristics of different versions of f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) can be analyzed experimentally to note when poorer versions begin to adversely affect vehicle behavior. There is a trade off between the number of pieces in the piecewise function, the creation time, and the error associated therewith. With an increasing number of pieces, it has been found that there is a point of diminishing returns where additional pieces have a smaller return in reduced error. An ideal piece count cannot be formulated on each iteration of the control loop; however, enough analysis of the vehicle can allow choice of a piece-count that works sufficiently well in all situations.

The shortest path behavior is concerned with finding a path of minimal distance from the current position of the vehicle (os.sub.LAT; os.sub.LON) to a particular destination [d.sub.LAT; d.sub.LON].As with the previous behavior, the aim is to produce an IvP function f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) that not only indicates which next maneuver(s) are optimal with respect to the behavior's goals, but evaluates all possible maneuvers in this regard. The primary difference between this behavior and the previous behavior, is that here, f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) is piecewise defined over the latitude-longitude space rather than over the decision space. The function f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) as in other behaviors, is created during each iteration of the control loop, and must be created quickly. In the shortest path behavior, an intermediate function, spath(p.sub.LAT; p.sub.LON), is created once, off-line, for a particular destination, and gives the shortest-path distance to the destination given a point in the ocean, [p.sub.LAT; p.sub.LON]. The creation of spath(p.sub.LAT; p.sub.LON) is described below. This function in turn is built upon a third function, bathy(p.sub.LAT; p.sub.LON), which returns a depth value for a given point in the ocean, and is described below.

The function bathy(p.sub.LAT; p.sub.LON) is a piecewise constant function over the latitude-longitude space, where the value inside each piece represents the shallowest depth within that region. This function is formed in a manner similar to that taught by U.S. patent application Ser. No. 10/631,527, A MULTI-OBJECTIVE OPTIMIZATION METHOD which has been incorporated by reference herein. The "underlying" function in this case is a large file of bathymetry data, where each line is a triple: [p.sub.LAT; p.sub.LON; depth]. These bathymetry files can be obtained for any particular region of the ocean from the Naval Oceanographic Office Data Warehouse, with varying degrees of precision, i.e., density of data points.

The primary purpose of the bathy(p.sub.LAT; p.sub.LON) function is to provide a quick and convenient means for determining if one point in the ocean is directly reachable from another. Consider the example function, bathy(p.sub.LAT; p.sub.LON), which is an approximation of the bathymetry data. This data can be used in determining whether the proposed destination point is reachable from all points inside a current region, for a given depth. The function spath(p.sub.LAT; p.sub.LON) is built by using the function bathy(p.sub.LAT; p.sub.LON) and performing many of the above such queries. The accuracy in representing the underlying bathymetry data is enhanced by using finer latitude and longitude pieces. However, the query time is also increased with more pieces, since all pieces between the two points must be retrieved and tested against the query depth. Actually, just finding one that triggers an unreachable response is sufficient, but to answer that the destination is reachable, all must be tested.) The preferred function bathy(p.sub.LAT; p.sub.LON) uses a uniform piecewise function.

An equivalent non-uniform function can be constructed by combining neighboring pieces with similar values. Further consolidation can be done if a range of operating depth for the vehicle is known a priori. For example, if the vehicle will travel no deeper than 30 meters, then the function can be simplified, since pieces with depths of 30 and 45 meters are functionally equivalent when the vehicle is restricted to depths less than 30 meters.

The function spath(p.sub.LAT; p.sub.LON) is a piecewise linear function over the latitude-longitude space, where the value inside each piece represents the shortest path distance to the destination [d.sub.LAT; d.sub.LON], given a bathymetry function, bathy (p.sub.LAT; p.sub.LON), and a specific operating depth. On a basic level, this function only considers simple linear distance, but it is recognized that one of ordinary skill in the art would consider other factors, such as preferred depth, current flow, and proximity to obstacles with uncertainty in order to provide a more robust implementation. These factors are discussed in the prior art to John Reif and Zheng Sun, "Motion Planning in the Presence of Flows," Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS2001), pages 450-461, Brown University, Providence, R.I., August 2001. Volume 2125 of Lecture Notes in Computer Science.

In building spath(p.sub.LAT; p.sub.LON) for a particular destination and depth, the latitude-longitude space is divided into either free space, or obstacles, based on the bathy(p.sub.LAT; p.sub.LON) function. A simple case is shown below in FIG. 4. FIG. 4 provides a map 60 of latitude-longitude pieces. Pieces identified by the bathymetry function as being impassable are cross hatched as identified by piece 62. The destination is shown as "o" identified as 64. In the first stage of building spath (p.sub.LAT; p.sub.LON), all latitude-longitude pieces are identified such that all interior positions of the piece are reachable to the destination on a single direct linear path. In FIG. 4, these "direct-path" pieces are indicated by the empty pieces 66. The other pieces, such as the pieces identified as 68, are marked with .infin., since their distance to the destination 64 is initially unknown. Choosing these pieces to be uniform was done only for clarity in these examples. The pieces in spath (p.sub.LAT; p.sub.LON) and bathy (p.sub.LAT; p.sub.LON) are not required to be uniform, and the algorithm provided below is not dependent on uniform pieces.

After the first stage, there exists a "frontier" of pieces identified as 70, each having a directly-reachable neighbor 72 that has a known shortest-path distance. For these frontier pieces 70, one can at least improve the ".infin." distance by proceeding through its neighbor 72. But consider the case of the piece identified as 74, where a frontier piece has two such neighbors. Unless an effort is made to properly "orient" the frontier, unintended consequences may occur. Furthermore, even if the correct neighbor is chosen, we can often do better than simply proceeding through the neighbor. This section describes implementation of an all-sources shortest path algorithm. The only value we ultimately care about for each piece is the linear interior function indicating the shortest-path distance for a given interior position. However, the following intermediate terms are useful: dist(pc.sub.a, pc.sub.b)=Distance between center points of pc.sub.a and pc.sub.b. pc.sub.a.fwdarw.dist=Distance from the center point of pc.sub.a to the destination. pc.sub.a.fwdarw.waypt=The next waypoint for all points in pc.sub.a.

After the first stage of finding all directly reachable pieces 66, the value of pc.sub.a.fwdarw.waypt for such pieces is simply the coordinates of destination point 64, [d.sub.LAT; d.sub.LON], and NULL for all other pieces. By keeping the waypoint for each piece, we can reconstruct the actual path that the shortest-path distance is based upon. The basic algorithm is given in FIG. 5. Three subroutine calls are left un-expanded: setDirectPieces( ), sampleFrontier( ), and refine( ), on lines 0, 3, and 5. The basic idea of the while loop is to continue refining pieces on the frontier until a set amount (in this case 100) of successive refinements fail to exceed a fixed threshold of improvement.

The function sampleFrontier(amt) searches for pairs of neighboring pieces, [pc.sub.a, pc.sub.b], where one piece could improve its path by simply proceeding through its neighbor. The pairs of pieces are randomly chosen by picking points in the latitude-longitude space. The opportunity for improving pc.sub.a through its neighbor, pc.sub.b, is measured by: opp.sub.a=pc.sub.a.fwdarw.dist-(dist(pc.sub.a, pc.sub.b)+pc.sub.b.fwdarw.dist). Each pair of pieces is then placed in a fixed-length priority queue, where the maximum element is a (frontier) pair with the greatest opportunity for improvement. This queue will never be empty but will eventually contain only pairs with little or no opportunity for improvement. There is also no guarantee that the same pair is not in the queue twice.

After a certain amount of sampling is done, the maximum pair is popped from the queue as in line 4 in FIG. 5. The function refine(pc.sub.a, pc.sub.b) is then executed, returning the measure of improvement given by val. The counter, threshCount, is incremented if the improvement is insignificant, eventually triggering the exit from the while-loop. If the improvement in pc.sub.a is significant, it will likely create a good opportunity for improvement in other neighbors of pc.sub.a. These neighbors (pairs) are therefore evaluated and pushed into the priority queue. The refine(pc.sub.a, pc.sub.b) function should, at the very least, make the simple improvement of setting the pc.sub.a.fwdarw.waypt to an interior point in pc.sub.b, e.g. the center point, and the linear function inside pc.sub.a is set to represent the distance to this new way-point, plus the distance from that way-point to the destination. Other refinements can be made that search for shortcuts points along the path from pc.sub.b to its way-point. If such a point is found, it becomes the value of pc.sub.a.fwdarw.waypt, and the appropriate linear interior distance function is calculated. The value returned by refine(pc.sub.a, pc.sub.b) is the difference in pc.sub.a.fwdarw.dist before and after the function call.

In spath (p.sub.LAT; p.sub.LON), the shortest distance for each point is based on a particular set of waypoints composing the shortest path, so the next waypoint is stored with each point in latitude-longitude space. This forms a linked list from which a full set of waypoints can be reconstructed for any given start position.

Once the function spath(p.sub.LAT; p.sub.LON) has been created for a particular destination and depth, the function f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) for a given ownship position can be quickly created. Like bathy(p.sub.LAT; p.sub.LON) and spath(p.sub.LAT; p.sub.LON), this function is defined over the latitude-longitude space, but the function f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) is defined only over the points reachable within one maneuver. A distance radius is determined by the maximum values for x.sub.s and x.sub.t. The objective function, f.sub.IVP(x.sub.c; x.sub.s; x.sub.t), produced by this behavior ranks waypoints based on the additional distance, over the shortest-path distance, that would be incurred by traveling through them.

For each piece in f.sub.IVP(x.sub.c; x.sub.s; x.sub.t), the linear interior function represents a detour distance calculated using three components. The first two are linear functions in the piece representing the distance to the destination, and the distance to the current ownship position. The third component is simply the distance from the current ownship position to the destination, given by spath(OS.sub.LAT; OS.sub.LON). Thus, the linear function representing the detour distances for all points [x; y] in a given piece, is given by: (m.sub.1+m.sub.2)(x)+(n.sub.1+n.sub.2)(y)+b.sub.1+b.sub.2-spath(OS.sub.LA- T, OS.sub.LON). A utility metric is then applied to this result to both normalize the function f.sub.IVP(x.sub.c; x.sub.s; x.sub.t), and allow a nonlinear utility to be applied against a range of detour distances.

The objective functions built by the shortest path behavior may also reflect alternative paths that closely missed being the shortest, from a given position. For example, the shortest path from positions just south of an island to the destination just north of the island may proceed either east or west depending on the starting position. A north-south line of demarcation can be drawn that determines the direction of the shortest path. When ownship is nearly on this line, the resulting objective function, f.sub.IVP(x.sub.c; x.sub.s; x.sub.t), reflects both alternative paths. If the shortest path proceeds east around the island, positions north-west can still be ranked highly due to the alternative, near-shortest path even though these positions represent a significant detour from the true shortest path. The presence of alternatives is important when the behavior needs to cooperate with another behavior that may have a good reason for not proceeding east.

The three functions in this behavior are coordinated to allow repeated construction of f.sub.IVP(x.sub.c; x.sub.s; x.sub.t) very quickly, since it needs to be built and discarded on each iteration of the control loop.

The bathymetry data is assumed to be stable during the course of an operation. Thus the piecewise representation of this data, bathy(p.sub.LAT; p.sub.LON), is calculated once, off-line, and its creation is not subjected to real-time constraints. The function spath(p.sub.LAT; p.sub.LON) is stable as long as the destination and operating depth remain constant.

An implementation of spath(p.sub.LAT; p.sub.LON) having sufficient speed has been developed. Alternatively, storing previously calculated versions of spath(p.sub.LAT; p.sub.LON) for different depths or destinations is another viable option. The volatile function, f.sub.IVP(x.sub.c; x.sub.s; x.sub.t), can be calculated very quickly since so much of the work is contained in the underlying spath(p.sub.LAT; p.sub.LON) function. The relationship between these three functions results in the appearance that ownship is performing "dynamic replanning" in cases where the shortest path becomes blocked by another vessel. The result is a behavior that has a strong "reactive" aspect because it explicitly states all its preferred alternatives to its most preferred action. It also has a strong "planning" aspect since its action choices are based on a sequence of perhaps many actions.

In transiting from one place to another as quickly as possible, proceeding on the shortest path may not always result in the quickest path. If the shortest path is indeed available at all times to the vehicle, at the vehicle's top speed, then the shortest path will indeed be the quickest. Other issues, such as collision avoidance with other moving vehicles, may create situations where the vehicle may need to leave the shortest path to arrive at its destination in the shortest time possible.

Concerning the boldest path behavior, sometimes there is just no good decision or action to take. But this doesn't mean that some are not still better than others. By including time, x.sub.t, as a component of our action space, we leave open the possibility for a form of procrastination, or self-delusion. If the vehicle's situation is doomed to be less than favorable an hour into the future, no matter what, actions that have a time component of only a minute appear to be relatively good. By narrowing the window into the future, it is difficult to distinguish which initial actions may actually lead to a minimal amount of damage in the future. The boldest-path behavior therefore gives extra rating to actions that have a longer duration, i.e., higher values of x.sub.t. This is not to say that choosing an action of brief duration, followed by different one, can sometimes be advantageous.

Other relevant behavior functions and decision variables can be determined in view of the mission of the vehicle. These techniques could also be applied to commercial autonomous vehicles.

Although we seek the optimum (x.sub.c; x.sub.s; x.sub.t) at each iteration of the vehicle control loop, there is a certain utility in maintaining the vehicle's current course and speed. In practice, when ownship is turning or accelerating, it not only makes noise, but also destabilizes its sensors for a period, making changes in a contact's solution harder to detect. The steady-path behavior implements this preference to keeping a steady course and speed by adding an objective function ranking values of x.sub.c and x.sub.s higher when closer to ownship's current course and speed.

After choosing the behavior equations for the vehicle, these equations are converted to interval functions as taught by the method. The behavior functions are weighted and summed to give an interval programming problem. At each time interval, the vehicle solves the interval programming problem. This can be performed by searching through the behavior functions to determine optimal values of the functions. These optimal values give the best course of action for the vehicle. The vehicle then implements this action and proceeds to formulate the next interval programming problem.

In light of the above, it is therefore understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described.

* * * * *