CN104407616A - Dynamic path planning method for mobile robot based on immune network algorithm - Google Patents

Abstract

A dynamic path planning method for a mobile robot based on an immune network algorithm. The steps of the method are: 1. Obtain information about the working environment of the mobile robot and process it, and represent the static obstacles in the surrounding environment in the form of a rectangular bounding box. 2. Based on the collected static environment information, apply the improved immune network algorithm for global path planning. 3. The robot travels along the planned path. If an unknown motion obstacle is found, it will predict whether it will hinder normal driving. If it affects normal driving, it will predict the dangerous area that may collide. 4. Form a new visual view of the local environment based on the predicted results and apply the immune network algorithm to plan a new local path. 5. When the robot reaches the temporary goal point of the local plan, it returns to the previously planned global path and continues to move forward. The present invention can guarantee the optimality of the path planning in the local dynamic area on the basis of ensuring the solution of the global optimal path in the complex environment.

Description

A Dynamic Path Planning Method for Mobile Robots Based on Immune Network Algorithm

Technical field: The present invention relates to a dynamic path planning method for a mobile robot based on an immune network algorithm. The invention can be widely used to solve the path planning problem of the mobile robot in a relatively complex dynamic environment.

Background technology: Path planning is one of the core contents of mobile robotics research. Its purpose is to find an appropriate safe motion path from a given starting point to a target point in a working environment with obstacles, so that the robot can Able to go around all obstacles without collision. Path planning technology is an important research field in the related technology research of mobile robot.

In reality, mobile robots are mostly in dynamic and uncertain environments. For dynamic obstacles in such environments, it is difficult for mobile robots to have prior knowledge and only have partial environmental information. In this case, mobile robots can only perform local path planning based on real-time detected environmental information. In order to solve this kind of path planning problem, the traditional global path planning algorithm is usually combined with the collision prediction method, such as an algorithm combining the collision prediction method and the artificial potential field method. position to change the running speed of the mobile robot to avoid, but it does not take into account the global path planning ability of the mobile robot in complex environments. In order to solve the above-mentioned deficiencies, the present invention uses an improved immune network algorithm for path planning of mobile robots in partially unknown environments.

The immune network algorithm is an important method in the artificial immune algorithm. Based on the unique network theory of the internal regulation of the immune system proposed by Jerne, de Castro and Timmis proposed the immune network algorithm (opt-aiNet) in 2002, which has fast convergence speed, high solution accuracy, good stability, and can effectively overcome The "premature" feature makes it have advantages in global optimization and optimization speed, so it is suitable for solving complex multi-obstacle global planning problems and fast dynamic obstacle avoidance planning problems in mobile robot path planning.

Invention content:

Purpose of the invention: In order to improve the solution quality and efficiency of mobile robot path planning problems, the present invention provides a mobile robot dynamic path planning method based on the immune network algorithm, which can not only solve the global path planning of mobile robots in complex environments , which is also suitable for local path planning when part of the environment is unknown.

Technical solutions:

A dynamic path planning method for a mobile robot based on an immune network algorithm, which is characterized in that: firstly, the global static environment space is preprocessed based on the visualization method, and then the global path is planned by applying the immune network algorithm, and the surrounding area is detected in real time during the traveling process. Environmental information, predict the danger of unknown dynamic obstacles entering the perception range, form a new visual view of the local environment according to the predicted results, and use the immune network algorithm to plan a new local path. When the robot reaches the temporary target point of the local plan, it returns to the Continue on the previously planned global path.

(1) The implementation process of the immune network algorithm:

After improving the immune network algorithm and combining with the visual graph, the specific implementation steps of the algorithm are as follows:

(1) Preprocess the environment space where the mobile robot operates, and build a visual map;

(2) According to the establishment and analysis of the visual map, summarize the prior knowledge and extract the vaccine, including the generated antibody or path does not pass through the bounding box of obstacles and the generated antibody or path does not have regression phenomenon;

(3) Population initialization: vaccinate first, and generate m antibodies or m paths by implanting vaccines in the search space. The path generation method is to gradually extend from the starting point to the target point, and the m antibodies are m paths Constitute the initial parent population The superscript i indicates the i-th generation, and the subscript m indicates the number of antibodies;

(4) Stop condition: According to the fitness between the antibody and the antigen and the concentration between the antibodies, the affinity of the antibody is finally determined, and the genetic algebra and the number of the current parent population are calculated. The affinity of all antibodies in , if the conditions are met, the operation is terminated and the result is output, otherwise continue;

(5) Clonal expansion: n clones are generated for each antibody (path) in the above-mentioned antibody group, and at this time, m*n cloned antibodies (paths) are amplified, and the antibody group becomes Each path is replicated n times, and the path variation in the next step will be more sufficient, increasing the diversity of each generation of antibodies;

(6) High-frequency variation: clonal antibody group The antibody of each clone must undergo high-frequency mutation to obtain This refers to adding or deleting nodes to the antibody path;

(7) Recalculate the fitness value: recalculate the affinity of all individuals in the antibody population, including each parent antibody and its variant clone antibody;

(8) Memory antibody group update: from each parent antibody and its clone antibody Among them, the mutated clone antibody with the highest affinity is selected to form m new elite mutated antibody groups with the highest affinity And use it as a candidate to update the memory antibody group, and then from and Select the m with the highest affinity to form a new elite mutant antibody group Then calculate the average affinity in the memory antibody population;

(9) Immune self-regulation and receptor editing: randomly generate r (r<m) brand new antibodies Replace the antibody population at this time The r antibodies with the lowest affinity are used to simulate the receptor editing process in the biological immune system and increase the diversity of the antibody population. In this way, the algorithm generates the next generation of antibody populations Then return to step 4;

(2) Steps of dynamic path planning for mobile robot based on immune network algorithm:

For the situation where the mobile robot’s workspace is partially unknown, the specific path planning steps are as follows:

(1) Apply the improved immune network algorithm to the known static environment information for global path planning;

(2) The robot moves along the planned path;

(3) Judging whether to reach the target point, if it arrives, it will end, if it does not arrive, it will continue to travel along the planned path;

Since the information of the static obstacles in the environmental space is known in advance, every time the robot takes a step, it will be judged whether the distance between the robot and the known static obstacles is smaller than the rolling window, that is, the radius of the sensing range of the sensor. It can be concluded whether these static obstacles have appeared within the range of the rolling window;

(4) Determine whether the movement obstacle hinders the normal driving of the robot;

(5) It is predicted that the marked unknown dynamic obstacle will collide with the robot traveling along the previously planned path at the next T time, then record the position of the unknown moving obstacle at T time as a "static Obstacle" processing, taking into account the prediction error and the uncertain factors in the actual environment, expand the area of this "static obstacle" and record it as a dangerous area;

(6) When the dangerous area completely enters the rolling window, the robot takes the intersection point of the rolling window at the current moment and the previously planned path as a temporary local target point, and the current robot position as the starting point to perceive static obstacles and dangerous areas in the window As the local environment information, a new path is planned by applying the immune network algorithm, and the robot drives along the newly planned path, and returns to step 3.

(2) In step (4) of step (4), the robot does not need to consider the rolling window until the sensor finds that a new unknown obstacle enters the rolling window, that is, the distance between the unknown obstacle and the robot is less than the rolling window radius, mark the unknown dynamic obstacle and start to predict the trajectory of the unknown obstacle; the prediction results are divided into the following two situations: one is that the unknown obstacle will not hinder the normal driving of the robot, then the robot continues to follow the previously planned The path can be followed, that is, return to step 2; the second is to predict that the movement obstacle may hinder the normal driving of the robot, then go to step (5) of step (2).

Antibody design in the immune network algorithm:

After processing the working environment space of the mobile robot by the visual graph method, the composition of the antibody path only needs to consider the elements in the set V of each obstacle vertex, and does not need to consider any points outside the environment space, so the search range will be significantly reduced, making Algorithm efficiency is improved. The structure of each node is as follows:

ID points IDobject x the y

Among them, IDpoint represents the node number, IDobject represents the obstacle number to which the node belongs, and x and y represent the horizontal and vertical coordinates of the node respectively; in the path planning problem of the mobile robot, the antigen represents the problem to be solved, that is, the optimal path, and this application sets it as The Euclidean distance between the starting point s and the target point g, the antibody represents the solution of the problem to be sought, that is, the feasible path searched, which is composed of the starting point of the mobile robot, the target point and a series of broken lines connected by intermediate nodes, which is a clear description The direction of the path, the order of the elements in the antibody indicates the order of the nodes that the mobile robot passes through when moving, the antibody uses a string encoding method, and its length can vary with the number of nodes, the data structure of the antibody is as follows:

Affinity Density Fitness Length the s … v … g

Among them, Affinity represents the affinity of the antibody, which is used to evaluate the quality of the antibody here; Fitness represents the fitness of the antibody, and antibodies with shorter paths have higher fitness; Density represents the concentration of the antibody, that is, the concentration of the same antibody. Accounting for the proportion of the antibody group, Length indicates the length of the antibody from s to g, and the rest is the node that constitutes the path. This storage structure can flexibly change the length of the antibody when the antibody changes;

Calculation of affinity in the immune network algorithm:

In order to suppress and avoid the appearance of prematurity in this application, the calculation of antibody concentration is added here, and the calculation formula of specific affinity is as follows:

$\mathrm{<span\; class="notranslate">\; Affinity</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; Fitness</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}\mathrm{<span\; class="notranslate">\; ln</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; Density</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}$

Among them, Affinity(i) represents the affinity of antibody i; Fitness(i) represents the fitness of antibody i, which is related to distance. The shorter the distance of the antibody path, the higher the fitness of the antibody; Density(i) represents the antibody The concentration of i, that is, the more the same antibody path, the greater the antibody concentration; α is a positive constant, through this formula, it can be seen that the greater the fitness, the greater the affinity; the higher the concentration, the greater the affinity The smaller the degree.

Advantages and effects: the present invention provides a dynamic path planning method for mobile robots based on the immune network algorithm. This application takes the length of the path as the main criterion for measuring whether the path is good or not. In the environment where the static environment information is known and the dynamic obstacle information is unknown The path planning method combining opt-aiNet algorithm and visual graph in idiotype immune network theory is studied. Firstly, the global static environment space is described based on the visualization method, and then the global path is planned by using the immune network algorithm. Detect the surrounding environment information in real time during the robot’s movement, predict the danger of unknown dynamic obstacles entering the perception range, form a new visual view of the local environment according to the predicted results, and use the immune network algorithm to plan a new local path, so as to achieve local dynamics Combination of planning and global static programming. In addition, in order to avoid problems such as premature evolution and lack of antibody diversity that are prone to occur when the immune network is used for robot path planning, a calculation method for antibody concentration is introduced. The present invention can also guarantee the optimization of local dynamic area path planning on the basis of ensuring the global optimal path.

Description of drawings:

Figure 1 Schematic diagram of the working environment of the robot;

Figure 2 is a flow chart of local path planning;

Figure 3 Immune Network Algorithm Flowchart;

Fig. 4 Path planning with relatively complicated working environment;

Figure 5 Statistics of evolutionary algebra;

The analysis of the antibody affinity of Fig. 6 population;

Fig. 7 Path planning with unknown dynamic obstacles.

The specific embodiment: the present invention will be further described below in conjunction with accompanying drawing:

