CN119604824A

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

Info

Publication number: CN119604824A
Application number: CN202380051908.2A
Authority: CN
Inventors: 卢卡·科拉桑托; 阿恩·西夫尔林
Original assignee: Real Time Robots Ltd
Current assignee: Real Time Robots Ltd
Priority date: 2022-07-05
Filing date: 2023-06-29
Publication date: 2025-03-11
Anticipated expiration: 2043-06-29
Also published as: WO2024011062A1; JP2025526458A; JP7814081B2; TW202415506A; EP4523051A4; EP4523051A1; CN119604824B

Abstract

Motion planning generates a motion plan for a robot operating in a shared workspace, the motion plan including a nominal trajectory (e.g., a specified trajectory). An acceptable lag time is determined for the nominal trajectory, wherein compliance with the acceptable lag time during actual operation ensures self-collision-free operation. Actual operation of the robot (e.g., an actual trajectory) is monitored for compliance with the corresponding acceptable lag time. Optionally, remedial action is selected and/or taken when necessary (e.g., the actual lag time approaches or exceeds a margin or threshold, such as the corresponding acceptable lag time). Motion planning can select a trajectory using the determined acceptable lag time to provide more robust operation for the robot.

Description

Robust motion planning and/or control for a multi-robot environment

Cross Reference to Related Applications

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

Technical Field

The present disclosure relates generally to motion planning and operation of robots operating in a shared workspace, and to computationally efficient generation of robust motion plans (e.g., reducing or even eliminating collisions and unexpected outages) that can be performed by robots in an efficient manner, as well as monitoring of actual execution of motion plans, and optionally taking remedial action if necessary.

Background

Description of the Related Art

There are a variety of applications that employ two or more robots to operate in a shared workspace. For example, two or more robots may be employed to perform tasks on or with one or more objects or workpieces in a shared workspace, e.g., screw bolts to a chassis, where portions of the robots may overlap over a range of motion.

Planning generally involves mission planning and motion planning. For example, the mission plan can determine that the robot needs to move between two poses (e.g., from a start pose to an end pose) in order to perform a given mission. In contrast, motion planning focuses on how to move a robot between two poses.

Motion planning is a fundamental problem in robot control and robotics. The motion planning specifies the trajectory that the robot is able to transition from a starting pose, configuration or state to a destination pose, configuration or state, typically in order to accomplish a task without or with a reduced likelihood of collision with any obstacle in the shared space. The challenges of motion planning relate to the ability to perform motion planning quickly (i.e., in real-time) while possibly taking into account environmental changes (e.g., changes in the position or orientation of obstacles in a shared workspace). Challenges also include performing motion planning with relatively low energy consumption and limited computing power and/or storage space (e.g., memory circuitry, such as "on-processor-chip" circuitry) using relatively low cost equipment.

Operating two or more robots in a shared workspace (also known as a workcell or multi-robot operating environment) presents a particular class of problems. For example, the movement plan should take into account and avoid situations where the robots or robotic attachments of the robots may interfere with each other during the execution of the tasks.

One method of operating multiple robots in a shared workspace can be referred to as a task level method. An engineer may manually ensure that robots do not collide by defining portions of the shared workspace where robots may collide with each other (i.e., interference areas) and programming each robot so that only one robot is in the interference area of the shared workspace at any given point in time. For example, when a first robot starts to move into an interference area of the shared workspace, the first robot may set a flag. A controller (e.g., a Programmable Logic Controller (PLC)) reads the flag and prevents other robots from moving to an interference area of the shared workspace until the first robot releases the flag upon exiting the interference area. This approach is intuitive, easy to understand, but is often difficult and time consuming to implement, and may not yield optimal results. Since this approach leaves at least one of the robots in an idle state for a considerable time, it necessarily results in a low work throughput, even though an idle robot is technically possible to perform useful work in a shared workspace.

In conventional approaches, the project division team typically breaks down the problem and optimizes the resulting smaller sub-problems independently of each other (e.g., assigning tasks to robots, ordering tasks assigned to each robot, and performing motion planning for each robot). This may take iterative simulation movements to ensure that the robots/robot attachments do not collide with each other, which simulation may take hours of computation time and may not lead to an optimized solution. Furthermore, if a modification to the shared workspace causes a change in the actual trajectory of one of the robot/robotic attachments, the entire workflow must be re-verified. It is clear that this approach is not optimal and often requires that the expert go through a slow iterative process in an attempt to find a solution combination that can produce good results. In any case, this approach generally does not ensure collision-free operation when robots operating under real world conditions perform motion planning.

Disclosure of Invention

Various methods and apparatus are described herein for generating a motion plan for robots operating in a shared workspace, the motion plan including a nominal trajectory (e.g., a specified trajectory) having an associated acceptable lag time, wherein compliance with the acceptable lag time during actual operation ensures self-collision free operation (i.e., collisions of one robot with itself and collisions of one robot with other robots of the robotic system). For example, the nominal trajectory can represent a corresponding collision-free path. Various methods and apparatus are described herein that monitor the actual operation of a robot (e.g., an actual trajectory) relative to an acceptable lag time, and optionally take one or more remedial actions if necessary (e.g., the actual lag time approaches or exceeds a threshold, such as a corresponding acceptable lag time).

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

The motion plan can be represented by a set of discrete robot trajectories: Wherein Where N represents the total number of robots of the robotic 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 that there is no collision with respect to all robots of the robot system. In other words, the motion specified by the set of trajectories Trj (t) of the robot system having two or more robots does not result in self-collision (i.e., collision of one robot with itself and collision of one robot with other robots of the robot system). Although collision assessment can be performed for other objects or obstacles in the shared workspace, the set of trajectories Trj (t) of the robotic system do not necessarily collide with respect to other objects or obstacles in the environment. Such a no-self-collision condition can be easily checked or inspected in the simulation, and once checked or inspected, it can be considered safe to perform the movement prescribed by the movement plan.

However, in practice, during actual execution of a motion plan by a physical robot system comprising two or more robots, many factors may adversely affect the synchronization between the robots. For example, these factors may include signal communication, control delays, sensor noise, numerical approximation errors, and the like. This can cause the actual physical robotic system to deviate from the trajectory Trj (t) specified by the motion plan. In addition to such "realistic gaps" between the simulated environment for generating and reviewing one or more motion plans and the actual operation of a real physical robotic system, many other factors may also cause the robotic system to deviate from a motion plan that provides a set of nominal trajectories. For example, in some cases, the execution of a task may require more time to complete than expected, and thus, the robot may need to last or stay at a particular location (e.g., the destination location, and thus in a particular pose, configuration, or state) for a longer time than specified by the trajectory in the motion plan. Deviations from a particular motion plan that is reviewed and considered safe may be dangerous and may compromise the safety of the robotic system.

The set of trajectories Trj (t) specified by the motion plan are herein named a set of nominal trajectories to indicate that these trajectories are specified trajectories. The single trajectory specified by the motion plan is referred to herein as the nominal trajectory. The set of trajectories performed by the actual physical movements of the robot is herein named a set of actual trajectories to distinguish from a specified trajectory or nominal trajectory. The single trajectory performed by the actual physical movement of the robot is referred to herein as the actual trajectory.

The methods described herein advantageously extend the safe operating regime beyond that associated with a set of one or more nominal trajectories or nominal trajectories of a motion plan, e.g., by calculating a neighborhood of one or more nominal trajectories of a motion plan in which the robotic system is able to operate without causing a self-collision as described above. For each robot that is to operate in the shared workspace, the maximum acceptable lag time (e.g., time delay or "lag") for one or more nominal trajectories that the robot may perform will be calculated. During online execution (i.e., run time), 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 to execute the motion planning, since no self-collision movement between robots is ensured. If the actual lag time of any of the robots exceeds the corresponding margin or threshold, safety is compromised because no self-collision free operation can be ensured anymore. Optionally, the processor-based system is capable of selecting and/or taking one or more remedial actions in such a case.

Drawings

In the drawings, like reference numerals identify similar elements or acts. The dimensions and relative positioning 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 portions of such elements are arbitrarily enlarged and positioned to improve drawing legibility. Furthermore, the particular shapes of the elements as drawn, are not intended to convey any information regarding the actual shape of the particular elements, and have been solely selected for ease of recognition in the drawings.

FIG. 1 is a schematic diagram of a shared workspace and a configuration optimization system performing optimization to configure robots in which multiple robots operate in the shared workspace to perform tasks, according to one illustrated embodiment.

Fig. 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 operation of the first robot, wherein the robot control system includes a motion planner that advantageously determines and employs acceptable lag times for respective nominal trajectories of robots in the motion plan, and optionally monitors actual operation of at least the first robot, compares the actual lag times to a margin or threshold (e.g., acceptable lag times), and optionally takes remedial action if necessary.

Fig. 3 illustrates a method of operation of a processor-based system to perform motion planning to control robots to operate in a shared workspace, wherein acceptable lag times for each robot are determined based on nominal trajectories of other robots without regard to the effects of lag times in the nominal trajectories of other robots, and a motion plan specifying nominal trajectories associated with the respective acceptable lag times is generated or selected, in accordance with at least one illustrated embodiment.

Fig. 4 illustrates a method of operation of a processor-based system to perform motion planning to control robots to operate in a shared workspace, wherein acceptable lag times for each robot are determined based on nominal trajectories of other robots while the effects of lag times in the nominal trajectories of other robots must be considered, and a motion plan specifying nominal trajectories associated with the respective acceptable lag times is generated or selected, in accordance with at least one illustrated embodiment.

Fig. 5 illustrates a method of operation of a processor-based system for generating a swept volume for one or more trajectories of each of a plurality of robots to be operated in a shared workspace, in accordance with at least one illustrated embodiment, optionally usable to perform the methods of fig. 3, 4, and/or 6.

Fig. 6 illustrates a method of operation of a processor-based system for performing collision assessment on a plurality of robots and a plurality of trajectories for each of the robots, wherein movement of the robots or portions thereof along the trajectories is represented as a swept volume, and the collision assessment can be used to determine acceptable lag times for one or more robots operating in a shared workspace, according to at least one illustrated embodiment.

Fig. 7 illustrates a method of operation of a processor-based system for generating or selecting a motion plan for one or more robots to operate in a shared workspace based at least in part on an acceptable lag time and optionally based at least in part on other criteria such as a cost or cost function, in accordance with at least one illustrated embodiment.

FIG. 8 illustrates a method of operation of a processor-based system for controlling operation of a robot operating in a shared workspace based at least in part on acceptable lag time, in accordance with at least one illustrated embodiment.

Detailed Description

In the following description, certain specific details are set forth in order to provide a thorough understanding of the various disclosed embodiments. One skilled in the relevant art will recognize, however, that the embodiments can be practiced without one or more of the specific details, or with 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 descriptions 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 descriptions of the embodiments.

Throughout the specification and the appended claims, the words "comprise" and variations thereof, such as "comprises" and "comprising", are to be interpreted as open-ended inclusion meaning, i.e. "including, but not limited to, unless the context requires otherwise.

Reference throughout this specification to "one embodiment" or "an embodiment," or "one example" or "an example" means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment or at least one example. Thus, the appearances of the phrase "one embodiment" or "an embodiment" or "in one embodiment" or "in an embodiment" in various places throughout this specification are not necessarily all referring to the same embodiment or embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more implementations or embodiments.

Unless the context clearly indicates otherwise, an undefined number of elements in this specification and the appended claims means that at least one of the elements is present. It should also be noted that the term "or" is generally employed in its sense including "and/or" unless the content clearly dictates otherwise.

As used in this specification and the appended claims, the term "optimize" and variants thereof means that improved results are being prepared, generated, or produced, or that improved results have been prepared, generated, or produced. These terms are used in a relative sense and do not necessarily mean that an absolute optimum value has been prepared, generated or produced.

As used in this specification and the appended claims, the term "workspace" or "shared workspace" is used to refer to an operating environment in which two or more robots operate, one or more parts of the shared workspace being the volume in which the robots may potentially collide with each other, and thus these parts may be named interference areas. The operating environment may include obstacles (i.e., items with which the robot is to avoid collisions) and/or workpieces (i.e., items with which the robot needs to interact or act).

As used in this specification and the appended claims, the term "task" is used to refer to a robotic task in which a robot transitions from pose a to pose B, preferably without collision with an obstacle in its environment. The task may involve grabbing or loosening an item, moving or dropping an item, rotating an item, or retrieving or placing an item. The transition from gesture a to gesture B may optionally include a transition between one or more intermediate gestures.

As used in this specification and the appended claims, the term "trajectory" or "trajectories" is used to refer to an ordered sequence of poses or configurations or states of one or more robots, which sequence is parameterized in time, by which sequence one or more robots, or at least a portion thereof, can move, e.g., perform a task. The trajectories are preferably represented in a configuration space (also referred to as C-space) of the respective robot, but alternatively can also be represented in a real space or real world space of the shared workspace. The trajectory can include pauses, changes in direction, or even reversals of one or more gestures, and is not necessarily smooth in direction, time, speed, or acceleration.

As used in this specification and the appended claims, the term "nominal trajectory" or "nominal trajectories" is used to refer to one or more trajectories that are "specified". As used in this specification and the appended claims, the term "actual trajectory" or "actual trajectories" is used to refer to one or more trajectories actually performed by physical motions of a physical robot as distinguished from "nominal trajectory" or "nominal trajectories". In some cases, the "actual track" or "actual tracks" may match the "nominal track" or "nominal tracks", although in many cases there may be a difference between the two, for example, because the "actual track" or "actual tracks" lag in time the "nominal track" or "nominal tracks".

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

The headings and abstract of the disclosure are provided herein for convenience only and do not interpret the scope or meaning of the embodiments.

The methods described herein advantageously extend the safety of robot operations beyond that ensured by the nominal trajectory of the motion plan by determining an acceptable lag time for the physical robot of the robot system to be able to operate while still ensuring that such operation of the robot system does not self-collide. In at least some implementations, a maximum acceptable lag time (e.g., time delay or "lag") is calculated for each of the one or more nominal trajectories for each robot of the robotic system that is to operate in the shared workspace. Advantageously, the maximum acceptable lag time can be calculated during a configuration time before the robot performs the motion planning. During online execution (i.e., at run-time, after configuration time), the actual motion of each robot is monitored, including monitoring 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 continued execution of the motion plan may be deemed safe because no self-collision movement can be ensured. If the actual lag time of the robot exceeds the corresponding margin or threshold, safety is compromised because no self-collision operation can be ensured anymore. 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 to be adversely affected. Optionally, the processor-based system is capable of selecting and/or taking one or more remedial actions in such a case.

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

The plurality of robots may be configured to perform a set of tasks. A task may be designated as a mission plan. The mission plan may specify T missions that need to be performed by N robots. The mission plan can be modeled as a vector for each robot, where the vector is an ordered list of tasks to be performed by the respective robot (e.g., { task 7, task 2, task 9 }). The task vector can also optionally include a dwell duration that specifies the duration that the robot or portion thereof should stay at a given configuration or target. The task vector may also specify a home gesture (home pose) and/or other "functional gestures" (e.g., a "yield" or storage gesture) that are not directly related to the resolution task. The pose may be specified in the C-space of the robot.

The robot 102 can take any of a variety of forms. Typically, the robot 102 will take the form of or have one or more robotic attachments 103 (only one labeled) and a base 105 (only one labeled) from which the robotic attachments 103 extend. The robot 102 may include one or more links having one or more joints, and an actuator (e.g., an electric motor, a stepper motor, a solenoid, a pneumatic actuator, or a hydraulic actuator) coupled and operable to move the links in response to control or drive signals. For example, the pneumatic actuator may include one or more pistons, cylinders, valves, gas reservoirs, and/or pressure sources (e.g., compressors, blowers). For example, the hydraulic actuator may include one or more pistons, cylinders, valves, a liquid reservoir (e.g., low-compressibility hydraulic fluid), and/or a pressure source (e.g., compressor, blower). The robotic system 100 may employ other forms of robots 102, such as automated vehicles.

