CN113110412A - Voronoi-APF algorithm-based group robot path planning method - Google Patents

Abstract

The invention relates to a Voronoi-APF algorithm-based group robot path planning method, which comprises the steps of firstly, utilizing a grid method to carry out environment modeling and preprocessing an obstacle; then, a Hungarian algorithm and a replacement strategy are adopted to assign the target to the group robots; finally, a Voronoi diagram is constructed through the real-time positions of the group robots, each robot carries out path planning by using an artificial potential field algorithm, the motion space of each robot is divided, and the paths of the robots are limited in the corresponding division space of the constructed Voronoi diagram, namely the robots stop moving to the end point or the boundary of the division space once; this step is repeated until all the group robots reach the designated end point. The invention has the improvement effect on time consumption and path length, and has certain optimization in the aspects of universality, time consumption and path consumption.

Description

Voronoi-APF algorithm-based group robot path planning method

Technical Field

The invention relates to the technical field of computer artificial intelligence, in particular to a group robot path planning method based on a Voronoi-APF algorithm.

Background

Self-assembly is an important research area in group robot collaboration, and path planning is particularly critical in order to achieve target configuration. Path planning and obstacle avoidance are core problems in this area. In a complex practical application environment, the problem of ensuring collision avoidance and avoidance of map obstacles among robots is more and more emphasized. An artificial potential field Algorithm (APF) and an improvement thereof are widely applied to robot path planning but are unsatisfactory in aspects of dynamic target assignment, iteration speed, robot shaking and the like, wherein in an OAPF algorithm, a distance factor means that a distance element is added in a repulsive force calculation formula of an original artificial potential field algorithm, and the introduction of the method leads the robot path planning to be highly closely related to a robot motion endpoint. While purely considering distance elements in a complex map does not necessarily result in optimal planning. For example, the peripheral robot can reach the terminal point preferentially, so that the inner robot can not enter the terminal point. When the robot needs to exchange target points after crossing complex terrain, if the dynamic assignment strategy is not considered, the robustness and convergence of the algorithm are influenced.

In terms of the collision avoidance problem, although the OAPF algorithm regards individuals other than the robot itself as obstacles, the collision problem is well solved. However, this means that in each iteration process, each robot needs to know the current positions of all other robots to construct a repulsive force field, and the problem of robot communication in practical situations is considered, which greatly limits the efficiency and practical application of the model.

In the OAPF algorithm, collision is avoided when the robots move simultaneously by limiting the moving step length of the robots in single iteration, and the complexity of the algorithm is greatly increased, so that the time overhead of completing target configuration is increased, meanwhile, the group robots gradually gather to increase the repulsive force between the robots, the robots are less likely to approach a target point, and the overhead in the aspect of the distance is increased.

From the above analysis, it can be known that the manual potential field improvement algorithm OAPF is not suitable for a dynamic target assignment strategy, and has a large improvement space in this respect, and secondly, the repulsive force between robots, although solving the problem of collision between robots, greatly reduces the performance of the algorithm and the feasibility of practical application.

Disclosure of Invention

The invention aims to overcome the defects and aims to provide a method for planning the path of the group robot based on the Voronoi-APF algorithm. And repeating the steps until all the robots reach the specified end point. The VAPF algorithm not only retains the advantages of the artificial potential field algorithm, but also realizes collision avoidance among robots. The improved effect of the matlab on time consumption and path length can be proved by matlab simulation comparison experiments. The invention has certain optimization in the aspects of universality, time consumption and distance consumption.

The invention achieves the aim through the following technical scheme: a group robot path planning method based on a Voronoi-APF algorithm comprises the following steps:

(1) carrying out environment modeling by using a grid method, and preprocessing the barrier;

(2) performing target assignment for the group robots by adopting a Hungarian algorithm and a replacement strategy;

(3) constructing a Voronoi diagram through the real-time positions of the group robots, respectively planning paths by using an artificial potential field algorithm for each robot, dividing the motion space of each robot, and limiting the paths in the corresponding division spaces of the constructed Voronoi diagram, namely stopping when the robots move to a terminal point or the boundary of the division spaces once; this step is repeated until all the group robots reach the designated end point.

