Traveling down a prescribed arrangement of paths with a mobile robot

Abstract

A method for traveling down a prescribed arrangement of paths which are connected to one another at nodes with a mobile robot. The robot changes from an initial route, which contains all as yet untraveled paths, to a different replacement route including a loop route which retakes at least one path and at least one further path, and a subsequent remaining route which contains all as yet untraveled paths at that time if a value of a quality function for the replacement route is lower than a value of this quality function for the initial route. The quality function is dependent on a first effort, a second effort, and a variable weighting of the first and second values in relation to one another. The variable weighting weights the second effort lower for a first localization uncertainty of the robot.

Claims

1. A method for traversing a prescribed arrangement of paths with a mobile robot, wherein the paths are connected to one another at nodes, the method comprising: switching the robot from an initial route that contains all remaining untraveled paths of the initial route to a different replacement route and a subsequent remaining route in response to a value of a quality function for the replacement route being less than a value of a quality function for the initial route; wherein the replacement route includes a loop route; wherein the loop route comprises at least one path that is re-taken after the mobile robot already traversed that path, and at least one further path; wherein the subsequent remaining route comprises all remaining untraveled paths of the initial route at the time the mobile robot is switched from the initial route; wherein the quality function depends on a first effort value, a second effort value, and a variable weighting of the first and second effort values in relation to one another; wherein the first effort value is the lower of: a minimum effort value for a loop route that retakes at least one path after taking that path and at least one further path, and a minimum effort value for a target route that contains all remaining untraveled paths of the initial route; and the second effort value is a minimum effort value for a remaining route that contains all remaining untraveled paths of the initial route after the loop route; and wherein the variable weighting weights the second effort value lower for a first localization uncertainty of the robot than for a smaller second localization uncertainty of the robot.

2. The method of claim 1, wherein at least one of: the mobile robot is an autonomous robot; the variable weighting weights the second effort value to a maximum value when the localization uncertainty of the robot is at a minimum; the variable weighting weights the second effort value to be equal to the first effort value when the localization uncertainty of the robot is at a minimum; the variable weighting weights the second effort value to a minimum value when the localization uncertainty of the robot is at a maximum; or the variable weighting weights the second effort value such that it decreases to zero when the localization uncertainty of the robot is at a maximum.

3. The method of claim 1, wherein the robot switches from the initial route to one of a plurality of replacement routes for which the value of the quality function is the smallest.

4. The method of claim 1, further comprising determining at least one pose of the mobile robot in its environment.

5. The method of claim 4, further comprising creating a map of the environment of the mobile robot based on the at least one determined pose.

6. The method of claim 1, wherein an effort value of a route is at least one of: proportional to a length of the route; dependent on a time required to travel the route with the robot; or dependent on an energy expended to travel the route with the robot.

7. The method of claim 1, wherein the localization uncertainty of the mobile robot depends on at least one of: a length of a previously traveled route; a number of loop routes traveled by the mobile robot; or a determination of at least one pose of the mobile robot in its environment.

8. A system for traveling down a predetermined arrangement of paths, which are connected to one another at nodes, with a mobile robot, the system comprising: means for switching the robot from an initial route that contains all remaining untraveled paths of the initial route to a different replacement route and a subsequent remaining route in response to a value of a quality function for the replacement route being less than a value of a quality function for the initial route; wherein the replacement route includes a loop route; wherein the loop route comprises at least one path that is re-taken after the mobile robot already traversed that path, and at least one further path; wherein the subsequent remaining route comprises all remaining untraveled paths of the initial route at the time the mobile robot is switched from the initial route; wherein the quality function depends on a first effort value, a second effort value, and a variable weighting of the first and second effort values in relation to one another; wherein the first effort value is the lower of: a minimum effort value for a loop route that retakes at least one path after taking that path and at least one further path, and a minimum effort value for a target route that contains all remaining untraveled paths of the initial route; and the second effort value is a minimum effort value for a remaining route that contains all remaining untraveled paths of the initial route after the loop route; and wherein the variable weighting weights the second effort value lower for a first localization uncertainty of the robot than for a smaller second localization uncertainty of the robot.

