CN110595478A - Robot full-coverage path planning method, device and equipment based on off-line map - Google Patents
Robot full-coverage path planning method, device and equipment based on off-line map Download PDFInfo
- Publication number
- CN110595478A CN110595478A CN201910869194.1A CN201910869194A CN110595478A CN 110595478 A CN110595478 A CN 110595478A CN 201910869194 A CN201910869194 A CN 201910869194A CN 110595478 A CN110595478 A CN 110595478A
- Authority
- CN
- China
- Prior art keywords
- path
- sub
- map
- line
- area
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 68
- 238000010408 sweeping Methods 0.000 claims abstract description 18
- 238000004364 calculation method Methods 0.000 claims description 8
- 230000011218 segmentation Effects 0.000 claims description 8
- 230000010354 integration Effects 0.000 claims description 6
- 238000007781 pre-processing Methods 0.000 claims description 4
- 238000000638 solvent extraction Methods 0.000 claims description 3
- 238000004140 cleaning Methods 0.000 description 5
- 239000011159 matrix material Substances 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 241001417527 Pempheridae Species 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/20—Instruments for performing navigational calculations
- G01C21/206—Instruments for performing navigational calculations specially adapted for indoor navigation
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
Abstract
The invention discloses a robot full-coverage path planning method based on an off-line map. The method is suitable for an off-line map, can calculate the path points of the full-coverage path of the sweeping robot in advance, and can improve the efficiency of path planning.
Description
Technical Field
The invention relates to a planning method for a sweeping robot to sweep a full-coverage path, in particular to a robot full-coverage path planning method, a device and equipment based on an off-line map.
Background
The sweeping robot is a household service robot and is currently a popular research field. The sweeping robot has two main cleaning modes, one mode is that the sensor is used for sensing environmental information, and when the sweeping robot sees that an obstacle exists in a short distance through a laser or a vision sensor, the walking direction is changed in advance to bypass the obstacle to continue cleaning. This random sweeping method has the disadvantages of high repetition rate and low efficiency. Another is to construct a map of the indoor environment in advance so that the cleaned part and the uncleaned part can be distinguished at the time of cleaning, thereby reducing the repetition rate of cleaning. For the sweeping robot, the coverage rate of the cleaning path is also one of the important indexes for evaluating the performance of the sweeping robot. How to plan a full coverage path by using known map information is a key research technology of the sweeping robot.
Disclosure of Invention
The purpose of the invention is as follows: aiming at the defects in the prior art, the invention aims to provide a robot full-coverage path planning method, device and equipment based on an off-line map, so that the sweeping robot sweeping path planning efficiency and coverage rate are improved.
The technical scheme is as follows: a robot full-coverage path planning method based on an off-line map comprises the following steps:
(1) dividing the map by a sliding method to obtain sub-regions;
(2) planning the traversal sequence among the subregions;
(3) planning a path inside each sub-area;
(4) and connecting the paths of all the sub-areas to obtain the path of the whole map.
Further, the step (1) specifically includes the following sub-steps:
(1.1) finding a point with the minimum y coordinate in a feasible area of a map, and constructing a straight line which passes through the point and is parallel to the x axis, and marking the straight line as a sliding line l;
(1.2) aligning the slide line l with the first row and counting the number of connected domains in the first row, starting from the second row;
(1.3) sliding downwards along the y-axis direction and calculating the connectivity of each row, namely the number of connected domains;
(1.4) for a certain connected domain s _ l in the previous row, if only one connected domain s _ c in the current row is connected with the connected domain s _ l, dividing s _ c into sub-regions where s _ l is located; if n connected domains are communicated with s _ l in the current row and n is greater than 1, ending the division of the sub-region where s _ l is located and starting the division of n new sub-regions;
(1.5) for a certain connected domain s _ c in the current row, if 0 or n connected domains are connected with the connected domain s _ c in the previous row, and n is greater than 1, ending the division of the sub-area where the n connected domains are located, and starting the division of 1 new area;
(1.6) repeating the steps (1.3) - (1.5) until l slides to the bottom of the map, and the division is finished.
Further, the traversal order between the planning sub-regions in the step (2) adopts the following method:
(2.1) acquiring a sub-area where the robot is located according to the initial position of the robot on the map, and taking the sub-area as a first traversed sub-area;
(2.2) after the first sub-area is determined, planning the traversing sequence of the rest sub-areas by using a TSP method.
Further, the planning of the path inside each sub-region in step (3) specifically adopts the following method:
(3.1) calculating a path line of the sub-area;
and (3.2) connecting the path lines in sequence to obtain the arch-shaped path of the sub-area.
Further, the step (3.1) specifically adopts the following method:
(3.1.1) obtaining the maximum value and the minimum value of all map point coordinates in the sub-area: x _ min, x _ max, y _ min, y _ max;
(3.1.2) calculating a first path line: fixing y to y _ init, gradually increasing the value of x by a step ds from x to x _ init, and sequentially using the obtained (x, y) combination as the coordinates of the path point until x is larger than or equal to x _ max; wherein, y _ init is y _ min + do, and x _ init is x _ min + do;
(3.1.3) calculate the remaining path lines: gradually increasing the value of y by the step length dp until y is larger than y _ max, taking the obtained value as the y coordinate of the path point on each path line, and calculating the x coordinate by using the same method as the method (3.1.2);
then, before step (3.1.2), a minimum distance do between the route and the obstacle, a minimum distance ds between route points, and a route line pitch dp are set.
Further, the step (3.2) adopts the following method:
(3.2.1) sequentially calculating paths between the current position of the robot and four vertexes of the sub-region by using an A-x algorithm, and selecting the vertex with the shortest path length as a starting point for traversing the sub-region; wherein, the vertex is the first point and the last point on the first route of the area, and the first point and the last point on the last route are numbered 0, 1, 2 and 3 respectively;
(3.2.2) if the number of the starting point is less than 2, sequentially connecting the paths from the first path line to the lower part; otherwise, the paths are sequentially connected from the last path line to the top;
(3.2.3) if the number of the start point is 0 or 2, connecting the path points as the zigzag path; if the starting point number is 1 or 3, the path points are connected as S-shaped paths.
Further, the step (3.2.3) is specifically: if the number of the starting point is 0 or 2, sequentially connecting the path points according to the sequence from left to right when the starting points are connected for the first time, connecting the last path point with the rightmost point on the next path line, and sequentially connecting the points on the next path line according to the sequence from right to left; by analogy, a bow-shaped path is obtained;
if the starting point number is 1 or 3, sequentially connecting the path points according to the sequence from right to left when the starting points are connected for the first time, connecting the last path point with the leftmost point on the next path line, and sequentially connecting the points on the next path line according to the sequence from left to right; and by analogy, an S-shaped path is obtained.
Further, the map area is preprocessed before the step (1), and the sub-area is preprocessed before the step (3.1), wherein the preprocessing method comprises the following steps:
(A) calculating a main direction of the region;
(B) the map of the area is rotated so that the main direction coincides with the direction of the x-axis of the map.
Further, the specific method for calculating the main direction of the area in the step (a) is as follows:
(A1) detecting a boundary line segment of a map;
(A2) extracting all straight line segments in the boundary line segment, wherein the length of each straight line segment is not less than a preset threshold value;
(A3) and calculating the direction of each straight line segment, grouping the directions of each straight line segment according to the angle range, and taking the average value of the angle ranges of the groups with the highest frequency as the main direction of the area.
Further, the step (4) is specifically: and (4) taking the last path point of each sub-area in the step (3) as the current position of the robot to calculate the initial path point of the next sub-area, and connecting according to the traversal sequence between the sub-areas obtained in the step (2) to obtain the path of the whole map.
A robot full coverage path planning device based on an off-line map comprises:
a map segmentation module: the method comprises the steps of dividing a map by a sliding method to obtain sub-areas;
a traversal order planning module: for planning a traversal order between the sub-regions;
an internal path planning module: for planning a path inside each sub-region;
a path integration module: the path for connecting all sub-areas obtains the path of the entire map.
Furthermore, the sweeping robot further comprises a driving module for driving the sweeping robot to walk according to the path output by the path integration module.
Further, the map segmentation module: the method is specifically used for:
finding a point with the minimum y coordinate in a feasible area of the map, constructing a straight line which passes through the point and is parallel to the x axis, and marking the straight line as a sliding line l; sliding downwards along the y-axis direction and calculating the number of connected domains in each row;
if only one connected domain in the current row is connected with one connected domain in the previous row, dividing the connected domain in the current row into sub-regions where the connected domain in the previous row is located; if only one connected domain in the current line is connected with one connected domain in the previous line, starting to divide a plurality of new sub-regions;
for a certain connected domain s _ c in the current row, if 0 or n connected domains are connected with the connected domain s _ c in the previous row, and n is greater than 1, ending the division of the sub-region where the n connected domains are located, and starting the division of 1 new region;
until l slides to the bottom of the map, the partitioning ends.
Further, the traversal order planning module includes:
the initial position acquisition module is used for acquiring a sub-area where the initial position of the robot on the map is located as a first traversed sub-area;
and the TSP module is used for planning the traversing sequence of the rest sub-areas based on the TSP.
Further, the method also comprises the following steps:
the main direction calculation module is used for calculating the main direction of the map area or the sub-area;
the rotating module is used for rotating the map to enable the main direction to be consistent with the direction of the x axis of the map;
further, the internal path planning module includes:
route calculation module: a path line for calculating a sub-region;
route line connection module: and the path lines are sequentially connected to obtain the zigzag path of the sub-area.
An apparatus comprising a processor and a memory, the memory for storing a program, the processor for executing the program to perform the above-described off-line map-based robot full coverage path planning method.
Has the advantages that: the map is divided into a plurality of more regular sub-areas by a sliding method, then the traversing sequence among the sub-areas is planned by using a traveler problem, finally the zigzag path in each sub-area is planned, and the paths of all the sub-areas are connected to obtain the path of the whole map. The method is suitable for an off-line map, can calculate the path points of the full-coverage path of the sweeping robot in advance, and can improve the efficiency of path planning.
Drawings
FIG. 1 is a flow chart of the method of the present invention.
Detailed Description
The technical solution is described in detail below with reference to a preferred embodiment and the accompanying drawings.
A robot full-coverage path planning device based on an off-line map comprises a map segmentation module, a traversal sequence planning module, an internal path planning module, a path integration module, a driving module, a main direction calculation module and a rotation module.
A map segmentation module: the method is used for segmenting a map by a sliding method to obtain sub-areas, and is specifically used for:
finding a point with the minimum y coordinate in a feasible area of the map, constructing a straight line which passes through the point and is parallel to the x axis, and marking the straight line as a sliding line l; sliding downwards along the y-axis direction and calculating the number of connected domains in each row;
if only one connected domain in the current row is connected with one connected domain in the previous row, dividing the connected domain in the current row into sub-regions where the connected domain in the previous row is located; if only one connected domain in the current line is connected with one connected domain in the previous line, starting to divide a plurality of new sub-regions;
for a certain connected domain s _ c in the current row, if 0 or n connected domains are connected with the connected domain s _ c in the previous row, and n is greater than 1, ending the division of the sub-region where the n connected domains are located, and starting the division of 1 new region;
until l slides to the bottom of the map, the partitioning ends.
A traversal order planning module: the system is used for planning a traversal sequence among the sub-areas and comprises an initial position acquisition module and a TSP module;
the initial position acquisition module is used for acquiring a sub-area where the initial position of the robot on the map is located as a first traversed sub-area;
the TSP module is used for planning the traversing sequence of the rest sub-areas based on the TSP.
The internal path planning module is used for planning a path inside each sub-area and comprises a path line calculation module and a path line connection module.
The path line calculation module is used for calculating path lines of the sub-areas;
the path line connecting module is used for sequentially connecting the path lines to obtain the zigzag path of the sub-area.
The path integration module is used for connecting paths of all the sub-areas to obtain a path of the whole map.
The driving module is used for driving the sweeping robot to walk according to the path output by the path integration module.
The main direction calculation module is used for calculating the main direction of the map area or the sub-area.
The rotation module is used for rotating the map to enable the main direction to be consistent with the direction of the x axis of the map.
In this embodiment, for an obtained offline map, the map is divided into a plurality of relatively regular sub-areas by a sliding method, then a traversary order between the sub-areas is planned by using a traveler problem, and finally a zigzag path inside each sub-area is planned and the paths of all the sub-areas are connected to obtain the path of the whole map.
As shown in fig. 1, the implementation method of the apparatus specifically includes the following steps:
(1) dividing the map by a sliding method to obtain sub-regions;
(2) planning the traversal sequence among the subregions;
(3) planning a path inside each sub-area;
(4) and connecting the paths of all the sub-areas to obtain the path of the whole map.
The detailed method comprises the following steps:
map segmentation
The present embodiment uses a "sliding" method to divide the environment map into several more regular sub-areas, that is, an obstacle area and a feasible area of the map are obtained by sliding a line and are divided. In this method, the selection of the direction of the sliding line will affect the planning effect of the final path, especially the number of the sub-regions obtained by dividing and the number of turns of the path in each sub-region. The present embodiment uses the main direction of the map as the direction of the slide line. The map segmentation mainly comprises the following steps:
first, the map area is preprocessed, i.e.
(A) The method for calculating the main direction of the area specifically comprises the following steps:
(A1) detecting a boundary line segment of a map;
(A2) extracting all straight line segments in the boundary line segment, wherein the length of each straight line segment is not less than a preset threshold value, such as 1 m;
(A3) the direction of each straight line segment is calculated, the directions of the straight line segments are grouped according to the angle range, the average value of the angle range of the group with the highest frequency count is used as the main direction of the area, the angle between the direction of each straight line segment and the x axis of the map is calculated in the embodiment, an angle histogram is drawn according to the size of a certain group distance, and the average value of the group with the highest frequency count is selected as the main direction of the map.
(B) And calculating a rotation matrix of the map relative to a map coordinate system according to the main direction, and rotating the map of the area to enable the main direction to be consistent with the direction of the x axis of the map.
Then, the rotated map is divided to obtain sub-regions. The method specifically comprises the following steps:
(1.1) the coordinate system of the known picture is defined as: the origin is the first point at the upper left corner of the picture, the positive direction of the x axis is towards the right, and the positive direction of the y axis is towards the lower; finding a point with the minimum y coordinate in a feasible area of the map, constructing a straight line which passes through the point and is parallel to the x axis, and marking the straight line as a sliding line l;
(1.2) aligning the slide line l with the first row and counting the number of connected domains in the first row, starting from the second row; "rows" are rows of pixels in the map picture;
(1.3) sliding downwards along the y-axis direction and calculating the connectivity of each row, namely the number of connected domains;
(1.4) for a certain connected domain s _ l in the previous row, if only one connected domain s _ c in the current row is connected with the connected domain s _ l, dividing s _ c into sub-regions where s _ l is located; if n connected domains are communicated with s _ l in the current row and n is greater than 1, ending the division of the sub-region where s _ l is located and starting the division of n new sub-regions;
(1.5) for a certain connected domain s _ c in the current row, if 0 or n connected domains are connected with the connected domain s _ c in the previous row, and n is greater than 1, ending the division of the sub-area where the n connected domains are located, and starting the division of 1 new area;
(1.6) repeating the steps (1.3) - (1.5) until l slides to the bottom of the map, and the division is finished.
Sub-region traversal order determination
In the previous step, the map is divided into a plurality of areas, and then the traversal sequence of the sub-areas, namely the sweeping sequence of the sweeper needs to be determined. The specific process is as follows:
(2.1) acquiring a sub-area where the robot is located according to the initial position of the robot on the map, and taking the sub-area as a first traversed sub-area;
(2.2) after the first sub-region is determined, the traversal order of the rest of the sub-regions is planned using the TSP method (tracking Salesman Problem, traveler's Problem).
Subregion glyph path planning
In order to obtain the sweeping path of the whole map, after the traversal order of the sub-areas is determined, the traversal path inside each sub-area needs to be planned. Mainly comprises the following steps:
first, the subregions are preprocessed, i.e.
(A) Calculating the main direction of the sub-region, and the specific method comprises the following steps:
(A1) detecting a boundary line segment of a map;
(A2) extracting all straight line segments in the boundary line segment, wherein the length of each straight line segment is not less than a preset threshold value, such as 1 m;
(A3) the direction of each straight line segment is calculated, the directions of the straight line segments are grouped according to the angle range, the average value of the angle range of the group with the highest frequency count is used as the main direction of the area, the angle between the direction of each straight line segment and the x axis of the map is calculated in the embodiment, an angle histogram is drawn according to the size of a certain group distance, and the average value of the group with the highest frequency count is selected as the main direction of the sub-area.
(B) And calculating a rotation matrix of the map relative to a map coordinate system according to the main direction, and rotating the map of the area to enable the main direction to be consistent with the direction of the x axis of the map, wherein the consistent direction is parallel to the x axis.
Then, (3.1) calculating a path line of the sub-area, which specifically comprises:
(3.1.1) obtaining the maximum value and the minimum value of all map point coordinates in the sub-area: x _ min, x _ max, y _ min, y _ max;
(3.1.2) calculating a first path line: fixing y to y _ init, gradually increasing the value of x by a step ds from x to x _ init, and sequentially using the obtained (x, y) combination as the coordinates of the path point until x is larger than or equal to x _ max (the value when x is larger than or equal to x _ max is not used as the coordinates of the path point); wherein, y _ init is y _ min + do, and x _ init is x _ min + do;
(3.1.3) calculate the remaining path lines: gradually increasing the value of y by the step length dp until y is larger than y _ max, taking the obtained value as the y coordinate of the path point on each path line, and calculating the x coordinate by using the same method as the method (3.1.2);
then, before step (3.1.2), a minimum distance do between the route and the obstacle, a minimum distance ds between route points, and a route line pitch dp are set.
And (3.2) sequentially connecting the path lines to obtain the arch-shaped path of the sub-area, and adopting the following method:
(3.2.1) sequentially calculating paths between the current position of the robot and four vertexes of the sub-region by using an A-Star algorithm, and selecting the vertex with the shortest path length as a starting point for traversing the sub-region; wherein, the vertex is the first point and the last point on the first route of the area, and the first point and the last point on the last route are numbered 0, 1, 2 and 3 respectively; wherein the last path line means: in step (3.1.3), the last resulting one of all the path lines that satisfies y < ═ y _ max is calculated.
(3.2.2) if the number of the starting point is less than 2, sequentially connecting the paths from the first path line to the lower part; otherwise, the paths are sequentially connected from the last path line to the top;
(3.2.3) if the number of the start point is 0 or 2, connecting the path points as the zigzag path; if the start point number is 1 or 3, the path points are connected as S-shaped paths (i.e., mirrored zigzag paths).
The step (3.2.3) is specifically as follows: if the number of the starting point is 0 or 2, sequentially connecting the path points according to the sequence from left to right when the starting points are connected for the first time, connecting the last path point with the rightmost point on the next path line, and sequentially connecting the points on the next path line according to the sequence from right to left; by analogy, a bow-shaped path is obtained;
if the starting point number is 1 or 3, sequentially connecting the path points according to the sequence from right to left when the starting points are connected for the first time, connecting the last path point with the leftmost point on the next path line, and sequentially connecting the points on the next path line according to the sequence from left to right; and by analogy, an S-shaped path is obtained.
The step (4) is specifically as follows: and (4) taking the last path point of each sub-area in the step (3) as the current position of the robot to calculate the initial path point of the next sub-area, and connecting according to the traversal sequence between the sub-areas obtained in the step (2) to obtain the path of the whole map.
The embodiment also provides equipment comprising a processor and a memory, wherein the memory is used for storing programs, and the processor is used for running the programs so as to execute the robot full coverage path planning method based on the offline map.
The above is only a preferred embodiment of the present invention, and it will be apparent to those skilled in the art that several modifications and improvements can be made without departing from the principle of the present invention, and these modifications and improvements should be considered as the protection scope of the present invention.
Claims (16)
1. The robot full-coverage path planning method based on the off-line map is characterized by comprising the following steps of:
(1) dividing the map by a sliding method to obtain sub-regions;
(2) planning the traversal sequence among the subregions;
(3) planning a path inside each sub-area;
(4) and connecting the paths of all the sub-areas to obtain the path of the whole map.
2. The off-line map-based robot full coverage path planning method according to claim 1, wherein the step (1) specifically comprises the following sub-steps:
(1.1) finding a point with the minimum y coordinate in a feasible area of a map, and constructing a straight line which passes through the point and is parallel to the x axis, and marking the straight line as a sliding line l;
(1.2) aligning the slide line l with the first row and counting the number of connected domains in the first row, starting from the second row;
(1.3) sliding downwards along the y-axis direction and calculating the connectivity of each row, namely the number of connected domains;
(1.4) for a certain connected domain s _ l in the previous row, if only one connected domain s _ c in the current row is connected with the connected domain s _ l, dividing s _ c into sub-regions where s _ l is located; if n connected domains are communicated with s _ l in the current row and n is greater than 1, ending the division of the sub-region where s _ l is located and starting the division of n new sub-regions;
(1.5) for a certain connected domain s _ c in the current row, if 0 or more than n (n >1) connected domains are connected with the connected domain s _ c in the previous row, ending the division of the sub-area where the n connected domains are located, and starting the division of 1 new area;
(1.6) repeating the steps (1.3) - (1.5) until l slides to the bottom of the map, and the division is finished.
3. The off-line map-based robot full coverage path planning method according to claim 1, wherein the traversal sequence between the planning sub-areas in the step (2) adopts the following method:
(2.1) acquiring a sub-area where the robot is located according to the initial position of the robot on the map, and taking the sub-area as a first traversed sub-area;
(2.2) after the first sub-area is determined, planning the traversing sequence of the rest sub-areas by using a TSP method.
4. The off-line map-based robot full coverage path planning method according to claim 1, wherein the planning of the path inside each sub-area in the step (3) specifically adopts the following method:
(3.1) calculating a path line of the sub-area;
and (3.2) connecting the path lines in sequence to obtain the arch-shaped path of the sub-area.
5. The off-line map-based robot full coverage path planning method according to claim 4, wherein the step (3.1) specifically adopts the following method:
(3.1.1) obtaining the maximum value and the minimum value of all map point coordinates in the sub-area: x _ min, x _ max, y _ min, y _ max;
(3.1.2) calculating a first path line: fixing y to y _ init, gradually increasing the value of x by a step ds from x to x _ init, and sequentially using the obtained (x, y) combination as the coordinates of the path point until x is larger than or equal to x _ max; wherein, y _ init is y _ min + do, and x _ init is x _ min + do;
(3.1.3) calculate the remaining path lines: gradually increasing the value of y by the step length dp until y is larger than y _ max, taking the obtained value as the y coordinate of the path point on each path line, and calculating the x coordinate by using the same method as the method (3.1.2);
then, before step (3.1.2), a minimum distance do between the route and the obstacle, a minimum distance ds between route points, and a route line pitch dp are set.
6. The off-line map-based robot full coverage path planning method according to claim 4, wherein the step (3.2) adopts the following method:
(3.2.1) sequentially calculating paths between the current position of the robot and four vertexes of the sub-region by using an A-x algorithm, and selecting the vertex with the shortest path length as a starting point for traversing the sub-region; wherein, the vertex is the first point and the last point on the first route of the area, and the first point and the last point on the last route are numbered 0, 1, 2 and 3 respectively;
(3.2.2) if the number of the starting point is less than 2, sequentially connecting the paths from the first path line to the lower part; otherwise, the paths are sequentially connected from the last path line to the top;
(3.2.3) if the number of the start point is 0 or 2, connecting the path points as the zigzag path; if the starting point number is 1 or 3, the path points are connected as S-shaped paths.
7. The off-line map-based robot full coverage path planning method according to claim 6, wherein the step (3.2.3) is specifically: if the number of the starting point is 0 or 2, sequentially connecting the path points according to the sequence from left to right when the starting points are connected for the first time, connecting the last path point with the rightmost point on the next path line, and sequentially connecting the points on the next path line according to the sequence from right to left; by analogy, a bow-shaped path is obtained;
if the starting point number is 1 or 3, sequentially connecting the path points according to the sequence from right to left when the starting points are connected for the first time, connecting the last path point with the leftmost point on the next path line, and sequentially connecting the points on the next path line according to the sequence from left to right; and by analogy, an S-shaped path is obtained.
8. The off-line map-based robot full coverage path planning method according to claim 4, further comprising preprocessing the map area before the step (1), and further comprising preprocessing the sub-area before the step (3.1), wherein the preprocessing method comprises:
(A) calculating a main direction of the region;
(B) the map of the area is rotated so that the main direction coincides with the direction of the x-axis of the map.
9. The method for planning the full coverage path of the robot based on the off-line map as claimed in claim 1, wherein the specific method for calculating the main direction of the area in the step (a) is as follows:
(A1) detecting a boundary line segment of a map;
(A2) extracting all straight line segments in the boundary line segment, wherein the length of each straight line segment is not less than a preset threshold value;
(A3) and calculating the direction of each straight line segment, grouping the directions of each straight line segment according to the angle range, and taking the average value of the angle ranges of the groups with the highest frequency as the main direction of the area.
10. The off-line map-based robot full coverage path planning method according to claim 1, wherein the step (4) is specifically: and (4) taking the last path point of each sub-area in the step (3) as the current position of the robot to calculate the initial path point of the next sub-area, and connecting according to the traversal sequence between the sub-areas obtained in the step (2) to obtain the path of the whole map.
11. Robot full coverage path planning device based on off-line map, its characterized in that includes:
a map segmentation module: the method comprises the steps of dividing a map by a sliding method to obtain sub-areas;
a traversal order planning module: for planning a traversal order between the sub-regions;
an internal path planning module: for planning a path inside each sub-region;
a path integration module: the path for connecting all sub-areas obtains the path of the entire map.
12. The off-line map-based robot full coverage path planning device according to claim 11, further comprising a driving module for driving the sweeping robot to walk according to the path output by the path integrating module.
13. The off-line map-based robot full coverage path planning apparatus of claim 11, wherein the map segmentation module: the method is specifically used for:
finding a point with the minimum y coordinate in a feasible area of the map, constructing a straight line which passes through the point and is parallel to the x axis, and marking the straight line as a sliding line l; sliding downwards along the y-axis direction and calculating the number of connected domains in each row;
if only one connected domain in the current row is connected with one connected domain in the previous row, dividing the connected domain in the current row into sub-regions where the connected domain in the previous row is located; if only one connected domain in the current line is connected with one connected domain in the previous line, starting to divide a plurality of new sub-regions;
for a certain connected domain s _ c in the current row, if 0 or n connected domains are connected with the connected domain s _ c in the previous row, and n is greater than 1, ending the division of the sub-region where the n connected domains are located, and starting the division of 1 new region;
until l slides to the bottom of the map, the partitioning ends.
14. The off-line map-based robot full coverage path planning apparatus of claim 11, wherein the traversal order planning module comprises:
the initial position acquisition module is used for acquiring a sub-area where the initial position of the robot on the map is located as a first traversed sub-area;
and the TSP module is used for planning the traversing sequence of the rest sub-areas based on the TSP.
15. The off-line map-based robot full coverage path planning apparatus according to claim 11, further comprising:
the main direction calculation module is used for calculating the main direction of the map area or the sub-area;
the rotating module is used for rotating the map to enable the main direction to be consistent with the direction of the x axis of the map;
further, the internal path planning module includes:
route calculation module: a path line for calculating a sub-region;
route line connection module: and the path lines are sequentially connected to obtain the zigzag path of the sub-area.
16. An apparatus comprising a processor and a memory, the memory for storing a program, the processor for executing the program to perform the off-line map based robot full coverage path planning method of any one of claims 1-10.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910869194.1A CN110595478A (en) | 2019-09-16 | 2019-09-16 | Robot full-coverage path planning method, device and equipment based on off-line map |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910869194.1A CN110595478A (en) | 2019-09-16 | 2019-09-16 | Robot full-coverage path planning method, device and equipment based on off-line map |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN110595478A true CN110595478A (en) | 2019-12-20 |
Family
ID=68859603
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910869194.1A Pending CN110595478A (en) | 2019-09-16 | 2019-09-16 | Robot full-coverage path planning method, device and equipment based on off-line map |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110595478A (en) |
Cited By (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111202471A (en) * | 2020-01-08 | 2020-05-29 | 上海高仙自动化科技发展有限公司 | Full-coverage path generation method and generation device, intelligent robot and storage medium |
| CN111681250A (en) * | 2020-05-16 | 2020-09-18 | 珠海市一微半导体有限公司 | Segmentation method based on laser grid map |
| CN112035921A (en) * | 2020-08-25 | 2020-12-04 | 中船文化科技(北京)有限公司 | Shelter moving line planning method and device, electronic equipment and storage medium |
| CN112068557A (en) * | 2020-08-27 | 2020-12-11 | 珠海市一微半导体有限公司 | Mobile robot full-coverage path planning method, chip and robot |
| CN112286194A (en) * | 2020-10-29 | 2021-01-29 | 广东杜尼智能机器人工程技术研究中心有限公司 | Cost map area division method |
| CN112504273A (en) * | 2020-10-29 | 2021-03-16 | 广东杜尼智能机器人工程技术研究中心有限公司 | Seamless connection planning method for arcuate path |
| CN113252026A (en) * | 2021-06-03 | 2021-08-13 | 炬星科技（深圳）有限公司 | Cross-scene navigation method, equipment and storage medium |
| CN113469398A (en) * | 2020-03-31 | 2021-10-01 | 广东博智林机器人有限公司 | Path planning method and device, electronic equipment and storage medium |
| CN113741425A (en) * | 2021-08-04 | 2021-12-03 | 中山大学 | Full-coverage path planning method and navigation system |
| CN113759907A (en) * | 2021-08-30 | 2021-12-07 | 武汉理工大学 | A sub-region full coverage path planning method, device, equipment and storage medium |
| CN113985894A (en) * | 2021-11-29 | 2022-01-28 | 中国人民解放军火箭军工程大学 | Autonomous obstacle avoidance path planning method, device, equipment and storage medium |
| CN114489068A (en) * | 2022-01-24 | 2022-05-13 | 上海利淘豪斯机器人有限公司 | Routing method and device for routing inspection task path of inspection robot under complex path |
| CN115509215A (en) * | 2021-06-08 | 2022-12-23 | 广东博智林机器人有限公司 | A robot-based floor grinding path generation method and device |
| CN115599081A (en) * | 2021-07-09 | 2023-01-13 | 尚科宁家（中国）科技有限公司（Cn） | Method and device for planning path of robot, robot and storage medium |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2014003517A1 (en) * | 2012-06-29 | 2014-01-03 | 인텔렉추얼디스커버리 주식회사 | Mobile robot and method for covering and controlling entire online path of mobile robot |
| CN108120441A (en) * | 2016-11-28 | 2018-06-05 | 沈阳新松机器人自动化股份有限公司 | Complete coverage path planning method and system |
| CN108663063A (en) * | 2018-05-09 | 2018-10-16 | 宁波拓邦智能控制有限公司 | Overlay path planing method, device, equipment, computer installation and storage medium |
| CN109947114A (en) * | 2019-04-12 | 2019-06-28 | 南京华捷艾米软件科技有限公司 | Robot complete coverage path planning method, device and equipment based on grating map |
-
2019
- 2019-09-16 CN CN201910869194.1A patent/CN110595478A/en active Pending
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2014003517A1 (en) * | 2012-06-29 | 2014-01-03 | 인텔렉추얼디스커버리 주식회사 | Mobile robot and method for covering and controlling entire online path of mobile robot |
| CN108120441A (en) * | 2016-11-28 | 2018-06-05 | 沈阳新松机器人自动化股份有限公司 | Complete coverage path planning method and system |
| CN108663063A (en) * | 2018-05-09 | 2018-10-16 | 宁波拓邦智能控制有限公司 | Overlay path planing method, device, equipment, computer installation and storage medium |
| CN109947114A (en) * | 2019-04-12 | 2019-06-28 | 南京华捷艾米软件科技有限公司 | Robot complete coverage path planning method, device and equipment based on grating map |
Non-Patent Citations (4)
| Title |
|---|
| 唐烨: "室内移动机器人搜索人的算法设计", 《轻工机械》 * |
| 徐博等: "智能机械全覆盖路径规划算法综述", 《计算机测量与控制》 * |
| 王俭等: "基于子区域的机器人全覆盖路径规划的环境建模", 《苏州科技学院学报》 * |
| 陈逸怀等: "基于单元分解法的移动机器人遍历路径规划", 《装备制造技术》 * |
Cited By (20)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111202471A (en) * | 2020-01-08 | 2020-05-29 | 上海高仙自动化科技发展有限公司 | Full-coverage path generation method and generation device, intelligent robot and storage medium |
| CN113469398A (en) * | 2020-03-31 | 2021-10-01 | 广东博智林机器人有限公司 | Path planning method and device, electronic equipment and storage medium |
| CN111681250A (en) * | 2020-05-16 | 2020-09-18 | 珠海市一微半导体有限公司 | Segmentation method based on laser grid map |
| CN111681250B (en) * | 2020-05-16 | 2023-04-07 | 珠海一微半导体股份有限公司 | Segmentation method based on laser grid map |
| CN112035921A (en) * | 2020-08-25 | 2020-12-04 | 中船文化科技(北京)有限公司 | Shelter moving line planning method and device, electronic equipment and storage medium |
| CN112035921B (en) * | 2020-08-25 | 2021-06-29 | 中船文化科技(北京)有限公司 | Shelter moving line planning method and device, electronic equipment and storage medium |
| CN112068557A (en) * | 2020-08-27 | 2020-12-11 | 珠海市一微半导体有限公司 | Mobile robot full-coverage path planning method, chip and robot |
| CN112504273B (en) * | 2020-10-29 | 2022-05-24 | 广东杜尼智能机器人工程技术研究中心有限公司 | Seamless connection planning method for arcuate path |
| CN112286194B (en) * | 2020-10-29 | 2022-05-17 | 广东杜尼智能机器人工程技术研究中心有限公司 | Cost map area division method |
| CN112504273A (en) * | 2020-10-29 | 2021-03-16 | 广东杜尼智能机器人工程技术研究中心有限公司 | Seamless connection planning method for arcuate path |
| CN112286194A (en) * | 2020-10-29 | 2021-01-29 | 广东杜尼智能机器人工程技术研究中心有限公司 | Cost map area division method |
| CN113252026A (en) * | 2021-06-03 | 2021-08-13 | 炬星科技（深圳）有限公司 | Cross-scene navigation method, equipment and storage medium |
| CN113252026B (en) * | 2021-06-03 | 2021-10-08 | 炬星科技（深圳）有限公司 | Cross-scene navigation method, equipment and storage medium |
| CN115509215A (en) * | 2021-06-08 | 2022-12-23 | 广东博智林机器人有限公司 | A robot-based floor grinding path generation method and device |
| CN115599081A (en) * | 2021-07-09 | 2023-01-13 | 尚科宁家（中国）科技有限公司（Cn） | Method and device for planning path of robot, robot and storage medium |
| CN113741425A (en) * | 2021-08-04 | 2021-12-03 | 中山大学 | Full-coverage path planning method and navigation system |
| CN113741425B (en) * | 2021-08-04 | 2023-11-24 | 中山大学 | Full-coverage path planning method and navigation system |
| CN113759907A (en) * | 2021-08-30 | 2021-12-07 | 武汉理工大学 | A sub-region full coverage path planning method, device, equipment and storage medium |
| CN113985894A (en) * | 2021-11-29 | 2022-01-28 | 中国人民解放军火箭军工程大学 | Autonomous obstacle avoidance path planning method, device, equipment and storage medium |
| CN114489068A (en) * | 2022-01-24 | 2022-05-13 | 上海利淘豪斯机器人有限公司 | Routing method and device for routing inspection task path of inspection robot under complex path |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110595478A (en) | Robot full-coverage path planning method, device and equipment based on off-line map | |
| CN111857127B (en) | Clean partition planning method for robot walking along edge, chip and robot | |
| CN109947114B (en) | Robot full-coverage path planning method, device and equipment based on grid map | |
| CN111830970B (en) | Regional cleaning planning method for robot walking along edge, chip and robot | |
| CN108151751B (en) | Path planning method and device based on combination of high-precision map and traditional map | |
| CN105844629B (en) | A kind of large scene City Building facade point cloud automatic division method | |
| CN106054900B (en) | The interim barrier-avoiding method of robot based on depth camera | |
| CN102147260B (en) | Electronic map matching method and device | |
| CN110398964A (en) | A low energy loss robot full coverage path planning method and system | |
| CN108898672A (en) | A kind of semi-automatic cloud method making three-dimensional high-definition mileage chart lane line | |
| CN107679498A (en) | A kind of airborne laser point cloud downtown roads recognition methods | |
| CN107807649A (en) | A kind of sweeping robot and its cleaning method, device | |
| CN107505939A (en) | A full-coverage path planning method for mobile robots | |
| CN108804539B (en) | Track anomaly detection method under time and space double view angles | |
| CN103969683B (en) | Method for picking position faces in batched mode based on constraint in three-dimensional seismic interpretation | |
| CN111202471A (en) | Full-coverage path generation method and generation device, intelligent robot and storage medium | |
| CN113674351B (en) | Drawing construction method of robot and robot | |
| CN112180947B (en) | Method and equipment for selecting initial travelling direction of mobile robot | |
| CN112882459A (en) | Cleaning path planning method, cleaning path planning device and cleaning robot | |
| CN109410183A (en) | Plane extraction method, system and device based on point cloud data and storage medium | |
| CN105844224A (en) | Point cloud fast ordering method for on-vehicle LiDAR road points | |
| CN109459052A (en) | A kind of sweeper complete coverage path planning method | |
| CN117464694B (en) | Path planning method for automatic hollow glass cleaning device | |
| CN112656307B (en) | Cleaning method and cleaning robot | |
| CN115308770A (en) | Dynamic obstacle detection method based on fitting graph |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20191220 |