Programming of an extended path for an autonomous mobile unit for the subsequent traversing of path sections that are temporarily blocked

When a sub-section of a predefined path temporarily cannot be traversed by an autonomous mobile unit, an extended path is found for subsequently traversing the temporarily blocked sub-section. A first path point of the predefined path is determined using at least one predefinable distance criterion, which takes into consideration the distance of the temporarily blocked sub-section from the first path point. An extension sub-section is determined which begins at the first path point, terminates at a second path point of the predefined path and encompasses at least the temporarily blocked sub-section. The extended path is programmed with the extension sub-section being integrated into the predefined path at the first path point.

CROSS REFERENCE TO RELATED APPLICATIONS

This application is based on and hereby claims priority to German Application No. 10138259.6 filed on Aug. 3, 2001, the contents of which are hereby incorporated by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to a method and system for programming an extended path for an autonomous mobile unit and to a computer program product and a computer-readable storage medium with a computer program stored thereon for programming an extended path for an autonomous mobile unit.

2. Description of Related Art

Repetitive activities are increasingly being reassigned to service robots. Examples of such activities include cleaning, transporting, distributing seed over relevant areas, and lawn mowing.

The problem with the service robots, to which associated surface-processing devices are attached, is that the surface-processing device is expected to cover as much of the available space as possible with as few paths as possible being traversed more than once. Moreover, the effort needed to program this path must be sufficiently low to require little computing capacity. This is the only way to ensure acceptable time characteristics during the programming process.

There is the added problem in the case of a cleaning robot whose function is to perform cleaning tasks in a supermarket, for instance, that additional obstacles in the form of customers with trolleys appear when the robot is being used while the supermarket is open for business. If the dimensions of the work area and the position of the obstacles located therein are known, it is possible with the aid of a pre-programming method to program an optimum path the traversing of which takes minimum time while simultaneously taking into consideration as much of the surface to be traversed as possible. The service robot starts traversing the path when the pre-programmed path has been pre-programmed and determined.

A pre-programming method of this type is known, for example, from DE 198 04 195 A1. However, any obstacles that may briefly appear, for example customers with their trolleys, consequently cannot be taken into consideration when the path is being pre-programmed. In this case the service robot detects the obstacles while moving. The robot takes evasive action, which is to say it departs from the pre-programmed path, bypasses the obstacle, and returns after the evasive action to its original path. A type of programming and execution of such evasive action is also known from DE 198 04 195 A1. However, the section of the original path that was not traversed owing to the evasive action remains unprocessed or uncleaned at this time and will have to be processed or cleaned subsequently.

Two different post-programming methods are known for subsequently processing unprocessed path sections of this type. In the case of the first post-programming method, the previously executed pre-programming method is executed a second time. The already traversed and accordingly processed sub-section of the original path is no longer taken into consideration here, while the unprocessed, omitted sub-section is taken into consideration during subsequent programming.

The disadvantage of this method, however, is that a completely new path is determined for the remaining section of the original path still to be processed on account of taking the omitted sub-section into consideration. Yet this complete re-programming results in unnecessarily long programming times and places a high demand on computing power. A provision in this case of the second known post-programming method is for the unprocessed path section to be appended at the end of the original path and to be traversed on completion of the path. However, this method results in unnecessarily extended paths and so is also inefficient.

Other path programming methods are known from “Approximation Algorithms for Lawn Mowing and Milling”, Arkin E. M. et al., Angewandte Mathematik und Informatik (Applied Mathematics and Computer Science), University of Cologne, Report No. 97.255, 1997.

SUMMARY OF THE INVENTION

An object of the invention is accordingly to disclose a path programming method for an autonomous mobile unit facilitating efficient and flexible programming of a path extended to include an alternative path.

This object may be achieved by a method for programming an extended path for an autonomous mobile unit to determine a sub-section of a predefined path which cannot be traversed by the autonomous mobile unit. A non-traversable sub-section of this kind may occur if an obstacle blocks the predefined path. Such blocking is generally only temporary so that the sub-section is at times non-traversable.

The method further entails determining a first path point of the predefined path using at least one predefinable distance criterion which takes into consideration a distance from the sub-section to the first path point. An extension sub-section is thereupon determined which begins at the first path point, terminates at a second path point of the predefined path, and encompasses at least the sub-section. When the extended path is programmed, the extension sub-section is integrated into the predefined path at the first path point.

The system for programming an extended path for an autonomous mobile unit has a path programming unit, for example a computer processor, which is set up to perform the following steps. A section of a pre-determined path can be determined which is a sub-section of the path and which cannot be traversed by the autonomous mobile unit. A first path point of the predefined path can furthermore afterwards be determined using at least one predefinable distance criterion which takes into consideration a distance from the sub-section to the first path point. An extension sub-section can thereupon be determined which begins at the first path point, terminates at a second path point of the predefined path, and encompasses at least the sub-section. When the extended path is programmed, the extension sub-section can be integrated into the predefined path at the first path point.

