CN106444773B - An Environmental Modeling Method Based on Recursively Simplified Visual Graph - Google Patents

Abstract

The invention relates to an environment modeling method, in particular to an environment modeling method based on recursion simplified visual, which comprises the following steps: (1) recording the position of the robot and the arrival position, (2) connecting S-H-G-L-S to form A quadrangle, (3) traversing each current side of the quadrangle, (4) judging whether the current side is intersected with the obstacle, (5) determining A midway point, (6) transferring each side of the newly enclosed polygon S-A-H-B-G-L-C-S to the step 3 for traversing, and (7) finishing the traversing of the current side of the polygon. The invention finally obtains a polygonal area, the obstacles outside the polygonal area can be completely simplified, and the obstacles in the polygonal area are the obstacles to be considered in the robot path planning. The invention effectively reduces the number of visual lines and improves the execution efficiency of the subsequent robot path planning algorithm.

Description

An Environmental Modeling Method Based on Recursively Simplified Visual Graph

technical field

The invention relates to an environment modeling method, in particular to an environment modeling method based on recursively simplified visual graphs.

Background technique

When a mobile robot moves in an environment with multiple obstacles, it needs to find an optimal path from the start point to the end point that can avoid all obstacles, such as the shortest path, the least time-consuming, and the lowest energy consumption. In order to solve this problem, mobile robots generally need to model the environment first when performing path planning. The existing environment modeling mainly includes: grid graph, tangent graph, Voronoi graph, probability graph, and visual graph.

The modeling method based on the visual graph represents the obstacles in the environment by a convex polygonal envelope. The vertices of the polygon, together with the starting point and end point of the mobile robot, are regarded as mass points. The coordinates of each point are known in the global coordinate system. Visually judge the start point and end point and the vertices of the obstacle polygon: if the line segment formed by the two-point connection does not intersect any obstacle polygon, then the two points are said to be visible, and the line segment is called the visible line. Due to the simple and intuitive characteristics of visual graphs, the modeling method based on visual graphs has become a hot spot that many scholars pay attention to.

At present, there are two main methods of visual map simplification, one is the dynamic visual map method proposed by Huang, which can simplify some "redundant" obstacles; the other is the improved dynamic visual map method, proposed by Zhang Qi, called In order to simplify the visualization method, this method can eliminate irrelevant obstacles to a greater extent by designing necessary obstacle rules. However, there is a problem in the simplified visualization method, that is, the problem of wrongly simplifying obstacles may occur in complex environments.

Contents of the invention

In order to overcome the deficiencies in the prior art, the purpose of the present invention is to provide an environment modeling method based on recursively simplified visual graphs. Through the method provided by the present invention, a polygonal area can be finally obtained, and all obstacles outside the area can be simplified, and the obstacles in the area are the obstacles that need to be considered in the path planning of the robot. The invention effectively reduces the number of visible lines and improves the execution efficiency of the follow-up robot path planning algorithm.

In order to achieve the above-mentioned purpose of the invention and solve the problems existing in the prior art, the technical solution adopted by the present invention is: an environment modeling method based on recursively simplified visual graphs, including the following steps:

Step 1. Record the location and arrival position of the robot, record the location of the robot as point S, and record the expected arrival position as point G, and then use the computer to scan the entire map environment where the robot is located, and use a closed polygon to map each Obstacles are enveloped and these polygons are preserved;

Step 2. Connect S-H-G-L-S to form a quadrilateral, connect point S and point G, and the line segment SG is called the robot crossing line. At this time, the crossing line SG will intersect with multiple obstacle polygons, and record these intersecting obstacle polygons 2, 7, and 8 , and then find a point on both sides of the crossing line SG, which must meet the following two conditions: first, it is a vertex of these intersecting obstacle polygons 2, 7, 8, and second, it is on the crossing line The point on one side of SG is the farthest from the crossing line, and is recorded as point H and point L respectively, connecting S-H-G-L-S to form a quadrilateral;

Step 3. Traverse each current side of the quadrilateral, i.e. the current sides SH, HG, GL, LS. The endpoints of each current side are the current side starting point and the current side end point respectively. For example, when traversing to the current side HG, the current side starting point It is point H, and the end point of the current side is point G;

Step 4. Determine whether the current edge intersects with obstacles. If it does not intersect, such as the current edge GL, save the current edge to the active area set, and then return to step 3 to continue traversing the subsequent current edges. When the traversal is completed, skip Go to step 7; if they intersect, such as the current edge SH, HG, LS, then go to step 5;

Step 5. Determine the halfway point. Among all the obstacles intersecting with the current side, take the vertex of these obstacles that is farthest from the crossing line SG and on the same side as the current side, and record it as the halfway point A, B, C, and connect them respectively The starting point of the current edge and the halfway point, the halfway point and the end point of the current edge form two new current edges; for example, the original current edge SH is formed by connecting the starting point S of the current edge to the intermediate point A, and then connecting the intermediate point A to the end point H of the current edge. Two sides SA and AH form the current current side: for example, the original current side HG connects the starting point H of the current side to the midway point B, and then connects the midway point B to the end point G of the current side to form the current current side composed of two sides HB and BG Side; for example, the original current side LS is connected by the starting point L of the current side to the midway point C, and then the midway point C is connected to the end point S of the current side to form the current current side composed of two sides LC and CS;

Step 6, transfer each edge of the newly formed polygon S-A-H-B-G-L-C-S to step 3 for traversal;

Step 7. After traversing the current sides of the polygon, the polygon surrounded by all the sides in the active area set is the output result. The obstacle polygons 1, 3, 10, and 11 outside the active area do not need to be considered, while the obstacles in the active area Polygons 2, 4, 5, 6, 7, 8, and 9 are what the robot needs to consider when planning its path.

The beneficial effects of the present invention are: an environment modeling method based on recursively simplified visual graphs, comprising the following steps: (1) recording where the robot is and its arrival position, (2) connecting S-H-G-L-S to form a quadrilateral (3) traversing each of the quadrilateral On the current side, (4) judge whether the current side intersects with obstacles, (5) determine the halfway point, (6) turn each side of the newly formed polygon S-A-H-B-G-L-C-S to step 3 for traversal, (7) the current side of the polygon The traversal is complete. Compared with the prior art, the present invention finally obtains a polygonal area, all obstacles outside the area can be simplified, and the obstacles in the area are the obstacles that need to be considered in the path planning of the robot. The invention effectively reduces the number of visible lines and improves the execution efficiency of the follow-up robot path planning algorithm.

Description of drawings

Fig. 1 is a flowchart of the method steps of the present invention.

Fig. 2 is a visual diagram generated in step 2 of the method of the present invention.

Fig. 3 is a visual diagram generated by the first layer of recursion in the method of the present invention.

Fig. 4 is a visual diagram generated by the second layer of recursion in the method of the present invention.

Fig. 5 is a visual diagram generated by the third layer of recursion in the method of the present invention.

Detailed ways

The present invention will be further described below in conjunction with accompanying drawing.

As shown in Figure 1, an environment modeling method based on recursively simplified visual graphs includes the following steps:

Step 1. Record the location and arrival position of the robot, record the location of the robot as point S, and record the expected arrival position as point G, and then use the computer to scan the entire map environment where the robot is located, and use a closed polygon to map each Obstacles are enveloped and these polygons are preserved;

Step 2. Connect S-H-G-L-S to form a quadrilateral, connect point S and point G, and the line segment SG is called the robot crossing line. At this time, the crossing line SG will intersect with multiple obstacle polygons, and record these intersecting obstacle polygons 2, 7, and 8 , and then find a point on both sides of the crossing line SG, which must meet the following two conditions: first, it is a vertex of these intersecting obstacle polygons 2, 7, 8, and second, it is on the crossing line The point on one side of SG is the farthest from the crossing line, and is recorded as point H and point L respectively, connecting S-H-G-L-S to form a quadrilateral;

Step 3. Traverse each current side of the quadrilateral, i.e. the current sides SH, HG, GL, LS. The endpoints of each current side are the current side starting point and the current side end point respectively. For example, when traversing to the current side HG, the current side starting point It is point H, and the end point of the current side is point G;

Step 4. Determine whether the current edge intersects with obstacles. If it does not intersect, such as the current edge GL, save the current edge to the active area set, and then return to step 3 to continue traversing the subsequent current edges. When the traversal is completed, skip Go to step 7; if they intersect, such as the current edge SH, HG, LS, then go to step 5;

Step 5. Determine the halfway point. Among all the obstacles intersecting with the current side, take the vertex of these obstacles that is farthest from the crossing line SG and on the same side as the current side, and record it as the halfway point A, B, C, and connect them respectively The starting point of the current edge and the halfway point, the halfway point and the end point of the current edge form two new current edges; for example, the original current edge SH is formed by connecting the starting point S of the current edge to the intermediate point A, and then connecting the intermediate point A to the end point H of the current edge. Two sides SA and AH form the current current side: for example, the original current side HG connects the starting point H of the current side to the midway point B, and then connects the midway point B to the end point G of the current side to form the current current side composed of two sides HB and BG Side; for example, the original current side LS connects the starting point L of the current side to the midway point C, and then connects the midway point C to the end point S of the current side to form the current current side composed of two sides LC and CS;

Step 6, transfer each edge of the newly formed polygon S-A-H-B-G-L-C-S to step 3 for traversal;

Step 7. After traversing the current sides of the polygon, the polygon surrounded by all the sides in the active area set is the output result. The obstacle polygons 1, 3, 10, and 11 outside the active area do not need to be considered, while the obstacles in the active area Polygons 2, 4, 5, 6, 7, 8, and 9 are what the robot needs to consider when planning its path.

The specific working process is as follows:

The pseudo-code used in the present invention is shown in Table 1, which includes a main function and a recursive kernel function.

Table 1

The main function is the program entry of the present invention. Through the given starting point S and end point G, the crossing line line_sg is obtained by the function getLine, and the obstacle set obs_pass intersecting with the crossing line is obtained by the function getObsPass, and the crossing line is obtained by the function getHighPoint and getLowPoint. On both sides of line_sg, the obstacle vertices high (point H) and low (point L) that are farthest from line_sg and passed by line_sg, connect S-H-G-L-S, and you can get the visible view in Figure 2. The black color block is the obstacle polygon , the dotted line is the boundary of the current active area. Then, by calling the recursive kernel function, the boundary line of the active area evolved from each side of S-H-G-L-S can be calculated respectively, and the getMidPoint function is to find the vertex of the obstacle that is the farthest side from the line_sg. . The visible view formed by the first layer of recursion is shown in Figure 3, the visible view formed by the second layer of recursion is shown in Figure 4, and the visible view formed by the third layer of recursion is shown in Figure 5. Finally, the program ends when it recurses to the third layer, and the boundary line of the active region is saved in the online collection activeRegion, and the final visible view formed is shown in Figure 5.

In Figure 5, the obstacles (1, 3, 10, 11) outside the active area will be simplified in the subsequent path planning and do not need to be considered, while the obstacles (2, 4, 5, 6, 7, 8, 9) are what the robot needs to consider when planning the path.

Claims (1)

1. A method for modeling environments based on recursively simplified visual graphs, comprising the following steps: Step 1. Record the location and arrival position of the robot, record the location of the robot as point S, and record the expected arrival position as point G, and then use the computer to scan the entire map environment where the robot is located, and use a closed polygon to map each Obstacles are enveloped and these polygons are preserved; Step 2. Connect S-H-G-L-S to form a quadrilateral, connect point S and point G, and the line segment SG is called the robot crossing line. At this time, the crossing line SG will intersect with multiple obstacle polygons, and record these intersecting obstacle polygons 2, 7, and 8 , and then find a point on both sides of the crossing line SG, which must meet the following two conditions: first, it is a vertex of these intersecting obstacle polygons 2, 7, 8, and second, it is on the crossing line Within the range of one side of SG, this point is the farthest from the crossing line, and is recorded as point H and point L respectively, connecting S-H-G-L-S to form a quadrilateral, which is characterized in that: Step 3. Traverse each current side of the quadrilateral, that is, the current sides SH, HG, GL, and LS. The endpoints of each current side are the current side starting point and the current side end point respectively. When traversing to the current side HG, the current side starting point is Point H, the end point of the current side is point G; Step 4. Determine whether the current edge intersects with obstacles. If it does not intersect, that is, the current edge GL, save the current edge to the active area set, and then return to step 3 to continue traversing the subsequent current edges. When the traversal is completed, skip Go to step 7; if it intersects, that is, the current edge SH, HG, LS, then go to step 5; Step 5. Determine the halfway point. Among all the obstacles intersecting with the current side, take the vertex of these obstacles that is farthest from the crossing line SG and on the same side as the current side, and record it as the halfway point A, B, C, and connect them respectively The starting point of the current edge and the halfway point, the halfway point and the end point of the current edge form two new current edges; the original current edge SH is formed by connecting the starting point S of the current edge to the intermediate point A, and then connecting the intermediate point A to the end point H of the current edge to form SA The current side is composed of the two sides AH: the original current side HG is connected by the starting point H of the current side to the midway point B, and then the midway point B is connected to the end point G of the current side to form the current side composed of two sides HB and BG; The original current edge LS connects the starting point L of the current edge to the halfway point C, and then connects the halfway point C to the end point S of the current edge to form the current edge consisting of two edges LC and CS; Step 6, transfer each edge of the newly formed polygon S-A-H-B-G-L-C-S to step 3 for traversal; Step 7. After traversing the current sides of the polygon, the polygon surrounded by all the sides in the active area set is the output result. The obstacle polygons 1, 3, 10, and 11 outside the active area do not need to be considered, while the obstacles in the active area Polygons 2, 4, 5, 6, 7, 8, and 9 are what the robot needs to consider when planning its path.