Path planning process for a mobile surface treatment unit

• US 6,240,342 B1
• Filed: 08/02/2000
• Issued: 05/29/2001
• Est. Priority Date: 02/03/1998
• Status: Expired due to Term

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Fiegert, Michael, Helbach, Jorg, Lawitzky, Gisbert
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Hernandez, Olga
• Application Number:
  US09/601,464
• Time in Patent Office: 300 Days
• Field of Search: 701/25, 701/1, 701/209, 701/23, 901/1, 180/169
• US Class Current: 701/25
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface

Abstract

In a path planning method is disclosed for surface processing machines such as, for example, cleaning machines in a supermarket first, potential sub-paths are produced that, proceeding from boundary lines of obstacles or the work area parallel to these boundary lines shifted by the width of the processing device are erected in the form of concentric circles. These potential sub-paths are then sub-divided by maneuvering marks according to an heuristics, for example on the basis of the maneuverability of the mobile unit, and are connected to one another by sub-paths. The respective sub-paths are subsequently evaluated with a cost function that considers the distances, the area already covered, and the maneuverability of the unit, and the most cost-beneficial path is combined to form a planned path for the mobile unit. Preferably, sub-paths between the maneuvering marks are interpreted as graph edges and the maneuvering marks are interpreted as nodes and are evaluated with known evaluation methods for generating optimum graphs. Areas of employment are cleaning robots for supermarkets, lawnmowers, or painting devices and the like.

Claims

1. A path planning method for a mobile unit for surface processing, comprising the steps of:

providing a contour line of the processing surface and at least a contour line of an obstacle to be traveled around within the processing surface in the form of a closed line train composed of straight line sections connected in kinks;

dependent on a width of a surface processing device attached to the mobile unit, first, potential paths with the processing width are planned essentially parallel to the contour lines that allow the mobile unit to guide the surface processing device along the processing strip which has arisen in this way between the first potential path and the contour line;

in a further planning step, planning second potential paths in a same way as the first potential paths with the first potential paths as contour lines;

dividing the potential paths into potential sub-path segments dependent on a length of kinks in the contour lines between which a respective maneuvering mark is marked;

correcting at least two respective maneuvering marks of immediately adjacent, potential paths by potential sub-path segments; and

planning the path from interconnected, potential sub-path segments in that these are weighted with a cost function into which at least one of the following cost criteria enters;

traversability criterion on the basis of kinematics of the mobile unit, area criterion on the basis of processing strips already traversed in relationship to the overall processing area, and length of the potential sub-path.

2. The method according to claim 1, whereby the processing surface is divided into a grid, and a node with respect to surface elements of the grid is undertaken as to whether these are intersected by a sub-path segment, which serves as surface criterion for said path.

3. The method according to claim 1 whereby a distance from another contour line is checked in the planning of potential paths as the planning criterion, and the potential path is planned only when this is greater then the processing width.

4. The method according to claim 3 whereby potential paths are planned until the planning criterion is no longer satisfied.

5. The method according to claim 1 whereby a sub-path has a travel direction for the mobile unit prescribed, and whereby adherence of the travel direction in conjunction with the kinematics of the mobile unit is evaluated in the evaluation by the cost function.

6. Method according to claim 1 wherein the potential paths are produced as follows with potential sub-path segments:

the length of the line segments of the contour line is retained and corresponds to a potential sub-path segment at whose end points maneuvering marks are marked;

a respective sub-path segment is shifted essentially perpendicular to the contour line by the amount of the processing width; and

those maneuvering marks of potential sub-path segments that are from a kink of the contour line before their displacement are connected to one another by a further, potential sub-segment.

7. The method according to claim 1 wherein a graph is produced, whereby the potential sub-path segments serve as edges of the graph and the maneuvering marks serve as nodes of the graph.

8. The method according to claim 7 wherein traversed edges are noted as having been cleaned and when no uncleaned edge departs from a node located between these edges, these are combined to form a meta-edge in order to be able to evaluate the entire graph given a constant search depth.

9. The method according to claim 8 wherein the evaluation is implemented with a known graph algorithm.

10. The method according to claim 9 wherein the depth search or the weighted depth search are known graph algorithms.

11. The method according to claim 1 wherein maneuvering marks in the form of a configuration as reference mark are employed at the mobile unit and the alignment thereof.

12. A path planning method for a mobile unit for surface processing, comprising the steps of:

providing a contour line of the processing surface and at least a contour line of an obstacle to be traveled around within the processing surface in the form of a closed line train composed of straight line sections connected in kinks;

dependent on a width of a surface processing device attached to the mobile unit, first, potential paths with the processing width are planned approximately parallel to the contour lines that allow the mobile unit to guide the surface processing device along the processing strip between the first potential path and the contour line;

in a further planning step, planning second potential paths in a substantially same way as the first potential paths with the first potential paths as contour lines;

dividing the potential paths into potential sub-path segments dependent on a length of kinks in the contour lines between which a respective maneuvering mark is marked;

correcting at least two respective maneuvering marks of immediately adjacent, potential paths by potential sub-path segments; and

planning the path from interconnected, potential sub-path segments in that these are weighted with a function into which at least one of the following criteria enters;

traversability criterion on the basis of kinematics of the mobile unit, area criterion on the basis of processing strips already traversed in relationship to the overall processing area, and length of the potential sub-path.