9. The system of claim 8, wherein at least one of: the mobile robot is an autonomous robot; the variable weighting weights the second effort value to a maximum value when the localization uncertainty of the robot is at a minimum; the variable weighting weights the second effort value to be equal to the first effort value when the localization uncertainty of the robot is at a minimum; the variable weighting weights the second effort value to a minimum value when the localization uncertainty of the robot is at a maximum; or the variable weighting weights the second effort value such that it decreases to zero when the localization uncertainty of the robot is at a maximum.

10. A computer program product for traversing a prescribed arrangement of paths with a mobile robot, wherein the paths are connected to one another at nodes, the computer program product including a program code stored on a non-transient, computer-readable medium, the program code, when executed by a computer, causing the computer to: switch the robot from an initial route that contains all remaining untraveled paths to a different replacement route and a subsequent remaining route in response to a value of a quality function for the replacement route being less than a value of a quality function for the initial route; wherein the replacement route includes a loop route; wherein the loop route comprises at least one path that is re-taken after the mobile robot already traversed that path, and at least one further path; wherein the subsequent remaining route comprises all remaining untraveled paths of the initial route at the time the mobile robot is switched from the initial route; wherein the quality function depends on a first effort value, a second effort value, and a variable weighting of the first and second effort values in relation to one another; wherein the first effort value is the lower of: a minimum effort value for a loop route that retakes at least one path after taking that path and at least one further path, and a minimum effort value for a target route that contains all remaining untraveled paths of the initial route; and the second effort value is a minimum effort value for a remaining route that contains all remaining untraveled paths of the initial route after the loop route; and wherein the variable weighting weights the second effort value lower for a first localization uncertainty of the robot than for a smaller second localization uncertainty of the robot.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate exemplary embodiments of the invention and, together with a general description of the invention given above, and the detailed description given below, serve to explain the principles of the invention.

(2) FIG. 1 schematically depicts a mobile robot following a prescribed arrangement of paths according to an embodiment of the present invention; and

(3) FIG. 2 illustrates a method for traveling the prescribed arrangement of paths with the mobile robot according to an embodiment of the present invention.

DETAILED DESCRIPTION

(4) FIG. 1 shows a prescribed arrangement of paths that are connected to one another in nodes K1-K10, as well as an autonomous mobile robot 1 with a controller 2.

(5) By travelling all paths of the prescribed arrangement, in particular an exploration path for a simultaneous localization and map creation with the robot 1 can be prescribed and a priori environmental information thereby used or taken into account.

(6) Costs c are specified for each of the paths, for which values are given by way of example in FIG. 1, for example costs of 10 units for the path between nodes K1 and K2 (c.sub.1-2=10). These costs can, for example, depend on the length of the path, the time required to travel down it by the robot 1 or the like, and can in particular indicate or be these.

(7) In a first step S10 (cf. FIG. 2), a (first) initial route was determined using a CPP solution method which, starting at node K1, contains all paths at least once, and thereby a (total) effort equal to the sum of all costs of all paths traveled is minimized.

(8) In the embodiment, this resulted in the (first) initial route K1.fwdarw.K2.fwdarw.K3.fwdarw.K4.fwdarw.K5.fwdarw.K4.fwdarw.K7.fwdarw.K10.fwdarw.K9.fwdarw.K8.fwdarw.K3.fwdarw.K8.fwdarw.K7.fwdarw.K6.fwdarw.K5.fwdarw.K1.

(9) When following this initial route K1, robot 1 currently approached node K7. For this, the controller 2 determines the current localization uncertainty of the robot in a step S20, for example in the form of quantity normalized to the range [0; 1] or the sum K of the main diagonals of the covariance matrix of the pose of the robot 1 in its environment.