The computer program product, which includes a computer-readable storage medium on which a program is stored, allows a computer, after the program has been loaded into a memory of the computer, to execute the following steps for programming an extended path for an autonomous mobile unit. A section of a pre-determined path can be determined which is a sub-section of the path and which cannot be traversed by the autonomous mobile unit. A first path point of the predefined path can furthermore afterwards be determined using at least one predefinable distance criterion which takes into consideration a distance from the sub-section to the first path point.

An extension sub-section can thereupon be determined which begins at the first path point, terminates at a second path point of the predefined path, and encompasses at least the sub-section. When the extended path is programmed, the extension sub-section can be integrated into the predefined path at the first path point.

On the computer-readable storage medium a program is stored which allows the computer, after the program has been loaded into a storage medium of the computer, to execute the following steps for programming an extended path for an autonomous mobile unit. A section of a pre-determined path can be determined which is a sub-section of the path and which cannot be traversed by the autonomous mobile unit. A first path point of the predefined path can furthermore afterwards be determined using at least one predefinable distance criterion which takes into consideration a distance from the sub-section to the first path point.

An extension sub-section can thereupon be determined which begins at the first path point, terminates at a second path point of the predefined path, and encompasses at least the sub-section. When the extended path is programmed, the extension sub-section can be integrated into the predefined path at the first path point.

The system, the computer program product, and the computer-readable storage medium are particularly suitable for carrying out the method according to the invention or one of its developments explained in the following.

A particular advantage of the invention is that when the extended path is being programmed the predefined, original path is used as a basis for programming additional subsections of the extension path which only extend or supplement the predefined path. This obviates the need for re-programming which would result in a routing that may be substantially different from the original path. This saves computing power and memory space. The programming process is also accelerated.

The invention has the further advantage that no additional information is needed when the extended path is programmed, such as information requiring to be newly integrated about the surroundings. Only information already contained in the predefined path is used when the extended path is programmed. This is very advantageous especially when the predefined path contains manually integrated knowledge which cannot be generated automatically, or can be generated only with great difficulty.

The developments described in the following relate both to the method and to the system. The invention and developments described in the following can be implemented both as software and as hardware, for example using special electric circuitry. The invention or a development described in the following can furthermore be implemented by a computer-readable storage medium on which is stored a computer program which executes the invention or development.

The invention or any of the developments described in the following can also be implemented by a computer program product having a storage medium on which is stored a computer program which executes the invention or development.

Other criteria can be used besides the distance criterion when the first path point is being determined, for example a cinematic criterion taking into consideration a cinematic characteristic of the autonomous mobile unit.

A further criterion or further criteria can be a time criterion and/or a processing criterion taking into consideration a travel time and/or travel route of the autonomous mobile unit.

The first path point can furthermore also be determined by applying standard methods of graph theory according to Dijkstra which are known from “Introduction to Algorithms”, Thomas H. Cormen et al., The MIT Press, Cambridge, Mass., 23rd edition, London, 1999, McGraw-Hill Book Company, New York.

The extension sub-section includes, in one embodiment, at least one further sub-section of the predefined path in addition to the sub-section which cannot be traversed by the autonomous mobile unit. It is also possible for the extension sub-section largely to comprise sub-sections of the predefined path.

In one development, the second path point is identical to the first path point. This, in plain terms, means the autonomous mobile unit departs from the originally programmed path at one path point, traverses the sub-section which could not be traversed at an earlier time, then returns at the same path point to the originally programmed path.

In certain circumstances, for example when the path routing is complex, it may be favorable in terms of achieving as short and effective path routing as possible, for the second path point to be situated on the predefined path after the first path point. This makes it possible to avoid repeated traversing of the same path section.

The method for programming an extended path for an autonomous mobile unit is preferably employed in a recursive path programming method in such a way that the extended path, which was determined in a preceding iteration step, is the predefined path of an iteration step following the preceding iteration step. This makes it possible to promptly take into consideration any suddenly appearing new obstacles by an extension program without the need to determine a completely new path whenever new obstacles appear. The method or a development thereof is employed in one embodiment in a cleaning robot which, in this case, traverses the extended path in the course of a cleaning activity and cleans at least sections of the extended path.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

FIG. 2shows a cleaning robot201with a cleaning device210and a plurality of laser scanners202. The laser scanners202record images of the surroundings of the cleaning robot201and route the images to a computing unit203via connections204,205. The image signals are routed to the memory208via an input/output interface206connected via a bus207to a memory208and a processor209.

The method described in the following is executed in the processor209. The processor209is therefore set up such that the method-related steps described in the following are executable.

