COVERAGE PATH PLANNING METHOD FOR MULTIPLE UNMANNED SURFACE MAPPING VEHICLES

Abstract

Disclosed is a coverage path planning method for multiple unmanned surface mapping vehicles, comprising: simultaneously creating submaps and an overall map; outputting its own position information and obstacle information, transmitting to BL.sub.l.sup.i and updating BL.sub.l.sup.m; defining a behavior strategy list (BS); determining the BS with priority for path planning, outputting a to or th state if any criterion is satisfied; when trapped in a local optimum, updating map layers layer-by-layer going upwards, searching for tp in the corresponding layers, performing a BS determination, and outputting a tr instruction; if no target point is found even at the highest layer, checking each CS.sub.P.sub.i∈{FN.sub.i,UFN.sub.i}, and determining a termination. As such, the coverage rate and coverage effect of multiple unmanned surface mapping vehicles in a complex environment can be increased, thus increasing the operational efficiency of the unmanned surface mapping vehicles.

Claims

1. A coverage path planning method for multiple unmanned surface mapping vehicles, comprising: (1) importing a static map in an initialization stage, initializing grid state according to the static map, creating submaps and an overall map synchronously, and conducting area division on the submaps and the overall map based on task performance; where, the static map is used to reflect the environmental information, the submaps represents area map formed after the gridded static map is divided into areas using CCIBA* algorithm, and the overall map represents integration and iteration of the submaps; (2) according to USMV.sub.i of each sub-area P.sub.i in the submaps BL.sub.l.sup.i and the overall map BL.sub.l.sup.m, outputting its own position information co and obstacle information transmitting to BL.sub.l.sup.i and updating BL.sub.l.sup.m, and then path planning is carried out to find a target point tp; (3) when trapped in a local optimum, map level is updated layer by layer upward, and the target point tp is found in a corresponding level, and a BS determination is conducted, and sending tr instruction to the USMV.sub.i of the sub-area Pi, where, the BS determination represents the collaborative behavior strategy determination, tp represents grid index value of a next target point of USMV, and tr instruction indicates that the USMV is in the Travel state, which is the abnormal task status after the local optimum is reached; (4) if the target point has not yet been found in the highest map level, checking each CS.sub.P.sub.i∈{FN.sub.i,UFN.sub.i}, and the BS determination is over, where CS.sub.P.sub.i represents the status of the regional depth sounding task in current sub-area where USMV.sub.i is located, FN.sub.i represents complete, and UFN.sub.i represents incomplete.

2. The coverage path planning method for multiple unmanned surface mapping vehicles according to claim 1, step S101 comprises: At the beginning, each unmanned surface mapping vehicle is in a default starting position with a status of O; coordinate transformation grid index of the static map is established; grid status update is carried out in each submaps, and 0˜L level assignment of all maps is updated in turn; the USMV.sub.i outputs the tn instruction; at the same time, the USMV.sub.i records and transmits its own position ω and obstacle information each USMV.sub.i starts to independently update its own grid status list GT_list and start collaborative coverage task, where tn means to guide the USMV in a normal state, so that it performs normal coverage tasks in the subarea.

3. The coverage path planning method for multiple unmanned surface mapping vehicles according to claim 1, defining a list of behavior strategies: BS∈{ex1, ex2, ex3, ex4}, ex1, ex2, ex3, ex4 correspond to four situations of area segmentation, backtracking transfer, area exchange, and joint recognition of obstacles in collaborative behavior strategies.

4. The coverage path planning method for multiple unmanned surface mapping vehicles according to claim 3, path planning gives priority to the BS determination, and outputting te or th status if any situation is met, and outputting tp.sub.m based on BL.sub.l.sup.m planning if cross-area is involved; if it does not comply with any of the conditions of BS, a path planning will be performed independently and tn or tc status will be output, where tp.sub.m represents grid index value of location of next target point of the USMV in the overall map, tn means to guide the USMV to be in Normal status, tc means to guide the USMV to start depth sounding task, te indicates to guide the USMV to start switching areas and coordinate the coverage tasks between areas; th means to guide the USMV to continue to cover tasks in new areas.