The shared workspace 104 generally represents a three-dimensional space in which the robot 102 may 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 area where at least a portion of the robot 102 may overlap in space and time, or if motion is not controlled to avoid collisions, collisions may occur. Notably, the shared workspace 104 is a physical space or volume, wherein the position and orientation of the physical space or volume may be conveniently represented via, for example, a Cartesian coordinate system relative to a reference system (e.g., the reference system 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 is different from the corresponding "configuration space" or "C-space" of any of the robots 102, which is typically represented by a set of joint positions, orientations, or configurations in the corresponding reference frame of any of the robots 102.

As described herein, the 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 machine 102 b). The shared workspace 104 may also include other obstructions such as mechanical components (e.g., conveyor 106), posts, struts, walls, ceilings, floors, tables, people, and/or animals. The shared workspace 104 may also include one or more work items or artifacts that the robot 102 manipulates (e.g., one or more packages, wrappers, fasteners, tools, items, or other objects) as part of performing the task.

Optionally, the robotic system 100 includes one or more processor-based multi-robot configuration optimization systems 108 (one shown in fig. 1). The optional one or more multi-robot configuration optimization systems 108 receive a set of inputs 109 and generate as outputs 111 one or more solutions specifying the configuration of the robots 102, including a work cell layout (e.g., the respective base position and orientation of each robot 102), one or more mission plans (e.g., the respective mission plans of each of the robots 102), and optional one or more motion plans that specify or include one or more nominal trajectories of the robots 102 a-102 c (e.g., the respective nominal trajectories of each of the robots 102) and an acceptable lag time for each of the nominal trajectories. One or more components of the output 111 may be optimized, at least to some extent.

The optional one or more multi-robot configuration optimization systems 108 may include a population generator 110, a multi-robot environment simulator 112, a multi-robot optimization engine 114, and an acceptable lag time evaluator 115.

Population generator 110 generates a set of candidate solutions 116 based on the provided inputs 109. Candidate solutions 116 represent possible solutions to the configuration problem (i.e., how to configure robots 102 in shared workspace 104 to complete a set of tasks). Any given candidate solution 116 may in fact be viable, it may not be possible. That is, the initial candidate may be invalid (e.g., the robot is in a non-possible place, has an unreachable target, or an infeasible mission plan that may result in a collision). In some embodiments, the population generator may attempt to find better candidate solutions.

The multi-robot environment simulator 112 models the workspace or multi-robot environment on a per-candidate solution basis to determine certain attributes, such as the amount of time required to complete a task, the probability or ratio of collisions at the completion of the task, the feasibility or infeasibility of a particular configuration specified by the candidate solution. For example, the multi-robot environment simulator 112 may reflect these attributes in terms of cost via the cost generated by one or more cost functions.

For example, the cost or cost function can represent the probability or likelihood of collision. Alternatively, the cost or cost function can represent one or more of an acceptable lag time or "robustness", severity of the collision, energy consumption or loss to perform or complete the motion corresponding to the nominal trajectory, and/or time or lag. In some embodiments, the cost or cost function represents an acceptable lag time for the determination of a given nominal trajectory for a given robot. The determined acceptable lag time represents the maximum or near maximum or optimized lag time that may be incurred if the respective nominal trajectory is performed while still maintaining, ensuring, or even guaranteeing at least no self-collision movement with respect to itself and with respect to other robots operating in the shared workspace or work cell. Thus, the lag time can represent the amount of lag that can be introduced into or caused by the actual execution of the nominal trajectory without abandoning the safety factor (e.g., no self-collision operation), thereby enhancing the robustness of the corresponding motion plan. For example, the safety factor can be checked or censored via simulating the robot operation using the nominal trajectory. Thus, if the actual trajectory of the robot lags behind the nominal trajectory by more than a specified margin or threshold (e.g., acceptable lag time), collision-free operation is no longer ensured.

The multi-robot optimization engine 114 evaluates the candidate solutions based at least in part on the association cost 119 and advantageously performs a collaborative optimization across a set of two or more non-homogenous parameters, e.g., across two or more parameters of the respective base positions and orientations of robots, assigning tasks to the respective robots, the respective target sequences of robots, and/or the respective trajectories or paths between consecutive targets (e.g., collision-free trajectories or paths). A straight line trajectory between successive objects may be used to simplify the description, but the trajectory is not necessarily a straight line trajectory.

The input 109 may include one or more static environmental models representing or characterizing the operating environment or shared workspace 104, e.g., representing floors, walls, ceilings, posts, other obstructions, etc. The operating environment or shared workspace 104 may be represented by one or more models, for example, geometric models (e.g., point clouds) representing floors, walls, ceilings, obstructions, and other objects in the operating environment. For example, the model may be represented in Cartesian coordinates.

The 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, range of joint type motion, speed limit, acceleration limit, or jerk limit. The robot 102 may be represented by one or more robot geometry models that define the geometry of a given robot 102 a-102C, e.g., in terms of joints, degrees of freedom, dimensions (e.g., link lengths), and/or corresponding C-space of the robots 102 a-102C.

The input 109 may include one or more sets of tasks to be performed, for example, represented as a target purpose (e.g., gesture, configuration, state, or location or place). For example, the task may be represented by a last pose, a last configuration, or a last state and/or an intermediate pose, an intermediate configuration, or an intermediate state of the respective robot 102 a-102 c. For example, the pose, configuration, or state may be defined in terms of joint positions and joint angles/rotations (e.g., joint pose, joint coordinates) of the respective robots 102 a-102 c. Alternatively, the input 109 may include one or more dwell times that specify a nominal amount of time that the robot or portion thereof should stay at a given target in order to complete a task (e.g., tightening a screw or nut, picking and placing objects, in order to sort a stack of objects into an object stack of two or more different types of objects by two or more robots operating in a common workspace).

In some implementations, one or more multi-robot configuration optimization systems 108 can generate a nominal trajectory for each robot to perform one or more tasks. The nominal trajectories are "specified" trajectories, wherein each nominal trajectory comprises a time-parameterized ordered set or sequence of poses, configurations, or states of the robot between an initial or starting pose, configuration, or state of the nominal trajectory and a final or ending pose, configuration, or state of the nominal trajectory, each with a corresponding timing. The pose or configuration is preferably represented in a configuration space (also referred to as C-space) of the respective robot, or alternatively in real space or real world space of the working space. The timing may be specified in relative terms (e.g., timing defined by a relative offset from the timing of an immediately preceding gesture) or in absolute terms (e.g., timing defined by the duration of execution of the trace from the beginning, and e.g., relative to a common clock). In at least some cases, the nominal trajectory can specify or include one or more pauses in the motion or path of the robot or portion thereof, and/or can specify reversal of the direction or path of motion of the robot or portion thereof, which may not otherwise be smooth motion in direction or time. The applicant notes that although any given trajectory can correspond to a smooth motion of the robot, the term "trajectory" as used herein is not limited thereto and will generally designate an uneven motion, nor define a straight line path for the robot or portion thereof. For example, the nominal trajectory can specify a time-parameterized ordered set or sequence of poses by which the robot or portion thereof moves to complete a task or portion of a task. Performing any given task can take one or more nominal trajectories. As described herein, the actual motion or actual trajectory of the robot or portion thereof may deviate from the corresponding nominal trajectory, for example, due to unexpected delays in transitioning between poses (e.g., due to a longer time to stay or stay at the target object than expected).

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

The input 109 may optionally include a limit on the number of robots that can be configured in the shared workspace 104. The input 109 may optionally include a limit on the number of tasks or targets that can be allocated to a given robot 102 a-102 c, referred to herein as a task capacity, that can be configured in the shared workspace 104, e.g., limiting the complexity of the configuration problem to ensure that the configuration problem is solvable, or using available computing resources within some acceptable period of time, or eliminating in advance certain solutions that are considered too slow because of a significant over allocation of tasks or targets to a given robot 102 a-102 c. The input 109 may optionally include one or more limits or constraints on the variable or other parameter. The input 109 may optionally include a total number of iteration loops or a time limit of the iteration that may be used to refine the candidate solution, e.g., to ensure that the configuration problem is solvable or is solvable using available computing resources for some acceptable period of time.

The robotic system 100 may optionally include one or more robotic control systems 118 (only one shown in fig. 1) communicatively coupled to control the robot 102. For example, one or more robot control systems 118 may provide control signals (e.g., drive signals) to various actuators to cause the robot 102 to move between various configurations to various specified targets to perform specified tasks.

The robotic system 100 may optionally include one or more motion planners 120 (only one shown in fig. 1) communicatively coupled to control the robot 102. As described elsewhere herein, one or more motion planners 120 generate, select, or refine a motion plan for the robot 102, e.g., to account for small deviations in time from the motion plan provided by the multi-robot optimization engine 114, or to account for unexpected occurrences of obstacles (e.g., human entry into the operating environment or shared workspace 104). The optional motion planner 120 is operable to dynamically generate motion plans to cause the robot 102 to perform tasks in an operating environment. The motion planner 120, as well as other structures and/or operations, may be as described in U.S. patent application Ser. No. 62/865431 filed 24 at 2019, 6.

Where motion planner 120 is included, motion planner 120 is optionally communicatively coupled to receive as input sensory data provided, for example, by a sensory subsystem (not shown). The perceptual data represents previously unknown static and/or dynamic objects in the shared workspace 104. The perception 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 to a digital representation of an obstacle by a perception subsystem, which may generate a corresponding discretization of an environmental representation in which the robot 102 is to operate to perform tasks of various different scenes.

The various communication paths are shown in fig. 1 as lines between the various structures, and in some cases, arrows indicate the direction of the input 109 and the output 111. For example, the 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 radio 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), and so forth. The general operation of the robotic system 100, and in particular the general operation of the one or more multi-robot configuration optimization systems 108, is shown and described in International patent application PCT/US2021/013610 (publication No. WO 2021/150439), and is not repeated herein for the sake of brevity. Only some of the more significant differences in operation are described herein, e.g., in embodiments, one or more multi-robot configuration optimization systems 108 perform the various methods described herein to determine acceptable lag times, generate or select a motion plan based at least in part on the determined acceptable lag times, and/or one or more robot control systems 118 perform the various methods described herein to monitor actual lag times of robots executing the motion plan, compare the actual lag times to a margin or threshold (e.g., acceptable lag time), and/or control the robots accordingly, e.g., to take one or more remedial actions if one or more of the actual lag times exceeds one or more of the acceptable lag times or related thresholds.

Fig. 2 illustrates a robotic system according to at least one illustrated embodiment, wherein the first robotic control system 200a includes a first motion planner 204a that generates a first motion plan 206a to control operation of the first robot 202, and optionally provides the first motion plan 206a and/or the motion representations as obstacles to other motion planners 204b of other robotic control systems 200b via at least one communication channel (represented by approximate arrows, e.g., transmitters, receivers, transceivers, radios, routers, ethernet) to control other robots (not shown in fig. 2). In the robot control systems 200a, 200b of fig. 2, the acceptable lag time is determined by the motion planner along with the motion plans 206a, 206b, which include one or more nominal trajectories performed by the one or more robots 202. In contrast to the robot control system 100 (fig. 1), the robot control systems 200a, 200b of fig. 2 do not necessarily perform optimization of work cell arrangements or mission plans. Further, as described herein, the robotic control system 200a, 200b of fig. 2 monitors the actual lag time and, optionally, selects and/or takes remedial action as necessary.

Likewise, 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 operation of one or more other robots (not shown in fig. 2), and optionally provide the one or more other motion plans 206b to other ones of the first motion planner 204a and one or more other motion planners 204b of the one or more other robot control systems 200 b. The motion planners 204a, 204b may also optionally receive motion completion information 209, which indicates when the motion of the respective robot 202 has been completed. This may allow the motion planners 204a, 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 completes some or all of the set of motions that form part of the first robot 102 completing the task, a portion of the shared workspace may become blocked, unblocked, or otherwise available for the second robot to perform the task. Additionally or alternatively, the motion planners 204a, 204b can receive information (e.g., images, occupied mesh, joint positions, and joint angles/rotations) collected by various sensors or generated by other motion planners 204b that indicates when a portion of the shared workspace may become blocked, unblocked, or otherwise available for the second robot to perform tasks after the first robot 202 has completed some or all of the set of motions that form part of the first robot 102 to complete the task.

As described herein, the motion plans 206a, 206b specify a nominal trajectory for each robot, e.g., for performing one or more tasks. As described previously, nominal trajectories are "specified" trajectories, wherein each nominal trajectory comprises a time-parameterized ordered set or sequence of poses, configurations, or states of the robot, each with a corresponding timing. The pose, configuration or state is preferably represented in a configuration space (also referred to as C-space) of the respective robot.

The robotic control systems 200a, 200b may optionally be communicatively coupled, for example via at least one communication channel (represented by approximate arrows, e.g., transmitter, receiver, transceiver, radio, router, ethernet) to optionally receive the motion planning map 208 and/or swept volume representation 211 from one or more sources 212 of the motion planning map 208 and/or swept volume representation 211. According to one illustrated embodiment, the one or more sources 212 of the motion planning map 208 and/or swept volume representation 211 may be separate and distinct from the motion planners 204a, 204 b. For example, the one or more sources 212 of the motion planning map 208 and/or swept volume representation 211 may be one or more processor-based computer systems (e.g., server computers) that may be operated or controlled by a respective manufacturer of the robot 202 or some other entity. The motion plan 208 may each include a set of nodes 214 (only two are labeled in fig. 2) and a set of edges 216 (only two are labeled in fig. 2), the nodes 214 representing the pose, configuration, or state of the respective robot, the edges 216 coupling the nodes 214 of the respective node pairs 214 and representing legal or valid transitions between the pose, configuration, and state. For example, the pose, configuration, or state may be defined in a respective configuration space (C-space) of the robot, representing a set of joint positions, directions, poses, or coordinates of each of the joints of the respective robot 202. Thus, each node 214 may represent a pose, configuration, or state of the robot 202 or portion thereof, which is entirely defined by the pose configuration or state of the joints making up the robot 202. The motion plan graph 208 may be determined, set, or defined prior to runtime (i.e., defined prior to performing a task), such as during pre-runtime or configuration time. The optional swept volume representation 211 represents the respective volume that the robot 202 or portion thereof would occupy when performing a motion or transition between poses corresponding to the respective edges 216 of the motion plan 208. The optional swept volume representation 211 may be represented in any of a variety of forms, for example, as voxels, euclidean distance fields, a hierarchy of geometric objects. This advantageously allows some of the most computationally intensive work to be performed before run time, as the response capability is not of particular concern at this time. Although a swept volume is used herein, this is exemplary and any of a variety of other collision assessment methods can be employed.

Each robot 202 may optionally include a base (not shown in fig. 2). The base may be fixed in the environment or movable in the environment (e.g., an automated or semi-automated vehicle). Each robot 202 may optionally include a set of links, joints, end-of-arm tools, or end effectors and/or actuators 218a, 218b, 218c (three shown, collectively 218) operable to move the links about the joints. The set of links, joints, end-of-arm tools, or end effectors typically include one or more robotic attachments that are capable of being movably coupled to a base of the robot. 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 plans 206 a) and provide drive signals to drive actuators 218. Alternatively, the motion controller 220 can be separate from the robot 202 and communicatively coupled to the robot 202. For example, as described in International patent application PCT/US2021/013610 (publication number WO 2021/150439), each robot 202 can be positioned and oriented in a shared workspace based on an optimized work cell layout.