FIG. 1is a symbolic depiction of the map101produced by the cleaning robot201representing a space to be cleaned by the cleaning robot201. In plain terms, a map101of this type is an electronic image of the space to be cleaned.

The map101is produced by the cleaning robot201in such a way that the robot moves through the space and, by the laser scanners202, records images of its surroundings at different instances and at different locations in the space to be cleaned. The recorded images of the space are stored by the cleaning robot201and brought together into the map101which is also stored. Walls103within the space as well as obstacles104in the form of shelving or cabinets protruding into the space are therefore imaged in the map101.

With the aid of the map101, as part of a pre-programming action using a pre-programming method the cleaning robot201determines an optimal, pre-programmed cleaning path110the traversing of which will take a minimum length of time but take into consideration as much as possible of the area comprising the space to be traversed and cleaned. The pre-programmed cleaning path110is entered in the map101and stored.

FIG. 1shows the pre-programmed path110. The pre-programmed path110starts at point S (start)111and leads from there along an indicated path line112in the direction of the arrow113to point E (end)114. The pre-programming method executed by the cleaning robot201is described in DE 198 04 195 A1.

When pre-programming has been completed and the pre-programmed path110has been determined, as part of a cleaning process the service robot begins to traverse the path110. During the cleaning process the cleaning device210of the cleaning robot201is in active contact with the floor of the space to be cleaned.

The cleaning robot201moves along the pre-programmed and stored path110or indicated path line112and records images of its surroundings at periodic intervals. The robot201orientates itself in the space by comparing the recorded images with the stored map.

The cleaning robot201continues traversing the pre-programmed path110until it detects a new obstacle which was not taken into consideration during pre-programming and which is blocking a section of the pre-programmed path110. An obstacle of this type can be, for instance, a person situated within the space or another mobile item of furniture.

Blocking of the pre-programmed path110by the new obstacle prevents a sub-section of the original path110from being traversed and requires an alternative path or subsequent cleaning path to be programmed. A subsequent cleaning path of this type includes not only an altered path course in the narrower sense, which is to say not only a path for bypassing the new obstacle and not only an additional subsequent cleaning sub-section integrated at a subsequent point along the pre-programmed path, but the entire, newly programmed path course which also includes path sections remaining unaltered with respect to the pre-programmed path. A programming and execution of a path sub-section for bypassing or circumnavigating an obstacle is described in DE 198 04 195 A1.

The programming of a subsequent cleaning path of this type is described in the following.FIG. 3shows the stored map101with the pre-programmed path110and a new obstacle301, and a subsequent cleaning path programmed by the cleaning robot with the path sub-sections302,303,304,305,306, and307.

The following fundamental programming strategies are applied to the programming of a subsequent cleaning path:a) No subsequent cleaning path will be programmed if an object is blocking a section which is a sub-section of the pre-programmed path and which will be traversed again at a subsequent point along the pre-programmed path. The obstacle will be circumnavigated as closely as possible taking a predefined safety clearance into consideration.b) If an object is blocking a section which is a sub-section of the pre-programmed path and which will not be traversed again at a subsequent point along the pre-programmed path, a subsequent cleaning path will be programmed in the manner described below:b0) The subsequent cleaning path will include the path sub-section on which the cleaning robot will circumnavigate the new obstacle as closely as possible while maintaining a predefined safety clearance.b1) That particular path point in the pre-programmed path will be determined which is situated closest to the pre-programmed path sub-section which is blocked and which will be omitted when the new obstacle is circumnavigated, or to the obstacle. An additional path section will be integrated into the pre-programmed path at this nearest path point.b2) The sub-section being additionally integrated leads from the nearest path point to that particular path point in the pre-programmed path at which the cleaning robot will depart from the pre-programmed path when circumnavigating the new obstacle or will rejoin the path after circumnavigating the new obstacle (approach sub-section).b3) The sub-section being additionally integrated furthermore includes the sub-section which will be omitted when the new obstacle is circumnavigated and which will be appended to the approach sub-section.b4) A return sub-section leading back to the nearest path point will be added to the appended sub-section.b5) The further course of the subsequent cleaning path will correspond to the original course of the pre-programmed path.c) The subsequent cleaning path will replace the pre-programmed path during the further course of the cleaning process.d) If the cleaning robot encounters another new obstacle during the further course of the cleaning process, which is to say while traversing the subsequent cleaning path replacing the original, pre-programmed path, the above described programming strategies will be recursively re-executed analogously.

