CN-117707137-B - Regional coverage path planning method based on dynamic networking under local communication

CN117707137BCN 117707137 BCN117707137 BCN 117707137BCN-117707137-B

Abstract

A regional coverage path planning method based on dynamic networking under local communication comprises the steps of initializing positions of N robots, enabling the N robots to communicate with each other, setting a virtual position outside a coverage area, enabling all the robots to synchronously complete moving to respective next target neighbor points in each iteration period, judging whether all the robots are moving, resetting moving states of all the robots if the robots are moving, ending the iteration period, otherwise judging whether the robots which are involved in deadlock exist, enabling the deadlock to be relieved if the robots which are involved in deadlock exist, and ending the iteration period after all the robots which are involved in deadlock finish moving to the target neighbor points. Repeating the moving iteration cycle of the robot until the iteration times reach a preset value or all environment areas are covered. The method can effectively respond to the change of the area to be covered of the environment in real time under the barrier-free environment with limited communication, and can realize the complete coverage of the area with the minimum cost.

Inventors

ZHANG JUNQI
HAN BINBIN
WANG CHENG
DENG RONG
Zang di
ZHANG ZHIMING
LIU CHUNMEI

Assignees

同济大学

Dates

Publication Date: 20260512
Application Date: 20231113

Claims (9)

1. The regional coverage path planning method based on dynamic networking under local communication is characterized by comprising the following steps: Step 1, establishing a search environment and initializing group robots; Step 2, calculating neighbor points to be selected of each robot; Step 3, based on the crowd communication range of the moved robot, acquiring selectable neighbor points of the not-moved robot; step 4, calculating predation avoidance rewards of the selectable neighbor points obtained in the step 3 respectively; Step 5, calculating linear motion rewards of the selectable neighbor points obtained in the step 3 respectively; step 6, calculating boundary coverage rewards of the selectable neighbor points obtained in the step 3 respectively; Step 7, calculating the total benefits of the neighbor points according to the reward value components calculated in the steps 4-6 respectively; step 8, selecting a neighbor point corresponding to the maximum benefit value as a moving target of the corresponding robot in the iteration period according to the total benefits of the neighbor points calculated in the step 7, and setting the moving state of the robot; Step 9, repeating the steps 3-8 in the iteration period until all robots move or have the robot which falls into the deadlock; Step 10, if all robots have moved, ending the iteration and resetting all robot states; if a deadlock robot exists, the deadlock is relieved, and the iteration is ended; Step 11, if the current iteration number reaches a preset value or all environment areas are covered, executing step 12, otherwise executing step 2; Step 12, outputting a moving coverage path of each robot; In step 10, for robots that have a trapping "deadlock", three situations are included: In the first case, all robots do not have any selectable neighbor points, and all neighbor points of the robots are covered; Secondly, the existing part of robots do not have any selectable neighbor points, and all neighbor points of the existing part of robots are covered; The third condition is that although uncovered neighbor points exist around part of robots, due to the limitation of communication constraint, the moving direction of the robot which the robot follows can only move to a specific neighbor point in the same direction, and the neighbor point is covered by the robot or other robots, so that the robot has no selectable point and is passively in a deadlock state; for the first case, an algorithm A is adopted to determine the proper backtracking point to the uncovered area, and the current position is firstly used Put into open list And repeating the following processes of judging whether the area coverage is completed or reaches the backtracking point, if so, ending the algorithm, otherwise, calculating and acquiring the current position according to the formula in the step 2 Is placed in an open list After that, according to the formula in the step 7, the cost values reaching each target point can be calculated respectively, and the target point corresponding to the minimum cost value is taken as the current position And put the target point into the close list Finally, when the robot reaches the position When the neighbor target point is not covered, at this time Namely the backtracking point is the backtracking point, The target point sequence in the model is a moving path, and path planning is completed; aiming at the second and third cases, when part of robots are in a deadlock state, a following escape mechanism is adopted to achieve the purpose of reaching a backtracking point as soon as possible and maintaining the communication network uninterrupted.
2. The regional coverage path planning method based on dynamic networking under local communication according to claim 1, wherein the step 1 comprises: Establishing a search environment and setting a virtual reference position Initializing algorithm parameters, namely the number of robots Communication distance of robot Weight factor ; Initializing a position of a robot And ensures that communication with each other is possible via AD-HOC mode.
3. The regional coverage path planning method based on dynamic networking under local communication according to claim 2, wherein the step 2: Robot with arbitrary robot The current position is Its neighbor target point is expressed as Comprising four connecting points And calculating neighbor points to be selected of each robot, wherein the formula is as follows: Wherein, the Is a robot Is used for the current coordinate position of the (c).
4. The regional coverage path planning method based on dynamic networking under local communication according to claim 3, wherein the step 3: Is provided with For the position of the group of the moved robots, the neighbor points and the neighbor points to be selected Shortest Euclidean distance is The calculation formula is as follows: Wherein the method comprises the steps of When (when) In the time-course of which the first and second contact surfaces, When (1) In the time-course of which the first and second contact surfaces, When (1) In the time-course of which the first and second contact surfaces, , Is a moved robot if and only if When the neighbor target point is within the communication range of the mobile robot group, the neighbor target point is used as a selectable neighbor point; Is the communication distance of the robot.
5. The regional coverage path planning method based on dynamic networking under local communication according to claim 4, wherein in the step 4, the formula for calculating predation avoidance rewards is: Wherein, the In order to select the number of neighbor points, For a preset maximum prize value component, Is a neighbor point To predators The Euclidean distance of (2), and the like, For the current point Maximum Euclidean distance from predator among all neighbor points of (2) For the current point The minimum Euclidean distance between all neighbor points of the predator is calculated as follows: 。
6. The regional coverage path planning method based on dynamic networking under local communication according to claim 5, wherein in step 5, the formula for calculating the linear motion reward is: Wherein, the In order to select the number of neighbor points, For a preset maximum prize value component, For the current point Is a previous history of locations (a); For the current position Is the first of (2) Selecting neighbor points; Is vector quantity And (3) with And a bevel angle is formed.
7. The regional coverage path planning method based on dynamic networking under local communication according to claim 6, wherein in the step 6, the formula for calculating the boundary coverage rewards is: Wherein, the In order to select the number of neighbor points, For a preset maximum prize value component, Representation of Maximum number of possible neighbors of (a) Is that Is the jth neighbor point of (2) Number of uncovered neighbors.
8. The regional coverage path planning method based on dynamic networking in local communication according to claim 7, wherein the step 7 is to calculate the prize value components according to the steps 4-6 respectively , And Calculating neighbor points The total benefit of (2) is as follows: Wherein, the And The weight factors of the predation avoidance, the linear motion and the boundary coverage rewarding values respectively determine the importance degree of the foragers on different rewards when determining the next moving direction.
9. The regional coverage path planning method based on dynamic networking under local communication according to claim 8, wherein for the second case and the third case, a following escape mechanism is adopted, which is specifically implemented as follows: the area constituted by the dots is set as a coverage area, , And Three robots for performing path planning tasks, wherein For the robot involved in the deadlock, the coordinates of the three robots are respectively , And ; First, according to the formula of step 7, the free robot without deadlock is calculated preferentially , Respective optimal neighbor target points , And respectively set as the current positions; Then, the dead-lock robot is calculated according to the Euclidean distance calculation formula in the step 4 And (3) with , Is the Euclidean distance of (2) , ; If it is At this time, the robot Robot should follow Moving, i.e. following, robots Taking the position of the previous step as a reference point, moving to a neighbor target point in the same direction until the robot To the appropriate backtracking point of the uncovered area.