(10) If this value exceeds a specified threshold value (for the first time) for the current node K7, as in the embodiment, since the localization uncertainty has become too great due to the distance to this node without a loop route, for example, the controller 2 determines in a step S30 a (current) initial route, which connects this node with the target node K1 and contains all as yet untraveled paths; in the embodiment, it uses the remainder of the above-mentioned (first) initial; route (K7.fwdarw.K10.fwdarw.K9.fwdarw.K8.fwdarw.K3.fwdarw.K8.fwdarw.K7.fwdarw.K6.fwdarw.K5.fwdarw.K1).

(11) It can be seen that no route is retaken after taking this path and at least one further path, so the current initial route does not have a loop route.

(12) In step S30, the controller 2 additionally determines possible replacement routes which each retake at least one path after taking this path and at least one further path.

(13) To do this, it hides the three most recently traveled paths K3-K4, K4-K5 and K4-K7 and establishes for nodes K3 and K5 that have already been approached that these also then or with hidden paths K3-K4, K4-K5 and K4-K7 can be approached from the current node K7, whereas this is not the case for K4 (in this way, a trivial return K7 K4 is avoided).

(14) For these nodes K3 and K5with the paths K3-K4, K4-K5 and K4-K7 unhiddenin step S30, by means of an open and/or selective CPP solution method (Open Rural Chinese Postman Problem), a loop route is determined, which retakes at least one path after taking this path and at least one further path, and one subsequent remaining path, which route then contains all as yet untraveled paths and leads back to the destination node K1.

(15) The value of a quality function G is determined in a step S40 for the current initial route and replacement routes, each composed of one of the loop routes and the subsequent remaining route.

(16) For this purpose, in step S40, a first effort is determined in each case as the smaller of a minimum effort for of a loop route, which retakes at least one path after taking this path and at least one further path, and a minimal effort for a target route that contains all as yet untraveled paths, as well as a second effort, which is a minimal effort for a remaining route that contains all the paths that have not yet been traveled after this loop route:

(17) $\mathrm{current}\mathrm{exit}\mathrm{route}:K7.fwdarw.K10.fwdarw.K9.fwdarw.K8.fwdarw.K3.fwdarw.K8.fwdarw.K7.fwdarw.K6.fwdarw.K5.fwdarw.K1\mathrm{first}\mathrm{effort}{C}_{1,A}=c_{7-10}+c_{10-9}+c_{9-8}+c_{8-3}+c_{3-8}+c_{8-7}+c_{7-6}+c_{6-5}+c_{5-1}\begin{array}{c}\left(\mathrm{target}\mathrm{route}\right)=3+5+3+5+5+5+5+5+4\\ =40\end{array}\mathrm{second}\mathrm{effort}{C}_{2A}=0\mathrm{Replacment}\mathrm{route}\mathrm{with}K5\mathrm{or}\mathrm{path}4-5:\mathrm{Loop}\mathrm{route}:K7.fwdarw.K6.fwdarw.K5.fwdarw.K4\begin{array}{c}\mathrm{first}\mathrm{effort}{C}_{1,E1}=c_{7-6}+c_{6-5}+c_{5-4}\\ =5+5+5\\ =15\end{array}\mathrm{Remaining}\mathrm{route}:K4.fwdarw.K7.fwdarw.K10.fwdarw.K9.fwdarw.K8.fwdarw.K3.fwdarw.K8.fwdarw.K7.fwdarw.K4.fwdarw.K5.fwdarw.K1\begin{array}{c}\mathrm{second}\mathrm{effort}{C}_{2,E2}=c_{4-7}+c_{7-10}+c_{10-9}+c_{9-8}++\\ c_{8-3}+c_{3-8}+c_{8-7}+c_{7-4}+c_{4-5}+c_{5-1}\\ =5+3+5+3+5+5+5+5+5+4\\ =45\end{array}\mathrm{Replacement}\mathrm{route}\mathrm{with}K3\mathrm{or}\mathrm{path}3-4:\mathrm{Loop}\mathrm{route}:K7.fwdarw.K8.fwdarw.K3.fwdarw.K4\begin{array}{c}\mathrm{first}\mathrm{effort}{C}_{1,E2}=c_{7-8}+c_{8-3}+c_{3-4}\\ =5+5+5\\ =15\end{array}\mathrm{Remaining}\mathrm{route}:K4.fwdarw.K7.fwdarw.K10.fwdarw.K9.fwdarw.K8.fwdarw.K7.fwdarw.K6.fwdarw.K5.fwdarw.K1\begin{array}{c}\mathrm{second}\mathrm{effort}{C}_{2,E2}=c_{4-7}+c_{7-10}+c_{10-9}+c_{9-8}++\\ c_{8-7}+c_{7-6}+c_{6-5}+c_{5-1}\\ =5+3+5+3+5+5+5+4\\ =35\end{array}$

