DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Status of Claims
This Office Action is in response to the application filed on April 1, 2025. Claims 1-9 are pending. Claim 1 is independent.
Priority
Receipt is acknowledged of certified copies of papers submitted under 35 U.S.C. 119(a)-(d), which papers have been placed of record in the file.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on April 1, 2025 has been considered. The submission is in compliance with the provisions of 37 CFR 1.97. The Forms PTO-1449 are signed and attached hereto.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-9 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Yuanchang Liu et al., "Intelligent multi-task allocation and planning for multiple unmanned surface vehicles (USVs) using self-organising maps and fast marching method, September 2019, ScienceDirect.com, Volume 496m, Pages 180-197 (hereinafter “Liu”).
Claims 1-9 are rejected under 35 U.S.C. 102(a)(2) as being anticipated by Liu.
With respect to independent claim 1, Liu discloses receiving task information by a task allocator, wherein the task information comprises a task area, restricted area, parameters and state quantities of targets, and parameters and state quantities of unmanned surface vehicles (see Algorithms 2-5, page 186-190, Section 5 simulation results: (a) Task allocation without regard to energy and communication constraints: in this simulation, the core is to demonstrate how the SOM based task allocation algorithm can successfully allocate different tasks to a multi-USV system with the assumption been made that no energy or communication constraints will influence the multi-USV system. The updating process (or the training process) of the SOM neural network will be explicitly presented to reveal how the tasks are allocated in a balanced way. (b) Task allocation under energy and communication constraints: in this simulation, the primary aim is to test the algorithm’s capability in dealing with energy and communication constraints using the proposed coordinating scheme as well as the task prioritising strategy. Different energy and communication constraints will be adopted to demonstrate that the proposed algorithm is robust enough to provide an optimised solution under all conditions. (c) Multi-task allocation and path planning for multi-USV system: in this simulation, multi-task allocation (SOM based) and path planning (FMM based) algorithms are integrated together and tested to validate that multiple tasks can be effectively assigned to USVs teams consisting of different number of vessels and a safe trajectory can always be efficiently generated while each vessel is executing tasks.);
identify a set of unassigned targets Ta and a set of unmanned surface vehicles without assigned tasks Un through the parameters and state quantities of the targets and unmanned surface vehicles (see Algorithm 2, Section 3.2 pages 186-187: A priority list ( priority list ) will first be initialised of a size equal to the number of cities. Then, for each city, if the distance between the city and base station is less than the communication range, it is considered that a successful transmission can be established and retained and a maximum priority value (valuemax) will therefore be assigned to the denoted city. However, if such a distance is greater than the communication range, a minimum priority value (valuemin) is given to the city indicating that the USV is too far away to successfully broadcast the information to the base station. Such a priority list will be used in the task allocation algorithm (Algorithm 2) to ensure that only the tasks within the communication range will be regarded as valid and therefore be taken into account when updating the SOM as shown in Line 8 of Algorithm 2.);
assigning a corresponding target to each unmanned surface vehicle, comprising: calculating an adjusted distance d't1 from each target j to each unmanned surface vehicle i:d1=
PNG
media_image1.png
23
22
media_image1.png
Greyscale
+A
PNG
media_image1.png
23
22
media_image1.png
Greyscale
+D
PNG
media_image2.png
23
22
media_image2.png
Greyscale
wherein, dij is the Euclidean distance from the i-th unmanned surface vehicle to the j-th target, Δd11 is an adjustment term considering performance parameters of the unmanned surface vehicle for the distance, Ddg1 is a penalty term for the j-th target bypassing restricted area from the i- th unmanned surface vehicle (see pages 182-187, Sections 3.1 – 3.2, Equations (1), (11, (13) and (14));
constructing an adjusted distance matrix Dmxn between unmanned surface vehicles and targets by d'
PNG
media_image3.png
10
10
media_image3.png
Greyscale
, defining a
PNG
media_image4.png
10
6
media_image4.png
Greyscale
sub-matrix D', D'E Dmxn, D' comprising rows and columns corresponding to unassigned unmanned
PNG
media_image4.png
10
6
media_image4.png
Greyscale
surface vehicles u1 and targets t1, and matching the unassigned unmanned
PNG
media_image4.png
10
6
media_image4.png
Greyscale
surface vehicles u1 and targets t1 based on a minimum element in D' (see Figure 1, pages 182 – 183, Section 2.1, Equations (1) and (2));
wherein the unmanned
PNG
media_image4.png
10
6
media_image4.png
Greyscale
surface vehicle u1 belongs to the set of unmanned surface vehicles without assigned tasks Unn and the target t1 belongs to the set of unassigned targets Tan; a process for obtaining the penalty term for each target j bypassing restricted area from the unmanned surface vehicle i is: 1) dividing a straight-line path from the unmanned surface vehicle i to the target j into N segments, each segment having a length of
PNG
media_image5.png
20
10
media_image5.png
Greyscale
and endpoints of each segment being denoted as sampling points P0
PNG
media_image6.png
19
96
media_image6.png
Greyscale
PNG
media_image4.png
10
6
media_image4.png
Greyscale
; 2) determining whether a connecting line Pk~k+1 intersects with a boundary of a no-go zone Fm, and if intersecting, denoting a first intersection point and a last intersection point as ak
PNG
media_image7.png
11
13
media_image7.png
Greyscale
bk respectively, and deleting sampling points between ak
PNG
media_image8.png
10
43
media_image8.png
Greyscale
;
PNG
media_image9.png
9
8
media_image9.png
Greyscale
; 3) finding a point nk on the boundary of Fm that is closest to ak;
PNG
media_image10.png
10
8
media_image10.png
Greyscale
; 4) calculating a point afl obtained by extending from nk outwards along a normal vector direction away from a center point cm of Fm by a distance d;
PNG
media_image11.png
12
12
media_image11.png
Greyscale
; 5) starting from afl
PNG
media_image12.png
12
12
media_image12.png
Greyscale
, traversing boundary points of Fm outwards by a distance d in clockwise and counter-clockwise directions respectively to obtain points afl
PNG
media_image13.png
12
29
media_image13.png
Greyscale
, until a connecting line between a
PNG
media_image14.png
35
40
media_image14.png
Greyscale
and bk does not intersect with Fm, and recording path lengths in clockwise and counter-clo se directions Le,Lee, respectively; 6) selecting a smaller value from Le, and Lee,, and denoting it as Lk; 7) adding path points bypassing Fm, i.e., points in Lk, between the sampling points ak, bk, and repeating steps 2. to 6. to process subsequent restricted area Fm+i; 8) finally obtaining a sampling point sequence P as a path bypassing all Fm, and a length thereof being 2;
PNG
media_image15.png
27
22
media_image15.png
Greyscale
; 9) for the sampling point sequence P, calculating a turning angle Bk between each adjacent sampling line segment PkPk+1 and Pk+1Pk+2; 10) calculating a path turning penalty term: Do=2,ok being a turning penalty parameter;
PNG
media_image16.png
31
108
media_image16.png
Greyscale
; 11) the penalty term 2di for each target j bypassing restricted area from the unmanned surface vehicle i is: 2dij=2
PNG
media_image17.png
26
84
media_image17.png
Greyscale
(see Equations (11) and (12; Algorithm 4, Section 3.1 and 4.1 pages 186-189);
for the matched unmanned surface vehicles and corresponding targets, calculating to obtain a waypoint sequence Pi1 bypassing restricted area from the unmanned surface vehicle u, to the target t1, and interpolating Pi1 to generate a new waypoint sequence P'
PNG
media_image18.png
10
17
media_image18.png
Greyscale
using the sequence P'i; as a navigation waypoint sequence from the unmanned surface vehicle u to the target ti, and sending and storing it in a navigation system of a corresponding unmanned surface vehicle (see pages 188-189, Section 4 and 4.1; Algorithms 3 and 4: After each USV has been allocated its own set of tasks based upon the particular vessel’s energy storage and communication capability, the next step is to make sure that each USV is able to execute these tasks by visiting them in sequence and to the most extent, appreciate the navigational safety and avoid any potential collision en route. To achieve this, path planning functionality will be called to generate feasible trajectory for each USV. Similar to work in Liu and Bucknall [18], the trajectory has been calculated on the basis that the minimum distance cost should be maintained, i.e. the straight line between two points should be considered as an ideal candidate if the line does not violate any obstacle area. With the existence of obstacles, the ideal path (the straight line) should be accordingly and appropriately modified such that collision risks can be eliminated.);
inputting parameters and state quantities of the unmanned surface vehicle
PNG
media_image19.png
15
22
media_image19.png
Greyscale
an obstacle set Obs, restricted area Fm, a task area L, and an expected velocity vector Vdes of the unmanned surface vehicle u, to its next waypoint PiEP'; into an optimizer, and solving to obtain a velocity control quantity; using the velocity control quantity to drive the unmanned surface vehicle u to travel towards the target waypoint Pi, and after reaching the waypoint, deleting Pi from the waypoint sequence P'ij until reaching a last waypoint in the waypoint sequence P
PNG
media_image20.png
26
33
media_image20.png
Greyscale
.e., reaching a task area of the target t1, and after performing a task, adding the unmanned surface vehicle u, to Uu again, and restarting step 2. until all tasks are completed (see Algorithm 4, Section 4.1 page 189: Based on V, the FMM is executed to calculate an arrival time matrix TFMM, and upon the time matrix TFMM, the optimal path is finally searched by applying the gradient descent method from the end point to the start point. Further explanation of FMM based path planning can be referred to in Garrido et al. [13]).
With respect to dependent claim 2, Liu discloses The method for target assignment and route planning for multi-agent unmanned surface vehicles according to claim 1, characterized in that, the adjustment term considering performance parameters of the unmanned surface vehicle for the distance is calculated according to the following formula:
PNG
media_image21.png
55
354
media_image21.png
Greyscale
|wherein, vi is a velocity vector of the i-th unmanned surface vehicle, 0, is a direction of the velocity vector, V is a maximum speed, co is a maximum turning rate, Ogj is an azimuth angle from the i-th unmanned surface vehicle pointing to the j-th target, oi,c2 are weighting coefficients (see page 187 and equations (13) and (14): As regards optimising energy consumption of multi-USV systems when allocating multiple tasks, this has been achieved by implementing a new coordinate updating scheme as shown in Line 7 in Algorithm 1. A new winner selection scheme is proposed using the equation: . . . where dCW is the Euclidean distance between the city and the neuron on ith ring is the length of the ith ring, and lengthave is the average length of all the rings. σenergy is the energy adjustment parameter, which is used to ensure that winning neuron will be selected from the longest ring. Such a scheme has been established based upon the fact that if the USV is fuelled with sufficient energy, the vessel will be able to navigate a longer route and execute more tasks. Therefore, when updating the SOM, σenergy is determined inversely proportional to the equipped energy storage onboard. For example, a smaller σenergy value will be assigned to the ring that belongs to the USV having larger energy storage such that winner neuron can be more frequently selected from this ring and subsequently the updating process for other rings will be restricted.).
With respect to dependent claim 3, Liu discloses characterized in that, interpolating Pi1 to generate a new waypoint sequence P'i1 specifically adopts the following method:
1) constructing a cubic B-spline curve C(u) by using Pi1 as a control point sequence;
2) defining a turning energy function Eb-fC2(u) du, representing turning energy;
3) defining a route length function El= f IC(u) du, representing route length;
4) constructing an objective function E =wiEb + w2E1 , wherein w1, w2 are weighting coefficients;
5) minimizing the objective function by adjusting w1, w2 values to obtain a smooth curve C* (u);
6) sampling the C* (u) curve to generate a new waypoint sequence Pety;
7) deleting points in the new waypoint sequence Peti that are within restricted area or in a task area to obtain the sequence P'ij.
(See page 183 and page 189, Section 4.1: Cai et al. [4] proposed to use the genetic algorithm to solve the multi-task allocation problem for a swarm of AUVs in a three dimensional (3D) underwater environment. The nonholonomic motion constraints of AUVs were specifically addressed by using interpolated 3D Dubin's curves that were compliant with vehicles’ dynamic characteristics. By observing the results in Fig. 3, it can be summarised that paths generated by conventional algorithms such as RRT and A∗ (in Fig. 3(c) and 3(d)) normally consist of several segments making them non-continuous. Hence, additional path smoothers are necessary to be applied to increase the continuity. The FMM algorithm is able to provide the path with improved continuity and smoothness (in Fig. 3(a)). In addition, as stated in Garrido et al. [13], two more additional benefits can be provided by FMM based path planning algorithm: • Completeness: some path planning algorithms developed using the evolutionary searching algorithm (genetic algorithm, ant colony algorithm and etc.) suffer from the problem of searching incompleteness, which means the algorithm may fail to find a path in a complex environment. The algorithm developed based upon the FMM adopts a deterministic searching scheme ensuring a path can always be found as long as it exists. • Fast computation time: the FMM algorithm is fast in dealing with the searching problem due to its low computation complexity. For a grid map having total grid number of N, the time complexity is O(Nlog(N)) [13]. Such a feature is especially useful for practical path planning, where a fast decision making process is preferred.).
With respect to dependent claim 4, Liu discloses characterized in that, an objective function of the optimizer is: J(v)=IVdes -VI2 + Cpenalty (V) wherein, v is an optimization variable, Cpenalty is a penalty term. (See Algorithm 4 and page 187: The proposed multi-task allocation algorithm can specifically address the issues of limited energy consumption and constrained communication range, which are two main constraints for USVs operation in maritime environment and have not been properly considered in other works such as Faigl [8] and Best et al. [2]. Also, because of the implementation of the improved SOM as the base algorithm, compared with the algorithm in Faigl [8], the proposed algorithm has the feature of fast computational time, which makes the algorithm more suitable in large scale application where a USV swarm is deployed to conduct a large number of missions [18].).
With respect to dependent claim 5, Liu discloses characterized in that, constraint conditions constructed by the optimizer are: c1:lvi;V, ensuring that a speed is less than a maximum speed Vi;C2: PnextV Fm, ensuring that a future position is not within restricted area Fm; C3: PnextE L, ensuring that a future position is within a task area L;wherein, Pnext=Pi + v - dt is a next moment position calculated according to a velocity control quantity v. (see page 188-191, Section 4.1: The FMM based path planning algorithm is described in Algorithm 3. Consider the planning space (M), to which the algorithm is to be applied, has a representation of a binary map and is perfectly rasterised. The algorithm first reads in M and calculates its according speed matrix (V). The speed matrix (V) has the same size as M and defines the interface propagation speed at each point in M. Based on V, the FMM is executed to calculate an arrival time matrix TFMM, and upon the time matrix TFMM, the optimal path is finally searched by applying the gradient descent method from the end point to the start point. Further explanation of FMM based path planning can be referred to in Garrido et al. [13]. Task allocation without regard to energy and communication constraints: in this simulation, the core is to demonstrate how the SOM based task allocation algorithm can successfully allocate different tasks to a multi-USV system with the assumption been made that no energy or communication constraints will influence the multi-USV system. The updating process (or the training process) of the SOM neural network will be explicitly presented to reveal how the tasks are allocated in a balanced way.).
With respect to dependent claim 6, Liu discloses characterized in that, solving for a velocity control quantity v* that minimizes the objective function J(v):
PNG
media_image22.png
29
52
media_image22.png
Greyscale
v) s.t. C1,C2, c3using the solved v* as the velocity control quantity. (See page 10: the FMM algorithm is able to provide the path with improved continuity and smoothness (in Fig. 3(a)). In addition, as stated in Garrido et al. [13], two more additional benefits can be provided by FMM based path planning algorithm:
• Completeness: some path planning algorithms developed using the evolutionary searching algorithm (genetic algorithm, ant colony algorithm and etc.) suffer from the problem of searching incompleteness, which means the algorithm may fail to find a path in a complex environment. The algorithm developed based upon the FMM adopts a deterministic searching scheme ensuring a path can always be found as long as it exists).
With respect to dependent claim 7, Liu discloses characterized in that, in each time step dt of solving by the optimizer, for each unmanned surface vehicle checking whether there are other unmanned surface vehicles u or targets tk within a search radius, and if yes, adding the other unmanned surface vehicles u or targets tk to an obstacle set Obs.
PNG
media_image23.png
15
22
media_image23.png
Greyscale
(See page 188: Paths provided by the first step can be used as the off-line trajectories for the multi-USV system, and while each USV starts to track its individual path, some obstacles still require further path refinement to reduce collision risks. These collision risks could be the result of either already known obstacles where the connection between two missions may still pass through, or by some newly emerged obstacles that are detected by the vessel during the navigation.).
With respect to dependent claim 8, Liu discloses characterized in that, the parameters and state quantities of the unmanned surface vehicles comprise a unique identifier, a maximum speed, a turning rate, a search radius, whether a task has been assigned, a current position, and a current velocity vector; the parameters and state quantities of the targets comprise a unique identifier, whether it has been assigned, a work area radius, and a current position. (See Algorithm 2 and page 186: The improved SOM algorithm inherits the key structure of the conventional SOM with the main change being the adoption of a new updating equation to find the winner neuro when the network is being updated. As a consequence, the computational complexity of the improved SOM algorithm is the same to the conventional one, which in general is O(tf(dn + qn2)), where n is the number of neurons in a SOM, and each neuro is q-dimensional, the input data are D-dimensional and tf is the learning steps [15]. Note that in this research because multi-USV systems are assumed to be operating in a two-dimensional (2D) environment, q and d both equal to 2, and tf should be configured according specific application and in this paper, it is set up to be 1000 to give an optimised convergence rate. Based upon the improved SOM, an algorithm can now be designed to solve the multi-task allocation problem for multiUSV systems. As mentioned earlier, issues of energy consumption and communication range are the two main fundamental constraints that restrict the operation of USVs in wide range deployments. To effectively tackle these problems, two additional novel improvements have been designed and implemented in the algorithm with the pseudocode shown at Algorithm 2.).
With respect to dependent claim 9, Liu discloses characterized in that, the task area is a convex polygon defined by a plurality of two-dimensional coordinates meeting a WSG84 standard; and the restricted area are convex polygons defined by a plurality of two-dimensional coordinates meeting the WSG84 standard (see page 183: To solve the TSP based task allocation problem for autonomous vehicles, a series of works carried out by Faigl [5], Faigl et al. [6], Faigl [7] and Faigl [8] are representative. The main contribution derived from these studies is the adapting of a distance measurement metric that is used within the SOM updating process to make the SOM more suitable for autonomous vehicle applications, especially for solving the collision avoidance problem during navigation. See page 190: Algorithms have been coded in Matlab and simulations are run on the computer with a Pentium i7 3.4 GHz processor and 8 GB of RAM. A practical area, shown in Fig. 4, has been used as the simulation environment, and has been converted to a 500 pixels ∗ 500 pixels binary map that can be read and further processed by the algorithm.).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DEMETRA R SMITH-STEWART whose telephone number is (571)270-3965. The examiner can normally be reached 10am - 6pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Peter Nolan can be reached at 571-270-7016. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/DEMETRA R SMITH-STEWART/Examiner, Art Unit 3661
/PETER D NOLAN/Supervisory Patent Examiner, Art Unit 3661