Each robot 202 (only one robot is shown in fig. 2) may have a corresponding robot control system 200a, 200b, or alternatively, one robot control system 200a may perform motion planning for two or more robots 202. For purposes of illustration, one of the robotic control systems 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 examples of other robotic control systems 200.

The first robotic 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 (not shown) of the processors 222. A non-transitory computer or processor-readable storage medium (e.g., system memory 224a, one or more disk drives 224 b) is communicatively coupled to the 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 of 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, peripheral component interconnect express (PCIe), or via Thunderbolt ^®.

The first robotic control system 200a may also be communicatively coupled to one or more remote computer systems, such as a server computer (e.g., source 212), a desktop computer, a laptop computer, a ultra-portable computer, a tablet computer, a smart phone, a wearable computer, and/or sensors (not shown in fig. 2), which are communicatively coupled to the various components of the first robotic control system 200a directly or indirectly, such as via interface 227. A remote computing system, such as a server computer (e.g., source 212), may be used to program, configure, control, or otherwise interact with the first robotic control system 200a and the various components in the first robotic control system 200a, or to input data (e.g., motion planning map 208, swept volume representation 211, task specification 215, or even candidate paths or nominal trajectories). Such connections may be through one or more communication channels 210, such as one or more Wide Area Networks (WANs), e.g., ethernet, or the internet using internet protocols. As described above, the pre-run calculations may be performed by a system separate from the first robot control system 200a or the first robot 202, while the run-time calculations may be performed by the one or more processors 222 of the first robot control system 200a as the one or more robots perform tasks. In some embodiments, one or more of the robot control systems 200a, 200b may be mounted on a respective robot (e.g., the first robot 202).

As described above, the first robotic control system 200a may include one or more processors 222 (i.e., circuitry), a non-transitory storage medium (e.g., system memory 224a, one or more disk drives 224 b), and a system bus 234 that couples various system components. The processor 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, which can form part of the ROM 226, contains the basic routines that help to transfer information between elements within the first robotic control system 200a, such as during start-up.

For example, one or more disk drives 224b may be a hard disk drive for reading from and writing to magnetic disks, a solid state (e.g., flash) drive for reading from and writing to solid state memory, and/or an optical disk drive for reading from and writing to removable optical disks. In various embodiments, the first robotic control system 200a may also include any combination of such disk drives. One or more disk drives 224b may be in communication with one or more processors 222 via a system bus 234. As known to those skilled in the relevant art, one or more disk drives 224b may include an interface or controller (not shown) coupled between such drives and system bus 234. The one or more disk drives 224b and their associated computer-readable media provide nonvolatile storage of computer or processor readable and/or executable instructions, data structures, program modules, and other data for the first robot control system 200 a. One skilled in the relevant art will appreciate that other types of computer readable media which are capable of storing computer-accessible data, such as WORM drives, RAID drives, magnetic cassettes, digital video disks ("DVDs"), bernoulli cartridges, RAMs, ROMs, smart cards, and the like, may be used.

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

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

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

The application 238 may include processor-executable instructions that cause the one or more processors 222 to determine a respective acceptable lag time for the nominal trajectory. An acceptable lag time is generally an amount of time that an actual motion (e.g., an actual trajectory) of the robot 202 can lag or differ from a nominal time specified by a corresponding nominal trajectory, while ensuring at least no self-collision operation of the robot 202 relative to one or more other robots operating in the shared workspace. In some embodiments, the precondition for no self-collision operation is that the other robots do not experience any lag time in performing, although preferably, the precondition for no self-collision operation is that all robots are operating within a respective acceptable lag time of their respective nominal trajectories, thus taking into account that each robot experiences a lag time in performing a respective nominal trajectory.

To generate a motion plan, generate a nominal trajectory, and/or determine an acceptable lag time, the application 238 may include processor-executable instructions that cause the one or more processors 222 to invoke or otherwise perform collision assessment. Collision assessment is often referred to as "collision detection" or "collision check", even though the assessment will typically determine the probability or likelihood of a collision and will typically occur prior to the actual movement of the robot, rather than meaning that an actual physical collision of the robot is detected during the physical movement of the robot. Collision assessment may be alternatively referred to herein as "collision detection," collision check, "or" collision analysis.

The application 238 may include processor-executable instructions that cause the one or more processors 222 to set a cost value or cost function for an edge in the motion planning map, e.g., reflecting a determined probability or likelihood of collision, and optionally other parameters. The application 238 may include processor-executable instructions that cause the one or more processors 222 to set a cost value or cost function for the nominal trajectory, e.g., reflecting the corresponding acceptable lag time, and alternatively additionally reflecting the determined probability or likelihood of collision, and optionally other parameters.

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

The application 238 may also include one or more machine-readable and machine-executable instructions that cause the one or more processors 222 to monitor robot movements (e.g., actual trajectories) and evaluate the actual delays or actual lag times of the actual trajectories as compared to a margin or threshold (e.g., acceptable lag time or based on acceptable lag time) of the corresponding nominal trajectories. Optionally, the application 238 may also include one or more machine-readable and machine-executable instructions that cause the one or more processors 222 to select and/or take one or more remedial actions (e.g., slow one or more robots, stop one or more robots, and/or accelerate one or more robots) when necessary (e.g., if the actual lag time approaches or exceeds an acceptable lag time).

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

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

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

Although shown in fig. 2 as being stored in system memory 224a, 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 224 b).

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

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

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

The motion converter 250 can include a trajectory predictor 251 for predicting the trajectory of a transient object (e.g., other robots, other objects, including, for example, a person), for example, when the trajectory of the transient object is unknown (e.g., where the object is another robot but does not receive a motion plan for the other robot, the object is not another robot, such as a person). For example, trajectory predictor 251 can assume that the object will continue to move in both directions, velocities, and accelerations without change. For example, the trajectory predictor 251 can consider an expected change in the motion or path of the object, such as when the path of the object would cause a collision, and thus can expect the object to stop or change direction, or when the object's purpose is known, and thus can predict that the object stops when the purpose is reached. In at least some cases, the trajectory predictor 251 can predict the trajectory of the object using a learned behavioral model of the object. For example, the trajectory predictor 251 can infer known motion and expected changes to generate a predicted trajectory of the transient object.

The motion converter 250 then optionally determines regions or volumes corresponding to known and/or one or more inferred motions of the object. For example, the motion converter can convert the motion into a respective swept volume, i.e. a volume swept by the respective robot or part thereof when moving or converting between poses represented by the motion plan, e.g. by generating a volumetric representation of the robot or part thereof, and projecting the volumetric representation along a path defined by the trajectory of the robot or part thereof. Also for example, the motion converter can convert motion into a corresponding swept volume, e.g., by generating a volumetric representation of an object (e.g., a non-robotic object such as a human) and projecting the volumetric representation of the object along a path defined by a known and/or inferred trajectory of the object. Advantageously, the motion planner 204a may simply queue an obstacle (e.g., swept volume) and may not need to determine, track, or indicate the time of the corresponding motion or swept volume. Although generally described as a motion converter 250 for the first robot 202 that converts motion of other robots (not shown in fig. 2) to obstacles, in some embodiments, other robot control systems 200b of other robots operating in a shared workspace may provide an obstacle representation (e.g., swept volume) of a particular motion to the motion planner 204a of the first robot 202.

The path generator 252 generates a path (e.g., an ending gesture, configuration, state; or a destination gesture, configuration, and state) from one gesture, configuration, or state (e.g., a starting gesture, configuration, or state) to another gesture or configuration, or state. The path generator 252 is capable of determining or identifying one or more possible paths from a start (e.g., a start node or start gesture or start state) to a destination (e.g., a destination node or destination gesture or destination state; an end node or end gesture or end state). For example, the path generator 252 can determine or identify an ordered sequence of nodes in the motion plan graph that provides a complete path from a starting or current node to a destination or ending node (i.e., a set of ordered nodes for which each pair of consecutive nodes in the complete path has a corresponding effective transition therebetween, e.g., represented by the presence of an edge of the node coupling the pair of nodes). As described above, each node can correspond to a respective pose, configuration, or state of a respective robot. The path generator 252 can use or perform any kind of path finding method, technique, and/or algorithm. For example, the path generator 252 can employ various methods, techniques, and/or algorithms to randomly or pseudo-randomly generate paths to select a sequence of nodes in a motion planning graph, where a node is connected to a next node in the sequence via an edge (i.e., an edge representing an effective transition between poses represented by the connected nodes). The path generator 252 is capable of generating a relatively large number of candidate paths between the start node and the end node, thereby generating a large number of candidate paths between the start pose, configuration, or state and the end pose, configuration, or state. In some implementations, the path generator 252 can determine or identify viable paths or trajectories independent of costs (e.g., costs representing the probability or likelihood of experiencing a collision along the path), thereby creating a set of viable paths or candidate paths that can later be evaluated based at least in part on the probability or likelihood of experiencing a collision. In other cases, the path generator 252 can consider costs (e.g., costs representing the probability or likelihood of experiencing collisions along the path) in determining or identifying a viable path or trajectory.

The collision evaluator 253 performs collision evaluation, also referred to as collision detection or collision analysis. Specifically, the collision evaluator 253 optionally performs collision evaluation as a part of determining whether a candidate path representing a transition or movement of a given robot 202 or a part thereof specified in accordance with a nominal trajectory will result in or possibly cause a collision with an obstacle. As mentioned above, the movements of other robots may advantageously be represented as obstacles. Thus, the collision evaluator 253 can determine whether the motion of one robot would cause or may cause a collision with another robot moving in the shared workspace.

As described herein, collision assessment, detection, or analysis can be performed not only on candidate paths, but additionally or alternatively, on nominal trajectories (e.g., specified trajectories), and in particular on nominal trajectories that introduce various lag times (e.g., simulating actual trajectories that may lag the nominal trajectories). In at least some embodiments, collision assessment, detection, or analysis of a nominal trajectory that introduces various lag times can be performed for each of two or more robots (e.g., paired robots). Collision assessment, detection or analysis can be performed on one or more nominal trajectories of each robot in the 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 and non-zero lag times, e.g., evaluating a trajectory pair for each permutation of lag times of the trajectory pair. As described herein, collision assessment, detection, or analysis does not necessarily yield a binary result, but can yield a non-binary value, e.g., representing the probability or likelihood of a collision between a pair of robots caused by a path or trajectory.

In some implementations, the collision evaluator 253 enables software-based collision evaluation, detection, or analysis, e.g., performing bounding box-bounding box collision evaluation, detection, or analysis based on a hierarchy of geometric (e.g., sphere) representations of volumes swept by a robot (e.g., the first robot 202) or portions thereof during movement. In some implementations, collision evaluator 253 enables hardware-based collision evaluation, detection, or analysis, e.g., employing a set of dedicated hardware logic circuits to represent an obstacle, and streaming the representation of motion through the dedicated hardware logic circuits. In hardware-based collision assessment, detection, or analysis, the collision detector can employ one or more configurable circuit arrays, e.g., one or more FPGAs 259, and can optionally generate a boolean collision assessment.

Cost setter 254 can set, update, and/or adjust a cost or cost function associated with a conversion (e.g., an edge in a motion plan graph) or a motion (e.g., a trajectory of a motion plan). For example, cost setter 254 can set, update, and/or adjust a cost or cost function based at least in part on collision assessment, detection, or analysis. For example, cost setter 254 can set a relatively high cost value for edges or trajectories representing transitions between nodes or motions that result in or likely to result in collisions. Also for example, cost setter 254 can set a relatively low cost value for edges or trajectories representing transitions between nodes or motions that do not or are less likely to result in collisions. Setting, updating, and/or adjusting a cost or cost function can include setting, updating, or adjusting a cost or cost function associated with corresponding edge or trace logic via some data structure (e.g., fields in a record, pointers in a list, tables).

In some implementations, for example, cost setter 254 is optionally capable of setting, updating, or adjusting a cost or cost function to at least partially represent the determined acceptable lag time for the corresponding nominal trajectory. This can advantageously enable 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, e.g., to select a 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 embodiments, additionally or alternatively, cost setter 254 can set, update, or adjust a cost or cost function to at least partially represent one or more other parameters, such as one or more of severity of the collision, consumption or loss of energy, and/or time or delay of execution or completion.

The alternative path analyzer 255 can use the motion plan graph 208 and the cost or cost function to determine or identify one or more suitable paths and/or to select a single path (i.e., a selected path, e.g., an optimal or optimized path). For example, the alternative path analyzer 255 can identify one or more paths that meet some specified criteria (e.g., cost is within an upper threshold), or even select a single path from a set of candidate viable paths determined or identified by the path generator 252 (e.g., select a single lowest cost path). The identified paths can be named suitable paths because these represent options with acceptably low collision probabilities or likelihoods. For example, the alternative path analyzer 255 can constitute a lowest cost path optimizer that determines a lowest or relatively low cost path between two nodes (thus, represented by a corresponding node in a motion planning graph between two poses, configurations, or states). The optional path analyzer 255 can use or execute any kind of path finding algorithm (e.g., a lowest cost path finding algorithm) that, in view of the cost values associated with each edge, represent the probability or likelihood of collision and optionally represent one or more other parameters (e.g., severity of collision, consumption or loss of energy, and/or time or delay of execution or completion). In some embodiments, cost-based optimization can alternatively or additionally be applied to the nominal trajectory to advantageously cause an acceptable lag time to be represented in the cost value or cost function, as described herein, for example, in addition to the probability or likelihood of a collision, and optionally in addition to or in lieu of one or more of severity of the collision, consumption or loss of energy, and/or time or delay of execution or completion.

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

Acceptable lag time estimator 257 estimates various candidate lag times for a given nominal trajectory to determine an acceptable lag time, which ensures no self-collision operation even if the lag of the actual trajectory of the corresponding robot from the nominal trajectory does not exceed the acceptable lag time. In a preferred approach, acceptable lag time estimator 257 considers the lag effects not only in the nominal trajectory of a given robot, but also in the corresponding nominal trajectories of other robots operating in the shared workspace. Thus, acceptable lag time estimator 257 identifies an acceptable lag time for each nominal trajectory that assumes the worst case scenario, wherein the actual trajectories of all robots operating in the shared workspace experience their corresponding acceptable lag times. Thus, for example, acceptable lag time estimator 257 can determine an optimized (e.g., maximum) lag time for each robot that ensures no self-collision operation. Several methods of determining an acceptable lag time are described herein, for example, with respect to method 300 (fig. 3), method 400 (fig. 4), method 500 (fig. 5), method 600 (fig. 6), and/or method 700 (fig. 7).

The optional nominal trajectory analyzer 258 can use a cost value or cost value function or some other objective function to determine, identify, or select one or more suitable trajectories and/or to determine, identify, or select a single trajectory (i.e., a selected trajectory, e.g., an optimal or optimized trajectory). For example, the nominal trajectory analyzer 258 can determine, identify, or select one or more trajectories that meet some specified criteria (e.g., the cost is within a threshold upper bound), 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 the trajectory generator 256 (e.g., determine, identify, or select the lowest cost trajectory). For example, the nominal trajectory analyzer 258 can constitute a lowest cost trajectory optimizer that determines a lowest or relatively low cost trajectory between two poses, configurations, or states represented by corresponding nodes in a motion plan graph. For example, the nominal trajectory analyzer 258 can select a set of trajectories for all robots that optimize robust operation, e.g., by maximizing the sum of all lag times for all robots, a given task, or a set of given tasks to be performed by the robots within a given time period. The nominal trajectory analyzer 258 can use or execute any kind of algorithm, such as a lowest cost trajectory finding algorithm, while taking into account the costs associated with each trajectory, wherein the cost or cost function represents the probability or likelihood of a collision and an acceptable lag time, and optionally represents one or more of the severity of the collision, the consumption or loss of energy, and/or the time or delay of execution or completion.

