Patent ID: 12202146

DETAILED DESCRIPTION OF THE EMBODIMENTS

The following discussion of the embodiments of the disclosure directed to methods and systems for robotic system dynamic velocity modification is merely exemplary in nature, and is in no way intended to limit the disclosed devices and techniques or their applications or uses.

It is well known to use industrial robots for a variety of manufacturing, assembly and material movement operations. These operations include spray painting, welding, part pick and place tasks, and many others. In many robot workspace environments, obstacles may be present and may at times be in the path of the robot's motion. That is, without adaptive motion planning, some part of the robot may collide with some part of an obstacle when the robot moves from its current position to a destination position. The obstacles may be static structures such as fixtures and tables, or the obstacles may be dynamic (moving) objects such as people, forklifts, other robots and other machines. When dynamic objects may be present, the robot's motion must be planned in real time for each control cycle.

In some robotic applications, the robot's path can be adjusted to move around an obstacle. However, in many applications, the robot (tool center) must move along a planned reference path in order to complete the task properly. In these defined-path applications, the only recourse when an obstacle obstructs the robot's path is to slow down or stop the robot. Techniques have been developed for modifying a robot's speed in response to the presence of an obstacle. However, these techniques suffer from various drawbacks—including too frequently stopping the robot in the presence of an obstacle, and deviating from the planned reference path when the robot's speed is reduced.

The present disclosure provides methods and systems which adaptively respond to the presence of obstacles in the robot workspace, slowing the robot down only as necessary to allow the potential collision to clear, while maintaining the planned reference path of the tool. The technique has been tested in simulation and real world experiments, including both multi-robot environments and human-robot interactions. These methods and systems, including two different implementation embodiments, are discussed in detail below.

In any technique which slows down a robot in response to the presence of a workspace obstacle, it is necessary to determine how much the robot needs to be slowed down. The amount of slowdown is based on several factors, including current robot velocity (actually a vector of rotational velocities, one for each joint in the robot), a stopping time calculated from the current velocity and robot mechanical constraints, and distance and velocity properties of the obstacle.

FIG.1is a graph100showing how a robot stopping time is computed from robot joint velocity and maximum joint acceleration and jerk constraints, in a manner known in the art. The graph100plots joint acceleration on a vertical axis against time on a horizontal axis. Consider the graph100to represent a single robot joint, where the same calculation is performed for each of the (five or six) joints in the robot. At time t=0, the joint has a velocity −{dot over (q)} and a maximum acceleration −{umlaut over (q)} toward the obstacle. In order to stop the robot joint, a maximum jerk (rate of change of acceleration)maxmust be applied in a first phase110until a maximum acceleration {umlaut over (q)}maxis reached. The maximum jerk and maximum acceleration values for each joint are known mechanical limitations of the robot. In a second phase120, the robot joint maintains the maximum acceleration {umlaut over (q)}max. In a third phase130, the acceleration drops off at a rate of the negative of the maximum jerkmax.

The area under the curve of a graph of acceleration vs. time is velocity. The two triangular portions of area under the curve in the first phase110cancel each other out. The remaining portion of area under the curve is the shaded area of the graph100, comprised of a rectangular portion140and a triangular portion150. The total area of the rectangular portion140and the triangular portion150must add up to a value of {dot over (q)} in order to take the joint from the initial velocity −{dot over (q)} to a stop. That is,

q˙=12⁢ts⁢l⁢o⁢p⁢e⁢q¨max+tconst⁢q¨max(1)

The total stopping time of the robot, tstop, is represented by arrow160. The total stopping time tstopis made up of three maximum jerk segments170(designated tslope) and one maximum acceleration segment180(tconst). That is,
tstop=3tslope+tconst(2)

Furthermore, the duration of the maximum jerk segments170can be determined by:
tslope={dot over (q)}max/max(3)

Evaluating Equations (1)-(3) for each of the joints i in the robot, the robot stopping time tstopcan be determined based on the robot joint velocities as follows:

tstop=maxi=1,…,n(❘"\[LeftBracketingBar]"q˙i❘"\[RightBracketingBar]"q¨i,max+2.5⁢q¨i,maxi,max)(4)
Where |{dot over (q)}i| is the absolute value of the velocity of each joint i, and all other values are known constants (mechanical constraints of each joint).

Finally, an appropriate robot speed limit can be determined for each joint i in the robot, for operation in the presence of an obstacle, as follows:

❘"\[LeftBracketingBar]"q˙i,brake❘"\[RightBracketingBar]"=max⁡(0,min⁡(q˙i,max,(tstop-2.5⁢q¨i,maxi,max)⁢q¨i,max))(5)
Where all constants and variables in Equation (5) have been defined above, and the speed limit {dot over (q)}i,brakeis determined for each joint i in the robot. For an obstacle in the robot workspace having a robot-obstacle distance dobsand a maximum velocity vmaxof the obstacle itself or the robot-obstacle relative velocity, the value of tstopcan be determined as tstop=dobs/vmax, and inserted into Equation (5) to calculate the joint speed limits.

