HK40122307B - Robust motion planning and/or control for multi-robot environments - Google Patents

Description

Robust motion planning and/or control for multi-robot environments

Cross-reference to related applications

This patent application claims priority to U.S. Patent Application No. 63/358422, filed July 5, 2022, the disclosure of which is incorporated herein by reference in its entirety for all purposes.

Technical Field

This disclosure generally relates to motion planning and operation of robots operating in a shared workspace, and to the computationally efficient generation of robust motion plans that can be executed efficiently by the robot (e.g., reducing or even eliminating collisions and unexpected shutdowns), as well as the monitoring of the actual execution of the motion plans, and optionally taking remedial measures where necessary.

Background Technology

Description of related technologies

There are many applications that use two or more robots operating in a shared workspace. For example, two or more robots can be used to perform tasks on or with one or more objects or workpieces in a shared workspace, such as tightening bolts onto a chassis, where parts of the robots may overlap within their range of motion.

Planning typically involves task planning and motion planning. For example, task planning determines the movement a robot needs to make between two poses (e.g., from a starting pose to an ending pose) in order to perform a given task. In contrast, motion planning focuses on how to move the robot between two poses.

Motion planning is a fundamental problem in robot control and robotics. It specifies the trajectory a robot should follow to transition from an initial pose, configuration, or state to a desired pose, configuration, or state, typically to complete a task without colliding with any obstacles in a shared workspace, or to reduce the likelihood of such collisions. Challenges in motion planning involve the ability to execute motion plans quickly (i.e., in real-time), potentially taking into account environmental changes (e.g., changes in the position or orientation of obstacles in a shared workspace). Further challenges include performing motion planning using relatively low-cost equipment with relatively low energy consumption and limited computing power and/or storage space (e.g., memory circuitry, such as circuitry on a processor chip).

Operating two or more robots in a shared workspace (also known as a work cell or multi-robot operation environment) presents a specific set of problems. For example, motion planning should consider and avoid situations where robots or robot attachments may interfere with each other during task execution.

One approach to operating multiple robots in a shared workspace can be called a task-level approach. Engineers can manually ensure that robots do not collide by defining areas within the shared workspace where they might collide (i.e., interference zones) and programming each robot so that only one robot is in the interference zone at any given time. For example, when the first robot begins to move into the interference zone, it sets a flag. A controller (e.g., a programmable logic controller (PLC) reads this flag and prevents other robots from moving into the interference zone until the first robot removes the flag when it exits the interference zone. This approach is intuitive and easy to understand, but it is often difficult to implement, time-consuming, and may not yield optimal results. Because this approach leaves at least one robot idle for a considerable period, it inevitably leads to low throughput, even if the idle robot could technically be performing useful work in the shared workspace.

In traditional approaches, engineering teams typically break down the problem and optimize the resulting smaller subproblems independently (e.g., assigning tasks to robots, prioritizing tasks for each robot, and performing motion planning for each robot). This involves iteratively simulating motion to ensure the robots/robot attachments don't collide, a simulation that can take hours of computation and may not yield an optimal solution. Furthermore, if modifications to the shared workspace cause a change in the actual trajectory of one of the robots/robot attachments, the entire workflow must be revalidated. Clearly, this approach is not optimal and often requires experts to go through a slow, iterative process trying to find a combination of solutions that produce good results. In any case, this approach generally cannot guarantee collision-free operation when robots operating under real-world conditions perform motion planning.

Summary of the Invention

This document describes various methods and apparatuses for generating motion plans for robots operating in a shared workspace. The motion plans include a nominal trajectory (e.g., a specified trajectory) with associated acceptable lag times, wherein conforming to the acceptable lag times during actual operation ensures collision-free operation (i.e., collisions between a robot and itself, and collisions between a robot and other robots in a robot system). For example, the nominal trajectory can represent a corresponding collision-free path. This document also describes various methods and apparatuses that monitor the robot's actual operation relative to the acceptable lag time (e.g., the actual trajectory) and optionally take one or more remedial measures as necessary (e.g., when the actual lag time approaches or exceeds a threshold, such as the corresponding acceptable lag time).

A particularly advantageous method is described in international patent application PCT/US2021/013610 (publication number WO2021150439A1), which describes a system for generating optimized multi-robot motion plans. More specifically, the motion plans are optimized by minimizing or attempting to minimize some cost function (e.g., the probability or likelihood of collisions) related to system performance. Since the motion plans specify a nominal trajectory for the robot system, each motion plan is also time-based. A nominal trajectory is a specified ordered sequence of poses, configurations, or states of each movable part of one or more robots in the robot system, and is parameterized by time (e.g., in each time unit throughout the trajectory). For example, a nominal trajectory can represent a corresponding collision-free path. Since the robot system can include multiple individual robots, the motion plans can be “multi-robot.”

A motion plan can be represented by a set of discrete robot trajectories: Trj(t) = {trj_r(t), where r ∈ {1…N}, t ∈ {0, ΔT, 2ΔT, …, T}}, where N represents the total number of robots in the robot system, ΔT represents the sample time step, and T represents the total duration of the motion plan. For a sufficiently small ΔT value, Trj(t) ensures no collisions with any of the robots in the robot system. In other words, the motion specified by a set of trajectories Trj(t) for a robot system with two or more robots will not result in self-collisions (i.e., a robot colliding with itself and with other robots in the robot system). Although collision assessments can be performed for other objects or obstacles in the shared workspace, the set of trajectories Trj(t) for the robot system is not necessarily guaranteed to be collision-free with respect to other objects or obstacles in the environment. This self-collision-free condition can be easily checked or reviewed in the simulation; and once checked or reviewed, the execution of the motion specified by the motion plan can be considered safe.

However, in practice, during the actual execution of motion plans by a physical robotic system comprising two or more robots, numerous factors can adversely affect synchronization between the robots. These factors may include, for example, signal communication, control delays, sensor noise, numerical approximation errors, etc. This can cause the actual physical robotic system to deviate from the trajectory Trj(t) specified by the motion plan. Besides this "reality gap" between the simulation environment used to generate and review one or more motion plans and the actual operation of the real physical robotic system, many other factors can also cause the robot system to deviate from the motion plan that provides a set of nominal trajectories. For example, in some cases, task execution may require more time to complete than expected; therefore, the robot may need to remain or stay in a particular location (e.g., the destination location, and thus in a particular pose, configuration, or state) for a longer period than specified in the trajectory of the motion plan. Deviating from a specific motion plan that has been reviewed and deemed safe can be dangerous and may jeopardize the safety of the robotic system.

A set of trajectories Trj(t) specified by the motion plan is referred to as a set of nominal trajectories in this document to indicate that these trajectories are specified trajectories. A single trajectory specified by the motion plan is referred to as a nominal trajectory in this document. A set of trajectories executed by the robot's actual physical motion is referred to as a set of actual trajectories in this document to distinguish them from specified or nominal trajectories. A single trajectory executed by the robot's actual physical motion is referred to as an actual trajectory in this document.

The method described herein advantageously extends the safety operating regime beyond a set of nominal trajectories or associated with one or more motion plans. For example, by calculating the neighborhood of one or more nominal trajectories of the motion plan, the robotic system is able to operate within that neighborhood without causing the self-collisions described above. For each robot to operate in a shared workspace, the maximum acceptable lag time (e.g., time delay or “hysteresis”) of one or more nominal trajectories that the robot may execute is calculated. During online execution (i.e., runtime), the actual lag time of each robot is monitored. If the actual lag time is within a defined margin or threshold, it is considered safe to continue executing the motion plan because self-collision-free movement between robots is ensured. If the actual lag time of any robot exceeds the corresponding margin or threshold, then safety is compromised because self-collision-free operation can no longer be guaranteed. Optionally, a processor-based system can select and/or take one or more remedial measures in this case.

Attached Figure Description

In the accompanying drawings, the same reference numerals identify similar elements or actions. The dimensions and relative positions of elements in the drawings are not necessarily drawn to scale. For example, the angles and shapes of various elements are not drawn to scale, and parts of such elements are arbitrarily enlarged and positioned to improve the readability of the drawings. Furthermore, the specific shapes of the elements drawn are not intended to convey any information about the actual shape of the particular element, but are chosen solely for ease of identification in the accompanying drawings.

Figure 1 is a schematic diagram of a shared workspace and a configuration optimization system for configuring robots according to an illustrated embodiment, wherein multiple robots operate in a shared workspace to perform tasks.

Figure 2 is a functional block diagram of at least a first robot and a robot control system according to at least another illustrated embodiment, wherein the robot control system is communicatively coupled to control the operation of the first robot, wherein the robot control system includes a motion planner that advantageously determines and adopts an acceptable lag time for a corresponding nominal trajectory of the robot in motion planning, and optionally monitors the actual operation of at least the first robot, compares the actual lag time with a margin or threshold (e.g., acceptable lag time), and optionally takes remedial measures if necessary.

Figure 3 illustrates a method for performing motion planning to control the operation of a robot to operate in a shared workspace according to at least one of the illustrated embodiments of a processor-based system, wherein an acceptable lag time for each robot is determined based on the nominal trajectories of other robots without taking into account the influence of lag times in the nominal trajectories of other robots, and a motion plan for a specified nominal trajectory is generated or selected, which is associated with a corresponding acceptable lag time.

Figure 4 illustrates a method for executing motion planning to control the operation of a robot that will operate in a shared workspace according to at least one of the illustrated embodiments of a processor-based system, wherein an acceptable lag time for each robot is determined based on the nominal trajectories of other robots, while taking into account the impact of the lag time in the nominal trajectories of other robots, and a motion plan for a specified nominal trajectory is generated or selected, which is associated with the corresponding acceptable lag time.

Figure 5 illustrates an operational method of a processor-based system according to at least one illustrated embodiment for generating sweep volumes for one or more trajectories of each of a plurality of robots operating in a shared workspace. Optionally, the method can be used to perform the methods of Figures 3, 4 and/or 6.

Figure 6 illustrates an operational method of a processor-based system according to at least one of the illustrated embodiments, for performing collision assessments on multiple robots and multiple trajectories of each robot, wherein the movement of a robot or a portion thereof along the trajectory is represented as a sweep volume, and the collision assessment can be used to determine acceptable hysteresis times for one or more robots operating in a shared workspace.

Figure 7 illustrates an operational method of a processor-based system according to at least one of the illustrated embodiments, for generating or selecting motion plans for one or more robots to operate in a shared workspace, based at least in part on an acceptable lag time and optionally at least in part on other criteria such as cost or cost function.

Figure 8 illustrates an operation method of a processor-based system according to at least one of the illustrated embodiments, for controlling the operation of a robot operating in a shared workspace based at least in part on an acceptable lag time.

Detailed Implementation

In the following description, certain specific details are set forth to provide a thorough understanding of the various disclosed embodiments. However, those skilled in the art will recognize that the embodiments can be implemented without one or more of these specific details, or using other methods, components, materials, etc. In other instances, well-known structures associated with computer systems, robots, actuator systems, and/or communication networks have not been shown or described in detail to avoid unnecessarily obscuring the description of the embodiments. In other instances, well-known computer vision methods and techniques for generating perceptual data and volumetric representations of one or more objects and the like have not been described in detail to avoid unnecessarily obscuring the description of the embodiments.

Unless the context otherwise requires, throughout the specification and the appended claims, the word “comprising” and its variations, such as “including” and “comprise”, shall be interpreted as having an open-ended meaning of “including, but not limited to”.

Throughout this specification, the terms "one embodiment" or "implementation," or "an example" or "an embodiment" mean that a particular feature, structure, or characteristic described in connection with that embodiment is included in at least one embodiment or at least one implementation. Therefore, the phrases "one embodiment" or "implementation," "in one embodiment," or "in an embodiment" appearing throughout this specification do not necessarily refer to the same embodiment or example. Furthermore, a particular feature, structure, or characteristic may be combined in any suitable manner in one or more embodiments or examples.

Unless otherwise expressly indicated in the content, an element whose quantity is not limited in this specification and the appended claims means that at least one of that element is present. It should also be noted that, unless otherwise expressly indicated in the content, the term "or" is generally used to include the meaning of "and/or".

As used in this specification and the appended claims, the term "optimization" and its variations mean that an improved result is being prepared, generated, or produced, or that an improved result has already been prepared, generated, or produced. These terms are used in a relative sense and do not necessarily mean that an absolutely optimal value has been prepared, generated, or produced.

As used in this specification and the appended claims, the term "workspace" or "shared workspace" refers to an operating environment in which two or more robots operate, and a portion or more of the shared workspace is the volume in which the robots may potentially collide with each other; therefore, these portions may be designated as interference areas. The operating environment may include obstacles (i.e., objects that the robots must avoid colliding with) and/or workpieces (i.e., objects that the robots need to interact with or act upon).

As used in this specification and the appended claims, the term "task" refers to a robotic task in which the robot transitions from posture A to posture B, preferably without colliding with obstacles in its environment. This task may involve grasping or releasing an object, moving or placing an object, rotating an object, or retrieving or placing an object. The transition from posture A to posture B may optionally include transitions between one or more intermediate postures.

As used in this specification and the appended claims, the terms "a trajectory" or "multiple trajectories" refer to an ordered sequence of poses, configurations, or states of one or more robots, parameterized in time, through which one or more robots, or at least a portion thereof, can move, for example, to perform a task. Trajectories are preferably represented in the configuration space (also known as C-space) of the respective robots, but alternatively, they can also be represented in a shared workspace or real-world space. Trajectories can include pauses, changes in orientation, or even reversals of one or more poses, and are not necessarily smooth in terms of orientation, time, velocity, or acceleration.

As used in this specification and the appended claims, the terms "a nominal trajectory" or "a plurality of nominal trajectories" are used to refer to one or more trajectories "designated". As used in this specification and the appended claims, the terms "a practical trajectory" or "a plurality of practical trajectories" are used to refer to one or more trajectories actually performed by the physical motion of a physical robot, and are distinguished from "a nominal trajectory" or "a plurality of nominal trajectories". In some cases, "a practical trajectory" or "a plurality of practical trajectories" may match "a nominal trajectory" or "a plurality of nominal trajectories", although in many cases there will be differences between the two, for example, because "a practical trajectory" or "a plurality of practical trajectories" lags behind "a nominal trajectory" or "a plurality of nominal trajectories" in time.

As used in this specification and the appended claims, when used or referred to in the context of a robot system comprising two or more robots, the term "self-collision" includes both: i) a collision between a robot and itself, and ii) a collision between a robot and other robots in the robot system. As used in this specification and the appended claims, when used or referred to in the context of a single robot, the term "self-collision" includes a collision between a robot and itself.

The headings and abstracts provided herein are for convenience only and do not define the scope or meaning of the embodiments.

The method described herein advantageously extends the safety of robot operation beyond that guaranteed by the nominal trajectories of the motion plan by determining an acceptable lag time that the physical robot of the robotic system can operate with, while still ensuring that such operation of the robotic system does not result in self-collision. In at least some embodiments, for each robot of the robotic system operating in a shared workspace, a maximum acceptable lag time (e.g., time delay or “lag”) is calculated for each of one or more nominal trajectories. Advantageously, this maximum acceptable lag time can be calculated within the configuration time before the robot executes the motion plan. During online execution (i.e., at runtime, after the configuration time), the actual movement of each robot is monitored, including the actual lag time of each robot along its actual trajectory. If the actual lag time value is within a defined margin or threshold (e.g., acceptable lag time), then it can be considered safe to continue executing the motion plan because self-collision-free movement can be ensured. If the robot’s actual lag time exceeds the corresponding margin or threshold, then safety is compromised because self-collision-free operation can no longer be guaranteed. For example, even if only one robot is experiencing an actual lag time exceeding a corresponding margin or threshold, the safety of all robots may be considered adversely affected. Optionally, a processor-based system can select and/or take one or more remedial measures in such cases.

Figure 1 illustrates a robot system 100 according to one illustrated embodiment, comprising multiple robots 102a, 102b, 102c (collectively referred to as 102) operating in a shared workspace 104 (also referred to as a multi-robot environment) to perform tasks. In the robot system 100 of Figure 1, as part of optimization, an acceptable lag time is determined and provided to one or more robot control systems along with an optimized motion plan including the robot's nominal trajectory.

Multiple robots can be configured to perform a set of tasks. Tasks can be specified as task plans. A task plan can specify T tasks that need to be performed by N robots. The task plan can be modeled as a vector for each robot, where the vector is an ordered list of tasks to be performed by the corresponding robot (e.g., {task 7, task 2, task 9}). The task vector can also optionally include a dwell duration, which specifies the duration for which the robot or a portion thereof should remain at a given configuration or objective. The task vector can also specify a home pose and/or other "functional poses" not directly related to task resolution (e.g., "give way" or store pose). Pose can be specified in the robot's C-space.

Robot 102 can take any of a variety of forms. Typically, robot 102 will take the form of one or more robot attachments 103 (only one is shown) and a base 105 (only one is shown) extending therefrom the robot attachments 103. Robot 102 may include one or more links having one or more joints, and actuators (e.g., electric motors, stepper motors, solenoids, pneumatic actuators, or hydraulic actuators) coupled and operable to move the links in response to control or drive signals. For example, a pneumatic actuator may include one or more pistons, cylinders, valves, gas reservoirs, and/or pressure sources (e.g., compressors, blowers). For example, a hydraulic actuator may include one or more pistons, cylinders, valves, liquid reservoirs (e.g., low-compressibility hydraulic fluid), and/or pressure sources (e.g., compressors, blowers). Robot system 100 may take the form of other forms of robot 102, such as autonomous vehicles.