Figure 1 shows the working environment space of the mobile robot. The car traveling along the path represents the mobile robot. The dotted circle around it is the local sensing range of the mobile robot, that is, the effective sensing range of the sensor (such as laser sensor, ultrasonic sensor or panoramic vision sensor, etc. ), s represents the starting point of the mobile robot, g represents the final goal point of the mobile robot, the black rectangle represents the static obstacle in the environment space (represented by O _j ), another car in the environment space represents the dynamic obstacle, and the arrow represents its In the direction of movement, the four vertices of the rectangular bounding box of each obstacle have a fixed number (indicated by v _i ), and the corresponding relationship between the number i of the vertex and the number j of the obstacle is i=1,2,... ,j*4.

In this paper, considering the actual size of the mobile robot, a certain safety distance is reserved when constructing the obstacle bounding box, that is, the dotted line frame around the obstacle bounding box, and all the endpoints that meet the conditions in Figure 1 are connected to form a visible view, as shown in Figure 1. Each line from the starting point s to the final goal point g in is a path (also representing an antibody). The representation method of the path is the sequence of vertices that the mobile robot passes through, such as path1=s→v ₉ →v ₂ →g.

After the preprocessing of the environment space by the visualization method, the search range of the algorithm is reduced from all points in the working environment to the nodes and target points of each obstacle, which greatly reduces the search range of the algorithm and greatly improves the convergence speed of the optimization algorithm , so that it can be adapted to real-time local path planning.

A mobile robot path planning steps based on immune network algorithm:

For the situation where the mobile robot’s workspace is partly unknown to the environment information, as shown in Figure 2, the specific path planning steps are as follows:

Step 1: Obtain the information of the working environment of the mobile robot and process it, and represent the static obstacles in the surrounding environment with a rectangular bounding box.

Considering the complexity and real-time requirements of the algorithm search caused by the variability of the working environment of the mobile robot, this application adopts the visual diagram method to describe the working environment of the mobile robot. Note the visible view VG=(V, L), wherein V is composed of each vertex of each obstacle bounding box, the starting point s, the target point g, and each obstacle rectangular bounding box. This application adopts each vertex of the rectangular bounding box to form Set, L represents the "visible" connection between each vertex, that is, if these connections do not intersect with obstacles, the line segment is considered "visible", then the combination of all "visible" connections is the current A visual map of the environment space, each line also represents the runnable path of the mobile robot.

Using the visualization method to plan and process the working environment space of the mobile robot, the core problem is to construct the cost matrix, that is, the matrix formed by the distance between each node. Use the node number, the four vertices of the rectangular bounding box of each obstacle, the starting point, and the target point to represent the rows and columns in the cost matrix, and the contents in the rows and columns are represented by the Euclidean Distance representation, where ∞ means that the connection between two nodes passes through obstacles, that is, the cost is infinite. Using the cost matrix, the cost required for any path can be quickly calculated; after the cost matrix is constructed, it will to a certain extent affect the extraction of vaccines and the determination of antibody encoding methods when the immune network algorithm solves the problem of path planning for mobile robots.

Step 2: Apply the immune network algorithm on the basis of the collected static environment information for global path planning.

Treat the problem to be solved, that is, the optimal path, as an antigen, and the solution of the problem (the optimal path obtained) as an antibody, randomly generate a given number of initial paths (antibodies), and use operators such as selection, copying, and transformation paths Evolutionary operations are performed on the population to produce offspring paths that are superior to parent paths. Here, the simulation of the interaction between antibodies in the network or the immune self-regulation function is added, and the number of antibodies in the antibody population is dynamically balanced by calculating the similarity between antibodies.

This step improves the way affinity is calculated in the immune network algorithm and how antibodies and their genes are encoded.

The flow chart of implementing path planning by applying the immune network algorithm is shown in Figure 3, and the algorithm steps are as follows:

(1) Based on the establishment and analysis of the visual graph, summarize the prior knowledge and extract the vaccine, including the generated antibody (path) does not pass through the bounding box of obstacles and the generated antibody (path) does not have regression phenomenon.

After processing the working environment space of the mobile robot by the visual graph method, the composition of the antibody path only needs to consider the elements in the set V of each obstacle vertex, and does not need to consider any points outside the environment space, so the search range will be significantly reduced, making Algorithm efficiency is improved. The structure of each node is shown in Table 1:

ID points IDobject x the y

Table 1 Node encoding format

Among them, IDpoint represents the node number, IDobject represents the obstacle number to which the node belongs, and x and y represent the horizontal and vertical coordinates of the node respectively. In the path planning problem of mobile robots, the antigen represents the problem to be solved, that is, the optimal path, which is set as the Euclidean distance between the starting point s and the goal point g in this application. The antibody represents the solution to the problem, that is, the searched feasible path, which is composed of the starting point, the target point and a series of broken lines connected by the mobile robot. In order to clearly describe the path direction, the sequence of elements in the antibody represents the sequence of nodes that the mobile robot passes through. The antibody adopts a string encoding method, and its length can vary with the number of nodes. The data structure of the antibody is shown in Table 2:

Affinity Density Fitness Length the s … v … g

Table 2 Antibody coding format

Among them, Affinity represents the affinity of the antibody, which is used to evaluate the quality of the antibody here; Fitness represents the fitness of the antibody, and antibodies with shorter paths have higher fitness; Density represents the concentration of the antibody, that is, the concentration of the same antibody. Accounting for the proportion of the antibody population, Length represents the length of the antibody from s to g, and the rest are the nodes that constitute the path. This storage structure can flexibly change the length of the antibody when the antibody changes.

In the immune network algorithm, the affinity of antibodies plays an important role, especially in the steps of updating memory antibody population and immune self-regulation, using affinity to measure the value of antibodies, so as to screen antibodies.

The affinity of an antibody refers to the binding strength between an antibody and an antigen. This application uses affinity to evaluate the quality of an antibody. In order to suppress and avoid the appearance of premature maturation, the calculation of antibody concentration is added here. The calculation formula of specific affinity is as follows:

$\mathrm{<span\; class="notranslate">\; Affinity</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; Fitness</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}\mathrm{<span\; class="notranslate">\; ln</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; Density</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}$

Among them, Affinity(i) represents the affinity of antibody i; Fitness(i) represents the fitness of antibody i, which is related to distance. The shorter the distance of the antibody path, the higher the fitness of the antibody; Density(i) represents the antibody The concentration of i, that is, the more the same antibody path, the greater the concentration of antibody; α is a positive constant. Through this formula, it can be seen that the greater the fitness, the greater the affinity; the higher the concentration, the smaller the affinity.

(2) Population initialization: vaccinate first, and generate m antibodies (m paths) by implanting vaccines in the search space. The path generation method is to gradually extend from the starting point to the target point. path) to form the initial parent population The superscript i indicates the i-th generation, and the subscript m indicates the number of antibodies.

(3) Stopping condition: According to the fitness between the antibody and the antigen and the concentration between the antibodies, the affinity of the antibody is finally determined, and the genetic algebra and the number of the current parent population are calculated. The affinity of all antibodies in , if the conditions are met, terminate the operation and output the result, otherwise continue.

(4) Clonal expansion: n clones are generated for each antibody (path) in the above-mentioned antibody group, and at this time, m*n cloned antibodies (paths) are amplified, and the antibody group becomes Each path is replicated n times, and the path variation in the next step will be more sufficient, increasing the diversity of each generation of antibodies.

(5) High-frequency variation: clonal antibody group The antibody of each clone must undergo high-frequency mutation to obtain This refers to adding or deleting nodes to the antibody path.

(6) Recalculate the fitness value: recalculate the affinity of all individuals in the antibody population, including each parent antibody and its variant clone antibody.

(7) Memory antibody group update: from each parent antibody and its clone antibody Among them, the mutated clone antibody with the highest affinity is selected to form m new elite mutated antibody groups with the highest affinity And use it as a candidate to update the memory antibody group, and then from and Select the m with the highest affinity to form a new elite mutant antibody group The average affinity in the memory antibody population is then calculated.

(8) Immune self-regulation and receptor editing: Randomly generate r (r<m) brand new antibodies Replace the antibody population at this time The r antibodies with the lowest affinity are used to simulate the receptor editing process in the biological immune system and increase the diversity of the antibody population. In doing so, the algorithm generates the next generation of antibody populations $A_m^{i+1}=C_r^i+{\mathrm{D.}}_{m-r}^i,$ Then return to (3).

Step 3: The robot moves along the planned path.

Step 4: Judging whether the target point is reached, if it is reached, it will end, and if it is not reached, it will continue to travel along the planned path.

Since the information of the static obstacles in the environmental space is known in advance, each time the robot takes a step, it will be judged whether the distance between the robot and the known static obstacles is smaller than the radius of the rolling window (the sensing range of the sensor), so It can be concluded whether these static obstacles have appeared within the range of the rolling window.

Step 5: Determine whether the movement obstacle hinders the normal driving of the robot.

The robot does not need to consider the rolling window when it is moving, until the sensor finds that a new unknown obstacle enters the rolling window (that is, the distance between the unknown obstacle and the robot is less than the radius of the rolling window), the unknown dynamic obstacle is marked and Start to predict the trajectory of unknown obstacles. The prediction results are divided into the following two cases: one is that the unknown obstacle will not hinder the normal driving of the robot, then the robot can continue to travel along the previously planned path, that is, return to step 3. The second is to predict that the movement obstacle may hinder the normal driving of the robot, then go to step 6.

Step 6: It is predicted that the marked unknown dynamic obstacle will collide with the robot traveling along the previously planned path at the next T time, then record the position of the unknown moving obstacle at T time as a "static Obstacle" processing, taking into account the prediction error and the uncertain factors in the actual environment, expand the area of this "static obstacle" and record it as a dangerous area.

Step 7: When the dangerous area completely enters the rolling window, the robot takes the intersection of the rolling window and the previously planned path at the current moment as a temporary local target point, and the current position of the robot as the starting point to perceive static obstacles and dangerous areas in the window As the local environment information, a new path is planned by applying the immune network algorithm, and the robot drives along the newly planned path, and returns to step 4.

Through the description of the above steps, it can be concluded that the present invention can not only realize the global path planning of the mobile robot in a complex environment more efficiently, but also complete the local path planning with local unknown dynamic obstacles.

Figure 4 shows the relatively complex global path planning in the environment space, and multiple dense obstacles are set in the robot's motion environment. Every line connecting any two points that does not pass through obstacles in the figure represents a feasible path segment of the robot, and any path from s to g is a combination of these feasible path segments. As the number of obstacles increases, the path from s to g can be said to increase exponentially. It can be seen that the number of feasible paths in Figure 4 is very large, and the algorithm finally needs to select the path with the lowest cost from the large number of paths. The line from s to g in bold represents the final path solved by the algorithm. , it can be seen from Fig. 4 that the solved path is optimal. Figure 5 shows the relationship between path planning times and evolutionary algebra. In this working environment, 500 times of planning were carried out. Since the initial antibody (path) population of each planning is randomly generated, coupled with the randomness of high-frequency variation and the addition of new antibodies (paths) in each generation, each planning The evolution algebra needed to find the optimal path is uncertain. After 500 planning statistics, the average evolutionary algebra is only 248 generations, which is significantly lower than the traditional immune network algorithm whose evolutionary algebra is obviously high due to the large search space. From these 500 plans, the data whose evolutionary algebra (245 generations) is close to the average evolutionary algebra (248 generations) was selected for analysis. The ever-increasing changes, the abscissa represents the evolutionary algebra, and the ordinate represents the affinity. It can be seen from Figure 6 that the optimal antibody affinity of the population shows a gradual increasing trend with the increase of evolutionary generations. Although the algorithm has evolved for 500 generations, it has reached the highest affinity when it has evolved to 245 generations. degree; when the optimal affinity reaches the highest value, the average affinity has always fluctuated to a certain extent. This is because in order to maintain the diversity of antibodies in the population, new random antibodies are generated in each generation to replace the same number of antibodies in the population. Antibody with the lowest affinity.

The local path planning is based on the global path planning to plan for the dynamic unknown and uncertain obstacles in the working environment. uniform one-way motion. It can be seen that the planned global path and local path are optimal. In most cases, the obstacle information contained in the local environment is smaller or significantly smaller than the global information, so in terms of calculation amount, the local path planning is equivalent to the global path planning when the environment is simple, and the convergence speed of the algorithm is capable of real-time sexual demands.

Claims (4)

1. the mobile robot's dynamic path planning method based on Immune network algorithm, it is characterized in that: first based on Visual Graph method, pre-service is carried out to overall static environment space, apply Immune network algorithm afterwards and cook up global path, ambient condition information is detected in real time in the process of advancing, risk prediction is carried out to the unknown dynamic disorder entering sensing range, form new local environment Visual Graph according to the result of prediction and apply Immune network algorithm and plan the local path made new advances, continue to advance in the global path of the preplanning got back to after robot arrives the transient target point of sector planning.

2. the mobile robot's dynamic path planning method based on Immune network algorithm according to claim 1, is characterized in that:

(1), the implementation procedure of Immune network algorithm:

Through to the improvement of Immune network algorithm and and the combination of Visual Graph, the concrete performing step of algorithm is as follows:

(1) pre-service is carried out to the environment space that mobile robot runs, build Visual Graph;

(2) according to the Establishment and analysis of Visual Graph, sum up priori and also extract vaccine, not there is not setback in the bounding box of penetrate thing and the antibody of generation or path to comprise the antibody of generation or path;

(3) initialization of population: first vaccine inoculation, in search volume, produce m antibody and m paths by implanting vaccine, the generating mode in path progressively extends to impact point from starting point, forms initial parent population by this m antibody and m paths , wherein subscript i represented for the i-th generation, and subscript m represents antibody number;

(4) stop condition: the affinity finally determining antibody according to the concentration between the fitness between antibody and antigen and antibody, calculate current parent for population genetic algebra and in the affinity of all antibody, if satisfy condition, then stop computing and Output rusults, otherwise continue;

(5) clonal expansion: produce n clone body respectively to each antibody (path) in above-mentioned antibody population, now amplification is m*n clonal antibody (path), and now antibody population becomes every paths all copies n doubly, and next step path variation will be more abundant, add often for the diversity of antibody;

(6) high frequency closedown: clonal antibody group in the antibody of each clone all to experience high frequency closedown and obtain here refer to antagonist path to carry out increasing or deletion of node;

(7) recalculate adaptation value: all individualities in antagonist group, comprise each father's antibody and variant clone antibody thereof, recalculate its affinity;

(8) memory antibody group upgrades: from each father's antibody and clonal antibody thereof in, select to have the variant clone antibody of the highest affinity, elite's antibody variants group of what common composition m was new have most high-affinity and it can be used as the candidate upgrading memory antibody group, then from with in select the new elite's antibody variants group of m the composition that affinity is the highest calculate the average affinity in memory antibody group afterwards again;

(9) immune self-regulation and receptor editing: the individual brand-new antibody of stochastic generation r (r<m) replace now antibody population the individual antibody with minimum affinity of middle r, to simulate the receptor editing process in Immune System, increase the diversity of antibody population, thus, namely algorithm creates follow-on antibody population return step 4 afterwards;

(2), based on mobile robot's active path planning step of Immune network algorithm:

Send out for mobile the situation that robot working space is the unknown of environmental information part, concrete path planning step is as follows:

(1) global path planning is carried out to the Immune network algorithm of known static context information application enhancements;

(2) robot advances along the path cooked up;

(3) judge whether to arrive impact point, arrive and then terminate, do not arrive the path of then continuing along cooking up and advance;

