CN116360437A - Intelligent robot path planning method, device, equipment and storage medium - Google Patents

Abstract

The invention belongs to the technical field of intelligent robots, and discloses an intelligent robot path planning method, an intelligent robot path planning device, intelligent robot path planning equipment and a storage medium. According to the invention, the initial position and the target position of the intelligent robot are obtained, the initial position and the target position are searched based on an improved Harriset algorithm in an intelligent path planning model, an initial planning path is generated, the improved Harriset algorithm comprises the steps of replacing random parameters in an original Harriset algorithm to initialize a population to obtain an initial population sequence, adding elite reverse learning strategies to update the population, and determining a global optimal path based on the initial planning path, so that the problems that the random parameters cannot completely traverse all the section spaces for initializing the population, the obtained population is uneven in distribution and the population falls into an early state, so that the population has higher quality and diversity, higher searching speed and convergence precision compared with the prior art, and the path optimizing capability of the intelligent robot is improved.

Description

Intelligent robot path planning method, device, equipment and storage medium

technical field

The present invention relates to the technical field of intelligent robots, in particular to an intelligent robot path planning method, device, equipment and storage medium.

Background technique

In recent years, with the rapid development of the information industry and industrial technology, intelligent robots have been widely used in many fields, such as logistics distribution, hotel delivery, warehouse management and other scenarios.

In this type of problem, the robot needs to find a shortest path between a given starting point and a goal point, usually avoiding different types of obstacles on the road, and in some cases time The balance between cost and transportation cost, or the optimal routing problem for multi-objective problems, their results are often diverse, so there are different choices for path planning methods. Traditional path planning methods such as dijsktra algorithm, A* algorithm, etc., have the disadvantages of low efficiency and slow speed. In real scenes, robots perform poorly when searching for paths, and cannot solve the problem of intelligent robots in static scenes. Excellent process.

The above content is only used to assist in understanding the technical solution of the present invention, and does not mean that the above content is admitted as prior art.

Contents of the invention

The main purpose of the present invention is to provide a path planning method, device, equipment and storage medium for an intelligent robot, aiming at solving the technical problem in the prior art that the intelligent robot performs poorly in finding the path in the display scene.

To achieve the above object, the present invention provides a method for path planning of an intelligent robot, said method comprising the following steps:

Obtain the initial position and target position of the intelligent robot;

Based on the improved Harris Eagle algorithm in the intelligent path planning model, the initial position and the target position are routed to generate an initial planning path. The improved Harris Eagle algorithm includes replacing the original Harris Eagle algorithm with random parameters to initialize the population. , get the initial population sequence, add the elite reverse learning strategy to update the population;

A globally optimal path is determined based on the initial planned path.

Optionally, the improved Harris Eagle algorithm based on the intelligent path planning model performs pathfinding on the initial position and the target position, and generates an initial planning path, including:

Obtain obstacle information in the real scene, and create a static grid map based on the obstacle information;

Setting preset populations in the static grid map;

Initializing the preset population to obtain an initialized population, the population includes at least one individual;

When the current number of iterations does not reach the maximum number of iterations, the fitness of each individual in the population is obtained according to the limit of the search space;

updating the escape energy of each individual in the population, executing a round-up strategy according to the escape energy, and obtaining the position of each individual in the population;

An initial planned path is generated based on the position.

Optionally, the improved Harris Eagle algorithm includes replacing the original Harris Eagle algorithm with random parameters to initialize the population to obtain an initial population sequence, including:

Set the initial population sequence and iteration parameters;

Iterating the initial population sequence according to the iteration parameters and the objective function to obtain the offspring population sequence, and updating the current number of iterations;

When the current number of iterations is equal to the maximum number of iterations, an initial population sequence is generated according to the child population sequence.

Optionally, the iterating the initial population sequence according to the iteration parameter and the objective function to obtain the offspring population sequence includes:

obtaining the relative average position of the individual in the population according to the current position of the individual in the population;

Obtain the next iteration position of the individual according to the current position of the individual in the population, the current number of iterations, the position of the prey and the relative average position;

Select elite individuals according to the fitness and the next iteration position;

Obtain the reverse population according to the boundary between the elite individual and the static grid map;

The population sequence after iterating the reverse population and the initial population sequence is used to obtain the descendant population sequence.

Optionally, the obtaining the fitness of each individual in the population according to the limit of the search space includes:

obtaining the corresponding moving distance according to the current position and the initial position of each individual in the population;

The fitness of each individual in the population is obtained according to the moving distance and the limit of the search space.

Optionally, the updating the escape energy of each individual in the population, executing a round-up strategy according to the escape energy, obtaining the position of each individual in the population, and generating an initial planning path according to the position includes:

Obtain the escape energy of each individual according to the current number of iterations and the maximum number of iterations of each individual in the population;

When the escape energy is greater than the preset swooping and encircling energy, adopt a encircling strategy, adjust the escape energy and obtain the encircled position;

When the escape energy is less than the preset swooping and rounding up energy, adopt a swooping and rounding up strategy, adjust the escape energy and obtain the position after rounding up;

An initial planned path is generated according to the captured position.

Optionally, the determining the global optimal path based on the initial planning path includes:

Obtaining the current position of each individual in the population, obtaining the moving distance according to the current position and the initial position, and storing the current position, the initial position and the moving distance in a taboo table;

The moving distances in the taboo table are compared, and when there is no obstacle on the current path, the shortest path among the moving distances is taken as the globally optimal path.