The shared workspace 104 generally represents a three-dimensional space in which the robot 102 can operate and move, although in some limited embodiments, the shared workspace 104 may represent a two-dimensional space. The shared workspace 104 is a volume or region in which at least a portion of the robot 102 may overlap spatially and temporally, or where collisions would occur if motion were not controlled to avoid them. It is noteworthy that the shared workspace 104 is a physical space or volume in which the position and orientation of the physical space or volume can be conveniently represented, for example, via a Cartesian coordinate system relative to a reference frame (e.g., the reference frame represented by orthogonal axes X, Y, and Z shown in FIG. 1). It should also be noted that the reference frame of the shared workspace 104 differs from the corresponding “configuration space” or “C-space” of any robot in the robot 102, which is typically represented by a set of joint positions, orientations, or configurations in the corresponding reference frame of any robot in the robot 102.

As described herein, robot 102a or a portion thereof may constitute an obstacle when considered from the perspective of another robot 102b (i.e., when performing motion planning for another robot 102b). The shared workspace 104 may also include other obstacles such as mechanical components (e.g., conveyor belt 106), pillars, supports, walls, ceilings, floors, tables, people, and/or animals. The shared workspace 104 may also include one or more work items or workpieces that robot 102 manipulates (e.g., one or more packages, packs, fasteners, tools, items, or other objects) as part of performing a task.

Optionally, the robot system 100 includes one or more processor-based multi-robot configuration optimization systems 108 (one is shown in FIG. 1). The optional multi-robot configuration optimization system 108 receives a set of inputs 109 and generates one or more solutions as outputs 111 specifying the configuration of the robots 102. These outputs include a work cell layout (e.g., the corresponding base position and orientation of each robot 102), one or more task plans (e.g., a corresponding task plan for each of the robots 102), and optional one or more motion plans specifying or including one or more nominal trajectories of robots 102a to 102c (e.g., a corresponding nominal trajectory for each of the robots 102) and an acceptable hysteresis time for each of the nominal trajectories. One or more components of the output 111 can be optimized at least to some extent.

The optional multi-robot configuration optimization system 108 may include a population generator 110, a multi-robot environment simulator 112, a multi-robot optimization engine 114, and an acceptable lag time estimator 115.

Population generator 110 generates a set of candidate solutions 116 based on the provided input 109. Candidate solutions 116 represent possible solutions to the configuration problem (i.e., how to configure the robots 102 in the shared workspace 104 to complete a set of tasks). Any given candidate solution 116 may or may not be feasible. That is, the initial candidates may be invalid (e.g., the robots are in impossible locations, have unreachable goals, or have infeasible task plans that would lead to collisions). In some implementations, the population generator may attempt to find better candidate solutions.

The multi-robot environment simulator 112 models the workspace or multi-robot environment based on each candidate solution to determine certain properties, such as the amount of time required to complete the task, the probability or ratio of collisions when completing the task, and the feasibility or infeasibility of a particular configuration specified by the candidate solution. For example, the multi-robot environment simulator 112 may reflect these properties in terms of cost through costs generated by one or more cost functions.

For example, a cost or cost function can represent the probability or likelihood of a collision. Optionally, a cost or cost function can represent one or more of the following: acceptable lag time or "robustness," the severity of a collision, the energy consumption or loss and/or time or lag in executing or completing a motion corresponding to a nominal trajectory. In some implementations, the cost or cost function represents a determined acceptable lag time for a given nominal trajectory of a given robot. The determined acceptable lag time represents the maximum or near-maximum or optimized lag time that may result from executing the corresponding nominal trajectory while still maintaining, ensuring, or even guaranteeing at least no self-collision movement relative to itself and relative to other robots operating in a shared workspace or work cell. Thus, lag time can represent the amount of lag that can be introduced into the actual execution of or actual execution of the nominal trajectory without sacrificing a safety factor (e.g., no self-collision operation), thereby thus enhancing the robustness of the corresponding motion plan. For example, the safety factor can be checked or reviewed by simulating robot operation using the nominal trajectory. Therefore, if the robot's actual trajectory lags behind the nominal trajectory by more than a specified margin or threshold (e.g., acceptable lag time), collision-free operation can no longer be guaranteed.

The multi-robot optimization engine 114 evaluates candidate solutions at least in part based on association costs 119 and advantageously performs cooperative optimization across a set of two or more non-homogeneous parameters, for example, across two or more of the following parameters: the corresponding basic position and orientation of the robots, the assignment of tasks to the corresponding robots, the corresponding sequence of targets for the robots, and/or the corresponding trajectories or paths (e.g., collision-free trajectories or paths) between consecutive targets. Straight-line trajectories between consecutive targets may be used for simplification, but the trajectories are not necessarily straight-line trajectories.

Input 109 may include one or more static environment models representing or characterizing the operating environment or shared workspace 104, such as representing floors, walls, ceilings, columns, other obstacles, etc. The operating environment or shared workspace 104 may be represented by one or more models, such as geometric models (e.g., point clouds) representing floors, walls, ceilings, obstacles, and other objects in the operating environment. For example, the model may be represented using Cartesian coordinates.

Input 109 may include one or more robot models representing or characterizing each of the robots 102, for example, specifying geometry and kinematics, such as size or length, number of links, number of joints, joint type, range of motion, velocity limits, acceleration limits, or jerk limits. Robot 102 may be represented by one or more robot geometric models that define the geometry of a given robot 102a to 102c, for example, in terms of joints, degrees of freedom, dimensions (e.g., link lengths), and/or the corresponding C-space aspects of robots 102a to 102c.

Input 109 may include one or more sets of tasks to be performed, for example, represented as a target objective (e.g., pose, configuration, state, or position or location). For example, the task may be represented by the final pose, final configuration, or final state and/or intermediate pose, intermediate configuration, or intermediate state of the respective robots 102a to 102c. For example, pose, configuration, or state may be defined based on the joint positions and joint angles/rotations (e.g., joint pose, joint coordinates) of the respective robots 102a to 102c. Optionally, input 109 may include one or more dwell times, which specify the nominal amount of time that a robot or a part thereof should remain at a given target in order to complete a task (e.g., tightening a screw or nut, picking up and placing objects, with the aim of sorting a pile of objects into two or more different types of object piles by two or more robots operating in a common workspace).

In some implementations, one or more multi-robot configuration optimization systems 108 are capable of generating nominal trajectories for each robot to perform one or more tasks. A nominal trajectory is a “specified” trajectory, wherein each nominal trajectory comprises a time-parameterized ordered set or sequence of poses, configurations, or states of the robot between the initial or starting pose, configuration, or state of the nominal trajectory and the final or ending pose, configuration, and state of the nominal trajectory, with each pose, configuration, and state having a corresponding timing. The pose or configuration is preferably represented in the configuration space (also referred to as C-space) of the respective robot, or alternatively in the real space of the workspace or real-world space. Timing can be specified in relative terms (e.g., timing defined by a relative offset from the timing of the immediately preceding pose) or in absolute terms (e.g., timing defined by the duration from the start of trajectory execution, and, for example, relative to a common clock). In at least some cases, a nominal trajectory can specify or include one or more pauses in the motion or path of the robot or a portion thereof, and/or can specify a reversal of the motion direction or path of the robot or a portion thereof, which would otherwise not be smooth in terms of direction or time. The applicant notes that while any given trajectory can correspond to smooth motion of a robot, the term "trajectory" as used herein is not limited to this and will generally specify non-smooth motion, nor will it define a straight path for the robot or a part thereof. For example, a nominal trajectory can specify a time-parameterized set or sequence of poses through which the robot or a part thereof moves to complete a task or part of a task. Performing any given task can employ one or more nominal trajectories. As described herein, the actual motion or actual trajectory of the robot or a part thereof may deviate from the corresponding nominal trajectory, for example, due to unexpected delays in transitions between poses (e.g., due to the need to linger or remain at the target object for a longer period than expected).

Acceptable lag time estimator 115 evaluates each candidate lag time for a given nominal trajectory to determine an acceptable lag time that ensures collision-free operation even if the actual trajectory of the corresponding robot lags behind the nominal trajectory by no more than the acceptable lag time. In a preferred method, the acceptable lag time estimator 115 considers not only the effect of lag in the nominal trajectory of the given robot, but also one or more lags or effects of the corresponding nominal trajectories of other robots operating in the shared workspace. Therefore, the acceptable lag time estimator 115 is able to identify the acceptable lag time for each nominal trajectory, or in other words, the time lag, assuming the worst-case scenario where the actual trajectories of all robots operating in the shared workspace experience their respective acceptable lag times. Thus, for example, the acceptable lag time estimator 115 is able to determine the maximum acceptable lag time for each robot that still ensures collision-free operation, even if it is assumed that all robots experience their respective maximum acceptable lag times. Several methods for determining acceptable lag times are described herein.

Input 109 may optionally include a limit on the number of robots that can be configured in the shared workspace 104. Input 109 may optionally include a limit on the number of tasks or objectives that can be assigned to a given robot 102a through 102c, referred to herein as task capacity, which can be configured in the shared workspace 104. This could be used, for example, to limit the complexity of the configuration problem to ensure that the configuration problem is solvable, or solvable within an acceptable time period using available computing resources, or to preemptively eliminate certain solutions that are considered too slow because the tasks or objectives are clearly over-assigned to the given robots 102a through 102c. Input 109 may optionally include one or more bounds or constraints on variables or other parameters. Input 109 may optionally include a limit on the total number of iteration loops or the time limit for iterations, which can be used to refine candidate solutions, for example, to ensure that the configuration problem is solvable or solvable within an acceptable time period using available computing resources.

Robot system 100 may optionally include one or more robot control systems 118 (only one is shown in FIG. 1), which are communicatively coupled to control robot 102. For example, one or more robot control systems 118 may provide control signals (e.g., drive signals) to various actuators to move robot 102 to various designated targets between various configurations, thereby performing a designated task.

Robot system 100 may optionally include one or more motion planners 120 (only one is shown in Figure 1), communicatively coupled to control robot 102. As described elsewhere herein, one or more motion planners 120 generate, produce, select, or improve motion plans for robot 102, for example, taking into account small temporal deviations from motion plans provided by multi-robot optimization engine 114, or taking into account the unexpected appearance of obstacles (e.g., human entry into the operating environment or shared workspace 104). Optional motion planners 120 are operable to dynamically generate motion plans to enable robot 102 to perform tasks in the operating environment. Motion planners 120 and other configurations and/or operations may be as described in U.S. Patent Application Serial No. 62/865431, filed June 24, 2019.

In the case of a motion planner 120, the motion planner 120 may optionally be communicatively coupled to receive, for example, perceptual data provided by a perception subsystem (not shown) as input. The perceptual data represents previously unknown static and/or dynamic objects in the shared workspace 104. The perceptual data may be raw data sensed via one or more sensors (e.g., cameras, stereo cameras, time-of-flight cameras, LiDAR) and/or raw data converted by the perception subsystem into a digital representation of obstacles, which can generate a corresponding discretization of the environment in which the robot 102 will operate to perform tasks in various different scenarios.

Figure 1 illustrates various communication paths as lines between various structures, with arrows indicating the directions of input 109 and output 111 in some cases. For example, a communication path may take the form of one or more wired communication paths (e.g., electrical conductors, signal buses, or optical fibers) and/or one or more wireless communication paths (e.g., via RF or microwave radios and antennas, infrared transceivers). For example, a communication channel may include one or more transmitters, receivers, transceivers, radios, routers, wired ports (e.g., Ethernet ports), etc. The general operation of robot system 100, and particularly the general operation of one or more multi-robot configuration optimization systems 108, is shown and described in International Patent Application PCT/US2021/013610 (Publication No. WO2021/150439), and will not be repeated herein for the sake of brevity. This document describes only some of the more significant differences in operation. For example, in implementations, one or more multi-robot configuration optimization systems 108 perform the various methods described herein to determine acceptable lag times, generate or select motion plans at least in part based on the determined acceptable lag times, and/or one or more robot control systems 118 perform the various methods described herein to monitor the actual lag times of the robots executing motion plans, compare the actual lag times with margins or thresholds (e.g., acceptable lag times), and/or control the robots accordingly, for example, taking one or more remedial measures if one or more actual lag times exceed one or more acceptable lag times or related thresholds.

Figure 2 illustrates a robot system according to at least one of the illustrated embodiments, wherein a first robot control system 200a includes a first motion planner 204a that generates a first motion plan 206a to control the operation of a first robot 202, and optionally provides the first motion plan 206a and/or motion representation as obstacles to other motion planners 204b of other robot control systems 200b via at least one communication channel (indicated by approximate arrows, e.g., transmitter, receiver, transceiver, radio, router, Ethernet) to control other robots (not shown in Figure 2). In the robot control systems 200a, 200b of Figure 2, an acceptable lag time is determined by the motion planner together with the motion plans 206a, 206b, which include one or more nominal trajectories executed by one or more robots 202. Compared to robot control system 100 (Figure 1), the robot control systems 200a, 200b of Figure 2 do not necessarily perform optimization of cell layout or task planning. Furthermore, as described herein, the robot control systems 200a and 200b of Figure 2 monitor the actual lag time and, optionally, select and/or take remedial measures when necessary.

Similarly, one or more other motion planners 204b of one or more other robot control systems 200b generate one or more other motion plans 206b to control the operation of one or more other robots (not shown in FIG. 2), and optionally provide one or more other motion plans 206b to the first motion planner 204a and other motion planners 204b of one or more other robot control systems 200b. Motion planners 204a and 204b may also optionally receive motion completion information 209, indicating when the motion of each robot 202 has been completed. This allows motion planners 204a and 204b to generate new or updated motion plans based on the current or updated state of the shared workspace. For example, after the first robot 202 has completed part or all of a set of motions (which constitute part of the task performed by the first robot 102), a portion of the shared workspace may become blocked, unblocked, or otherwise made available for the second robot to perform a task. Additionally or alternatively, motion planners 204a and 204b are able to receive information (e.g., images, occupancy grids, joint positions, and joint angles/rotations) collected by various sensors or generated by other motion planners 204b, indicating when a portion of the shared workspace may become blocked, unblocked, or otherwise become available for the second robot to perform a task after the first robot 202 has completed part or all of a set of movements (which constitute part of the task performed by the first robot 102).

As described herein, motion plans 206a and 206b specify a nominal trajectory for each robot, for example, to perform one or more tasks. As previously described, a nominal trajectory is a “specified” trajectory, wherein each nominal trajectory comprises a time-parameterized ordered set or sequence of robot poses, configurations, or states, each pose, configuration, and state having a corresponding timing. The poses, configurations, or states are preferably represented in the configuration space (also known as C-space) of the respective robot.

The robot control systems 200a and 200b may be optionally communicatively coupled, for example via at least one communication channel (indicated by approximate arrows, such as a transmitter, receiver, transceiver, radio, router, or Ethernet), to optionally receive the motion planning map 208 and/or sweep volume representation 211 from one or more sources 212. According to one illustrated embodiment, the one or more sources 212 of the motion planning map 208 and/or sweep volume representation 211 may be separate from and distinct from the motion planners 204a and 204b. For example, the one or more sources 212 of the motion planning map 208 and/or sweep volume representation 211 may be one or more processor-based computer systems (e.g., server computers) that may be operated or controlled by the respective manufacturer of the robot 202 or some other entity. Motion planning graph 208 may each include a set of nodes 214 (only two are shown in Figure 2) and a set of edges 216 (only two are shown in Figure 2). Nodes 214 represent the pose, configuration, or state of the corresponding robot, and edges 216 couple the nodes of the corresponding node pair 214 and represent legal or valid transitions between poses, configurations, and states. For example, poses, configurations, or states can be defined in the robot's corresponding configuration space (C-space), representing the set of joint positions, orientations, poses, or coordinates of each joint in the joints of the corresponding robot 202. Therefore, each node 214 can represent the pose, configuration, or state of the robot 202 or a portion thereof, which is entirely defined by the pose configuration or state of the joints constituting the robot 202. Motion planning graph 208 can be determined, set up, or defined before runtime (i.e., before performing the task), such as during pre-runtime or configuration time. The optional sweep volume representation 211 represents the corresponding volume that the robot 202 or a portion thereof will occupy when performing motion or transitions between poses corresponding to the respective edges 216 of the motion planning graph 208. The optional sweep volume representation 211 can be represented in any of a variety of forms, such as, for example, voxels, Euclidean distance fields, or hierarchical structures of geometric objects. This advantageously allows some of the most computationally intensive work to be performed before runtime, when responsiveness is not of particular concern. While sweep volume is used herein, it is exemplary and can be employed with any of a variety of other collision assessment methods.

Each robot 202 may optionally include a base (not shown in Figure 2). The base may be fixed to the environment or movable within the environment (e.g., an autonomous or semi-autonomous vehicle). Each robot 202 may optionally include a set of links, joints, end-effectors or end effectors and/or actuators 218a, 218b, 218c (three shown, collectively referred to as 218) operable to move the links about the joints. This set of links, joints, end-effectors or end effectors typically includes one or more attachments to the robot that are movably coupled to the robot's base. Each robot 202 may optionally include one or more motion controllers (e.g., motor controllers) 220 (only one shown) that receive control signals (e.g., in the form of motion plan 206a) and provide drive signals to drive the actuators 218. Alternatively, the motion controller 220 may be decoupled from the robot 202 and communicatively coupled to the robot 202. For example, as described in International Patent Application PCT/US2021/013610 (Publication No. WO 2021/150439), each robot 202 is able to locate and orient itself in a shared workspace based on an optimized work cell layout.