Because the information of the static-obstacle thing in environment space is known in advance, so whenever robot ambulation one step will judge whether the distance between robot and each known static-obstacle thing is less than scrolling windows, the i.e. radius of the sensing range of sensor, so just can show whether these static-obstacle things have appeared in the scope of scrolling windows;

(4) judge whether dyskinesia hinders the normal traveling of robot;

(5) dope mark unknown dynamic barrier can with along the preplanning good path robot of advancing next certain T moment collides, then the position in this Unknown Motion barrier T moment is recorded, be used as " static-obstacle thing " process, consider the uncertain factor in the error of prediction and actual environment, the region of this " static-obstacle thing " is expanded, is denoted as hazardous location;

(6) when hazardous location enters after within scrolling windows completely, robot using the path intersection point of current time scrolling windows preplanning with it as interim localized target point, the position of current robot is as starting point, static-obstacle thing in perceived window and hazardous location are as local environmental information, application Immune network algorithm plans the path made new advances, robot, along the route of new planning, returns step 3.

3. the mobile robot's local paths planning method based on Immune network algorithm according to claim 2, it is characterized in that: in (4) step of (two) step, robot first need not consider scrolling windows in the process of advancing, until sensor finds that new unknown barrier enters within scrolling windows, namely, when the distance of unknown barrier and robot is less than the radius of scrolling windows, marks this unknown dynamic barrier and start to predict the movement locus of unknown barrier; The result of prediction is divided into following two kinds of situations: one is the normal traveling that unknown barrier can not hinder robot, then robot continue along the good path of preplanning advance, namely return to step 2; Two is dope the normal traveling that dyskinesia may hinder robot, then forward (5) step of (two) step to.

4. the mobile robot's local paths planning method based on Immune network algorithm according to claim 2, is characterized in that:

The design of antibody in Immune network algorithm:

After Visual Graph method is to the process of mobile work robot environment space, form antibody path only to need to consider the element in the set V on each barrier summit, do not need to consider any point outside in environment space, such hunting zone will significantly be reduced, and efficiency of algorithm is improved.The structure of each node is as follows:

IDpoint IDobject x y

Wherein IDpoint represents node serial number, and IDobject represents barrier numbering belonging to node, and x, y represent the transverse and longitudinal coordinate of node respectively, in mobile robot path planning problem, antigen represents problem to be solved and optimal path, the application is set as the Euclidean distance of starting point s and impact point g, antibody represents the solution of required problem, namely the feasible path searched out, it is by the starting point of mobile robot, the broken line that impact point and a series of intermediate node connect into is formed, for describing path trend clearly, through the order of node when in antibody, the order of element represents moveable robot movement, antibody adopts string encoding mode, its length can change with the number of node, the data structure of antibody enter lower shown in:

Affinity Density Fitness Length s … v … g

Wherein Affinity represents the affinity of antibody, evaluates the quality of antibody here with affinity; Fitness represents the fitness of antibody, has and has higher fitness compared with the antibody of short path; Density represents the concentration of antibody, the ratio namely in antibody population shared by same antibody, and Length represents the length of antibody by s to g, and remainder is form the node in path, this storage organization when antibody changes, the length of flexibly changing antibody;

The calculating of affinity in Immune network algorithm:

The application, in order to suppress and avoid the appearance of precocious phenomenon, adds the calculating of antibody concentration here, and the computing formula of concrete affinity is as follows:

$\mathrm{Affinity}\left(i\right)=\frac{\mathrm{Fitness}\left(i\right)}{1+\mathrm{\&alpha;}\ln (1+\mathrm{Density}\left(i\right))}$

Wherein Affinity (i) represents the affinity of antibody i; Fitness (i) represents the fitness of antibody i, and distance dependent, and the distance in antibody path is shorter, and the fitness of its antibody is higher; Density (i) represents the concentration of antibody i, and namely identical antibody path is more, and the concentration of antibody is larger; α is a positive constant, and can find out that fitness is larger by this formula, affinity is larger; Concentration is higher, and affinity is less.