Various algorithms and structures may 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 may be used, including but not limited to determining the lowest cost path or lowest cost trajectory as a path between two nodes in the motion planning map 208, or as a trajectory specified by a time parameterized ordered pose sequence such that the sum of the costs or weights of its constituent edges or motions is minimized. The process improves the motion planning technique of the robots 102 (fig. 1), 202 (fig. 2) by determining an acceptable lag time, optionally selecting a trajectory based on the determined acceptable lag time, monitoring the actual trajectory to evaluate whether the actual lag time approaches or exceeds a margin or threshold (e.g., acceptable lag time), and optionally selecting and/or taking remedial action, if necessary.

Although not shown, the motion planner 204a may optionally include a look-ahead evaluator that may cause corrective action to be taken, such as in response to a determination of the presence or occurrence of a jam or likely jam condition, or a determination of a jam or likely foot-jam location that will occur when a given robot and/or other robots are moving along a corresponding trajectory. In at least some implementations, the look-ahead evaluator can determine or select a type of improvement to be taken, e.g., select from a set of different types of improvements based on one or more criteria. One or more of various types of improvements (among others, referred to as remedial measures) can be implemented as described in U.S. patent application 63/327,917 filed on 6, 4, 2022. For example, a new, revised, or replacement first motion plan may be generated to move the given robot to the first destination based on an analysis of a second motion plan to move the given robot from the first destination. Furthermore, for example, new, revised or replacement motion plans can be generated for another robot that is or may block a given robot. Also for example, a new order of a set of targets can be determined or generated, the set of targets comprising a first target and at least a second target. This can be determined or generated pseudo-randomly or based on one or more heuristics (e.g., always attempting 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 can optionally include an optional multipath analyzer that can analyze the total cost or aggregate cost associated with the trajectories of two or more motion plans (e.g., the total cost of the first motion plan and the second motion plan), for example, as described in U.S. patent application 63/327,917 filed on month 4 and 6 of 2022. This can be used to identify the combination of motion plans with the lowest total cost. For example, the multi-path analyzer can consider the total cost or aggregate cost of two or more options of the first motion plan in conjunction with the second motion plan, e.g., using or executing any sort of lowest cost finding algorithm, while considering cost values that represent the likelihood of an associated collision, and optionally one or more of acceptable lag time, severity of the collision, consumption or loss of energy, and/or time or delay associated with executing or completing the transition represented by the respective edge.

Optionally, the motion planner 204a may include a trimmer 260. The trimmer 260 may receive information indicating that the other robots completed the movement, which information is referred to herein as a movement complete message 209. Alternatively, a flag may be set to indicate completion. In response, the trimmer 260 may remove an obstacle or a portion of an obstacle that represents the motion that has been completed. This may allow a new movement plan to be generated for a given robot, which may be more efficient, or allow a given robot to perform a task that was previously blocked by the movement of another robot. This approach advantageously allows the motion converter 250 to ignore the timing of the motion in generating a representation of the obstacle to motion, while still achieving better throughput than using other techniques. The motion planner 204a may also send a signal, prompt, or trigger to cause the collision evaluator 253 to perform new collision detection or evaluation if the obstacle is modified to generate an updated motion plan map in which the edge weights or costs associated with the edges have been modified and to cause the cost setter 254, the alternative path analyzer 255, and the nominal trajectory analyzer 258 to update the cost value and determine new or revised paths, trajectories, and/or motion plans accordingly.

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

The one or more processor processors 222 and/or the motion planner 204a may be, or may include, any logic processing unit, e.g., 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, itanium, and Xeon series microprocessors provided by Intel ^®, K8, K10, bulldozer, and Bobcat series microprocessors provided by Chalcon semiconductor, america, A5, A6, and A7 series microprocessors provided by apple computer, wittig series microprocessors provided by Highway Co., ltd, and SPARC series microprocessors provided by oracle. The construction and operation of the various structures shown in FIG. 2 may be implemented or employed in the structures, techniques and algorithms described or analogous thereto under International patent application number PCT/US2017/036880 filed on 6/9/2017, international patent application publication number WO 2016/122840 filed on 5/1/2016, U.S. patent application number 62/616783 filed on 12/1/2018, international patent application PCT/US2021/013610, publication number WO 2021/150439, and/or U.S. patent application number 63/327917 filed on 4/6/2022.

Although not required, many embodiments 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, that are capable of performing obstacle representations, collision assessment, and other motion planning operations.

The motion planning operations may include, but are not limited to, generating or converting one, more or all of a geometric model-based robot geometric representation, a task specification 215, and a selectable representation of the volume occupied by the robot (e.g., swept volume) under various states or poses and/or during movement between states or poses, a representation in digital form, such as a point cloud, a euclidean distance field, a data structure format (e.g., hierarchical format, non-hierarchical format), and/or a curve (e.g., polynomial or spline representation). The motion planning operation may optionally include, but is not limited to, generating or converting one, more or all of a representation of a static or persistent obstacle and/or perceived data of a static or transient obstacle into a digital form, such as a point cloud, a euclidean distance field, a data structure format (e.g., hierarchical format, non-hierarchical format), and/or a curve (e.g., polynomial or spline representation).

The motion planning operations may include, but are not limited to, assessing, detecting, determining, or predicting collisions of various poses, configurations, or transitions between states of the robot, or collisions of motions of the robot between states or poses along respective trajectories, using various collision assessment techniques or algorithms (e.g., software-based, hardware-based).

In some embodiments, the motion planning operations may include, but are not limited to, determining one or more motion plans, or roadmaps having nominal trajectories, acceptable lag times for the nominal trajectories, storing the determined plans, motion plans, or roadmaps, or acceptable lag times, and/or providing the plans, motion plans, or roadmaps, or acceptable lag times, to control operation of one or more robots, and optionally monitor operation of the robots, and select and/or take remedial action, if necessary.

In one embodiment, collision detection or evaluation is performed in response to a function call or similar process and a boolean value is returned thereto. 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 embodiments, these operations may be performed entirely in hardware, or as software stored in a memory such as system memory 224a and executed by one or more hardware processors 222a, e.g., 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.

Various aspects of sensing, layout construction, collision detection, and path searching that may be employed in whole or in part are also described below, international patent application number PCT/US2017/036880 filed on 6 months and 9 days 2017, international patent application number WO 2016/122840 filed on 5 months and 5 days 2016, U.S. patent application number 62/616783 filed on 12 months and 1, 2019, U.S. patent application number 62/856548 filed on 3 months and 2020, international patent application number PCT/US2020/039193 filed on 23 months and 6, 2020 (publication number WO 2020/263861), international patent application number PCT/US2021/013610, publication number WO 2021/150439, and/or U.S. patent application number 63/327917 filed on 4 months and 6 days 2022. Those skilled in the relevant art will appreciate that the illustrated embodiments and other embodiments can be practiced with other system configurations and arrangements and/or other computing system configurations and arrangements, including robots, hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, personal computers ("PCs"), networked PCs, minicomputers, mainframe computers, and the like. These implementations or embodiments, or portions thereof (e.g., at configuration time and run time), are capable of being practiced in distributed computing environments where tasks or modules are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices or media. However, where and how certain types of information are stored is important to help improve motion planning.

For example, various motion planning solutions "embed (rake in)" a roadmap (i.e., a motion planning map) into a processor (e.g., FPGA 259), and each edge in the roadmap corresponds to a non-reconfigurable boolean circuit of the processor. A problem with designs that "embed" the planning map into the processor is that the processor circuitry is limited, cannot store multiple or large planning maps, and is generally not reconfigurable for use with different robots.

One solution is to provide a reconfigurable design that places layout information in memory. This approach stores information in memory rather than embedded in circuitry. Another approach is to replace the memory with a templated reconfigurable circuit.

As described above, some information (e.g., a robot geometry model) may be captured, received, entered, or provided during a configuration time (i.e., prior to runtime). The received information may be processed during a configuration time to generate processed information (e.g., the motion planning map 208) to speed up operations or reduce computational complexity during runtime.

During runtime, collision detection may be performed on the entire environment (i.e., shared workspace), including determining, for any pose or movement between poses, 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 (e.g., people) in the environment having unknown trajectories.

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

The lag time monitor 264 monitors the actual lag time of the actual trajectory performed by the robot and compares the actual lag time to a margin or threshold value for the corresponding nominal trajectory (e.g., a margin or threshold value representing or even equal to the corresponding acceptable lag time). As previously described, 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 execution of at least some of the poses, configurations, states, or movements of the actual trajectory lags the timing of those poses, configurations 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 actual trajectory of the robot is approaching or exceeding a margin or threshold of the respective robot (e.g., a respective determined acceptable lag time of the respective nominal trajectory). For example, if the actual lag time of any robot operating in the shared workspace exceeds a respective threshold (e.g., approaches or exceeds a respective acceptable lag time), the lag time monitor 264 can provide an indication (e.g., set a flag, send information, and/or invoke the remedial action selector 266). In some embodiments, the margin or threshold can be set to include a desired safety factor, e.g., a set amount or defined percentage less than the determined acceptable lag time of the corresponding nominal trajectory. Thus, in some embodiments, the margin or threshold can be set equal to the respective acceptable lag time, while in other embodiments, the margin or threshold can be less than (e.g., less than 10%) the respective acceptable lag time, thereby enabling detection and remedial action to be taken before a self-collision is likely to occur.

The optional remedial action selector 266 selects one or more appropriate remedial actions and/or causes the selected remedial action to be taken in response to determining that the monitored amount of lag time exceeds a respective threshold (e.g., determined acceptable lag time) for the respective trajectory of any robot. Determining that the actual lag time exceeds the corresponding threshold (e.g., the determined acceptable lag time) means that no self-collision movement is ensured, and therefore one or more remedial actions may need to be taken.

The remedial action can include one or more of stopping movement of the one or more robots, slowing movement of the one or more robots, and/or speeding movement of the one or more robots. For example, the movement of one, two, more or even all robots can be stopped. Furthermore, for example, the movement of one, two, more or even all robots can be slowed down, for example by different amounts with respect to each other. Furthermore, for example, the movement of one, two, more or even all robots can be accelerated, for example, by different amounts relative to each other. Further, for example, movement of one or more robots can be stopped while movement of one or more robots is slowed down. Further, for example, movement of one or more robots can be stopped while movement of one or more robots is accelerated or kept constant. Further, for example, movement of one or more robots can be slowed down while movement of one or more robots is accelerated or kept constant. Further, for example, movement of one or more robots can be stopped while slowing movement of one or more robots and while speeding movement of one or more robots or keeping 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., via actuators 218 a-218 c of motion controller 220) to stop, slow, accelerate, and even follow respective trajectories specified by the respective nominal trajectories. For example, this may then restart the movement of the robot, e.g., from where the movement stopped or slowed, although in some cases it may involve returning to the start of the corresponding nominal trajectory and restarting from there.

Fig. 3 illustrates a method 300 of operation of a processor-based system that performs motion planning to control robots to operate in a shared workspace, in accordance with at least one illustrated embodiment. In accordance with at least one illustrated embodiment, a processor-based system includes one or more processors executing processor-executable instructions to determine an acceptable lag time for each robot based on nominal trajectories of other robots without regard to the effects of the lag time in the nominal trajectories of the other robots and generate or select a motion plan specifying the nominal trajectories associated with the respective acceptable lag times. For example, the method 300 can be performed during a configuration or "pre-run" time, i.e., a time at which some or all of the motion planning occurs, e.g., generating a nominal trajectory and/or motion plan for each robot. The configuration or "pre-run" time can occur before the robots move in accordance with the nominal trajectory of the respective robot, e.g., before run time, where run time is the time that one or more robots execute the respective motion plan. This advantageously allows some of the most computationally intensive work to be performed before run time, as the response capability is not of particular concern at this time. In at least some implementations, the method 300, or portions thereof, is performed during a runtime (i.e., a time at which one or more robots are performing tasks) subsequent to a configuration time or a pre-runtime. In other implementations, the method 300 is performed during a runtime (i.e., the time at which one or more robots perform tasks) subsequent to a configuration time or a pre-runtime.

The method 300 begins at 302, for example, in response to a start-up or power-up of the system or a component thereof, receipt of information or data, or a call or enablement of a calling routine or program.

Although not shown in fig. 3, the method 300 is capable of generating paths, performing collision assessment or detection or analysis on the paths, setting, updating, or adjusting costs of edges of the paths, and optionally performing analysis to identify or select paths (e.g., lowest cost paths) based on costs. This is described above with reference to fig. 2, and at least some aspects of the references cited herein are described. These are omitted from method 300 for simplicity.

Optionally, at 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 poses, configurations, or states of the robot that extends between two poses, configurations, and states (e.g., a start pose, configuration, or state; an end pose, configuration, state), and includes a respective timing for each pose or configuration. The timing can be specified in relative terms (timing is defined by a relative offset from a previous pose) or absolute terms (timing is defined by a relative offset from the start of track execution, e.g., relative to a common clock). The applicant notes that although any given trajectory can correspond to a smooth motion of the robot, the term "trajectory" as used herein is not limited thereto and will generally designate an uneven motion, nor define a straight line path for the robot or portion thereof. In at least some cases, the nominal trajectory can specify or include one or more pauses in the movement of the robot or portion thereof, and/or can specify changes in direction or path direction of movement of the robot or portion thereof, even in reverse, changes in velocity, and changes in acceleration, and may not be smooth movement in direction, velocity, or time. For example, the nominal trajectory can specify a time-parameterized ordered set or sequence of poses by which the robot or portion thereof moves to perform a task or portion of a task. Performing any given task can take one or more nominal trajectories. As described herein, the actual motion or actual trajectory of the robot or portion thereof may deviate from the corresponding nominal trajectory, for example, due to unexpected delays in transitioning between poses (e.g., due to a need to stay or stay on the target object longer than expected).

The nominal trajectory can be generated using any of a variety of techniques and/or algorithms, such as a sample-based motion planner (SBMP), e.g., a Probabilistic Roadmap (PRM) or fast-explored random tree (RRT, RTT s), stable sparse RRT (SST) and/or fast-match tree (FMT). In at least one embodiment, the nominal trajectory can be generated via systems, methods, and techniques described in International patent application PCT/US2021/013610 (publication number WO 2021150439A 1). The teachings of the present patent application are not limited to the generation of a particular form of nominal trajectory. Advantageously, the teachings herein include any combination or permutation of computationally efficient use of nominal trajectories to generate a motion plan with associated acceptable lag times, monitoring deviations of actual motion from nominal trajectories in terms of lag times, optionally taking remedial action to deviations exceeding respective acceptable lag times, and/or optionally using determined lag times to select a set of nominal trajectories for the motion plan to enhance robustness of operation.

In 306, at least one processor of the processor-based system initializes a robot counter I, e.g., sets the robot counter equal to an integer value of 1. In 308, at least one processor of the processor-based system performs an external iterative loop, performing an iteration on each of the two or more robots to operate in the shared workspace, or until a stop condition is reached (e.g., determining a maximum lag time to ensure no self-collision movement).

At 310, at least one processor of the processor-based system initializes a nominal trace counter J, e.g., sets the nominal trace counter equal to an integer value of 1.

At 312, at least one processor of the processor-based system performs an internal iterative loop, performing an iteration for each nominal trajectory of the given robot, at least until a stop condition is reached.

