Robot motion planning

Abstract

A method for motion planning for at least one robot includes providing a start configuration comprising at least one start position and a destination configuration comprising at least one destination position for the robot, providing a motion of at least one obstacle in the workspace of the robot, the obstacle motion defining a position of the obstacle that varies over time, and determining a motion of the robot from its start configuration to its destination configuration. The robot motion definies a position of the robot over a time period from a start time to a destination time. The robot motion is determined such that at each point in time between the start and destination times a distance between the robot and the obstacle does not fall below a predetermined threshold.

Claims

1. A method for motion planning for at least one robot having a plurality of axes that are actuated by respective drives and a microprocessor adapted to control the drives, the method comprising: providing a start configuration of a first robot comprising at least one start position; providing a destination configuration of the first robot comprising at least one destination position; providing information for a motion of at least one obstacle in the workspace of the first robot, the obstacle motion information defining a position of the obstacle varying over time; determining with the microprocessor a motion of the first robot from the start configuration to the destination configuration, the robot motion defining a position of the first robot over a time period from a start time to a destination time; wherein the robot motion is determined such that at each point in time between the start time and the destination time, a distance between the first robot and the obstacle does not fall below a predetermined threshold; wherein determining the motion of the first robot comprises employing at least one of: a state space comprising a time dimension and at least one position dimension, or a hyperspace comprising state transitions of the state space; wherein at least one of the state space or the hyperspace is discretized; determining a first motion of the first robot employing at least one of the state space or the hyperspace discretized at a first resolution; and determining a subsequent motion of the first robot employing a subspace of at least one of the state space or the hyperspace, wherein the subspace is at least one of in the vicinity of the first motion, or is discretized at a subsequent resolution finer than the first resolution.

2. The method of claim 1, wherein providing the destination configuration comprises providing the destination time for at least one destination position of the destination configuration.

3. The method of claim 1, wherein determining the first motion and the subsequent motion is performed iteratively.

4. The method of claim 1, wherein determining the motion of the first robot comprises finding a trajectory within at least one of the state space or the hyperspace that avoids cells occupied by the obstacle.

5. The method of claim 1, wherein at least one of: the motion of the first robot is determined such that a defined cost function is optimized; the motion of the first robot is determined until a predefined criterion is met; or the motion of the first robot is determined employing an A* algorithm.

6. The method of claim 1, further comprising smoothing the determined motion of the first robot.

7. The method of claim 6, wherein smoothing the determined motion of the first robot comprises filtering the determined motion.

8. The method of claim 1, further comprising: altering the motion of the obstacle in the workspace of the first robot; and redetermining the motion of the first robot; wherein the robot motion is redetermined such that at each subsequent point in time, a distance between the first robot and the obstacle moving according to the altered motion does not fall below the predetermined threshold.

9. The method of claim 8, wherein redetermining the motion of the first robot comprises redetermining the motion of the first robot in the vicinity of the previously determined motion of the robot.

10. The method of claim 1, further comprising: providing a start configuration comprising at least one start position for at least a second robot; providing a destination configuration comprising at least one destination position for the at least one second robot; and determining a motion of the second robot from the start configuration to the destination configuration according to one of the preceding claims; wherein the motions of the first and second robots are determined such that, at each point in time between a start time and a destination time of the first and second robots, a distance between the first and second robots does not fall below a predetermined threshold.

11. The method of claim 10, further comprising: determining initial motions of the first and second robots from the respective start configuration to the destination configuration, individually, such that for each robot at each point in time between the respective start and destination times of the respective robot, a distance between the respective robot and the obstacle does not fall below a predetermined threshold; and determining coordinated motions of the first and second robots from the respective start configuration to the respective destination configuration, such that at each point in time between the respective start and destination times of the first and second robots, a distance between the first and second robots does not fall below a predetermined threshold based on the determined initial motions.

12. The method of claim 11, wherein the coordinated motions of the first and second robots is determined such that the distance between the first and second robots does not fall below the predetermined threshold in the vicinity of the determined initial motions.

13. A method for operating at least one robot, the method comprising: determining a motion of the at least one robot according to claim 1; and controlling the at least one robot with the microprocessor to perform the determined motion.