According to the above fundamental programming strategies, the cleaning path302to307described in the following will be determined by the cleaning robot201. Corresponding method-related steps are shown inFIG. 5. When the cleaning robot201reaches path point A, at which it detects the new obstacle301, it will trigger programming of the subsequent cleaning path302to307(500). The subsequent cleaning path302to307leads from the path point A past the new obstacle301302, maintaining a predefined safety clearance with respect to the new obstacle301(505). The subsequent cleaning path302to307rejoins the original, pre-programmed path110at point B. The cleaning robot stores the fact that the path section305which is a section of the pre-programmed path110and which is delimited by the points A and B was not traversed or cleaned and so was omitted (505). The cleaning robot201then checks whether the non-traversed or omitted path section305will be traversed again at a subsequent point in the pre-programmed cleaning path110(510).

This does not apply to the pre-programmed cleaning path110, so that subsequent cleaning of the omitted sub-section305and corresponding programming of the subsequent cleaning path302to307is necessary. Further programming of the subsequent cleaning path302to307would otherwise be unnecessary (511). The original, pre-programmed path course112would continue to apply.

The cleaning robot201checks the subsequent path points along the further course of the pre-programmed path110to ascertain which path point is situated closest to the omitted path section305(515). To do so, it determines the path point C at which path sub-sections304to306of the subsequent cleaning path302to307are integrated (515).

The subsequent cleaning path302to307thereafter proceeds from point B along the original path110to point C303. From point C the subsequent cleaning path proceeds by the shortest link to point B304, which is the last path point of the omitted sub-section305(520).

From point B the subsequent cleaning path302to307proceeds along the original path110to point A305, with the omitted sub-section305being traversed counter to the originally programmed direction of travel and cleaned in he process (525).

From point A the subsequent cleaning path302to307proceeds to return by the shortest link306to point C and so rejoins the original pre-programmed path110(530). The subsequent course307of the subsequent cleaning path302to307corresponds to the original course of the pre-programmed path110and ends at point E (535).

Alternatives Ai (i=number of the respective alternative) to the exemplary embodiment are described in the following.

In one alternative (A1) to the exemplary embodiment the map101is not generated by traversing and recording the space to be cleaned but, instead, was produced in advance by means, for example, of a programming action, and is stored in the cleaning robot.

In a further alternative (A2) to the exemplary embodiment a cinematic criterion taking into consideration a cinematic characteristic of the autonomous mobile unit is employed in addition to the distance criterion when the nearest point C, the integration point of the extension sub-section, is being determined.

If, for example, a cleaning robot201has a tricycle cinematic characteristic, which is to say it only moves on three wheels, certain points within the space will only be approachable with considerable difficulty and only with the cleaning robot's having attained a specific orientation. A complex shunting maneuver would have to be executed by the robot in such cases in order to attain a predefined orientation.

With this alternative the nearest point C is displaced along the pre-programmed path until it can also be approached cinematically favorably by the cleaning robot, which is to say without the need for major shunting maneuvers. Subsequent programming steps will be executed in accordance with the original method.

In a further alternative (A3) to the exemplary embodiment a time criterion and a processing criterion taking into consideration a travel time and a travel route of the cleaning robot are employed in addition to the distance criterion when the nearest point C, the integration point of the extension sub-section, is being determined.

With this alternative the nearest point C is displaced along the pre-programmed path until it can also be approached favorably in conditions relating to time and processing. Subsequent programming steps will be executed in accordance with the original method.

Conditions favorable in terms of time are to be understood as cleaning which is of as short a duration as possible. Conditions favorable in terms of processing are to be understood as cleaning positions which are as efficient as possible.

A fourth alternative (A4) to the exemplary embodiment relates to determining the return sub-section306(strategy step b4). It may be more favorable in terms of, for example, cleaning efficiency, for the return sub-section to end at a path point along the pre-programmed path which is different from the start point, which is to say at the nearest point C (see also exemplary embodiment). A case such as this is shown inFIG. 4.

FIG. 4shows the stored map101with the configuration according to the exemplary embodiment, which is to say with the pre-programmed path110, and with the new obstacle301, and also the subsequent cleaning path which was programmed by the cleaning robot and which has the path sub-sections302,303,304,305,307, and307.

FIG. 4also shows another new obstacle401and the associated subsequent cleaning path which was programmed by the cleaning robot and which has the path sub-sections402,403,404,405,406, and407. In this case the return sub-section406does not end at point C but at a point D. The path sub-section408of the original path110between the points C and D remains uncleaned in this case.

It should be noted that the original programming method can also be modified by any combinations of the described alternatives.

Shown below is a commented log file recorded by the cleaning robot during a cleaning process. A log file of this type is generally produced during a cleaning process (online). The cleaning robot records all programming and travel processes, which are stored in the log file. This allows the programming and travel processes to be retraced and checked on completion of the cleaning process. The log file shown below records various path courses traversed by the cleaning robot (FIG. 6atoFIG. 6f) and contains comments on which path courses were determined according to the programming methods described in the preceding.

The invention has been described in detail with particular reference to preferred embodiments thereof and examples, but it will be understood that variations and modifications can be effected within the spirit and scope of the invention.