Search

CN-116820088-B - Dynamic real-time planning method for collaborative search scene

CN116820088BCN 116820088 BCN116820088 BCN 116820088BCN-116820088-B

Abstract

A dynamic real-time planning method for collaborative search scenes is characterized in that the total search path length of unmanned ship units is estimated through an optimization algorithm according to the initial position of a cluster and the boundary of a strange area to be explored, and search areas of the unmanned cluster units are independently arranged. Compared with the prior art, the method and the system can enable the unmanned cluster to master the global situation information of the area to be probed at the highest speed, autonomously decide the task state and path planning of each unit of the cluster according to the current situation so as to eliminate the influence of uncertainty in the actual probing process, and finally realize the total time minimization of multi-objective searching.

Inventors

  • HUANG WENDAO
  • LI HAO
  • YU MODUO
  • LU SHIPING
  • TAI NENGLING
  • Hu Sizhe

Assignees

  • 上海交通大学

Dates

Publication Date
20260505
Application Date
20230414

Claims (7)

  1. 1. A dynamic real-time planning method for collaborative search scenes is characterized by comprising the following steps: step 1) scene initialization, namely generating an initial task area and scene elements, and setting initial parameters of obstacles, targets to be checked, unmanned clusters and unmanned ship units; Step 2) distributing and generating search paths, namely generating initial search task areas of all unmanned ship units through a task distribution planning method according to initial positions of unmanned clusters and boundary sizes of areas to be probed, wherein the initial search task areas comprise the steps of checking the relation between the total width of the sub-area X direction and the detection diameter of the unmanned ship units, when the sum of the detection diameters of the unmanned ship units is larger than the total width of the sub-area X direction, the task of searching the areas can be completed only by using part of unmanned ship units, arranging the first m (m < nk)) unmanned ship units to participate in a map scanning, and directly distributing and verifying the remaining nk-m unmanned ship units, wherein when the range of a sub-area k is larger, the planned unmanned ship units need to complete the area searching work through turning back, and the division of the unmanned ship unit exploration area needs to consider the total navigation distance of the unmanned ship units, and the aim is to complete the search time of all strange areas as short as possible, namely, the mixed integer linear planning problem of min-max is satisfied: solving to obtain the value of x im , namely obtaining the number of channels distributed by each unmanned ship unit, wherein the constraint comprises: i) The total sailing distance of the unmanned ship unit i comprises the total length of the channel in the Y direction covered by the unmanned ship unit i and the sailing distance in the X direction required by the target channel, and specifically comprises the following steps: ; ii) each aisle must be covered by one unmanned boat unit: ; iii) The total width of the channel covered by the unmanned ship unit is larger than the width of the subarea in the X direction, and the method specifically comprises the following steps: ; iv) when the unmanned ship unit participates in searching of the strange area, the Boolean variable z i is equal to 1, namely the unmanned ship unit i is allocated with a search task, specifically: ; v) the total number of unmanned ship units participating in the search task in the subarea is not more than the total number of unmanned ship units allocated to the subarea, specifically: ; vi) only planning 1 unmanned ship unit for each channel to complete searching, specifically: wherein the collection of cluster units within a sub-area Aggregation of channel numbers D is the detection diameter of the unmanned ship unit i, that is, the channels in the subarea, that is, the number of channels of the unmanned ship unit i for single voyage without turning back in the direction of the map Y is at most not more than the total width divided by the minimum detection diameter of the unmanned ship unit, K is a set of subareas, x im is a boolean variable, x im =1 when the unmanned ship unit i is allocated to the mth channel, the meaning of the objective function is that the maximum voyage distance of each unmanned ship unit in the hope subarea is minimum, the search process often requires that the voyage speed of the unmanned ship unit is not too fast because the target to be searched is required to be covered to the maximum, and the maximum total time is the shortest and the maximum total shortest equivalent is obtained when the allowable maximum voyage speeds of all unmanned ship units in the cluster are the same; in order to ensure that the boundary of the search area is covered by no dead angle, planning the channel farthest from the initial position to turn back once more, and directly entering a target verification stage to be probed after any unmanned ship unit finishes the search of the allocated area; Step 3) updating the environment map, namely adding the target position and the obstacle position detected in the searching process into the map, and updating the environment map information; step 4) updating the target state, namely updating target verification information after the unmanned ship unit effectively verifies the target once; Step 5) planning and distributing a next exploration target, namely establishing a collaborative verification path planning objective function according to available unmanned ship unit information, an environment map and target state information of a target which is not distributed currently, and then calculating to obtain a target distribution result of each unmanned ship unit; Step 6) unmanned ship unit task state switching, namely defining a task state and a state transition relation in a planning process, wherein the unmanned ship unit is possibly in an idle state, a task executing state and a disconnection state; and 7) judging whether the collaborative search task is completed or not.
  2. 2. The method for dynamic real-time planning for collaborative search scenes according to claim 1 is characterized in that the step 1 specifically comprises the steps of determining the number of unmanned ship units to be allocated to each subarea, and when the number of unmanned ship units allocated to a left area is N1 and the number of unmanned ship units allocated to a right area is N2, calculating the number as follows: wherein: For the location of the center point of the drone cluster on the x-axis in a cartesian coordinate system, , The left lower angle x-axis coordinate and the right lower angle x-axis coordinate of the region to be probed are respectively; n is the total number of unmanned ship units in the cluster, N1 is the number of unmanned ships distributed on the left side of the starting area, N2 is the number of unmanned ships distributed on the right side of the starting area, and N=N1+N2 is satisfied.
  3. 3. The method for dynamic real-time planning for collaborative search scene according to claim 1, wherein the step 3) comprises updating the environmental information according to the search result of each unmanned ship unit in the step 2), specifically updating the target or the obstacle to be searched into the map environmental information when any unmanned ship unit searches for a previously undiscovered target or common obstacle; The environment information comprises the state of the object to be probed and the position information of the obstacle.
  4. 4. The collaborative search scene oriented dynamic real-time planning method according to claim 1, wherein the collaborative verification constraint of dynamic real-time path planning comprises: a) The revisit time constraint during the secondary verification of the unmanned ship unit, wherein when any unmanned ship unit verifies any target for the second time, the time interval for the two verifications is more than a certain threshold value, and the two verifications can be calculated as one effective verification; b) And (3) revisiting distance constraint during secondary verification of the unmanned ship unit, namely, when any unmanned ship unit verifies any target for the second time, the unmanned ship unit leaves a certain distance beyond a threshold value of the target, and then goes to the target for verification.
  5. 5. The collaborative search scene-oriented dynamic real-time planning method according to claim 1, wherein the collaborative verification path planning objective function is Wherein the variables are optimized Taking 1 as an integer, taking the 1 th unmanned ship unit as the i unmanned ship unit to go to the target j to be verified, and taking 0 as the unmanned ship unit not to go to the target j to be verified, wherein the target function coefficient is the target function coefficient For the verification cost of the ith unmanned ship unit from the current position to the target j to be verified, if When the secondary visit distance constraint is met, the cost is as follows: Otherwise the cost is When (when) If the method does not belong to the secondary verification, the cost is as follows: wherein: for the distance between unmanned boat unit i to target j at the current moment, Is the average speed of the unmanned boat unit i, For the time of the current moment of time, For the moment when unmanned ship unit i last verified j, For the revisit time threshold for target j, A revisit distance threshold for target j; The constraint of the collaborative verification path planning objective function comprises: , , , wherein: for a set of targets that have not yet been verified, For a verified set of targets, Is the single verification capability of the unmanned ship unit i, The heuristic threshold value of the target j is equal to the residual verification base +h of the target j, and h is a heuristic function and is determined according to the situations of the current cluster and the residual targets; and finally, planning to obtain a target distribution result of each unmanned ship unit, and sending an instruction to a track planning and tracking layer for execution.
  6. 6. The collaborative search scene-oriented dynamic real-time planning method according to claim 1 is characterized in that step 6 specifically comprises the steps that each unmanned boat unit executes a next task according to a current task instruction, a finite state machine is used for system, wherein task=8 is a search stage of an unmanned boat unit execution area, task=0 is a state that the unmanned boat unit is currently in a target not yet allocated, target allocation needs to be carried out, task=1 is a target to which the unmanned boat unit is allocated and is in the process of going to the verification target, task= -1 is a state that the unmanned boat unit is in a linkage state, switching conditions among the states are Start are that when scene initialization is carried out, all unmanned boat units trigger the conditions, and enter a stage of task=8, A is that when the unmanned boat unit has been tracked into a target search path allocated, the unmanned boat unit directly enters a state waiting for target allocation, task=1 is a state waiting for the unmanned boat unit to enter the target allocation, and when the unmanned boat unit is in a failure state, and D is a stage of the unmanned boat unit is in a failure state, and when the unmanned boat unit is in a failure state, and the unmanned boat unit is in a failure state after the unmanned boat unit is in a failure state, and the unmanned boat unit is in a failure state.
  7. 7. A dynamic real-time planning system for realizing the collaborative search scene-oriented dynamic real-time planning method according to any one of claims 1-6 is characterized by comprising an unmanned ship unit simulation module, a system configuration module, a cluster task allocation module and a cluster planning module, wherein the unmanned ship unit simulation module models and sets static and dynamic model parameters of unmanned ship units according to physical dimensions, speeds, accelerations and steering angular speeds of the unmanned ship units, the system configuration module configures environment parameters and unmanned ship unit parameters, the cluster task allocation module obtains an initial exploration area allocation result of each unmanned ship unit according to the environment parameters and the unmanned ship unit parameters based on an initial task allocation algorithm, and the cluster planning module carries out real-time task re-planning processing according to target information obtained by exploration to obtain a exploration path planning result of each unmanned ship unit in the next step.