14. A system for planning motion of at least one robot, the system comprising: means for providing a start configuration of the robot, the start configuration comprising at least one start position of the robot, and for providing at least one destination configuration of the robot that comprises at least one destination position for the robot; means for providing information of a motion of at least one obstacle in the workspace of the robot, the obstacle motion defining a position of the obstacle varying over time; and means for determining a motion of the robot from the start configuration to the destination configuration, the robot motion defining a position of the robot over a time period from a start time to a destination time, such that at each point in time between the start time and the destination time, a distance between the robot and the obstacle does not fall below a predetermined threshold; wherein determining the motion of the robot comprises employing at least one of: a state space comprising a time dimension and at least one position dimension, or a hyperspace comprising state transitions of the state space; wherein at least one of the state space or the hyperspace is discretized; and wherein determining the motion of the robot further comprises: determining a first motion of the robot employing at least one of the state space or the hyperspace discretized at a first resolution, and determining a subsequent motion of the robot employing a subspace of at least one of the state space or the hyperspace, wherein the subspace is at least one of in the vicinity of the first motion, or is discretized at a subsequent resolution finer than the first resolution.

15. An arrangement comprising: at least one robot; and a system for motion planning for the at least one robot according to claim 14.

16. A computer program product comprising source code stored on a non-transitory computer-readable medium, the source code, when executed on a microprocessor, causing the microprocessor to: provide a start configuration of a first robot, the start configuration comprising at least one start position; provide a destination configuration of the first robot, the destination configuration comprising at least one destination position; provide information for a motion of at least one obstacle in the workspace of the first robot, the obstacle motion information defining a position of the obstacle varying over time; and determine a motion of the first robot from the start configuration to the destination configuration, the robot motion defining a position of the first robot over a time period from a start time to a destination time; wherein the robot motion is determined such that at each point in time between the start time and the destination time, a distance between the first robot and the obstacle does not fall below a predetermined threshold; wherein determining the motion of the robot comprises employing at least one of: a state space comprising a time dimension and at least one position dimension, or a hyperspace comprising state transitions of the state space; wherein at least one of the state space or the hyperspace is discretized; and wherein determining the motion of the robot further comprises: determining a first motion of the robot employing at least one of the state space or the hyperspace discretized at a first resolution, and determining a subsequent motion of the robot employing a subspace of at least one of the state space or the hyperspace, wherein the subspace is at least one of in the vicinity of the first motion, or is discretized at a subsequent resolution finer than the first resolution.

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 present invention.

(2) FIGS. 1a-d graphically illustrate steps of a method of motion planning for at least one robot according to an embodiment of the present invention.

(3) FIG. 2 is a flowchart illustrating the method of motion planning.

(4) FIG. 3 depicts an arrangement comprising at least one robot and a system (for) carrying out the method.

(5) FIG. 4 illustrates a state space employed in the motion planning.

DETAILED DESCRIPTION

(6) FIGS. 1 and 2 show steps of a method of motion planning for one or two mobile robots R1, R2 of an arrangement by a system S of said arrangement (cf. FIG. 3) according to an embodiment of the present invention.

(7) In a first step S10 start and destination configurations for mobile robot R1 are provided by a user, e.g. by entering corresponding values into system S. A horizontal start position (x1, y1) on a floor at a start time t0 and a horizontal destination position (x3, y1) at a predefined destination time t2 are indicated by bold frames in FIG. 1 a), c) and FIG. 4 respectively.

(8) If a coordinated motion also of mobile robot R2 is to be planned then a start position (x3, y2) at start time t0 and a destination position (x1, y2) at destination time t2 are provided as well in step S10 as indicated in dashed lines in FIG. 1 a) and c) respectively.

(9) Subsequently (cf. step S20), parallel or before, a linear motion of a dynamic obstacle O is provided between (x3, y1) at t0 and (x1, y1) at t2 as indicated by a shaded cell in FIG. 1 a)-c) and FIG. 4.

(10) In step S30 the state space (x, y, t) is discretized at a first resolution as indicated by corresponding discrete cells of the horizontal floor at discrete times t0, t1 and t2 in FIG. 1 a)-c) and FIG. 4.

(11) Next, a motion of mobile robot R1 is determined by an D* Lite algorithm such that cells occupied by robot R1 and obstacle O are not identical but neighbouring at least while minimizing energy consumption as a cost function in step S30.

(12) Thereto transitions between states of said discretized state space are employed to satisfy predefined kinematical and dynamical restrictions as indicated by arrows in FIG. 1 a)-c). Just as a simple example for better understanding in FIG. 1 b) no immediate return from (x2, y2) to (x1, y1) is possible or taken into account respectively since the required reverse motion would exceed drive capability of the mobile robot R1.

(13) Since energy consumption is employed as cost function, a certain contribution of energy consumption can be assigned to each such state transition which corresponds to a (super- or hyper)state of a hyperspace comprising state transitions of said state space (x, y, t). Thus the contribution of energy consumption can be assigned to corresponding super- or hyperstates of said hyperspace respectively, which allows for improved computation of the motion.

(14) This first motion is schematically indicated by the sequence FIG. 1 a)-c). Determining said motion can be understood as finding a trajectory of minimal energy consumption connecting (x1, y1, t0) and (x3, y1, t2) while avoiding the cells (x3, y1, t0), (x2, y1, t1) and (x1, y1, t2).

(15) This is illustrated by FIG. 4 showing said discretized state space with said cells (x3, y1, t0), (x2, y1, t1) and (x1, y1, t2) occupied by moving obstacle O (shaded in FIG. 4) and start and destination configuration of R1 (bold in FIG. 4).

(16) In subsequent step S40 the resolution of the state space's discretization is increased in the vicinity of the motion determined in step S30 as indicated by FIG. 1d).

(17) As long as a predefined threshold for the resolution of the state space or its discretization respectively has not yet been reached (S40: N), the method or system S respectively returns to step S30, determining a (further) subsequent motion of R1 within a state space which is (further) restricted to the vicinity of the foregoing (first) motion and discretized at the (further) increased resolution (cf. FIG. 1 d)).

(18) If said criterion is met (S40: Y), the method or system S respectively proceeds with step S50, therein checking whether all robots' motions have been determined.

(19) Ifaccording to one embodimentonly robot R1's motion is to be planned, the method or system S respectively proceeds with step S60.

(20) Ifaccording to another embodimentalso motion of mobile robot R2 is to be planned then the method or system S respectively returns to step S30 and determines such motion as described before, starting again with the first resolution.

(21) As one understands therefrom, those initial motions of robots R1, R2 are initially determined individually, in particular independently from one another, in steps S30-S50.

(22) This results in an initial motion (x3, y2, t0).fwdarw.(x2, y2, t1).fwdarw.(x1, y2, t2) for R2 which thus would collide with R1 at its initial motion (x1, y1, t0).fwdarw.(x2, y2, t1).fwdarw.(x3, y1, t2).

(23) Thus, starting with these initial motions of R1, R2, in step S60 coordinated motions are determined in step S60.

(24) This may be implemented as described before with respect to the individual motions but within a common state space comprising the (discretized) unique time dimension t and position dimensions (x.sub.R1, y.sub.R1) for robot R1 and position dimensions (x.sub.R2, y.sub.R2) for robot R2 ({x.sub.R1y.sub.R1x.sub.R2y.sub.R2t}). Thus the coordinated motions are determined as a trajectory in said common state space with higher dimension .sup.5 in which states or discrete cells (x.sub.R1=a, y.sub.R1=b, x.sub.R2=a, y.sub.R2=b, t=c) are avoided or forbidden respectively as are states or discrete cells occupied by the obstacle(s).

(25) Again such coordinated motions may be iteratively optimized until a predefined criterion is met (S70: Y), e.g. a maximum computing time has been lapsed or the like.

(26) In step S80 said coordinated motions are smoothened by filtering as indicated in FIG. 1 d)).

(27) In step S90 the method or system S respectively checks whether the motion of obstacle O has altered. If so (S90: Y), motions of R1 (and R2 as the case may be) are re-planed as described above with respect to steps S20-S80, starting with the already determined motions as a basis.

(28) Otherwise (S90: N) the planned motion(s) is/are performed by controlling the robots R1, R2 accordingly (cf. step S100 and FIG. 3).

(29) While at least one exemplary embodiment has been presented in the foregoing summary and detailed description, it should be appreciated that a vast number of variations exist. It should also be appreciated that the exemplary embodiment or exemplary embodiments are only examples, and are not intended to limit the scope, applicability, or configuration in any way. Rather, the foregoing summary and detailed description will provide those skilled in the art with a convenient road map for implementing at least one exemplary embodiment, it being understood that various changes may be made in the function and arrangement of elements described in an exemplary embodiment without departing from the scope as set forth in the appended claims and their legal equivalents.

(30) In particular for easier understanding determining the motions has been illustrated in particular with respect to the state space itself. However, as already explained before, its hyperspace comprising the state transitions may be employed additionally or alternatively.

(31) For example instead of start position (x1, y1, t0) possible state transitions {(x1, y1, t0).fwdarw.(x2, y1, t1), (x1, y1, t0).fwdarw.(x1, y2, t1), (x1, y1, t0).fwdarw.(x2, y2, t1)} may be employed and the like.

(32) Then for example a state transition (x2, y2, t1).fwdarw.(x1, y1, t2) corresponding to a reverse motion exceeding drive capabilities corresponds to a (super- or hyper)state of such hyperspace. By avoiding or forbidding said (super- or hyper)state the corresponding dynamic constraint can easily be observed.

(33) Additionally, energy consumption required for e.g. a state transition (x1, y1, t0).fwdarw.(x2, y2, t1) can be assigned to the corresponding (super- or hyper)state, thus facilitating computation of the cost function.

(34) 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 detail. 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 NUMBERS

(35) .circle-solid. obstacle R1 mobile robot R2 further mobile robot S system