At 314, at least one processor of the processor-based system determines a respective acceptable lag time for a current nominal trajectory (i.e., current in the inner iteration loop) of the current robot (i.e., current in the outer iteration loop). The corresponding acceptable lag time reflects the maximum acceptable delay or lag in the current nominal trajectory J that still ensures a self-collision free movement of the current robot relative to the other robots each moving in accordance with the corresponding nominal trajectory when the current robot performs the nominal trajectory (the corresponding acceptable lag time is introduced into the nominal trajectory of the current robot). As long as all other robots are following their respective nominal trajectories (i.e. lag time=0), an acceptable lag time for a given robot I can be ensured that no self-collision will occur. In other words, as long as the respective current actual lag time of a given robot is less than or equal to (i.e., not greater than) the respective acceptable lag time of that robot, and the other robots are traveling in their nominal trajectories, the robots will not collide with each other (i.e., it is ensured that no self-collision between robots occurs).

At 316, at least one processor of the processor-based system determines whether each of the nominal trajectories of the given robot is considered, e.g., determines 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 been considered, control passes to 318, at which the nominal trajectory counter is incremented (e.g., j=j+1), and control then returns to 312 to consider the next nominal trajectory of the given robot. If each nominal trajectory (e.g., j=m) of a given robot has been considered, control passes directly to 320.

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

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

At 324, at least one processor of the processor-based system determines whether each of the robots is considered, e.g., whether the robot counter I is equal to the total number of robots (e.g., i=n. If each of the robots has not been considered (e.g., I < N), control passes to 326, at least one processor of the processor-based system iterates the robot counter (e.g., i=i+1) at 326, and control then returns to 308 to consider the next robot. If each of the robots has been processed (e.g., i=n), control passes directly to 328.

At 328, at least one processor of the processor-based system generates or selects a respective motion plan for each robot. The motion plan can be or can represent a nominal trajectory of the robot associated with a maximum acceptable lag time. The motion plan can be or can represent a nominal trajectory of one or more robots. Such a method can advantageously enhance the robustness of the motion plan generated by the motion plan and thereby improve the operation of the robot performing the resulting motion plan.

At 330, at least one processor of the processor-based system provides a respective motion plan to each robot or motion controller to cause the robot to move according to the respective motion plan.

At 332, the method 300 may terminate, for example, until recalled. Although the method 300 is described in terms of an ordered flow, in many embodiments, various acts or operations will be performed concurrently or in parallel, and/or additional acts can be included and/or some acts omitted.

Fig. 4 illustrates a method 400 of operation of a processor-based system that performs motion planning to control robots to operate in a shared workspace, in accordance with at least one illustrated embodiment. The processor-based system includes one or more processors executing processor-executable instructions to determine an acceptable lag time for each robot based on nominal trajectories of other robots and at the same time must take into account the effects of the lag time in the nominal trajectories of other robots and generate or select a motion plan specifying the nominal trajectories associated with the respective acceptable lag times. For example, the method 400 can be performed during a configuration or "pre-run" time, i.e., a time at which some or all of the motion planning occurs, e.g., generating a nominal trajectory and/or motion plan for each robot. The configuration or "pre-run" time can occur before the robots move in accordance with the nominal trajectory of the respective robot, e.g., before run time, where run time is the time that one or more robots execute the respective motion plan. This advantageously allows some of the most computationally intensive work to be performed before run time, as the response capability is not of particular concern at this time. In at least some implementations, the method 400, or portions thereof, is performed during a runtime (i.e., a time at which one or more robots are performing tasks) subsequent to a configuration time or a pre-runtime. In still other embodiments, the method 400 is performed during a runtime (i.e., the time at which one or more robots perform tasks) subsequent to a configuration time or a pre-runtime.

The method 400 begins at 402, for example, in response to a start-up or power-up of the system or a component thereof, receipt of information or data, or a call or enablement of a calling routine or program.

Although not shown in fig. 4, the method 400 is capable of generating paths, collision assessment or detection or analysis of the paths, setting, updating, or adjusting costs of edges of the paths, and optionally performing analysis to identify or select paths (e.g., lowest cost paths) based on costs. This is described above with reference to fig. 2, and at least some aspects of the references cited herein are described. These are omitted from method 400 for simplicity.

Optionally, at 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 comprises an ordered set or sequence of poses, configurations, and states of the robot between two poses, configurations, or states, and a respective timing for each pose or configuration. The timing can be specified in relative terms (timing is defined by a relative offset from a previous pose) or absolute terms (timing is defined by a relative offset from the start of track execution, e.g., relative to a common clock). The applicant notes that although any given trajectory can correspond to a smooth motion of the robot, the term "trajectory" as used herein is not limited thereto and will generally designate an uneven motion, nor define a straight line path for the robot or portion thereof. In at least some cases, the nominal trajectory can specify or include one or more pauses in the movement of the robot or portion thereof, and/or can specify changes in direction or path direction of movement of the robot or portion thereof, even in reverse, changes in velocity, and changes in acceleration, and may not be smooth movement in direction, velocity, or time. For example, the nominal trajectory can specify a time-parameterized ordered set or sequence of poses by which the robot or portion thereof moves to perform a task or portion of a task. Performing any given task can take one or more nominal trajectories. As described herein, the actual motion or actual trajectory of the robot or portion thereof may deviate from the corresponding nominal trajectory, for example, due to unexpected delays in transitioning between poses (e.g., due to a need to stay or stay on the target object longer than expected).

The nominal trajectory can be generated using any of a variety of techniques and/or algorithms, such as a sample-based motion planner (SBMP), e.g., a Probabilistic Roadmap (PRM) or fast-explored random tree (RRT, RTT s), stable sparse RRT (SST) and/or fast-match tree (FMT). In at least one embodiment, the nominal trajectory can be generated via systems, methods, and techniques described in International patent application PCT/US2021/013610 (publication number WO 2021150439A 1). The teachings of the present patent application are not limited to the generation of a particular form of nominal trajectory. Advantageously, the teachings herein include any combination or permutation of computationally efficient use of nominal trajectories to generate a motion plan with associated acceptable lag times, monitoring deviations of actual motion from nominal trajectories in terms of lag times, optionally taking remedial action for deviations exceeding respective acceptable lag times, and/or optionally using determined lag times to select a set of nominal trajectories for the motion plan to enhance robustness of operation.

At 406, at least one processor of the processor-based system initializes a robot counter I, e.g., sets the robot counter equal to an integer value of 1. At 408, at least one processor of the processor-based system performs an external iterative loop, performing an iteration on each of the two or more robots to operate in the shared workspace, or until a stop condition is reached (e.g., determining a maximum lag time to ensure no self-collision motion between robots).

At 410, at least one processor of the processor-based system initializes a nominal trace counter J, e.g., sets the nominal trace counter equal to an integer value of 1. At 412, at least one processor of the processor-based system performs an internal iterative loop, performing an iteration for each nominal trajectory of the given robot, at least until a stop condition is reached.

At 414, at least one processor of the processor-based system determines a respective acceptable lag time for a current nominal trajectory (i.e., current in the inner iteration loop) of the current robot (i.e., current in the outer iteration loop). The corresponding acceptable lag time reflects the maximum acceptable delay or lag in the current nominal trajectory J that still ensures that the current robot moves relative to each according to the corresponding nominal trajectory (the corresponding acceptable lag time is introduced into the corresponding nominal trajectory) when the current robot executes the nominal trajectory (the corresponding acceptable lag time is introduced into the nominal trajectory of the current robot)

In) the robot is not subject to self-collision. The acceptable lag time for a given robot I ensures that no self-collision will occur as long as the current actual lag time for all other robots is less than its corresponding acceptable lag time. That is, the other robots do not have to travel on their respective nominal trajectories (i.e., lag time = 0). In other words, as long as the respective 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 respective acceptable lag time of the robots, the robots will not collide with each other or with themselves (i.e., it is ensured that no self-collision between robots occurs).

At 416, at least one processor of the processor-based system determines whether each of the nominal trajectories of the given robot is considered, e.g., determines 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 been considered, control passes to 418, where the nominal trajectory counter is incremented (e.g., j=j+1), and control then returns to 412 to consider the next nominal trajectory of the given robot. If each nominal trajectory (e.g., j=m) of a given robot has been considered, control passes directly to 420.

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

At 424, at least one processor of the processor-based system determines whether each of the robots is considered, e.g., whether the robot counter I is equal to the total number of robots (e.g., i=n. If each of the robots has not been considered (e.g., I < N), control passes to 426, at 426 at least one processor of the processor-based system iterates the robot counter (e.g., i=i+1), and control then returns to 408 to consider the next robot. If each of the robots has been processed (e.g., i=n), control passes directly to 428.

At 428, at least one processor of the processor-based system generates or selects a respective motion plan for each robot. The motion plan can be or can represent a nominal trajectory of the robot associated with a maximum acceptable lag time. The motion plan can be or can represent a nominal trajectory of one or more robots. Such a method can advantageously enhance the robustness of the motion plan generated by the motion plan and thereby improve the operation of the robot performing the resulting motion plan.

At 430, at least one processor of the processor-based system provides the corresponding motion plan to

Each robot or each motion controller to cause the robot to move according to a corresponding motion plan.

At 432, the method 400 may terminate, for example, until recalled. Although method 400 is described in terms of an ordered flow, in many embodiments, various acts or operations will be performed concurrently or in parallel, and/or additional acts can be included and/or some acts omitted.

As described herein, to determine an acceptable lag time, a processor-based system can perform a collision assessment to determine which of a set of candidate lag times will result in or likely to result in a collision. One method of collision assessment is to use the swept volume of the robot to perform collision assessment. The swept volume represents the volume swept by the robot or portion thereof as it moves along a given trajectory. The swept volume is specified by the geometry and kinematics of the given robot and by the starting and ending positions specified by the given trajectory. Notably, the swept volume itself is not affected by the particular time at which the trajectory-specified motion is performed. Thus, the swept volume can advantageously be determined during configuration or pre-run time before the run time of the robot performing or executing the task. Thus, the processor-based system is able to generate a swept volume for each of a plurality (e.g., many) of paths from which to generate trajectories for robots for each robot to operate in a shared workspace. The processor-based system is capable of performing collision assessment using the swept volume. For example, for each of two or more robots, the processor-based system is capable of performing collision assessment between i) representing at least a portion of a respective sample trajectory of the robot that introduces a respective nominal trajectory of at least one respective lag time, and ii) at least a portion of a respective sample of each of the respective trajectories of each of the other of the two or more robots, wherein at least one respective lag time is introduced into the respective trajectories of each of the other of the two or more robots. In response to determining that a collision (e.g., expressed as a probability or likelihood) will occur or likely occur between the robot and at least one other robot of the two or more robots, the processor-based system can identify, for one or more nominal trajectories of the robots, a respective lag time that is less than a respective lag time that results in a determination that a collision will occur as the respective acceptable lag time. The acceptable lag time can represent a maximum acceptable delay in timing of the pose relative to the nominal trajectory that still ensures that movement of the robot through the nominal trajectory-specified pose sequence remains collision-free (no self-collision for the robotic system) relative to movement of other robots of the two or more robots. Figures 5 and 6 below describe a non-limiting method of determining an acceptable lag time using swept volumes.

Fig. 5 illustrates a method 500 of operation of a processor-based system for generating a swept volume for one or more trajectories for each of a plurality of robots to be operated in a shared workspace, in accordance with at least one illustrated embodiment. In accordance with at least one illustrated embodiment, the processor-based system includes one or more processors that execute processor-executable instructions to generate a swept volume. For example, the method 500 can be performed during a configuration or "pre-run" time, i.e., a time at which some or all of the motion planning occurs, e.g., generating a nominal trajectory and/or motion plan for each robot. For example, a configuration or "pre-run" time can precede a run time, where the run time is the time at which one or more robots execute the respective motion plan. This advantageously allows some of the most computationally intensive work to be performed before run time, as the response capability is not of particular concern at this time. In at least some implementations, the robot configuration method 500, or portions thereof, is performed during a configuration time or a runtime subsequent to a pre-runtime (i.e., a time when one or more robots are performing tasks). Alternatively, the configuration-time operations can be performed via a processor-based system that is different from the processor-based system that performs the runtime operations. For example, method 500 can alternatively be used to perform the methods of fig. 3, 4, and/or 6, e.g., as part of performing collision detection (see method 600, fig. 6) in determining the respective hysteresis acceptable hysteresis times 314 (fig. 3) and 414 (fig. 4).

The method 500 of generating a swept volume begins at 502, for example, in response to a start-up or power-up of the system or a component thereof, receipt of information or data, or a call or enablement of a calling routine or program.

At 504, at least one processor of the processor-based system initializes a robot counter I (e.g., i=1). At 506, at least one processor of the processor-based system executes an external robotic processing cycle. The external robot processing loop allows at least one processor of the processor-based system to perform generation of swept volumes for each of the robots to be operated in the shared workspace.

At 508, at least one processor of the processor-based system initializes a trace counter J (e.g., j=1). At 510, at least one processor of the processor-based system performs an internal nominal trace processing loop. The internal nominal trajectory processing cycle is nested within the external robotic processing cycle. The internal nominal trajectory processing loop allows at least one processor of the processor-based system to generate a respective swept volume for each of one or more nominal trajectories of a given robot.

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

At 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 all of the trajectories for the given robot have not been processed, control passes to 516, where the trajectory counter is incremented (e.g., j=j+1) in 516, and control then returns to the top of the internal nominal trajectory processing loop 510. If all nominal trajectories have been processed (e.g., j=m), control passes directly to 518.

At 518, at least one processor of the processor-based system determines whether all robots have been processed (e.g., i=n. If all robots have not been processed, control passes 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 passes directly to 522.

At 522, the method 500 may terminate, for example, until recalled. Although the method 500 is described in terms of an ordered flow, in many embodiments, various acts or operations will be performed concurrently or in parallel, and/or additional acts can be included and/or some acts omitted.

Fig. 6 illustrates a method 600 of operation of a processor-based system for performing collision assessment for a plurality of robots and a plurality of trajectories for each of the robots, in accordance with at least one illustrated embodiment. The method 600 can be used to perform collision assessment to identify a feasible path between a starting node and an ending node in a motion planning map. Additionally or alternatively, the method 600 can be used to perform collision assessment in order to determine respective acceptable lag times for one or more nominal trajectories of robots operating in a shared workspace. In accordance with at least one illustrated embodiment, a processor-based system includes one or more processors that execute processor-executable instructions to perform collision assessment, for example, using swept volumes. The swept volume represents or simulates the volume swept by the robot or portion thereof in, for example, a transition between various poses, configurations, or states transitioning between a start node and an end node along a path represented in a motion plan graph, or in, for example, a nominal trajectory movement between along the start pose, configuration, or state to the end pose, configuration, or state. For example, the method 600 can advantageously use the swept volume generated via the method 500. For example, the method 600 can be performed during a configuration or "pre-run" time, i.e., a time at which some or all of the motion planning occurs, e.g., generating a nominal trajectory and/or motion plan for each robot. For example, a configuration or "pre-run" time can precede a run time, where the run time is the time at which one or more robots execute the respective motion plan. This advantageously allows some of the most computationally intensive work to be performed before run time, as the response capability is not of particular concern at this time. In at least some implementations, the robot configuration method 600, or portions thereof, is performed during a configuration time or a runtime subsequent to a pre-runtime (i.e., a time at which one or more robots are performing tasks).

The method 600 of determining an acceptable lag time begins at 602, for example, in response to a start-up or power-up of the system or a component thereof, receipt of information or data, or a call or enablement of a calling routine or program.

At 604, at least one processor of the processor-based system initiates an external robot-to-collision assessment cycle. The external robot-to-collision assessment loop allows at least one processor of the processor-based system to assess or estimate the probability or likelihood of collision between robots in each pair of robots to be operated in the shared workspace. The external robot pair collision assessment cycle is capable of handling collisions that may occur in each combination or permutation of robot pairs.

At 606, at least one processor of the processor-based system initializes a trace counter J (e.g., j=1). At 608, at least one processor of the processor-based system performs an internal nominal trajectory collision assessment loop. The internal nominal trajectory collision assessment cycle is nested within the external robotic collision assessment cycle. The internal nominal trajectory collision assessment loop allows at least one processor of the processor-based system to assess or estimate a collision probability or likelihood for each of the one or more nominal trajectories for a given robot pair.

At 610, at least one processor of the processor-based system initializes a latency counter K (e.g., k=1). At 612, at least one processor of the processor-based system performs a nested internal lag time collision assessment loop. The nested internal lag time collision assessment loop is nested within the internal nominal trajectory collision assessment loop. The nested internal lag time collision assessment loop allows at least one processor of the processor-based system to assess or estimate the impact 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, a nominal trajectory introducing a hysteresis time equal to zero and introducing a plurality (one, two or more) of non-zero hysteresis times may be evaluated to determine the probability or likelihood of collision if a trajectory corresponding to the nominal trajectory introducing the respective hysteresis time is performed. Continuously longer lag times can be evaluated.

At 614, at least one processor of the processor-based system uses the generated swept volumes to perform collision assessment on the respective trajectories that introduce a lag time (e.g., for zero and non-zero lag times). For example, at least one processor of the processor-based system can determine whether respective swept volumes intersect, where the respective swept volumes correspond to respective volumes swept by robots of a pair of robots when performing a nominal trajectory that introduces a lag time equal to zero and each of a plurality of non-zero lag times. For example, for each of the two or more robots, the processor-based system is capable of performing collision assessment between i) at least a portion of the respective sample trajectories representing the respective nominal trajectories of the robots that introduce at least one respective lag time (e.g., zero lag time and at least one non-zero lag time), and ii) at least a portion of each respective sample of the respective trajectories of each of the other robots of the two or more robots, wherein at least a portion of the respective samples of each of the respective trajectories of each of the other robots of the two or more robots, wherein at least one respective lag time (e.g., zero lag time and at least one non-zero lag time) is introduced into the respective trajectories of each of the other robots of the two or more robots. Thus, for each of the robots and each of the nominal trajectories, all permutations of "candidate" lag times can be evaluated, e.g., identifying when the probability or likelihood of a collision equals or exceeds a certain collision detection threshold.