Each robot 202 (only one robot is shown in Figure 2) may have a corresponding robot control system 200a, 200b, or alternatively, a robot control system 200a may perform motion planning for two or more robots 202. For illustrative purposes, one robot control system 200 will be described in detail. Those skilled in the art will recognize that this description can be applied to similar or even identical additional instances of other robot control systems 200.

The first robot control system 200a may include one or more processors 222, and one or more associated non-transitory computer- or processor-readable storage media, such as system memory 224a, one or more disk drives 224b, and/or memory or registers of processor 222 (not shown). The non-transitory computer- or processor-readable storage media (e.g., system memory 224a, one or more disk drives 224b) are communicatively coupled to one or more processors 222a via one or more communication channels (e.g., system bus 234). The system bus 234 can employ any known bus structure or architecture, including a memory bus with a memory controller, a peripheral bus, and/or a local bus. One or more such components may also, or alternatively, communicate with each other via one or more other communication channels, such as one or more parallel cables, serial cables, or wireless network channels capable of high-speed communication, such as Universal Serial Bus (“USB”) 3.0, Fast Peripheral Component Interconnect (PCIe), or via...

The first robot control system 200a can also be communicatively coupled to one or more remote computer systems, such as server computers (e.g., source 212), desktop computers, laptop computers, ultra-portable computers, tablet computers, smartphones, wearable computers, and/or sensors (not shown in FIG. 2). These remote computer systems are directly or indirectly communicatively coupled to the various components of the first robot control system 200a, for example, via interface 227. The remote computing systems, such as server computers (e.g., source 212), can be used to program, configure, control, or otherwise interact with the first robot control system 200a and its various components, or to input data (e.g., motion planning graph 208, sweep volume representation 211, task specification 215, or even candidate paths or nominal trajectories). This connection can be via one or more communication channels 210, such as one or more wide area networks (WANs), such as Ethernet, or the Internet using Internet Protocol. As described above, pre-run calculations can be performed by a system separate from the first robot control system 200a or the first robot 202, while runtime calculations can be performed by one or more processors 222 of the first robot control system 200a while one or more robots are performing tasks. In some embodiments, one or more of the robot control systems 200a and 200b can be mounted on the respective robot (e.g., the first robot 202).

As described above, the first robot control system 200a may include one or more processors 222 (i.e., circuitry), non-transitory storage media (e.g., system memory 224a, one or more disk drives 224b), and a system bus 234 coupling various system components. The processors 222 may be any logic processing unit, such as one or more central processing units (CPUs), digital signal processors (DSPs), graphics processing units (GPUs), field-programmable gate arrays (FPGAs), application-specific integrated circuits (ASICs), programmable logic controllers (PLCs), etc. The system memory 224a may include read-only memory (“ROM”) 226, random access memory (“RAM”) 228, flash memory 230, EEPROM (not shown), or any combination thereof. A basic input/output system (“BIOS”) 232 capable of forming a portion of the ROM 226 contains basic routines that facilitate the transfer of information between elements within the first robot control system 200a, for example, during startup.

For example, one or more disk drives 224b may be hard disk drives for reading from and writing to disks, solid-state (e.g., flash memory) drives for reading from and writing to solid-state memory, and/or optical disk drives for reading from and writing to removable optical disks. In various embodiments, the first robot control system 200a may also include any combination of such disk drives. One or more disk drives 224b may communicate with one or more processors 222 via a system bus 234. As known to those skilled in the art, one or more disk drives 224b may include an interface or controller (not shown) coupled between such drives and the system bus 234. One or more disk drives 224b and their associated computer-readable media provide the first robot control system 200a with non-volatile storage of computer- or processor-readable and/or executable instructions, data structures, program modules, and other data. Those skilled in the art will understand that other types of computer-readable media capable of storing computer-accessible data can be used, such as WORM drives, RAID drives, cassette tapes, digital video discs (“DVDs”), Bernoulli boxes, RAM, ROM, smart cards, etc.

Executable instructions and data can be stored in system memory 224a, such as operating system 236, one or more application programs 238, other application programs or modules 240, and program data 242. Application program 238 may include processor-executable instructions that cause one or more processors 222 to execute one or more of the following.

Application 238 may include processor-executable instructions that cause one or more processors 222 to receive or generate a discretized representation of a shared workspace in which robot 202 will operate, including obstacles and/or target objects or workpieces in the shared workspace, wherein planned motions of other robots may be represented as obstacles.

Application 238 may include processor-executable instructions that cause one or more processors 222 to generate motion plans 206a, 206b specifying nominal trajectories. Each of the nominal trajectories typically defines a corresponding ordered sequence of poses, configurations, or states of the robot or a part thereof, and these sequences are parameterized over time.

Application 238 may include processor-executable instructions that cause one or more processors 222 to determine a corresponding acceptable lag time for the nominal trajectory. The acceptable lag time is typically the amount of time by which the actual motion (e.g., actual trajectory) of robot 202 lags behind or differs from the nominal time specified by the corresponding nominal trajectory, ensuring at least no self-collision operation of robot 202 relative to one or more other robots operating in the shared workspace. In some embodiments, the prerequisite for no self-collision operation is that other robots do not experience any lag time during execution; however, preferably, the prerequisite for no self-collision operation is that all robots operate within the corresponding acceptable lag time of their respective nominal trajectories, thus taking into account that each robot experiences lag time while executing its respective nominal trajectory.

To generate motion plans, generate nominal trajectories, and/or determine acceptable lag times, application 238 may include processor-executable instructions that cause one or more processors 222 to invoke or otherwise perform a collision assessment. Collision assessment is commonly referred to as “collision detection” or “collision checking,” even though the assessment typically determines the probability or likelihood of a collision and usually occurs before the robot’s actual movement, rather than detecting an actual physical collision during the robot’s physical movement. Collision assessment may alternatively be referred to herein as “collision detection,” “collision checking,” or “collision analysis.”

Application 238 may include processor-executable instructions that cause one or more processors 222 to set a cost or penalty function for edges in the motion planning graph, such as reflecting a certain probability or likelihood of a collision, and optional other parameters. Application 238 may include processor-executable instructions that cause one or more processors 222 to set a cost or penalty function for a nominal trajectory, such as reflecting a corresponding acceptable lag time, and alternatively additionally reflecting a certain probability or likelihood of a collision, and optional other parameters.

Application 238 may include processor-executable instructions that cause one or more processors 222 to evaluate available nominal trajectories generated from the motion planning graph; to identify (e.g., select, determine, generate) the nominal trajectory based on, for example, a cost or cost function; and/or to identify or generate motion plans that can be executed by one or more robots to enable the robots to perform motion, for example, to further perform one or more tasks by one or more robots. Application 238 may include processor-executable instructions that cause one or more processors 222 to optionally store the determined motion plans and/or provide instructions to enable one or more robots to perform or otherwise move according to the motion plans. Motion planning and motion plan construction (e.g., collision assessment or detection, setting, updating, or adjusting costs or cost functions, for example, based at least in part on collision assessment or detection, and optionally in part on a determined acceptable lag time), as well as nominal trajectory generation, analysis or evaluation of candidate nominal trajectories (e.g., selecting between two nominal trajectories based at least in part on corresponding acceptable lag times), can be performed as described herein (e.g., with reference to the methods in Figures 3, 4, 5, 6, 7, and 8) and in a manner described by reference in the references incorporated herein. Collision detection or evaluation can employ various structures, techniques, and algorithms described herein and elsewhere.

Application 238 may also include one or more machine-readable and machine-executable instructions that cause one or more processors 222 to monitor robot motion (e.g., actual trajectories) and evaluate the actual delay or actual lag time of these actual trajectories compared to a margin or threshold (e.g., acceptable lag time or based on acceptable lag time) of the corresponding nominal trajectory. Optionally, application 238 may also include one or more machine-readable and machine-executable instructions that cause one or more processors 222 to select and/or take one or more remedial measures (e.g., causing one or more robots to decelerate, stop, and/or accelerate) when necessary (e.g., if the actual lag time is close to or exceeds the acceptable lag time).

Application 238 may also include one or more machine-readable and machine-executable instructions that optionally cause one or more processors 222 to monitor the robot in the environment to determine when a path along the actual trajectory becomes unblocked or unobstructed, and in response to the path along the actual trajectory becoming unblocked or unobstructed, cause the robot to move toward a target.

Application 238 may also additionally include one or more machine-readable and machine-executable instructions that cause one or more processors 222 to perform other operations, such as, optionally, processing sensed data (captured via sensors). Application 238 may also additionally include one or more machine-executable instructions that cause one or more processors 222 to perform various other methods described herein and by reference incorporated herein.

In various embodiments, one or more of the above operations may be performed by one or more remote processing devices or computers connected via interface 227 through communication channel 210 (e.g., network).

Although shown in Figure 2 as stored in system memory 224a, the operating system 236, application programs 238, other programs/modules 240, and program data 242 can be stored on other non-transitory computer or processor-readable media (e.g., one or more disk drives 224b).

The motion planner 204a of the first robot control system 200a may include dedicated motion planner hardware, or may be implemented wholly or partially via one or more processors 222 and processor-executable instructions stored in system memory 224a and/or one or more disk drives 224b.

The motion planner 204a may include or implement a motion converter 250, a path generator 252, a collision estimator 253, a cost setter 254, an optional path analyzer 255, a trajectory generator 256, an acceptable lag time estimator 257, and an optional nominal trajectory analyzer 258. Each of these can be implemented via logic executed by one or more processors (e.g., circuitry), such as executable software instructions, firmware instructions, hardwired logic, or any combination thereof.

Motion converter 250 converts the motion of an object (e.g., another robot, a person) into a representation of obstacles. Motion converter 250 receives motion plans 206b or other motion representations from other motion planners 204b.

The motion converter 250 may include a trajectory predictor 251 for predicting the trajectory of a transient object (e.g., another robot, another object, including, for example, a person), for example, when the trajectory of the transient object is unknown (e.g., when the object is another robot but has not received a motion plan from that other robot, or when the object is not another robot, for example, a person). For example, the trajectory predictor 251 may assume that the object will continue its existing movement in two directions, velocities, and accelerations without change. For example, the trajectory predictor 251 may consider expected changes in the object's motion or path, such as when the object's path would lead to a collision, thus expecting the object to stop or change direction, or when the object's destination is known, thus predicting that the object will stop upon reaching its destination. In at least some cases, the trajectory predictor 251 may use a learned model of the object's behavior to predict the object's trajectory. For example, the trajectory predictor 251 may extrapolate known motions and expected changes to generate a predicted trajectory for the transient object.

The motion converter 250 then optionally determines regions or volumes corresponding to known and/or one or more calculated movements of the object. For example, the motion converter is capable of converting a movement into a corresponding sweep volume, i.e., the volume swept by the corresponding robot or part thereof as it moves or transitions between postures represented by the motion plan, for example, by generating a volume representation of the robot or part thereof and projecting that volume representation along a path defined by the trajectory of the robot or part thereof. Similarly, for example, the motion converter is capable of converting a movement into a corresponding sweep volume, for example, by generating a volume representation of the object (e.g., a non-robot object such as a human) and projecting the object's volume representation along a path defined by the object's known and/or calculated trajectory. Advantageously, the motion planner 204a can simply queue obstacles (e.g., sweep volumes) and may not require determining, tracking, or indicating the timing of corresponding movements or sweep volumes. Although typically described as a motion converter 250 for first robot 202 that converts the motion of other robots (not shown in FIG. 2) into obstacles, in some embodiments, the other robot control system 200b of other robots operating in a shared workspace may provide a representation of obstacles (e.g., sweep volume) for a specific motion to the motion planner 204a of first robot 202.

Path generator 252 generates paths (e.g., ending pose, configuration, or state; or destination pose, configuration, and state) from one pose, configuration, or state (e.g., initial pose, configuration, or state) to another pose, configuration, or state. Path generator 252 is capable of determining or identifying one or more feasible paths from a start (e.g., a start node or start pose or start state) to a destination (e.g., a destination node or destination pose or destination state; an end node or end pose or end state). For example, path generator 252 is capable of determining or identifying an ordered sequence of nodes in a motion planning graph that provides a complete path from the start or current node to the destination or end node (i.e., a set of ordered nodes for which there is a corresponding valid transition between each pair of consecutive nodes in the complete path, e.g., represented by the presence of an edge coupling the nodes of that pair). As described above, each node can correspond to a corresponding pose, configuration, or state of the corresponding robot. Path generator 252 is capable of using or executing any kind of pathfinding method, technique, and/or algorithm. For example, path generator 252 can employ various methods, techniques, and/or algorithms to randomly or pseudo-randomly generate paths, selecting a sequence of nodes in a motion planning graph, wherein nodes are connected to the next node in the sequence via edges (i.e., edges representing valid transitions between the poses represented by the nodes). Path generator 252 can generate a relatively large number of candidate paths between the starting and ending nodes, thereby generating a large number of candidate paths between the starting pose, configuration, or state and the ending pose, configuration, or state. In some embodiments, path generator 252 can determine or identify feasible paths or trajectories independently of cost (e.g., a cost representing the probability or likelihood of experiencing a collision along the path), thereby creating a set of feasible paths or candidate paths that can later be evaluated at least in part based on the probability or likelihood of experiencing a collision. In other cases, path generator 252 can consider cost (e.g., a cost representing the probability or likelihood of experiencing a collision along the path) when determining or identifying feasible paths or trajectories.

The collision evaluator 253 performs a collision evaluation, also known as collision detection or collision analysis. Specifically, the collision evaluator 253 optionally performs a collision evaluation as a means of determining whether a candidate path representing a transition or motion of a given robot 202 or a portion thereof according to a nominal trajectory will result in or may result in a collision with an obstacle. As mentioned above, the motion of other robots can advantageously be represented as obstacles. Therefore, the collision evaluator 253 is able to determine whether the motion of one robot will result in or may result in a collision with another robot moving in a shared workspace.

As described herein, collision assessment, detection, or analysis can be performed not only on candidate paths, but also, additionally or alternatively, on nominal trajectories (e.g., specified trajectories), and particularly on nominal trajectories that introduce various lag times (e.g., simulated actual trajectories that may lag behind the nominal trajectory). In at least some embodiments, collision assessment, detection, or analysis of nominal trajectories introducing various lag times can be performed on each of two or more robots (e.g., pairs of robots). Collision assessment, detection, or analysis can be performed on one or more nominal trajectories for each robot in a robot pair. Collision assessment, detection, or analysis can be performed on each of those nominal trajectories (e.g., one, two, or more) that introduce zero lag time and non-zero lag time, for example, evaluating the trajectory pair for each permutation of the lag time of the trajectory pair. As described herein, collision assessment, detection, or analysis does not necessarily produce binary results, but is able to produce non-binary values, for example, representing the probability or likelihood of a collision between robot pairs caused by a path or trajectory.

In some implementations, the collision evaluator 253 performs software-based collision evaluation, detection, or analysis, for example, by performing bounding box-to-bounding box collision evaluation, detection, or analysis based on a hierarchy of geometric (e.g., sphere) representations of the volumes swept by a robot (e.g., the first robot 202) or its parts during movement. In some implementations, the collision evaluator 253 performs hardware-based collision evaluation, detection, or analysis, for example, by employing a set of dedicated hardware logic circuits to represent obstacles and streaming the representation of motion through the dedicated hardware logic circuits. In hardware-based collision evaluation, detection, or analysis, the collision detector can employ one or more configurable circuit arrays, such as one or more FPGAs 259, and can optionally generate Boolean collision evaluations.

Cost setter 254 can set, update, and/or adjust costs or cost functions associated with transitions (e.g., edges in a motion planning graph) or motions (e.g., trajectories in a motion plan). For example, cost setter 254 can set, update, and/or adjust costs or cost functions based at least in part on collision assessment, detection, or analysis. For example, cost setter 254 can set relatively high costs for edges or trajectories representing transitions between nodes or motions that cause or may cause a collision. Similarly, for example, cost setter 254 can set relatively low costs for edges or trajectories representing transitions between nodes or motions that do not cause or are unlikely to cause a collision. Setting, updating, and/or adjusting costs or cost functions can include setting, updating, or adjusting costs or cost functions logically associated with the corresponding edges or trajectories via some data structure (e.g., fields in a record, pointers in a list, tables).

In some implementations, for example, the cost setter 254 may optionally be able to set, update, or adjust the cost or cost function to at least partially represent a determined acceptable lag time for the corresponding nominal trajectory. This advantageously enables the first robot control system 200a to select a nominal trajectory from a set of available or candidate nominal trajectories for the robot to perform a given task, for example, selecting the nominal trajectory with the longest or largest determined acceptable lag time for generating a motion plan that achieves more robust operation when the robot experiences real-world conditions while performing the task.

In some implementations, additionally or alternatively, the cost setter 254 may set, update or adjust the cost or cost function to at least partially represent one or more other parameters, such as one or more of the following: the severity of the collision, energy consumption or loss and/or the time or delay of execution or completion.

The optional path analyzer 255 can use the motion planning graph 208 and the cost or cost function to determine or identify one or more suitable paths and/or select a single path (i.e., select a path, such as an optimal or optimized path). For example, the optional path analyzer 255 can identify one or more paths that meet some specified criteria (e.g., the cost is within a threshold upper limit), or even select a single path from a set of candidate feasible paths determined or identified by the path generator 252 (e.g., select a single path with the lowest cost). The identified paths can be named as suitable paths because these paths represent options with an acceptablely low probability or likelihood of collision. For example, the optional path analyzer 255 can constitute a minimum-cost path optimizer, which determines the lowest or relatively low-cost path between two nodes (therefore, the path between two poses, configurations, or states is represented by the corresponding nodes in the motion planning graph). The optional path analyzer 255 is capable of using or executing any kind of pathfinding algorithm (e.g., a minimum-cost pathfinding algorithm) taking into account the costs associated with each edge, which represent the probability or likelihood of a collision, and optionally one or more other parameters (e.g., the severity of a collision, energy consumption or loss, and/or the time or delay of execution or completion). In some implementations, cost-based optimization can be alternatively or additionally applied to the nominal trajectory to advantageously represent acceptable lag times in the cost values or cost function, as described herein, for example, in addition to the probability or likelihood of a collision, and optionally in addition to or replacing one or more of the following: the severity of a collision, energy consumption or loss, and/or the time or delay of execution or completion.

The nominal trajectory generator 256 is capable of generating a nominal trajectory that the robot can follow, for example, to complete a task. As described herein, the trajectory comprises an ordered sequence of poses, configurations, or states parameterized by time, through which the robot, or at least a portion thereof, can move, for example, to complete a task. The nominal trajectory generator 256 is capable of generating trajectories for all generated paths, or, if employing the optional path analyzer 255, generating trajectories only for selected paths or only for a single selected path.

Acceptable lag time estimator 257 evaluates various candidate lag times for a given nominal trajectory to determine an acceptable lag time that ensures collision-free operation even if the lag between the actual trajectory and the nominal trajectory of the corresponding robot does not exceed this acceptable lag time. In a preferred method, the acceptable lag time estimator 257 considers not only the lag effect in the nominal trajectory of the given robot but also the lag effect of the corresponding nominal trajectories of other robots operating in the shared workspace. Therefore, the acceptable lag time estimator 257 identifies an acceptable lag time for each nominal trajectory that assumes the worst-case scenario, where the actual trajectories of all robots operating in the shared workspace experience their respective acceptable lag times. Thus, for example, the acceptable lag time estimator 257 is able to determine the optimized (e.g., maximum) lag time for each robot to ensure collision-free operation. This article describes several methods for determining acceptable lag times, such as Method 300 (Figure 3), Method 400 (Figure 4), Method 500 (Figure 5), Method 600 (Figure 6), and/or Method 700 (Figure 7).

Optional nominal trajectory analyzer 258 can use cost or a cost function or some other objective function to determine, identify or select one or more suitable trajectories and/or determine, identify or select a single trajectory (i.e., select a trajectory, e.g., the optimal or optimized trajectory). For example, nominal trajectory analyzer 258 can determine, identify or select one or more trajectories that meet some specified criteria (e.g., cost is within a threshold upper limit), or even determine, identify or select a single trajectory (e.g., the trajectory with the lowest cost) from a set of feasible or candidate trajectories generated by trajectory generator 256 (e.g., determine, identify or select the lowest cost trajectory). For example, nominal trajectory analyzer 258 can constitute a lowest cost trajectory optimizer that determines the lowest or relatively low cost trajectory between two poses, configurations or states represented by corresponding nodes in the motion planning graph. For example, nominal trajectory analyzer 258 can select a set of trajectories that optimize robust operation for all robots, e.g., by maximizing the sum of all lag times of all robots, a given task, or a set of given tasks to be performed by a robot within a given time period. The nominal trajectory analyzer 258 is capable of using or executing any kind of algorithm, such as a minimum cost trajectory finding algorithm, while taking into account the cost associated with each trajectory, wherein the cost or cost function represents the probability or likelihood of a collision and the acceptable lag time, and optionally, one or more of the severity of the collision, energy consumption or loss, and/or the time or delay of execution or completion.

Various algorithms and structures can be used to determine the lowest-cost path and/or lowest-cost trajectory, including algorithms and structures implementing the Bellman-Ford algorithm, but other algorithms and structures can also be used, including but not limited to any process that determines the lowest-cost path or lowest-cost trajectory as a path between two nodes in motion planning graph 208, or a trajectory specified by a time-parameterized ordered sequence of poses, such that the sum of the costs or weights of its constituent edges or motions is minimized. This process improves the motion planning techniques of robots 102 (Figure 1) and 202 (Figure 2) by determining an acceptable lag time, optionally selecting a trajectory based on the determined acceptable lag time, monitoring the actual trajectory to assess whether the actual lag time is close to or exceeds a margin or threshold (e.g., acceptable lag time), and optionally selecting and/or taking remedial measures (if necessary).

Although not shown, the motion planner 204a may optionally include a look-ahead evaluator that can lead to the taking of improvement measures, such as in response to the determination of the presence or occurrence of a blocking or potential blocking condition, or the determination of a blocking or potential blocking location that will occur when the given robot and/or other robots move along a corresponding trajectory. In at least some embodiments, the look-ahead evaluator is capable of determining or selecting the type of improvement measure to be taken, for example, selecting from a set of different types of improvement measures based on one or more criteria. As described in U.S. Patent Application 63/327,917, filed April 6, 2022, one or more of various types of improvement measures (wherein referred to as remedial measures) can be implemented. For example, a new, revised, or alternative first motion plan can be generated to move the given robot to a first objective based on the analysis of a second motion plan that moves the given robot from a first objective. Furthermore, for example, a new, revised, or alternative motion plan can be generated for another robot that is or may block the given robot. Also, for example, a new order of a set of objectives can be determined or generated, the set of objectives including a first objective and at least a second objective. This can be determined or generated pseudo-randomly or based on one or more heuristics (e.g., always trying to move the first target one position downstream relative to the order of the set of targets being modified).

Although not shown, the motion planner 204a may optionally include an optional multipath analyzer capable of analyzing the total or aggregate cost associated with the trajectories of two or more motion plans (e.g., the total cost of a first motion plan and a second motion plan), as described, for example, in U.S. Patent Application 63/327,917, filed April 6, 2022. This can be used to identify combinations of motion plans with the lowest total cost. For example, the multipath analyzer may consider the total or aggregate cost of two or more options of the first motion plan in conjunction with the second motion plan, for example, using or performing any kind of lowest-cost search algorithm, while considering a cost value representing the probability of an associated collision, and optionally representing one or more of the following: acceptable lag time, collision severity, energy consumption or loss, and/or the time or delay associated with performing or completing a transition represented by the corresponding edge.

Optionally, motion planner 204a may include trimmer 260. Trimmer 260 may receive information indicating that another robot has completed motion, referred to herein as motion completion message 209. Alternatively, a flag may be set to indicate completion. In response, trimmer 260 may remove obstacles or portions of obstacles that indicate that motion has now been completed. This may allow the generation of new motion plans for a given robot, which may be more efficient, or allow a given robot to perform a task previously blocked by the motion of another robot. This method advantageously allows motion converter 250 to ignore the timing of motion when generating obstacle representations of motion, while still achieving better throughput than using other techniques. Motion planner 204a may also send signals, cues, or triggers to cause collision evaluator 253 to perform new collision detection or evaluation in the event that obstacles have been modified, to produce an updated motion planning graph, wherein the edge weights or costs associated with the edges have been modified, and to cause cost setter 254, optional path analyzer 255, and nominal trajectory analyzer 258 to update cost values and accordingly determine new or revised paths, trajectories, and/or motion plans.

The motion planner 204a may optionally include an environment converter 263 that converts the output (e.g., a digital representation of the environment) from an optional sensor 262 (e.g., a digital camera) into a representation of obstacles. Therefore, the motion planner 204a is capable of performing motion planning that takes into account transient objects in the environment (e.g., people, animals, etc.).

One or more processors, processor 222 and/or motion planner 204a, may be, or may include, any logic processing unit, such as one or more central processing units (CPUs), digital signal processors (DSPs), graphics processing units (GPUs), application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), programmable logic controllers (PLCs), etc. Non-limiting examples of commercially available computer systems include, but are not limited to: Celeron, Core, Core 2, Itanium, and Xeon series microprocessors provided by the company; K8, K10, Bulldozer, and Bobcat series microprocessors provided by Advanced Micro Devices, Inc.; A5, A6, and A7 series microprocessors provided by Apple Computer, Inc.; Snapdragon series microprocessors provided by Qualcomm Incorporated, Inc.; and SPARC series microprocessors provided by Oracle Corporation. The construction and operation of the various structures shown in Figure 2 can be implemented or employ structures, techniques, and algorithms described or similar to those described below: International Patent Application No. PCT/US2017/036880, filed June 9, 2017; International Patent Application Publication No. WO 2016/122840, filed January 5, 2016; U.S. Patent Application No. 62/616783, filed January 12, 2018; International Patent Application PCT/US2021/013610, Publication No. WO 2021/150439; and/or U.S. Patent Application No. 63/327917, filed April 6, 2022.

Although not strictly necessary, many implementations will be described in the general context of computer-executable instructions, such as program application modules, objects, or macros stored on a computer or processor-readable medium and executed by one or more computers or processors, capable of performing obstacle representation, collision assessment, and other motion planning operations.

Motion planning operations may include, but are not limited to, generating or transforming one or more or all of the following: a geometric representation of the robot based on a geometric model, task specification 215, and optional representations of the volume (e.g., swept volume) occupied by the robot in various states or poses and/or during movement between states or poses, in digital form, such as point clouds, Euclidean distance fields, data structure formats (e.g., hierarchical formats, non-hierarchical formats), and/or curves (e.g., polynomial or spline representations). Motion planning operations may optionally include, but are not limited to, generating or transforming one or more or all of the following: representing static or persistent obstacles and/or perceptual data of static or transient obstacles in digital form, such as point clouds, Euclidean distance fields, data structure formats (e.g., hierarchical formats, non-hierarchical formats), and/or curves (e.g., polynomial or spline representations).

Motion planning operations may include, but are not limited to, using various collision assessment techniques or algorithms (e.g., software-based, hardware-based) to assess, detect, determine, or predict collisions during transitions between various poses, configurations, or states of a robot, or collisions during the robot's motion between states or poses along corresponding trajectories.

In some implementations, motion planning operations may include, but are not limited to: determining one or more motion plans, motion schemes, or route maps with nominal trajectories; acceptable lag times of the nominal trajectories; storing the determined plans, motion schemes, or route maps or acceptable lag times; and/or providing plans, motion schemes, or route maps or acceptable lag times to control the operation of one or more robots, and optionally monitor the operation of the robots, and select and/or take remedial measures as necessary.

In one implementation, collision detection or evaluation is performed in response to a function call or similar process, and a Boolean value is returned to it. The collision evaluator 253 may be implemented via one or more field-programmable gate arrays (FPGAs) 259 and/or one or more application-specific integrated circuits (ASICs) to achieve low latency, relatively low power consumption, and increased amount of information that can be processed while performing collision detection.

In various implementations, these operations may be performed entirely in hardware circuitry, as software stored in a memory such as system memory 224a, or by one or more hardware processors 222a, such as one or more microprocessors, digital signal processors (DSPs), field-programmable gate arrays (FPGAs), application-specific integrated circuits (ASICs), graphics processing unit (GPU) processors, programmable logic controllers (PLCs), electrically programmable read-only memory (EEPROMs), or as a combination of hardware circuitry and software stored in memory.

The following also describe aspects of sensing, mapping, collision detection, and pathfinding that can be used in whole or in part: International Patent Application No. PCT/US2017/036880, filed June 9, 2017; International Patent Application No. WO 2016/122840, filed January 5, 2016; U.S. Patent Application No. 62/616783, filed January 12, 2018; U.S. Patent Application No. 62/856548, filed June 3, 2019; International Patent Application No. PCT/US2020/039193 (Publication No. WO 2020/263861), filed June 23, 2020; International Patent Application PCT/US2021/013610, Publication No. WO 2021/150439; and/or U.S. Patent Application No. 63/327917, filed April 6, 2022. Those skilled in the art will understand that the illustrated embodiments and other embodiments can be practiced with other system architectures and arrangements and/or other computing system architectures and arrangements, including robots, handheld devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, personal computers (“PCs”), networked PCs, microcomputers, mainframes, etc. These embodiments or examples, or portions thereof (e.g., at configuration and runtime), can be practiced in a distributed computing environment when tasks or modules are performed by a remote processing device connected via a communication network. In a distributed computing environment, program modules can reside on both local and remote storage devices or media. However, where and how certain types of information are stored is important for helping to improve motion planning.

For example, various motion planning solutions "bake in" the pathmap (i.e., motion planning graph) into a processor (e.g., FPGA 259), and each edge in the pathmap corresponds to a non-reconfigurable Boolean circuit in the processor. A problem with this design is that the processor has limited circuitry, making it impossible to store multiple or large planning graphs, and they are generally not reconfigurable for use with different robots.

One solution is to provide a reconfigurable design that stores the planning information in memory. This approach stores the information in memory rather than embedding it into the circuitry. Another approach is to use templated, reconfigurable circuitry instead of memory.

As described above, some information (e.g., robot geometry) can be captured, received, input, or provided during configuration time (i.e., before runtime). The received information can be processed during configuration time to generate processed information (e.g., motion planning graph 208), thereby accelerating operation or reducing computational complexity during runtime.

During runtime, collision detection can be performed across the entire environment (i.e., the shared workspace), including determining whether any part of the robot will or is expected to collide with another part of the robot itself, with other robots or parts thereof, with persistent or static obstacles in the environment, or with transient obstacles in the environment with unknown trajectories (e.g., people) for any pose or movement between poses.

The first robot control system 200a or some other processor-based system may include a hysteresis monitor 264 (interchangeably referred to as hysteresis time monitor 264) and/or a remedial action selector 266. The hysteresis time monitor 264 and/or the remedial action selector 266 operate during runtime (e.g., during the operation of one or more robots completing one or more tasks), monitor the operation of the robots, and select and take one or more remedial actions when necessary (e.g., slowing down or stopping one or more robots if the actual hysteresis time approaches or exceeds a margin or threshold (e.g., the corresponding acceptable hysteresis time).

The lag time monitor 264 monitors the actual lag time of the actual trajectory executed by the robot and compares the actual lag time with a margin or threshold (e.g., a margin or threshold representing or even equal to the corresponding acceptable lag time) of the corresponding nominal trajectory. As previously mentioned, while the actual trajectory may match the nominal trajectory in some cases, in many cases the actual trajectory will not match the nominal trajectory. Typically, the timing of the execution of at least some poses, configurations, states, or movements of the actual trajectory lags behind the timing of those poses, configuration states, or movements specified by the nominal trajectory. The lag time monitor 264 determines the actual lag time and whether the monitored amount of the actual lag time of the robot's actual trajectory is close to or exceeds the margin or threshold of the corresponding robot (e.g., the corresponding determined acceptable lag time of the corresponding nominal trajectory). For example, if the actual lag time of any robot operating in a shared workspace exceeds the corresponding threshold (e.g., close to or exceeds the corresponding acceptable lag time), the lag time monitor 264 can provide an indication (e.g., setting a flag, sending a message, and/or invoking the remedial action selector 266). In some implementations, the margin or threshold can be set to include a desired safety factor, for example, less than a set amount or defined percentage of a determined acceptable hysteresis time for the corresponding nominal trajectory. Thus, in some implementations, the margin or threshold can be set equal to the corresponding acceptable hysteresis time, while in other implementations, the margin or threshold can be less than (e.g., less than 10%) the corresponding acceptable hysteresis time, thereby enabling detection and remedial measures to be taken before a self-collision may occur.

The optional remedial action selector 266 selects one or more appropriate remedial actions and/or takes the selected remedial action in response to determining that the monitored lag time exceeds a corresponding threshold (e.g., a determined acceptable lag time) for any robot's corresponding trajectory. Determining that the actual lag time exceeds the corresponding threshold (e.g., a determined acceptable lag time) means that collision-free movement is no longer guaranteed, and therefore one or more remedial actions may be required.

Remedial measures can include one or more of the following: stopping the movement of one or more robots, slowing down the movement of one or more robots, and/or speeding up the movement of one or more robots. For example, it is possible to stop the movement of one, two, more, or even all robots. Furthermore, for example, the movement of one, two, more, or even all robots can be slowed down, for example, by different amounts relative to each other. Furthermore, for example, the movement of one, two, more, or even all robots can be speeded up, for example, by different amounts relative to each other. Furthermore, for example, it is possible to stop the movement of one or more robots while simultaneously slowing down the movement of one or more robots. Furthermore, for example, it is possible to stop the movement of one or more robots while simultaneously speeding up the movement of one or more robots or keeping the movement of one or more robots constant. Furthermore, for example, it is possible to slow down the movement of one or more robots while simultaneously speeding up the movement of one or more robots or keeping the movement of one or more robots constant. Furthermore, for example, it is possible to stop the movement of one or more robots while simultaneously slowing down the movement of one or more robots and simultaneously speeding up the movement of one or more robots or keeping the movement of one or more robots constant. To take at least one remedial action, the processor-based system can send instructions to one or more actuators (e.g., actuators 218a to 218c via motion controller 220) to stop, slow down, speed up, or even proceed along a corresponding trajectory specified by the corresponding nominal trajectory. For example, this can then restart the robot's movement, such as from where the movement stopped or slowed down, although in some cases this may involve returning to the starting point of the corresponding nominal trajectory and starting again from there.

Figure 3 illustrates an operation method 300 of a processor-based system according to at least one illustrated embodiment, the system performing motion planning to control robots operating in a shared workspace. According to at least one illustrated embodiment, the processor-based system includes one or more processors that execute processor-executable instructions to determine an acceptable lag time for each robot based on the nominal trajectories of other robots, without considering the impact of lag times in the nominal trajectories of other robots, and to generate or select a motion plan for a specified nominal trajectory associated with a corresponding acceptable lag time. For example, method 300 can be performed during a configuration or “pre-run” time, i.e., the time when some or all of the motion planning occurs, such as generating a nominal trajectory and/or motion plan for each robot. The configuration or “pre-run” time can occur before the robots move according to their respective nominal trajectories, for example, before the runtime, where the runtime is the time when one or more robots execute their respective motion plans. This advantageously allows some of the most computationally intensive work to be performed before the runtime, since responsiveness is not particularly of concern at this time. In at least some embodiments, method 300 or a portion thereof is executed during runtime (i.e., the time during which one or more robots are performing tasks) following a configuration time or pre-run time. In other embodiments, method 300 is executed during runtime (i.e., the time during which one or more robots are performing tasks) following a configuration time or pre-run time.

Method 300 begins at 302, for example, in response to the startup or power-on of the system or its components, the receipt of information or data, or the invocation or activation of a routine or program.

Although not shown in Figure 3, method 300 is capable of generating paths; performing collision assessments or detections or analyses on these paths; setting, updating, or adjusting the costs of the edges of the paths; and optionally performing analyses to identify or select paths based on cost (e.g., the lowest-cost path). This has been described above with reference to Figure 2, and at least some aspects of the references cited herein have been described. For the sake of brevity, these are omitted in method 300.

Optionally, in 304, at least one processor of the processor-based system generates or accesses (e.g., receives, retrieves) a set of nominal trajectories for each robot I. As previously described, a nominal trajectory is a “specified” trajectory, wherein each trajectory comprises an ordered set or sequence of robot poses, configurations, or states extending between two poses, configurations, and states (e.g., a starting pose, configuration, or state; an ending pose, configuration, or state), and includes a corresponding timing for each pose or configuration. Timing can be specified in relative terms (timing is defined by a relative offset relative to the previous pose) or absolute terms (timing is defined by a relative offset from the start of trajectory execution, e.g., relative to a common clock). The applicant notes that while any given trajectory can correspond to smooth motion of the robot, the term “trajectory” as used herein is not limited to this and will generally specify non-smooth motion, and will not define a straight path for the robot or its parts. In at least some cases, a nominal trajectory can specify or include one or more pauses in the motion of a robot or part thereof, and/or can specify changes or even reversals in the direction or path of motion of the robot or part thereof, changes in rate, velocity, and acceleration, and may not be smooth motion in terms of direction, rate, velocity, or time. For example, a nominal trajectory can specify a time-parameterized set or sequence of poses through which the robot or part thereof moves to perform a task or part of a task. Performing any given task can employ one or more nominal trajectories. As described herein, the actual motion or actual trajectory of the robot or part thereof may deviate from the corresponding nominal trajectory, for example, due to unexpected delays in transitions between poses (e.g., due to the need to linger or remain on a target object for a longer period than expected).

The nominal trajectory can be generated using any of a variety of techniques and/or algorithms, such as sample-based motion planners (SBMPs), probabilistic route maps (PRMs) or fast exploratory random trees (RRTs, RTTs), stable sparse RRTs (SSTs), and/or fast matching trees (FMTs). In at least one embodiment, the nominal trajectory can be generated via the system, method, and techniques described in International Patent Application PCT/US2021/013610 (Publication No. WO 2021150439A1). The teachings of this patent application are not limited to the generation of a particular form of nominal trajectory. Advantageously, the teachings herein include any combination or arrangement of the following: computationally efficient use of nominal trajectories to generate motion plans with associated acceptable lag times; monitoring deviations between actual motion and nominal trajectories in terms of lag time; optionally taking remedial measures for deviations exceeding the corresponding acceptable lag time; and/or optionally using determined lag times to select a set of nominal trajectories for the motion plan to enhance operational robustness.

In 306, at least one processor of the processor-based system initializes the robot counter I, for example, by setting the robot counter to an integer value of 1. In 308, at least one processor of the processor-based system executes an external iterative loop, iterating over each of two or more robots that will operate in the shared workspace, or until a stopping condition is met (e.g., determining the maximum lag time to ensure self-collision-free movement).

In 310, at least one processor of the processor-based system initializes the nominal trajectory counter J, for example, by setting the nominal trajectory counter to an integer value of 1.

In 312, at least one processor of the processor-based system executes an internal iterative loop to iterate over each nominal trajectory of a given robot, at least until a stopping condition is met.

In 314, at least one processor of the processor-based system determines the corresponding acceptable lag time of the current nominal trajectory (i.e., the current trajectory in the inner iteration loop) of the current robot (i.e., the current trajectory in the outer iteration loop). The corresponding acceptable lag time reflects the maximum acceptable delay or lag in the current nominal trajectory J, which, while the current robot executes its nominal trajectory (the corresponding acceptable lag time is introduced into the current robot's nominal trajectory), still guarantees the current robot's self-collision-free movement relative to other robots moving along their respective nominal trajectories. The acceptable lag time of a given robot I guarantees no self-collision as long as all other robots are running along their respective nominal trajectories (i.e., lag time = 0). In other words, as long as the corresponding current actual lag time of a given robot is less than or equal to (i.e., not greater than) the robot's corresponding acceptable lag time, and other robots are running along their nominal trajectories, the robots will not collide with each other (i.e., self-collision between robots is guaranteed).

In 316, at least one processor of the processor-based system determines whether each of the nominal trajectories of the given robot has been considered, for example, determining whether the nominal trajectory counter J is equal to the total number of nominal trajectories of the given robot (e.g., J = M?). If each of the nominal trajectories of the given robot has not yet been considered, control proceeds to 318, in which the nominal trajectory counter is incremented (e.g., J = J + 1), and then control returns to 312 to consider the next nominal trajectory of the given robot. If each of the nominal trajectories of the given robot has already been considered (e.g., J = M), control proceeds directly to 320.

Optionally, in 320, at least one processor of the processor-based system selects the maximum value from a determined set of acceptable lag times for a given robot.

In 322, at least one processor of the processor-based system provides one or more determined acceptable lag times (e.g., providing a maximum value of selected determined acceptable lag times) to a given robot for determining a motion plan for at least the given robot and/or controlling the operation of the given robot. For example, this can include providing one or more determined acceptable lag times to different processors, or transferring one or more determined acceptable lag times to different registers of the processors.

In step 324, at least one processor of the processor-based system determines whether each robot in the robot array has been considered, for example, whether the robot counter I is equal to the total number of robots (e.g., I = N?). If each robot has not yet been considered (e.g., I < N), control proceeds to step 326, where at least one processor of the processor-based system iterates the robot counter (e.g., I = I + 1), and then control returns to step 308 to consider the next robot. If each robot has been processed (e.g., I = N), control proceeds directly to step 328.

In 328, at least one processor in the processor-based system generates or selects a corresponding motion plan for each robot. The motion plan can be, or can represent, the robot's nominal trajectory associated with a maximum acceptable lag time. The motion plan can be, or can represent, the nominal trajectories of one or more robots. This approach advantageously enhances the robustness of the motion plans generated by motion planning, and thereby improves the operation of the robot executing the resulting motion plans.

In 330, at least one processor of the processor-based system provides a corresponding motion plan to each robot or motion controller so that the robot moves according to the corresponding motion plan.

In 332, method 300 may terminate, for example, until it is called again. Although method 300 is described as an ordered process, in many implementations, various actions or operations will be performed simultaneously or in parallel, and/or additional actions may be included and/or some actions may be omitted.

Figure 4 illustrates an operation method 400 of a processor-based system according to at least one illustrated embodiment, the system performing motion planning to control robots operating in a shared workspace. The processor-based system includes one or more processors that execute processor-executable instructions to determine an acceptable lag time for each robot based on the nominal trajectories of other robots, while simultaneously taking into account the impact of lag times in the nominal trajectories of other robots, and to generate or select a motion plan for a specified nominal trajectory associated with a corresponding acceptable lag time. For example, method 400 can be performed during a configuration or “pre-run” time, i.e., the time when some or all of the motion planning occurs, such as generating a nominal trajectory and/or motion plan for each robot. The configuration or “pre-run” time can occur before the robots move according to their respective nominal trajectories, e.g., before the runtime, where the runtime is the time when one or more robots execute their respective motion plans. This advantageously allows some of the most computationally intensive work to be performed before the runtime, since responsiveness is not particularly of concern at this time. In at least some embodiments, method 400 or a portion thereof is executed during runtime (i.e., the time during which one or more robots are performing tasks) following a configuration time or pre-run time. In other embodiments, method 400 is executed during runtime (i.e., the time during which one or more robots are performing tasks) following a configuration time or pre-run time.

Method 400 begins at 402, for example, in response to the startup or power-on of the system or its components, the receipt of information or data, or the invocation or activation of a routine or program.

Although not shown in Figure 4, method 400 is capable of generating paths; performing collision assessments or detections or analyses on these paths; setting, updating, or adjusting the costs of the edges of the paths; and optionally performing analyses to identify or select paths based on cost (e.g., the lowest-cost path). This has been described above with reference to Figure 2, and at least some aspects of the references cited herein have been described. For the sake of brevity, these are omitted in method 400.

Optionally, in 404, at least one processor of the processor-based system generates or accesses (e.g., receives, retrieves) a set of nominal trajectories for each robot (i). As previously described, a nominal trajectory is a “specified” trajectory, wherein each trajectory includes an ordered set or sequence of poses, configurations, and states of the robot between two postures, configurations, or states, and includes a corresponding timing for each posture or configuration. Timing can be specified in relative terms (timing is defined by a relative offset relative to the previous posture) or absolute terms (timing is defined by a relative offset from the start of trajectory execution, e.g., relative to a common clock). The applicant notes that while any given trajectory can correspond to smooth motion of the robot, the term “trajectory” as used herein is not limited to this and will generally specify non-smooth motion, and will not define a straight path for the robot or a part thereof. In at least some cases, a nominal trajectory can specify or include one or more pauses in the motion of the robot or a part thereof, and/or can specify changes or even reversals in the direction or path of motion of the robot or a part thereof, changes in rate, changes in velocity, and changes in acceleration, and may not be smooth motion in terms of direction, rate, velocity, or time. For example, a nominal trajectory can specify a time-parameterized, ordered set or sequence of poses through which a robot or a part of it moves to perform a task or part of a task. Performing any given task can employ one or more nominal trajectories. As described herein, the actual motion or actual trajectory of the robot or a part of it may deviate from the corresponding nominal trajectory, for example, due to unexpected delays in transitions between poses (e.g., due to the need to linger or remain on a target object for a longer period than expected).

The nominal trajectory can be generated using any of a variety of techniques and/or algorithms, such as sample-based motion planners (SBMPs), probabilistic route maps (PRMs), or fast exploratory random trees (RRTs, RTTs), stable sparse RRTs (SSTs), and/or fast matching trees (FMTs). In at least one embodiment, the nominal trajectory can be generated via the system, method, and techniques described in International Patent Application PCT/US2021/013610 (Publication No. WO 2021150439A1). The teachings of this patent application are not limited to the generation of a particular form of nominal trajectory. Advantageously, the teachings herein include any combination or arrangement of the following: computationally efficient use of nominal trajectories to generate motion plans with associated acceptable lag times; monitoring deviations between actual motion and nominal trajectories in terms of lag time; optionally taking remedial measures for deviations exceeding the corresponding acceptable number of lags; and/or optionally using determined lag times to select a set of nominal trajectories for the motion plan to enhance operational robustness.

In 406, at least one processor of the processor-based system initializes the robot counter I, for example, by setting the robot counter to an integer value of 1. In 408, at least one processor of the processor-based system executes an external iterative loop, iterating over each of two or more robots that will operate in the shared workspace, or until a stopping condition is met (e.g., determining the maximum lag time to ensure no self-collision motion between robots).

In step 410, at least one processor of the processor-based system initializes the nominal trajectory counter J, for example, by setting the nominal trajectory counter to an integer value of 1. In step 412, at least one processor of the processor-based system executes an internal iterative loop, iterating over each nominal trajectory of the given robot until at least a stopping condition is met.

In 414, at least one processor of the processor-based system determines the corresponding acceptable lag time of the current nominal trajectory (i.e., the current trajectory in the inner iteration loop) of the current robot (i.e., the current trajectory in the outer iteration loop). The corresponding acceptable lag time reflects the maximum acceptable delay or lag in the current nominal trajectory J, which, while the current robot executes the nominal trajectory (the corresponding acceptable lag time is introduced into the current robot's nominal trajectory), still guarantees the current robot's self-collision-free movement relative to other robots, each moving along its corresponding nominal trajectory (the corresponding acceptable lag time is introduced into the corresponding nominal trajectory). The acceptable lag time of a given robot I guarantees no self-collision, provided that the current actual lag time of all other robots is less than their corresponding acceptable lag time. That is, other robots do not need to run on their corresponding nominal trajectories (i.e., lag time = 0). In other words, robots will not collide with each other or with themselves as long as the corresponding current actual lag time of each of all robots operating in the shared workspace is less than or equal to (i.e., not greater than) the corresponding acceptable lag time of the robot (i.e., self-collision between robots is guaranteed).

In 416, at least one processor of the processor-based system determines whether each nominal trajectory in the given robot's nominal trajectories has been considered, for example, determining whether the nominal trajectory counter J is equal to the total number of nominal trajectories of the given robot (e.g., J = M?). If each nominal trajectory in the given robot's nominal trajectories has not yet been considered, control proceeds to 418, where the nominal trajectory counter is incremented (e.g., J = J + 1), and then control returns to 412 to consider the next nominal trajectory of the given robot. If each nominal trajectory of the given robot has already been considered (e.g., J = M), control proceeds directly to 420.

Optionally, in 420, at least one processor of the processor-based system selects the maximum value from a determined set of acceptable lag times determined for a given robot. In 422, at least one processor of the processor-based system provides one or more determined acceptable lag times (e.g., the maximum value of the selected determined acceptable lag times) to the given robot for determining at least the motion plan of the given robot and/or controlling the operation of the given robot. For example, this can include providing one or more determined acceptable lag times to different processors, or transferring one or more determined acceptable lag times to different registers of the processors.

In step 424, at least one processor of the processor-based system determines whether each robot in the robot group has been considered, for example, determining whether the robot counter I is equal to the total number of robots (e.g., I = N?). If each robot in the robot group has not yet been considered (e.g., I < N), control proceeds to step 426, where at least one processor of the processor-based system iterates the robot counter (e.g., I = I + 1), and then control returns to step 408 to consider the next robot. If each robot in the robot group has been processed (e.g., I = N), control proceeds directly to step 428.

In 428, at least one processor of the processor-based system generates or selects a corresponding motion plan for each robot. The motion plan can be, or can represent, the robot's nominal trajectory associated with a maximum acceptable lag time. The motion plan can be, or can represent, the nominal trajectories of one or more robots. This approach advantageously enhances the robustness of the motion plans generated by motion planning, and thereby improves the operation of the robot executing the resulting motion plans.

In 430, at least one processor of the processor-based system provides a corresponding motion plan to each robot or each motion controller so that the robot moves according to the corresponding motion plan.

In 432, method 400 may terminate, for example, until it is called again. Although method 400 is described as an ordered process, in many implementations, various actions or operations will be performed simultaneously or in parallel, and/or additional actions may be included and/or some actions may be omitted.

As described herein, to determine acceptable lag times, processor-based systems can perform collision assessments to determine which of a set of candidate lag times will cause or may cause a collision. One approach to collision assessment is to use the robot's sweep volume. A sweep volume represents the volume swept by the robot or a portion thereof as it moves along a given trajectory. The sweep volume is specified by the geometry and kinematics of a given robot and the start and end positions specified by the given trajectory. Notably, the sweep volume itself is not affected by the specific timing of the motion specified by the trajectory. Therefore, the sweep volume can be advantageously determined during configuration or pre-run time before the robot performs or executes a task. Thus, processor-based systems can generate sweep volumes for each of multiple (e.g., many) paths for each robot operating in a shared workspace, from which trajectories are generated for the robot. Processor-based systems can use sweep volumes to perform collision assessments. For example, for each of two or more robots, a processor-based system is capable of performing collision assessment between i) and ii), where i) represents at least a portion of a corresponding sample trajectory of the robot's nominal trajectory with at least one corresponding lag time introduced, and ii) at least a portion of a corresponding sample trajectory of each of the other robots' corresponding trajectories, wherein at least one corresponding lag time is introduced into the corresponding trajectory of each of the other robots' corresponding trajectories. In response to determining that a collision will or may occur between the robot and at least one of the other robots (e.g., expressed as a probability or likelihood), the processor-based system is capable of identifying, for one or more nominal trajectories of the robot, a corresponding lag time smaller than the corresponding lag time that leads to the determination that a collision will occur as the corresponding acceptable lag time. The acceptable lag time can represent the maximum acceptable delay in timing the pose relative to the nominal trajectory, which still guarantees that the robot's movement through the pose sequence specified by the nominal trajectory remains collision-free (or self-collision-free for the robot system) relative to the movement of the other robots' movements. Figures 5 and 6 below illustrate a non-restricted method for determining acceptable hysteresis using sweep volume.

Figure 5 illustrates an operation method 500 of a processor-based system according to at least one illustrated embodiment for generating sweep volumes for one or more trajectories of each of a plurality of robots operating in a shared workspace. According to at least one illustrated embodiment, the processor-based system includes one or more processors that execute processor-executable instructions to generate sweep volumes. For example, method 500 can be performed during a configuration or “pre-run” time, i.e., when part or all of the motion planning occurs, such as generating nominal trajectories and/or motion plans for each robot. For example, the configuration or “pre-run” time can be performed before the runtime, where the runtime is the time when one or more robots execute their respective motion plans. This advantageously allows some of the most computationally intensive work to be performed before the runtime, since responsiveness is not particularly of concern at this time. In at least some embodiments, robot configuration method 500 or a portion thereof is performed during runtime (i.e., the time when one or more robots are performing tasks) after the configuration or pre-run time. Optionally, configuration-time operations can be performed via a different processor-based system than the processor-based system performing runtime operations. For example, method 500 can be optionally used to perform the methods of Figures 3, 4 and/or 6, for example, as part of performing collision detection (see method 600, Figure 6) when determining the corresponding acceptable hysteresis times 314 (Figure 3) and 414 (Figure 4).

The method 500 for generating the swept volume begins at 502, for example, in response to the startup or power-on of the system or its components, the receipt of information or data, or the invocation or activation of a routine or program.

In step 504, at least one processor of the processor-based system initializes the robot counter I (e.g., I = 1). In step 506, at least one processor of the processor-based system executes an external robot processing loop. The external robot processing loop allows at least one processor of the processor-based system to generate a sweep volume for each of the robots that will operate in the shared workspace.

In step 508, at least one processor of the processor-based system initializes the trajectory counter J (e.g., J = 1). In step 510, at least one processor of the processor-based system executes an internal nominal trajectory processing loop. The internal nominal trajectory processing loop is nested within the external robot processing loop. The internal nominal trajectory processing loop allows at least one processor of the processor-based system to generate a corresponding sweep volume for each of one or more nominal trajectories of a given robot.

In 512, at least one processor of the processor-based system generates a swept volume representation representing the volume swept by at least a portion of a given robot I as it moves between poses of a set or sequence of poses specified by a given nominal trajectory J. Therefore, for each of two or more robots, and for each of one or more nominal trajectories, the processor-based system is capable of generating a swept volume representation representing the volume swept by at least a portion of the robot as it moves between a set of poses specified by the nominal trajectory from at least one time on the nominal trajectory to another time on the nominal trajectory. The swept volume can be generated using any of a variety of techniques, including digitally representing the robot or a portion thereof with one or more (e.g., hierarchical) data structures or point clouds, and generating a digital representation of the swept volume (e.g., a voxel set) by projecting the digital representation along a path or trajectory.

In 514, at least one processor of the processor-based system determines whether all trajectories of the given robot have been processed (e.g., J = M?). If not all trajectories of the given robot have been processed, control proceeds to 516, where the trajectory counter is incremented (e.g., J = J + 1), and control returns to the top of the internal nominal trajectory processing loop 510. If all nominal trajectories have been processed (e.g., J = M), control proceeds directly to 518.

In 518, at least one processor of the processor-based system determines whether all robots have been processed (e.g., I = N?). If not all robots have been processed, control proceeds to 520, where the robot counter is incremented (e.g., I = I + 1), and control returns to the top of the external robot processing loop 506. If all robots have been processed (e.g., I = N), control proceeds directly to 522.

In 522, method 500 may terminate, for example, until it is called again. Although method 500 is described as an ordered process, in many implementations, various actions or operations will be performed simultaneously or in parallel, and/or additional actions may be included and/or some actions may be omitted.

Figure 6 illustrates an operational method 600 of a processor-based system according to at least one illustrated embodiment for performing collision assessments on multiple robots and multiple trajectories of each robot. Method 600 is capable of performing collision assessments to identify feasible paths between start and end nodes in a motion planning graph. Additionally or alternatively, method 600 is capable of performing collision assessments to determine corresponding acceptable hysteresis times for one or more nominal trajectories of robots operating in a shared workspace. According to at least one illustrated embodiment, the processor-based system includes one or more processors that execute processor-executable instructions to perform collision assessments, for example, using swept volumes. A swept volume represents or simulates a volume swept by a robot or a portion thereof in the following processes: for example, during transitions between various poses, configurations, or states along a path represented in a motion planning graph between start and end nodes, or for example, during nominal trajectory movement along a start pose, configuration, or state to an end pose, configuration, or state. For example, method 600 is advantageously capable of using swept volumes generated via method 500. For example, method 600 can be executed during the configuration or "pre-run" time, i.e., the time when part or all of the motion planning occurs, such as generating a nominal trajectory and/or motion plan for each robot. For example, the configuration or "pre-run" time can occur before the runtime, where the runtime is the time when one or more robots execute their respective motion plans. This advantageously allows some of the most computationally intensive work to be performed before the runtime, since responsiveness is not of particular concern at this time. In at least some embodiments, robot configuration method 600 or a portion thereof is executed during the runtime (i.e., the time when one or more robots are performing a task) after the configuration or pre-run time.

The method for determining acceptable lag time 600 begins at 602, for example, in response to the startup or power-on of the system or its components, the receipt of information or data, or the invocation or activation of a routine or program.

In 604, at least one processor of the processor-based system initiates an external robot pair collision evaluation loop. The external robot pair collision evaluation loop allows at least one processor of the processor-based system to evaluate or estimate the probability or likelihood of a collision occurring between robots in each pair of robots operating in a shared workspace. The external robot pair collision evaluation loop is capable of handling collisions that may occur in every combination or arrangement of robot pairs.

In step 606, at least one processor of the processor-based system initializes the trajectory counter J (e.g., J = 1). In step 608, at least one processor of the processor-based system executes an internal nominal trajectory collision evaluation loop. The internal nominal trajectory collision evaluation loop is nested within an external robot collision evaluation loop. The internal nominal trajectory collision evaluation loop allows at least one processor of the processor-based system to evaluate or estimate the collision probability or likelihood of each of one or more nominal trajectories for a given robot pair.

In step 610, at least one processor of the processor-based system initializes a lag time counter K (e.g., K = 1). In step 612, at least one processor of the processor-based system executes a nested inner lag time collision evaluation loop. The nested inner lag time collision evaluation loop is nested within an inner nominal trajectory collision evaluation loop. The nested inner lag time collision evaluation loop allows at least one processor of the processor-based system to evaluate or estimate the effect of each of a plurality of possible lag times (i.e., candidate lag times from a set of candidate lag times) when introduced into a given nominal trajectory. Thus, for example, the introduction of a lag equal to zero and the introduction of multiple (one, two, or more) non-zero lag times can be evaluated to determine the probability or likelihood of a collision if the trajectory corresponding to the nominal trajectory with the introduced lag time is executed. Evaluation can be performed on consecutive, longer lag times.

In 614, at least one processor of the processor-based system uses the generated sweep volume to perform a collision assessment on the corresponding trajectory with introduced lag time (e.g., for zero and non-zero lag time). For example, at least one processor of the processor-based system is capable of determining whether the corresponding sweep volumes intersect, wherein the corresponding sweep volume corresponds to the volume swept by one of a pair of robots when executing a nominal trajectory with introduced zero lag time and each of a plurality of non-zero lag times. For example, for each of two or more robots, the processor-based system is capable of performing collision assessment between: i) at least a portion of a corresponding sample trajectory of a corresponding nominal trajectory of said robot, which incorporates at least one corresponding lag time (e.g., zero lag time and at least one non-zero lag time); and ii) at least a portion of each corresponding sample of the corresponding trajectory of each of the other two or more robots, wherein at least a corresponding lag time (e.g., zero lag time and at least one non-zero lag time) is incorporated into the corresponding trajectory of each of the other two or more robots. Therefore, for each robot and each nominal trajectory, it is possible to evaluate all permutations of “candidate” lag times, e.g., to identify when the probability or likelihood of a collision equals or exceeds a certain collision detection threshold.

Although the collision assessment is described based on the swept volume, the teachings of this paper are not necessarily limited to this, and the method and system can be adapted to a variety of other collision assessment or detection techniques or algorithms.

In 616, at least one processor of the processor-based system determines whether or potentially a collision is likely between a given pair of robots based on a collision assessment. In at least some embodiments, the collision assessment is capable of producing a non-binary value representing a collision chance or probability. It is possible to determine whether or potentially a collision is likely based on a non-binary value higher than a defined collision detection threshold (e.g., collision probability > 50%; collision probability > 10%; collision probability > 5%). In 617, in response to determining that a collision has been detected or is likely to occur (e.g., a collision probability equal to or greater than the collision detection threshold), the processor-based system is capable of identifying and/or storing previous hysteresis values that did not lead to a potential collision, and optionally exiting the nested inner hysteresis collision assessment loop 612, returning control to the top of the inner nominal trajectory collision assessment loop 608. Therefore, for example, in response to determining that a collision will or may occur between the robot and at least one of two or more other robots, for one or more nominal trajectories of at least one of the two or more other robots where a collision has been determined to occur, the processor-based system identifies a corresponding lag time less than the determined corresponding lag time that leads to the determination of a collision as the corresponding acceptable lag time, wherein the acceptable lag reflects the maximum acceptable delay in attitude timing relative to the nominal trajectory, which still ensures that the robot's movement through the attitude sequence specified by the corresponding nominal trajectory remains collision-free relative to the movement of the other two or more robots. In response to determining that a collision has been detected or may be detected (e.g., the collision probability is equal to or greater than a collision detection threshold), control proceeds directly to 618.

In 618, at least one processor of the processor-based system determines whether all lag times of the current trajectory of the current robot pair have been considered (e.g., K = P?). If not all lag times have been considered, the lag time counter K is incremented at 620 (e.g., K = K + 1) to select the next candidate lag time from the candidate lag time set for evaluation, and control returns to the top of the nested inner lag time collision evaluation loop 612. If all lag times have been considered, control proceeds directly to 622.

In step 622, at least one processor of the processor-based system determines whether all trajectories for a given robot pair have been processed (e.g., J = M?). If not all trajectories for the given robot pair have been processed, the trajectory counter increments in step 624 (e.g., J = J + 1), and control returns to the top of the internal nominal trajectory collision evaluation loop 608. If all nominal trajectories have been processed (e.g., J = M), control proceeds to step 626.

In step 626, at least one processor of the processor-based system determines whether there are any additional robot pairs that need to be processed. Method 600 can process each permutation of robot pairs, each permutation of the trajectories of these robot pairs, and each permutation of candidate lag times, at least until a stopping condition is met (e.g., an unacceptably high collision probability is found). Thus, for any given robot, the determined acceptable lag time (e.g., maximum lag time) can be a function of the corresponding selected trajectories of each other robot operating in the shared workspace and the determined acceptable lag time associated with those selected trajectories. In this sense, the term "maximum lag time" does not necessarily mean the absolute maximum lag time of a given robot in isolation, but can mean the maximum lag time of a given robot taking into account the trajectories and associated lag times of other robots operating in the shared workspace. If there are any additional robot pairs that need to be processed, control proceeds to step 628, where a new robot pair is selected, and control then proceeds to the top of the external robot pair collision evaluation loop. If no remaining robot pairs need to be processed, control proceeds directly to step 630.

In 630, at least one processor of the processor-based system returns a corresponding acceptable hysteresis time for one or more nominal trajectories. For example, the acceptable hysteresis time can be stored in a non-transitory processor-readable medium, such as in one or more data structures associated with the nominal trajectory. Control then proceeds to 632.

In 632, method 600 may terminate, for example, until it is called again. Although method 600 is described as an ordered process, in many implementations, various actions or operations will be performed simultaneously or in parallel, and/or additional actions may be included and/or some actions may be omitted.

To determine the appropriate acceptable lag time for a nominal trajectory, for example, a processor-based system can iterate over each of a plurality of candidate lag times in order from relatively small to relatively large candidate lag times, at least until a stopping condition is met, covering each of the plurality of times for the iterated nominal trajectory. Based on the current candidate lag time, a collision is checked between one of two or more robots and at least one of the other two or more robots. In response to determining that a collision will occur or is likely to occur between one of the two or more robots and at least one of the other two or more robots, the processor-based system can set the appropriate acceptable lag time of the nominal trajectory of the robot determined to be colliding with at least one of the other two or more robots to the closest previous candidate lag time (e.g., a lag time with a collision probability below a collision detection threshold indicating an acceptable collision risk). To check for collisions, for example, a processor-based system can determine whether the sweep volume of one robot in a robot pair intersects with the sweep volume of another robot in the robot pair. For example, a processor-based system can generate a collision indication in response to determining that the sweep volume of one robot in a robot pair intersects with the sweep volume of the other robot in the robot pair, and identifying the robot that has collided.

The following section outlines exemplary methods for determining and applying acceptable hysteresis times to provide a safety margin.

First, for example, an optimization described in International Patent Application PCT/US2021/013610 (Publication No. WO2021150439A1) is used to generate a motion plan comprising a set of nominal trajectories (Trj(t)). Therefore, for each mobile robot r in the motion plan, an acceptable lag time (e.g., a maximum safe lag value (max_lag_r)) relative to the motion plan is calculated. It is important to note that: (i) the acceptable lag time value (max_lag) for each robot r may be different (e.g., max_lag_r1 ≠ max_lag_r2); (ii) the acceptable lag time value (max_lag) depends strictly on the set of nominal trajectories Trj(t) and the relative position of the robot r; and (iii) static obstacles and static robots (if present) do not affect the acceptable lag time value (max_lag). In this example, a set of nominal trajectories Trj(t) and acceptable lag time values (max_lag_r) are calculated sequentially, preferably offline within a configured timeframe prior to runtime; however, this is not intended to limit the methods described herein. A central clock(t) is implemented during execution (e.g., online; during runtime), which is shared by all robots operating in a shared workspace. For each robot r, the lag (lag_r) relative to the nominal motion plan is calculated at a high frequency; that is, monitoring of the actual lag time is performed at a sufficiently high frequency relative to the robot's motion speed to avoid unwanted actual collisions.

Ideally, each robot r is perfectly synchronized with the motion plan, and the actual lag of the robot is zero (lag_r = 0). However, in general, one or more robots may lag behind the plan, where the current robot state is given by the trajectory trj_r(t-nΔT) and the actual lag lag_r = nΔT.

Processor-based systems monitor actual lag values to ensure the safety of the robot system. If all actual lag values are within the safety margin specified by the acceptable lag time (e.g., lag_r ≤ max_lag_r), then continuing execution is considered safe because the self-collision-free condition is ensured. Otherwise, the system's safety is considered compromised because the self-collision-free condition cannot be ensured.

To ensure the robot remains in a safe state, the system monitors actual hysteresis values and simply stops the entire robot system's movement if a safety margin is exceeded (e.g., exceeding the margin or threshold). To safely restart operation, the robot can move to any (safe) state of a set of nominal trajectories Trj(t*), and the central clock is reset to t*.

Less disruptive solutions can involve remedial or corrective actions taken when the robot is still within safe boundaries but relatively close to its limits. For example, accelerating the movement of a robot approaching its limits (increasing speed) can reduce the value of its actual lag time. This measure will directly increase the distance to the limit and improve the safety level. Alternatively, other robots can be slowed down. This measure might utilize time dilation of a central clock to maintain consistency. Hybrid measures can also be very effective.

The following pseudocode illustrates an exemplary processor-executable algorithm for determining safety margins.

To better understand this algorithm, it can be divided into four parts:

·mainloop: It spans candidate hysteresis values from 0 to L and iterates over the nominal trajectory Trj(t).

`CheckLagCollision()`: Evaluates the impact of candidate hysteresis values applied at a specific time `t`. Given a set of candidate hysteresis values for each robot in the robot group, it determines whether any robot collides at a given time `t`. In the region without hysteresis, the robot occupies the volume determined by its current pose. Currently, in the case of hysteresis, the robot can sweep the volume based on the trajectory it takes from its pose from time `t-lag` to time `t`.

·ComputeSweptVolume_r(t1, t2): Calculates the volume swept by robot r as it moves along the trajectory from time t1 to time t2 (trj_r(t1...t2)).

VolumesExcept(): Geometrically searches for the intersection of two volumes.

The main_loop() and CheckLagCollision() will be described in detail below. ComputeSweptVolume_r() and VolumesIntersect() are not described in detail because they can be implemented using many algorithms.

The input includes: trj[1...N]: a set of collision-free trajectories for N robots; ΔT: sampling time; T: the maximum duration of robot activity; ΔL: the sample lag time value for the search; and L: the maximum lag value for the search (L<=T).

The output includes: the maximum lag value max_lag[1...N] for each robot to ensure collision-free motion between robots.

The internal variables include: lag_candidate: the lag value evaluated in the current iteration; lag[1...N]: the lag value evaluated for each robot in the current iteration; lag_prev[1...N]: the lag value evaluated for each robot in the previous iteration; found_max-lag[1...N]: the boolean value at which each robot stops searching.

Figure 7 illustrates an operation method 700 of a processor-based system according to at least one illustrated embodiment, for generating or selecting motion plans for one or more robots to operate in a shared workspace, based at least in part on an acceptable lag time and optionally at least in part on other criteria. The lag time and optional other criteria can be expressed as a cost or cost function. For example, method 700 can be executed during a configuration or “pre-run” time, i.e., the time when some or all of the motion planning occurs, such as generating a nominal trajectory and/or motion plan for each robot. The configuration or “pre-run” time can precede the runtime, which is the time when one or more robots execute their respective motion plans. This advantageously allows some of the most computationally intensive work to be performed before the runtime, since responsiveness is not particularly of concern at this time. In at least some embodiments, method 700 or a portion thereof is executed during the runtime (i.e., the time when one or more robots are performing tasks) after the configuration or pre-run time.

The method for determining acceptable lag time 700 begins at 702, for example, in response to the startup or power-on of the system or its components, the receipt of information or data, or the invocation or activation of a routine or program.

Optionally, in 704, at least one processor of the processor-based system generates or accesses (e.g., receives, retrieves) the nominal trajectory for each robot. As described above, a nominal trajectory is a “specified” trajectory, wherein each trajectory includes an ordered sequence of robot poses or configurations, and a corresponding timing for each pose or configuration. As described herein, the actual motion or actual trajectory of the robot or its parts may deviate from the corresponding nominal trajectory, for example, due to unexpected delays in transitions between poses (e.g., due to the need to linger or remain on a target object for a longer period than expected).

As described above, nominal trajectories can be generated using any of a variety of techniques and/or algorithms, such as sample-based motion planners (SBMPs), probabilistic route graphs (PRMs), or fast exploratory random trees (RRTs, RTTs), stable sparse RRTs (SSTs), and/or fast matching trees (FMTs). Advantageously, the teachings of this paper include computationally efficient use of deterministic lag times to select a set of nominal trajectories for motion planning to enhance operational robustness.

In 706, at least one processor of the processor-based system initializes the robot counter I, for example, by setting the robot counter to an integer value of 1. In 708, at least one processor of the processor-based system executes an external robot processing iteration loop, performing iterations for each of two or more robots that will operate in a shared workspace, or until a stopping condition is met (e.g., determining the maximum lag time to ensure collision-free motion).

In 710, at least one processor of the processor-based system initializes the nominal trajectory counter J, for example, by setting the nominal trajectory counter to an integer value of 1. In 712, at least one processor of the processor-based system executes an internal nominal trajectory processing iteration loop, iterating over each nominal trajectory of the given robot. The internal nominal trajectory processing iteration loop 712 is nested within the external robot processing iteration loop 708.

In 714, at least one processor of the processor-based system determines the corresponding acceptable lag time for the current nominal trajectory J of the current robot I. The corresponding acceptable lag time reflects the maximum acceptable delay or lag in the current nominal trajectory J, which, at least while the current robot I (the current robot in the external robot processing iteration loop) executes the current nominal trajectory J (the current nominal trajectory in the internal current nominal trajectory iteration loop), still guarantees the current robot I's self-collision-free movement relative to its respective nominal trajectory, where the corresponding acceptable lag time is introduced into the current robot I's current nominal trajectory J. Preferably, this can be evaluated relative to the nominal trajectories of other robots that introduce various candidate lag times (e.g., zero and non-zero lag times) or even, where known, the corresponding acceptable lag time. A given acceptable lag time for robot I guarantees no self-collision, provided all other robots are operating on or within their respective nominal trajectories (i.e., lag time = 0), or all other robots are operating on or within their respective nominal trajectories that introduce the corresponding lag time. Therefore, in at least one embodiment, robots will not collide with each other as long as the corresponding current actual lag time of a given robot is less than the corresponding acceptable lag time of the robot, and other robots are running according to their nominal trajectories (ensuring no self-collision between robots). Therefore, in at least one preferred embodiment, robots will not collide with each other as long as the corresponding current actual lag time of all robots is less than the corresponding acceptable lag time of each robot (ensuring no self-collision between robots).

In 716, at least one processor of the processor-based system determines whether each of the nominal trajectories of a given robot has been considered, for example, determining whether the nominal trajectory counter J is equal to the total number of nominal trajectories of the given robot (e.g., J = M?). If each of the nominal trajectories of the given robot has not yet been considered, control proceeds to 718, where the nominal trajectory counter is incremented (e.g., J = J + 1), and control returns to the top of the internal nominal trajectory processing iteration loop 712 to consider the next nominal trajectory of the given robot I. If each of the nominal trajectories of the given robot I has already been considered (e.g., J = M), control proceeds directly to 720.

In 720, at least one processor of the processor-based system selects the maximum value from a set of determined acceptable lag times determined for a given robot I. In 722, at least one processor of the processor-based system provides one or more determined acceptable lag times (e.g., provides a selected maximum value of determined acceptable lag times) to the given robot for determining a motion plan for at least the given robot. For example, this can include providing one or more determined acceptable lag times to different processors, or transferring one or more determined acceptable lag times to different registers of the processors, or otherwise storing them in a non-transitory processor-readable medium.

In 724, at least one processor of the processor-based system determines whether each robot in the robot group has been considered, for example, whether the robot counter I is equal to the total number of robots (e.g., I = N?). If each robot in the robot group has not been considered (e.g., I < N), control proceeds to 726, where at least one processor of the processor-based system iterates the robot counter (e.g., I = I + 1), and then control returns to the top of the outer iterative robot processing loop 708 to consider the next robot. If each robot in the robot group has been processed (e.g., I = N), control proceeds directly to 728.

In 728, at least one processor of the processor-based system generates or selects a corresponding motion plan for each robot. The motion plan can be, or can represent, the robot's corresponding nominal trajectory associated with the maximum acceptable lag time. This can advantageously enhance the robustness of the motion plans generated by motion planning, and thus improve the operation of the robot executing the resulting motion plans.

When considering multiple trajectories for each robot, the acceptable lag time (e.g., maximum lag time) determined for any given robot can be a function of the corresponding selected trajectories of each of the other robots operating in the shared workspace and the determined acceptable lag time associated with those selected trajectories. Therefore, as described herein, in at least some embodiments, the system determines the acceptable lag time for each robot and each candidate trajectory of that robot, given all other possible combinations of candidate trajectories and candidate lag times for all other robots. Once this is done, the system (e.g., nominal trajectory analyzer 258 of FIG. 2) is able to select a set of trajectories for all robots operating in the shared workspace. The system (e.g., nominal trajectory analyzer 258 of FIG. 2) is able to partition this set of trajectories, for example, by optimizing an objective function (e.g., the maximum sum of all lag times of all robots).

In 730, at least one processor of the processor-based system provides a corresponding motion plan to each robot or each motion controller so that the robot moves according to the corresponding motion plan. For example, this can include providing the motion plan to the corresponding motion controller of each of one or more robots.

At 732, method 700 may terminate, for example, until it is called again. Although method 700 is described as an ordered process, in many implementations, various actions or operations will be performed simultaneously or in parallel, and/or additional actions may be included and/or some actions may be omitted.

Therefore, for example, a processor-based system can determine a corresponding acceptable lag time for each of two or more robots, and for each of two or more nominal trajectories of the corresponding robot, reflecting a maximum acceptable delay in attitude timing relative to the nominal trajectory. This delay still ensures that movement of the robot through a sequence of poses specified by the nominal trajectory remains collision-free relative to movement through a corresponding sequence of poses specified by the corresponding nominal trajectories of the other two or more robots, since the nominal trajectories of the other two or more robots are themselves delayed by the corresponding acceptable lag time. For example, a processor-based system can select between two or more nominal trajectories at least in part based on the corresponding acceptable lag time of the two or more nominal trajectories; and provide a motion plan for the corresponding robot at least in part based on the selected nominal trajectory to control the operation of the corresponding robot among the two or more robots. For example, a processor-based system can select the nominal trajectory with the maximum acceptable lag time among two or more nominal trajectories for the corresponding robot, thereby generating a more robust motion plan than otherwise provided. For example, a processor-based system can select a nominal trajectory based on a corresponding cost function, which represents the acceptable lag time and optional collision risk or probability associated with each of two or more nominal trajectories of a given robot. For example, a processor-based system can select a nominal trajectory based on a corresponding cost function, which represents the acceptable lag time, collision risk or probability, and optional collision severity associated with each of two or more nominal trajectories of a given robot. For example, a processor-based system can select a nominal trajectory based on a corresponding cost function, which represents the acceptable lag time, collision risk or probability, collision severity, and optionally at least one of the following: completion duration or energy consumption, associated with each of two or more nominal trajectories of a given robot, wherein each variable in the cost function represents the acceptable lag time, collision risk or probability, collision severity, and at least one of the following: completion duration or energy consumption, and these variables are weighted in the corresponding cost function. For example, a processor-based system can select a corresponding nominal trajectory for each of two or more robots to maximize the overall acceptable lag time for all robots in the two or more robots. For example, a processor-based system can select a corresponding nominal trajectory for each of two or more robots such that the corresponding cost function for each robot is optimized overall across all robots in the two or more robots, where each cost function represents the acceptable lag time, at least the risk or probability of collision, and the severity of collision associated with the corresponding nominal trajectory in the two or more nominal trajectories of the corresponding robot. For example, a processor-based system can select a corresponding nominal trajectory for each of two or more robots such that the corresponding cost function for each robot is optimized overall across all robots in the two or more robots, where each cost function represents the acceptable lag time, at least the risk or probability of collision, and the severity of collision associated with the corresponding nominal trajectory in the two or more nominal trajectories of the corresponding robot. For example, a processor-based system can select a corresponding nominal trajectory for each of two or more robots, such that the corresponding cost function of each robot is optimized in aggregate across all two or more robots, wherein each cost function represents the acceptable lag time, at least the risk or probability of collision, the severity of collision, and at least one of the following: duration of completion or energy consumption, which are associated with the corresponding nominal trajectory of the two or more nominal trajectories of the respective robot, and each variable in the cost function represents the acceptable lag time, the risk or probability of collision, the severity of collision, and at least one of the following: duration of completion or energy consumption, which are weighted in the corresponding cost function.

For example, a processor-based system can determine the appropriate acceptable lag time for the nominal trajectory, which reflects the maximum acceptable delay in attitude timing relative to the nominal trajectory, while still ensuring that the robot's movement through the specified sequence of attitudes via the nominal trajectory remains collision-free among two or more robots in a shared workspace. This can include performing collision assessments for each of the two or more robots.

For example, a processor-based system is capable of performing collision assessment between i) and ii), where i) represents at least a portion of a sample trajectory of a corresponding nominal trajectory of the robot with at least one corresponding lag time introduced, and ii) at least a portion of a sample trajectory of each of the corresponding trajectories of each of two or more other robots, wherein at least one corresponding lag time is introduced into the corresponding trajectory of each of the two or more other robots.

Figure 8 illustrates an operation method 800 of a processor-based system according to at least one illustrated embodiment for controlling the operation of robots operating in a shared workspace, at least in part, based on an acceptable lag time. According to at least one illustrated embodiment, the processor-based system includes one or more processors that monitor the actual lag time compared to the acceptable lag time and optionally take one or more remedial actions if the actual lag time exceeds a threshold. Method 800 may be executed, for example, after the execution of methods 300 (Figure 3), 400 (Figure 4), 500 (Figure 5), 600 (Figure 6), and/or 700 (Figure 7). For example, method 800 can be executed during runtime, i.e., during the time when one or more robots are executing corresponding motion plans and/or performing tasks. For example, runtime can be performed after a configuration or "pre-run" time, during which partial or full motion planning, such as generating a nominal trajectory and/or motion plan for each robot, can be carried out.

Method 800 begins at 802, for example, in response to the startup or power-on of the system or its components, the receipt of information or data, or the invocation or activation of a routine or program.

Optionally, in 804, at least one processor of the processor-based system accesses (e.g., receives, retrieves) the corresponding motion plan for each robot. The corresponding motion plans can be stored and accessed from one or more non-transitory processor-readable media.

In 806, at least one processor in a processor-based system causes one or more robots to execute corresponding motion plans. For example, at least one processor is capable of providing instructions to one or more motion controllers of one or more robots. One or more motion controllers provide control signals to one or more actuators (e.g., electric motors, solenoids, valves, pumps), which are coupled to drive various links of the robot, thereby causing the robot or parts thereof to move.

In 808, at least one processor in the processor-based system monitors the amount of time lag (actual lag) between a corresponding actual trajectory executed by a corresponding robot and a corresponding nominal trajectory. As previously described, the actual trajectory is an actual sequence of poses and timings of those poses executed by the corresponding robot. While in some cases the actual trajectory may match the nominal trajectory, in many cases the actual trajectory will not match the nominal trajectory, typically the timing of the execution of at least some of the poses of the actual trajectories of one or more robots lags behind the timing of the poses specified by the corresponding nominal trajectory of the corresponding robot. Monitoring can be performed in any of a variety of ways. For example, a processor-based system can use input sensed via one or more sensors positioned to sense the position and/or movement and/or pose or configuration or state of the robots in a shared workspace. The sensors can monitor the entire workspace, for example, in the form of cameras, video cameras, stereo cameras, motion detectors, etc., positioned and having a field of view covering all or at least a portion of the shared workspace. Sensors can additionally or alternatively monitor the position and/or movement and/or attitude or configuration or state of a particular robot, for example, including any one or more of the following: cameras, video cameras, motion detectors, position encoders or rotary encoders, Hall effect sensors and/or reed switches associated with one or more joints, links and/or actuators of the robot. One or more processors can perform processing (e.g., machine vision processing) to monitor the actual trajectory. Additionally or alternatively, processor-based systems can use information from the robot control system and/or drive system (e.g., motor controllers, pneumatic controllers, hydraulic controllers, etc.) representing control signals (e.g., PWM motor control signals) used to drive the robot or parts thereof and/or use feedback signals received from the robot or the robot's drive system (e.g., inverse EMF). One or more processors can perform processing (e.g., machine vision processing) to determine the corresponding actual lag time of the actual trajectory.

In 810, at least one processor of the processor-based system determines whether the monitored lag time (actual lag time) exceeds a margin or threshold (e.g., a correspondingly determined acceptable lag time; a correspondingly determined percentage of the acceptable lag time) of the corresponding trajectory of any of the robots operating in the shared workspace.

In response to determining that the monitored lag time (i.e., the actual lag time) exceeds the corresponding margin or threshold (e.g., the determined acceptable lag time; the percentage of the corresponding determined acceptable lag time) of the corresponding trajectory of any robot, optionally in 812, at least one processor of the processor-based system selects and/or takes one or more remedial measures.

For example, to take at least one remedy, when at least one processor of the processor-based system executes processor-executable instructions, it is able to cause the processor to perform one or more of the following operations: stop the movement of one or more robots, slow down the movement of one or more robots, and/or speed up the movement of one or more robots. For example, at least one processor can stop the movement of one, two, more, or even all robots. Similarly, for example, at least one processor can slow down the movement of one, two, more, or even all robots. Similarly, for example, at least one processor can speed up the movement of one, two, more, or even all robots. Similarly, for example, at least one processor can stop the movement of one or more robots while slowing down the movement of one or more robots. Similarly, for example, at least one processor can stop the movement of one or more robots while speeding up the movement of one or more robots or keeping the movement of one or more robots constant. Similarly, for example, at least one processor can slow down the movement of one or more robots while speeding up the movement of one or more robots or keeping the movement of one or more robots constant. Similarly, for example, at least one processor is capable of stopping the movement of one or more robots while slowing down the movement of one or more robots, while speeding up the movement of one or more robots, or keeping the movement of one or more robots constant. The term "keeping the movement constant" means that the nominal trajectory of the robot does not change, although the robot's movement speed (i.e., velocity and direction) may change as specified by the nominal trajectory. Similarly, for example, to take at least one remedy, when at least one processor of the processor-based system executes processor-executable instructions, it is capable of causing the processor to perform one or more of the following operations: stopping the movement of one or more robots, causing one or more robots to proceed along a corresponding trajectory specified by the corresponding nominal trajectory, and then being able to restart the movement of the robots. Restarting the movement typically involves restarting the movement from where it stopped, although in some cases it may involve returning to the starting point of the corresponding trajectory and starting again from that point.

Optionally, in 814, at least one processor of the processor-based system monitors the amount of lag time (actual lag time) between the corresponding actual trajectory executed by the corresponding robot and the corresponding nominal trajectory.

Optionally, at 816, for each robot operating in the shared workspace, at least one processor of the processor-based system determines whether the monitored lag time (i.e., the actual lag time) no longer exceeds a corresponding margin or threshold (e.g., a determined acceptable lag time; a percentage of the corresponding determined acceptable lag time) for the corresponding robot's corresponding trajectory. The system is able to enter a waiting loop, continuing to monitor the lag time (i.e., the actual lag time) until it no longer exceeds the corresponding margin or threshold (e.g., a determined acceptable lag time; a percentage of the corresponding determined acceptable lag time) for all robots. Once this condition is met, control proceeds to 818.

Optionally, in 818, at least one processor of the processor-based system causes one or more robots to continue executing (e.g., restart movement) the corresponding motion plan.

Method 800 terminates at 820, for example, until it is called again. Although method 800 is described as an ordered process, in many implementations, various actions or operations will be performed simultaneously or in parallel, and/or additional actions may be included and/or some actions may be omitted.