In addition, in order to achieve the above purpose, the present invention also proposes an intelligent robot path planning device, which includes:

The position obtaining module is used to obtain the initial position and the target position of the intelligent robot;

The path planning module is used to find the initial position and the target position based on the improved Harris Eagle algorithm in the intelligent path planning model, and generate an initial planned path. The improved Harris Eagle algorithm includes replacing the original Harris Eagle algorithm. Random parameters are used to initialize the population to obtain the initial population sequence, and the elite reverse learning strategy is added to update the population;

A path determination module, configured to determine a globally optimal path based on the initial planned path.

In addition, in order to achieve the above object, the present invention also proposes a path planning device for an intelligent robot, which includes: a memory, a processor, and an intelligence stored in the memory and operable on the processor. A robot path planning program, the intelligent robot path planning program is configured to implement the steps of the above-mentioned intelligent robot path planning method.

In addition, in order to achieve the above object, the present invention also proposes a storage medium, on which an intelligent robot path planning program is stored, and when the intelligent robot path planning program is executed by a processor, the intelligent robot path as described above is realized. Steps of the planning method.

The present invention obtains the initial position and the target position of the intelligent robot, searches the initial position and the target position based on the improved Harris Eagle algorithm in the intelligent path planning model, and generates an initial planning path, and the improved Harris Eagle algorithm includes replacing the original In the Harris Eagle algorithm, random parameters are used to initialize the population to obtain the initial population sequence, and the elite reverse learning strategy is added to update the population, and the global optimal path is determined based on the initial planning path, which can solve the problem that random parameters cannot initialize the population. Completely traversing all knotted spaces, resulting in uneven distribution of the population, and the population falls into a premature state, so that the population has higher quality and diversity. Compared with the prior art, the present invention has higher search speed and convergence accuracy, and improves the intelligence of intelligent robots. Path finding ability.

Description of drawings

Fig. 1 is a schematic structural diagram of an intelligent robot path planning device for a hardware operating environment involved in the solution of an embodiment of the present invention;

Fig. 2 is a schematic flow chart of the first embodiment of the intelligent robot path planning method of the present invention;

Fig. 3 is a schematic flow chart of the second embodiment of the intelligent robot path planning method of the present invention;

Fig. 4 is a path optimization flow chart of an embodiment of the intelligent robot path planning method of the present invention;

5 is a schematic diagram of a grid map of an embodiment of an intelligent robot path planning method according to the present invention;

Fig. 6 is a control diagram of population initialization of an embodiment of the intelligent robot path planning method of the present invention;

Fig. 7 is a structural block diagram of the first embodiment of the intelligent robot path planning device of the present invention.

The realization of the purpose of the present invention, functional characteristics and advantages will be further described in conjunction with the embodiments and with reference to the accompanying drawings.

Detailed ways

It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

Referring to FIG. 1 , FIG. 1 is a schematic structural diagram of an intelligent robot path planning device in a hardware operating environment involved in an embodiment of the present invention.

As shown in FIG. 1 , the intelligent robot path planning device may include: a processor 1001 , such as a central processing unit (Central Processing Unit, CPU), a communication bus 1002 , a user interface 1003 , a network interface 1004 , and a memory 1005 . Wherein, the communication bus 1002 is used to realize connection and communication between these components. The user interface 1003 may include a display screen (Display), an input unit such as a keyboard (Keyboard), and the optional user interface 1003 may also include a standard wired interface and a wireless interface. The network interface 1004 may optionally include a standard wired interface and a wireless interface (such as a Wireless-Fidelity (Wi-Fi) interface). The memory 1005 may be a high-speed random access memory (Random Access Memory, RAM) memory, or a stable non-volatile memory (Non-Volatile Memory, NVM), such as a disk memory. Optionally, the memory 1005 may also be a storage device independent of the aforementioned processor 1001 .

Those skilled in the art can understand that the structure shown in Figure 1 does not constitute a limitation to the intelligent robot path planning device, and may include more or less components than shown in the illustration, or combine certain components, or arrange different components .

As shown in FIG. 1 , the memory 1005 as a storage medium may include an operating system, a network communication module, a user interface module, and an intelligent robot path planning program.

In the intelligent robot path planning device shown in Figure 1, the network interface 1004 is mainly used for data communication with the network server; the user interface 1003 is mainly used for data interaction with the user; the processor 1001 in the intelligent robot path planning device of the present invention . The memory 1005 can be set in the intelligent robot path planning device. The intelligent robot path planning device invokes the intelligent robot path planning program stored in the memory 1005 through the processor 1001, and executes the intelligent robot path planning method provided by the embodiment of the present invention.

An embodiment of the present invention provides a path planning method for an intelligent robot. Referring to FIG. 2 , FIG. 2 is a schematic flowchart of a first embodiment of a path planning method for an intelligent robot according to the present invention.

In this embodiment, the intelligent robot path planning method includes the following steps:

Step S10: Obtain the initial position and target position of the intelligent robot.

It should be noted that the execution subject of this embodiment is an intelligent robot path planning device, wherein the intelligent robot path planning device has functions such as data processing, data communication and program operation, and the intelligent robot path planning device can be an integrated controller , to control devices such as computers, of course, may also be other devices with similar functions, which is not limited in this embodiment.

It can be understood that the initial position refers to the starting point of the intelligent robot in this path planning, that is, the intelligent robot will start to move from the initial position, and the target position refers to the starting point of the intelligent robot. The location to be reached.