(18) Then, in step S40, the value of the quality criterion C.sub.E=C.sub.1+K.Math.C.sub.2 for each of the routes is determined:

(19) current initial route: C.sub.E,A=C.sub.1,A+K.Math.C.sub.2,A

(20) Replacement route with K5 or path 5-4: C.sub.E,E1=C.sub.1,E1+K.Math.C.sub.2,E1

(21) Replacement route with K3 or path 3-4: C.sub.E,E2=C.sub.1,E2+K.Math.C.sub.2,E2

(22) If, for example, the robot 1 is (still or again) perfectly localized at the node 7, its localization uncertainty or the variable weighting of the second effort C.sub.2 is equal to 1:

(23) $\mathrm{current}\mathrm{initial}\mathrm{route}:C_{E,A}=40+1.=40\mathrm{Replacement}\mathrm{route}\mathrm{with}K5\mathrm{or}\mathrm{path}5-4:C_{E,E1}=15+1.45=60\mathrm{Replacement}\mathrm{route}\mathrm{with}K3\mathrm{or}\mathrm{path}3-4:C_{E,E2}=15+1.35=50$

(24) Since the value of the quality function for the initial route is smaller than the value for the replacement routes (S50: N), the robot 1 does not change, but continues along the current initial route.

(25) Conversely, if the robot 1 is localized at node 7 with maximum uncertainty, its localization uncertainty or the variable weighting of the second effort C.sub.2 is equal to 0:

(26) $\mathrm{current}\mathrm{initial}\mathrm{route}:C_{E,A}=40+0.=40\mathrm{Replacement}\mathrm{route}\mathrm{with}K5\mathrm{or}\mathrm{path}5-4:C_{E,E1}=15+0.45=15\mathrm{Replacement}\mathrm{route}\mathrm{with}K3\mathrm{or}\mathrm{path}3-4:C_{E,E2}=15+0.35=15$

(27) Since the effort for the remaining route is no longer relevant and the value of the quality function for the replacement routes is thereby smaller than the value for the initial route (S50: Y), the robot 1 now changes to the (more favorable) replacement route (S60) as desired, wherein in this extreme case with K=0 both substitute routes appear equally good, with little consideration of the remaining route, the replacement route is more favorable with K3 or path 3-4 and is selected.

(28) Although embodiments have been explained in the preceding description, it is noted that a large number of modifications are possible. It is also noted that the embodiments are merely examples that are not intended to restrict the scope of protection, the applications and the structure in any way. Rather, the preceding description provides the person skilled in the art with guidelines for implementing at least one exemplary embodiment, with various changes, in particular with regard to the function and arrangement of the described components, being able to be made without departing from the scope of protection as it arises from the claims and from these equivalent combinations of features.

(29) While the present invention has been illustrated by a description of various embodiments, and while these embodiments have been described in considerable detail, it is not intended to restrict or in any way limit the scope of the appended claims to such de-tail. The various features shown and described herein may be used alone or in any combination. Additional advantages and modifications will readily appear to those skilled in the art. The invention in its broader aspects is therefore not limited to the specific details, representative apparatus and method, and illustrative example shown and described. Accordingly, departures may be made from such details without departing from the spirit and scope of the general inventive concept.

REFERENCE NUMERALS

(30) 1 Mobile robot 2 Controller K1, . . . , K10 Node K1-K2, K2-K3, . . . K1-K5, Path