Description

Dynamic real-time planning method for collaborative search scene Technical Field The invention relates to a technology in the field of unmanned cluster control, in particular to a dynamic real-time planning method for a collaborative search scene. Background The search task of the unmanned cluster generally needs to search for a strange area, that is, the unmanned cluster needs to perform blind area-free coverage search on a designated area, and obtain a specific position of a target to be probed. After the targets to be probed are detected, the unmanned clusters dynamically plan the tasks and tracks of all unmanned ship units in the clusters according to the known number and attribute of the targets to be probed, the known task load detection range of the unmanned ship units, the known residual verification base numbers of the targets to be probed and other indexes, so that effective searching of all the targets to be probed in unfamiliar areas is completed, and the initial positions are returned. In collaborative search, unmanned clusters are required to autonomously arrange track routes of unmanned ship units, search tasks of unfamiliar areas are completed, and a verification strategy of each unmanned ship unit to a target to be detected is determined, so that verification of all targets in the areas is guaranteed to be completed in an optimal or better mode. The technical difficulties of the unmanned cluster strange area in the current stage include that the positions and the number of objects to be probed cannot be known in advance in an actual task, an initial area searching and distributing strategy with reasonable design is needed, the feasible path action space for the exploration of a plurality of objects is often an NP-hard problem, and the optimal path planning result is difficult to solve in a short time. Disclosure of Invention Aiming at the defects in the prior art, the invention provides a dynamic real-time planning method for a collaborative search scene, which can enable an unmanned cluster to master global situation information of a region to be searched at the highest speed and autonomously decide task states and path planning of each unit of the cluster according to the current situation so as to eliminate the influence of uncertainty in the actual searching process and finally realize the minimization of the total time of multi-objective search. The invention is realized by the following technical scheme: the invention relates to a dynamic real-time planning method for collaborative search scenes, which comprises the following steps: Step 1) scene initialization, namely generating an initial task area and scene elements, and setting initial parameters of obstacles, targets to be checked, unmanned clusters and unmanned ship units. And 2) dividing the unmanned ship units distributed to the subareas into further exploration areas, and generating initial search task areas of all unmanned ship units by a task distribution planning method according to the initial positions of the unmanned clusters and the boundary sizes of the areas to be explored. And 3) updating the environment map, namely adding the target position and the obstacle position detected in the searching process into the map, and updating the environment map information. And 4) updating the target state, namely updating target verification information after the unmanned ship unit effectively verifies the target once. And 5) unmanned cluster collaborative verification dynamic real-time path planning, namely establishing a collaborative verification path planning objective function according to available unmanned ship unit information, an environment map and target state information of an object which is not distributed currently, calculating to obtain a target distribution result of each unmanned ship unit, and distributing the available unmanned ship unit to the next target point through a planning algorithm according to the position of an unmanned cluster unit to be distributed and the position of the object to be verified at any moment. And 6) switching task states of the unmanned ship units, namely defining task states and state transition relations when the unmanned ship units are possibly in idle states, task execution states, unconnected states and the like in the planning process. And 7) judging whether the collaborative search task is completed or not. The invention relates to a dynamic real-time planning system for realizing the method, which comprises an unmanned ship unit simulation module, a system configuration module, a cluster task allocation module and a cluster planning module, wherein the unmanned ship unit simulation module models according to the physical size, the speed, the acceleration and the steering angular speed of an unmanned ship unit and sets static and dynamic model parameters of the unmanned ship unit, the system configuration module configures environment parameters and unmanned ship unit param