Coverage-path planning method for single unmanned surface mapping vessel

Abstract

An optimized coverage-path planning method for a single unmanned surface mapping vessel (USMV) is implemented with a system including a computer processor executing a computer program loaded in a storage device and implanting the method. The method includes rasterizing and initializing an environmental map, and an unmanned vessel outputting position data and obstacle data according to the environmental map so that path planning is started to provide a target point to the unmanned vessel. In case of tripping in a local optimum at a current-level map for the target point, the map level is updated in an ascending order until the highest level, in order to identify a map level in which the target point is found.

Claims

1. A coverage-path planning method for a single unmanned surface mapping vessel, which is executable in a system that comprises a computer processor and a storage device in communication connection with the computer processor and loaded with a computer program executed in the processor to implement the coverage-path planning method, the coverage-path planning method comprising the following steps: (1) rasterizing an environmental map to create a plurality of grids, dividing the environmental map into a plurality of levels (BL.sub.0, BL.sub.1, . . . , BL.sub.L) with several grids of a lower level forming one grid in a next higher level, initializing the environmental map by assigning a status value (GT) to each of the plurality of grids as ue, assigning a grid value (BV.sub.a0) to a grid a.sub.0 in a BL.sub.0-level map, then importing the initialized environmental map, inputting coordinates and updating the environmental map, wherein the ue represents a free space where a bathymetry mission is not completed, L is a number of the levels of the environmental map, BL.sub.0 is a lowest level and BL.sub.L is a highest level; (2) outputting, by an Unmanned Surface Mapping Vessel (USMV), position information and obstacle information thereof according to the updated environmental map to further update the environmental map, outputting a grid status list (GT_list) of the plurality of grids according to the further updated environmental map, and receiving the grid value of each of the plurality of grids in the BL.sub.0-level map and the position information and obstacle information output from the USMV according to the grid status list, starting path planning, and outputting a target point tp to the USMV, wherein the tp represents an index value of the grid where a next target point of the USMV is located; (3) performing an operation of updating each map level in an ascending order in case of being in a local optimum at the BL.sub.0-level map, searching the corresponding level for the tp to acquire a tp list, calculating a final tp according to a cost value, transmitting the final tp to the USMV, switching the USMV to execute a tr instruction, and when the tr instruction is executed, entering the BL.sub.0-level map and continuing to perform the path planning, wherein the tr instruction represents that the USMV is in a Travel state which is a non-task state after the USMV reaches the local optimum; and (4) ending the operation of updating in case of finding no target point tp in the BL.sub.L-level map, checking a status of the highest level map, and outputting an end state.