In a specific implementation, when the intelligent robot obtains the initial position and the target position, it can obtain the initial position and the target position of the intelligent robot through the intelligent robot and an external communication device, and the intelligent robot can also With the ability of autonomous positioning, it can determine the current position and target position of the intelligent robot. In the actual process of path planning, there may be many forms. Generally speaking, the starting position of an intelligent robot is only One, starting from this point, perform corresponding work tasks, the function of the intelligent robot is determined according to the actual situation. This embodiment does not limit this. This embodiment takes the example of carrying goods for illustration, and the intelligent robot starts from the starting position , looking for goods, and transporting the goods to the designated location. In this process, it may be necessary to go to the intermediate node to complete the action of loading or unloading the goods. Therefore, the number of intermediate nodes is not fixed, so in actual scenarios, usually at least Including the following situations: one starting point, one target point; one starting point, one intermediate point, one target point; one starting point, multiple intermediate points, one target point; one starting point, multiple intermediate points, multiple target point, therefore, the number of the target position is at least one, and the delivery task is completed when the intelligent robot has traversed all the target points.

Step S20: Based on the improved Harris Eagle algorithm in the intelligent path planning model, pathfinding is performed on the initial position and the target position, and an initial planning path is generated. The improved Harris Eagle algorithm includes replacing the original Harris Eagle algorithm with a pair of random parameters The population is initialized to obtain the initial population sequence, and the elite reverse learning strategy is added to update the population.

It should be noted that the initial path refers to a path generated according to the initial position and the target position. For the same initial position and the target position, multiple initial paths may be generated, and the multiple The initial paths are different from each other.

In a specific implementation, the intelligent path planning model includes three stages, namely, an exploration stage, a transition stage from exploration to development, and a development stage. First of all, in the exploration stage, the population can be randomly distributed in the space to initialize the population, and monitor the surrounding environment, waiting for the appearance of prey. And two different strategies can be used to detect prey, namely:

Among them, t is the current iteration number, which is the current position of the eagle, indicating the next iteration position, which is the position of the prey (hare), r _i ∈ (0,1), (i=1,2,3,4), q∈(0,1), UB and LB are the upper and lower limits of variables respectively, and Xrand(t) represents an individual randomly selected from the current population.

In the second stage, while the Harris hawk is catching the prey, the prey will run away and consume energy. The energy loss model is:

Among them, t is the current number of iterations, T is the maximum number of iterations, E ₀ is the initial energy of the prey, each iteration of E ₀ changes randomly within the range of (-1,1), when E ₀ ∈ (0→-1 ), the prey is being marked and tracked by the hawks; when E ₀ ∈ (0→1), the prey is in a safe state and recovering energy. The escape energy of the prey changes dynamically, but generally shows a decreasing trend until the physical strength decreases to 0 or is caught by the eagle. When |E|>1, the algorithm is in the exploration stage; when |E|<1, the algorithm is in the development stage.

In the third phase, the Harris hawk will surround and attack prey that has been tracked in the previous phase. Predict the escape direction of the prey according to the remaining escape energy of the prey, and launch a dive attack on the prey from different directions or angles. The algorithm simulates the process of hunting prey with four attack strategies. r is used to represent the chance of the prey escaping, r ≥ 0.5 represents the case where the prey escapes successfully, and r < 0.5 represents the case that the prey does not escape and is caught by the eagle. Depending on the energy of the prey and the opportunity to escape, it adopts different strategies to hunt down the fleeing prey. Including soft surround, hard surround, soft surround fast dive and hard surround fast dive.

Step S30: Determine the global optimal path based on the initial planned path.

It should be noted that the initial planning path includes point information and path length, and the global optimal path is one of the initial planning paths, and is a path with the shortest moving distance among the initial planning paths.

In a specific implementation, the initial path is stored in a taboo table, and the taboo table is used to record map information and path information, and the map information includes a starting point position, a target point position, an intermediate point position, an obstacle position, and The status of each point, etc., the path information includes the passing point order, the shortest path length, etc., and the path passed by the robot during the delivery process is recorded by updating the information. When determining the global optimal path, it is necessary to traverse each initial path in the taboo table. The path length of the planning path, and the initial planning path with the smallest path length is taken as the global optimal path.

Further, the determining the global optimal path based on the initial planning path includes:

Obtaining the current position of each individual in the population, obtaining the moving distance according to the current position and the initial position, and storing the current position, the initial position and the moving distance in a taboo table;

The moving distances in the taboo table are compared, and when there is no obstacle on the current path, the shortest path among the moving distances is taken as the globally optimal path.

In the specific implementation, since each blank small square in the map is used as a passable node, and the taboo table stores the position coordinates of passable nodes and obstacle nodes, every time the algorithm traverses a node during execution, it will be in The coordinates of the current node are recorded in the taboo table, and the connectivity between every two nodes is verified to determine whether there is an obstacle between the nodes. When there is an obstacle node, the next passable node will be searched again. In the process of path optimization, start from the starting point, record the passing nodes in sequence, and number them in sequence, and gradually record the coordinates of new nodes until the path to the target point is found. At this time, the length of this path can be used as the number to represent the path. After all the paths are optimized, the shortest path can be determined by comparing the path lengths.