While collision assessment is described in terms of swept volumes, the teachings herein are not necessarily limited thereto, and the methods and systems can employ various other collision assessment or detection techniques or algorithms.

At 616, at least one processor of the processor-based system determines whether the robot of the given pair would or would likely cause a collision based on the collision assessment. In at least some embodiments, the collision assessment can produce a non-binary value that represents a chance or probability of collision. Whether a collision is likely or not can be determined based on the non-binary value being above a defined collision detection threshold (e.g., >50% collision probability, >10% collision probability, >5% collision probability). In 617, in response to determining that a collision has been detected or is likely to occur (e.g., the collision probability is equal to or greater than the collision detection threshold), the processor-based system can identify and/or store previous lag time values that did not result in a potential collision, and optionally exit the nested internal lag time collision assessment loop 612, returning control to the top of the internal nominal trajectory collision assessment loop 608. Thus, for example, in response to determining that a collision will occur or is likely to occur between a robot and at least one other robot of the two or more robots, for one or more nominal trajectories of at least one robot of the two or more other robots that have been determined to be colliding, the processor-based system identifies as the respective acceptable lag time a respective lag time that is less than a respective lag time that results in a determination that a collision will occur, wherein the acceptable lag reflects a maximum acceptable lag in gesture timing relative to the nominal trajectories that still ensures that movement of the robot through a gesture sequence specified by the respective nominal trajectory remains collision-free relative to movement of other robots of the two or more robots. In response to determining that a collision has been detected or is likely to be detected (e.g., the collision probability is equal to or greater than the collision detection threshold), control passes directly to 618.

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

At 622, at least one processor of the processor-based system determines whether all trajectories of a given robot pair have been processed (e.g., j=m. If all trajectories for a given robot pair have not been processed, the trajectory counter is incremented at 624 (e.g., j=j+1), and control returns to the top of the internal nominal trajectory collision assessment loop 608. If all nominal trajectories have been processed (e.g., j=m), control passes to 626.

At 626, at least one processor of the processor-based system determines if additional robot pairs are needed for processing. The method 600 may process each permutation of robot pairs, each permutation of trajectories of the robot pairs, and each permutation of candidate lag times, at least until a stop condition is reached (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 respective selected trajectories of each other robot operating in the shared workspace and the determined acceptable lag times 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 additional robot pairs remain to be processed, control passes to 628, where a new robot pair is selected, and control passes to the top of the external robot pair collision assessment cycle. If there are no remaining robot pairs to process, control passes directly to 630.

At 630, at least one processor of the processor-based system returns a respective acceptable lag time for the one or more nominal trajectories. For example, the acceptable lag time can be stored in a non-transitory processor-readable medium, e.g., in one or more data structures associated with the nominal trajectory. Control then passes to 632.

At 632, method 600 may terminate, for example, until called again. Although method 600 is described in terms of an ordered flow, in many embodiments, various acts or operations will be performed concurrently or in parallel, and/or additional acts can be included and/or some acts omitted.

To determine a respective acceptable lag time for the nominal trajectory, for example, the processor-based system can iterate each of the plurality of candidate lag times in order from a relatively smaller candidate lag time to a relatively larger candidate lag time, at least until a stop condition is reached, iterate the nominal trajectory over each of the plurality of times, and check for collisions between one of the two or more robots and at least one other of the two or more robots based on a current one of the candidate lag times. 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 other of the two or more robots, the processor-based system can set a respective acceptable lag time for the robot determined to be in collision with a nominal trajectory of at least one of the other of the two or more robots to be the closest previous candidate lag time (e.g., a lag time with a collision probability below a collision detection threshold that indicates an acceptable collision risk). To check for collisions, for example, the processor-based system can determine whether the swept volume of one robot in the robot pair intersects the swept volume of the other robot in the robot pair. For example, the processor-based system can generate a collision indication in response to determining that a swept volume of one robot of the pair of robots intersects a swept volume of the other robot of the pair of robots, and identifying a robot determined to be in collision.

Exemplary methods of determining and applying acceptable hysteresis times to provide a safety margin are set forth below.

First, a motion plan comprising a set of nominal trajectories (Trj (t)) is generated using, for example, the optimization described in international patent application PCT/US2021/013610 (publication No. WO2021150439 A1). Thus, for each mobile robot r in the motion plan, an acceptable lag time (e.g., maximum safety lag value #)). It is important to note that (i) acceptable lag time values for each robot r [ (]) May be different (e.g.,) (Ii) acceptable lag time value [ ]) Strictly dependent on the relative positions of a set of nominal trajectories Trj (t) and robot r, and (iii) static obstacles and static robots, if any, do not affect acceptable lag time values). In this example, a set of nominal trajectories Trj (t) and acceptable lag time values are calculated sequentially) And preferably off-line during a configuration time prior to run-time, however, this is not intended to limit the methods described herein. During execution (e.g. online; during run time) a central clock (t) is implemented, which is common to all robots running in the shared workspace. For each robot r, calculate the hysteresis relative to the nominal motion plan at a high frequency #) That is, the monitoring of the actual lag time is performed at a sufficiently high frequency relative to the movement speed of the robot to avoid an undesired actual collision.

In an ideal situation, each robot r is completely synchronous with the motion plan, and the actual lag of the robot is zero). However, in general, one or more robots may fall behind the plan, where the current robot state is determined by the trajectoryAnd actual hysteresisGiven.

The processor-based system monitors the actual hysteresis value to ensure the safety of the robotic system. If all of the actual hysteresis values are within the safety margin specified by the acceptable hysteresis time (e.g.,) Then it is considered safe to continue execution since no self-collision condition is ensured. Otherwise, the safety of the system is considered to be impaired because no self-collision condition is ensured.

To keep the robot in a safe state all the time, the system may monitor the actual hysteresis value and simply stop the movement of the entire robot system when a safety margin (e.g., a margin or threshold) is exceeded. To safely restart the operation, the robot can move to a set of nominal trajectoriesIs (are) and the central clock is reset to。

Less damaging solutions can include taking remedial or corrective action to the robot while it is still at a safe boundary but relatively close to a limit. For example, the movement (increasing speed) of the robot that is about to reach the limit can be accelerated to reduce the value of its actual lag time. This measure will directly increase the distance from the limit and increase the safety level. Alternatively, other robots can be decelerated. This measure may take advantage of the time expansion of the central clock to maintain consistency. The mixing measures may also be very effective.

Exemplary processor-executable algorithms for determining the safety margin are listed in the pseudo code below.

For better understanding, the algorithm can be divided into 4 parts:

● main_loop, which spans candidate hysteresis values from 0 to L, and iterates over the nominal track Trj (t).

● CheckLagCollision () to evaluate the effect of candidate hysteresis values applied at a particular time t. Given a set of candidate hysteresis values for each of the robots, it is determined whether there is any robot collision at a given time t. In areas without hysteresis, the robot occupies a volume determined by its current pose. Currently, with hysteresis, the robot can sweep the volume based on the trajectory it takes from the pose at time t-lag to time t.

● ComputeSweptVolume _r (t 1, t 2) calculating the swept volume of the robot r as it moves along the path from time t1 to time t2)。

● VolumesExcept () geometrically searches for an intersection between the two volumes.

Main_loop () and CheckLagCollision () will be described in detail below. ComputeSweptVolume _r () and VolumesIntersect () are not described in detail since they can be implemented using many algorithms.

The inputs include: a set of collision free trajectories for N robots, Δt: sampling time, T: maximum duration of robot activity, Δl: sample lag time value searched, and L: maximum lag value searched (L < = T).

The output includes a maximum hysteresis value for each robot that ensures no self-collision motion between robots。

The internal variables include lag_candidate, the hysteresis value evaluated in the current iteration; Hysteresis values evaluated by each robot in the current iteration; Each robot evaluating a hysteresis value in a previous iteration; each robot stops the boolean value of the search.

Fig. 7 illustrates a method 700 of operation of a processor-based system for generating or selecting a motion plan for one or more robots to operate in a shared workspace based at least in part on an acceptable lag time and optionally based at least in part on other criteria, in accordance with at least one illustrated embodiment. The lag time and optionally other criteria can be expressed as a cost or cost function. For example, the method 700 can be performed during a configuration or "pre-run" time, i.e., a time at which some or all of the movement planning occurs, e.g., generating a nominal trajectory and/or movement plan for each robot. The configuration or "pre-run" time may precede a run time, which is the time that one or more robots execute the corresponding motion plan. This advantageously allows some of the most computationally intensive work to be performed before run time, as the response capability is not of particular concern at this time. In at least some implementations, the method 700, or portions thereof, is performed during a runtime (i.e., a time at which one or more robots are performing tasks) subsequent to a configuration time or a pre-runtime.

The method 700 of determining an acceptable lag time begins at 702, for example, in response to a start-up or power-up of the system or a component thereof, receipt of information or data, or a call or enablement of a calling routine or program.

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

As previously described, any of a variety of techniques and/or algorithms can be employed to generate the nominal trajectory, e.g., a sample-based motion planner (SBMP), such as a Probabilistic Roadmap (PRM) or fast-exploring random tree (RRT, RTT x s), stable sparse RRT x (SST x), and/or fast-matching tree (FMT). Advantageously, the teachings herein include computationally efficient use of a determined lag time to select a set of nominal trajectories for a motion plan to enhance robustness of operation.

In 706, at least one processor of the processor-based system initializes a robot counter I, e.g., sets the robot counter equal to an integer value of 1. At 708, at least one processor of the processor-based system performs an external robotic processing iteration loop, performing an iteration on each of the two or more robots to operate in the shared workspace, or until a stop condition is reached (e.g., determining a maximum lag time to ensure collision-free motion).

At 710, at least one processor of the processor-based system initializes a nominal trace counter J, e.g., sets the nominal trace counter equal to an integer value of 1. At 712, at least one processor of the processor-based system performs an internal nominal trajectory processing iteration loop, performing an iteration for each nominal trajectory of the given robot. The inner nominal trajectory process iteration loop 712 is nested within the outer robotic process iteration loop 708.

In 714, at least one processor of the processor-based system determines a respective acceptable lag time for the current nominal trajectory J of the current robot I. The respective acceptable lag time reflects the maximum acceptable delay or lag in the current nominal trajectory J, which delay or lag still ensures a non-self-crashing movement of the current robot I relative to the respective movement according to the respective nominal trajectory, at least when the current robot I (the current robot of the outer robot processing iteration loop) performs the current nominal trajectory J (the current nominal trajectory of the inner current nominal trajectory iteration loop), wherein the respective acceptable lag time is introduced into the current nominal trajectory J of the current robot I. Preferably, this can be evaluated with respect to the nominal trajectories of other robots that introduce various candidate lag times (e.g., zero and non-zero lag times) or even, if known, corresponding acceptable lag times. As long as all other robots are running on or within their respective nominal trajectories (i.e. lag time = 0), or all other robots are running on or within their respective nominal trajectories that introduce respective lag times, an acceptable lag time for a given robot I can ensure that no self-collision occurs. Thus, in at least one embodiment, as long as the respective current actual lag time of a given robot is less than the respective acceptable lag time of the robots, and the other robots are traveling in their nominal trajectories, the robots will not collide with each other (ensuring that no self-collision between robots occurs). Thus, in at least one preferred embodiment, the robots will not collide with each other (ensuring that no self-collision between robots occurs) as long as the respective current actual lag time of all robots is less than the respective acceptable lag time of each robot.

At 716, at least one processor of the processor-based system determines whether each of the nominal trajectories of the given robot is considered, e.g., determines whether the nominal trajectory counter J is equal to the nominal trajectory total number of the given robot (e.g., j=m. If each of the nominal trajectories of the given robot has not been considered, control passes to 718 where the nominal trajectory counter is incremented (e.g., j=j+1), 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 nominal trajectory (e.g., j=m) of a given robot I has been considered, control passes directly to 720.

At 720, at least one processor of the processor-based system selects a maximum value of a set of determined acceptable lag times determined for a given robot I. At 722, at least one processor of the processor-based system provides one or more determined acceptable lag times (e.g., provides a selected maximum of the determined acceptable lag times) for 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 latencies to a different processor, or transmitting one or more determined acceptable latencies to a different register of a processor, or otherwise storing it in a non-transitory processor readable medium.

At 724, at least one processor of the processor-based system determines whether each of the robots is considered, e.g., whether the robot counter I is equal to the total number of robots (e.g., i=n. If each of the robots has not been considered (e.g., I < N), control passes to 726, at which point 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 external iterative robot processing loop 708 to consider the next robot. If each of the robots has been processed (e.g., i=n), control passes directly to 728.

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

When multiple trajectories for each robot are considered, the acceptable lag time (e.g., maximum lag time) determined for any given robot can be a function of the respective selected trajectories for each of the other robots operating in the shared workspace and the determined acceptable lag times associated with those selected trajectories. Thus, as described herein, in at least some embodiments, the system determines an acceptable lag time for each robot and each candidate trajectory for that robot given all other possible combinations of candidate trajectories and candidate lag times for all other robots. Once completed, the system (e.g., nominal trajectory analyzer 258 of fig. 2) can select a set of trajectories for all robots operating in the shared workspace. The system (e.g., nominal trajectory analyzer 258 of fig. 2) can divide the set of trajectories, for example, by optimizing an objective function (e.g., a maximum sum of all lag times for all robots).

At 730, at least one processor of the processor-based system provides a respective motion plan to each robot or each motion controller to cause the robot to move according to the respective motion plan. For example, this can include providing a motion plan to a respective motion controller of each of the one or more robots.

At 732, method 700 may terminate, for example, until called again. Although method 700 is described in terms of an ordered flow, in many embodiments, various acts or operations will be performed concurrently or in parallel, and/or additional acts can be included and/or some acts omitted.

Thus, for example, the processor-based system can determine, for each of the two or more robots, and for each of the two or more nominal trajectories of the respective robots, a respective acceptable lag time for the nominal trajectory that reflects a maximum acceptable delay in pose timing relative to the nominal trajectory that still ensures that movement of the robot through the pose sequence specified by the nominal trajectory remains collision-free relative to movement of the respective pose sequence specified by the respective nominal trajectory of each of the other robots because the nominal trajectory itself of each of the other robots is delayed by the respective acceptable lag time. For example, the processor-based system may select between two or more nominal trajectories based at least in part on respective acceptable lag times for the two or more nominal trajectories, and provide a motion plan for a respective robot based at least in part on the selected one nominal trajectory to control operation of the respective robot of the two or more robots. For example, the processor-based system can select a nominal trajectory for a respective robot that has the greatest acceptable lag time among two or more nominal trajectories, thereby generating a more robust motion plan than otherwise. For example, the processor-based system can select the nominal trajectories based on respective cost functions representing acceptable lag times and optional collision risks or probabilities each associated with a respective nominal trajectory of two or more nominal trajectories of a respective robot. For example, the processor-based system can select the nominal trajectory based on a respective cost function that represents an acceptable lag time, risk or probability of collision, and optionally severity of collision, each associated with a respective nominal trajectory of two or more nominal trajectories of the respective robot. For example, the processor-based system can select the nominal trajectory based on a respective cost function that represents at least one of an acceptable lag time, risk or probability of collision, severity of collision, and optionally at least one of an acceptable lag time, risk or probability of collision, severity of collision, and at least one of an acceptable energy consumption, each variable in the cost function representing an acceptable energy consumption, a corresponding energy consumption, and a corresponding time of collision, the variables being weighted in the respective cost function. For example, the processor-based system can select a respective nominal trajectory for each of the two or more robots to maximize an overall acceptable lag time for all of the two or more robots. For example, the processor-based system can select a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is generally optimized for all of the two or more robots, wherein each cost function represents an acceptable lag time and at least a risk or probability of collision each associated with a respective nominal trajectory of the two or more nominal trajectories of the respective robot. For example, the processor-based system can select a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is generally optimized for all of the two or more robots, wherein each cost function represents an acceptable lag time, at least a risk or probability of collision, and a severity of collision, each associated with a respective nominal trajectory of the two or more nominal trajectories of the respective robot. For example, the processor-based system can select a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is generally optimized for all of the two or more robots, wherein each cost function represents an acceptable lag time, at least a risk or probability of a collision, a severity of a collision, each associated with a respective nominal trajectory of the two or more nominal trajectories of the respective robot, and at least one of a duration or energy consumption of completion, wherein each variable in the cost function represents an acceptable lag time, a risk or probability of a collision, respectively, The severity of the collision, and at least one of the duration of completion or energy consumption, these variables being weighted in a corresponding cost function.

For example, the processor-based system can determine a respective acceptable lag time for the nominal trajectory that reflects a maximum acceptable delay in pose timing relative to the nominal trajectory that still ensures that movement of the robot through the nominal trajectory-specified pose sequence remains free of self-collisions with two or more robots in the shared workspace, which can include performing collision assessment for each of the two or more robots.

For example, the processor-based system can perform collision assessment between i) representing at least a portion of a respective sample trajectory of the robot that introduces a respective nominal trajectory of at least one respective lag time, ii) at least a portion of a respective sample of each of the respective trajectories of each of the other of the two or more robots, wherein at least one respective lag time is introduced into the respective trajectory of each of the other of the two or more robots.

Fig. 8 illustrates a method 800 of operation of a processor-based system for controlling operation of a robot operating in a shared workspace based at least in part on an acceptable lag time, in accordance with at least one illustrated embodiment. In accordance with at least one illustrated embodiment, a processor-based system includes one or more processors that monitor an actual lag time compared to an acceptable lag time, and if

The actual lag time exceeds a threshold, one or more remedial actions are optionally taken. Method 800 may be performed, for example, after performance of method 300 (fig. 3), method 400 (fig. 4), method 500 (fig. 5), method 600 (fig. 6), and/or method 700 (fig. 7). For example, the method 800 can be performed during runtime, i.e., during the time when one or more robots are performing respective motion plans and/or performing tasks. For example, the runtime can be after a configuration or "pre-run" time during which part or all of the motion planning can be performed, e.g., generating a nominal trajectory and/or motion plan for each robot.

The method 800 begins at 802, for example, in response to a start-up or power-up of a system or component thereof, receipt of information or data, or a call or enablement of a calling routine or program.

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

At 806, at least one processor of the processor-based system causes the one or more robots to execute the respective motion plans. For example, the at least one processor can provide 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., motors, solenoids, valves, pumps) that are coupled to drive various links of the robot to move the robot or portions thereof.