The detailed description above illustrates various implementations of the device and/or process using block diagrams, schematics, and examples. Within the scope of these block diagrams, schematics, and examples encompassing one or more functions and/or operations, those skilled in the art will understand that each function and/or operation in these block diagrams, schematics, or examples can be implemented individually and/or collectively by various hardware, software, firmware, or any combination thereof. In one implementation, the subject matter can be implemented via Boolean circuits, application-specific integrated circuits (ASICs), and/or FPGAs. However, those skilled in the art will recognize that the implementations disclosed herein can be implemented, wholly or partially, in standard integrated circuits in a variety of different ways, as one or more computer programs running on one or more computers (e.g., as one or more programs running on one or more computer systems), as one or more programs running on one or more controllers (e.g., microcontrollers), as one or more programs running on one or more processors (e.g., microprocessors), as firmware, or as virtually any combination thereof, and that designing circuits and/or writing code for software and/or firmware in accordance with this disclosure will be entirely within the skill level of those skilled in the art.

Those skilled in the art will recognize that many of the methods or algorithms described herein may employ additional actions, omit some actions, and/or perform actions in an order different from the specified order.

Furthermore, those skilled in the art will understand that the mechanisms taught herein can be implemented in hardware, such as in one or more FPGAs or ASICs.

The various embodiments described above can be combined to provide further embodiments. All commonly assigned U.S. patent application publications, U.S. patent applications, foreign patents, and foreign patent applications mentioned in this specification and/or listed in the application data sheet, including but not limited to International Patent Application No. PCT/US2017/036880 filed June 9, 2017; International Patent Application No. WO2016/122840 filed January 5, 2016; U.S. Patent Application No. 62/616783 filed January 12, 2018; and U.S. Patent Application No. 62/616783 filed February 6, 2018. U.S. Patent Application No. 62/626939; U.S. Patent Application No. 62/856548, filed June 3, 2019; U.S. Patent Application No. 62/865,431, filed June 24, 2019; U.S. Patent Application No. 62/964405, filed January 22, 2020; U.S. Patent Application No. 63/327917, filed April 6, 2022; and International Patent Application PCT/US2021/013610 (Publication No. WO2021150439A1), all of which are incorporated herein by reference. Based on the above detailed description, these and other changes to the embodiments are possible. Generally, the terminology used in the appended claims should not be construed as limiting the claims to the specific embodiments disclosed in the specification and claims, but should be understood to include all possible embodiments and the full scope of equivalents enjoyed by these claims. Therefore, the claims are not limited by this disclosure.

Claims (31)

1. A method for facilitating the operation of multiple robots in a processor-based system, the method being used in a multi-robot operation environment in which multiple robots will operate, the method comprising: For each of two or more robots, For each of one or more nominal trajectories of a corresponding robot among the two or more robots, the nominal trajectory specifies the corresponding pose sequence and pose timing of the corresponding robot. Determine a corresponding acceptable lag time for the nominal trajectory, the corresponding acceptable lag time reflecting the maximum acceptable delay in attitude timing relative to the nominal trajectory, the maximum acceptable delay still ensuring that the movement of the robot through the attitude sequence specified by the nominal trajectory remains collision-free relative to the movement through the corresponding attitude sequence specified by the corresponding nominal trajectory of each of the other two or more robots; and Provide the acceptable hysteresis time to at least one processor to control the operation of each of the two or more robots; and For each of the two or more robots For each of one or more actual trajectories executed by the corresponding robot Monitor the hysteresis between the nominal trajectory and the corresponding actual trajectory executed by the corresponding robot; Determine whether the detected lag exceeds the corresponding acceptable lag time of the corresponding actual trajectory of the robot; and In response to the detected hysteresis exceeding the corresponding determined acceptable hysteresis time of the corresponding trajectory of the corresponding robot, at least one remedial measure shall be taken. 2. The method according to claim 1, wherein determining the corresponding acceptable lag time of the nominal trajectory includes: For each of the two or more robots For each of the one or more nominal trajectories A sweep volume representation is generated, which represents the volume swept by at least a portion of the robot between a set of pose sequences specified by the nominal trajectory, from at least one time in the nominal trajectory to another time in the nominal trajectory. 3. The method according to claim 2, wherein determining the corresponding acceptable lag time of the nominal trajectory further includes: Perform a collision assessment using the generated swept volume. 4. The method of claim 3, wherein performing collision assessment using the generated sweep volume comprises: for each of the two or more robots, performing a collision assessment between i) and ii), wherein i) represents at least a portion of a corresponding sample trajectory of the robot with at least one corresponding lag time introduced, and ii) at least a portion of a corresponding sample of each trajectory of each of the other robots among the two or more robots, wherein at least one corresponding lag time is introduced into the corresponding trajectory of each of the other robots among the two or more robots, and In response to determining that a collision will occur between the robot and at least one of the other two or more robots, for one or more nominal trajectories of the robot, a corresponding lag time less than the corresponding lag time that would cause a collision to occur is identified as the corresponding acceptable lag time, wherein the acceptable lag time reflects the maximum acceptable delay in attitude timing relative to the nominal trajectory, the maximum acceptable delay still ensuring that the movement of the robot through the attitude sequence specified by the nominal trajectory remains collision-free relative to the movement of the other two or more robots. 5. The method according to claim 4, wherein determining the corresponding acceptable lag time of the nominal trajectory further comprises: In response to determining that a collision will occur between the robot and at least one of the other two or more robots, for one or more nominal trajectories of the other two or more robots where a collision has been determined to occur, a corresponding lag time less than the corresponding lag time that caused the collision to occur is identified as the corresponding acceptable lag time, wherein the acceptable lag time reflects the maximum acceptable delay in attitude timing relative to the nominal trajectory, the maximum acceptable delay still ensuring that the movement of the robot through the attitude sequence specified by the corresponding nominal trajectory remains collision-free relative to the movement of the other two or more robots. 6. The method according to claim 1, wherein determining the corresponding acceptable lag time of the nominal trajectory further comprises: Iterate through each of the multiple candidate lag times in order from the relatively smaller candidate lag times to the relatively larger candidate lag times, at least until the stopping condition is met. Iterate through each of the multiple time periods covered by the nominal trajectory. Based on the current candidate lag time from the candidate lag times, check for collisions between one of the two or more robots and at least one of the other two or more robots; and In response to determining that a collision will occur between one of the two or more robots and at least one of the other two or more robots, the corresponding acceptable lag time of the nominal trajectory of the robot that is determined to collide with at least one of the other two or more robots is set to the closest previous candidate lag time. 7. The method of claim 6, wherein checking for collisions between the robot and other robots based on the current candidate lag time from the candidate lag times comprises: For each of the two or more robots Collision assessment is performed on at least a portion of the nominal trajectory of the robot having the current candidate lag time or another previously determined lag time, relative to at least a portion of the trajectory of each of the other two or more robots having the current candidate lag time. 8. The method of claim 7, wherein performing a collision assessment on at least a portion of the corresponding nominal trajectory of the robot having the current candidate lag time or another previously determined lag time relative to at least a portion of the corresponding trajectory of each of the two or more robots having the current candidate lag time comprises: performing a collision assessment to determine whether at least a portion of the robot collides with at least a portion of any of the other robots while the robot and the other two or more robots are moving along at least a portion of the corresponding nominal trajectory delayed by the candidate lag time. 9. The method of claim 6, wherein checking for a collision between the robot and the other robots based on the current candidate lag time from the candidate lag times comprises: For each of the two or more robots Generate a sweep volume representation, which represents the volume swept by at least a portion of the robot between a set of pose sequences specified by a corresponding nominal trajectory, moving from at least one time in the corresponding nominal trajectory to another time in the corresponding nominal trajectory; and For each pair of robots of the two or more robots For attitude timing specified by a nominal trajectory without introducing any lag time and for attitude timing specified by a nominal trajectory that introduces each of multiple candidate lag times into the corresponding nominal trajectory, determine whether the sweep volume of one robot in the pair intersects with the sweep volume of the other robot in the pair, at least until an intersection is detected. In response to determining that the sweep volume of one robot in the pair intersects with the sweep volume of the other robot in the pair and identifying the robot that has collided, a collision indication is generated. 10. The method of claim 1, wherein taking at least one remedial action comprises at least one or more of the following: stopping the movement of one or more of the robots, slowing down the movement of one or more of the robots, or speeding up the movement of one or more of the robots. 11. The method of claim 1, wherein taking at least one remedial action comprises: stopping the movement of the robot, causing one or more of the robots to proceed along a corresponding trajectory specified by a corresponding nominal trajectory, and then restarting the movement of the robot. 12. The method of claim 1, wherein the determination of the corresponding acceptable lag time of the nominal trajectory occurs during a configuration time prior to the movement of at least two robots according to one or more nominal trajectories of the respective robots. 13. The method of claim 12, wherein the lag between the monitored nominal trajectory and the corresponding actual trajectory executed by the corresponding robot occurs during the runtime of the at least two robots executing a movement specified by one or more nominal trajectories of the corresponding robots, the runtime being after the configuration time. 14. The method of claim 1, wherein the hysteresis between the monitored nominal trajectory and the corresponding actual trajectory executed by the respective robot comprises a central clock shared by the monitors of one or more robots. 15. The method according to any one of claims 1 to 14 and any combination thereof, further comprising: Receive the corresponding motion plan for each of the robots, each motion plan specifying a corresponding nominal trajectory among one or more nominal trajectories for the corresponding robot, the nominal trajectory representing the corresponding collision-free path. 16. A processor-based system for facilitating the operation of multiple robots in a multi-robot operation environment in which multiple robots will operate, the processor-based system comprising: At least one processor; and At least one non-transitory processor-readable medium storing processor-executable instructions, which, when executed by the at least one processor, cause the at least one processor to perform the method of any one of claims 1 to 15. 17. A processor-based system for configuring multiple robots in a multi-robot operating environment, the processor-based system comprising: At least one processor; and At least one non-transitory processor-readable medium storing at least one of data and processor-executable instructions, which, when executed by the at least one processor, cause the at least one processor to: For each of two or more robots, For each of one or more nominal trajectories of a corresponding robot among the two or more robots, the nominal trajectory specifies the corresponding pose sequence and pose timing of the corresponding robot. Determine a corresponding acceptable lag time for the nominal trajectory, the corresponding acceptable lag time reflecting the maximum acceptable delay in attitude timing relative to the nominal trajectory, the maximum acceptable delay still ensuring that the movement of the robot through the attitude sequence specified by the nominal trajectory remains collision-free relative to the movement of the corresponding attitude sequence specified by the corresponding nominal trajectory of each of the two or more other robots; and Provide the acceptable hysteresis time to at least one processor to control the operation of each of the two or more robots; and For each of the two or more robots For each of one or more actual trajectories executed by the corresponding robot Monitor the hysteresis between the nominal trajectory and the corresponding actual trajectory executed by the corresponding robot; Determine whether the detected lag exceeds the corresponding acceptable lag time of the corresponding actual trajectory of the robot; and In response to the detected hysteresis exceeding a corresponding determined acceptable hysteresis time of the corresponding trajectory of the corresponding robot, at least one remedial action is performed. 18. The processor-based system of claim 17, wherein determining the corresponding acceptable lag time of the nominal trajectory comprises: For each of the two or more robots For each of the one or more nominal trajectories A sweep volume representation is generated, which represents the volume swept by at least a portion of the robot between a set of pose sequences specified by the nominal trajectory, from at least one time in the nominal trajectory to another time in the nominal trajectory. 19. The processor-based system of claim 18, wherein determining the corresponding acceptable lag time of the nominal trajectory further comprises: Perform a collision assessment using the generated swept volume. 20. The processor-based system of claim 19, wherein, in order to perform collision assessment using the generated sweep volume, the processor is executable instructions, when executed by the at least one processor, cause the at least one processor to perform collision assessment for each of the two or more robots between i) and ii), wherein i) represents at least a portion of a corresponding sample trajectory of the robot with at least one corresponding lag time introduced, and ii) at least a portion of a corresponding sample of each trajectory of each of the other two or more robots, wherein at least one corresponding lag time is introduced into the corresponding trajectory of each of the other two or more robots, and In response to determining that a collision will occur between the robot and at least one of the other two or more robots, for one or more nominal trajectories of the robot, a corresponding lag time less than the corresponding lag time that would cause a collision to occur is identified as the corresponding acceptable lag time, wherein the acceptable lag time reflects the maximum acceptable delay in attitude timing relative to the nominal trajectory, the maximum acceptable delay still ensuring that the movement of the robot through the attitude sequence specified by the nominal trajectory remains collision-free relative to the movement of the other two or more robots. 21. The processor-based system of claim 20, wherein, in order to determine the corresponding acceptable lag time of the nominal trajectory, the processor-executable instructions, when executed by the at least one processor, further cause the at least one processor to: In response to determining that a collision will occur between the robot and at least one of the other two or more robots, for one or more nominal trajectories of the other two or more robots where a collision has been determined to occur, a corresponding lag time less than the corresponding lag time that caused the collision to occur is identified as the corresponding acceptable lag time, wherein the acceptable lag time reflects the maximum acceptable delay in attitude timing relative to the nominal trajectory, the maximum acceptable delay still ensuring that the movement of the robot through the attitude sequence specified by the corresponding nominal trajectory remains collision-free relative to the movement of the other two or more robots. 22. The processor-based system of claim 17, wherein, in order to determine the corresponding acceptable lag time of the nominal trajectory, the processor-executable instructions, when executed by the at least one processor, further cause the at least one processor to: Iterate through each of the multiple candidate lag times in order from the relatively smaller candidate lag times to the relatively larger candidate lag times, at least until the stopping condition is met. Iterate through each of the multiple time periods covered by the nominal trajectory. Based on the current candidate lag time from the candidate lag times, check for collisions between one of the two or more robots and at least one of the other two or more robots; and In response to determining that a collision will occur between one of the two or more robots and at least one of the other two or more robots, the corresponding acceptable lag time of the nominal trajectory of the robot that is determined to collide with at least one of the other two or more robots is set as the closest previous candidate lag time. 23. The processor-based system of claim 22, wherein, in order to check for a collision between the robot and the other robots based on the current candidate lag time among the candidate lag times, the processor may execute instructions, when executed by the at least one processor, such that the processor: For each of the two or more robots Collision assessment is performed on at least a portion of the nominal trajectory of the robot having the current candidate lag time or another previously determined lag time, relative to at least a portion of the trajectory of each of the other two or more robots having the current candidate lag time. 24. The processor-based system of claim 23, wherein, in order to perform a collision assessment on at least a portion of a corresponding nominal trajectory of the robot having the current candidate lag time or another previously determined lag time relative to at least a portion of the corresponding trajectory of each of the two or more robots having the current candidate lag time, the processor is executable with instructions, when executed by the at least one processor, causing the processor to perform the collision assessment to determine whether at least a portion of the robot collides with at least a portion of any of the other robots during movement of the robot and the other two or more robots along at least a portion of the corresponding nominal trajectory delayed by the candidate lag time. 25. The processor-based system of claim 22, wherein, in order to check for a collision between the robot and the other robots based on the current candidate lag time among the candidate lag times, the processor is executable by instructions, when executed by the at least one processor, such that the processor: For each of the two or more robots Generate a swept volume representation, which represents the volume swept by at least a portion of the robot, moving from at least one time in a corresponding nominal trajectory to another time in a corresponding nominal trajectory, between a set of pose sequences specified by the corresponding nominal trajectory, wherein the current candidate lag time among the candidate lag times is incorporated into the corresponding nominal trajectory; and For each pair of robots of the two or more robots For attitude timing specified by a nominal trajectory without introducing any lag time and for attitude timing specified by a nominal trajectory that introduces each of multiple candidate lag times into the corresponding nominal trajectory, determine whether the sweep volume of one robot in the pair intersects with the sweep volume of the other robot in the pair, at least until an intersection is detected. In response to determining that the sweep volume of one robot in the pair intersects with the sweep volume of the other robot in the pair and identifying the robot that has collided, a collision indication is generated. 26. The processor-based system of claim 17, wherein, in order to take at least one remedy, the processor is executable instructions, when executed by the at least one processor, cause the processor to perform one or more of the following: stop the movement of one or more of the robots, slow down the movement of one or more of the robots, or speed up the movement of one or more of the robots. 27. The processor-based system of claim 17, wherein, in order to take at least one remedial action, the processor is executable instructions, when executed by the at least one processor, cause the processor to: stop the movement of the robot, cause one or more of the robots to advance along a corresponding trajectory specified by a corresponding nominal trajectory, and then restart the movement of the robot. 28. The processor-based system of claim 17, wherein the determination of the corresponding acceptable lag time of the nominal trajectory occurs during a configuration time prior to the movement of at least two robots according to one or more nominal trajectories of the respective robots. 29. The processor-based system of claim 28, wherein the lag between the monitored nominal trajectory and the corresponding actual trajectory executed by the corresponding robot occurs during runtime during which the at least two robots are executing a movement specified by one or more nominal trajectories of the corresponding robots, said runtime being after the configuration time. 30. The processor-based system of claim 17, wherein the hysteresis between the monitored nominal trajectory and the corresponding actual trajectory executed by the respective robot comprises a central clock shared by the monitors of one or more robots. 31. The processor-based system according to any one of claims 17 to 30 and any combination thereof, wherein the processor-executable instructions, when executed by the at least one processor, further cause the processor to: Receive the corresponding motion plan for each of the robots, each motion plan specifying a corresponding nominal trajectory among one or more nominal trajectories for the corresponding robot, the nominal trajectory representing the corresponding collision-free path.