In this embodiment, by obtaining the initial position and the target position of the intelligent robot, based on the improved Harris Eagle algorithm in the intelligent path planning model, the initial position and the target position are searched to generate an initial planning path, and the improved Harris Eagle algorithm includes Replace the original Harris Eagle algorithm with random parameters to initialize the population, obtain the initial population sequence, add the elite reverse learning strategy to update the population, and determine the global optimal path based on the initial planning path, which can solve the problem of random parameters on the population The initialization cannot completely traverse all knotted spaces, resulting in uneven distribution of the population, and the population falls into a premature state, so that the population has higher quality and diversity. Compared with the prior art, the present invention has higher search speed and convergence accuracy, and improves intelligence. The robot's path-finding ability.

Referring to FIG. 3 , FIG. 3 is a schematic flowchart of a second embodiment of a path planning method for an intelligent robot according to the present invention.

Based on the above-mentioned first embodiment, the intelligent robot path planning method in this embodiment, in the step S20, includes:

Step S201: Obtain obstacle information in a real scene, and create a static grid map based on the obstacle information.

It should be noted that, taking the scenario of a freight robot in logistics distribution as an example, the robot needs to deliver the goods at the specified location to the target point or area. The terrain in the real scene is usually an irregular polygonal area, so it is necessary to obtain the boundary and obstacle information of the terrain in the real scene. By describing the obstacle information, the distribution of the obstacles in the real scene can be obtained , and then the static grid map can be determined.

It can be understood that the static grid map simplifies the topographic map in three-dimensional space into a two-dimensional plane map, and uses grids of the same size to divide the two-dimensional environment. The map is more intuitive and adaptable to the environment. Draw a grid map as the environment model in the real scene, draw a grid map with three specifications of 10×10, 20×20, and 40×40 grids, with the same unit length, representing simple, medium and complex maps respectively. Randomly distribute some black grids on the map to indicate obstacles, and the area is not allowed to pass through. Ensure that there is at least one passable path between a specified starting point and a target point.

In a specific implementation, refer to FIG. 4 , which is a flow chart of path optimization. The intelligent robot path planning equipment can divide the real scene into regions, divide the real scene into several regular small square grids, establish a grid map in the two-dimensional coordinate system, and construct a simulated map environment. In a static map composed of n×n small squares, white can be used to represent areas that can travel, and black can represent obstacles. For static grid maps, the more detailed the division, the more accurate the results obtained.

In the process of establishing a static grid map, it is first necessary to clarify the division accuracy. This embodiment uses a grid map with a unit size of 20×20 as an example for illustration. Refer to FIG. 5 , which is a schematic diagram of a grid map. In the grid map, the number 0 and the number 1 are used to represent the barrier-free area and the obstacle area, and are distinguished by white and black, and a two-dimensional coordinate system is established on the grid map. At this time, the path planning problem is transformed into Find a path on the map from the starting point to the goal point. First, convert the grid map numbers into actual coordinates, and the conversion rules are as follows:

x=int(N/G _size )+1

y=N%G _size +1

Among them, G _size is the number of grids in each row, int means rounding, and N is the total number of grids in the map.

Use (x, y) to represent the coordinate position of a cell, and mark it according to the position coordinates obtained by the above conversion. Non-obstacles are marked as 0, obstacles are marked as 1, and the matrix model is:

In addition, the path through the grid must be continuous, according to the discriminant formula:

d=max{abs(x _i -x _i-1 ),abs(y _j -y _j-1 )}

If the value of d is 1, the path is continuous, otherwise it is discontinuous.

Step S202: Set a preset population in the static grid map.

It should be noted that the preset population refers to setting a specific number of Harris hawks that need to be arranged so that the Harris hawks are at an initial position.

Step S203: Initialize the preset population to obtain an initialized population, and the population includes at least one individual.

It should be noted that the initialized population refers to that the preset population is mapped into the space corresponding to the static grid map, so that the population can be evenly distributed in the entire space.

Further, the step S203 also includes the following steps:

Set the initial population sequence and iteration parameters;

Iterating the initial population sequence according to the iteration parameters and the objective function to obtain the offspring population sequence, and updating the current number of iterations;

When the current number of iterations is equal to the maximum number of iterations, an initial population sequence is generated according to the child population sequence.

It should be noted that the initial population sequence refers to the original population of Harris Eagles before population iteration, and the value of the iteration parameter is a restrictive condition for limiting the population to perform iteration.

In the specific implementation, refer to Figure 6. Figure 6 is a comparison diagram of population initialization. When performing population initialization, the Tent chaotic map is used to replace the random parameter initialization method of the original Harris Eagle. In the original algorithm, the random parameter initialization method Can not completely traverse all the solution space, the initial population distribution is not uniform, it is difficult to guarantee the quality of the population, and Tent chaotic mapping is a typical chaotic mapping method, compared with random distribution, chaotic mapping has good randomness, and can Traverse the entire search space regularly, and use this method to replace the random parameters in the original algorithm to ensure that the initial solutions generated in the search space are more diverse. Uniformity and diversity, and effectively improve the quality of the initial solution and the optimization speed of the algorithm. The general expression of Tent chaotic map is:

Among them, t is the current iteration number, x(t) is the current individual position, x(t+1) is the next generation individual position, and a takes a number between 0 and 1.

In the process of performing Tent chaotic mapping, first determine the iteration parameter a, a is a number between 0 and 1, preferably 0.5, and the iteration parameter can be reasonably set according to the actual situation, which is not limited in this embodiment. After determining the iteration parameters, set the initial value sequence within (0,1) according to the objective function and avoid falling within {0.2,0.4,0.6,0.8}, X(1)=x ₀ , i=j=1; The target parameters are constructed according to the needs of the problem. In the single-objective path planning problem exemplified in this embodiment, the optimization goal is generally to minimize the path length. For the divided grid, when constructing the model, each small A grid is regarded as a node, and there is a definite distance between any two nodes. It is necessary to calculate the distance of all passable paths, and select the shortest path as the target. In the model that only considers the passable area and the shortest passing distance, if there is a black square in a pair of nodes, the pair of nodes cannot form a path, and such cases are not included in the goal. Therefore, the objective function for path optimization is:

Among them, l _{i j} is the distance between the i-th node and the j-th node, ω _j is the weight of the i-th node, which is 0 or 1, 0 means the black square is the impassable area, and 1 means the white square The grid can pass through the area. Set the sequence of initial value x ₀ according to the above steps, and generate x(i) sequence, update node i=i+1, after the x(i) sequence is generated, it is necessary to judge the x(i) sequence, if x(i ) sequence falls in {0,0.25,0.5,0.75}, or x(i)=x(ik), k=(0,1,2,3,4) then x(i)=y(j+1) =z(j)+c is the initial value of iteration, c is a random number, j=j+1, otherwise reset the initial value sequence, stop until the number of iterations reaches the maximum, and generate an initialization sequence.

When iterating according to the objective function, the objective function can also be optimized, and the adaptive adjustment factor can be used, wherein the model for adjusting the adaptive factor is:

X' _rabbit = ω·X _rabbit

Among them, a and b are positive integers, t is the current iteration number, T is the maximum iteration number, X _rabbit and X' _rabbit represent the initial prey position and adjusted prey position respectively.

After introducing the weight factor, the algorithm will adjust the weight according to the distribution of the current population. Under the adjustment of the weight factor, when the algorithm performs a global search in the initial stage of iteration, the inertia weight is larger, the search range is larger, and the speed is faster, which avoids falling into a small-scale search in the early stage of iteration; when the algorithm enters the later stage of local search, the inertia weight Smaller, with high convergence precision and strong optimization ability. The advantage of adding an adaptive weight factor is that only one parameter is needed to adjust the two parts of the algorithm, which has strong adaptability.

Further, the step iterates the initial population sequence according to the iteration parameter and the objective function to obtain the offspring population sequence, including:

obtaining the relative average position of the individual in the population according to the current position of the individual in the population;

Obtain the next iteration position of the individual according to the current position of the individual in the population, the current number of iterations, the position of the prey and the relative average position;

Select elite individuals according to the fitness and the next iteration position;

Obtain the reverse population according to the boundary between the elite individual and the static grid map;

The population sequence after iterating the reverse population and the initial population sequence is used to obtain the descendant population sequence.

It should be noted that the offspring population sequence is the iterative result of the initial population sequence, which can reflect the pathfinding process, and the elite individual refers to the individual closest to the optimal solution in principle.

It is understandable that in order to prevent the algorithm from entering the premature state prematurely, a reverse learning strategy is introduced to increase the quality and diversity of the population. Generally speaking, elite individuals in the population often contain more effective information than ordinary individuals. The elite reverse learning strategy is to select elite individuals from the reverse population, so as to iterate and produce effective solutions.

其中

ω为分布在[0,1]区间内的一般化系数。在标准算法中，哈里斯鹰种群是随机选取一个个体进行迭代更新的，具有较大的不确定性，难以保证后代质量，迭代效率较低。引入精英个体机制，通过选出初代种群中的精英个体，根据精英个体的位置引导种群中其他个体更新。精英个体的迭代模型为：In the specific implementation, first calculate and evaluate the reverse solution of the current solution according to the reverse learning strategy, assuming that in the d-dimensional search space, the feasible solution of the current population is X=(x ₁ ,x ₂ ,...,x _d ), x _j ∈[a _j ,b _j ], the reverse solution is

in

ω is a generalization coefficient distributed in the [0,1] interval. In the standard algorithm, the Harris eagle population randomly selects an individual for iterative update, which has great uncertainty, it is difficult to guarantee the quality of offspring, and the iteration efficiency is low. Introduce the elite individual mechanism, select the elite individual in the first generation population, and guide other individuals in the population to update according to the position of the elite individual. The iterative model of elite individuals is:

X _best (t+1)＝lb+(ub-X _best (t))

Among them, X _best (t) is the elite object in the current population. At the t-th iteration, the individual with the highest fitness in the population is the elite object. In principle, the elite object is the closest to the optimal solution position. In the next iteration of the population, It will be more inclined to adjust to the direction of the elite object, making the iteration more purposeful and avoiding the problem of slow convergence caused by randomness. Since the elite object acts as the leader in the iteration, its position greatly affects the search efficiency of the population. In order to improve the quality of the elite object, a reverse learning operation is performed on it, and the reverse population is generated, and the reverse population is added to the descendant population sequence to expand the diversity of the population and further improve the search efficiency. The model of the reverse object is:

表示反向种群中的一个个体，ub、lb分别表示搜索范围的上下限。将反向种群与初始种群组成新的精英种群，进行迭代更新，并寻找适应度最高的个体作为精英对象，进行下一次迭代，在迭代过程中，可以采用移动平均法计算平均位置，得到的结果更为准确，公式如下：

Represents an individual in the reverse population, ub and lb represent the upper and lower limits of the search range, respectively. The reverse population and the initial population form a new elite population, iteratively update, and find the individual with the highest fitness as the elite object, and perform the next iteration. During the iteration process, the moving average method can be used to calculate the average position, and the obtained result is More precisely, the formula is as follows:

Among them, X _m (t) is the average position of the current population, X _m (t+1) is the average position of the next generation population, and T is the total number of iterations.