At 808, at least one processor of the processor-based system monitors an amount of lag time (actual lag time) of a respective actual trajectory performed by a respective one of the robots as compared to a respective nominal trajectory. As previously described, the actual trajectories are actual sequences of poses performed by the respective robots and the timings of these poses. 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 trajectory of one or more robots lags the timing of the poses specified by the respective nominal trajectories of the respective robots. Monitoring can be performed in any of a variety of ways. For example, the processor-based system can use inputs sensed via one or more sensors positioned to sense the position and/or movement and/or pose or configuration or state of the robot in the shared workspace. The sensor is capable of monitoring the entire workspace, e.g., the sensor takes the form of a camera, video camera, stereo camera, motion detector, etc., which is positioned and has a field of view that covers all or at least a portion of the shared workspace. The sensors can additionally or alternatively monitor the position and/or movement and/or pose or configuration or state of a particular robot, including, for example, any one or more of a camera, video camera, motion detector, position encoder or rotary encoder, hall effect sensor, and/or reed switch (REED SWITCHES) associated with one or more joints, links, and/or actuators of the robot. The one or more processors are capable of performing processing (e.g., machine vision processing) to monitor the actual trajectory. Additionally or alternatively, the processor-based system can use information from a robot control system and/or a drive system (e.g., motor controller, pneumatic controller, hydraulic controller, etc.) representing control signals (e.g., PWM motor control signals) for driving the robot or portions thereof and/or use feedback signals (e.g., back EMF) received from the robot or the drive system of the robot. The one or more processors can perform processing (e.g., machine vision processing) to determine a corresponding actual lag time for the actual trajectory.

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

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

For example, to take at least one remedial action, at least one processor of the processor-based system, when executing the processor-executable instructions, is capable of causing the processor to one or more of stopping movement of the one or more robots, slowing movement of the one or more robots, and/or speeding movement of the one or more robots. For example, the at least one processor can stop the movement of one, two, more or even all robots. Also, for example, the at least one processor can slow down the movement of one, two, more or even all robots. Also, for example, the at least one processor may accelerate the movement of one, two, more or even all robots. Also, for example, the at least one processor can stop movement of the one or more robots while slowing movement of the one or more robots. Also, for example, the at least one processor can stop movement of the one or more robots while accelerating or keeping the movement of the one or more robots constant. Also, for example, the at least one processor can slow down movement of the one or more robots while speeding up movement of the one or more robots or keeping movement of the one or more robots constant. Also, for example, the at least one processor can stop movement of the one or more robots while slowing movement of the one or more robots while speeding movement of the one or more robots or keeping movement of the one or more robots constant. The term "keeping the movement constant" means that the nominal trajectory of the robot does not change, although the movement speed (i.e. speed and direction) of the robot may change, as this is specified by the nominal trajectory. Also, for example, to take at least one remedial action, at least one processor of the processor-based system, when executing the processor-executable instructions, can cause the processor to perform one or more operations of stopping movement of the one or more robots, advancing the one or more robots along respective trajectories specified by the respective nominal trajectories, and then restarting movement of the robots. Restarting a movement typically involves restarting the movement from where the movement stopped, although in some cases it may involve returning to and restarting from the start of the corresponding trajectory.

Optionally, at 814, at least one processor of the processor-based system monitors an amount of lag time (actual lag time) of the respective actual trajectory performed by the respective robot compared to the respective 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 amount of lag time (i.e., the actual lag time) no longer exceeds a respective margin or threshold (e.g., a determined acceptable lag time; a respective determined percentage of acceptable lag time) for the respective trajectory of the respective robot. The system can enter a wait loop and continue to monitor the amount of lag time (i.e., the actual lag time) until it no longer exceeds the respective margin or threshold (e.g., the determined acceptable lag time; the percentage of the respective determined acceptable lag time) for all robots. Once this condition is reached, control passes to 818.

Optionally, at 818, at least one processor of the processor-based system causes the one or more robots to continue executing (e.g., resume moving) the respective motion plan.

The method 800 terminates at 820, for example, until called again. Although method 800 is described in terms of an ordered flow, in many embodiments, various acts or operations will be performed concurrently or in parallel, and/or additional acts can be included and/or some acts omitted.

The foregoing detailed description has set forth various embodiments of the devices and/or processes via the use of block diagrams, schematics, and examples. Insofar as such block diagrams, schematics, and examples contain one or more functions and/or operations, it will be understood by those within the art that each function and/or operation within such block diagrams, flowcharts, or examples can be implemented, individually and/or collectively, by a wide range of hardware, software, firmware, or any combination thereof. In one embodiment, the present subject matter may be implemented via a boolean circuit, an Application Specific Integrated Circuit (ASIC), and/or an FPGA. However, those skilled in the art will recognize that the embodiments disclosed herein can be implemented, in whole or in part, in a variety of different embodiments in a standard integrated circuit, 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 the circuitry and/or writing the code for the software and/or firmware would be well within the skill of one of ordinary skill in the art in light of this disclosure.

Those of skill in the art will recognize that many of the methods or algorithms described herein may employ additional acts, that some acts may be omitted, and/or that acts may be performed in a different order than specified.

Furthermore, those skilled in the art will appreciate 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 number PCT/US2017/036880, filed on 6/9/2017, international patent application number 5/1/2016, published as WO2016/122840, U.S. patent application number 62/616783, filed on 1/12/2018, U.S. patent application number 62/626939, U.S. patent application number 62/856548, filed on 6/3/2019, U.S. patent application number 62/865,431, filed on 22/1/9/2015/2022, U.S. patent application number 63/327917, filed on 4/6/2021/013610 (published as WO2021150439 A1), and the above are all incorporated herein by reference. These and other changes can be made to the embodiments in light of the above-detailed description. In general, in the following claims, the terms used should not be construed to limit the claims to the specific embodiments disclosed in the specification and the claims, but should be construed to include all possible embodiments along with the full scope of equivalents to which such claims are entitled. Accordingly, the claims are not limited by the present disclosure.

Claims

1. A method of operating in a processor-based system to facilitate operation of a plurality of robots, the method being for use in a multi-robot operating environment in which the plurality of robots are to operate, the method comprising:

For each of the two or more robots,

for each of the one or more nominal trajectories for a respective robot of the two or more robots, the nominal trajectory specifies a respective sequence of poses and pose timings for the respective robot,

determining a corresponding acceptable lag time for the nominal trajectory, the corresponding acceptable lag time reflecting a maximum acceptable delay in gesture timing relative to the nominal trajectory that still ensures that movement of the robot through the sequence of gestures specified by the nominal trajectory remains collision-free relative to movement of the corresponding sequence of gestures specified by the corresponding nominal trajectory of each of the other robots of the two or more robots; and

The acceptable lag time is provided to at least one processor to control operation of each of the two or more robots.

2. The method of claim 1 , wherein determining a corresponding acceptable lag time for the nominal trajectory comprises:

For each of the two or more robots,

For each of the one or more nominal trajectories,

A swept volume representation is generated that represents a volume swept by at least a portion of the robot moving 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 of claim 2, wherein determining the corresponding acceptable lag time of the nominal trajectory further comprises:

Use the resulting swept volume to perform collision evaluation.

4. The method of claim 3, wherein performing collision assessment using the generated swept volume comprises: for each of the two or more robots, performing collision assessment between i) and ii), wherein i) at least a portion of a respective sample trajectory representing a respective nominal trajectory of the robot into which at least one respective lag time is introduced, ii) at least a portion of a respective sample of each of the respective trajectories of each of the other robots of the two or more robots, wherein the at least one respective lag time is introduced into the respective trajectory of each of the other robots of 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 robots of the two or more robots, for one or more nominal trajectories of the robot, a corresponding lag time that is less than the corresponding lag time that caused the determination that a collision will occur is identified as the corresponding acceptable lag time, wherein the acceptable lag time reflects a maximum acceptable delay in gesture timing relative to the nominal trajectory, and the maximum acceptable delay still ensures that the movement of the robot through the gesture sequence specified by the nominal trajectory remains collision-free relative to the movement of the other robots of the two or more robots.

5. The method of 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 robots of the two or more robots, for one or more nominal trajectories of at least one of the other robots of the two or more robots that have been determined to collide, identifying a corresponding lag time that is less than the corresponding lag time that caused the determination that a collision will occur as the corresponding acceptable lag time, wherein the acceptable lag time reflects a maximum acceptable delay in gesture timing relative to the nominal trajectory, and the maximum acceptable delay still ensures that the movement of the robot through the gesture sequence specified by the corresponding nominal trajectory remains collision-free relative to the movement of the other robots of the two or more robots.

6. The method of claim 1 , wherein determining a corresponding acceptable lag time for the nominal trajectory further comprises:

iterating each of the plurality of candidate lags in order from relatively smaller candidate lags to relatively larger candidate lags, at least until a stopping condition is reached,

iterating each of a plurality of times covered by the nominal trajectory,

checking for collision between one of the two or more robots and at least one other of the two or more robots based on a current one of the candidate lag times; and

In response to determining that a collision will occur between one of the two or more robots and at least one other of the two or more robots, setting corresponding acceptable lag times of nominal trajectories of the robot determined to be colliding and at least one other of the two or more robots to the closest previous candidate lag times.

7. The method of claim 6, wherein checking for collision between the robot and other robots based on a current one of the candidate lag times comprises:

For each of the two or more robots,

A collision assessment is performed on at least a portion of a corresponding nominal trajectory of the robot having a current one of the candidate lag times or another previously determined lag time relative to at least a portion of each trajectory of a corresponding trajectory of each of the other robots of the two or more robots having a current one of the candidate lag times.

8. The method of claim 7 , wherein performing a collision assessment of at least a portion of a corresponding nominal trajectory of the robot having a current one of the candidate lag times or another previously determined lag time relative to at least a portion of each trajectory of a corresponding trajectory of each of the other robots of the two or more robots having a current one of the candidate lag times 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 during movement of the robot and the other robots of the two or more robots 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 collision between the robot and the other robots based on a current one of the candidate lag times comprises:

For each of the two or more robots,

generating a swept volume representation representing a volume swept by at least a portion of the robot moving from at least one time in the respective nominal trajectories to another time in the respective nominal trajectories between a set of pose sequences specified by the respective nominal trajectories; and

For each pair of robots among the two or more robots,

determining, for a pose timing specified for a nominal trajectory without any lag time introduced and for a pose timing specified for a nominal trajectory with each of a plurality of candidate lag times introduced into the corresponding nominal trajectory, whether a swept volume of one of the pair of robots intersects a swept volume of the other of the pair of robots, at least until an intersection is detected, and

In response to determining that a swept volume of one of the pair of robots intersects a swept volume of the other of the pair of robots and identifying the robots determined to have collided, a collision indication is generated.

10. The method according to claim 1, further comprising:

For each of the two or more robots,

For each actual trajectory of the one or more actual trajectories executed by the corresponding robot,

