CN113759907A - A sub-region full coverage path planning method, device, equipment and storage medium - Google Patents
A sub-region full coverage path planning method, device, equipment and storage mediumDownload PDFInfo
- Publication number
- CN113759907A CN113759907ACN202111005922.8ACN202111005922ACN113759907ACN 113759907 ACN113759907 ACN 113759907ACN 202111005922 ACN202111005922 ACN 202111005922ACN 113759907 ACN113759907 ACN 113759907A
- Authority
- CN
- China
- Prior art keywords
- path
- sub
- area
- intelligent
- planning
- 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
Images
Classifications
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0231—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means
- G05D1/0238—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means using obstacle or wall sensors
- G05D1/024—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means using obstacle or wall sensors in combination with a laser
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
- G05D1/0214—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with safety or protection criteria, e.g. avoiding hazardous areas
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0276—Control of position or course in two dimensions specially adapted to land vehicles using signals provided by a source external to the vehicle
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Aviation & Aerospace Engineering (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- General Physics & Mathematics (AREA)
- Automation & Control Theory (AREA)
- Optics & Photonics (AREA)
- Electromagnetism (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
Abstract
Translated fromChinese
Description
Technical Field
The present invention relates to the field of path planning technologies, and in particular, to a method, an apparatus, a device, and a storage medium for planning a sub-area full coverage path.
Background
With the accelerated development of modern construction, supermarkets, large-scale docks, logistics warehouses, high-grade hotels, large leisure parks, campuses, hospitals and other places are continuously increased in number and scale, various large living districts and activity places are increasingly increased, human activities, logistics transportation and the like become more complicated, and a large amount of manpower and material resources are needed to ensure cleanness and sanitation, so that the intelligent cleaning robot is produced at the same time. The intelligent cleaning robot is a relatively huge system, is a cross of modern science and technology, and mainly comprises a cleaning system, a navigation obstacle avoidance system and a path planning system. The path planning algorithm determines the efficiency of the cleaning robot. How to quickly find a path with the characteristics of high coverage rate, low repetition rate and the like, the working efficiency of the cleaning robot is improved, and the method becomes a research hotspot of path planning.
At present, the mainstream full-coverage path planning algorithm is mainly a unit decomposition method. The unit decomposition method is to divide the whole space area after obtaining the map information to form a plurality of simply-shaped and non-obstacle and non-overlapping sub-areas, to plan each sub-area, to reasonably distribute the operation sequence of each sub-area, to calculate the optimal sub-area connection route, to complete the whole path planning. The planning effect of the unit decomposition method depends on the number of the sub-regions, and the number of the sub-regions directly influences the complexity of the connection algorithm, so that in the case of complex terrain, the unit decomposition method can generate more sub-regions, generate unnecessary reciprocating motion, and cause poor planning effect.
Disclosure of Invention
In view of the above, it is desirable to provide a method, an apparatus, a device and a storage medium for planning a partitioned full coverage path, so as to solve the problems of more partitioned sub-regions and poor planning effect caused by using a cell decomposition method in the prior art.
In order to achieve the technical purpose, the invention adopts the following technical scheme:
in a first aspect, the present invention provides a method for planning a sub-area full coverage path, which is applied to an intelligent tracking device, and includes:
constructing a grid cost map according to the environmental information and the positioning information of the intelligent tracing equipment;
converting the grid cost map into a common pixel map;
dividing the normal pixel map into a plurality of sub-regions;
and determining a first path of each sub-area in the respective area and a second path between the sub-areas, and determining the optimal path of the intelligent tracking device according to the first path and the second path.
Preferably, converting the grid cost map into a normal pixel map comprises:
and converting point to point into a common pixel map according to the occupation state of the internal space of the grid in the grid cost map.
Preferably, determining the first path of each sub-region within the respective region comprises:
determining the range of the sub-region as the range of the region with the specific shape according to a preset rule;
and acquiring a full-coverage minimum round-trip path of the intelligent tracing device in the range of the specific shape area, wherein the full-coverage minimum round-trip path is a first path.
Preferably, the specific shape is a polygon, and acquiring a full-coverage minimum round-trip path of the intelligent tracking device in the specific shape area range specifically includes:
selecting the longest edge of the polygon as a reference edge, and selecting the vertex farthest from the reference edge as a target point;
and the analog intelligent tracking device reciprocates along the direction parallel to the reference edge until the intelligent tracking device reaches the target point.
Preferably, the simulating the intelligent tracking device performs a back-and-forth movement along a direction parallel to the reference edge until the intelligent tracking device reaches the target point, and specifically includes:
setting intelligent tracing equipment to move from any vertex of the reference edge to a polygonal first abutting edge along a first direction according to a preset step pitch;
after moving a preset distance along the first abutting edge, setting the intelligent tracking equipment to move to a polygonal second abutting edge along a second direction according to a preset step pitch;
and repeating the process until the intelligent tracking device reaches the target point.
Preferably, determining a second path connecting the sub-regions comprises:
and determining two end points of the first path in all the sub-areas, moving the simulated intelligent tracking equipment from the starting position to one end point of the first path in any sub-area, and moving the simulated intelligent tracking equipment from the other end point to one end point of the first path in the next sub-area until all the sub-areas are connected, wherein the path connecting all the sub-areas is the second path.
Preferably, determining the optimal path of the intelligent tracking device comprises:
and determining the shortest second path, wherein the shortest second path and the first path are the optimal paths of the intelligent tracking equipment.
In a second aspect, the present invention further provides a path planning apparatus, including:
the construction module is used for constructing a grid cost map according to the environment information and the positioning information of the intelligent tracing equipment;
the conversion module is used for converting the grid cost map into a common pixel map;
a segmentation module for dividing the common pixel map into a plurality of sub-regions;
and the planning module is used for determining a first path of each sub-area in the respective area and a second path between the sub-areas, and determining the optimal path of the intelligent tracking equipment according to the first path and the second path.
In a third aspect, the present invention also provides an electronic device comprising a memory and a processor, wherein,
a memory for storing a program;
and the processor is coupled with the memory and used for executing the program stored in the memory so as to realize the steps in the partition area full coverage path planning method in any one of the implementation modes.
In a fourth aspect, the present invention further provides a computer-readable storage medium, configured to store a computer-readable program or instruction, where the program or instruction, when executed by a processor, can implement the steps in the partition area full coverage path planning method in any one of the above implementations.
The beneficial effects of adopting the above embodiment are: the method for planning the full-coverage path of the subareas converts the grid cost map into the pixel map, divides the subareas by selecting the pixel points on the pixel map, is simple and convenient to operate, improves the dividing precision, can accurately divide the subareas, freely controls the sizes of the subareas, can generate the subareas in any number and any positions, plans the path by a unit dividing method, reduces the data processing amount, can reduce unnecessary round trip even facing complex terrain, has less information stored in each subarea, and is convenient to calculate and process.
Drawings
Fig. 1 is a schematic flowchart of an embodiment of a method for planning a sub-area full coverage path according to the present invention;
FIG. 2 is a diagram illustrating the effect of dividing the normal pixel map into a plurality of sub-regions according to an embodiment of the present invention;
FIG. 3 is a flowchart illustrating an embodiment of determining a first path of each sub-region in a respective region according to the present invention;
FIG. 4 is a flowchart illustrating an embodiment of step S302 in FIG. 3 according to the present invention;
FIG. 5 is a flowchart illustrating an embodiment of step S402 in FIG. 4 according to the present invention;
FIG. 6 is a diagram illustrating an embodiment of a first path plan within a sub-area provided by the present invention;
FIG. 7 is a diagram illustrating the planning effect of an embodiment of the optimal path planning provided by the present invention;
fig. 8 is a schematic structural diagram of a path planning apparatus according to an embodiment of the present invention;
fig. 9 is a schematic diagram of a hardware architecture of a sweeping robot according to an embodiment of the present invention;
fig. 10 is a schematic structural diagram of an embodiment of an electronic device provided in the present invention.
Detailed Description
The accompanying drawings, which are incorporated in and constitute a part of this application, illustrate preferred embodiments of the invention and together with the description, serve to explain the principles of the invention and not to limit the scope of the invention.
In the description of the present application, "a plurality" means two or more unless specifically limited otherwise.
Reference herein to "an embodiment" means that a particular feature, structure, or characteristic described in connection with the embodiment can be included in at least one embodiment of the invention. The appearances of the phrase in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. It is explicitly and implicitly understood by one skilled in the art that the embodiments described herein can be combined with other embodiments.
The invention provides a method, a device, equipment and a storage medium for planning a sub-area full-coverage path, which are respectively explained below.
Referring to fig. 1, fig. 1 is a schematic flow chart of an embodiment of a method for planning a full coverage path of a partitioned area according to the present invention, the method including:
s101, constructing a grid cost map according to the environment information and the positioning information of the intelligent tracing equipment;
s102, converting the grid cost map into a common pixel map;
s103, dividing the common pixel map into a plurality of sub-regions;
s104, determining a first path of each sub-area in the respective area and a second path between the sub-areas, and determining the optimal path of the intelligent tracking device according to the first path and the second path.
In step S101, the intelligent tracking device may be an intelligent tracking robot, an intelligent tracking car, or the like. In one embodiment, the intelligent tracking device is a sweeping robot that approximates a spherical structure. A grid cost map refers to the partitioning of an environment into a series of grids, where each grid is given a possible value, representing the probability that the grid is occupied. In a specific embodiment, the environmental information of the sweeping robot is obtained through the laser radar, the positioning information of the sweeping robot is obtained through the odometer, and the position of the obstacle is marked when the grid cost map is constructed according to the environmental information and the positioning information of the sweeping robot. Specifically, the obstacle refers to an obstacle that is permanently added to the map when the map is created. The construction method of the grid cost map is the prior art, the specific construction process is not described again, and the construction method of the grid cost map is not limited in this embodiment.
Further, a grid cost map of the environment where the sweeping robot is located is constructed through a mapping method of a Robot Operating System (ROS), which is the prior art and is not described herein again.
In step S102, the present invention provides a specific embodiment, the grid cost map is reassembled by an OpenCV algorithm, where OpenCV is a cross-platform computer vision library issued based on BSD license (open source), and each grid in the grid cost map is converted point to point into a common pixel map according to the occupied condition of each grid in the grid cost map, so as to facilitate the division of subsequent sub-regions and path planning.
In step S103, please refer to fig. 2, fig. 2 is a dividing effect diagram of an embodiment of dividing a general pixel map into a plurality of sub-areas according to the present invention, not all areas of a field need to be cleaned, but only an area to be cleaned needs to be divided, so as to meet the cleaning requirement, and the cleaning area is clear, and the clear area is more convenient to clean.
In step S104, a first path inside each barrier-free sub-area is planned by a unit segmentation method, after the planning of the first path inside each barrier-free sub-area is completed, an end point of the path inside each barrier-free sub-area is connected with a start point of a path inside a subsequent barrier-free sub-area, a path connecting all sub-areas is a second path, and a shortest total path is calculated, which is an optimal path plan of the sweeping robot.
Compared with the prior art, the method for planning the full-coverage path by the sub-regions converts the grid cost map into the pixel map, divides the sub-regions by selecting the pixel points on the pixel map, is simple and convenient to operate, improves the dividing precision, can accurately divide the sub-regions, freely controls the sizes of the sub-regions, plans the path by the unit division method, reduces the data processing amount, can reduce unnecessary round trip even facing complex terrains, has less information stored in each sub-region, and is convenient to calculate and process.
In some embodiments of the invention, converting the grid cost map into a normal pixel map comprises:
and converting point to point into a common pixel map according to the occupation state of the internal space of the grid in the grid cost map.
In the above embodiment, the grid cost map is a costmap grid cost map, one grid in the costmap grid cost map represents a part of area of actual terrain, and the probability of existence of an obstacle is represented by using gray-scale values, wherein occupied space of the grid in the costmap grid cost map is represented by 1, and unoccupied space is represented by 0, and the costmap grid cost map is converted into a common pixel map by point points according to the occupied state of the grid in the costmap grid cost map. And performing graying processing on the ordinary pixel map to obtain an ordinary pixel grayscale map, wherein the area represented by the grid marked as 1 is converted into black, and the area represented by the grid marked as 0 is converted into white. The pixel map simply and directly shows the occupation state of the located grid, each grid only stores the position and the occupation information, and the cleaning area is more conveniently divided.
Specifically, in an embodiment provided by the present invention, based on a Robot Operating System (ROS), the costmap grid cost map is recombined into a common pixel map according to a possible value of each grid in the costmap grid cost map by an OpenCV algorithm, and graying is performed on the common pixel map, where graying of the pixel map belongs to the prior art and is not described herein.
Referring to fig. 3, fig. 3 is a schematic flow chart of an embodiment of determining a first path of each sub-region in a respective region according to the present invention, where in some embodiments of the present invention, determining the first path of each sub-region in the respective region includes:
s301, determining the range of the sub-region as a specific shape region range according to a preset rule;
s302, acquiring a full-coverage minimum round-trip path of the intelligent tracking device in a specific shape area range, wherein the full-coverage minimum round-trip path is a first path.
In step S301, the preset rule is that a user freely selects a pixel point by using a Robot Operating System (ROS) according to the actual situation of the site to be cleaned and through an initialization function of OpenCV, and an area to be cleaned is marked out. The regions directly composed of the pixels are various and not beneficial to the planning of the path, and in a specific embodiment provided by the invention, the cleaning region needs to be approximated into a polygonal region.
In step S302, a full-coverage cleaning of the polygonal area is required, that is, a full-coverage path plan of the sweeping robot in the polygonal area is determined, and in order to reduce unnecessary cleaning, a minimum full-coverage round-trip path of the sweeping robot, that is, a first path in the polygonal area, is required to be determined.
Referring to fig. 4, fig. 4 is a schematic flowchart of an embodiment of the step S302 in fig. 3 according to the present invention, in some embodiments of the present invention, the specific shape is a polygon, and the step S302 specifically includes:
s401, selecting the longest edge of a polygon as a reference edge, and selecting the vertex farthest from the reference edge as a target point;
s402, simulating the intelligent tracking device to move back and forth along the direction parallel to the reference edge until the intelligent tracking device reaches a target point.
In step S401, a coordinate system is established on the ordinary pixel map, and the vertex of the polygon area is determined clockwise, i.e. the range of the polygon area can be determined, because the sweeping robot has a certain volume, the radius of the sweeping robot needs to be expanded on the polygon boundary to form a new polygon area, and a line segment function of the new polygon area boundary is calculated through a Robot Operating System (ROS), so that the longest side of the polygon area is determined, and the longest side is set as a reference side, and can be intersected with other boundaries inevitably when moving parallel to the longest side, thereby facilitating the simulation of the intersection point with the side in the polygon area boundary. And calculating the vertex farthest from the reference edge, wherein the point is the end point of the path in the polygonal area, and the number of times of the sweeping robot to make a round trip in the polygonal area can be determined according to the point and the size of the sweeping robot.
In step S402, the starting point of the sweeping robot may be a boundary connecting the left end point of the reference edge or a boundary connecting the right end point of the reference edge, which is not further limited in the embodiment provided by the present invention, and the sweeping robot moves parallel to the reference edge until reaching the target point, so that the shortest path planning of the full coverage in the polygonal area can be implemented.
In an embodiment of the present invention, the polygon area is mainly a quadrilateral area, because the quadrilateral can complete coverage of most terrains, and the planning calculation amount is small.
Referring to fig. 5, fig. 5 is a schematic flowchart of an embodiment of the step S402 in fig. 4 according to the present invention, where in some embodiments of the present invention, the step S402 specifically includes:
s501, setting intelligent tracking equipment to move from any vertex of a reference edge to a polygonal first abutting edge along a first direction according to a preset step pitch;
s502, after moving a preset distance along the first abutting edge, setting the intelligent tracing device to move to a polygonal second abutting edge along a second direction according to a preset step pitch;
and S503, repeating the process until the intelligent tracking device reaches the target point.
In step S501, the sweeping robot of an embodiment of the present invention is a sphere structure, and the radius of the sweeping robot is used as a preset step pitch, please refer to fig. 6, where fig. 6 is a schematic diagram of an embodiment of a first path plan in a sub-area provided by the present invention, a distance from the sweeping robot to a reference edge by one step pitch may be a left vertex or a right vertex starting from any vertex of the reference edge, the left vertex or the right vertex is selected as the starting point of the embodiment of the present invention, the first direction is a direction moving from the left vertex to an abutting edge a, the sweeping robot moves in parallel to the reference edge along the first direction, the distance of one step pitch is moved each time until the first abutting edge a is reached, the first abutting edge a is a boundary of the sub-area connecting the right endpoint of the reference edge, one step pitch may determine a navigation point, and the sweeping robot moves along the navigation point, so that the parallel motion can be accurately carried out according to the planned path.
In step S502, referring to fig. 6, to implement the planning of the full coverage path in the area, when the sweeping robot reaches the first abutting edge a, the sweeping robot needs to translate a preset distance equidistantly along the first abutting edge a, in this embodiment, the preset distance is set to be a distance of one step pitch, so as to avoid repeatedly cleaning a certain area when the sweeping robot moves back and forth, in the embodiment, the second direction is a direction moving from the abutting edge a to the abutting edge c, and then the sweeping robot still translates equidistantly to the second abutting edge c in a direction parallel to the second direction along the reference edge by using the preset step pitch as a unit until the sweeping robot reaches the second abutting edge c. Specifically, the first direction and the second direction are two completely opposite directions.
In step S503, each time the sweeping robot reaches a butting edge, the sweeping robot translates along the butting edge at equal intervals by a step distance, then moves parallel to the reference edge to the opposite butting edge, and repeats the process until the sweeping robot finally reaches a target point in the area, that is, the sweeping robot realizes the full coverage path planning in the area parallel to the reference edge.
In some embodiments of the invention, determining the second path between the sub-regions comprises:
and determining two end points of the first path in all the sub-areas, moving the simulated intelligent tracking equipment from the starting position to one end point of the first path in any sub-area, and moving the simulated intelligent tracking equipment from the other end point to one end point of the first path in the next sub-area until all the sub-areas are connected, wherein the path connecting all the sub-areas is the second path.
In the above embodiment, the Robot Operating System (ROS) determines two end points of the first path of each sub-region in each sub-region according to the first path in each sub-region, where an initial position of the sweeping robot is a start position, the sweeping robot starts from the start position, moves to one end point of the first path of any sub-region, then moves to another end point of the first path according to the planned first path, and then moves to one end point of the first path of the next sub-region, and the movement is repeated until all sub-regions are connected, so as to obtain multiple second path plans connecting the sub-regions. The order of the end points connecting the first paths in the respective sub-regions is not further limited, but all sub-regions must be covered, and each sub-region can only be included once except in the case where the sub-regions need to be repeatedly divided.
In some embodiments of the invention, determining the optimal path for the intelligent tracking device comprises:
and determining the shortest second path, wherein the shortest second path and the first path are the optimal paths of the intelligent tracking equipment.
Specifically, the optimal path is actually a path in which the first path and the second path are connected to form a shortest curve, and after the optimal path is determined, the intelligent tracking device (such as a sweeping robot) can sweep the to-be-swept area in a full coverage manner within a shortest time without touching an obstacle.
Referring to fig. 7, fig. 7 is a planning effect diagram of an embodiment of optimal path planning provided by the present invention, a Robot Operating System (ROS) simulates and plans a second path, has multiple planning schemes for the second path, calculates all lengths of the second path, and finds a shortest path planning scheme, which is the optimal second path planning scheme, where the optimal second path and the first paths in all sub-regions together form the optimal path planning scheme for the sweeping robot.
In order to better implement the method for planning a full coverage path of a sub-area in the embodiment of the present invention, on the basis of the method for planning a full coverage path of a sub-area, please refer to fig. 8, where fig. 8 is a schematic structural diagram of an embodiment of a path planning apparatus provided in the present invention, an embodiment of the present invention provides apath planning apparatus 800, including:
theconstruction module 801 is used for constructing a grid cost map according to the environment information and the positioning information of the intelligent tracing equipment;
aconversion module 802, configured to convert the grid cost map into a common pixel map;
asegmentation module 803, configured to divide the normal pixel map into a plurality of sub-regions;
theplanning module 804 is configured to determine a first path of each sub-area in the respective area and a second path between the sub-areas, and determine an optimal path of the intelligent tracking device according to the first path and the second path.
Here, it should be noted that: thepath planning apparatus 800 provided in the foregoing embodiment may implement the technical solutions described in the foregoing method embodiments, and the specific implementation principles of the modules or units may refer to the corresponding contents in the foregoing method embodiments, which are not described herein again.
Specifically, referring to fig. 9, fig. 9 is a schematic diagram of hardware connection of a sweeping robot according to an embodiment of the present invention, and the sweeping robot according to the embodiment of the present invention is a sweeping robot, and the sweeping robot includes acentral information processor 901, a bottomlayer motion controller 902, a bottomlayer motion driver 903, alaser radar 904, and aodometer 905.
Further, the robot for sweeping provided in the embodiment of the present invention obtains surrounding environment information through thelaser radar 904, records positioning information through theodometer 905, sends the environment information and the positioning information to thecentral information processor 901, constructs a grid cost map through a Robot Operating System (ROS), converts the grid cost map into a common pixel map through thecentral information processor 901, divides a plurality of initialized sub-areas by selecting pixel points through a user, determines a first path of each sub-area and a second path between each sub-area according to a unit division method through thecentral information processor 901 after the division is completed, determines an optimal path of the robot for sweeping according to the first path and the second path, screens out point locations in the path as target points, converts the point locations into a starting grid location map, and converts the optimal path into a data structure format which can be issued by the ROS system, corresponding topics are issued in the ROS system, then a motion control command is sent to the bottomlayer motion controller 902, then the bottomlayer motion controller 902 sends a PWM speed signal to the bottomlayer motion driver 903, and the sweeping robot moves to a target point and cleans according to a planned path.
It should be noted that thecentral information processor 901 may be a computer, a microcomputer, or the like, and only needs to be a MCU capable of installing a Linux system and having a certain calculation power, and in this embodiment, thecentral information processor 901 is a microcomputer, and has a Robot Operating System (ROS) inside, which can perform information fusion. The bottomlayer motion controller 902 can be a 51-chip microcomputer or a 32-chip microcomputer, and only needs to meet the control requirement, and the selection of the bottomlayer motion controller 902 is not further limited by the invention. The bottomlayer motion driver 903 comprises a storage battery, a motor and the like, wherein the used storage battery only needs to drive the motor to normally operate, the specific model of the storage battery is not further limited, the used motor only needs to meet the power requirement of the sweeping robot, and the specific model of the motor is not further limited. Thelaser radar 904 is a radar system that detects a characteristic amount, such as a position, a speed, and the like, of a target by emitting a laser beam, and obtains information about the target, such as environmental information around the target, by emitting a detection signal to the target, comparing a received signal reflected from the target with the emission signal, and appropriately processing the signal. Thelidar 904 has various models, for example, sixteen-line mechanical lidar and four-line solid-state lidar, and the embodiment only requires thelidar 904 to be capable of detecting the environment around the sweeping robot in 360 degrees in an all-around manner, and the specific model is not further limited. Theodometer 905 is a device that is mounted on the sweeping robot and measures the travel and the speed, and the specific model of theodometer 905 is not further limited as long as theodometer 905 of the embodiment can record the positioning information of the sweeping robot.
Referring to fig. 10, fig. 10 is a schematic structural diagram of an electronic device according to an embodiment of the invention. Based on the method for planning the full-coverage path by the subareas, the invention also correspondingly provides a path planning device which can be a mobile terminal, a desktop computer, a notebook computer, a palm computer, a server and other computing devices. The path planning device includes aprocessor 1010, amemory 1020, and adisplay 1030. Fig. 10 shows only some of the components of the electronic device, but it is to be understood that not all of the shown components are required to be implemented, and that more or fewer components may be implemented instead.
Thememory 1020 may in some embodiments be an internal storage unit of the path planning device, such as a hard disk or a memory of the path planning device. Thememory 1020 may also be an external storage device of the path planning apparatus in other embodiments, such as a plug-in hard disk provided on the path planning apparatus, a Smart Media Card (SMC), a Secure Digital (SD) Card, a Flash memory Card (Flash Card), and so on. Further, thememory 1020 may also include both an internal storage unit of the path planning device and an external storage device. Thememory 1020 is used for storing application software installed in the path planning apparatus and various data, such as program codes for installing the path planning apparatus. Thememory 1020 may also be used to temporarily store data that has been output or is to be output. In an embodiment, thememory 1020 stores apath planning program 1040, and thepath planning program 1040 can be executed by theprocessor 1010, so as to implement the method for planning a full coverage path in a partitioned area according to the embodiments of the present application.
Thedisplay 1030 may be an LED display, a liquid crystal display, a touch-sensitive liquid crystal display, an OLED (Organic Light-Emitting Diode) touch panel, and the like in some embodiments. Thedisplay 1030 is used to display information at the path planning apparatus and to display a visual user interface. Thecomponents
In one embodiment, the steps in the partitioned area full coverage path planning method described above are implemented when theprocessor 1010 executes thepath planning program 1040 in thememory 1020.
Those skilled in the art will appreciate that all or part of the flow of the method implementing the above embodiments may be implemented by a computer program instructing associated hardware, and the program may be stored in a computer-readable storage medium. The computer readable storage medium is a magnetic disk, an optical disk, a read-only memory or a random access memory.
The above description is only for the preferred embodiment of the present invention, but the scope of the present invention is not limited thereto, and any changes or substitutions that can be easily conceived by those skilled in the art within the technical scope of the present invention are also included in the scope of the present invention.
Claims (10)
1. A method for planning a sub-area full-coverage path is applied to intelligent tracing equipment and is characterized by comprising the following steps:
constructing a grid cost map according to the environmental information and the positioning information of the intelligent tracing equipment;
converting the grid cost map into a common pixel map;
dividing the normal pixel map into a plurality of sub-regions;
determining a first path of each sub-area in the respective area and a second path between the sub-areas, and determining an optimal path of the intelligent tracking device according to the first path and the second path.
2. The method of claim 1, wherein converting the grid cost map into a normal pixel map comprises:
and converting point to point into a common pixel map according to the occupation state of the internal space of the grid in the grid cost map.
3. The method for planning a full coverage path according to claim 1, wherein the determining the first path of each sub-area in the respective area comprises:
determining the sub-area range as a specific shape area range according to a preset rule;
acquiring a full-coverage minimum round-trip path of the intelligent tracing device in the range of the specific shape area, wherein the full-coverage minimum round-trip path is the first path.
4. The method according to claim 3, wherein the specific shape is a polygon, and the obtaining of the full-coverage minimum round-trip path of the intelligent tracking device in the specific shape region specifically comprises:
selecting the longest edge of the polygon as a reference edge, and selecting the vertex farthest from the reference edge as a final target point of the sub-region;
and simulating the intelligent tracing device to reciprocate along the direction parallel to the reference edge until the intelligent tracing device reaches the target point.
5. The method according to claim 4, wherein the simulating the intelligent tracking device to move back and forth in a direction parallel to the reference edge until the intelligent tracking device reaches the target point comprises:
setting the intelligent tracing equipment to move from any vertex of the reference edge to the first butting edge of the polygon along a first direction according to a preset step pitch;
after moving a preset distance along the first abutting edge, setting the intelligent tracing device to move to the polygonal second abutting edge along a second direction according to a preset step pitch;
and repeating the process until the intelligent tracking device reaches the target point.
6. The method for planning a sub-area full coverage path according to claim 5, wherein determining the second path between the sub-areas comprises:
and determining two end points of the first paths in all the sub-areas, moving the simulated intelligent tracking equipment from the starting position to one end point of the first path in any one sub-area, and moving the simulated intelligent tracking equipment from the other end point to one end point of the first path in the next sub-area until all the sub-areas are connected, wherein the path connecting each sub-area is the second path.
7. The method according to claim 6, wherein the determining the optimal path of the intelligent tracking device comprises:
and determining the shortest second path, wherein the shortest second path and the first path are the optimal paths of the intelligent tracking equipment.
8. A path planning apparatus, comprising:
the construction module is used for constructing a grid cost map according to the environment information and the positioning information of the intelligent tracing equipment;
the conversion module is used for converting the grid cost map into a common pixel map;
a segmentation module for dividing the common pixel map into a plurality of sub-regions;
and the planning module is used for determining a first path of each sub-area in the respective area and a second path between the sub-areas, and determining the optimal path of the intelligent tracking equipment according to the first path and the second path.
9. An electronic device comprising a memory and a processor, wherein,
the memory is used for storing programs;
the processor, coupled to the memory, is configured to execute the program stored in the memory to implement the steps in the method for planning a full coverage path with a partitioned area according to any one of claims 1 to 7.
10. A computer readable storage medium for storing a computer readable program or instructions, which when executed by a processor, can implement the steps of the method for planning a full coverage path with sub-areas according to any one of the preceding claims 1 to 7.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111005922.8ACN113759907A (en) | 2021-08-30 | 2021-08-30 | A sub-region full coverage path planning method, device, equipment and storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111005922.8ACN113759907A (en) | 2021-08-30 | 2021-08-30 | A sub-region full coverage path planning method, device, equipment and storage medium |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN113759907Atrue CN113759907A (en) | 2021-12-07 |
Family
ID=78791865
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202111005922.8APendingCN113759907A (en) | 2021-08-30 | 2021-08-30 | A sub-region full coverage path planning method, device, equipment and storage medium |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113759907A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115390552A (en)* | 2022-07-28 | 2022-11-25 | 云鲸智能(深圳)有限公司 | Path planning method, device, cleaning system and storage medium |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP2078996A2 (en)* | 2008-01-11 | 2009-07-15 | Samsung Electronics Co., Ltd. | Method and apparatus for planning path of mobile robot |
| CN104317972A (en)* | 2014-11-19 | 2015-01-28 | 国家电网公司 | Dynamic layer induction method and system |
| CN106527423A (en)* | 2015-09-15 | 2017-03-22 | 小米科技有限责任公司 | Cleaning robot and control method thereof |
| CN109541634A (en)* | 2018-12-28 | 2019-03-29 | 歌尔股份有限公司 | A kind of paths planning method, device and mobile device |
| CN110502006A (en)* | 2019-07-22 | 2019-11-26 | 中国矿业大学 | A full-coverage path planning method for mobile robots in abandoned mining areas |
| CN110595478A (en)* | 2019-09-16 | 2019-12-20 | 北京华捷艾米科技有限公司 | Robot full-coverage path planning method, device and equipment based on off-line map |
- 2021
- 2021-08-30CNCN202111005922.8Apatent/CN113759907A/enactivePending
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP2078996A2 (en)* | 2008-01-11 | 2009-07-15 | Samsung Electronics Co., Ltd. | Method and apparatus for planning path of mobile robot |
| CN104317972A (en)* | 2014-11-19 | 2015-01-28 | 国家电网公司 | Dynamic layer induction method and system |
| CN106527423A (en)* | 2015-09-15 | 2017-03-22 | 小米科技有限责任公司 | Cleaning robot and control method thereof |
| CN109541634A (en)* | 2018-12-28 | 2019-03-29 | 歌尔股份有限公司 | A kind of paths planning method, device and mobile device |
| CN110502006A (en)* | 2019-07-22 | 2019-11-26 | 中国矿业大学 | A full-coverage path planning method for mobile robots in abandoned mining areas |
| CN110595478A (en)* | 2019-09-16 | 2019-12-20 | 北京华捷艾米科技有限公司 | Robot full-coverage path planning method, device and equipment based on off-line map |
Non-Patent Citations (5)
| Title |
|---|
| 张旭: "一种兼顾全局与局部特性的机器人动态路径规划算法", 《测绘科学技术学报》* |
| 张旭: "一种兼顾全局与局部特性的机器人动态路径规划算法", 《测绘科学技术学报》, 22 October 2018 (2018-10-22), pages 315 - 320* |
| 王道累: "清洁机器人避障系统的路径规划算法研究", 《上海电力学院学报》, vol. 34, no. 3, pages 264 - 267* |
| 马全坤: "基于记忆模拟退火算法和A*算法的农业机器人遍历路径规划方法", 《华南农业大学学报》* |
| 马全坤: "基于记忆模拟退火算法和A*算法的农业机器人遍历路径规划方法", 《华南农业大学学报》, 11 June 2020 (2020-06-11), pages 128 - 129* |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115390552A (en)* | 2022-07-28 | 2022-11-25 | 云鲸智能(深圳)有限公司 | Path planning method, device, cleaning system and storage medium |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US12393196B2 (en) | Systems and methods for training a robot to autonomously travel a route | |
| CN110023867B (en) | System and method for robotic mapping | |
| CN116645649B (en) | Vehicle pose and size estimation method, device and storage medium | |
| CN113985894A (en) | Autonomous obstacle avoidance path planning method, device, equipment and storage medium | |
| CN109557919B (en) | Variable-width grid map construction method fusing artificial road sign information | |
| CN114431771B (en) | Sweeping method of sweeping robot and related device | |
| CN114815809A (en) | Obstacle avoidance method and system for mobile robot, terminal device and storage medium | |
| JP5212939B2 (en) | Autonomous mobile device | |
| CN112497218B (en) | Robot pose determination method, device, equipment and medium | |
| CN113759907A (en) | A sub-region full coverage path planning method, device, equipment and storage medium | |
| CN116048069A (en) | An outdoor full-coverage path planning method and robot based on GPS positioning | |
| Abeideh et al. | Autonomous Driving Robot for Indoor 2D Mapping | |
| CN115346041A (en) | Point marking method, device, equipment and storage medium based on deep learning | |
| CN112515565B (en) | Cleaning partition adjacent judgment method and cleaning robot | |
| CN203241822U (en) | A mobile robot based on a preset moving path | |
| CN101430797A (en) | Rubber band algorithm for three-dimensional virtual scene fast path planning | |
| Horváth et al. | Probabilistic occupancy grid map building for Neobotix MP500 robot | |
| CN115164903A (en) | Hierarchical map-free navigation method and device based on local path point generation | |
| CN115237125A (en) | Intelligent line planning method for unmanned distribution disinfection trolley | |
| CN113671958A (en) | Method and system for determining obstacle avoidance path of robot, electronic device and medium | |
| TW202123031A (en) | Apparatus, method and article to facilitate motion planning in an environment having dynamic objects | |
| CN117193283A (en) | Assessment method and device for path planning performance of mobile robot | |
| CN114019977A (en) | Path control method and device for mobile robot, storage medium and electronic device | |
| CN116540685A (en) | Boundary configuration method, chip and robot based on obstacle pixels | |
| Herbst et al. | Active object segmentation for mobile robots |
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 | Application publication date:20211207 | |
| RJ01 | Rejection of invention patent application after publication |