Step S204: When the current number of iterations does not reach the maximum number of iterations, obtain the fitness of each individual in the population according to the limit of the search space.

It should be noted that the fitness can be used to describe how far an individual is from the optimal solution position, and the search space refers to the space area.

In the specific implementation, when calculating the fitness of an individual, it is necessary to determine the location of the individual first, and at the same time, it is necessary to judge whether the individual is out of bounds. When calculating the fitness of an individual, it can be calculated according to the following formula Calculate fitness:

f(x)＝x·|FU+FL|+ub·FU+lb·FL

Among them, f(x) is used to evaluate the fitness of the current Harris Eagle to the current environment, x is the current individual position, ub and lb represent the upper limit and lower limit of the search space respectively, FU and FL are used to check whether the individual is out of bounds, and out of bounds is taken as 1, 0 if there is no crossing, wherein the smaller the function value of f(x), the higher the fitness of the current individual at the current location.

Step S205: Update the escape energy of each individual in the population, execute a round-up strategy according to the escape energy, and obtain the position of each individual in the population.

In the specific implementation, the escape energy and jumping strength of the prey are updated to judge the movement mode of the next stage, r is the escape probability, and the value is a random number between 0 and 1, and E represents the escape energy. When r>0.5 and E When >0.5, the soft encirclement method is adopted; when r<0.5 and E>0.5, the hard encirclement method is adopted; when r>0.5 and E<0.5, the hard encirclement and rapid dive encirclement method is adopted; At 0.5, the soft encirclement and fast swooping round-up method is adopted. The inertia weight parameter ω is introduced to balance the global search and local development of the algorithm. When performing global search, ω will increase to improve the search speed; when performing local development, ω will decrease to improve search accuracy.

X' _rabbit = ω·X _rabbit

Among them, a and b are positive integers, and X _rabbit represents the position of the prey. After adjustment is:

X(t+1)＝ΔX(t)-E·|J·ω·X _rabbit (t)-X(t)|

Different round-up methods will produce the next generation of optimized individuals, that is, the solution of the path sought, and the round-up method is determined according to the escape probability r and the escape energy E.

When r≥0.5&|E|≥0.5, it is the soft encirclement rounding method, the prey has enough energy to escape, it will jump in a certain direction randomly, and the Harris eagle group will adopt a soft encirclement strategy to encircle the prey to consume its physical strength , the mathematical model is:

X(t+1)＝ΔX(t)-E·|J·X _rabbit (t)-X(t)|

ΔX(t)＝X _rabbit (t)-X(t)

J＝2(1-r ₅ )

Among them, ΔX(t) is the change of the prey position before and after t iterations, r ₅ ∈ (0, 1), J represents the jumping intensity of the prey in the whole escape process, simulating the behavior characteristics of the prey when escaping.

When r≥0.5&|E|<0.5, it is a hard encirclement round-up method. The escape energy of the prey is low, but there is still a chance to escape the hunt. The Harris eagle can only raid the prey to try to capture. The model is as follows:

X(t+1)＝X _rabbit (t)-E·|ΔX(t)|

When r<0.5&|E|≥0.5, it is a soft encirclement and fast swooping roundup method. Since the prey still has enough physical strength to escape, the prey is soft encircled before the surprise attack. When simulating the jumping behavior of the prey, the prey may create a deceptive action to trick the hawks into the wrong direction. At the same time, the eagle will also perform rapid and multiple swoops, correct the direction of the prey and adjust the position of the prey. Use the following formula to simulate the action of an eagle swooping:

Y ₁ ＝X _rabbit (t)-E·|J·X _rabbit (t)-X(t)|

The Harris Eagle will compare this dive behavior with the previous one. When it notices that the prey has multiple deceptions, it will adjust the next dive and dive towards irregular fast dives. Here, the mechanism of Levi's flying LF is introduced. Indicates the irregular flight of the hawk, and its dive action is adjusted as follows:

Z＝Y ₁ +S·LF(D)

Among them, u and v are random values of (0, 1), and β is a constant value of 1.5.

Therefore, Harris Hawk's soft siege and dive strategy can be integrated as:

When r<0.5&|E|<0.5, it is hard encirclement and rapid dive encirclement, and the escape energy of the prey is insufficient, and the hard siege method is adopted to encircle the prey before raiding the prey. Similar to the soft siege dive, the mathematical model is still the above formula, but here the eagle tries to reduce the average distance between the prey and the prey in order to try to catch the prey, and the value of Y needs to be adjusted:

Y ₂ ＝X _rabbit (t)-E·|J·X _rabbit (t)-X _m (t)|

Step S206: Generate an initial planned route according to the location.

In the specific implementation, constraints on obstacles in the path: In robot path planning problems, there is usually a starting point and a target point specified, the robot needs to start from the specified starting point, and the path must avoid obstacles in the map. According to the marking of path nodes in the above description, the restriction of black squares cannot appear in the path, that is, the weight product of the path cannot be 0.

Constraints on path continuity: the final path through the grid must be continuous, calculated according to the following discriminant formula, if the result d=1, it is continuous, otherwise it is discontinuous.

d=max{abs(x _i -x _i-1 ), abs(y _j -y _j-1 )}

When the requested path is continuous and there are no obstacles on the path, record the nodes passed by the individual, and add up the distance traveled to obtain the total distance traveled. The distance calculation method is:

Among them, d(x) is used to calculate the total distance traveled between the initial point and the current node, x _i and y _i respectively represent the abscissa and ordinate of the current node in the grid, x _i+1 and y _{i+ 1} represents the abscissa and ordinate of the next node in the grid, respectively.

This embodiment initializes the initial population by introducing the Tent Chaos Algorithm, so that the population can be evenly distributed in the search space, improving the quality and diversity of the population. In addition, the elite population strategy is introduced, and the population after each iteration Among them, the individual with the highest fitness is regarded as the elite individual, and the reverse population is generated according to the elite individual, and the reverse population is added to the offspring population for the next iteration, which can prevent the population from entering premature maturity , affecting the quality of path planning. In addition, by adjusting the position parameters and introducing adaptive adjustment factors, adaptively adjust the parameter weights, so that the search speed and convergence accuracy of iterative updates are improved, and the final path planning is the optimal result.

In addition, the embodiment of the present invention also proposes a storage medium, on which an intelligent robot path planning program is stored, and when the intelligent robot path planning program is executed by a processor, the above-mentioned intelligent robot path planning method is realized. step.

Referring to FIG. 7, FIG. 7 is a structural block diagram of the first embodiment of the intelligent robot path planning device of the present invention.

As shown in Figure 7, the intelligent robot path planning device proposed by the embodiment of the present invention includes:

The position obtaining module 10 is used to obtain the initial position and the target position of the intelligent robot;

The path planning module 20 is used to find the initial position and the target position based on the improved Harris Eagle algorithm in the intelligent path planning model, and generate an initial planned path. The improved Harris Eagle algorithm includes replacing the original Harris Eagle algorithm. The population is initialized with random parameters to obtain an initial population sequence, and an elite reverse learning strategy is added to update the population;

A path decision module 30, configured to determine a globally optimal path based on the initial planned path.

In this embodiment, by obtaining the initial position and the target position of the intelligent robot, based on the improved Harris Eagle algorithm in the intelligent path planning model, the initial position and the target position are searched to generate an initial planning path, and the improved Harris Eagle algorithm includes Replace the original Harris Eagle algorithm with random parameters to initialize the population, obtain the initial population sequence, add the elite reverse learning strategy to update the population, and determine the global optimal path based on the initial planning path, which can solve the problem of random parameters on the population The initialization cannot completely traverse all knotted spaces, resulting in uneven distribution of the population, and the population falls into a premature state, so that the population has higher quality and diversity. Compared with the prior art, the present invention has higher search speed and convergence accuracy, and improves intelligence. The robot's path-finding ability.

In an embodiment, the path planning module 20 is further configured to obtain obstacle information in a real scene, and establish a static grid map according to the obstacle information;

Setting preset populations in the static grid map;

Initializing the preset population to obtain an initialized population, the population includes at least one individual;

When the current number of iterations does not reach the maximum number of iterations, the fitness of each individual in the population is obtained according to the limit of the search space;

updating the escape energy of each individual in the population, executing a round-up strategy according to the escape energy, and obtaining the position of each individual in the population;

An initial planned path is generated based on the position.

In one embodiment, the path planning module 20 is also used to set the initial population sequence and iteration parameters;

Iterating the initial population sequence according to the iteration parameters and the objective function to obtain the offspring population sequence, and updating the current number of iterations;

When the current number of iterations is equal to the maximum number of iterations, an initial population sequence is generated according to the child population sequence.

In one embodiment, the path planning module 20 is further configured to obtain the relative average position of the individuals in the population according to the current positions of the individuals in the population;

Obtain the next iteration position of the individual according to the current position of the individual in the population, the current number of iterations, the position of the prey and the relative average position;

Select elite individuals according to the fitness and the next iteration position;

Obtain the reverse population according to the boundary between the elite individual and the static grid map;

The population sequence after iterating the reverse population and the initial population sequence is used to obtain the descendant population sequence.

In one embodiment, the path planning module 20 is further configured to obtain the corresponding moving distance according to the current position and the initial position of each individual in the population;

The fitness of each individual in the population is obtained according to the moving distance and the limit of the search space.

In an embodiment, the path planning module 20 is further configured to obtain the escape energy of each individual in the population according to the current number of iterations and the maximum number of iterations of each individual in the population;

When the escape energy is greater than the preset swooping and encircling energy, adopt a encircling strategy, adjust the escape energy and obtain the encircled position;

When the escape energy is less than the preset swooping and rounding up energy, adopt a swooping and rounding up strategy, adjust the escape energy and obtain the position after rounding up;

An initial planned path is generated according to the captured position.

In one embodiment, the path determination module 30 is further configured to obtain the current position of each individual in the population, obtain the moving distance according to the current position and the initial position, and combine the current position, initial position and The moving distance is stored in a taboo table;

The moving distances in the taboo table are compared, and when there is no obstacle on the current path, the shortest path among the moving distances is taken as the globally optimal path.

It should be understood that the above is only an example, and does not constitute any limitation to the technical solution of the present invention. In specific applications, those skilled in the art can make settings according to needs, and the present invention is not limited thereto.

It should be noted that the workflow described above is only illustrative and does not limit the protection scope of the present invention. In practical applications, those skilled in the art can select part or all of them to implement according to actual needs. The purpose of the scheme of this embodiment is not limited here.

Furthermore, it should be noted that in this document, the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article or system comprising a set of elements includes not only those elements, but also other elements not expressly listed, or elements inherent in such a process, method, article, or system. Without further limitations, an element defined by the phrase "comprising a..." does not preclude the presence of additional identical elements in the process, method, article or system comprising that element.

