Multi-tool scheduling for cooperative manufacturing

Patent metadata

Field	Value
Publication number	US-10703083-B2
Application number	US-201715406446-A
Country	US
Kind code	B2
Filing date	Jan 13, 2017
Priority date	Jan 13, 2017
Publication date	Jul 7, 2020
Grant date	Jul 7, 2020

Abstract

Methods, systems, and apparatus, including medium-encoded computer program products, for synchronizing the manufacture of objects using two or more separate tools include, in at least one aspect, determining tasks to be performed in a shared build volume to manufacture a 3D object, assigning the tasks to respective queues, ordering the tasks within each queue of assigned tasks based on a spatial dimension extent, generating wait times within the queues in accordance with timing dependencies, identifying which of the queues of assigned tasks takes a most amount of time in accordance with temporal dimension extents and the wait times, creating at least one variant of the queues of assigned tasks, repeating the ordering, the adding, and the identifying to reduce a total time of manufacturing, and providing a finalized version of the queues of assigned tasks for conducting synchronized activities of manufacturing in the shared build volume.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
determining a set of multiple tasks to be performed by two or more robots in a shared build volume to manufacture a three-dimensional (3D) object in the shared build volume, wherein each of the tasks in the set has a spatial dimension extent and a temporal dimension extent;
assigning the tasks to respective queues of respective ones of the two or more robots, wherein each queue includes two or more assigned tasks;
ordering the tasks within each queue of assigned tasks based on the spatial dimension extent;
generating wait times within the queues of assigned tasks in accordance with timing dependencies among tasks in the queues of assigned tasks to avoid spatial overlap;
identifying which of the queues of assigned tasks takes a most amount of time from among all of the respective queues of assigned tasks in accordance with the temporal dimension extents and the wait times;
creating at least one variant of the queues of assigned tasks by moving a task in the identified queue, or a task on which a task in the identified queue depends, to another of the queues of assigned tasks;
repeating the ordering, the generating, and the identifying to reduce a total time of manufacturing; and
providing a finalized version of the queues of assigned tasks for conducting synchronized activities of the two or more robots when manufacturing the 3D object in the shared build volume.

2. The method of claim 1 , wherein the two or more robots comprise 3D printer robots, and determining the set of multiple tasks comprises:
obtaining a layer of a 3D model of the 3D object;
identifying disconnected regions of the layer; and
splitting at least one of the disconnected regions into smaller regions based on a spatial dimension of the at least one of the disconnected regions;
wherein each of the tasks corresponds to manufacture of one of the smaller regions or an un-split one of the disconnected regions.

3. The method of claim 1 , wherein the two or more robots comprise 3D printer robots, and determining the set of multiple tasks comprises:
obtaining tool path specifications for a layer of a 3D model of the 3D object;
identifying at least one of the tool path specifications that defines a tool path that spans a substantial portion of the shared build volume;
splitting the at least one of the tool path specifications into smaller tool path specifications;
wherein each of the tasks corresponds to one of the obtained tool path specifications or one of the smaller tool path specifications.

4. The method of claim 1 , wherein determining the set of multiple tasks comprises, for each of the tasks:
finding minimum and maximum coordinates of locations for manufacture of a portion of the 3D object represented by the task; and
adding a buffer to the minimum and maximum coordinates of locations in accordance with a largest one of the robots that can carry out the task.

5. The method of claim 4 , wherein assigning the tasks comprises:
sorting the tasks by average values of their spatial dimension extents; and
dividing the sorted tasks among the queues based on a number of the two or more robots and sums of the temporal dimension extents for the sorted tasks.

6. The method of claim 1 , wherein ordering the tasks within each queue of assigned tasks comprises:
sorting the tasks included in the queue for a leftmost robot of the two or more robots by maximum values of their spatial dimension extents; and
sorting the tasks included in the queue for a rightmost robot of the two or more robots by minimum values of their spatial dimension extents.

7. The method of claim 6 , comprising determining the timing dependencies among the tasks in the queues of assigned tasks by beginning with tasks assigned to the rightmost robot and proceeding in sequence through the queues of assigned tasks for the two or more robots, ending with tasks assigned to the leftmost robot.

8. The method of claim 1 , wherein generating the wait times within the queues of assigned tasks comprises checking an end time of a temporal dimension extent for a first task in a first of the queues of assigned tasks when a spatial dimension extent of the first task overlaps with a spatial dimension extent of a second task in a second of the queues of assigned tasks.

9. The method of claim 8 , wherein creating the at least one variant comprises:
moving a final task from the queue of assigned tasks that takes the most amount of time to a queue of assigned tasks for a next robot over in a positive direction of the spatial dimension; and
moving a root task in a dependency tree, which includes the final task, to a queue of assigned tasks for a next robot over in a negative direction of the spatial dimension.

10. The method of claim 1 , wherein the creating and the repeating are performed by a recursive program.

11. The method of claim 10 , wherein the recursive program maintains a global list of attempted task assignment solutions and skips a recursive call for any variant that is already included in the global list of attempted task assignment solutions.

12. A non-transitory computer-readable medium encoding instructions programmed to cause one or more hardware processors of one or more computing devices to perform operations comprising:
determining a set of multiple tasks to be performed by two or more robots in a shared build volume to manufacture a three-dimensional (3D) object in the shared build volume, wherein each of the tasks in the set has a spatial dimension extent and a temporal dimension extent;
assigning the tasks to respective queues of respective ones of the two or more robots, wherein each queue includes two or more assigned tasks;
ordering the tasks within each queue of assigned tasks based on the spatial dimension extent;
generating wait times within the queues of assigned tasks in accordance with timing dependencies among tasks in the queues of assigned tasks to avoid spatial overlap;
identifying which of the queues of assigned tasks takes a most amount of time from among all of the respective queues of assigned tasks in accordance with the temporal dimension extents and the wait times;
creating at least one variant of the queues of assigned tasks by moving a task in the identified queue, or a task on which a task in the identified queue depends, to another of the queues of assigned tasks;
repeating the ordering, the generating, and the identifying to reduce a total time of manufacturing; and
providing a finalized version of the queues of assigned tasks for conducting synchronized activities of the two or more robots when manufacturing the 3D object in the shared build volume.

13. The non-transitory computer-readable medium of claim 12 , wherein the two or more robots comprise 3D printer robots, and determining the set of multiple tasks comprises:
obtaining a layer of a 3D model of the 3D object;
identifying disconnected regions of the layer; and
splitting at least one of the disconnected regions into smaller regions based on a spatial dimension of the at least one of the disconnected regions;
wherein each of the tasks corresponds to manufacture of one of the smaller regions or an un-split one of the disconnected regions.

14. The non-transitory computer-readable medium of claim 12 , wherein the two or more robots comprise 3D printer robots, and determining the set of multiple tasks comprises:
obtaining tool path specifications for a layer of a 3D model of the 3D object;
identifying at least one of the tool path specifications that defines a tool path that spans a substantial portion of the shared bu

Assignees

• Autodesk Inc

Inventors

• Meess Gregory David

Classifications

• G05B19/402 Primary

  characterised by control arrangements for positioning, e.g. centring a tool relative to a hole in the workpiece, additional detection means to correct position (G05B19/19 takes precedence) · CPC title

• B33Y50/02 Primary

  for controlling or regulating additive manufacturing processes · CPC title

• B25J9/1682 Primary

  Dual arm manipulator; Coordination of several manipulators · CPC title

• Y02P90/02

  Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS] · CPC title

• G05B2219/39117

  Task distribution between involved manipulators · CPC title