HK40072330B - Motion planning for multiple robots in shared workspace - Google Patents

Description

Motion planning for multiple robots in a shared workspace

Technical Field

This disclosure generally relates to robot motion planning, and more particularly to systems and methods for generating motion planning to drive robots, etc., in a shared workspace by performing collision detection through processor circuitry.

Background Technology

Description of related technologies

Motion planning is a fundamental problem in robot control and robotics. Typically, to complete a task without colliding with any obstacles in the operating environment, or to reduce the likelihood of such collisions, motion planning specifies the path a robot can follow from a starting state to a target state. Challenges in motion planning include the ability to execute motion planning very quickly, even as environmental characteristics change. For example, features such as the position or orientation of one or more obstacles in the environment may change over time. Challenges also include performing motion planning using low-cost equipment with low power consumption and limited storage (e.g., memory circuitry, such as processor chip circuitry).

One problem in robotics is the operation of two or more robots in a shared workspace (often called a work cell), where, for example, the robots or their robotic appendages may interfere with each other while performing a task.

One approach to operating multiple robots in a shared workspace can be called a task-level approach. Task-level approaches can employ teaching and repeated training. Engineers can ensure no robot collisions by defining shared portions of the workspace and programming individual robots such that only one robot is in the shared workspace at any given time. For example, when the first robot begins to enter the workspace, it sets a flag. A controller (e.g., a programmable logic controller (PLC)) reads this flag and prevents other robots from moving into the shared workspace until the first robot removes the flag when it exits the workspace. This approach is intuitive, easy to understand, implement, and troubleshoot. However, because the use of task-level collision elimination typically results in at least one robot being idle for a considerable period, this approach inevitably suffers from low throughput, even if it is technically possible for idle robots to perform useful work in the shared workspace.

Another approach to operating multiple robots in a shared workspace employs offline planning to achieve higher throughput than the task-level collision avoidance methods described above. To this end, the system can attempt to solve the planning problem in the combined joint space of all robots or robot appendages. For example, if two 6-DOF appendages are in a workspace, a 12DOF planning problem must be solved. While this approach achieves high performance, the planning can be very time-consuming. The 12DOF problem is too large for conventional motion planning algorithms to be solved using currently available architectures.

One strategy for addressing these issues is to optimize the motion of the first robot/appendage and then manually optimize the motion of the second robot/appendage. This can be done by iteratively simulating the motion to ensure that the robots/appendages do not collide with each other, which can take many hours of computation. Furthermore, if modifications to the workspace cause a change in the trajectory of one of the robots/appendages, the entire workflow must be re-validated.

Summary of the Invention

The structures and algorithms described in this paper facilitate the operation of two or more robots operating in a shared workspace or work cell, preventing or at least reducing the risk of collisions between robots or robot appendages as they operate to perform their respective tasks in the shared workspace.

The structure and algorithm described in this paper enable high-degree-of-freedom robots to avoid collisions and continue operating in changing shared environments. An efficient planning method can be accelerated with or without hardware acceleration to generate collision-free motion plans within milliseconds. During task execution, ultrafast "real-time" motion planning allows robot paths to be determined at runtime without the need for training or time-consuming path optimization. This advantageously enables the coordination of multiple robots in a shared workspace.

In at least some implementations, the structures and algorithms described herein can guarantee collision-free robot coordination among multiple robots in a compact, shared workspace. Even at high speeds, all robot components (e.g., robot appendages, end-effectors, end effectors) can maintain collision-free motion.

By performing autonomous planning, the structures and algorithms described herein can advantageously reduce programming work in multi-robot workspaces. In at least some implementations, the operator does not need to program any safety zones, time synchronization, or joint spatial trajectories. Input may be limited to a description of the task to be performed and a geometric model of the robot. Input may also include representations of stationary objects, or optionally objects with unpredictable trajectories (e.g., people).

The structure and algorithm described in this paper can advantageously and dynamically assign tasks to be performed by the robot. One or more target poses may change during task execution. Even if a given robot malfunctions or is obstructed, the overall operation or execution of the task can continue.

In at least some implementations, the structures and algorithms described herein can allow robots to share information, for example via non-proprietary communication channels (e.g., Ethernet connections), which can advantageously facilitate the integration of robots from different manufacturers in a shared workspace.

In at least some embodiments, the structures and algorithms described herein can operate without cameras or other sensing sensors. In at least some embodiments, coordination between robots relies on the robots' geometric models, the robots' ability to communicate their respective motion plans, and the geometric model of the shared workspace. In other embodiments, vision or other sensing may optionally be employed, for example, to avoid people or other dynamic obstacles that may enter or occupy portions of the shared workspace.

A wide variety of algorithms are used to solve motion planning problems. Each of these algorithms typically needs to be able to determine whether a given pose of the robot, or a motion from one pose to another, results in a collision with an obstacle in the robot itself or in the environment. Collision evaluation or checking can be performed "in software" using a processor that executes processor-executable instructions from a stored set of processor-executable instructions to perform the algorithm. Collision evaluation or checking can also be performed "in hardware" using a set of dedicated hardware circuitry (e.g., collision checking circuitry implemented in a field-programmable gate array (FPGA) or application-specific integrated circuit (ASIC)). Such circuitry can, for example, represent the volume swept by the robot/robot appendage or a portion thereof during a corresponding motion or transition between two states (i.e., the swept volume). These circuits can, for example, produce a Boolean evaluation result indicating whether the motion will collide with any obstacles, where at least some obstacles represent volumes swept by other robots operating in a shared workspace while performing the motion or transition.

Aspect 1. A method for controlling multiple robots to operate in a common workspace, wherein the common workspace is a workspace in which the ranges of motion of the robots overlap. The method can be summarized as including:

Generate a first motion plan for robot _R1 among the plurality of robots;

For each of at least one robot _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 2.

Represent at least one obstacle as multiple motions of robot _R1 ;

Collision detection is performed on at least one motion of at least a portion of the robot _Ri , relative to the representation of the at least one obstacle; and

The method generates a first motion plan for robot _Ri based at least in part on collision detection of at least a portion of at least one motion of robot _Ri ; and the method further includes:

Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on the respective first motion plans of the respective robots among the plurality of robots.

Aspect 2. The method according to aspect 1 further includes:

In response to the robot _R1 completing at least one movement, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one movement completed by the robot _R1 .

Aspect 3. The method according to aspect 1 further includes:

In response to any one or more robots _R2 to _Rn completing at least one movement, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one movement completed by the respective robot _R2 to _Rn .

Aspect 4. The method according to aspect 1 further includes:

Generate a second motion plan for robot _R1 among the plurality of robots;

For each of at least one robot _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 2.

Represent at least one obstacle as multiple motions of robot _R1 ;

Collision detection is performed on at least one motion of at least a portion of robot _Ri , relative to a representation of at least one obstacle; and

A second motion plan for robot _Ri is generated, based at least in part on collision detection of at least a portion of at least one motion of robot _Ri ; and the method further includes:

Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on the corresponding second motion plan of the respective robot among the plurality of robots.

Aspect 5. According to the method of aspect 4, wherein the step of generating a first motion plan for robot _R1 to robot _Rn occurs consecutively from i equal to 1 to i equal to n.

Aspect 6. According to the method of aspect 5, wherein the step of generating a second motion plan for robot _R1 to robot _Rn occurs consecutively from i equal to 1 to i equal to n.

Aspect 7. According to the method of aspect 5, wherein the generation of the second motion plan for robot _R1 to robot _Rn does not occur continuously from i equal to 1 to i equal to n.

Aspect 8. The method according to aspect 4, wherein providing signals to control the operation of at least one of the robots _R1 to _Rn , based at least in part on a corresponding first motion plan of a respective robot among the plurality of robots, includes providing a signal to cause a robot _Ri to move ahead of said robot _R1 , and further includes:

In response to robot _Ri completing at least one motion, before generating a second motion plan for robot _R1 among a plurality of robots, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one motion completed by robot _Ri .

Aspect 9. The method according to aspect 1 further includes:

Generate a second motion plan for robot _R1 out of a group of robots;

For some, but not all, of two or more robots _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 3.

Represent at least one obstacle as multiple motions of robot _R1 ;

Collision detection is performed on at least one motion of at least a portion of robot _Ri , relative to a representation of at least one obstacle; and

The method generates a second motion plan for robot _Ri based at least in part on collision detection of at least a portion of at least one motion of robot _Ri ; and the method further includes:

Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on the corresponding second motion plan of the respective robot among the plurality of robots.

Aspect 10. The method according to aspect 9, wherein the generation of a second motion plan is skipped for one of robot _R2 to robot _Rn .

Aspect 11. The method according to aspect 9, wherein, in response to one of the robots _R2 to _Rn being blocked from moving by another robot among the robots _R2 to _Rn , a second motion plan is skipped for the corresponding robot among the robots _R2 to _Rn .

Aspect 12. The method according to aspect 9, wherein, in response to one of the robots _R2 to _Rn having an error state indicating that an error condition has occurred, a second motion plan is skipped for the corresponding robot among robots _R2 to _Rn .

Aspect 13. The method according to aspect 1, wherein representing a plurality of movements of at least robot _R1 as at least one obstacle comprises, for at least one robot Ri ₊₁ , representing the movements of two or more robots from robot _R1 to robot _Ri as obstacles before performing collision detection for at least one movement of robot Ri+ ₁ .

Aspect 14. The method according to aspect 13, wherein representing the motions of two or more robots from robot _R1 to robot _Ri as obstacles before performing collision detection for at least one motion of robot Ri ₊₁ comprises: using a set of sweep volumes previously calculated prior to operation, each sweep volume representing a corresponding volume swept by said portion of the corresponding robot from robot _R1 to robot _Ri as at least a portion of the corresponding robot from robot _R1 to robot _Ri moves along a trajectory represented by the corresponding motion.

Aspect 15. The method according to aspect 13 further includes:

Receive a set of sweep volumes previously calculated before operation, each sweep volume representing the corresponding volume swept by at least a portion of the _{corresponding} robot from robot _R1 to robot _Ri as _the respective robot moves along a trajectory represented by the corresponding motion.

Aspect 16. The method according to aspect 13, wherein representing the motions of two or more robots from robot _R1 to robot _Ri as obstacles before performing collision detection for at least one motion of robot Ri ₊₁ comprises: representing the motions of two or more robots from robot _R1 to robot _Ri as at least one of an occupied grid, a hierarchical tree, or an Euclidean distance field.

Aspect 17. The method according to aspect 1, wherein representing each of the movements of at least robot _R1 as at least one obstacle comprises: representing the corresponding movement using a corresponding sweep volume, the sweep volume corresponding to the volume swept by at least a portion of at least robot _R1 during the corresponding movement, and wherein performing collision detection for at least one movement of at least a portion of robot _Ri with respect to the representation of the at least one obstacle comprises performing collision detection using a representation of a sweep volume previously calculated prior to operation, the sweep volume representing the corresponding volume swept by said portion of robot _Ri when said portion of robot _Ri moves along the trajectory represented by the corresponding movement.

Aspect 18. The method according to aspect 1 further includes:

For each of the multiple robots, from robot _R1 to robot _Rn , the corresponding robot is represented by a corresponding motion planning graph. Each motion planning graph includes multiple nodes and edges, where the nodes represent the corresponding states of the corresponding robot, and the edges represent the effective transitions between the corresponding states represented by the corresponding node pairs connected by the edges.

Aspect 19. A system for controlling the operation of multiple robots in a common workspace, wherein the common workspace is a workspace in which the ranges of motion of the robots overlap. The system can be summarized as including:

At least one processor; and

At least one non-volatile storage medium communicatively connected to the at least one processor, and storing processor-executable instructions that, when executed by the at least one processor, cause the at least one processor to:

Generate a first motion plan for robot _R1 among the plurality of robots;

For each of at least one robot _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 2.

Represent at least one obstacle as multiple motions of robot _R1 ;

Collision detection is performed on at least one motion of at least a portion of the robot _Ri , relative to the representation of the at least one obstacle; and

A first motion plan for robot _Ri is generated, based at least in part on collision detection of at least one motion of at least a portion of the robot _Ri ; and further:

Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on the respective first motion plans of the respective robots among the plurality of robots.

Aspect 20. The system according to aspect 19, wherein, when executed by the at least one processor, the processor-executable instructions cause the at least one processor to further:

In response to the robot _R1 completing at least one movement, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one movement completed by the robot _R1 .

Aspect 21. The system according to aspect 19, wherein, when executed by the at least one processor, the processor-executable instructions cause the at least one processor to further:

In response to any one or more robots _R2 to _Rn completing at least one movement, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one movement completed by the respective robot _R2 to _Rn .

Aspect 22. The system according to aspect 19, wherein, when executed by the at least one processor, the processor-executable instructions cause the at least one processor to further:

Generate a second motion plan for robot _R1 among the plurality of robots;

For each of at least one robot _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 2.

Represent at least one obstacle as multiple motions of robot _R1 ;

Collision detection is performed on at least one motion of at least a portion of robot _Ri , relative to a representation of at least one obstacle; and

A second motion plan for robot _Ri is generated, based at least in part on collision detection of at least one motion of at least part of robot _Ri ; and further:

Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on the corresponding second motion plan of the respective robot among the plurality of robots.

Aspect 23. The system according to aspect 22, wherein the step of generating a first motion plan for robot _R1 to robot _Rn occurs consecutively from i equal to 1 to i equal to n.

Aspect 24. The system according to aspect 23, wherein the step of generating a second motion plan for robot _R1 to robot _Rn occurs consecutively from i equal to 1 to i equal to n.

Aspect 25. The system according to aspect 23, wherein the generation of the second motion plan for robot _R1 to robot _Rn does not occur continuously from i equal to 1 to i equal to n.

Aspect 26. The system according to aspect 22, wherein, in order to control the operation of at least one of the robots _R1 to _Rn based at least in part on a corresponding first motion plan of the respective robots among the plurality of robots, the processor is executable instructions, when executed by the at least one processor, such that the at least one processor provides a signal to move a robot _Ri before the robot _R1 , and further:

In response to robot _Ri completing at least one motion, before generating a second motion plan for robot _R1 among a plurality of robots, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one motion completed by robot _Ri .

Aspect 27. The system according to aspect 19, wherein the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to further:

Generate a second motion plan for robot _R1 out of a group of robots;

For some, but not all, of two or more robots _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 3.

Represent at least one obstacle as multiple motions of robot _R1 ;

Collision detection is performed on at least one motion of at least a portion of robot _Ri , relative to a representation of at least one obstacle; and

A second motion plan for robot _Ri is generated, based at least in part on collision detection of at least one motion of at least a portion _thereof ; and further:

Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on the corresponding second motion plan of the respective robot among the plurality of robots.

Aspect 28. The system according to aspect 27, wherein a second motion plan is generated for one of robot _R2 to robot _Rn .

Aspect 29. The system according to aspect 27, wherein, in response to one of robots _R2 to _Rn being blocked from moving by another robot among robots _R2 to _Rn , a second motion plan is skipped for the corresponding robot among robots _R2 to _Rn .

Aspect 30. The system according to aspect 27, wherein, in response to one of the robots _R2 to _Rn having an error state indicating that an error condition has occurred, a second motion plan is skipped for the corresponding robot among robots _R2 to _Rn .

Aspect 31. The system according to aspect 19, wherein, in order to represent multiple movements of at least robot _R1 as at least one obstacle, the processor executable instructions, when executed by the at least one processor, cause the at least one processor to: represent the movements of two or more robots from robot R1 to robot _Ri as obstacles before performing collision detection for at least one movement of robot _{Ri +1 .}

Aspect 32. The system according to aspect 31, wherein, in order to represent the motion of two or more robots _R1 to _R1 as an obstacle, the processor is executable instructions, when executed by the at least one processor, such that the at least one processor: uses a set of sweep volumes previously calculated prior to operation, each sweep volume representing a corresponding volume swept by said portion of the respective robot _R1 to _R1 as at least a portion of the respective robot _R1 to _R1 moves along a trajectory represented by the respective motion.

Aspect 33. The system according to aspect 31, wherein, when executed by the at least one processor, the processor-executable instructions cause the at least one processor to further:

Receive a set of sweep volumes previously calculated before operation, each sweep volume representing the corresponding volume swept by at least a portion of the _{corresponding} robot from robot _R1 to robot _Ri as _the respective robot moves along a trajectory represented by the corresponding motion.

Aspect 34. The system according to aspect 31, wherein, in order to represent the motions of two or more robots from robot _R1 to robot _Ri as obstacles before performing collision detection for at least one motion of robot Ri ₊₁ , the processor executable instructions, when executed by the at least one processor, cause the at least one processor to: represent the motions of two or more robots from robot _R1 to robot _Ri as at least one of an occupied grid, a hierarchical tree, or an Euclidean distance field.

Aspect 35. The system according to aspect 19, wherein, in order to represent each of the movements of at least robot _R1 as at least one obstacle, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to: represent the corresponding movement using a corresponding sweep volume, the sweep volume corresponding to the volume swept by at least a portion of at least robot _R1 during the corresponding movement, and wherein, in order to perform collision detection for at least one movement of at least a portion of robot _Ri relative to the representation of the at least one obstacle, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to: perform collision detection at least in part based on a representation of a sweep volume previously calculated prior to operation, the sweep volume representing the corresponding volume swept by said portion of robot _Ri when at least a portion of robot _Ri moves along the trajectory represented by the corresponding movement.

Aspect 36. The system according to aspect 19, wherein for each of a plurality of robots, from robot _R1 to robot _Rn , the respective robot is represented by a corresponding motion planning graph, each motion planning graph comprising a plurality of nodes and edges, the nodes representing a corresponding state of the respective robot, and the edges representing valid transitions between corresponding states represented by corresponding node pairs connected by the edges in the corresponding node pairs.

Attached Figure Description

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

Figure 1 is a schematic diagram of a robot system according to an embodiment shown. The robot system includes multiple robots operating in a shared workspace to perform tasks and includes a motion planner that dynamically generates motion plans for the robots by taking into account the planned motions of other robots. The robot system may optionally include a perception subsystem.

Figure 2 is a functional block diagram of an environment according to one of the illustrated embodiments, in which a first robot is controlled by a robot control system that includes a motion planner that provides motion plans to other motion planners of other robots, and also includes a separate planning map source that is different from the motion planner.

Figure 3 is an example motion planning diagram in C-space for a robot operating in a shared workspace according to one of the illustrated embodiments.

Figure 4 is a flowchart illustrating an operation method for generating motion planning maps and sweep volumes in a processor-based system according to at least one of the illustrated embodiments.

Figures 5A and 5B are flowcharts illustrating a method for generating motion plans and optionally controlling the operation of multiple robots in a shared workspace in a processor-based system according to one of the illustrated embodiments.

Figure 6 is a flowchart illustrating a method for generating motion plans and optionally controlling the operation of multiple robots in a shared workspace in a processor-based system according to at least one of the illustrated embodiments.

Detailed Implementation

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

Unless the context otherwise requires, throughout the specification and appended claims, the word “comprising” and its variations shall be interpreted as open-ended and encompassing, i.e., “including but not limited to”.

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

As used in this specification and the appended claims, unless otherwise expressly provided, the singular forms “a,” “an,” and “the” include the plural referents. It should also be noted that, unless the context clearly specifies otherwise, the term “or” is generally used to mean “and/or.”

As used in this specification and the appended claims, when used in the context of whether a collision will occur or result in, the term “determine” and its variations mean to assess or predict whether a given pose or movement between two poses via multiple intermediate poses will result in a collision between a part of the robot and an object (e.g., another part of the robot, a part of another robot, a persistent obstacle, a transient obstacle such as a person).

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

Figure 1 illustrates a robot system 100 according to one of the illustrated embodiments, which includes multiple robots 102a, 102b, 102c (collectively referred to as 102) operating in a shared workspace 104 to perform tasks.

Robot 102 can take any of a variety of forms. Typically, the robot will take the form of or have one or more robotic appendages. Robot 102 may include one or more links with one or more joints, and actuators (e.g., electric motors, stepper motors, solenoids, pneumatic actuators, or hydraulic actuators) coupled to and operable to move the links in response to control or drive signals. Pneumatic actuators may, for example, include one or more pistons, cylinders, valves, air reservoirs, and/or pressure sources (e.g., compressors, blowers). Hydraulic actuators may, for example, include one or more pistons, cylinders, valves, fluid reservoirs (e.g., low-compressibility hydraulic fluid), and/or pressure sources (e.g., compressors, blowers). Robot system 100 may take other forms of robot 102, such as autonomous vehicles.

Although in some limited embodiments, the shared workspace 104 may represent a two-dimensional space, it generally represents a three-dimensional space in which robots 102a-102c can operate and move. The shared workspace 104 is a volume or region in which at least a portion of robots 102 can overlap in space and time or collide without controlling movement to avoid collisions. Note that workspace 104 differs from the corresponding “configuration space” or “C-space” of robots 102a-102c, which will be described below, for example, with reference to FIG3.

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

Robot system 100 may include one or more robot control systems 109a, 109b, 109c (three shown, 109 in total), each robot control system including one or more motion planners, such as corresponding motion planners 110a, 110b, 110c (three shown, 110 in total) for each robot 102a, 102b, 102c. In at least some embodiments, a single motion planner 109 may be used to generate motion plans for two, more, or all robots 102. Motion planners 110 are communicatively connected to control the respective robots among the robots 102. The motion planner 110 is also communicatively coupled to receive various types of input, such as robot geometry models 112a, 112b, 112c (also referred to as kinematic models, collectively referred to as 112), task messages 114a, 114b, 114c (collectively referred to as 114), and other representations 116a, 116b, 116c (collectively referred to as 116) of motion planning or movement for other robots 102 operating in the shared workspace 104. The robot geometry model 112 defines the geometry of a given robot 102, for example, in terms of its respective C-space and/or joints, degrees of freedom, and dimensions (e.g., link lengths). (As shown in Figure 2, the conversion from robot geometry model 112 to motion planning diagrams can occur before operation or task execution, for example, performed by a processor-based system that uses any of a variety of technologies different from and separate from robot system 100). The task message 114 specifies the task to be performed, for example, based on the final pose, final configuration, or final state and/or intermediate pose, intermediate configuration, or intermediate state of the respective robot 102. An attitude, configuration, or state can be defined, for example, based on the joint positions and joint angles/rotations of the respective robot 102 (e.g., joint pose, joint coordinates).

Motion planner 110 is optionally communicatively connected to receive static object data 118a, 118b, 118c (collectively referred to as 118) as input. Static object data 118 is representative of static objects in workspace 104 (e.g., size, shape, location, space occupied), which may be, for example, known a priori. Static objects may include, for example, one or more fixed structures in the workspace, such as stakes, pillars, walls, ceilings, floors, conveyor 106. Because robot 102 operates in a shared workspace, the static objects are generally the same for each robot. Therefore, in at least some embodiments, the static object data 118a, 118b, 118c provided to motion planner 110 will be the same. In other embodiments, the static object data 118a, 118b, 118c provided to motion planner 110 for each robot may differ, for example, based on the position or orientation of robot 102 in the environment or the environmental perspective of robot 102. Additionally, as described above, in some embodiments, a single motion planner 110 can generate motion plans for two or more robots 102.

The motion planner 110 is optionally communicatively connected to receive, for example, sensing data 120 provided by the sensing subsystem 124 as input. The sensing data 120 represents static and/or dynamic objects in the workspace 104 that are unknown prior to the data. The sensing data 120 may be raw data sensed by one or more sensors (e.g., cameras 122a, 122b) and/or converted into a digital representation of obstacles by the sensing subsystem 124.

The optional perception subsystem 124 may include one or more processors that can execute one or more machine-readable instructions that cause the perception subsystem 124 to generate a corresponding discretized representation of the environment in which the robot 102 will operate to perform tasks in various different scenarios.

Optional sensors (e.g., cameras 122a, 122b) provide raw sensing information (e.g., point clouds) to the perception subsystem 124. The optional perception subsystem 124 can process the raw sensing information, and the resulting sensing data can be provided as point clouds, occupied meshes, boxes (e.g., bounding boxes), or other geometric objects, or a voxel stream representing obstacles present in the environment (i.e., a “voxel” is equivalent to a 3D or volumetric pixel). The representation of obstacles can optionally be stored in on-chip memory. The sensing data 120 can indicate which voxels or sub-volumes (e.g., boxes) are occupied in the environment at the current time (e.g., runtime). In some embodiments, when representing a robot or another obstacle in the environment, the corresponding surface of the robot or obstacle (e.g., including other robots) can be represented as voxels or polygonal meshes (typically triangles). In some cases, it is advantageous to represent objects as boxes (rectangular prisms, bounding boxes) or other geometric objects. Because objects are not randomly shaped, the organization of voxels can exhibit a large amount of structure; many voxels in an object are adjacent to each other in 3D space. Therefore, representing an object as a box may require far fewer bits (i.e., perhaps only the x, y, z Cartesian coordinates of the two opposite corners of the box). Furthermore, performing an intersection test on a box is comparable in complexity to performing an intersection test on a voxel.

At least some implementations can combine the outputs of multiple sensors, and the sensors can provide very fine-grained voxelization. However, in order for the motion planner to perform motion planning effectively, coarser voxels (i.e., "processor voxels") can be used to represent the environment and the volume in 3D space swept by the robot 102 or parts thereof when transitioning between various states, configurations, or poses. Thus, the optional perception subsystem 124 can accordingly transform the outputs of the sensors (e.g., cameras 122a, 122b). For example, the outputs of cameras 122a, 122b can use 10-bit precision per axis, so each voxel directly derived from cameras 122a, 122b has a 30-bit ID, and there are 2 ^{^30} sensor voxels. For an 18-bit processor voxel ID, system 200a (FIG. 2) can use 6-bit precision per axis, and there will be 2 ^{^18} processor voxels. Thus, for example, each processor voxel can have 2 ^{^12} sensor voxels. During runtime, if system 200a determines that any sensor voxel within the processor voxel is occupied, system 200a considers the processor voxel to be occupied and generates an occupancy grid accordingly.

In Figure 1, various communication paths are indicated by arrows. Communication paths can take the form of, for example, one or more wired communication paths (e.g., electrical conductors, signal buses, or optical fibers) and/or one or more wireless communication paths (e.g., via RF or microwave radios and antennas, infrared transceivers). Note that each of the motion planners 110a-110c is communicatively connected to each other, directly or indirectly, to provide motion planning for a corresponding one of the robots 102a-102c to the other motion planners 110a-110c. For example, the motion planners 110a-110c can be communicatively connected to each other via a network infrastructure, such as a non-proprietary network infrastructure (e.g., Ethernet network infrastructure) 126. This advantageously allows robots from different manufacturers to operate in a shared workspace.

The term "environment" refers to the robot's current workspace, which is a shared workspace in which two or more robots operate. This environment may include obstacles and/or workpieces (i.e., objects that the robot interacts with, acts upon, or works with). The term "task" refers to a robot task in which the robot transitions from posture A to posture B without colliding with obstacles in its environment. This task may involve grasping or not grasping an object, moving or placing an object, rotating an object, or retrieving or placing an object. The transition from posture A to posture B may optionally include transitions between one or more intermediate postures. The term "scenario" refers to a class of environment/task pairs. For example, a scenario could be "a pick-and-place task between obstacles of a given size and shape in an environment with a 3-foot table or conveyor belt, between x and y obstacles." Many different task/environment pairs may conform to these criteria, depending on the location of the target and the size and shape of the obstacles.

Motion planner 110 is operable to dynamically generate motion plan 116, enabling robot 102 to perform a task in the environment while taking into account the planned motions of other robots 102 (e.g., motion represented by the corresponding motion plan 116 or the resulting sweep volume). When generating motion plan 116, motion planner 110 may optionally consider representations of prior static objects 118 and/or perception data 120. Optionally, motion planner 110 may consider the motion state of other robots 102 at a given time, such as whether another robot 102 has already completed a given motion or task, and allow recalculation of the motion plan based on the motion or task being completed by one of the other robots, thereby making previously excluded paths or trajectories available. Optionally, motion planner 110 may consider the operational conditions of robot 102, such as the occurrence or detection of a fault condition, the occurrence or detection of an obstruction condition, and/or the occurrence or detection of a request to accelerate, delay, or skip motion plan.

Figure 2 illustrates an environment according to one of the illustrated embodiments, in which a first robot control system 200a includes a first motion planner 204a that generates a first motion plan 206a to control the operation of a first robot 202, and provides the first motion plan 206a and/or motion representations as obstacles to other motion planners 204b of other robot control systems 200b via at least one communication channel (indicated by the approaching arrows, e.g., transmitter, receiver, transceiver, radio, router, Ethernet) to control other robots (not shown in Figure 2).

Similarly, other motion planners 204b of other robot control systems 200b generate other motion plans 206b to control the operation of other robots (not shown in Figure 2) and provide these other motion plans 206b to other motion planners in the first motion planner 204a and other motion planners 204b of the robot control system 200b. Motion planners 204a and 204b can also receive motion completion messages 209 indicating when the movements of various robots 202 have been completed. This allows motion planners 204a and 204b to generate new or updated motion plans based on the current or updated state of the environment. For example, after the first robot 202 has completed part or all of its movements as part of a task performed by the first robot, a portion of the shared workspace can become available for the second robot to perform a task.

Robot control systems 200a and 200b may be communicatively connected, for example, via at least one communication channel (indicated by a proximate arrow, e.g., transmitter, receiver, transceiver, radio, router, Ethernet) to receive motion planning diagram 208 and/or sweep volume representation 211 from one or more sources 212. According to one illustrated embodiment, the source 212 of motion planning diagram 208 and/or sweep volume representation 211 may be separate and distinct from motion planners 204a and 204b. The source 212 of motion planning diagram 208 and/or sweep volume representation 211 may, for example, be one or more processor-based computing systems (e.g., server computers) that can be operated or controlled by the respective manufacturer of robot 202 or by some other entity. Motion planning graph 208 may each include a set of nodes 214 (only two are shown in Figure 2) and a set of edges 216 (only two are shown in Figure 2). Nodes 214 represent the state, configuration, or pose of the corresponding robot, and edges 216 connect the nodes 214 of the corresponding node pair 214 and represent a legal or valid transition between states, configurations, or poses. A state, configuration, or pose may, for example, represent a set of joint positions, orientations, poses, or coordinates of each joint of each robot 202. Therefore, each node 214 may represent the pose of the robot 202 or a portion thereof, defined entirely by the pose of the joints comprising the robot 202. Motion planning graph 208 may be determined, set, or limited before operation (i.e., limited before task execution), for example, before operation or during configuration time. Sweep volume 211 represents the corresponding volume that the robot 202 or a portion thereof will occupy when performing a movement or transition corresponding to the corresponding edge of motion planning graph 208. The swept volume 211 can be represented in any of a variety of forms, such as voxels, Euclidean distance fields, or hierarchical structures of geometry. This advantageously allows some of the most computationally intensive work to be performed before runtime, when responsiveness is not particularly important.

Each robot 202 may include a set of links, joints, end-effectors or end effectors and/or actuators 218a, 218b, 218c (three collectively shown as 218) operable to move the links about the joints. Each robot 202 may also 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 planning 206a) and provide drive signals to drive the actuators 218.

Each robot 202 may have its own robot control system 200a, 200b, or a robot control system 200a may perform motion planning for two or more robots 202. For illustrative purposes, a robot control system 200a will be described in detail. Those skilled in the art will recognize that this description can be applied to similar or even identical other instances of other robot control systems 200b.

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

The robot control system 200a can also be communicatively connected to one or more remote computer systems, such as server computers (e.g., the source of motion planning graph 212), desktop computers, laptop computers, ultra-portable computers, tablet computers, smartphones, wearable computers, and/or sensors (not shown in Figure 2), which are directly or indirectly communicatively connected to the components of the robot control system 200, for example, via network interface 227. The remote computing system (e.g., the server computer (e.g., the source of motion planning graph 212)) can be used to program, configure, control, or otherwise interact with or input data (e.g., motion planning graph 208, sweep volume 211, task specification 215) to or to the robot control system 200a and the components within the robot control system 200. Such connectivity can be achieved through one or more communication channels, such as one or more wide area networks (WANs), such as Ethernet or the Internet using Internet Protocol. As described above, pre-run calculations (e.g., generation of motion planning graph families) can be performed by a system independent of the robot control system 200a or the robot 202, while runtime calculations can be performed by the processor 222 of the robot control system 200, which in some embodiments may be on the robot 202.

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

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

Executable instructions and data can be stored in system memory 224a, such as operating system 236, one or more application programs 238, other programs or modules 240, and program data 242. Application program 238 may include processor-executable instructions that cause processor 212 to perform one or more of the following: generating a discretized representation of the environment in which robot 202 will operate (including obstacles and/or target objects or workpieces in the environment), where planned movements of other robots can be represented as obstacles; generating motion plans or route maps, including requesting or otherwise obtaining the results of collision assessments, setting cost values for edges in the motion planning graph, and evaluating available paths in the motion planning graph; and/or optionally storing multiple determined motion plans or route maps. Motion planning construction (e.g., collision detection or assessment, updating the costs of edges in the motion planning graph based on collision detection or assessment, and path search or assessment) can be performed as described herein (e.g., referring to Figures 4 and 5A and 5B) and by reference incorporated herein. Collision detection or assessment can be performed using various structures and techniques described elsewhere herein. Application 238 may also include one or more machine-readable and machine-executable instructions that cause processor 222 to perform other operations, such as optionally processing sensed data (captured by sensors). Application 238 may also include one or more machine-executable instructions that cause processor 212 to perform various other methods described herein and in references incorporated herein by reference.

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

Although shown in Figure 2 as stored in system memory 224a, the operating system 236, application program 238, other programs/modules 240, and program data 242 can be stored on other non-volatile computer or processor-readable media, such as drive 224b.

The motion planner 204a of the robot control system 200a may include dedicated motion planner hardware, or may be implemented wholly or partially by the processor 222 and processor-executable instructions stored in the system memory 224a and/or the driver 224b.

The motion planner 204a may include or implement a motion converter 250, a collision detector 252, a cost setter 254, and a path analyzer 256.

Motion converter 250 converts the motion of other robots into a representation of obstacles. Motion converter 250 receives motion plans 204b or other representations of motion from other motion planners 200b. Motion converter 250 then determines the area or volume corresponding to the motion. For example, the motion converter can convert the motion into a corresponding sweep volume, i.e., the volume swept by the respective robot or a part thereof as it moves or transitions between postures represented by the motion plan. Advantageously, motion planner 250 can simply queue obstacles (e.g., sweep volumes) and may not need to determine, track, or indicate the timing of corresponding motions or sweep volumes. While described as a motion converter 250 of a given robot 202 converting the motion of other robots 202b into obstacles, in some embodiments, other robots 202b may provide the given robot 202 with an obstacle representation (e.g., a sweep volume) for a specific motion.

Collision detector 252 performs collision detection or analysis to determine whether a transformation or movement of a given robot 202 or a part thereof will result in a collision with an obstacle. As mentioned above, the movement of other robots can advantageously be represented as an obstacle. Therefore, collision detector 252 is able to determine whether the movement of one robot will result in a collision with another robot moving in a shared workspace.

In some implementations, collision detector 252 performs software-based collision detection or evaluation, such as performing bounding box-to-bounding box collision evaluation or evaluation based on a hierarchical structure of the geometry (e.g., a sphere) of the volume swept by the robot 202, 202b, or a portion thereof during movement. In some implementations, collision detector 252 implements hardware-based collision detection or evaluation, for example, by employing a set of dedicated hardware logic circuits to represent obstacles and a flow representation of motion through the dedicated hardware logic circuits. In hardware-based collision detection or evaluation, the collision detector may employ one or more configurable arrays of circuits (e.g., one or more FPGAs 258) and may optionally generate Boolean collision evaluations.

Cost setter 254 can set or adjust edge costs in the motion planning graph based at least in part on collision detection or evaluation. For example, cost setter 254 can set higher cost values for edges representing transitions between states or movements between poses that cause or may cause a collision. Similarly, cost setter 254 can set lower cost values for edges representing transitions between states or movements between poses that do not cause or may not cause a collision. Setting costs can include setting cost values logically associated with the corresponding edges through some data structure (e.g., fields, pointers, tables).

Path analyzer 256 can use a motion planning graph with cost values to determine paths (e.g., optimal or optimized). For example, path analyzer 256 can be configured as a minimum-cost path optimizer to determine the lowest or lower-cost path between two states, configurations, or poses (represented by corresponding nodes in the motion planning graph). Considering the cost value associated with each edge representing the probability of collision, path analyzer 256 can use or execute any kind of path-finding algorithm, such as a minimum-cost path-finding algorithm.

Various algorithms and structures can be used to determine the minimum-cost path, including those implementing the Bellman-Ford algorithm. However, other algorithms and structures can also be used, including but not limited to any process where the minimum-cost path is determined as the path between two nodes in motion planning graph 208 that minimizes the sum of the costs or weights of its constituent edges. This process improves the motion planning techniques of robots 102 and 202 by using motion planning graphs that represent the motion of other robots as obstacles and collision detection, thereby increasing efficiency and response time, and finding the “optimal” path to perform the task without collisions.

The motion planner 204a may optionally include a cutter 260. The cutter 260 may receive information indicating that another robot has completed a motion, referred to herein as a motion completion message 209. Alternatively, a flag may be set to indicate completion. In response, the cutter 260 may remove an obstacle or part of an obstacle indicating that the motion is now completed. This may allow the generation of new motion plans for a given robot, which may be more efficient or allow the given robot to focus on performing a task previously prevented by the motion of another robot. This approach advantageously allows the motion converter 250 to ignore the timing of motion when generating obstacle representations of motion, while still achieving better throughput than using other techniques. The motion planner 204a may also send signals, cues, or triggers such that, in the event of a change in a given obstacle, the collision detector 252 performs a new collision detection or evaluation to generate an updated motion plan graph (in which the edge weights or costs associated with the edges have been changed), and causes the cost setter 254 and the path analyzer 256 to update cost values and determine new or modified motion plans accordingly.

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

Processor 212 and/or motion planner 204a may be or may include any logic processing unit, such as one or more central processing units (CPUs), digital signal processors (DSPs), graphics processing units (GPUs), application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), programmable logic controllers (PLCs), etc. Non-limiting examples of commercial computer systems include, but are not limited to, Celeron, Core, Core 2, Itanium, and Xeon series microprocessors from U.S. companies; K8, K10, Bulldozer, and Bobcat series microprocessors from AMD; A5, A6, and A7 series microprocessors from Apple Computer; Snapdragon series microprocessors from Qualcomm; and SPARC series microprocessors from Oracle. The construction and operation of the various structures shown in Figure 2 can be realized or employ structures, techniques and algorithms similar to those described in or adopted in International Patent Application No. PCT/US2017/036880, filed on June 9, 2017, entitled “MOTION PLANNING FOR AUTONOMOUSVEHICLES AND RECONFIGURABLE MOTION PLANNING PROCESSORS”; or in the application filed on January 5, 2016, entitled “SPECIALIZED ROBOT MOTION PLANNING HARDWARE”. International Patent Application Publication No. WO 2016/122840 entitled “AND METHODS OF MAKING AND USINGSAME”; and/or U.S. Patent Application No. 62/616,783 entitled “APPARATUS, METHOD AND ARTICLE TO FACILITATE MOTION PLANNING OF AN AUTONOMOUS VEHICLE IN AN ENVIRONMENT HAVING DYNAMIC OBJECTS”, filed on January 12, 2018.

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

Motion planning operations may include, but are not limited to, generating or converting one, more, or all of the following into digital form: a representation of the robot geometry based on geometric model 112 (FIG. 1) and task 114 (FIG. 1); and a representation of the volume (e.g., sweep volume) occupied by the robot in various states or poses and/or during movement between states or poses, wherein the digital form is, for example, a point cloud, an Euclidean distance field, a data structure format (e.g., a hierarchical format, a non-hierarchical format), and/or a curve (e.g., a polynomial or spline representation). Motion planning operations may optionally include, but are not limited to, generating or converting one, more, or all of the following into digital form: a representation of a static or persistent obstacle 118 (FIG. 1) and/or a perceived data representation of a static or transient obstacle 120 (FIG. 1), wherein the digital form is, for example, a point cloud, an Euclidean distance field, a data structure format (e.g., a hierarchical format, a non-hierarchical format), and/or a curve (e.g., a polynomial or spline representation).

Motion planning operations may include, but are not limited to, using various collision assessment techniques or algorithms (e.g., software-based, hardware-based) to determine or detect or predict collisions in each state or pose of the robot or the robot’s motion between states or poses.

In some implementations, motion planning operations may include, but are not limited to, determining one or more motion plans, motion plans, or route maps; storing the determined plans, motion plans, or route maps; and/or providing plans, motion plans, or route maps to control the operation of the robot.

In one implementation, collision detection or evaluation is performed in response to a function call or similar process, and a Boolean value is returned to it. The collision detector 252 can be implemented by one or more field-programmable gate arrays (FPGAs) and/or one or more application-specific integrated circuits (ASICs) to perform collision detection while achieving low latency, low power consumption, and increased information processing capacity.

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

International patent application No. PCT/US2017/036880, filed on June 9, 2017, entitled "MOTION PLANNING FOR AUTONOMOUS VEHICLES AND RECONFIGURABLE MOTION PLANNING PROCESSORS"; International patent application publication No. WO2016/122840, filed on January 5, 2016, entitled "SPECIALIZED ROBOT MOTION PLANNING HARDWARE AND METHODS OF MAKING AND USING SAME"; and International patent application No. APPARATUS, METHOD AND ARTICLOS, filed on January 12, 2018, entitled "APPARATUS, METHOD AND ARTICLOS". U.S. Patent Application No. 62/616,783, entitled “To Facilitate Motion Planning of an Autonomous Vehicle in an Environment Haring Dynamic Objects,” and U.S. Patent Application No. 62/856,548, filed June 3, 2019, entitled “Apparatus, Methods and Articles to Facilitate Motion Planning in Environment Haring Dynamic Objects,” also describe aspects of perception, mapping, collision detection, and pathfinding that can be employed in whole or in part. Those skilled in the art will understand that the illustrated and other embodiments can be practiced with other system architectures and arrangements and/or other computing system architectures and arrangements, including those of robots, handheld devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, personal computers (“PCs”), networked PCs, microcomputers, mainframes, and the like. Implementation methods or embodiments, or parts thereof (e.g., at configuration time and runtime), can be practiced in a distributed computing environment where tasks or modules are executed by remote processing devices linked via a communication network. In a distributed computing environment, program modules can reside in both local and remote memory storage devices or media. However, where and how specific types of information are stored is important for helping to improve motion planning.

For example, various motion planning solutions "burn" the roadmap (i.e., motion planning graph) into a processor (e.g., an FPGA), and each edge of the roadmap corresponds to a non-reconfigurable Boolean circuit in the processor. The design of "burning" the planning graph into the processor presents a problem: processor circuitry is limited in its ability to store multiple or large planning graphs and is generally not reconfigurable for use with different robots.

One solution provides a reconfigurable design that stores the planning map information in memory. This approach stores the information in memory instead of "burning" it into the circuitry. Another approach uses templated, reconfigurable circuitry instead of memory.

As described above, during the pre-run configuration time, some information (e.g., robot geometry) can be captured, received, input, or provided. The received information can be processed during configuration time to produce processed information (e.g., motion planning graphs), thereby accelerating operations or reducing computational complexity during runtime.

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

Figure 3 shows an example motion planning diagram 300 for robots 102 (Figure 1) and 202 (Figure 2), where the goal of robots 102 and 202 is to perform tasks while avoiding collisions with static and dynamic obstacles, which may include other robots operating in a shared workspace.

Planning diagram 300 includes multiple nodes 308a-308i (represented as open circles in the diagram) connected by edges 310a-310i (represented as straight lines between node pairs in the diagram). Each node implicitly or explicitly represents the time and variables characterizing the state of robots 102 and 202 in their configuration space. The configuration space is often referred to as C-space and is the space representing the state, configuration, or pose of robots 102 and 202 as shown in planning diagram 300. For example, each node may represent the state, configuration, or pose of robots 102 and 202, which may include, but is not limited to, position, orientation, or posture (i.e., position and orientation). The state, configuration, or pose may be represented, for example, by a set of joint positions and joint angles/rotations (e.g., joint pose, joint coordinates) of the joints of robots 102 and 202.

The edges in planning graph 300 represent valid or permitted transitions between these states, configurations, or poses of robots 102 and 202. The edges of planning graph 300 do not represent actual motion in Cartesian coordinates, but rather transitions between states, configurations, or poses in C-space. Each edge of planning graph 300 represents a transition of robots 102 and 202 between corresponding node pairs. For example, edge 310a represents a transition between two nodes. Specifically, edge 310a represents a transition between the state of robots 102 and 202 in a specific configuration associated with node 308b and the state of robots 102 and 202 in a specific configuration associated with node 308c. For example, robots 102 and 202 may currently be in the specific configuration associated with node 308a. Although the nodes are shown as being at different distances from each other, this is for illustrative purposes only and is unrelated to any physical distance. There is no limit to the number of nodes or edges in the planning graph 300. However, the more nodes and edges used in the planning graph 300, the more accurately and precisely the motion planner can determine the best path to perform the task based on one or more states, configurations or poses of the robots 102, 202, because the lowest cost path can be selected from more paths.

Each edge is assigned or associated with a cost value. The cost value can represent a collision assessment with respect to the motion represented by the corresponding edge.

Typically, it is desirable for robots 102 and 202 to avoid certain obstacles, such as other robots in a shared workspace. In some cases, it may be desirable for robots 102 and 202 to contact or approach certain objects in the shared workspace, such as grasping or moving objects or workpieces. Figure 3 illustrates a planning diagram 300, which the motion planner uses to identify the path of robots 102 and 202 when their objective is to move through multiple poses while performing a task (e.g., picking up and placing objects) while avoiding collisions with one or more obstacles.

Obstacles can be represented digitally as, for example, bounding boxes, directed bounding boxes, curves (e.g., splines), Euclidean distance fields, or hierarchical structures of geometric entities. Whichever numerical representation best suits the type of obstacle and the type of collision detection to be performed can itself depend on the specific hardware circuitry employed. In some implementations, the sweep volume in the route map of the master agent 102 is pre-calculated. Examples of collision assessments are described in International Patent Application No. PCT/US2017/036880, filed June 9, 2017, entitled “MOTION PLANNING FOR AUTONOMOUS VEHICLES AND RECONFIGURABLE MOTION PLANNING PROCESSORS”; U.S. Patent Application No. 62/722,067, filed August 23, 2018, entitled “COLLISION DETECTIONUSEFUL IN MOTION PLANNING FOR ROBOTICS”; and International Patent Application Publication No. WO 2016/122840, filed January 5, 2016, entitled “SPECIALIZED ROBOT MOTION PLANNING HARDWARE AND METHODS OF MAKING AND USING SAME”.

The motion planner or a part thereof (e.g., collision detector 252 in Figure 2) determines or evaluates the likelihood or probability that a motion or transition (represented by edges) will result in a collision with an obstacle. In some cases, this determination results in a Boolean value, while in others, it can be represented as a probability.

For nodes in the planning graph 300, where direct transitions between nodes may result in collisions with obstacles, the motion planner (e.g., cost setter 254 of Figure 2) assigns cost values or weights to the edges of the planning graph 300 that transition between these nodes (e.g., edges 310a, 310b, 310c, 310d, 310e, 310f, 310g, 310h), indicating the probability of collision with obstacles. In the example shown in Figure 3, the area with a higher probability is represented as graphical portion 314, but does not correspond to a physical region.

For example, the motion planner can assign a cost value or weight equal to or close to zero to each of the multiple edges of the planning graph 300, where each edge of the planning graph 300 has a probability of colliding with a corresponding obstacle that is lower than a defined collision threshold probability. In this example, the motion planner has assigned zero cost values or weights to some edges in the planning graph 300 that represent the transitions or movements of robots 102, 202, which have no probability of colliding with obstacles or a very low probability of colliding with obstacles. For each edge of the multiple edges of the planning graph 300 whose corresponding probability of colliding with obstacles in the environment is higher than a defined collision threshold probability, the motion planner assigns a cost value or weight that is significantly greater than zero. In this example, the motion planner has assigned cost values or weights greater than zero to those edges in the planning graph 300 with higher probabilities of colliding with obstacles. The specific threshold used for the collision probability can vary. For example, the threshold could be 40%, 50%, 60%, or lower or higher than the collision probability. Furthermore, assigning a value greater than zero to a cost value or weight can include assigning a weight with a magnitude greater than zero that corresponds to the corresponding collision probability. For example, as shown in planning diagram 300, the motion planner has assigned a cost value or weight of 5 to edges 310f and 310i, which have a higher collision probability, but has assigned a cost value or weight of 1 to edges 310p and 310g, which the motion planner determines have a much lower collision probability. In other embodiments, the cost value or weight may represent a binary choice between collision and no collision, with only two cost values or weights available when assigning cost values or weights to edges.

Motion planners can assign, set, or adjust the cost value or weight of each edge based on factors or parameters other than collision probability.

After the motion planner sets cost values or weights representing the probability of collision between robots 102, 202 and obstacles based at least in part on collision assessment, the motion planner (e.g., path analyzer 256 of Figure 2) performs optimization to identify paths 312 in the resulting planning map 300 that provide motion planning for robots 102, 202, with no or low probability of collision with obstacles, including other robots operating in the shared workspace.

In one implementation, once all edge costs of the planning graph 300 have been assigned or set, a motion planner (e.g., path analyzer 256 of FIG. 2) can perform calculations to determine the minimum-cost path to or toward the target state represented by the target node. For example, path analyzer 256 (FIG. 2) can perform a minimum-cost path algorithm from the current state of robots 102, 202 in planning graph 300 to possible states, configurations, or poses. The motion planner then selects the path in planning graph 300 with the minimum cost (closest to zero). As mentioned above, cost can reflect not only the probability of collision but also other factors or parameters. In this example, the current state, configuration, or pose of robots 102, 202 in planning graph 300 is at node 308a, and this path is depicted in planning graph 300 as path 312 (a thick-line path, including the line segment extending from node 308a to node 308i).

Although shown as a path with many sharp turns in planning diagram 300, these turns do not represent corresponding physical turns in the route, but rather logical transitions between the states, configurations, or postures of robots 102, 202. For example, each edge in the identified path 312 may represent a change in state relative to the physical configuration of robots 102, 202 in the environment, but not necessarily a change in direction of robots 102, 202 corresponding to the angle of path 312 shown in Figure 3.

Figure 4 illustrates an operational method 400 for generating motion planning maps and sweep volumes in a processor-based system according to at least one of the illustrated embodiments. Method 400 may be performed prior to operation, for example, during configuration time. Method 400 may be executed by a processor-based system (e.g., a server computer) that is separate from and may be geographically distant from one or more robots and/or one or more robot control systems.

In section 402, a processor-based system receives one or more robot kinematic models. These models provide the geometric specifications for each robot.

In 404, a processor-based system generates a motion planning graph for the robot based on a corresponding robot kinematic model. The motion planning graph represents each state, configuration, or pose of the robot as a corresponding node, and the valid transitions between pairs of states, configurations, or poses as edges connecting the corresponding pairs of nodes. Although described graphically, the motion planning graph does not necessarily need to be represented or stored as a conventional graph, but can be logically represented, or represented in storage circuitry or a computer processor, using any kind of data structure (e.g., records and fields, tables, linked lists, pointers, trees).

In 406, processor-based systems generate sweep volumes for each edge of the motion planning graph. A sweep volume represents the volume swept by the robot or a part thereof when performing a motion or transition corresponding to the respective edge. Sweep volumes can be represented in any of a variety of forms, such as voxels, Euclidean distance fields, spherical hierarchies, or other geometric objects.

At 408, a processor-based system provides motion maps and/or sweep volumes to the robot control system and/or motion planner. The processor-based system can provide motion maps and/or sweep volumes via a non-proprietary communication channel (e.g., Ethernet). In some embodiments, robots from different robot manufacturers can operate in a shared workspace. In some embodiments, each robot manufacturer can operate a proprietary processor-based system (e.g., a server computer) that generates motion maps and/or sweep volumes for each robot manufactured by that manufacturer. Each robot manufacturer is able to provide its own motion maps and/or sweep volumes for use by the robot controller or motion planner.

Figures 5A and 5B illustrate an operational method 500 for generating motion plans and optionally controlling multiple robots operating in a shared workspace in a processor-based system, according to at least one of the illustrated embodiments. Method 500 can be executed at runtime, for example, after a configuration time. Method 500 can be executed by one or more processor-based systems that take the form of one or more robot control systems. The robot control system may, for example, be co-located with or "on" the respective robot.

For example, in response to power on the robot and/or robot control system, in response to a call or reference from a calling routine, or in response to the receipt of a task, method 500 begins at 502.

At 504, the processor-based system may optionally receive one or more motion planning graphs for the robot. For example, the processor-based system may receive the motion planning graph from another processor-based system that generates the motion planning graph during configuration time. The motion planning graph represents each state, configuration, or pose of the robot as a corresponding node and represents valid transitions between pairs of states, configurations, or poses as edges connecting the corresponding nodes. Although described in the form of a graph, each motion planning graph does not necessarily need to be represented or stored as a conventional graph, but can be represented, for example, logically, or in storage circuitry or a computer processor, using any kind of data structure (e.g., records and fields, tables, linked lists, pointers, trees).

In section 506, a processor-based system may optionally receive a set of sweep volumes from one or more robots. For example, the processor-based system may receive this set of sweep volumes from another processor-based system that generates a motion planning graph during configuration time. Alternatively, the processor-based system may generate a set of sweep volumes itself, for example, based on the motion planning graph. A sweep volume represents the corresponding volume swept by the robot or a part thereof when performing a motion or transition corresponding to a corresponding edge. Sweep volumes can be represented in any of a variety of forms, such as voxels, Euclidean distance fields, spherical hierarchies, or other geometric objects.

In 508, a processor-based system receives multiple tasks, for example, in the form of task specifications. The task specifications define the robotic tasks to be performed by the robot. For example, a task specification might specify that the robot moves from a first position to a second position, grasps an object at the second position, moves the object to a third position, and releases the object at the third position. Task specifications can take various forms, such as high-level specifications (e.g., prose and grammar) that need to be parsed down to lower-level specifications. Task specifications can also take the form of low-level specifications, such as specifying a set of joint positions and joint angles/rotations (e.g., joint poses, joint coordinates).

In 510, the processor-based system optionally receives or generates a set or collection of motion planning requests for each of multiple robots _R1 - _RN operating in a shared workspace. The set or collection of requests is named a list or queue of requests, but this does not necessarily mean that the order or arrangement of tasks in the list or queue corresponds to the order in which tasks should or will be performed, completed, or processed. Requests can be generated based on the tasks to be performed by each robot. In some cases, requests in the request queue can be ordered relative to each other, for example, in the case where the first robot should perform a first motion (e.g., release a workpiece at a first position) before the second robot performs a second motion (e.g., grasp a workpiece at a first position).

In 512, for the first queue request I, the processor-based system generates a corresponding motion plan for the corresponding robot (e.g., robot Ri). Generating the motion plan may include, for example, performing collision detection or evaluation, setting the cost values of the edges in the motion planning graph of robot _Ri based on the collision detection or evaluation, and determining the path using the motion planning graph with the cost values, for example, through minimum cost analysis. Although this specification uses the same count for the request and the robot executing the request, this is only for ease of understanding. As described herein, any given request to perform a task can be performed by any given robot capable of performing the corresponding task. For example, the i-th request can be completed by the (i+3)-th robot, for example, the (i+3)-th robot is the one available when the i-th request is served. Typically, there are many more tasks than robots, so any given robot _Ri will execute all requests in the queue except for the i-th request. Therefore, the relationship between requests and robots is not necessarily one-to-one.

In 514, a processor-based system represents motions from motion plans of one or more robots (e.g., robot _Ri ) as obstacles for other robots. For example, a processor-based system can arrange sweep volumes corresponding to each motion as obstacles in an obstacle queue. The sweep volumes may have been previously determined or computed for each edge and are logically associated with each edge in memory via data structures (e.g., pointers). As previously described, sweep volumes can be represented in any of a variety of forms, such as voxels, Euclidean distance fields, spherical hierarchies, or other geometric objects.

In 516, the processor-based system can optionally control the operation of a corresponding robot (for which a motion plan has been generated, such as robot _Ri ). For example, the processor-based system can send control or drive signals to one or more motion controllers (e.g., motor controllers) to cause one or more actuators to move one or more links according to the motion plan.

In 518, the processor-based system can optionally determine whether a corresponding motion has been completed. Monitoring the completion of a motion advantageously allows the processor-based system to disregard obstacle removal corresponding to the motion during subsequent collision detection or evaluation. The processor-based system can rely on the coordinates of the corresponding robot. The coordinates can be based on information from motion controllers, actuators, and/or sensors (e.g., cameras, rotary encoders, reed switches) to determine whether a given motion has been completed.

In 520, a processor-based system responds to determining that a given motion has been completed by generating or sending a motion completion message or setting a flag.

At 522, the processor-based system performs an iterative loop for each additional queued request i+1. In each iteration of the iterative loop, the processor-based system performs one or more of the actions 524 to 544 described below. Although described as an iterative loop, the processor-based system may perform one or more actions of method 500 for each task or motion planning request in the set, list, or queue of task or motion planning requests. Motion planning for any given task or motion planning request may be performed relative to any selected robot, a selection that may be made autonomously by the processor-based system based on one or more criteria, such as those described below with reference to FIG6.

In step 524, the processor-based system determines whether a motion completion message has been generated or received, or whether a flag has been set.

In 526, a processor-based system, in response to determining that a motion completion message has been generated or received, or that a flag has been set, removes one or more obstacles corresponding to a given motion. For example, a processor-based system can remove a corresponding obstacle from an obstacle queue. This advantageously allows collision detection or evaluation to be performed in environments where swept volumes no longer exist as obstacles. It also advantageously allows for tracking of motion and corresponding swept volumes when it is no longer necessary to track the motion or the corresponding swept volume.

In 532, a processor-based system performs collision detection or evaluation for a robot (e.g., Ri ₊₁ ). The processor-based system can perform collision detection or evaluation using any of the various architectures and algorithms described herein or by reference to materials incorporated herein. Collision detection or evaluation may include performing collision detection or evaluation for each motion for each obstacle in an obstacle queue.

In 534, processor-based systems set the cost values of edges in a motion planning graph based at least in part on collision detection or evaluation by the robot (e.g., Ri ₊₁ ). Processor-based systems can perform cost value setting using any of the various structures and algorithms described herein or in materials incorporated herein by reference, typically setting or adjusting the cost of edges with no or low collision risk to lower values (e.g., zero), and setting or adjusting the cost of edges that would result in a collision or have a high collision risk to higher values (e.g., 100,000).

In 536, processor-based systems generate motion plans for robots (e.g., Ri ₊₁ ) based at least in part on collision detection or evaluation. Processor-based systems can generate motion plans using any of the various structures and algorithms described herein or in materials incorporated herein by reference, such as performing a minimum cost analysis on a motion plan graph with a set cost value.

In 538, a processor-based system represents the motion of the current robot (e.g., Ri ₊₁ ) from its motion plan as obstacles for other robots. For example, a processor-based system can arrange the sweep volumes corresponding to each motion as obstacles in an obstacle queue. The sweep volumes may have been previously determined or computed for each edge and are logically associated with each edge in memory via data structures (e.g., fields, pointers). As previously described, sweep volumes can be represented in any of a variety of forms, such as voxels, Euclidean distance fields, spherical hierarchies, or other geometric objects.

At 540, a processor-based system controls the operation of the current robot (generating motion plans for that robot, e.g., robot Ri ₊₁ ). For example, the processor-based system may send control or drive signals to one or more motion controllers (e.g., motor controllers) to cause one or more actuators to move one or more links.

In 542, the processor-based system can optionally determine whether a corresponding motion has been completed. Monitoring the completion of a motion advantageously allows the processor-based system to disregard obstacle removal corresponding to the motion during subsequent collision detection or evaluation. The processor-based system can rely on the coordinates of the corresponding robot. The coordinates can be based on information from motion controllers, actuators, and/or sensors (e.g., cameras, rotary encoders, reed switches) to determine whether a given motion has been completed.

In 544, a processor-based system responds to determining that a given motion has been completed by generating or sending a motion completion message.

In 546, the processor-based system determines whether the end of the queue has been reached. For example, the processor-based system may determine whether there are any remaining motion planning requests in the motion planning request queue, and/or whether all tasks have been completed. In at least some embodiments, the task set (e.g., the task queue) may be temporarily exhausted, and new or additional tasks may arrive later. In such embodiments, the processor-based system may perform a wait loop, periodically checking for new or additional tasks, or waiting for a signal indicating that new or additional tasks can be processed and executed.

Method 500 may terminate at 548. Alternatively, method 500 may be repeated until it definitively stops, for example, due to a power outage or other condition. In some implementations, method 500 may be executed as a multi-threaded process on one or more processors.

Although the operation method 500 is described according to an ordered process, in many embodiments, various actions or operations will be performed simultaneously or in parallel. Typically, when one or more robots perform a task, motion planning for one robot to perform one task can be executed. Therefore, robot task execution may overlap with, or occur simultaneously with, or in parallel with, the motion planning performed by one or more motion planners. Robot task execution may overlap with, or occur simultaneously with, or in parallel with the task execution of other robots. In some embodiments, at least some portions of a robot's motion planning may overlap with, or occur simultaneously with, or in parallel with, at least some portions of the motion planning of one or more other robots.

Figure 6 illustrates a method 600 for generating motion plans and optionally controlling multiple robots operating in a shared workspace in a processor-based system, according to at least one of the illustrated embodiments. Method 600 can be executed at runtime, for example, after a configuration time. Method 600 can be executed by one or more processor-based systems that take the form of one or more robot control systems. The robot control system can, for example, be co-located with or "on" a corresponding robot. Method 600 can be used in conjunction with method 500 (Figures 5A and 5B).

For example, in response to power on the robot and/or robot control system, in response to a call or reference from a calling routine, or in response to the receipt of a task set, list, or queue, method 600 begins at 602.

In section 604, a processor-based system selects tasks from a set, list, or queue of tasks to be performed. These tasks may collectively achieve a common objective. For example, tasks may include picking up and placing objects, while the objective is for two or more robots operating in a shared workspace to sort a pile of objects into two or more distinct piles of objects of corresponding types.

Processor-based systems can select tasks from a set of tasks (e.g., a task queue). These tasks can take the form of motion planning requests, correspond to motion planning requests, or generate motion planning requests based on a specific system architecture. Tasks in the task queue may or may not be ordered. Tasks can be selected based on any one or more criteria, such as the order of one task relative to another to achieve a goal, the priority of a task relative to other tasks, the efficiency of achieving the goal (e.g., time to achieve the goal, energy consumption, number of movements to achieve the goal, ability to operate the robot in parallel, minimizing robot latency), robot availability, and/or the availability of robots suitable for performing specific types of tasks (e.g., the availability of robots with specific types of end-effectors or end effectors).

At 606, the processor-based system selects a robot to perform a selected task. The processor-based system may select a robot based on any one or more criteria, such as robot availability, robot suitability for the task, other robots being unsuitable for performing the task or performing other types of tasks that the robot is unsuitable for, and the presence or absence of conditions (e.g., error conditions, low power conditions, obstruction conditions, wear conditions, scheduled service conditions).

At 608, the processor-based system performs motion planning for a pair of selected tasks and a selected robot. For example, the processor-based system can perform motion planning as generally described in reference method 500 (Figures 5A and 5B).

At 610, the processor-based system determines whether a condition exists that would cause the selected robot to skip or delay the execution of the selected task. Conditions may include error conditions indicating operational or mechanical malfunctions in the selected robot or its corresponding robot control system. Conditions may include obstruction conditions indicating that a given motion of the robot, as instructed by motion planning, is currently blocked or cannot be achieved. Conditions may include low-power conditions, wear conditions, or scheduled service conditions of the selected robot, all of which indicate that the selected robot may not be able to complete the task at a given time. Conditions may also include skip conditions in which the given robot or robot control system asserts coverage of the task or motion planning request. Additionally or alternatively, the processor-based system may handle acceleration conditions including override requests that accelerate a given task or motion planning request, move a given task or motion planning request ahead of other task or motion planning requests in the task or motion planning request queue, or otherwise prioritize a task or motion planning request relative to one or more other task or motion planning requests.

In response to a condition determined at 610 that would cause the selected robot to skip the execution of the selected task, the processor-based system returns control to 606 to select a different robot to perform the selected task. Optionally, control can be passed to 604 to select a new task, with the previous task remaining in the task queue to be executed or being added back to the task queue. This may be helpful in selecting more urgent tasks that may have been added to the task queue during this period.

In response to the determination at 610 that the condition does not exist, control proceeds to 612, where a motion plan for performing the selected task is sent to the selected robot. This can include, for example, providing high-level or low-level instructions (e.g., motor control instructions) to the selected robot via a wired or wireless communication channel.

In section 614, the selected robot performs or implements motion planning. For example, one or more actuators enable the robot's appendages and associated end-effector tools to perform tasks.

In 616, the processor-based system determines whether there are additional tasks or motion planning requests to be served in a set, list, or queue. In at least some embodiments, the task set (e.g., the task queue) may be temporarily exhausted while new or additional tasks may arrive later. In such embodiments, the processor-based system may execute a wait loop, periodically checking for new or additional tasks, or waiting for a signal indicating that new or additional tasks can be processed and executed.

Method 600 may terminate at 618. Alternatively, method 600 may repeat until it is definitively stopped, for example, due to a power outage or other condition. In some implementations, method 600 may be executed as a multi-threaded process on one or more processors. For example, motion planning for multiple tasks may be performed concurrently.

The foregoing detailed description has illustrated various embodiments of the device and/or process using block diagrams, schematic diagrams, and examples. Within the scope of such block diagrams, schematic diagrams, and examples encompassing one or more functions and/or operations, those skilled in the art will understand that each function and/or operation in such block diagrams, flowcharts, or examples can be implemented individually and/or collectively by a wide range of hardware, software, firmware, or virtually any combination thereof. In one embodiment, this subject matter can be implemented using Boolean circuits, application-specific integrated circuits (ASICs), and/or FPGAs. However, those skilled in the art will recognize that the embodiments disclosed herein can be implemented, in whole or in part, in various different ways in standard integrated circuits as one or more computer programs running on one or more computers (e.g., 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 virtually any combination thereof, and that designing circuitry and/or writing code for software and/or firmware according to this disclosure will be entirely within the skill of those skilled in the art.

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

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

The various embodiments described above can be combined to provide further embodiments. All commonly assigned U.S. patent application publications, U.S. patent applications, foreign patents, and foreign patent applications mentioned in this specification and/or listed in the application data sheet, including but not limited to International Patent Application No. PCT/US2017/036880, filed June 9, 2017, entitled “MOTION PLANNING FOR AUTONOMOUS VEHICLES AND RECONFIGURABLE MOTION PLANNING PROCESSORS,” and International Patent Application No. SPECIALIZE, filed January 5, 2016, entitled “SPECIALIZE,” are also included. International patent application No. WO 2016/122840, entitled "D ROBOT MOTION PLANNING HARDWARE AND METHODS OF MAKING AND USING SAME"; and another patent application filed on January 12, 2018, entitled "APPARATUS, METHOD AND ARTICLE TO FACILITATE MOTION PLANNING OF AN AUTONOMOUS VEHICLE IN AN ENVIRONMENT HAVIN U.S. Patent Application No. 62/616,783 entitled "G DYNAMICOBJECTS"; U.S. Patent Application No. 62/626,939 entitled "MOTION PLANNING A ROBOT STORING A DISCRETIZED ENVIRONMENT ON ONE OR MORE PROCESSORS AND IMPROVED OPERATION OF SAME" filed on February 6, 2018; and U.S. Patent Application No. 62/626,939 entitled "APPARATUS, ME" filed on June 3, 2019. The entire contents of U.S. Patent Application No. 62/856,548, entitled “Those and Articles to Facilitate Motion Planning Inner Vironment's Having Dynamic Obstacles,” and U.S. Patent Application No. 62/865,431, filed June 24, 2019, entitled “Motion Planning for Multiple Robots in Shared Workspace,” are incorporated herein by reference. Based on the above detailed description, these and other changes to the embodiments are possible. Generally, the terminology used in the appended claims should not be construed as limiting the claims to the specific embodiments disclosed in the specification and claims, but should be construed as encompassing all possible embodiments and the full scope of equivalents of these claims. Therefore, the claims are not limited by this disclosure.

Claims (34)

1. A method for controlling multiple robots to operate in a common workspace, wherein the ranges of motion of the robots in the common workspace overlap, the method comprising: Generate a first motion plan for robot _R1 among the plurality of robots; For each of at least one of robots _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 2. Represent at least one obstacle as multiple motions of robot _R1 ; Collision detection is performed on at least one motion of at least a portion of robot _Ri , relative to the representation of the at least one obstacle. A first motion plan for robot _Ri is generated, based at least in part on collision detection of at least one motion of at least part of the robot _Ri . Based at least in part on a corresponding first motion plan of a corresponding one of the plurality of robots, signals are provided to control the operation of at least one of the robots _R1 to _Rn ; and In response to the robot _R1 completing at least one movement, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one movement completed by the robot _R1 . 2. The method according to claim 1, further comprising: In response to any one or more robots _R2 to _Rn completing at least one movement, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one movement completed by the corresponding robot _R2 to _Rn . 3. The method according to claim 1, further comprising: Generate a second motion plan for robot _R1 among the plurality of robots; For each of at least one of the robots _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 2. Represent at least one obstacle as multiple motions of robot _R1 ; Collision detection is performed on at least one motion of at least a portion of the robot _Ri , relative to the representation of the at least one obstacle; and A second motion plan for robot _Ri is generated, based at least in part on collision detection of at least a portion of at least one motion of robot _Ri ; and the method further includes: Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on a corresponding second motion plan of a corresponding one of the plurality of robots. 4. The method of claim 3, wherein the step of generating a first motion plan for robots _R1 to _Rn occurs consecutively from i equal to 1 to i equal to n. 5. The method of claim 4, wherein the step of generating a second motion plan for robot _R1 to robot _Rn occurs consecutively from i equal to 1 to i equal to n. 6. The method of claim 4, wherein the generation of the second motion plan for robot _R1 to robot _Rn does not occur continuously from i equal to 1 to i equal to n. 7. The method of claim 3, wherein providing signals to control the operation of at least one of the robots _R1 to _Rn , based at least in part on a corresponding first motion plan of a corresponding one of the plurality of robots, comprises providing a signal to move a robot _Ri ahead of said robot _R1 , and wherein: The representation of an obstacle is updated in response to robot _Ri completing at least one motion to eliminate the portion corresponding to at least one motion completed by robot _Ri before a second motion plan is generated for robot _R1 among a plurality of robots. 8. The method according to claim 1, further comprising: Generate a second motion plan for robot _R1 among multiple robots; For some, but not all, of two or more robots _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 3. Represent at least one obstacle as multiple motions of robot _R1 ; Collision detection is performed on at least one motion of at least a portion of robot _Ri , relative to the representation of the at least one obstacle; and The method generates a second motion plan for robot _Ri based at least in part on collision detection of at least a portion of at least one motion of robot _Ri ; and the method further includes: Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on a corresponding second motion plan of a corresponding one of the plurality of robots. 9. The method of claim 8, wherein the generation of a second motion plan is skipped for one of robot _R2 to robot _Rn . 10. The method of claim 8, wherein, in response to one of the robots _R2 to _Rn being blocked from moving by another robot among the robots _R2 to _Rn , a second motion plan is skipped for the corresponding robot among the robots _R2 to _Rn . 11. The method of claim 8, wherein, in response to one of the robots _R2 to _Rn having an error state indicating that an error condition has occurred, a second motion plan is skipped for the corresponding robot among the robots _R2 to _Rn . 12. The method of claim 1, wherein representing the plurality of motions of at least robot _R1 as at least one obstacle comprises, for at least one robot Ri ₊₁ , representing the motions of two or more robots from robot _R1 to robot _Ri as obstacles before performing collision detection for at least one motion of robot Ri+ ₁ . 13. The method of claim 12, wherein representing the motions of two or more robots from robots _R1 to _R1 as obstacles before performing collision detection for at least one motion of robot R1 ₊₁ comprises: using a set of sweep volumes previously calculated prior to operation, each sweep volume representing a corresponding volume swept by said portion of robot _R1 to _R1 as at least a portion of robot _R1 to _R1 moves along a trajectory represented by the corresponding motion. 14. The method of claim 12, further comprising: Receive a set of sweep volumes previously calculated before operation, each sweep volume representing _the corresponding volume swept by the corresponding portion of robot _R1 to robot _Ri as at least a portion of a _{corresponding} robot moves along a trajectory represented by the corresponding motion. 15. The method of claim 12, wherein representing the motions of two or more robots from robot _R1 to robot Ri as obstacles before performing collision detection for at least one motion of robot _{Ri +1} comprises: representing the motions of two or more robots from robot _R1 to robot _Ri as at least one of an occupied grid, a hierarchical tree, or an Euclidean distance field. 16. The method of claim 1, wherein representing each of the movements of at least robot _R1 as at least one obstacle comprises: representing the corresponding movement using a corresponding sweep volume, the sweep volume corresponding to the volume swept by at least a portion of at least robot _R1 during the corresponding movement, and wherein performing collision detection for at least one movement of at least a portion of robot _R1 with respect to the representation of the at least one obstacle comprises _performing collision detection using a representation of the sweep volume previously calculated prior to operation, the sweep volume representing the corresponding volume swept by said portion of robot _R1 when said portion moves along the trajectory represented by the corresponding movement. 17. The method according to claim 1, further comprising: For each of the plurality of robots, from robot _R1 to robot _Rn , the corresponding robot is represented by a corresponding motion planning graph. Each motion planning graph includes multiple nodes and edges, where the nodes represent the corresponding states of the corresponding robot, and the edges represent valid transitions between the corresponding states represented by the corresponding nodes in the corresponding node pairs connected by the edges. 18. A system for controlling multiple robots to operate in a common workspace, the robots having overlapping ranges of motion in the common workspace, the system comprising: At least one processor; and At least one non-volatile storage medium communicatively connected to the at least one processor, and storing processor-executable instructions that, when executed by the at least one processor, cause the at least one processor to: Generate a first motion plan for robot _R1 among the plurality of robots; For each of at least one of robots _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 2. Represent at least one obstacle as multiple motions of robot _R1 ; Collision detection is performed on at least one motion of at least a portion of the robot _Ri , relative to the representation of the at least one obstacle; and A first motion plan for robot _Ri is generated, based at least in part on collision detection of at least one motion of at least a portion of the robot _Ri ; and further: Based at least in part on a corresponding first motion plan of a corresponding one of the plurality of robots, signals are provided to control the operation of at least one of the robots _R1 to _Rn ; and In response to the robot _R1 completing at least one movement, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one movement completed by the robot _R1 . 19. The system of claim 18, wherein the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to further: In response to any one or more robots _R2 to _Rn completing at least one movement, the representation of the obstacle is updated to eliminate the portion corresponding to the at least one movement completed by the corresponding robot _R2 to _Rn . 20. The system of claim 18, wherein the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to further: Generate a second motion plan for robot _R1 among the plurality of robots; For each of at least one of the robots _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 2. Represent at least one obstacle as multiple motions of robot _R1 ; Collision detection is performed on at least one motion of at least a portion of the robot _Ri , relative to the representation of the at least one obstacle; and A second motion plan for robot _Ri is generated, based at least in part on collision detection of at least one motion of at least part of robot _Ri ; and further: Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on a corresponding second motion plan of a corresponding one of the plurality of robots. 21. The system of claim 20, wherein the step of generating a first motion plan for robot _R1 to robot _Rn occurs consecutively from i equal to 1 to i equal to n. 22. The system of claim 21, wherein the step of generating a second motion plan for robot _R1 to robot _Rn occurs consecutively from i equal to 1 to i equal to n. 23. The system of claim 21, wherein the generation of the second motion plan for robot _R1 to robot _Rn does not occur continuously from i equal to 1 to i equal to n. 24. The system of claim 20, wherein, in order to control the operation of at least one of the robots _R1 to _Rn based at least in part on a corresponding first motion plan of a corresponding one of the plurality of robots, the processor is executable by instructions, when executed by the at least one processor, such that the at least one processor provides a signal to move a robot _Ri ahead of the robot _R1 , and further: In response to robot _Ri completing at least one motion, before generating a second motion plan for robot _R1 among a plurality of robots, the representation of obstacles is updated to eliminate the portion corresponding to the at least one motion completed by robot _Ri . 25. The system of claim 18, wherein the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to further: Generate a second motion plan for robot _R1 among the plurality of robots; For some, but not all, of two or more robots _Ri , i equals 2 to i equals n, where n is the total number of robots in the plurality of robots, and n is an integer equal to or greater than 3. Represent at least one obstacle as multiple motions of robot _R1 ; Collision detection is performed on at least one motion of at least a portion of robot _Ri , relative to the representation of the at least one obstacle; and A second motion plan for robot _Ri is generated, based at least in part on collision detection of at least one motion of at least a portion _thereof ; and further: Signals are provided to control the operation of at least one of the robots _R1 to _Rn , based at least in part on a corresponding second motion plan of a corresponding one of the plurality of robots. 26. The system of claim 25, wherein the second motion plan is skipped for one of robot _R2 to robot _Rn . 27. The system of claim 25, wherein, in response to one of robots _R2 to _Rn being blocked from moving by another robot among robots _R2 to _Rn , a second motion plan is skipped for the corresponding robot among robots _R2 to _Rn . 28. The system of claim 25, wherein, in response to one of the robots _R2 to _Rn having an error state indicating that an error condition has occurred, a second motion plan is skipped for the corresponding robot among the robots _R2 to _Rn . 29. The system of claim 18, wherein, in order to represent at least a plurality of movements of at least robot _R1 as at least one obstacle, the processor executable instructions, when executed by the at least one processor, cause the at least one processor to: represent the movements of two or more robots from robot _R1 to robot _Ri as obstacles before performing collision detection for at least one movement of robot _{Ri +1} . 30. The system of claim 29, wherein, in order to represent the motion of two or more robots _R1 to _R1 as an obstacle, the processor executable instructions, when executed by the at least one processor, cause the at least one processor to: use a set of sweep volumes previously calculated prior to operation, each sweep volume representing a corresponding volume swept by said portion of the corresponding robot _R1 to _R1 as at least a portion of the corresponding robot _R1 to _R1 moves along a trajectory represented by the corresponding motion. 31. The system of claim 29, wherein the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to further: Receive a set of sweep volumes previously calculated before operation, each sweep volume representing _the corresponding volume swept by the corresponding portion of robot _R1 to robot _Ri as at least a portion of a _{corresponding} robot moves along a trajectory represented by the corresponding motion. 32. The system of claim 29, wherein, in order to represent the motions of two or more robots from robot _R1 to robot _Ri as obstacles before performing collision detection for at least one motion of robot Ri ₊₁ , the processor executable instructions, when executed by the at least one processor, cause the at least one processor to: represent the motions of two or more robots from robot _R1 to robot _Ri as at least one of an occupied grid, a hierarchical tree, or an Euclidean distance field. 33. The system of claim 18, wherein, in order to represent each of the movements of at least robot _R1 as at least one obstacle, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to: represent the corresponding movement using a corresponding sweep volume, the sweep volume corresponding to the volume swept by at least a portion of at least robot _R1 during the corresponding movement, and wherein, in order to perform collision detection for at least one movement of at least a portion of robot _R1 relative to the representation of the at least one obstacle, the processor-executable instructions, when executed by the at least one processor, cause the at least one processor to: perform collision detection at least in part based on a representation of the sweep volume previously calculated prior to operation, the sweep volume representing the corresponding volume swept by said portion of robot _R1 when at least a portion of robot _R1 moves along the trajectory represented by the corresponding movement. 34. The system of claim 18, wherein for each of the plurality of robots, _R1 to _Rn , the corresponding robot is represented by a corresponding motion planning graph, each motion planning graph including a plurality of nodes and edges, the nodes representing a corresponding state of the corresponding robot, and the edges representing valid transitions between corresponding states represented by corresponding nodes in a pair of corresponding nodes connected by the edges.