The serial numbers of the above embodiments of the present invention are for description only, and do not represent the advantages and disadvantages of the embodiments.

Through the description of the above embodiments, those skilled in the art can clearly understand that the methods of the above embodiments can be implemented by means of software plus a necessary general-purpose hardware platform, and of course also by hardware, but in many cases the former is better implementation. Based on such an understanding, the essence of the technical solution of the present invention or the part that contributes to the prior art can be embodied in the form of a software product, and the computer software product is stored in a storage medium (such as a read-only memory (Read Only Memory) , ROM)/RAM, magnetic disk, optical disk), including several instructions to make a terminal device (which can be a mobile phone, computer, server, or network device, etc.) execute the methods described in various embodiments of the present invention.

The above are only preferred embodiments of the present invention, and are not intended to limit the patent scope of the present invention. Any equivalent structure or equivalent process conversion made by using the description of the present invention and the contents of the accompanying drawings, or directly or indirectly used in other related technical fields , are all included in the scope of patent protection of the present invention in the same way.

Claims (10)

1. A path planning method for an intelligent robot, characterized in that, the intelligent path planning method comprises: Obtain the initial position and target position of the intelligent robot; Based on the improved Harris Eagle algorithm in the intelligent path planning model, the initial position and the target position are routed to generate an initial planning path. The improved Harris Eagle algorithm includes replacing the original Harris Eagle algorithm with random parameters to initialize the population. , get the initial population sequence, add the elite reverse learning strategy to update the population; A globally optimal path is determined based on the initial planned path. 2. The method according to claim 1, wherein the improved Harris Eagle algorithm based on the intelligent path planning model carries out pathfinding to the initial position and the target position, and generates an initial planning path, comprising: Obtain obstacle information in the real scene, and create a static grid map based on the obstacle information; Setting preset populations in the static grid map; Initializing the preset population to obtain an initialized population, the population includes at least one individual; When the current number of iterations does not reach the maximum number of iterations, the fitness of each individual in the population is obtained according to the limit of the search space; updating the escape energy of each individual in the population, executing a round-up strategy according to the escape energy, and obtaining the position of each individual in the population; An initial planned path is generated based on the position. 3. The method according to claim 1, wherein the improved Harris Eagle algorithm comprises replacing the original Harris Eagle algorithm with random parameters to initialize the population to obtain an initial population sequence, comprising: Set the initial population sequence and iteration parameters; Iterating the initial population sequence according to the iteration parameters and the objective function to obtain the offspring population sequence, and updating the current number of iterations; When the current number of iterations is equal to the maximum number of iterations, an initial population sequence is generated according to the child population sequence. 4. The method according to claim 3, wherein said initial population sequence is iterated according to said iteration parameter and objective function to obtain a descendant population sequence, comprising: obtaining the relative average position of the individual in the population according to the current position of the individual in the population; Obtain the next iteration position of the individual according to the current position of the individual in the population, the current number of iterations, the position of the prey and the relative average position; Select elite individuals according to the fitness and the next iteration position; Obtain the reverse population according to the boundary between the elite individual and the static grid map; The population sequence after iterating the reverse population and the initial population sequence is used to obtain the descendant population sequence. 5. The method according to claim 2, wherein said obtaining the fitness of each individual in the population according to the limit of the search space comprises: obtaining the corresponding moving distance according to the current position and the initial position of each individual in the population; The fitness of each individual in the population is obtained according to the moving distance and the limit of the search space. 6. The method according to claim 2, characterized in that, updating the escape energy of each individual in the population, executing a round-up strategy according to the escape energy, obtaining the position of each individual in the population, and according to The locations generate an initial planned path, including: Obtain the escape energy of each individual according to the current number of iterations and the maximum number of iterations of each individual in the population; When the escape energy is greater than the preset swooping and encircling energy, adopt a encircling strategy, adjust the escape energy and obtain the encircled position; When the escape energy is less than the preset swooping and rounding up energy, adopt a swooping and rounding up strategy, adjust the escape energy and obtain the position after rounding up; An initial planned path is generated according to the captured position. 7. The method according to any one of claims 1 to 6, wherein said determining the global optimal path based on said initial planning path comprises: Obtaining the current position of each individual in the population, obtaining the moving distance according to the current position and the initial position, and storing the current position, the initial position and the moving distance in a taboo table; The moving distances in the taboo table are compared, and when there is no obstacle on the current path, the shortest path among the moving distances is taken as the globally optimal path. 8. A path planning device for an intelligent robot, characterized in that the path planning device for an intelligent robot comprises: The position obtaining module is used to obtain the initial position and the target position of the intelligent robot; The path planning module is used to find the initial position and the target position based on the improved Harris Eagle algorithm in the intelligent path planning model, and generate an initial planned path. The improved Harris Eagle algorithm includes replacing the original Harris Eagle algorithm. Random parameters are used to initialize the population to obtain the initial population sequence, and the elite reverse learning strategy is added to update the population; A path determination module, configured to determine a globally optimal path based on the initial planned path. 9. A path planning device for an intelligent robot, characterized in that the device comprises: a memory, a processor, and an intelligent robot path planning program stored on the memory and operable on the processor, the intelligent robot The path planning program is configured to implement the steps of the intelligent robot path planning method according to any one of claims 1 to 7. 10. A storage medium, characterized in that an intelligent robot path planning program is stored on the storage medium, and when the intelligent robot path planning program is executed by a processor, the intelligent robot according to any one of claims 1 to 7 is realized. Steps of the robot path planning method.

Images