FIG.2is a block diagram illustration of a dynamic motion optimization technique known in the art, where robot velocity may be reduced in the presence of a workspace obstacle. A tracking controller210receives as input a reference position xrefand a reference velocity vref, which define a target tool center path and velocity (both in Cartesian coordinates). The tracking controller210computes a desired velocity vector {dot over (x)}desbased on the reference inputs and feedback from the robot (discussed below), and provides the desired velocity vector {dot over (x)}desto a dynamic motion optimization module220.

The dynamic motion optimization module220receives obstacle data input from a perception module230, and computes robot joint position and velocity commands, qcmdand {dot over (q)}cmd, respectively. The joint command output from the dynamic motion optimization module220includes slowdown of the robot if necessary based on the workspace obstacle data. The dynamic motion optimization module220uses Equations (1)-(5) above to compute reduced robot joint speeds in the presence of workspace obstacles. A robot system240includes a controller and a robot, where the controller causes the robot to follow the joint commands from the dynamic motion optimization module220. The robot system240provides actual joint state (position and velocity) data, qactand {dot over (q)}act, respectively, as feedback on line250to the tracking controller210.

FIG.3is an illustration of how a commanded tool path position can deviate from a planned reference path when velocity is reduced in the prior art technique ofFIG.2. On the left-hand side ofFIG.3, a curve310represents the target tool center path, which is reference position xrefdefined above, and a point312is one particular point along the tool center path xref. The xrefpoint312is the point that was most recently computed by the tracking controller210. A current position point xcur320indicates the current actual tool center point of the robot. Because the current position point xcur320is well behind the xrefpoint312, due to a robot slowdown commanded by the dynamic motion optimization module220, the tracking controller210computes a desired velocity vector {dot over (x)}des(arrow330) which is not along the curve310defining the reference path. This causes the robot's actual path to deviate from the reference path310. This effect can be seen in the illustrations on the right-hand side ofFIG.3.

A multi-link robot arm340is shown in top view. The robot arm340has a tool center point which follows a reference path350. A robot arm360operates in the same workspace as the robot arm340, where the robot arm360is programmed for its tool center point to follow a reference path370. The reference paths350and370overlap, and thus the robot arms340and360would collide with each other if no obstacle detection and avoidance measures were taken. In this example, the robot arm340carries out its motion with no collision avoidance measures, while the robot arm360is programmed with the dynamic motion optimization technique ofFIG.2. That is, the robot arm360will be commanded to slow down when the robot arm340is in its path.

An actual path380shows the actual path taken by the tool center point of the robot arm360. It can be seen that the actual path380deviates from the reference path370in the middle portion of the paths. This path deviation from reference is undesirable, and is caused by the effect discussed above—namely, the dynamic motion optimization module220commands a slowdown of the robot arm360due to the obstacle in its path, but the tracking controller210does not adequately recognize the slowdown and provides desired velocity instructions which cause the actual path to deviate from the reference path.

The techniques of the present disclosure have been developed to overcome the drawbacks of the prior art dynamic motion optimization technique discussed above.

FIG.4is a block diagram illustration of a dynamic motion optimization system400, and flowchart diagram of a corresponding method, where robot velocity may be reduced in the presence of a workspace obstacle, and a slowdown factor is provided as feedback from an online velocity modification (OVM) module to a tracking controller, according to an embodiment of the present disclosure. A tracking controller410receives as input a reference position qref, which defines a target (planned) robot path in joint coordinates. The tracking controller410computes desired robot joint position and velocity vectors, (qdesand {dot over (q)}des, respectively) based on the reference path input, and provides the desired joint position and velocity vector data to an online velocity modification module420.

The online velocity modification module420receives obstacle data input from a perception module430, and computes robot joint position and velocity commands, qcmdand {dot over (q)}cmd, respectively. The joint command output from the online velocity modification module420includes slowdown of the robot if necessary based on the workspace obstacle data. The online velocity modification module420uses Equations (1)-(5) discussed above to compute reduced robot joint speeds in the presence of workspace obstacles. The amount of robot speed attenuation computed by the online velocity modification module420is embodied in a slowdown ratio ds, where the value of ds is in a range from zero (ds=0; full stop of robot) to one (ds=1; full speed of robot per the planned motion; no slowdown; in this case, {dot over (q)}des={dot over (q)}cmd). The value of ds is provided as feedback on a line440from the online velocity modification module420to the tracking controller410.

A robot system450includes a controller and a robot, where the controller causes the robot to follow the joint commands (qcmdand {dot over (q)}cmd) from the online velocity modification module420. The robot in the robot system450provides actual joint state data, qactand {dot over (q)}act, as feedback to the controller in the robot system450. However, because the slowdown ratio ds from the online velocity modification module420is already known by the tracking controller410, feedback of robot state data from the robot system450to the tracking controller410is not needed. That is, the online velocity modification module420provides the value of ds as feedback to the tracking controller410, whereby the tracking controller410takes the robot slowdown into account when computing the desired robot joint position and velocity vectors, (qdesand {dot over (q)}des, respectively). This is illustrated further in the following figure.

FIG.5is an illustration of how a planned reference path comprised of a sequence of interpolation points is parameterized into a continuous path defined by an arc length s, in the system ofFIG.4, according to an embodiment of the present disclosure. A planned reference path510is defined by a plurality of interpolation points q0(512), q1(514), q2(516), . . . and so forth through a final target point qT(518). The planned reference path510is provided as input to the tracking controller410as shown inFIG.4and discussed above.

On the right, a continuous reference path520is computed as a function of an arc length parameter s, where s=0 at the initial path point q0(512), and s=1 at the final (target) point qT(518). The continuous reference path p(s)520is computed by the tracking controller410using any suitable technique, such as a spline function. The continuous reference path p(s)520is then used by the tracking controller410, along with the slowdown ratio ds feedback, as follows. At each computation cycle, the tracking controller410would ordinarily increment the value of s in order to move along the continuous reference path520, in an amount consistent with the time duration of the reference path motion and the time increment of the computation cycle. If the feedback from the online velocity modification module420indicates that the value of ds=1, then the tracking controller410increments the value of s in the full amount for this computation cycle. On the other hand, if the feedback from the online velocity modification module420indicates that the value of ds=0, then the tracking controller410does not increment the value of s at all for this computation cycle, which means that qdesdoes not change from the previous computation cycle, {dot over (q)}desbecomes zero, and the robot stops. If 0<ds<1, then the tracking controller410increments the value of s in an amount proportional to ds for the current computation cycle; this means that the robot slows down from its planned motion, which is the desired response in the presence of a qualifying workspace obstacle.

Returning toFIG.4, the online velocity modification module420receives the obstacle data from the perception module430and performs a velocity modification optimization at each computation cycle as follows:

minq.qdes-q2+λ⁢q.(6)s.t.q.i≤❘"\[LeftBracketingBar]"q.i,brake❘"\[RightBracketingBar]"(7)
Where Equation (6) is the optimization objective function which minimizes path deviation between a computed path q and the desired path qdes, and Equation (7) is a constraint equation on the individual robot joint velocities, and where |{dot over (q)}i,brake| (in Equation (7)) is computed from Equation (5) discussed previously. In this way, the online velocity modification module420determines if slowdown is necessary based on the obstacle data, and if so, computes the individual joint speed limits based on the stopping time tstop.

After the optimization computation has converged, a value of the slowdown ratio ds is computed by:
ds=min(|{dot over (q)}brake|/|{dot over (q)}max|)  (8)
Where Equation (8) calculates the ratio of |{dot over (q)}brake| to |{dot over (q)}max| for each robot joint i, and uses the minimum joint speed ratio value as the slowdown ratio ds.

As discussed above, the value of the slowdown ratio ds is provided as feedback from the online velocity modification module420to the tracking controller410. The tracking controller410then computes a new value of the arc length parameter as s=s+ds. That is, if ds=1, the arc length parameter is incremented by a full step, and if ds=0, the arc length parameter does not change and the robot stops. The new desired position along the path is then computed by xdes=xref(s) (in Cartesian space) or qdes=qref(s) (in joint space). In this way, the tracking controller410provides new desired joint positions qdeswhich immediately reflect any obstacle-avoidance robot joint speed reductions commanded by the online velocity modification module420. This immediate adjustment by the tracking controller410causes the commanded robot motions qcmdto faithfully follow the target reference path qref.

The block diagram illustration ofFIG.4also serves as a flowchart diagram illustration of a method for adaptive robot velocity modification, according to the present disclosure. That is, the method includes providing workspace obstacle data, using the obstacle data and a reference path to determine if velocity attenuation is needed for obstacle avoidance including computing the slowdown ratio ds, computing a commanded robot motion using the slowdown ratio and a desired motion, using the slowdown ratio and the reference path to compute the desired motion for the next control cycle (feedback loop440), and providing the commanded robot motion to the robot system.

In the system and method ofFIG.4, the parameterization of the sequence of interpolation points into a continuous path, as depicted inFIG.5, is optional. This parameterization may be implicitly performed in the robot controller's motion system in which, in some embodiments discussed below, the online velocity modification calculations are embedded. In other embodiments, the parameterization shown inFIG.5is an explicit step performed on a computer other than the robot controller. In all embodiments, the input of a reference path (depicting a planned task motion for the robot) is required.

FIG.6is an illustration of a two-robot system with intersecting paths, with simulation results showing how collision is prevented when the online velocity modification technique ofFIG.4is implemented in one of the robots, according to an embodiment of the present disclosure. A robot610and a robot630operate in a shared workspace600depicted by a three dimensional (3D) Cartesian grid inFIG.6. The robot610is programmed to follow a path620, one way, from a start point622to an end point624. The robot630is programmed to follow a path640, both ways, from a start point642to an end point644and back to the start point642.

In the absence of any collision avoidance technology, the robots610and630would collide if both begin their tasks at the same time, as there is an obvious overlap of their operating envelopes around the area where the paths620and640cross. It is inefficient to simply program the robots so that one robot completes its task and then the other robot begins. Thus, there is a need for automatic velocity adjustment in the case of impending collision.

When the robot610is configured with the motion optimization/velocity modification system ofFIG.4, both robots begin to track their tool center point along their respective paths, and as the robot610approaches a point626, the robot610detects the robot630(with its tool center at about a point646) ahead in its path. The robot610thus slows and possibly stops with its tool center at around the point626, while the robot630continues outbound and back along the path640. When the robot630reaches about the point646on the return motion, the robot610resumes motion along the path620toward the end point624. The net result is that robot collision is avoided, and the robot610can at least partially complete its task while the robot630is in its path. Other scenarios can easily be envisioned, where the timing is such that one robot simply has to slow down a little bit while the other robot clears the overlap area, and the disclosed the motion optimization/velocity modification technique maintains very high efficiency while preventing collisions. The scenarios outlined inFIG.6deal with robot-to-robot collisions. The disclosed velocity modification technique is equally adept and handling any other type of moving obstacle.

FIG.4showed a block diagram of the motion optimization/velocity modification system of the present disclosure at a high level, and the ensuing discussion described the details of the velocity modification calculations and the slowdown ratio feedback and usage to keep the actual path on the reference path. Two different detailed implementation embodiments are shown in the following figures, along with a method of determining when to trigger the collision avoidance velocity modification routine.

FIG.7is a block diagram illustration of a first implementation architecture700of an online velocity modification control structure, according to an embodiment of the present disclosure. The architecture ofFIG.7mirrors that ofFIG.4, where a tracking controller710computes desired robot joint position and velocity vectors, (qdesand {dot over (q)}des, where {dot over (q)}desis either provided directly or computed by differencing qdesat current time step from previous time step) based on the reference path input qref, and provides the desired joint position and velocity vector data to an online velocity modification module720. A perception module730(one or more sensors that can detect obstacle presence and movement—such as cameras, lidars, motion capture systems, or proximity sensors) provides obstacle position and velocity data (pobsand vobs) for any obstacles found in the camera images or sensor data. Alternatively, in multi-robot systems, the obstacle data could be state data about another robot provided by that other robot's controller, as discussed further with respect toFIG.8.

The online velocity modification module720computes an amount of velocity modification (“reduced speed limit”) necessary based on any obstacles identified in the obstacle data. If no obstacles are present in the workspace, then the robot performs its task using the original planned motion path and velocity. The online velocity modification module720provides feedback of the slowdown ratio ds (0≤ds≤1) to the tracking controller710, and the online velocity modification module720provides commanded robot joint positions and velocities (qcmdand {dot over (q)}cmd) to a robot controller750. In the architecture700ofFIG.7, the tracking controller710and the online velocity modification module720are implemented upstream of the controller750, such as in a separate computer740. The computer740could also perform some of the perception function—for example, the camera(s) could provide raw images to the computer740, which would then process the images to determine the presence (and position and velocity) of any obstacles. The robot controller750provides joint motion commands to a robot760, and the robot760provides joint position feedback qactfrom joint encoders back to the controller750so that the controller750knows the exact position of the robot joints at all times, as known in the art.

The architecture700ofFIG.7has been implemented in simulations which confirm that the robot760operates at full planned speed in the absence of any workspace obstacles, slows down as necessary to avoid collisions with obstacles, and the tool center point faithfully tracks the reference path, even for curved paths when significant slowdowns are enforced.

FIG.8is a block diagram illustration of an architecture800, a second implementation architecture of an online velocity modification control structure, according to an embodiment of the present disclosure. The architecture800ofFIG.8is designed for straightforward implementation in existing robot controller systems. A robot controller810has a motion control module820which computes commanded robot joint motions, (qcmd, and also {dot over (q)}cmdeither directly or implicitly as discussed above) based on a reference path input qref. The motion control module820includes internal modules which perform computations required to provide the commanded robot joint motions (qcmd), including computing an intermediate variable equivalent to the desired robot joint motions (qdes).

A perception module840(one or more sensors that can detect obstacle presence and movement—such as cameras, lidars, motion capture systems, or proximity sensors) provides obstacle position and velocity data (pobsand vobs) for any obstacles found in the camera images or sensor data. Alternatively, as described above for the system ofFIG.7, the obstacle data could be state data about another robot provided by that other robot's controller842. That is, in a multi-robot system such as shown inFIG.6, each robot may be an obstacle to the other. Thus, in a multi-robot system, the perception module840may be eliminated (if no other obstacles are expected in the robot workspace), and instead each robot's position and velocity data provided to the other robot's controller to be used in computing obstacle data. The obstacle data (whether from the perception module840or from the other robot's controller842, or both) is provided to an online velocity modification module850which computes an amount of velocity modification (“reduced speed limit”) necessary based on any obstacles identified in the obstacle data. If no obstacles are present in the workspace, then the robot performs its task using the original planned motion path and velocity. The online velocity modification module850is preferably implemented on a processor within the robot controller810(dashed outline), as an additional software algorithm.

The online velocity modification module850receives the desired robot motions qdesfrom the motion control module820and, along with the obstacle data, computes the slowdown ratio ds in the manner discussed previously. The online velocity modification module850provides the slowdown ratio ds (0≤ds≤1) to the motion control module820where it is used to compute the commanded robot motions qcmdwhich are revised from the desired robot motions qdesif necessary based on any slowdown indicated in ds. The slowdown ratio ds is also used by the motion control module820to slow down the desired robot motions qdescomputed from qrefif necessary based on the value of ds. The motion control module820provides the commanded robot joint motions (qcmdand, either directly or implicitly, {dot over (q)}cmd) to a servo control module860, which is a known element of the controller810. The servo control module860of the controller810provides joint motion commands to a robot870, and the robot870provides joint position feedback qactfrom joint encoders back to the robot controller810so that the servo control module860knows the exact position of the robot joints at all times. The joint position feedback qactis also provided to the online velocity modification module850, so that the online velocity modification module850knows the actual position and velocity of the robot870for computing robot-obstacle distance and relative velocity.

The architecture800ofFIG.8has been implemented in an actual physical robot-controller system, with the online velocity modification module850programmed on a processor in the controller as described above. This prototype system exhibited the desired behavior—including the robot operating at full planned speed in the absence of any workspace obstacles, and the robot slowing down as necessary to avoid collisions with obstacles, while the tool center point faithfully tracked the reference path, even for curved paths when significant slowdowns were enforced. Experimental results are discussed further below.

The preceding discussion ofFIGS.4-8describes how the online velocity modification module performs an optimization computation to determine a robot slowdown ratio based on the presence of workspace obstacles, and how the slowdown ratio ds is used to modify robot velocity if necessary while faithfully following the planned reference path of the tool center. An additional aspect of the present disclosure is a technique for determining when to “turn on” the velocity modification optimization computation, so that the online velocity modification computation is not performed in situations when robot-obstacle conflicts are not likely or possible.

FIG.9is a flowchart diagram900of a method for triggering the online velocity modification calculation based on robot-obstacle distance and relative velocity, according to an embodiment of the present disclosure. In the method ofFIG.9, both robot-obstacle distance (minimum distance between the obstacle and any part of the robot) and robot-obstacle relative velocity (rate of change of minimum distance) are evaluated, and the velocity modification calculations are performed only when both the distance and velocity meet predefined criteria. The method ofFIG.9is performed in the online velocity modification module720ofFIG.7or the online velocity modification module850ofFIG.8.

Upon entering the online velocity modification (OVM) module, at decision diamond902, it is determined whether the current robot-obstacle minimum distance dobsis less than or equal to a predetermined threshold distance dthresh. The threshold distance can be defined based on robot maximum working speed and other factors, such as whether people may be present within the workspace. If the current robot-obstacle minimum distance is greater than the threshold distance, then the process moves to box904where the slowdown ratio is set to ds=1 and the OVM optimization calculations are not performed. If the current robot-obstacle minimum distance is less than or equal to the threshold distance at the decision diamond902, then the process moves to decision diamond906.

At the decision diamond906, it is determined whether the relative velocity vrelof the obstacle with respect to the robot is less than or equal to zero. The robot-obstacle relative velocity can be determined from the rate of change of the minimum robot-obstacle distance from one time step to the next. If the robot-obstacle relative velocity is greater than zero, this means that the obstacle is moving away from the robot (or the robot is moving away from the obstacle, or a combination of the two), and because the distance is increasing, a collision is not possible under the current conditions. When the robot-obstacle relative velocity is greater than zero, the process moves to the box904where the slowdown ratio is set to ds=1 and the OVM calculations are not performed.

If the robot-obstacle relative velocity is less than or equal to zero (and the distance is less than the threshold from the decision diamond902), then at box908the robot stopping time tstopis computed based on robot-obstacle distance as follows:

tstop=min⁡(do⁢b⁢s❘"\[LeftBracketingBar]"νr⁢e⁢l❘"\[RightBracketingBar]",do⁢b⁢s❘"\[LeftBracketingBar]"νs⁢a⁢f⁢e❘"\[RightBracketingBar]")(9)
Where vsafeis a speed magnitude which is used to avoid a numerical error when vrel=0.

The stopping time tstopis then used in Equation (5) to determine a joint velocity limit as discussed above. The online velocity modification optimization computations are then performed at box910using Equations (6)-(8) as discussed above, resulting in a slowdown ratio having a value 0≤ds≤1. The online velocity modification module exits either from the box904(ds=1) or from the box910(value of ds computed).

It is known in the art to perform robot collision avoidance computations only when workspace obstacles are within a certain distance of the robot. However, by evaluating the robot-obstacle relative velocity along with the minimum distance as shown inFIG.9, the presently disclosed technique avoids performing the computations and potentially slowing down the robot in situations where the obstacle is moving away from the robot (and/or the robot is moving away from the obstacle), when a collision is not possible even though the robot-obstacle distance may be small.

Many simulations and real world experiments have been performed which validate the effectiveness of the online velocity modification techniques discussed above. The simulations include multi-robot workspace scenarios such as the one shown inFIG.6, and the real world experiments include a human and a hand-held obstacle moving around the workspace of a robot which is programmed to follow both linear and curved path segments. In all cases, data analysis shows that a slowdown (ds<1) is commanded only when the robot-obstacle distance is less than the threshold and the robot-obstacle relative velocity is decreasing, the value of the slowdown ratio from the online velocity modification calculations is as expected based on robot-obstacle distance, and the actual tool center point path follows the reference tool center point path even in curved portions of the path when the robot slows down in response to ds<1. Several examples of the simulation and experimental results are shown in later figures and discussed below.

In the earlier discussion ofFIG.6, it was described how collisions are prevented in a two-robot system with intersecting paths when the online velocity modification technique is implemented in one of the robots. It is preferable to implement the online velocity modification technique in all robots of a multi-robot system, so that overall efficiency can be maximized (number and duration of slowdowns minimized). However, in order to do this, a robot priority or precedence order must be established in real time based on workspace conditions, and a sequential process of calculating the slowdown ratio ds for each robot in priority order must be followed. This technique is discussed below.

When two or more robots are operating in a shared workspace with the operational envelopes of the robots overlapping, it is possible that collisions could occur. Such collisions can be avoided by pre-programming the robots to strictly follow a synchronized sequence of movements which prevents two robots from being in the same place at the same time. However, some types of tasks dictate that each of the robots operates at its own pace, which prevents a strict synchronization of movements. In such cases, a potential overlap region can be identified, and the distance of each robot from the overlap region (at a current time step or robot control cycle) can be used to establish a priority order. This technique is described below.

FIG.10is a flowchart diagram1000of a method for establishing priority of each robot in a multi-robot system, and performing the online velocity modification calculation based on the priority, according to an embodiment of the present disclosure.FIG.11is an illustration of a two-robot system1100with intersecting paths, with simulation results showing how the OVM priority logic ofFIG.10affects a first motion scenario, according to an embodiment of the present disclosure.FIG.12is an illustration of the two-robot system1100, with simulation results showing how the OVM priority logic ofFIG.10affects a second motion scenario, according to an embodiment of the present disclosure.

The process begins for a particular time step (robot control cycle) at box1002, where a potential overlap region of robot motion is identified. In a workspace1100ofFIG.11, an overlap region1102is identified involving a robot1110and a robot1130. The overlap region may be a two-dimensional area (in top view, for example), or the overlap region may be a three-dimensional volume. At box1004, a distance from each robot's current position to the overlap region is calculated. The distance calculation may be formulated to correspond with the nature of the overlap region. For example, the distance could be calculated as the distance a robot's tool center point has to travel in order to enter the 2D overlap region projected vertically. Or the distance could be calculated as an actual 3D distance for any part of a robot to enter a 3D overlap volume. These calculations can be defined to suit a particular application.

At box1006, a priority order for the robots in the system is defined by sorting the robots based on distance (in one embodiment) from the overlap region—where the robot closest to the overlap region has top/highest priority (1), and the robot furthest from the overlap region has the lowest priority. The idea behind this priority sorting is to allow the closest robot to pass through the overlap region as quickly as possible, while the other robots pass through the overlap region in succession. In many cases, it is possible that the top priority robot will not have to slow down at all, and successive robots may only have to slow down a small amount.

In an alternate embodiment, instead of distance to the overlap region, a time to reach the overlap region for each robot may be calculated at the box1004, and the time value used to establish robot priority order at the box1006. Time, rather than distance, may be used in applications where one robot in the system has a planned speed or path length which is much different than one or more other robots in the system. In still other embodiments, acceleration/deceleration capability of the robots may be considered in determining priority, where a robot with the least acceleration/deceleration capability (such as a largest robot with greatest inertia) may be assigned the highest priority. Other factors may also be considered, and the priority may in fact be assigned based on user preference, or using a user-defined formula including constants (such as robot capabilities) and variables (such as a distance to overlap region at a particular control cycle).

The output of the box1006is a priority order of the robots for the particular robot control cycle which is currently being evaluated. InFIG.11, by way of example, it may be that the robot1130has highest priority and the robot1110has lowest priority. For the following discussion, a 3-robot system is used as an example, and the priority order for the 3-robot system is assumed to be PO=[R2, R1, R3], which indicates that the robot R2has highest priority (1), the robot R1has second-highest priority (2), and the robot R3has lowest priority (3). Again, these priorities only apply to a particular portion of the robots' operations; at a later time, the priority order may be entirely different based on conditions at that time.

Still continuing for the particular robot control cycle, calculations of the slowdown ratio for each robot begin at box1008with an initiation, where a priority order counter is initialized (i=1), and preliminary slowdown ratio values are set (ds1=dsmax=1). That is, the slowdown ratio ds for the robot having priority 1 (robot R2) is set to a preliminary value of one, and a parameter dsmaxis also set to a value of one.

At decision diamond1010, it is determined whether all robots (all three in this example) have had their ds value calculated. If not, then at box1012, the robot is selected which has the priority order of the current priority order counter, which is robot R2because the counter is still i=1. The slowdown ratio ds is then computed for R2using the OVM calculations discussed above (evaluate robot-obstacle distance and velocity, then compute ds from tstopand optimization computation). Even though the robot R2has the highest priority, ds is still computed, because there may be other obstacles requiring that the robot R2slow down. The ds value for R2is then set as the minimum of the value just computed by OVM and the previously-set value of dsmax. That is, for robot R2, ds2=min(ds, dsmax). For the highest priority robot (R2), dsmax=1 was previously set at the box1008. Therefore, ds2will be equal to the value of ds just computed by OVM, which could be as high as ds=1.

In the preceding discussion of the box1012, the value of ds was computed for the highest priority (i=1) robot R2. Then at box1014, the counter value is incremented (i=i+1), and the maximum possible value of ds for the next priority robot is set to the ds value for the robot just calculated. That is, dsmax=dsj, which establishes that each robot in descending priority order can have a ds value which is no higher than that of the robot having immediately higher priority. The process then loops back to the decision diamond1010, where it is determined whether all robots' ds values have been updated.

Continuing with the 3-robot system example, only the top priority robot R2has been computed thus far. The process therefore continues to the box1012, where robot having priority i=2 is now selected (from the priority order established at the box1006), which is robot R1. The value of ds1is then computed for the robot R1, and can be no higher than the value dsmaxestablished for the previous robot (ds2). At the box1014, the priority order counter is again incremented (i=i+1), and the maximum possible value of ds for the next priority robot is set to the ds value for the robot just calculated.

The process then loops back to the decision diamond1010, and proceeds to the box1012where ds is calculated for the next lower priority (i=3) robot R3. When the process again loops back to the decision diamond1010, it is determined that all three robots have had a ds value calculated for the current control cycle, and at box1016the values of dsjfor all robots (ds2for top priority robot R2; ds1for second priority robot R1; etc.) are output for usage as discussed above (feedback to the tracking controller for each robot, or usage by the interpolation module). The process then loops back to the box1002for the next control cycle.

FIG.11depicts the robot1110having a one-way planned path1112, and the robot1130having a two-way (outbound and return) planned path1132. InFIG.11, the scenario is that the robot1130takes highest priority by virtue of being nearest to or soonest to arrive at the overlap region1102. Therefore, the first thing that happens is that the robot1110begins moving along its planned path1112and the robot1130begins moving along its planned path1132. These movements happen simultaneously, and are both depicted with an arrow labelled {circle around (1)} indicating that they happen first. When the robot1110(which is lower priority) nears a point1114, the robot1110must slow down, and may stop near the point1114to allow the higher priority robot1130to complete its outbound path (arrow {circle around (1)}) and its return path (arrow {circle around (2)}). When the robot1130has nearly completed its return path (arrow {circle around (2)}), such that the robot1130is out of the way of the robot1110and/or is moving away from the robot1110, only then can the robot1110complete its path as indicated by the dashed arrow {circle around (3)}.

FIG.12depicts the same workspace1100with the robots1110and1130having the same planned paths (1112and1132, respectively) and the same overlap region1102, as inFIG.11. InFIG.12, the scenario is that the robot1110takes highest priority by virtue of being nearest to or soonest to arrive at the overlap region1102. Therefore, the first thing that happens is that the robot1110begins moving along its planned path1112and the robot1130begins moving along its planned path1132. These movements happen simultaneously, and are both depicted with an arrow labelled {circle around (1)} indicating that they happen first. The robot1110completes the entire planned path1112without interruption, because it is highest in priority. Meanwhile, when the robot1130(which is lower priority) nears a point1234, the robot1130must slow down, and may stop near the point1234to allow the higher priority robot1110to pass through the overlap region1102. When the robot1110has nearly completed its path (arrow {circle around (1)}), such that the robot1110is out of the way of the robot1130and/or is moving away from the robot1130, only then can the robot1130complete its outbound path (dashed arrow {circle around (2)}) and then its return path (arrow {circle around (3)}).

The robots1110and1130ofFIGS.11-12may be operating independently of one another, such that their motions cannot be permanently synchronized for each task. This would be the case when the robots are performing tasks which depend on the availability of inbound parts, or depend on the status of another machine, for example. This situation makes the presently disclosed techniques—adaptively determining robot priority in real time, and performing velocity modification as necessary to prevent collisions—extremely beneficial.

FIG.13is a graph1300of an actual tool center point path superimposed on a reference path, depicting how the actual tool center point path follows the reference path, even in tight curves and when the robot velocity is reduced to avoid obstacles, according to an embodiment of the present disclosure. The data plotted on the graph1300is from physical experiments conducted using the online velocity modification techniques discussed above, programmed onto a robot controller controlling a robot as inFIG.8.

The graph1300represents a workspace having an x dimension on a horizontal axis1310and a y dimension on a vertical axis1312. The units of the axes1310and1312are in millimeters (mm). The z dimension is not shown and is not significant to the discussion, as the robot in the experiment was programmed for the tool center point to follow a sort of zig-zag shape in an x-y plane, where the shape moves back and forth in the y direction a few times while steadily moving in the x direction, then looping back around to the starting point. This tool center point path is depicted by a trace1320, which is both the actual tool center point path and the reference (programmed) path; the actual and reference paths are so identical that they cannot be distinguished in the graph1300.

Even when zooming in to one of the corners of the path, as in a second graph1330, the actual and reference paths are indistinguishable in a trace1340, where the trace1340is the portion of the trace1320indicated in oval1322. The high fidelity path following is true even though significant and repeated robot slowdowns were commanded by the online velocity modification module during the robot motions. A third graph1350shows the speed override percentage (the slowdown ratio ds converted to a percentage) vs. time for the duration of the path tracing of the graphs1300and1330. The slowdowns and stops for collision avoidance are readily apparent on the graph1350. The dashed trace on the graph1350indicates the value of the speed override percentage (which is the slowdown ratio ds converted to a percentage) as computed by the OVM module, while the solid trace indicates the value of the speed override percentage after being passed through a low-pass filter.

Taken together, the graphs onFIG.13illustrate that the online velocity modification techniques of the present disclosure are highly effective at maintaining a programmed (reference) tool center point path, while attenuating robot speed as necessary to avoid close encounters with workspace obstacles.

FIG.14is a graph set plotting robot-obstacle distance and relative velocity vs. time, and also showing the resultant OVM speed override percentage, or slowdown ratio, according to an embodiment of the present disclosure. A graph1410plots minimum robot-obstacle distance vs. time. A curve1412indicates the value of the minimum distance as it increases, decreases and increases again during a portion of an experiment using an actual robot and controller programmed with the online velocity modification technique. In a shaded section1414of the graph1410, the minimum robot-obstacle distance is greater than the minimum distance threshold (0.5 m) which was used as a trigger for the online velocity modification calculation as shown inFIG.9. In a section1416, the minimum robot-obstacle distance is less than the minimum distance threshold. In a shaded section1418, the minimum robot-obstacle distance is again greater than the minimum distance threshold. Thus, in the shaded sections1414and1418, the minimum robot-obstacle distance indicates that the online velocity modification calculation does not need to be performed.

A graph1420plots robot-obstacle relative velocity vs. time. A curve1422indicates the value of the relative velocity as it varies throughout a portion of the experiment using the actual robot and controller programmed with the online velocity modification technique. The graph1420plots data from the same experimental trial as the graph1410, on the same time scale. In a shaded section1424of the graph1420, the robot-obstacle relative velocity is greater than zero. In a section1426, the robot-obstacle relative velocity is less than zero. In a shaded section1428, the robot-obstacle relative velocity is again greater than zero. Thus, again referring to the method ofFIG.9, in the shaded sections1424and1428, the robot-obstacle relative velocity indicates that the online velocity modification calculation does not need to be performed.

The curve1412on the graph1410, and the curve1422on the graph1420, both exhibit what is known as zero order hold signal behavior. This is where the curves take a small horizontal step from one data point to the next. The reason for this behavior is that the robot system runs at higher frequency than the perception system (e.g., cameras). Hence, when the robot system (such as the controller750ofFIG.7, or the controller810ofFIG.8) computes new robot commands for a time step, but the camera did not provide an updated frame (no new obstacle data), the robot system treats the obstacle as being at the same position and the same velocity as in the previous time step. This phenomenon does not adversely affect robot system performance when using the online velocity modification techniques.

A graph1430plots OVM speed override percentage vs. time. The graph1430plots data from the same experimental trial as the graphs1410and1420, on the same time scale. A dashed curve1432indicates the value of the speed override percentage (which is the slowdown ratio ds converted to a percentage), as computed by the OVM module, as it varies throughout a portion of the experiment. A solid curve1434indicates the value of the speed override percentage after being passed through a low-pass filter. The low-pass filter is used to remove jerky characteristics of the speed override percentage which may appear under certain conditions, as observed at about 1.25 seconds on the graph1430. A section1436of the graph1430corresponds to a time period where the online velocity modification calculations are indicated by both the minimum distance graph1410(the section1416) and the relative velocity graph1420(the section1426). Thus, in the section1436, where the robot-obstacle minimum distance is less than the threshold and the relative velocity is less than zero, the slowdown ratio ds is computed and has a value less than one. The low-pass filtered version of the ds signal (the curve1434) is provided to the motion system in the robot controller to slow down or stop the robot, providing the desired robot-obstacle collision avoidance behavior.

The graphs ofFIG.14clearly show that the online velocity modification technique of the present disclosure is effective in commanding a robot slowdown (or stop) only as needed based on obstacle conditions in the workspace, including both robot-obstacle minimum distance and relative velocity conditions. These results were obtained and observed in experiments with a human manipulating an object in the workspace with the robot, where the robot controller was programmed with the online velocity modification techniques as shown inFIG.8.

Throughout the preceding discussion, various computers and controllers are described and implied. It is to be understood that the software applications and modules of these computers and controllers are executed on one or more electronic computing devices having a processor and a memory module. In particular, this includes a processor in each of the robot controller750and the separate computer740ofFIG.7, and the controller810ofFIG.8, along with the perception systems, as discussed above. Specifically, the processors in the controllers and the separate computer are configured to perform the online velocity modification computations for robot-obstacle collision avoidance described in detail above, including the technique for determining whether to activate the online velocity modification calculation, and the technique for determining a priority order for multi-robot systems.

While a number of exemplary aspects and embodiments of the methods and systems for robotic system dynamic velocity modification have been discussed above, those of skill in the art will recognize modifications, permutations, additions and sub-combinations thereof. It is therefore intended that the following appended claims and claims hereafter introduced are interpreted to include all such modifications, permutations, additions and sub-combinations as are within their true spirit and scope.