monitoring an amount of lag between a nominal trajectory and a corresponding actual trajectory executed by the corresponding robot;

determining whether the monitored amount of lag exceeds a corresponding determined acceptable lag time of a corresponding actual trajectory of the corresponding robot; and

In response to the monitored amount of lag exceeding a corresponding determined acceptable lag time for a corresponding trajectory of the corresponding robot, at least one remedial action is taken.

11. The method of claim 10, wherein taking at least one remedial action comprises at least one or more of: stopping the movement of one or more of the robots, slowing down the movement of one or more of the robots, and speeding up the movement of one or more of the robots.

12. The method of claim 10, wherein taking at least one remedial action comprises stopping movement of the robot, advancing one or more of the robots along respective trajectories specified by respective nominal trajectories, and then restarting movement of the robot.

13. The method of claim 10, wherein the determining the respective acceptable lag times of the nominal trajectories occurs during a configuration time prior to movement of at least two robots as specified by one or more nominal trajectories of the respective robots.

14. The method of claim 13, wherein the amount of lag between the monitored nominal trajectories and the respective actual trajectories executed by the respective robots occurs during a runtime during which the at least two robots are executing movements specified by one or more nominal trajectories of the respective robots, the runtime being after the configuration time.

15. The method of claim 10, wherein the monitoring the amount of lag between the nominal trajectory and the corresponding actual trajectory executed by the corresponding robot comprises using a central clock common to the monitors of each of the one or more robots.

16. The method according to any one of claims 1 to 15 and any combination thereof, further comprising:

A respective motion plan is received for each of the robots, each motion plan specifying a respective one of one or more nominal trajectories for the respective robot, the nominal trajectory representing a respective collision-free path.

17. A processor-based system for facilitating operation of a plurality of robots, the system being for use in a multi-robot operating environment in which the plurality of robots are to 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 16.

18. A processor-based system for configuring a plurality of robots for use in a multi-robot operating environment in which the plurality of robots are to operate, 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 that, when executed by the at least one processor, cause the at least one processor to:

For each of the two or more robots,

determining a corresponding acceptable lag time for the nominal trajectory, the corresponding acceptable lag time reflecting a maximum acceptable delay in gesture timing relative to the nominal trajectory that still ensures that movement of the robot through a sequence of gestures specified by the nominal trajectory remains collision-free relative to movement of a corresponding sequence of gestures specified by a corresponding nominal trajectory of each of the other robots of the two or more robots; and

19. The processor-based system of claim 18, wherein determining a corresponding acceptable lag time for the nominal trajectory comprises:

For each of the two or more robots,

For each of the one or more nominal trajectories,

20. The processor-based system of claim 19, wherein determining a corresponding acceptable lag time for the nominal trajectory further comprises:

Use the resulting swept volume to perform collision evaluation.

21. The processor-based system of claim 20, wherein to perform collision assessment using the generated swept volume, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to perform, for each of the two or more robots, collision assessment between i) and ii), wherein i) at least a portion of a respective sample trajectory representing a respective nominal trajectory of the robot with at least one respective lag time introduced, ii) at least a portion of a respective sample of each of the respective trajectories of each of the other robots of the two or more robots, wherein the at least one respective lag time is introduced into the respective trajectory of each of the other robots of the two or more robots, and

22. The processor-based system of claim 21, wherein, to determine the corresponding acceptable lag time for the nominal trajectory, the processor-executable instructions, when executed by the at least one processor, further cause the at least one processor to:

23. The processor-based system of claim 18, wherein, to determine the corresponding acceptable lag time for the nominal trajectory, the processor-executable instructions, when executed by the at least one processor, further cause the at least one processor to:

iterating each of a plurality of times covered by the nominal trajectory,

24. The processor-based system of claim 23, wherein, to check for collision between the robot and the other robots based on a current one of the candidate lag times, the processor-executable instructions, when executed by the at least one processor, cause the processor to:

For each of the two or more robots,

25. The processor-based system of claim 24, wherein, to perform a collision assessment of at least a portion of a corresponding nominal trajectory of the robot having a current one of the candidate lag times or another previously determined lag time relative to at least a portion of each trajectory of a corresponding trajectory of each of the other robots of the two or more robots having a current one of the candidate lag times, the processor-executable instructions, when executed by the at least one processor, cause the processor to perform 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 during movement of the robot and the other robots of the two or more robots along at least a portion of the corresponding nominal trajectory delayed by the candidate lag time.

26. The processor-based system of claim 23, wherein, to check for collision between the robot and the other robots based on a current one of the candidate lag times, the processor-executable instructions, when executed by the at least one processor, cause the processor to:

For each of the two or more robots,

generating a swept volume representation representing a volume swept by at least a portion of the robot moving from at least one time in the respective nominal trajectories to another time in the respective nominal trajectories between a set of pose sequences specified by the respective nominal trajectories, wherein a current one of the candidate lag times is introduced into the respective nominal trajectories; and

For each pair of robots among the two or more robots,

27. The processor-based system of claim 18, wherein the processor-executable instructions, when executed by the at least one processor, further cause the processor to:

For each of the two or more robots,

In response to the monitored amount of lag exceeding a corresponding determined acceptable lag time for a corresponding trajectory of the corresponding robot, at least one remedial action is caused to occur.

28. The processor-based system of claim 27, wherein, in order to take at least one remedial action, the processor-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, speed up the movement of one or more of the robots.

29. The processor-based system of claim 27, wherein, in order to take at least one remedial action, the processor-executable instructions, when executed by the at least one processor, cause the processor to: stop movement of the robots, advance one or more of the robots along respective trajectories specified by respective nominal trajectories, and then restart movement of the robots.

30. The processor-based system of claim 27, wherein said determining respective acceptable lag times for said nominal trajectories occurs during a configuration time prior to movement of at least two robots as specified by one or more nominal trajectories of respective robots.

31. The processor-based system of claim 30, wherein the amount of lag between the monitored nominal trajectories and the respective actual trajectories executed by the respective robots occurs during a runtime during which the at least two robots are executing moves specified by one or more nominal trajectories of the respective robots, the runtime being after the configuration time.

32. The processor-based system of claim 27, wherein monitoring the amount of lag between a nominal trajectory and a corresponding actual trajectory executed by the corresponding robot comprises using a central clock common to monitors of each of the one or more robots.

33. The processor-based system of any one of claims 18 to 32 and any combination thereof, wherein the processor-executable instructions, when executed by the at least one processor, further cause the processor to:

34. A method of operating in a processor-based system to facilitate operation of a plurality of robots, the method for use in a multi-robot operating environment in which the plurality of robots are to operate, the method comprising:

For each of the two or more robots,

for each of two or more nominal trajectories for a respective robot of the two or more robots, the nominal trajectory specifies a respective sequence of poses and pose timings for the respective robot,

determining a respective acceptable lag time for the nominal trajectory, the respective acceptable lag time reflecting a maximum acceptable delay in gesture timing relative to the nominal trajectory that still ensures that movement of the robot through the sequence of gestures specified by the nominal trajectory remains collision-free relative to movement of a respective sequence of gestures specified by a respective nominal trajectory of each of the other robots of the two or more robots that is delayed by the respective acceptable lag time of the nominal trajectory of at least one of the other robots of the two or more robots;

selecting between the two or more nominal trajectories based at least in part on their respective acceptable lag times; and

A motion plan is provided for the respective robot based at least in part on the selected one of the nominal trajectories to control operation of the respective robot of the two or more robots.

35. A method according to claim 34, wherein, based at least in part on the corresponding acceptable lag times of two or more nominal trajectories for each robot, selecting between the two or more nominal trajectories includes: selecting the nominal trajectory with the largest acceptable lag time among the two or more nominal trajectories of the corresponding robot.

36. The method of claim 34, wherein selecting between two or more nominal trajectories based at least in part on the respective acceptable lag times for the two or more nominal trajectories for each robot comprises selecting a nominal trajectory based on a respective cost function representing the respective acceptable lag times and at least the risk or probability of collision associated with the respective ones of the two or more nominal trajectories for the respective robots.

37. The method of claim 34, wherein selecting between two or more nominal trajectories based at least in part on the respective acceptable lag times for the two or more nominal trajectories for each robot comprises selecting a nominal trajectory based on a respective cost function representing an acceptable lag time, a risk or probability of collision, and a severity of collision, each associated with a respective one of the two or more nominal trajectories for the respective robot.

38. The method of claim 34, wherein selecting between two or more nominal trajectories based at least in part on respective acceptable lag times for the two or more nominal trajectories for each robot comprises selecting a nominal trajectory based on respective cost functions representing respective acceptable lag times, risk or probability of collision, severity of collision, and at least one of duration to completion or energy expenditure associated with respective ones of the two or more nominal trajectories of the respective robots, wherein each variable in the cost function represents respectively the acceptable lag time, risk or probability of collision, severity of collision, and at least one of duration to completion or energy expenditure, and each variable is weighted in the respective cost function.

39. The method of claim 34, wherein selecting between two or more nominal trajectories based at least in part on respective acceptable lag times for the two or more nominal trajectories comprises selecting a respective nominal trajectory for each of the two or more robots such that an overall acceptable lag time for all of the two or more robots is maximized.

40. The method of claim 34, wherein selecting between the two or more nominal trajectories based at least in part on the respective acceptable lag times for each robot comprises selecting a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is optimized overall across all of the two or more robots, wherein each cost function represents an acceptable lag time and at least a risk or probability of collision respectively associated with a respective one of the two or more nominal trajectories for the respective robot.

41. The method of claim 34, wherein selecting between the two or more nominal trajectories based at least in part on the respective acceptable lag times for the two or more nominal trajectories for each robot comprises selecting a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is optimized overall across all of the two or more robots, wherein each cost function represents an acceptable lag time, at least a risk or probability of a collision, and a severity of a collision, respectively, associated with a respective one of the two or more nominal trajectories for the respective robot.

42. The method of claim 34, wherein selecting between two or more nominal trajectories based at least in part on respective acceptable lag times for the two or more nominal trajectories for each robot comprises selecting a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is optimized overall for all of the two or more robots, wherein each cost function represents an acceptable lag time, at least a risk or probability of collision, a severity of collision, and at least one of: duration of completion or energy consumption, respectively, associated with a respective one of the two or more nominal trajectories for the respective robot, wherein each variable in the cost function represents an acceptable lag time, a risk or probability of collision, a severity of collision, and at least one of: duration of completion or energy consumption, respectively, and each variable is weighted in the respective cost function.

43. The method of claim 34, wherein determining a corresponding acceptable lag time for a nominal trajectory that reflects a maximum acceptable delay in posture timing relative to the nominal trajectory, the maximum acceptable delay still ensuring that movement of the robot through the posture sequence specified by the nominal trajectory will remain collision-free, comprises: performing a collision assessment on each of the two or more robots.

44. The method of claim 43, wherein performing a collision assessment on each of the two or more robots comprises:

A collision assessment is performed between i) and ii), wherein i) at least a portion of a respective sample trajectory representing a respective nominal trajectory of the robot into which at least one respective lag time is introduced, and ii) at least a portion of a respective sample of each of the respective trajectories of each of the other robots of the two or more robots, wherein at least one respective lag time is introduced into the respective trajectory of each of the other robots of the two or more robots.

45. The method of claim 44, wherein determining a corresponding acceptable lag time for the nominal trajectory further comprises:

46. The method of claim 45, wherein determining a corresponding acceptable lag time for the nominal trajectory further comprises:

47. A processor-based system for facilitating operation of a plurality of robots, the system for use in a multi-robot operating environment in which the plurality of robots are to 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 34 to 46.

48. A processor-based system for configuring a plurality of robots for use in a multi-robot operating environment in which the plurality of robots are to operate, the processor-based system comprising:

at least one processor; and

For each of the two or more robots,

49. The processor-based system of claim 48, wherein, to select between two or more nominal trajectories for each robot based at least in part on respective acceptable lag times for the two or more nominal trajectories, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to select the nominal trajectory having the greatest acceptable lag time among the two or more nominal trajectories for the respective robot.

50. The processor-based system of claim 48, wherein, to select between two or more nominal trajectories for each robot based at least in part on respective acceptable lag times for the two or more nominal trajectories, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to select a nominal trajectory based on respective cost functions representing respective acceptable lag times and at least a risk or probability of collision associated with respective ones of the two or more nominal trajectories of the respective robot.

51. The processor-based system of claim 48, wherein, to select between two or more nominal trajectories for each robot based at least in part on respective acceptable lag times for the two or more nominal trajectories, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to select a nominal trajectory based on respective cost functions representing respective acceptable lag times, risks or probabilities of collisions, and severity of collisions associated with respective ones of the two or more nominal trajectories of the respective robot.

52. The processor-based system of claim 48, wherein, to select between two or more nominal trajectories for each robot based at least in part on respective acceptable lag times for the two or more nominal trajectories, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to select a nominal trajectory based on a respective cost function representing an acceptable lag time, a risk or probability of collision, a severity of collision, and at least one of duration to completion or energy expenditure, respectively, associated with a respective one of the two or more nominal trajectories of the respective robot, wherein each variable in the cost function represents an acceptable lag time, a risk or probability of collision, a severity of collision, and at least one of duration to completion or energy expenditure, respectively, and each variable is weighted in the respective cost function.

53. The processor-based system of claim 48, wherein, to select between two or more nominal trajectories based at least in part on respective acceptable lag times for the two or more nominal trajectories, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to select a respective nominal trajectory for each of the two or more robots such that an overall acceptable lag time for all of the two or more robots is maximized.

54. The processor-based system of claim 48, wherein, to select between two or more nominal trajectories for each robot based at least in part on respective acceptable lag times for the two or more nominal trajectories, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to select a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is optimized overall across all of the two or more robots, wherein each cost function represents an acceptable lag time and at least a risk or probability of collision respectively associated with a respective one of the two or more nominal trajectories for the respective robot.

55. The processor-based system of claim 48, wherein, to select between two or more nominal trajectories for each robot based at least in part on respective acceptable lag times for the two or more nominal trajectories, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to select a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is optimized across all of the two or more robots, wherein each cost function represents an acceptable lag time, at least a risk or probability of a collision, and a severity of a collision, respectively, associated with a respective one of the two or more nominal trajectories for the respective robot.

56. The processor-based system of claim 48, wherein, to select between two or more nominal trajectories for each robot based at least in part on respective acceptable lag times for the two or more nominal trajectories, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to select a respective nominal trajectory for each of the two or more robots such that a respective cost function for each robot is optimized overall for all of the two or more robots, wherein each cost function represents an acceptable lag time, at least a risk or probability of collision and a severity of collision, and at least one of: duration to completion or energy expenditure, respectively, associated with a respective one of the two or more nominal trajectories of the respective robot, wherein each variable in the cost function represents an acceptable lag time, a risk or probability of collision, a severity of collision, and at least one of: duration to completion or energy expenditure, each variable being weighted in the respective cost function.

57. The processor-based system of claim 48, wherein, in order to determine a corresponding acceptable lag time for a nominal trajectory that reflects a maximum acceptable delay in pose timing relative to the nominal trajectory that still ensures that movement of the robot through the sequence of poses specified by the nominal trajectory will remain collision-free, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to perform a collision assessment for each of the two or more robots.

58. The processor-based system of claim 57, wherein, to perform a collision assessment for each of the two or more robots, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to:

59. The processor-based system of claim 58, wherein, to determine a corresponding acceptable lag time for the nominal trajectory, the processor-executable instructions, when executed by the at least one processor, further cause the at least one processor to:

60. The processor-based system of claim 59, wherein, to determine a corresponding acceptable lag time for the nominal trajectory, the processor-executable instructions, when executed by the at least one processor, further cause the at least one processor to: