Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Automatic route guidance vehicle
Reexamination Certificate
2000-08-02
2001-05-29
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Automatic route guidance vehicle
C701S209000, C701S023000, C901S001000, C180S169000
Reexamination Certificate
active
06240342
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention is directed to a method with which a mobile unit can be controlled on a working surface locked by obstacles such that a work device attached to it covers the remaining surface as completely as possible.
Repetitive activities are being transferred more and more often to service robots. Examples of such activities are cleaning tasks, transport tasks, dispersing seed or, for example, lawn mowing. Given service robots to which surface processing devices are attached, there is the problem that this surface processing device should cover the entire space available as completely as possible, whereby optimally few paths should be traveled twice. The expense for the planning of this path should thereby also be so low that little computing capacity need be employed for this purpose, so that an accessible time behavior can be assured in the planning process. Given a cleaning robot that, for example, is intended to carry out cleaning jobs in a supermarket, the additional problem is comprised therein that, when it is utilized at the time the store is open, additional obstacles in the form of customers with grocer carts occur, and that the path traveled by the robot should be so predictable that the customers are not frightened by the cleaning robot. When the dimensions of the work and the obstacles present therein are known in terms of their position, an optimum path can be planned with the assistance of an advance traversal, traveling this path requiring little time and thereby taking as much of the surface to be covered into consideration as possible. Although path planning methods for autonomous mobile units are already known in the prior art, the topic of planning surface-covering paths has already been sporadically discussed therein: “Path Planning and Guidance Techniques For An Autonomous Mobile Cleaning Robot” by Christian Hofner and Gunther Schmidt, published in Proceedings of the Intelligent Robots and Systems IROS '94, Munich, Sep. 12-16, 1994, pages 610 through 617.
SUMMARY OF THE INVENTION
An object underlying the invention is comprised in specifying an improved path planning method for a mobile unit for surface processing.
According to the present invention, a path planning method is provided for a mobile unit for surface processing. The contour line of the processing surface and at least the contour line of an obstacle to be traveled around the processing surface is provided 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. The potential paths are divided into potential sub-path segments dependent on a length of kinks in the contour lines between which a respective maneuvering mark is marked. At least two respective maneuvering marks of immediately adjacent, potential paths are connected by potential sub-path segments. The path is planned 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: transversability 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.
Advantageously, the width of the work device is planned in a given application of the inventive method, so that a low number of potential paths are prescribed, these being advantageously subdivided into potential sub-path segments by maneuvering marks that are preferably arranged such that the mobile unit, on the basis of its kinematic givens, is unproblemmatically in the position to proceed from one maneuvering mark to the next maneuvering mark. In this way, an optimally low plurality of potential sub-path segments is prescribed, these having to be interpreted by an evaluation event and, accordingly, incurring an optimally low calculating expense.
In a development of the method, the work area is advantageously divided in the form of a grid, whereby the grid surface notes whether this is to be traversed by a sub-path segment that is to be planned, from which conclusions can be drawn as to whether this surface area has already been cleaned. This leads to the fact that the cost function for evaluating the respective sub-path segments can be adapted to this situation.
In a development of the proposed method, a check is preferably carried out before the planning of a potential path as to whether this adheres to a minimum spacing from further contour lines, since producing unnecessary, potential sub-paths is avoided in this way because such potential sub-paths are likewise already produced proceeding from other contour lines. In this way, the calculating expense is to be reduced in the planning and evaluation of the path that is to be traversed by the mobile unit.
In a development of the proposed method, one advantageously continues with generating potential paths until a spacing criterion with respect to a contour line has been downwardly crossed, since it is assured in this way that the entire, remaining work area is penetrated by potential paths and it is simultaneously assured that an excessive number of potential paths are not produced.
In a development of the proposed method, a direction is advantageously prescribed for the individual sub-paths, since it can be assured in this way that surface processing devices arranged laterally at a mobile unit can be conducted along the contour line.
In a development of the proposed method, a potential path at potential sub-path segments are advantageously generated in that the line segments of the contour line are simply perpendicularly shifted by the amount of the width of the surface processing device, and the end points of the sub-path segments that have arisen in this way are connected by further sub-path segments. This method is simple to program and produces its potential sub-paths and potential paths with maneuvering marks in a simple way that can be easily traversed by a mobile unit.
In a development of the proposed method, the sub-path can be advantageously represented in the form of edges of a graph and the maneuvering marks can be advantageously represented as nodes of a graph; graph-theoretical fundamentals can thus be utilized. A great variety of possibilities for constructing optimum graphs and for evaluating individual edges of these graphs are already present therein.
Advantageously, the path to be crossed by the mobile unit is implemented by a weighted depth search of the edges of the graph, since good path courses can be found in this way using little calculating expense and, thus, using small computers as well.
Advantageously, the maneuvering marks are presented in the form of configurations of the mobile unit as coordinates plus direction, whereby the same reference point at the mobile unit is always employed.
Exemplary embodiments of the invention are explained in further detail below with reference to the drawings figures.
REFERENCES:
patent: 4700427 (1987-10-01), Knepper
patent: 4706200 (1987-11-01), Kishi et al.
patent: 5602748 (1997-02-01), Seki et al.
patent: 6102147 (2000-08-01), Shimizu et al.
patent: 6167332 (2000-12-01), Kurtzberg et al.
patent: 0 335 975 (1989-10-01), None
patent: 0 402 764 (1990-12-01), None
patent: 0 564 854 (1993-10-01), None
Path Planning And Guidance Techniques For An Autonomous Mobile Cleaning Robot—Hofner et al No. 8393 Jul. 4, 2000.
Fiegert Michael
Helbach Jörg
Lawitzky Gisbert
Cuchlinski Jr. William A.
Hernandez Olga
Schiff & Hardin & Waite
Siemens Aktiengesellschaft
LandOfFree
Path planning process for a mobile surface treatment unit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Path planning process for a mobile surface treatment unit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path planning process for a mobile surface treatment unit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2490096