2. The coverage-path planning method according to claim 1, wherein the status value (GT.sub..sub.0) of the grid a.sub.0 in the BL.sub.0-level map is defined as: ${\mathrm{GT}}_{{}_0}=\mathrm{obs},\exp ,\mathrm{ue}\mathrm{or}\mathrm{fz}$ wherein obs represents an obstacle, exp represents the free space where the bathymetry mission has been completed, and fz represents a forbidden zone; the grid value (BV.sub.a0) of the grid a.sub.0 in the BL.sub.0-level map is defined as: ${\mathrm{BV}}_{{}_0}=\{\begin{array}{c}-1,\mathrm{if}{\mathrm{GT}}_{{}_0}=\mathrm{obs}\mathrm{or}\mathrm{fz}\\ 0,\mathrm{if}{\mathrm{GT}}_{{}_0}=\exp \\ {}_{{}_0},\mathrm{if}{\mathrm{GT}}_{{}_0}=\mathrm{ue}\end{array}$ wherein .sub..sub.0 is a potential energy of the grid a.sub.0 defined as: ${}_{{}_0}\left(x_o,y_o\right)=k.Math.N_x-x_0,k>1$ wherein x.sub.o and y.sub.o are a horizontal coordinate value and a vertical coordinate value of the grid a.sub.0 in the BL.sub.0-level map respectively; k is a potential energy coefficient, and N.sub.x is a maximum horizontal coordinate value in the BL.sub.0-level map; and the grid value is assigned to each of the plurality of grids in the BL.sub.0-level map line-by-line.

3. The coverage-path planning method according to claim 1, wherein the step (2) comprises: recording a detection area of the USMV in the updated environmental map as D.sup.0(), D.sup.0(), wherein the D.sup.0() contains all the grids perceptible to the USMV at a current position; defining a priority area F.sup.0, wherein F.sup.0 comprises a set of grids with a connection line between each of the set of grids and the does not pass through a grid in a fz or obs state and a potential energy value of each of the set of grids being positive, F.sup.0 .Math.D.sup.0(); for coverage-path planning in the BL.sub.0-level map, since a priority path of the USMV is to complete a coverage task in a direction of a single scanning line, selecting the grid on a same scanning line in the D.sup.0() as the target point; wherein the grid is selected according to the following steps: defining the grids in the D.sup.0() in both north and south directions as .sup.N and .sup.s, when BV.sub.>0 and {.sup.N,.sup.S}F.sup.0, in order to circumvent the case of massive backtracking, selecting the grid adjacent to the obstacle from the two grids, denoting the grid as tp.sub.obs, in the case where both the .sup.N and .sup.s are adjacent to the obstacle, introducing both into a cost calculation formula to calculate the potential cost values J(tp) produced by both paths, and selecting a relatively optimum path from local and global points of view; in the case where only one of the .sup.N and .sup.s is adjacent to the obstacle, then then giving priority to a .sup.N or .sup.s orientation where the adjacent obstacle is located to start traversal, wherein in the case of BV.sub.>0, the status value of the grid where the USMV is located ue, in two grids above and below the grid, the status value of one is exp or obs and the status value of the other one is ue, the grid is the target point tp, and the USMV switches to execute a tc instruction which guides the USMV to start an actual bathymetry mission; when BV.sub.=0, F.sup.0, determining that the USMV has completed the task on the single scanning line, starting to turn to a next stage of traversal, taking the grid with a largest grid value as the target point tp, starting a next action; and when none of the above cases are met, determining that the USMV is in the local optimum, wherein the USMV is driving into a concave obstacle area or is surrounded by an area with BV0 when being in the local optimum, and switching to a high-level map for the path planning, and switching the USMV to execute the tr instruction.

4. The coverage-path planning method according to claim 3, wherein the priority area is determined by: $F^0=\left\{{}_0{D}^0\left(\right):{\mathrm{BV}}_{{}_0}>0\right\}.$

5. The coverage-path planning method according to claim 4, wherein the potential cost value is determined by: $J\left(\mathrm{tp}\right)=k_{}.Math.\left(,\mathrm{tp}\right)+k_d.Math.d\left(,\mathrm{tp}\right)+k_{\mathrm{ul}}.Math.N_{\exp },$ $\mathrm{wherein},$ $d\left(,\mathrm{tp}\right)={.Math.\left({}_x,{}_y\right)-\left({\mathrm{tp}}_x,{\mathrm{tp}}_y\right).Math.}_2,$ k.sub. represents a turn cost coefficient and is considered as a unit turn angle cost; represents an absolute value of an angular change; k.sub.d represents a distance cost coefficient, and is considered as a unit distance movement cost; d represents a Euclidean distance; k.sub.ul represents a global trend coefficient and is considered as the cost of changing the situation; N.sub.exp represents a number of ue-state grids in an input direction, (.sub.x, .sub.y) represents horizontal and vertical coordinates of the grid, and (tp.sub.x, tp.sub.y) represents horizontal and vertical coordinates of the target point tp.

6. The coverage-path planning method according to claim 5, wherein the step (3) comprises: switching to a BL.sub.1-level map with l=1, finding a grid .sub.1 with a largest BV.sub.F.sub.l.sub.() in F.sup.l, wherein, the detection area of the USMV at the grid in the BL.sub.l-level map and having a detection range of R.sub.L is defined as D.sup.l(), D.sup.l(); the priority area in the detection area Dl() that is available for the USMV at the grid through an adjacent path and that is positive in the grid value is defined as F.sup.l, F.sup.l.Math.D.sup.l() and F.sup.l={.sub.lD.sup.l (): BV.sub..sub.l>0}; keeping in a calculation state to calculate potential costs of all target points in the tp list comprising no less than 2 target points; selecting an optimum target point, and making the USMV start the bathymetry mission; and since the local optimum mainly occurs at the end of the obstacle or at an end of the scanning line, calculating an adjacent path with a greedy algorithm when executing the tr instruction for continuing to track an obstacle contour until moving directly to the target point, breaking away from the local optimum and reaching the target point; in a scanning task, performing a collision avoidance action by the USMV in a scenario with obstacle existing, and switching the USMV to execute the tr instruction, returning to the BL.sub.0-level map after past and clear, resuming the bathymetry mission; if it is still impossible to break away from the local optimum when l=1, switching to a higher-level map level by level until the target point is derived; and if it is still unable to break away from the local optimum when l=L, then preliminarily determining that the traversal is completed.

7. The coverage-path planning method according to claim 6, wherein, in the BL.sub.l-level map, the priority area is specifically expressed as: $F^l=\left\{{}_l{D}^l\left(\right):{\mathrm{BV}}_{{}_l}>0\right\},$ wherein 1lL.

8. The non-transitory tangible computer-readable storage device storing the computer program which, when executed by the computer processor, causes the system to implement the coverage-path planning method according to claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flow block diagram illustrating a coverage-path planning method for a single unmanned surface mapping vessel in accordance with an embodiment of the present disclosure;

(2) FIG. 2 is a flow diagram illustrating the coverage-path planning method for the single unmanned surface mapping vessel in accordance with an embodiment of the present disclosure;

(3) FIG. 3 shows a schematic view illustrating level division of an environmental map.

DETAILED DESCRIPTION

(4) In order to make the objectives, technical solutions and advantages of the disclosure more clear, the disclosure will be described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are intended only to explain the disclosure and are not intended to limit it. Further, the technical features related to the various embodiments of the present disclosure described below can be combined with each other as long as they do not conflict with each other.

(5) The disclosure provides an optimized coverage-path planning method (IBA*) for a single unmanned surface mapping vessel, which improves the coverage rate and coverage effect of the unmanned surface mapping vessel in a complex working environment and improves the working efficiency of the unmanned surface mapping vessel. In order to make the above objectives, features and advantages of the disclosure more obvious and understandable, the disclosure will be further described in detail with reference to the drawings and specific embodiments.

(6) FIG. 1 is a flow block diagram illustrating the coverage-path planning method for the single unmanned surface mapping vessel in accordance with an embodiment of the present disclosure, and the method shown in FIG. 1 includes four steps: initialization, path planning in a BL.sub.0-level map, path-planning in a BL.sub.l-level map (l1), and end state.

(7) In particular, FIG. 2 is a flow diagram illustrating the coverage-path planning method for the single unmanned surface mapping vessel in accordance with an embodiment of the present disclosure, and the method includes the steps of:

(8) In step S101, an environmental map is rasterized to create a plurality of grids, the environmental map is divided into a plurality of levels (BL.sub.0, BL.sub.1, . . . , BL.sub.L) with several grids of a lower level forming one grid in a next higher level, the environmental map is initialized by assigning a status value (GT) to each of the plurality of grids as ue, assigning a grid value (BV.sub.a0) to a grid a.sub.0 in a BL.sub.0-level map, then the initialized environmental map is imported, coordinates are inputted and the environmental map is updated.

(9) GT represents the status value of the grid, and the ue represents a free space where a bathymetry mission is not completed. L is the number of the levels of the environmental map, BL.sub.0 is the lowest level and BL.sub.L is the highest level.

(10) During the rasterization, the environmental map in divided into several equally sized adjacent grids for easy update and maintenance. The environmental map is first quantized at a certain size, grid coordinates are established, then the coordinated grids are placed in one array, and attribute assignment is made to each grid for distinguishing different locations or grid cells.

(11) As shown in FIG. 3, the environmental map is divided into a plurality of levels. In the BL.sub.L-level map, each grid can be divided into several grids, such as four grids as shown in FIG. 3, to form the BL.sub.L-1-level map. Each grid of the BL.sub.L-1-level map can further be divided into several grids to for the BL.sub.L-2-level map. The grid of the BL.sub.0-level map cannot be divided further and thus the BL.sub.0-level map has the highest precision.

(12) In step S102, the USMV outputs position information and obstacle information q thereof according to the updated environmental map to further update the environmental map, a grid status list GT_list of the plurality of grids is output according to the further updated environmental map, and the grid value of each of the plurality of grids in the BL.sub.0-level map and position information w and obstacle information q output from the USMV is received according to the GT_list, path planning is started, and a target point tp is output to the USMV, wherein the tp represents an index value of the grid where a next target point of the USMV is located;

(13) The grid status list is defined as GT_list, and

(14) $\mathrm{GT\_list}=\left\{\mathrm{obs},\exp ,\mathrm{fz},\mathrm{ue}\right\}$ where obs represents an obstacle, exp represents the free space where the bathymetry mission has been completed, and fz represents a forbidden zone.

(15) The grid value (BV.sub.a0) of the grid a.sub.0 in the BL.sub.0-level map is defined as:

(16) ${\mathrm{BV}}_{{}_0}=\{\begin{array}{c}-1,\mathrm{if}{\mathrm{GT}}_{{}_0}=\mathrm{obs}\mathrm{or}\mathrm{fz}\\ 0,\mathrm{if}{\mathrm{GT}}_{{}_0}=\exp \\ {}_{{}_0},\mathrm{if}{\mathrm{GT}}_{{}_0}=\mathrm{ue}\end{array}$ where .sub..sub.0 is a potential energy of the grid a.sub.0 defined as:

(17) ${}_{{}_0}\left(x_o,y_o\right)=k.Math.N_x-x_0,k>1$ where x.sub.o and y.sub.0 are a horizontal coordinate value and a vertical coordinate value of the grid a.sub.0 in the BL.sub.0-level map respectively; k is a potential energy coefficient, and N.sub.x is a maximum horizontal coordinate value in the BL.sub.0-level map; and the grid value is assigned to each of the plurality of grids in the BL.sub.0-level map line-by-line.

(18) In step S103, in case of being in a local optimum at the BL.sub.0-level map, each map level is updated in ascending order, and the corresponding level is searched for the tp to acquire a tp list, a final tp is calculated according to a cost value, the final tp is transmitted to the USMV, and the USMV is switched to execute a tr instruction, and when the tr instruction is executed, the BL.sub.0-level map in entered and path planning is performed; wherein the tr instruction represents the USMV is in a Travel state which is a non-task state after the USMV reaches the local optimum.

(19) In step S104, when no target point tp is found in the BL.sub.L-level map, the task is ended, the status of the highest level map is checked, and an end state is output.

(20) In some alternative embodiments, the step S102 may comprise the following steps: recording a detection area of the USMV in the updated environmental map as D.sup.0(), D.sup.0(), wherein w is the position of the USMV, the D.sup.0() contains all the grids perceptible to the USMV at a current position; defining a priority area F.sup.0 wherein F.sup.0.Math.D.sup.0(), and the grids contained in the priority area F.sup.0 satisfy the following two requirements: (1) a connection line between the grid and the w does not pass through a grid in a fz or obs state; and (2) a potential energy value of the grid is positive; for coverage-path planning in the BL.sub.0-level map, since a priority path of the USMV is to complete a coverage task in a direction of a single scanning line, selecting the grid on a same scanning line in the D.sup.0() as the target point; wherein specifically, the grid is selected according to the following steps: defining the grids in the D.sup.0() in both north and south directions as .sup.N and .sup.s, when BV.sub.>0 and {.sup.N, .sup.s}F.sup.0, in order to circumvent the case of massive backtracking, selecting the grid adjacent to the obstacle from the two grids, denoting the grid as tp.sub.obs, in the case where both the .sup.N and .sup.s are adjacent to the obstacle, introducing both into a cost calculation formula to calculate the potential cost values J(tp) produced by both paths, and selecting a relatively optimum path from local and global points of view; in the case where only one of the .sup.N and .sup.s is adjacent to the obstacle, then then giving priority to a .sup.N or .sup.s orientation where the adjacent obstacle is located to start traversal, wherein in the case of BV.sub.>0, the status value of the grid where the USMV is located ue, in two grids above and below the grid, the status value of one is exp or obs and the status value of the other one is ue, the grid is the target point tp, and the USMV switches to execute a tc instruction which guides the USMV to start an actual bathymetry mission; when BV.sub.=0, F.sup.0, determining that the USMV has completed the task on the single scanning line, starting to turn to a next stage of traversal, taking the grid with a largest grid value as the target point tp, starting a next action; and when none of the above cases are met, determining that the USMV is in the local optimum, wherein the USMV is driving into a concave obstacle area or is surrounded by an area with BV0 when being in the local optimum, and switching to a high-level map for the path planning, and switching the USMV to execute the tr instruction.

(21) The priority area is determined by:

(22) 0$F^0=\left\{{}_0{D}^0\left(\right):{\mathrm{BV}}_{{}_0}>0\right\}.$

(23) The potential cost value is determined by:

(24) $J\left(\mathrm{tp}\right)=k_{}.Math.\left(,\mathrm{tp}\right)+k_d.Math.d\left(,\mathrm{tp}\right)+k_{\mathrm{ul}}.Math.N_{\exp },$$\mathrm{wherein},$$d\left(,\mathrm{tp}\right)={.Math.\left({}_x,{}_y\right)-\left({\mathrm{tp}}_x,{\mathrm{tp}}_y\right).Math.}_2,$ k.sub. represents a turn cost coefficient and is considered as a unit turn angle cost; represents an absolute value of an angular change; k.sub.d represents a distance cost coefficient, and is considered as a unit distance movement cost; d represents a Euclidean distance; k.sub.ul represents a global trend coefficient and is considered as the cost of changing the situation; N.sub.exp represents a number of ue-state grids in an input direction, (.sub.x, .sub.y) represents horizontal and vertical coordinates of the grid, and (tp.sub.x, tp.sub.y) represents horizontal and vertical coordinates of the target point tp.

(25) In some alternative embodiments, the step S103 comprises: switching to a BL.sub.l-level map with l=1, finding a grid .sub.l with a largest BV.sub.F.sub.l.sub.() in F.sup.l, wherein, the detection area of the USMV at the grid in the BL.sub.l-level map and having a detection range of R.sub.L is defined as D.sup.l(), D.sup.l(); the priority area in the detection area D.sup.l() that is available for the USMV at the grid through an adjacent path and that is positive in the grid value is defined as F.sup.l, F.sup.l.Math.D.sup.l() and F.sup.l={.sub.lD.sup.l(): BV.sub..sub.l, >0}; keeping in a calculation state to calculate potential costs of all target points in the tp list comprising no less than 2 target points; selecting an optimum target point, and making the USMV start the bathymetry mission; and since the local optimum mainly occurs at the end of the obstacle or at an end of the scanning line, calculating an adjacent path with a greedy algorithm when executing the tr instruction for continuing to track an obstacle contour until moving directly to the target point, breaking away from the local optimum and reaching the target point; in a scanning task, performing a collision avoidance action by the USMV in a scenario with obstacle existing, and switching the USMV to execute the tr instruction, returning to the BL.sub.0-level map after past and clear, resuming the bathymetry mission; if it is still impossible to break away from the local optimum when l=1, switching to a higher-level map level by level until the target point is derived; and if it is still unable to break away from the local optimum when l=L, then preliminarily determining that the traversal is completed.

(26) In the BL.sub.l-level map, the priority area is specifically expressed as:

(27) $F^l=\left\{{}_l{D}^l\left(\right):{\mathrm{BV}}_{{}_l}>0\right\},$ where 1lL.

(28) The application also provides a computer-readable storage medium, such as a flash memory, a hard disk, a multimedia card, a card-type memory (e.g., SD or DX memory, etc.), a random access memory (RAM), a static random access memory (SRAM), a read-only memory (ROM), an electrically erasable programmable read-only memory (EEPROM), a programmable read-only memory (PROM), a magnetic memory, a disk, an optical disk, a server, an App market, etc., a computer program is stored thereon which, when executed by a processor, implements the coverage-path planning method for the single unmanned surface mapping vessel in a method embodiment.

(29) Additionally, in a first aspect, the present disclosure provides the coverage-path planning method for a single unmanned surface mapping vessel, which is executed with a system including at least one computer processor and a storage device in communication connection with the at least one processor, wherein the storage device stores instructions to be executed by the at least one processor and the instructions are executed in the at least one processor so that the at least one processor executes the coverage-path planning method for a single unmanned surface mapping vessel described above.

(30) In a second aspect, the present disclosure provides a computer program product that includes a coverage-path planning process. The computer program product includes a computer program that is stored in a computer-readable storage medium. The computer program is executable by a computer to implement the above-described coverage-path planning method for a single unmanned surface mapping vessel.

(31) In a third aspect, the present disclosure includes at least one signal transmitting module that is operable to a control signal, a path planning message or other necessary messages for communication with an external system or an operator in order to realize adjustment of a planned path, feedback for tasks, or other necessary communication; and an unmanned vessel signal receiving module and a data link, which are arranged for receiving signals and data transmitted from an external system, a transducer, or an operator for path adjustment, remote control, or data feedback, so that when a moth path of the unmanned vessel is confirmed, data can be transmitted to a motion controller of the unmanned vessel for subsequent operation.

(32) In a fourth aspect, the present disclosure provides a motion controller of an unmanned vessel, which, based on a path message generated with a path-planning program that may include, at least partly, the computer program discussed above for implementing the above-described coverage-path planning method for a single unmanned surface mapping vessel, controls the course, the speed, and steering of the unmanned vessel, interprets data of the transducer, implements path planning, monitors progress of planning, and adjusts operation of the unmanned vessel, in order to ensure the unmanned vessel is following a predetermined path and executing a predetermined task; and an unmanned vessel power system in connection with the motion controller and including systems of driving, propelling, and energy for supplying power to the unmanned vessel to ensure the unmanned vessel is operable for moving along the planned path.

(33) In a fifth aspect, the present disclosure enables visualization of a result of coverage-path planning by providing a visualizable interface for intuitively display a water body area, a location of an unmanned vessel, and a result of path planning, such that, on a map, each of a number of unmanned vessels is designated with a unique individual identification mark or symbol to assist operators or users to identify the vessels, wherein the identification mark or symbol includes or carries essential messages of the unmanned vessels, such as titles, speeds, and results of unmanned vessel coverage-path planning result.

(34) The present disclosure, for at least the embodiments or aspects provided herein, is advantageous for at least the following. The present disclosure provides a coverage-path planning method for a single unmanned surface mapping vessel and a system or a set of devices for implementing or operating with the method, in which target points of a path are determined according to data of a water body area and distance, and among the target points, already-surveyed target points are recorded and un-surveyed target point are determined so that a cruise path having a shortest distance is generated dynamically during the cruise to ensure that even an unmanned vessel deviates from a predetermined path due to various factor, the unmanned vessel may still move along an optimum cruise path that is determined momentarily.

(35) It should be noted that the various steps/components described in the present application may be split into more steps/components or two or more steps/components or partial operations of the steps/components may be combined into new steps/components to achieve the objectives of the present disclosure, depending on the requirements of the implementation.

(36) It will be readily understood by those skilled in the art that the above description is only preferred embodiments of the present disclosure and is not intended to limit the present disclosure. Any modification, equivalent replacement, improvement, etc. made within the spirit and principles of the present disclosure should be included in the scope of protection of the present disclosure.