Preferably, the group robot path planning method based on the Voronoi-APF algorithm further includes a step (4) of optimizing the motion control of the group robot to realize the motion control of the group robot.

Preferably, the step (1) is specifically as follows: the robot moves in 2D space, knowing: starting all robots; secondly, target configuration requirements; barrier information; the robot self-assembly environment is stored and expressed in a limited space, and a grid method is adopted for environment modeling: selecting a proper rectangular space, wherein the space comprises the first position and the second position, and dividing the environment into u multiplied by v grids; finally, a rectangular coordinate method is adopted to represent the grid position, and any grid can represent coordinates by using data pairs { x, y };

when the obstacle is preprocessed, the robot is regarded as a mass point, and expansion processing is carried out on the obstacle, namely the shape of the obstacle is kept unchanged, and the peripheral outline of the obstacle deviates outwards for a certain distance; after the expansion treatment is carried out on the obstacle, only the information of the obstacle which is increased after the expansion is reserved, and the information of the original obstacle is abandoned; after the environment modeling and the obstacle processing are based on the above, the follow-up work is developed based on the following four assumptions: the 2D plane is uniform and smooth except the obstacles; the robot can determine the self coordinate and the motion direction; the robot has enough capacity to complete the task; the self-assembly task may be completed.

Preferably, the step (2) is specifically as follows:

assume that there are N robots in the group robot, and the position set is S ═ S₁，S₂，...，S_NLet T ═ T be the target configuration set₁，T₂，...，T_NCompleting one-to-one corresponding target configuration in order to obtain the minimum cost, and converting the problem into an assignment problem;

for cost matrix

Wherein c is_i，jRepresentative robot S_iTo target T_jThe optimal assignment matrix X needs to be found, and the following formula needs to be satisfied:

according to the Conniger theorem: the maximum number of independent 0 elements in the coefficient matrix is equal to the minimum linear number capable of covering all 0 elements, and the process of calculating the assignment matrix by adopting the Hungarian algorithm is as follows:

(i) subtracting the minimum value of the row from all elements of each row of the cost matrix C, and subtracting the minimum value of the column from all elements of each column;

(ii) if N independent 0 elements can be found, the assignment can be made, where 0 element corresponds to X in the position _i，j1, other positions X_i，jWhen the value is 0, the assignment is finished;

(iii) for K (K < N) independent 0 elements, covering all 0 elements by K straight lines, finding the smallest uncovered element a, subtracting a from all elements of the uncovered row, and adding a to all elements of the covered column; (iii) returning to step (ii);

considering that the cost matrix can not be accurately obtained in a complex environment, a time threshold delta t for updating the target assignment is set, and if the current time exceeds the threshold delta t from the last target assignment time, the target assignment is performed again; secondly, the traditional cost matrix adopts Euclidean distance or Manhattan distance, which is shown as the following formula;

h_m＝d_x+d_y

wherein h is_oRepresents the Euclidean distance, h_mRepresenting the Manhattan distance, d_x，d_yRespectively representing the difference between the abscissa and ordinate of the starting point and the end point; the diagonal distance is used here, as shown in the following equation:

h_d＝D(d_x+d_y)+(D₂-2*D)*min(d_x，d_y) Wherein D represents the moving cost of the parallel movement of the robot, and D₂Representing the movement cost of the robot for diagonal movement; assignment matrix

And

are all optimal assignments;

if the assignment matrix X is selected₂Robot S₂Will block the robot S₁(ii) a Considering the practical requirements of self-assembly, the assignment matrix X should be chosen₁I.e. S₁→T₁，S₂→T₂(ii) a Under similar conditions, the result generated by the Hungarian algorithm may have a plurality of same optimal solution results, and a replacement strategy is introduced:

after the Hungarian algorithm is finished, if two pairs of target assignment S exist_a→T_y，S_b→T_zIf the following formula is satisfied, the target points of the two robots are exchanged, i.e. the assignment matrix is modified:

C_a，y+C_b，z＝C_a，z+C_y，b

abs(C_a，z-C_y，b)＜abs(C_a，y-C_b，z)。

preferably, the step (3) is specifically: through a robot current position set S, a Voronoi graph is constructed by adopting a Delaunay triangulation method, and a total space UU is divided into NN units V ═ V₁，V₂，...，V_nAnd the elements of the set S correspond to one-to-one elements of the set S, and satisfy the following formula:

V_i＝{p∈U|d(p，X_i)≤d(p，X_j)for all j≠i}

for each cell V_iAll of which are convex polygons; using a set of discrete nodes P ═ P₁，p₂，...，p_kRepresents; assuming that the discrete point set is ordered in a clockwise manner, and for any point Q in a unit, the following formula is constantly satisfied, then the point is located at V_iPerforming the following steps;

considering a single robot in a group as a node, constructing a Voronoi diagram based on the positions of the robot nodes has the following properties: the distance from any point in the Voronoi unit to the robot node of the unit is smaller than or equal to the distance from the point to the robot node of the adjacent unit, and the space plane is divided based on the position of the single robot node, so that one or only one robot node is generated in the Voronoi unit; therefore, the collision avoidance in the path planning of the group robot can be restricted by using the geometric characteristics among the node relations or units in the Voronoi diagram;

each robot carries out path planning in a corresponding unit by using an artificial potential field algorithm, and when the robot reaches a corresponding terminal or exceeds a motion range, the single iterative motion of the robot is ended; it should be noted that when the robot moves towards the boundary in the Voronoi diagram at the same time, there is a very small probability that the robot collides with the boundary, and at this time, the robot may adopt a small amount of retraction operation to avoid collision.

Preferably, in the step (4), when the direction of the force applied to the robot and the direction of the movement are always obtuse, a shaking phenomenon occurs, and therefore, in the optimization, a movement control formula shown in the following formula is used to solve the shaking problem:

90°≤|Δθ|≤180°

wherein, x (t), y (t) represent the current position of the robot, x (t +1), y (t +1) represent the position to which the robot is to arrive; theta (t) represents the current movement direction of the robot, delta theta represents the movement direction of the robot to be changed when the robot reaches the next step position, and l represents the movement distance of the robot; when the robot changes the movement direction to be an acute angle, the movement rule is not changed, and when the robot changes the movement direction to be an obtuse angle, the change direction is limited to be at most a right angle; τ represents an adjustment parameter; based on the motion rule, the robot moves by adopting a two-step method: the direction requirement is met through rotation, and then the displacement requirement is met through linear motion.

The invention has the beneficial effects that: (1) the method introduces a dynamic target assignment strategy, constructs a cost matrix through the diagonal distance between the real-time position of the group robot and the targets, uses a Hungarian algorithm to perform optimal assignment, and uses a replacement strategy to optimize the target assignment aiming at the condition of multiple optimal solutions; (2) the method introduces Voronoi constraint to ensure collision avoidance among robots, constructs a Voronoi diagram through real-time positions of group robots, and limits the single iterative motion range of a single robot in a cell corresponding to the Voronoi diagram; the method not only ensures avoidance between robots, but also greatly improves the single iterative motion range of the robots; (3) the invention introduces a motion control method to solve the problem of robot shaking, divides a motion strategy by changing the size of a motion angle through the robot, limits the motion angle and reduces the motion step length when the shaking phenomenon occurs when the angle is too large.

Drawings

FIG. 1 is a schematic flow diagram of the process of the present invention;

FIG. 2 is a schematic diagram of obstacle handling according to an embodiment of the present invention;

FIG. 3 is a diagram illustrating a special case of target assignment according to an embodiment of the present invention;

FIG. 4 is a schematic diagram of a linear self-assembly implemented by the VAPF algorithm according to an embodiment of the present invention;

FIG. 5 is a schematic diagram of a VAPF algorithm implementing H-type self-assembly according to an embodiment of the present invention;

FIG. 6 is a schematic diagram of a VAPF algorithm implementing irregular self-assembly according to an embodiment of the present invention;

FIG. 7 is a comparison graph of algorithm time consumption for an embodiment of the present invention;

FIG. 8 is an algorithmic distance consumption comparison graph of an embodiment of the present invention.

Detailed Description

The invention will be further described with reference to specific examples, but the scope of the invention is not limited thereto:

example (b): as shown in fig. 1, a group robot path planning method based on a Voronoi-APF algorithm includes firstly using a hungarian algorithm and a replacement policy to designate target points for each robot, then constructing a Voronoi diagram through real-time positions of the group robots, respectively using an artificial potential field algorithm to plan paths of the robots, and limiting the paths to be in a corresponding partitioned space of the constructed Voronoi diagram, that is, the robots stop when moving to a terminal point or a boundary of a partitioned space once. And repeating the steps until all the robots reach the specified end point. The VAPF algorithm not only retains the advantages of the artificial potential field algorithm, but also realizes collision avoidance among robots. The improved effect of the matlab on time consumption and path length can be proved by matlab simulation comparison experiments. The method comprises the following steps:

the method comprises the following steps: environmental modeling and obstacle pre-processing

The robot moves in 2D space, knowing: starting all robots; secondly, target configuration requirements; and obstacle information. The robot self-assembly environment can be stored and expressed by using a limited space, and the invention adopts a grid method to carry out environment modeling.

And selecting a proper rectangular space to satisfy the condition that the space contains the position I and the position II, and dividing the environment into u multiplied by v grids. And finally, representing the grid position by adopting a rectangular coordinate method, wherein any grid can represent coordinates by using data pairs { x, y }.

In order to simplify the problem, the robot is regarded as a mass point, and in order to ensure that the robot and the obstacle avoid collision, the obstacle needs to be subjected to expansion treatment, namely, the shape of the obstacle is kept unchanged, and the peripheral outline of the obstacle is outwards shifted by a certain distance. In consideration of unpredictability of the barrier, the expansion processing is beneficial to keeping a safe distance between the robot and the barrier, and risks can be avoided in time.

Secondly, the obstacle cannot cross and the initial position of the robot is not in the obstacle, so that only the peripheral outline information of the obstacle is necessary information for planning the path of the robot. Therefore, the present invention retains only the information of the obstacle added after the expansion of the obstacle, and discards the original obstacle information. The data volume of the environmental information is greatly reduced, and the robot can perform more efficient path planning. An example of obstacle handling is shown in fig. 2.

Based on the above environmental modeling and obstacle handling, the follow-up work will be developed based on four assumptions: the 2D plane is uniform and smooth except the obstacles; the robot can determine the self coordinate and the motion direction; the robot has enough capacity to complete the task; the self-assembly task may be completed.

Step two: target assignment

Assume that there are N robots in the group robot, and the position set is S ═ S₁，S₂，...，S_NLet T ═ T be the target configuration set₁，T₂，...，T_NAnd if the target configuration corresponding to one is completed with minimum cost, the problem is converted into an assignment problem.

For cost matrix

Wherein c is_i，jRepresentative robot s_iTo target T_jTo find the optimal assignment matrix X, equations (1) and (2) are satisfied.

According to the Conniger theorem: the maximum number of independent 0 elements in the coefficient matrix is equal to the minimum linear number capable of covering all 0 elements, and the process of calculating the assignment matrix by adopting the Hungarian algorithm comprises the following steps:

2.1): the cost matrix C subtracts the row minimum value from all elements in each row and subtracts the column minimum value from all elements in each column.

2.2): if N independent 0 elements can be found, the assignment can be made, where 0 element corresponds to X in the position _i，j1, other positions X _i，j0. The assignment is ended.

2.3): for K (K < N) individual 0 elements, all 0 elements are covered with K straight lines, then the smallest uncovered element a is found, all elements of the uncovered row are subtracted by a, and all elements of the covered column are added by a. And returning to the step two.

Considering that the cost matrix cannot be accurately obtained in a complex environment, the algorithm of the invention sets a time threshold delta t for updating the target assignment, and if the current time exceeds the threshold delta t from the last target assignment time, the target assignment is performed again. Secondly, the traditional cost matrix generally adopts the euclidean distance or the manhattan distance, as shown in formula (3) and formula (4).

(3)

h_m＝d_x+d_y

(4)

Wherein h is_oRepresents the Euclidean distance, h_mRepresenting the Manhattan distance, d_x，d_yRespectively, the differences between the abscissa and ordinate of the starting point and the ending point. The euclidean distance represents a straight line distance between two points, and does not consider the influence of an obstacle, and the square root operation increases the amount of calculation. The manhattan distance only considers the motion in four directions, does not consider the diagonal motion, is not practical and is not beneficial to target assignment. In order to be closer to the actual situation and ensure the simplicity and high efficiency of the operation, the invention adopts the diagonal distance as shown in the formula (5).

h_d＝D(d_x+d_y)+(D₂-2*D)*min(d_x，d_y)

(5)

Wherein D represents the moving cost of the parallel movement of the robot, and D₂Representing the movement cost of the robot for making a diagonal movement.

Considering the special case shown in FIG. 3, the assignment matrix

And

are all optimally assigned.

If the assignment matrix X is selected₂Robot S₂Will block the robot S₁. Considering the practical requirements of self-assembly, the assignment matrix X should be chosen₁I.e. S₁→T₁，S₂→T₂. Under the similar condition, the result generated by the Hungarian algorithm can have a plurality of same optimal solution results, and the invention provides a replacement strategy.

After the Hungarian algorithm is finished, if two pairs of target assignment S exist_a→T_y，S_b→T_sIf equations (6) and (7) are satisfied, the target points of the two robots are exchanged, i.e. the assignment matrix is modified.

C_a，y+C_b，z＝C_a，z+C_y，b

(6)

abs(C_a，zC_y，b)＜abs(C_a，y-C_b，z)

(7)

Through the strategy, the running distance of each robot can be effectively balanced, and the problems caused by the special conditions are solved.

Step three: motion space partitioning and path planning

Through the current position set S of the robot, a Voronoi graph is constructed by using a Delaunay triangulation method, and a full space U is divided into N units V ═ V₁，V₂，...，V_nAnd (5) corresponding to the elements of the set s one by one, and satisfying the formula (8).

V_i＝{p∈U|d(p，X_i)≤d(p，X_j)for all j≠i}

(8)

For each cell V_iAll of which are convex polygons. Because of the unit V_iIs a convex polygon, so a set of discrete nodes P ═ P can be used₁，p₂，...，p_kRepresents it. Assuming that the discrete point set is sorted in a clockwise order, for any point Q in a cell, the equation (9) is constantly satisfied, then that pointAt V_iIn (1).

Considering a single robot in a group as a node, constructing a Voronoi diagram based on the robot node positions has the following properties: the distance from any point in the Voronoi unit to the robot node of the unit is smaller than or equal to the distance from the point to the robot node of the adjacent unit, and the space plane is divided based on the position of the single robot node, so that one and only one robot node in the Voronoi unit is generated. Therefore, the collision avoidance in the path planning of the group robot can be restricted by using the geometrical characteristics among the node relations or units in the Voronoi diagram.

And each robot carries out path planning in the corresponding unit by using an artificial potential field algorithm, and when the robot reaches the corresponding end point or exceeds the motion range, the single iteration motion of the robot is ended. The specific algorithm (single-robot single-iteration motion flow) of the artificial potential field algorithm is shown in table 1.

TABLE 1

It should be noted that when the robot moves towards the boundary in the Voronoi diagram at the same time, there is a very small probability that the robot collides with the boundary, and at this time, the robot may adopt a small amount of retraction operation to avoid collision.

Step four: motion control of group robots

After collision avoidance and obstacle avoidance are completed, the invention researches the motion control of the group robot. In the artificial potential field algorithm, when the direction of the force applied to the robot and the moving direction always form an obtuse angle, a shaking phenomenon occurs, especially when an obstacle exists between the robot and a target point. In practical applications, the robot is expected to have a relatively smooth path, and the shaking phenomenon is not beneficial to the movement of the robot. The invention provides a motion control method as shown in formulas (10) and (11) to solve the problem of jitter.

Wherein, x (t), y (t) represent the current position of the robot, x (t +1), y (t +1) represent the position to which the robot is to arrive; theta (t) represents the current movement direction of the robot, delta theta represents the movement direction of the robot to be changed when the robot reaches the next step position, and l represents the movement distance of the robot; when the robot changes the movement direction to be an acute angle, the movement rule is not changed, and when the robot changes the movement direction to be an obtuse angle, the change direction is limited to be at most a right angle; tau represents an adjusting parameter, when the robot shakes possibly, the movement step length of the robot is limited, and the shaking phenomenon can be effectively relieved.

Based on the motion rule, the robot moves by adopting a two-step method: the direction requirement is met through rotation, and then the displacement requirement is met through linear motion. By adopting the method for controlling, the control difficulty of the robot can be effectively reduced, and the cost of a single robot can be controlled.

The invention carries out simulation experiment on matlab platform. Experiments ensure that the operation environment of the algorithm is unchanged and good parameters are set. Table 2 shows a list of parameters of the VAPF algorithm.

TABLE 2

The robot self-assembly environment is set to 500 × 500 grid graph, in which a plurality of circles are irregularly distributed to represent obstacles on the map. The initial positions of the robots are distributed randomly, but the robots are not arranged in the obstacles, and the number of target points is the same as that of the robots.

The experiment adopts the linear type, the H type and the irregular type in the self-assembly problem to carry out the comparison experiment. The linear type and the H type are the simplest conventional models, the accuracy, the stability and the performance of the algorithm can be effectively tested, and the composition of the simple models can simulate the movement mode of animals, so that the method has wide application prospect. The linear type and H type models of the experimental design are uniformly distributed, and the irregular target points are not uniformly distributed, but are configured in a surrounding type self-assembly manner to a certain extent, so that the performance of the algorithm on the target assignment problem can be effectively tested. Examples of the three types of model experiments are shown in fig. 4, 5, and 6. In the figure, the black circles represent the obstacles after pretreatment; the black solid lines represent the respective planned paths of the robots; the markers at the end of the solid line represent experimentally set target points; different color blocks are constructed by Voronoi diagrams and represent respective motion ranges of the robot, so that the robot can be effectively helped to realize collision avoidance.

According to the results, the robots can efficiently and safely reach respective target points under different self-assembly models by using the VAPF algorithm. The target assignment strategy enables the consumption of the robots reaching the target points to be balanced to the maximum extent; the motion space division can effectively avoid collision; the motion control method can effectively inhibit the robot from shaking during path planning.

Aiming at the experimental model, the experiment compares the performances of the VAPF algorithm and the OAPF algorithm in terms of time and distance by continuously increasing the number of robots. The data of the experimental results are shown in fig. 7 and 8. From the comparative experiments, it can be seen that the time consumption aspect: the time consumption of the two algorithms is increased along with the increase of the number of robots, the time consumption of the OAPF algorithm is approximately in an exponential growth trend, and the time consumption acceleration of the VAPF algorithm is far lower than that of the OAPF algorithm. The performance difference of the two algorithms is particularly obvious when the number of robots is relatively small. The VAPF divides the motion space through the Voronoi diagram, the relatively small number of robots means that the distribution is relatively sparse, and each robot has a larger independent motion space in a single iteration. Efficient iterative performance makes the joining of a small number of group robots have little impact on the VAPF algorithm performance, so in fig. 7, when the number of robots is less than 20, the time consumption is substantially unchanged. In the OAPF algorithm, repulsion among robots is considered in each iteration, the motion space of a single iteration is extremely small, and even the addition of a small number of group robots seriously aggravates the time consumption of the algorithm. H-type self-assembly is more complex than linear self-assembly, and irregular self-assembly is even more, the time consumption of the OAPF algorithm is greatly increased by the complex self-assembly requirement, while the VAPF algorithm has stable performance under different self-assembly requirements and is far superior to the OAPF algorithm. Average path length: the distribution of the robots has a relatively important influence on the results, and as the number of robots increases, a random and uniform distribution makes the average distance of the robots more stable. Due to repulsion between robots in the OAPF algorithm, the average path length of the OAPF algorithm is more than that of the VAPF algorithm, and the OAPF algorithm is particularly obvious in complex self-assembly experiments.