Description

Regional coverage path planning method based on dynamic networking under local communication Technical Field The invention relates to the field of regional coverage path planning of collaborative execution of group robots, in particular to a method for realizing regional coverage path planning of collaborative execution of group robots in a dynamic networking mode under the condition of local communication and only local communication. Background In real-world applications, autonomous navigational robots may accomplish many different types of tasks, such as environmental detection, disaster search and rescue, article handling, warehouse management, etc. And all tasks require that the robot can autonomously plan a moving path, reach a target position according to task requirements and execute corresponding operations. For planning of the moving path of the autonomous navigation robot, support of a path planning algorithm is required. From a task classification perspective, the goal of a full coverage path planning algorithm for a target area is to plan the shortest path of movement between the departure point and the target point. On the basis of completing path planning, an important study is made on optimizing path cost. The coverage path planning algorithm is an intelligent optimization algorithm, belongs to the derivative field of the problem of tourists, and solves the problem of regional coverage of unknown or known environments by using an autonomous entity robot system to perform autonomous navigation in the moving direction by using a specific sensor or communication device equipped with the autonomous entity robot system. Since its proposal, it has been extensively studied by the academia and widely used in the industry. In terms of the coverage path planning problem of the single robot, the technology at the present stage combines various strategies such as a traveler algorithm (TSP), an ant colony Algorithm (ACO), a Genetic Algorithm (GA), a K-Means algorithm and the like for optimizing the coverage path planning problem. However, if the area to be searched is large, the practical problems of low coverage efficiency, excessive power consumption and the like cannot be avoided. Therefore, the collaborative coverage path planning method of the group robot is paid importance to the academic world and industry, for example, in 2022, xie and the like, an improved genetic algorithm is proposed to solve the CPP problem of multiple unmanned aerial vehicles with energy constraint under multiple areas. In the same year, ma et al propose a co-coverage improved BA * algorithm (CCIBA *) for the co-coverage path planning problem of unmanned surface survey vehicles (USMV). 2023, cheng Xiaoming and the like introduce coverage detection problems of large three-dimensional structures into regional coverage realized by the group robots cooperatively, and propose a new method for solving coverage path planning problems based on an improved genetic algorithm. Although the coverage path planning problem of current group robots is intensively studied, most of the currently existing coverage path planning algorithms do not have the ability to enable the group robots to achieve complete coverage of an area with minimal path costs in case of local communication. Disclosure of Invention In order to solve the problems, the invention provides a method for realizing collaborative area coverage path planning by a group robot in a dynamic networking mode under the condition of local communication and only local communication. The technical principle of the invention is as follows: Based on predator-prey theory, all robots in the population will complete moving to their respective next target neighbor points simultaneously in each iteration cycle. Meanwhile, the selection of the target neighbor points is calculated by a total rewarding function and a communication constraint rule, wherein the total rewarding function is composed of three sub rewarding functions, the first rewarding function is related to movement of the robot away from predators (set virtual points) as far as possible so as to control movement trend of the robot and avoid inefficient turn-back coverage, the second rewarding function is related to continuous movement of the robot in the linear direction so that the robot can keep linear movement as far as possible, and the third rewarding function is related to the boundary of the robot covering as far as possible so as to further avoid turn-back coverage and fall into a deadlock situation. The total rewards function is used as a heuristic to guide the direction of movement coverage of the robot at each step. In the selection of the target neighbor points, another guiding factor is a local communication constraint rule among the group robots, and the algorithm constructs a dynamic networking model due to the limitation of the communication range among the robots, so that the robots can maintain networking communic