5. The coverage path planning method for multiple unmanned surface mapping vehicles according to claim 1, conducting area division on the submaps and the overall map based on task performance, comprising: (1) setting up multiple USMV sets, U={USMV.sub.i|1≤i≤I}, I represents the number of USMVs, and core goal of collaborative coverage is to enable i USMVs to fully traverse the entire task area P under premise of full efficiency; (2) according to performance of the USMV.sub.i individual or ability to perform coverage tasks, the task performance index Hi (i=1, . . . , I) is proposed, which depends on sensor performance, task function, and energy consumption limit carried by the USMV, and $\underset{i=1}{\overset{I}{.Math.}}{H}_i=1;$ (3) an overall task area P is divided into I parts according to number of USMVs, where each part corresponds to area where the USMV is located, and each part is expressed by its percentage of area, where each part is expressed as P.sub.i, i=1, . . . , 0<P.sub.i<1, and $\underset{i=1}{\overset{I}{.Math.}}{P}_i=1;$ (4) each grid α in the free space P.sub.F of the overall task area P is specified and scanned by at least one USMV.sub.i: $Y\left(\alpha ,i\right)=\{\begin{array}{cc}1,& {\mathrm{BV}}_{\alpha }^i\left(t\right)\le 0\\ 0,& \mathrm{else}\end{array}$ ${.Math.}_{{\mathrm{USMV}}_i\in U}Y\left(\alpha ,i\right)\ge 1,\forall \alpha \in P_F$ where, the free space is determined by 0<Pi<1 and $\underset{i=1}{\overset{I}{.Math.}}{P}_i=1,$ and Y(α,i) represents the grid restriction, BV.sub.α.sup.i(t) represents the grid α assignment at time t in the BL-level map; (5) for collaborative coverage of multiple unmanned surface mapping vehicles, the following factors are considered: overall coverage path, overall coverage time, single coverage performance, and overall coverage rate; firstly, d.sub.cost and t.sub.cost of an initial task area are estimated according to performance index H.sub.i of USMV where d.sub.cost represents coverage path, t.sub.cost represents coverage time, d.sub.cost is further modified according to distribution of obstacles, and t.sub.cost is adjusted considering the equipment carried by USMV, and redistributed sub-areas is finally output, where: $\min \phi =k_1.Math.\underset{i=1}{\overset{I}{.Math.}}{P}_i\left(d_{\mathrm{cost}}\right)+k_2.Math.\underset{i}{\max }{P}_i\left(t_{\mathrm{cost}}\right)$ $S.T.\{\begin{array}{c}\underset{i=1}{\overset{I}{.Math.}}{P}_i=1\\ k_1+k_2+1\\ {.Math.}_{{\mathrm{USMV}}_i\in U}Y\left(\alpha ,i\right)\ge 1,\forall \alpha \in P_F\end{array}$ where φ represents overall cost model of coverage of multiple unmanned surface mapping vehicles, k.sub.1 represents cost coefficient of coverage path, k.sub.2 represents the cost coefficient of coverage time, P.sub.i(d.sub.cost) represents estimated coverage path of P.sub.i region, P.sub.i(t.sub.cost) represents estimated coverage time of P.sub.i region.

6. The coverage path planning method for multiple unmanned surface mapping vehicles according to claim 1, wherein step (2) comprises: in the BL.sub.0.sup.m level map stage, potential energy priority is assigned to each submap row by row to ensure complete coverage path of USMV.sub.i in each submap; if BV.sub.ω>0 and {ω.sup.N,ω.sup.S}⊂F.sup.0, it is consistent with the IBA* algorithm action of single USMV, and relative optimal path is selected by calculating potential generation value J(tp); similarly, if one side of ω.sup.N and ω.sup.S is close to the obstacle, it is preferred to select this direction, and obstacle avoidance path of each interval P.sub.i is completed through this action, and ex4 process is started; ω represents number of grid sequences at the current position of USMV, and BV refers to assignment of number of grid sequences ω in BL highest-level map; the detection field of USMV in grid map is recorded as D.sup.0(ω), ω∈D.sup.0(ω), D.sup.0(ω) contains all grid information that can be sensed by the current position of the USMV; for any grid α.sub.0 in D.sup.0(ω), if the connection with ω does not pass through fz or obs state grid, and its potential energy value is positive, the set is defined as the priority field F.sup.0.Math.D.sup.0(μ), and the grids in the north and south directions in D.sup.0(ω) are defined as ω.sup.N and ω.sup.S; if BV.sub.ω>0, and only one side of ω.sup.N and cos is ω.sup.S status and the other side is forbidden area, then opening the tc instruction to guide the USMV.sub.i to start the depth sounding task, and updating BL.sub.l.sup.i and BL.sub.i.sup.m at the same time; if BV.sub.ω=0, F.sup.0≠Ø, then USMV.sub.i begins to move to the next stage of traversal, taking α.sub.0 with the largest BV.sub.α.sub.0 value in F.sup.0 as the tp point, and α.sub.0 represents grid index; if the above situations are inconsistent, it is determined that USMV.sub.i is in a locally optimal status at this time; before upgrading map level, BS determination is performed; if collaborative strategy is met, the preset action is started, the to instruction is output and the submaps are updated, and the sub-area P.sub.i is redistributed; if it does not conform to any of the situations in BS, it opens high BL level map stage to start routing and outputs the tr instruction.

7. The coverage path planning method for multiple unmanned surface mapping vehicles according to claim 6, wherein step (3) comprises: in the BL.sub.l.sup.m level map stage, the map level is improved step by step, and the map grid with the largest potential energy value is continued to be found in the high-level map; at the same time, its potential value J(tp) is calculated and the optimal tp point is selected; in the process of USMV.sub.i escaping local optimum, it still participates in BS determination in real time, and continues to evaluate the priority of independent coverage and collaborative partition.

8. The coverage path planning method for multiple unmanned surface mapping vehicles according to claim 7, wherein step (4) comprises: according to CS.sub.P.sub.i∈{FN.sub.i,UFN.sub.i}, when the USMV.sub.i of all sub-area P.sub.i is transmitted back to FN.sub.i, it is determined that the entire task area P coverage task is over; through all environmental information detected, missing area is reviewed to generate coverage information.

9. A computer-readable storage medium on which a computer program is stored, wherein the steps of the method described in claim 1 are realized when the computer program is executed by a processor.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] Accompanying drawings are for providing further understanding of embodiments of the disclosure. The drawings form a part of the disclosure and are for illustrating the principle of the embodiments of the disclosure along with the literal description. Apparently, the drawings in the description below are merely some embodiments of the disclosure, a person skilled in the art can obtain other drawings according to these drawings without creative efforts. In the figures:

[0012] FIG. 1 is a flow diagram of coverage path planning method for multiple unmanned surface mapping vehicles provided by an embodiment of this disclosure.

[0013] FIG. 2 is another flow diagram of coverage path planning method for multiple unmanned surface mapping vehicles provided by an embodiment of this disclosure.

[0014] FIG. 3(a) is a typical behavior strategy diagram of area division provided by an embodiment of this disclosure;

[0015] FIG. 3(b) is a typical behavior strategy diagram of recall and transfer provided by an embodiment of this disclosure;

[0016] FIG. 3(c) is a typical behavior strategy diagram of area exchange provided by an embodiment of this disclosure;

[0017] FIG. 3(d) is a typical behavior strategy diagram of recognizing obstacles provided by an embodiment of this disclosure;

[0018] FIG. 4 is a USMV.sub.i task decomposition flow chart provided by an embodiment of this disclosure.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

[0019] The technical solutions in the embodiments of the application will be described clearly and completely in combination with the drawings in the embodiments of the application.

[0020] The purpose of this disclosure is to provide a coverage path planning method for multiple unmanned surface mapping vehicles (CCIBA*). CCIBA* algorithm is an extension of IBA* (Improved BA*). Both CCIBA* and IBA* are improvements on the traditional BA* algorithm to improve the coverage rate and coverage effect of unmanned surface mapping vehicles under complex operation environment and improve the operation efficiency of unmanned surface mapping vehicles. In order to make the above purposes, features, and advantages of this disclosure more understandable, this disclosure will be further described in detail with the attached drawings and specific implementation methods.

[0021] As shown in FIG. 1, the flow diagram of a coverage path planning method for multiple unmanned surface mapping vehicles (CCIBA*) provided by this disclosure comprises: O stage, BL.sub.0.sup.m level map stage, BL.sub.l.sup.m level map stage, and E stage.

[0022] According to the above four stages, CCIBA* is divided into two processes: offline planning process and online planning process.

[0023] According to the offline planning process, sub-regions are divided based on task performance, and four typical collaborative behavior strategies are established, including area segmentation, backtracking transfer, area exchange and joint recognition of obstacles.

[0024] The online planning process specifically comprises task decomposition of scanning scenario and map update of scanning scenario.

[0025] Specifically, FIG. 2 shows the flow diagram of another coverage path planning method for multiple unmanned surface mapping vehicles provided by an embodiment of this disclosure, comprising the following steps:

[0026] S101: O stage: importing a static map in an initialization stage, initializing grid state according to the static map, creating submaps and an overall map synchronously, and conducting area division on the submaps and the overall map based on task performance;

[0027] where, the static map is used to reflect the environmental information, that is, the navigation map of the unmanned surface mapping vehicles (nautical chart or river chart). The submaps and the overall map all reflect the navigation environment information of the unmanned surface mapping vehicles. Submaps represents the area map formed after the gridded static map is divided into areas using CCIBA* algorithm, and overall map represents the integration and iteration of submaps.

[0028] In this disclosure, conducting area division on the submaps and the overall map based on task performance, comprising:

[0029] (1) multiple unmanned surface mapping vehicles: setting up multiple USMV sets, U={USMV.sub.i|1≤i≤I}, I represents the number of USMVs, and the core goal of collaborative coverage is to enable i USMVs to fully traverse the entire task area P under the premise of full efficiency;

[0030] (2) task performance: according to the performance of the USMV individual or the ability to perform coverage tasks, the task performance index Hi (i=1, . . . , I) is proposed, which depends on sensor performance, task function, and energy consumption limit carried by the USMV, and

[00001]$\underset{i=1}{\overset{I}{.Math.}}{H}_i=1;$

[0031] (3) area division: an overall task area P is divided into I parts according to the number of USMVs, where each part corresponds to the area where the USMV is located, and each part is expressed by its percentage of area, where each part is expressed as P.sub.i, i=1, . . . , 0<P.sub.i<1, and

[00002]$\underset{i=1}{\overset{I}{.Math.}}{P}_i=1;$

[0032] (4) grid restriction: each grid α in the free space P.sub.F of the overall task area P is specified and scanned by at least one USMV.sub.i:

[00003]$Y\left(\alpha ,i\right)=\{\begin{array}{cc}1,& {\mathrm{BV}}_{\alpha }^i\left(t\right)\le 0\\ 0,& \mathrm{else}\end{array}$${.Math.}_{{\mathrm{USMV}}_i\in U}Y\left(\alpha ,i\right)\ge 1,\forall \alpha \in P_F$

[0033] where, the free space is determined by 0<Pi<1 and

[00004]$\underset{i=1}{\overset{I}{.Math.}}{P}_i=1,$

and Y(α,i) represents the grid restriction, BV.sub.α.sup.i(t) represents the grid a assignment at time t in the BL-level map.

[00005]${\mathrm{BV}}_{{\alpha }_0}\left(t\right)=\{\begin{array}{cc}-1,& {\mathrm{GT}}_{{\alpha }_0\left(t\right)}=\mathrm{obs}\mathrm{or}\mathrm{fz}\\ 0,& {\mathrm{GT}}_{{\alpha }_0\left(t\right)}=\exp \\ {\epsilon }_{{\alpha }_0},& {\mathrm{GT}}_{{\alpha }_0\left(t\right)}=\mathrm{ue}\end{array},$

[0034] For example,

[0035] Where BV.sub.α.sub.0(t) represents grid α.sub.0 assignment at time tin the BL.sub.0 level map;

[0036] GT.sub.α.sub.0(t) represents grid α.sub.0 status at time tin the BL.sub.0 level map; ε.sub.α.sub.0 represents the potential energy distribution formula; obs represents an obstacle; fz represents forbidden zone; exp represents the free space of the depth sounding mission completed; ue represents the free space of the depth sounding mission not completed.

[0037] (5) Planning objectives: for collaborative coverage of multiple unmanned surface mapping vehicles, the following factors are considered: overall coverage path, overall coverage time, single coverage performance and overall coverage rate:

[00006]$\min \phi =k_1.Math.\underset{i=1}{\overset{I}{.Math.}}{P}_i\left(d_{\mathrm{cost}}\right)+k_2.Math.\underset{i}{\max }{P}_i\left(t_{\mathrm{cost}}\right)$$S.T.\{\begin{array}{c}\underset{i=1}{\overset{I}{.Math.}}{P}_i=1\\ k_1+k_2+1\\ {.Math.}_{{\mathrm{USMV}}_i\in U}Y\left(\alpha ,i\right)\ge 1,\forall \alpha \in P_F\end{array}$

[0038] where φ represents overall cost model of coverage of multiple unmanned surface mapping vehicles, k.sub.1 represents cost coefficient of coverage path, k.sub.2 represents the cost coefficient of coverage time, P.sub.i(d.sub.cost) represents estimated coverage path of P.sub.i region, P.sub.i(t.sub.cost) represents estimated coverage time of P.sub.i region.

[0039] Firstly, d.sub.cost and t.sub.cost of an initial task area are estimated according to performance index H.sub.i of USMV.sub.i, where dost represents coverage path, t.sub.cost represents coverage time, d.sub.cost is further modified according to distribution of obstacles, and t.sub.cost is adjusted considering the equipment carried by USMV, and redistributed sub-areas is finally output.

[0040] S102: BL.sub.0.sup.m level map stage: according to the USMV.sub.i of each sub-area P.sub.i in the submaps BL.sub.l.sup.i and the overall map BL.sub.l.sup.m, outputting its own position information co and obstacle information η, transmitting to BL.sub.l.sup.i and updating BL.sub.l.sup.m, and then the path planning is carried out to find the target point tp;

[0041] Among them, BL.sub.0, . . . , BL.sub.L represent each dynamic map level BaseLayer, L is the highest level, overall map is BL.sub.l.sup.m, and submaps is BL.sub.l.sup.i.

[0042] S103: BL.sub.l.sup.m Level map stage: when trapped in a local optimum, the map level is updated layer by layer upward, and the target point tp is found in the corresponding level, and BS determination is conducted, and sending tr instruction to the USMV.sub.i of the sub-area Pi. Among them, the BS determination represents the collaborative behavior strategy determination, tp represents grid index value of the next target point of the USMV, and tr instruction indicates that the USMV is in the Travel state, which is the abnormal task status after the local optimum is reached;

[0043] In this disclosure, defining a list of behavior strategies: BS∈{ex1, ex2, ex3, ex4}, ex1, ex2, ex3, ex4 correspond to the four situations of area segmentation, backtracking transfer, area exchange, and joint recognition of obstacles in the collaborative behavior strategies. The path planning gives priority to BS determination, and outputting to or th status if any situation is met, and outputting tp.sub.m based on BL.sub.l.sup.m planning if cross-area is involved; if it does not comply with any of the conditions of BS, a path planning will be performed independently and tn or tc status will be output, where tn means to guide the USMV to be in the Normal status, so that it can perform the normal coverage task in the sub-area, and tc means to guide the USMV to start the depth sounding task.

[0044] In some of the optional implementations, typical collaborative behavior strategies include:

[0045] As shown in FIG. 3(a)-FIG. 3(d), the dotted line represents area boundary, the irregular graph represents the obstacle, and dot dash line represents area exchange or redistribution involved in the collaborative behavior strategies.

[0046] As shown in FIG. 3(a), the area segmentation scenario involves small area temporary allocation and submaps update. For P.sub.2 area, USMV will face two potential losses when it enters a small A.sub.rea area formed by obstacles and area boundaries. Firstly, according to obstacle processing strategy of IBA* algorithm, when entering the area, it is affected by the narrow terrain, and the cost of bypassing obstacles increases. Secondly, without interference, entering the region may trapped in a local optimum. In the case of the initial recognition of the obstacle edge in the P.sub.1 area, the strategy incorporates the small A.sub.rea area in P.sub.2 area into the P.sub.1 area, so that the USMV can ‘homeopathicly’ perform coverage task in the A.sub.rea area while ensuring continuous coverage action. Due to the small area of the area, it has little effect on the task allocation of the two, and the completion time is basically unchanged.

[0047] As shown in FIG. 3(b), the backtracking transfer scenario involves the backtracking area caused by the change of path direction trend. In multi-USMV collaborative planning, the IBA* algorithm will generate potential backtracking areas due to the independent coverage update process of subareas. In this scenario, the USMV.sub.1 in the P.sub.1 area starts the detour action shortly after the starting position according to the IBA* algorithm. From this time until the USMV.sub.1 is out of the lower left corner, the A.sub.rea area is still in the state of unexplored coverage. Therefore, this strategy divides the A.sub.rea area into P.sub.2 area, so that the USMV.sub.2 in the area continues to enter the A.sub.rea area to perform additional coverage actions, reducing the backtracking cost of USMV.sub.1.

[0048] As shown in FIG. 3(c), the area exchange scenario involves the exchange allocation of larger areas. Due to the influence of obstacles and boundaries, a large area is separated from the P.sub.2 area. Continuing to perform the A.sub.rea_2 area task will increase the path cost and calculation cost of USMV.sub.2 in the P.sub.2 area. At this time, the A.sub.rea_2 area is located in the main coverage path direction of the P.sub.1 area, and the A.sub.rea_1 area is located in the main coverage path direction of the P.sub.2 area. Therefore, this strategy exchanges A.sub.rea_1 and A.sub.rea_2 in P.sub.1 and P.sub.2 areas. In this case, the coverage time and task volume are basically unchanged. Based on the roughly same obstacle avoidance cost, the impact on the path length is also small.

[0049] As shown in FIG. 3(d), joint recognition of obstacles scenario is mainly aimed at the processing of obstacles. Due to the update of the independent sub-area map, the single S.sub.P_1 and S.sub.P_1 segment of the obstacle path is not complete for each USMV, and the obstacle may be omitted, which will affect the update of the total area map. Therefore, while covering the task execution, an additional obstacle joint discrimination process is added.

[0050] In some optional embodiments, the task decomposition of scanning scenario comprises:

[0051] Firstly, the grid task decomposition is defined:

G.sup.m={g.sub.α.sup.m,α=1, . . . N}

g.sub.α.sup.m∩g.sub.β.sup.m=Ø,∀α,β∈{1, . . . N}

R.sub.G.sub.m=∪.sub.i=1.sup.IR.sub.i

[0052] Among them, G.sup.m represents grid list of the overall map, g.sub.α.sup.m represents grid individual space of the overall map, N represents the maximum number of the grids, R.sub.G.sub.m represents the overall task based on the overall grid list G.sup.m, R.sub.i represents the subtask numbered i, i represents the upper bound of the number of P.sub.i tasks, which is consistent with the number of USMVs participating in the task, and the superscript m has no specific physical meaning.

[0053] As shown in FIG. 4, the details are as follows:

[0054] (1) State definition: the state is the basic status of coverage path planning of multiple unmanned surface mapping vehicles, reflecting the overall process and internal adjustment of the task:

S.sup.m={O,Q.sub.ini,Q.sub.re,E,COM}

[0055] where S.sup.m represents the overall status list, O represents the start of the status, Q.sub.ini represents the initial task allocation, Q.sub.re represents the coordinated task allocation, E represents the end status, and COM represents the calculation status.

[0056] (2) Backtracking List:

ξ{λ:i=1,2 . . . I}

[0057] where, Represents a backtracking list, λ.sup.i represents the backtracking list of each sub-area.

[0058] (3) Sub-Area Information:

CS.sub.P.sub.i∈{FN.sub.i,UFN.sub.i}

[0059] Where, CS.sub.P.sub.i represents the status of the regional depth sounding task in the current sub-area where USMV.sub.i is located, FN.sub.i represents Finished, that is, completed, and UFN.sub.i represents Unfinished, that is, incomplete.

[0060] (4) USMV Control Command:

tp.sub.m∈{1, . . . N.sup.m}

OC.sub.m∈{tn,te,th}

[0061] where, tp.sub.m represents the grid index value of the location of the next target point of the USMV in the overall map, N.sup.m represents the natural number set, and OC.sub.m represents the USMV task instruction in the overall map, which has higher permissions and priority than the sub-area; tn indicates to guide the USMV to be in the normal status, so that it can perform the normal coverage task in the sub-area; te indicates to guide the USMV to start switching areas and coordinate the coverage tasks between areas; th means to guide the USMV to continue to cover tasks in new areas;

[0062] At the beginning, initializing the system status list S. After the O status is turned on, the Q.sub.ini status starts first. The task area is initialized. According to task performance evaluation, the task area of each USMV.sub.i is roughly divided. At this time, the tn instruction is output to each USMV.sub.i, and the sub-area coverage task is completed in its internal according to the IBA* algorithm, which is recorded as COM status. USMV.sub.i keeps recording and feedback ω and η, At the same time, obstacle information is generated in real time. According to the collaborative behavior matching, if the reallocation condition is met at this time, the system will be switched to the Q.sub.re state to start the reallocation of sub-areas, and the affected USMV.sub.i will be adjusted to te state. The coverage path planning algorithm will generate tp.sub.m, temporarily jump out of the original region, and guide to start the th state after reaching the specified starting point. USMV.sub.i records the status value of the grid CS and the status value CS.sub.P.sub.i of P.sub.i area in each area action.

[0063] In some optional implementation schemes, map update of scanning scenario comprises two parts: overall map update and map update of each sub-area. Among them, overall map has higher priority and authority, which can interfere when necessary.

[0064] The sub-area map update process is in an independent operation status. Each USMV.sub.i updates the overall map BL.sub.l.sup.m and submaps BL.sub.l.sup.i simultaneously in the action. After P.sub.i and R.sub.i allocate areas and tasks, each BL.sub.l.sup.i independently updates to complete the multi-USMV coverage task, Bl.sub.l.sup.m mainly acts on the collaborative behavior between inter-regional USMV.sub.i, so that USMV.sub.i has a more reasonable choice when searching for target points by upgrading the map level in the sub-area, thereby saving the overall coverage time and reducing the negative impact of tr state and te state on the path length.

[0065] The details are as follows:

[0066] (1) Initialization Modeling

[0067] Referring to the method of establishing the map level BaseLayer in the IBA* algorithm, the grid map level BL.sub.0.sup.m with the highest fineness is still established in the overall map. Subsequently, the map level BL.sub.0.sup.i of each sub-interval is continued to be established on the basis of the overall map. The specific coverage area is determined by the initial division of the overall area P. On the basis of the establishment of the BL.sub.0.sup.m level and the BL.sub.0.sup.i level, continuing to execute the upgrade instructions.

G.sub.l.sup.m={g.sub.α.sup.ml,α.sup.ml=1, . . . N.sub.ml},∀ml∈{0, . . . mL}

G.sub.l.sup.m=∪.sub.i=1.sup.IG.sub.l.sup.i

[0068] Among them, G.sub.l.sup.m represents overall map grid list of multiple unmanned surface mapping vehicles coverage containing all levels, g.sub.α.sup.ml represents the individual space of the grid, N.sub.ml represents the maximum number of G.sub.l.sup.m grids, ml represents the map level, and mL represents the highest level.

[0069] (2) BL.sub.0.sup.m Level Map Modeling and Assignment

[0070] Initializing BL.sub.0.sup.m level map. After initializing the assignment of the BL.sub.0.sup.m level map, the assignment of each BL.sub.0.sup.i level map will continue, and its potential energy distribution will be opened independently from each P.sub.i interval, so each grid g.sub.α.sup.ml will have 2 potential energy values. However, this process does not significantly increase the amount of calculation. On the one hand, there is a direct and simple conversion relationship between the two. On the other hand, BL.sub.0.sup.m will not be in an active state for most of the time like 0-level map of each P.sub.i interval, but only in the process of coordinated transfer of USMV.sub.i area.

[0071] For unknown obstacles, since a single USMV.sub.i updates GT_list={obs, exp, fz, ue} in an independent P.sub.i interval, if it is at the sub-region boundary, incomplete recognition will occur. At this time, the Bresenham algorithm is first used to rasterize the edge lines of the identified obstacles into pixels in the frame buffer, and then the Flood Fill algorithm is introduced to process the recognition results. After completing the obstacle update of BL.sub.0.sup.m, the information will be transmitted to each BL.sub.0.sup.i level map.

[0072] S104: E stage: if the target point has not yet been found in the highest map level, checking each CS.sub.P.sub.i∈{FN.sub.i,UFN.sub.i}, and the BS determination is over.

[0073] In some optional implementations, the O stage of step S101 comprises: At the beginning, each unmanned surface mapping vehicle is in the default starting position with a status of O. Coordinate transformation grid index of the static map is established. Grid status update is carried out in each submaps, and the 0˜L level assignment of all maps is updated in turn. The USMV.sub.i outputs the to instruction. At the same time, the USMV.sub.i records and transmits its own position co and obstacle information η. Each USMV.sub.i starts to independently update its own grid status list GT_list and start the collaborative coverage task.

[0074] In some optional implementations, the BL.sub.0.sup.m level map stage in step S102 comprises:

[0075] In the BL.sub.0.sup.m level map stage, the potential energy priority is assigned to each submap row by row to ensure the complete coverage path of USMV.sub.i in each submap.

[0076] If BV.sub.ω>0 and {Ω.sup.N,Ω.sup.S}⊂F.sup.0, it is consistent with the IBA* algorithm action of single USMV, and the relative optimal path is selected by calculating the potential generation value J(tp). Similarly, if one side of ω.sup.N and ω.sup.S is close to the obstacle, it is preferred to select this direction, and the obstacle avoidance path of each interval P.sub.i is completed through this action, and the ex.sub.4 process is started. ω represents the number of grid sequences at the current position of USMV, and BV refers to the assignment of the number of grid sequences co in the BL highest-level map.

[0077] Among them, the detection field of USMV in grid map is recorded as D.sup.0(ω), ω∈D.sup.0(ω), D.sup.0(ω) contains all grid information that can be sensed by the current position of the USMV. For any grid α.sub.0 in D.sup.0(ω), if the connection with ω does not pass through fz or obs state grid, and its potential energy value is positive, the set is defined as the priority field, and the grids in the north and south directions in D.sup.0(ω) are defined as ω.sup.N and ω.sup.S.

[0078] If BV.sub.ω>0, and only one side of ω.sup.N and ω.sup.S is ue status and the other side is forbidden area, then opening the tc instruction to guide the USMV.sub.i to start the depth sounding task, and updating BL.sub.l.sup.i and BL.sub.l.sup.m at the same time.

[0079] If BW.sub.ω=0,F.sup.0≠Ø, then USMV.sub.i begins to move to the next stage of traversal, taking α.sub.0 with the largest BV.sub.α.sub.0 value in F.sup.0 as the tp point, and α.sub.0 represents the grid index;

[0080] If the above situations are inconsistent, it is determined that USMV.sub.i is in a locally optimal status at this time. Before upgrading the map level, BS determination is performed. If collaborative strategy is met, the preset action is started, the to instruction is output and the submaps are updated, and the sub-area P.sub.i is redistributed. If it does not conform to any of the situations in BS, it opens the high BL level map stage to start routing and outputs the tr instruction.

[0081] In some optional implementations, the BL.sub.l.sup.m level map stage in step S103 specifically comprises:

[0082] In the BL.sub.l.sup.m level map stage, the map level is improved step by step, and the map grid with the largest potential energy value is continued to be found in the high-level map. At the same time, its potential value J(tp) is calculated and the optimal tp point is selected. In the process of USMV.sub.i escaping local optimum, it still participates in BS determination in real time, and continues to evaluate the priority of independent coverage and collaborative partition.

[0083] In some optional implementations, the E stage of step S104 comprises:

[0084] Stage E is the end stage. According to CS.sub.P.sub.i∈{FN.sub.i,UFN.sub.i}, when the USMV.sub.i of all sub-area P.sub.i is transmitted back to FN.sub.i, it is determined that the entire task area P coverage task is over. Through all the environmental information detected, the missing area is reviewed to generate coverage information.

[0085] The performance of the CCIBA* method of this disclosure in terms of path length, number of turns and coverage rate is compared with the traditional Boustrophedon algorithm and BA* algorithm in turn, and the number of turns is reduced by about 16.5% and 5.1% respectively; the number of units is decreased by 58.3% and 44.4% respectively; the coverage rate is increased by about 2.1% and 7.6% respectively. On the premise of ensuring complete coverage, the path length is not significantly increased compared with BA* algorithm, which is about 10.76% less than that of Boustrophedon algorithm which achieves complete coverage.

[0086] This disclosure also provides a computer-readable storage medium, such as flash memory, hard disk, multimedia card, card type memory (such as SD or DX memory), random access memory (RAM), static random access memory (SRAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), programmable read-only memory (PROM), magnetic memory, disk, optical disk, server, app application mall, etc, a computer program is stored on it. When the program is executed by the processor, the coverage path planning method for multiple unmanned surface mapping vehicles in the implementation example is implemented.

[0087] It should be pointed out that according to the needs of implementation, each step/part described in this application can be divided into more steps/parts, and two or more steps/parts or partial operations of steps/parts can be combined into new steps/parts to achieve the purpose of this disclosure.

[0088] It is to be understood, however, that even though numerous characteristics and advantages of this disclosure have been set forth in the foregoing description, together with details of the structure and function of the invention, the disclosure is illustrative only, and changes may be made in detail, especially in matters of shape, size, and arrangement of parts within the principles of the invention to the full extent indicated by the broad general meaning of the terms in which the appended claims are expressed.