Through the experimental comparison analysis, the VAPF algorithm has obvious advantages in time consumption and path length, and has good adaptability to different self-assembly requirements and the scale of the group robot. In general, the VAPF algorithm meets the requirements of collision avoidance and obstacle avoidance in the self-assembly process, has obvious superiority in performance and has a certain application prospect.

While the invention has been described in connection with specific embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.

Claims (6)

1. A group robot path planning method based on a Voronoi-APF algorithm is characterized by comprising the following steps:

(1) carrying out environment modeling by using a grid method, and preprocessing the barrier;

(2) performing target assignment for the group robots by adopting a Hungarian algorithm and a replacement strategy;

(3) constructing a Voronoi diagram through the real-time positions of the group robots, respectively planning paths by using an artificial potential field algorithm for each robot, dividing the motion space of each robot, and limiting the paths in the corresponding division spaces of the constructed Voronoi diagram, namely stopping when the robots move to a terminal point or the boundary of the division spaces once; this step is repeated until all the group robots reach the designated end point.

2. The group robot path planning method based on the Voronoi-APF algorithm as claimed in claim 1, wherein: the group robot path planning method based on the Voronoi-APF algorithm further comprises the step (4) of optimizing the motion control of the group robot to realize the motion control of the group robot.

3. The group robot path planning method based on the Voronoi-APF algorithm as claimed in claim 1, wherein: the step (1) is specifically as follows: the robot moves in 2D space, knowing: starting all robots; secondly, target configuration requirements; barrier information; the robot self-assembly environment is stored and expressed in a limited space, and a grid method is adopted for environment modeling: selecting a proper rectangular space, wherein the space comprises the first position and the second position, and dividing the environment into u multiplied by v grids; finally, a rectangular coordinate method is adopted to represent the grid position, and any grid can represent coordinates by using data pairs { x, y };

when the obstacle is preprocessed, the robot is regarded as a mass point, and expansion processing is carried out on the obstacle, namely the shape of the obstacle is kept unchanged, and the peripheral outline of the obstacle deviates outwards for a certain distance;

after the expansion treatment is carried out on the obstacle, only the information of the obstacle which is increased after the expansion is reserved, and the information of the original obstacle is abandoned; after the environment modeling and the obstacle processing are based on the above, the follow-up work is developed based on the following four assumptions: the 2D plane is uniform and smooth except the obstacles; the robot can determine the self coordinate and the motion direction; the robot has enough capacity to complete the task; the self-assembly task may be completed.

4. The group robot path planning method based on the Voronoi-APF algorithm as claimed in claim 1, wherein: the step (2) is specifically as follows:

assume that there are N robots in the group robot, and the position set is S ═ S₁，S₂，...，S_NLet T ═ T be the target configuration set₁，T₂，...，T_NCompleting one-to-one corresponding target configuration in order to obtain the minimum cost, and converting the problem into an assignment problem;

for cost matrix

Wherein c is_i，jRepresentative robot S_iTo target T_jThe optimal assignment matrix X needs to be found, and the following formula needs to be satisfied:

according to the Conniger theorem: the maximum number of independent 0 elements in the coefficient matrix is equal to the minimum linear number capable of covering all 0 elements, and the process of calculating the assignment matrix by adopting the Hungarian algorithm is as follows:

(i) subtracting the minimum value of the row from all elements of each row of the cost matrix C, and subtracting the minimum value of the column from all elements of each column;

(ii) if N independent 0 elements can be found, the assignment can be made, where 0 element corresponds to X in the position_i，j1, other positions X_i，jWhen the value is 0, the assignment is finished;

(iii) for K (K < N) independent 0 elements, covering all 0 elements by K straight lines, finding the smallest uncovered element a, subtracting a from all elements of the uncovered row, and adding a to all elements of the covered column; (iii) returning to step (ii);

considering that the cost matrix can not be accurately obtained in a complex environment, a time threshold delta t for updating the target assignment is set, and if the current time exceeds the threshold delta t from the last target assignment time, the target assignment is performed again; secondly, the traditional cost matrix adopts Euclidean distance or Manhattan distance, which is shown as the following formula;

h_m＝d_x+d_y

wherein h is_oRepresents the Euclidean distance, h_mRepresenting the Manhattan distance, d_x，d_yRespectively representing the difference between the abscissa and ordinate of the starting point and the end point; the diagonal distance is used here, as shown in the following equation:

h_d＝D(d_x+d_y)+(D₂-2*D)*min(d_x，d_y)

wherein D represents the moving cost of the parallel movement of the robot, and D₂Representing the movement cost of the robot for diagonal movement; assignment matrix

And

are all optimal assignments;

if the assignment matrix X is selected₂Robot S₂Will block the robot S₁(ii) a Considering the practical requirements of self-assembly, the assignment matrix X should be chosen₁I.e. S₁→T₁，S₂→T₂(ii) a Under similar conditions, the result generated by the Hungarian algorithm may have a plurality of same optimal solution results, and a replacement strategy is introduced:

after the Hungarian algorithm is finished, if two pairs of target assignment S exist_a→T_y，S_b→T_zIf the following formula is satisfied, the target points of the two robots are exchanged, i.e. the assignment matrix is modified:

C_a，y+C_b，z＝C_a，z+C_y，b

abs(C_a，z-C_y，b)＜abs(C_a，y-C_b，z)。

5. the group robot path planning method based on the Voronoi-APF algorithm as claimed in claim 1, wherein: the step (3) is specifically as follows: through a robot current position set S, a Voronoi graph is constructed by adopting a Delaunay triangulation method, and a total space UU is divided into NN units V ═ V₁，V₂，...，V_nAnd the elements of the set S correspond to one-to-one elements of the set S, and satisfy the following formula:

V_i＝{p∈U|d(p，X_i)≤d(p，X_j)for all j≠i}

for each cell V_iAll of which are convex polygons; using a set of discrete nodes P ═ P₁，p₂，...，p_kRepresents; assuming that the discrete point set is ordered in a clockwise manner, and for any point Q in a unit, the following formula is constantly satisfied, then the point is located at V_iPerforming the following steps;

considering a single robot in a group as a node, constructing a Voronoi diagram based on the positions of the robot nodes has the following properties: the distance from any point in the Voronoi unit to the robot node of the unit is smaller than or equal to the distance from the point to the robot node of the adjacent unit, and the space plane is divided based on the position of the single robot node, so that one or only one robot node is generated in the Voronoi unit; therefore, the collision avoidance in the path planning of the group robot can be restricted by using the geometric characteristics among the node relations or units in the Voronoi diagram;

each robot carries out path planning in a corresponding unit by using an artificial potential field algorithm, and when the robot reaches a corresponding terminal or exceeds a motion range, the single iterative motion of the robot is ended; it should be noted that when the robot moves towards the boundary in the Voronoi diagram at the same time, there is a very small probability that the robot collides with the boundary, and at this time, the robot may adopt a small amount of retraction operation to avoid collision.

6. The group robot path planning method based on the Voronoi-APF algorithm as claimed in claim 2, wherein: in the step (4), when the robot motion is controlled, when the direction of the robot force and the motion direction always form an obtuse angle, a shaking phenomenon occurs, and therefore, in optimization, a motion control formula shown in the following formula is adopted to solve the shaking problem:

90°≤|Δθ|≤180°

wherein, x (t), y (t) represent the current position of the robot, x (t +1), y (t +1) represent the position to which the robot is to arrive; theta (t) represents the current movement direction of the robot, delta theta represents the movement direction of the robot to be changed when the robot reaches the next step position, and l represents the movement distance of the robot; when the robot changes the movement direction to be an acute angle, the movement rule is not changed, and when the robot changes the movement direction to be an obtuse angle, the change direction is limited to be at most a right angle; τ represents an adjustment parameter; based on the motion rule, the robot moves by adopting a two-step method: the direction requirement is met through rotation, and then the displacement requirement is met through linear motion.

Images