Program synthesis for robotic tasks

• US 9,737,990 B2
• Filed: 05/16/2014
• Issued: 08/22/2017
• Est. Priority Date: 05/16/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Feniello, Ashley Nathan, Birchfield, Stan, Dang, Hao, Gulwani, Sumit
• Primary Examiner(s): Chang, Li-Wu
• Application Number:
  US14/280,187
• Publication Number:
  US 20150331416A1
• Time in Patent Office: 1,194 Days
• Field of Search: None
• CPC Class Codes: B25J 9/1656 characterised by programming, planning systems for manipulators
• CPC Class Codes: B25J 9/1661 characterised by task planning, object-oriented languages
• CPC Class Codes: G05B 2219/40518 Motion and task planning
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

Robotic task program synthesis embodiments are presented that generally synthesize a robotic task program based on received examples of repositioning tasks. In one implementation, the exemplary repositioning tasks are human demonstrations of object manipulation in an actual or displayed robot workspace. A domain specific language (DSL) designed for object repositioning tasks is employed for the robotic control program. In general, candidate robotic task programs are generated from the example tasks. Each candidate program includes instructions for causing the robot to reposition objects, and represents a different permutation of instructions consistent with the received example tasks. The candidate programs are ranked, and whenever the top ranking program accomplishes the repositioning specified in each example task, it is designated as the synthesized robotic task program.

Claims

1. A computer-implemented process for synthesizing a robotic task program, comprising:

using a computer to perform the following process actions;

receiving one or more example tasks, each example task comprising a scene-reposition pair, said scene portion of a scene-reposition pair comprising a collection of objects characterized by their orientation, location and perceptual object characteristics, and representing a starting configuration of the objects in a workspace associated with a robot, and said reposition portion of a scene-reposition pair comprising repositioning data for one or more of said objects, wherein the repositioning data for an object comprises a destination orientation, or destination location, or both and is indicative of a task that the robot is to perform on the various objects in the workspace;

generating a plurality of complete candidate robotic task programs, each program comprising task instructions for causing the robot to reposition one or more of said objects in the workspace, and wherein each program represents a different complete set of task instructions consistent with the received example task or tasks;

ranking the plurality of complete candidate robotic task programs generated based on the degree to which a candidate program causes the robot to reposition objects in a manner indicated by the scene-reposition pair or pairs of the received example task or tasks; and

whenever the top ranking candidate robotic task program accomplishes the repositioning specified in each of the scene-reposition pairs in the received example task or tasks, designating the top ranking candidate robotic task program as the synthesized robotic task program.

2. The process of claim 1, wherein the process action of generating a plurality of complete candidate robotic task programs, comprises the actions of:

classifying said objects in the workspace into one or more object classes based on their perceptual object characteristics to create one or more base object filters;

determining if one of the base object filters identifies each of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, and only the objects specified as being repositioned; and

whenever it is determined that one of the base object filters identifies each of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, and only the objects specified as being repositioned, designating that base filter as a correct filter.

3. The process of claim 2, further comprising, whenever it is determined that none of the base object filters identifies each of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, and only the objects specified as being repositioned:

a) combining the base object filters in multiple ways to create combined object filters;

b) determining if one of the current combined object filters identifies each of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, and only the objects specified as being repositioned;

c) whenever it is determined that one of the current combined object filters identifies each of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, and only the objects specified as being repositioned, designating that current combined object filter as the correct filter;

d) whenever it is determined that none of the current combined object filters identifies each of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, and only the objects specified as being repositioned,

combining the current combined object filters in multiple ways to create new combined object filters, and

repeating process actions b) through d) as appropriate, until one of the current combined object filters has been designated as the correct filter.

4. The process of claim 3, wherein the process actions of combining base object filters or current combined object filters, comprises an action of combining each object filter in a combination using one of the logical operators AND, or OR, or NOT.

5. The process of claim 3, wherein the process actions of combining base object filters or current combined object filters, further comprises:

for each object filter being combined, determining the number of objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks that the object filter correctly identifies and the number of said objects the object filter incorrectly identifies;

for an object filter determined to correctly identify some of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, but also incorrectly identify one of more of said objects, respectively combining the object filter with ones of the object filters that has been determined to incorrectly identify one of more of said objects and not correctly identify any of said objects, using a logical NOT operator.

6. The process of claim 3, wherein the process actions of combining base object filters or current combined object filters, further comprises:

for each object filter being combined, determining the number of objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks that the object filter correctly identifies and the number of said objects the object filter incorrectly identifies;

for an object filter determined to correctly identify some, but not all of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, but also not incorrectly identify any of said objects, respectively combining the object filter with ones of the object filters that has been likewise determined to correctly identify some, but not all of the objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, but also not incorrectly identify any of said objects, using a logical OR operator.

7. The process of claim 2, wherein the process action of classifying said objects in the workspace into one or more object classes based on their perceptual object characteristics to create one or more base object filters, comprises classifying said objects into one or more object classes comprising size, or shape, or aspect ratio, or color.

8. The process of claim 2, wherein the process action of classifying said objects in the workspace into one or more object classes based on their perceptual object characteristics to create one or more base object filters, comprises, for a perceptual object characteristic that exhibits a discrete value, an action of creating a base object filter that identifies objects exhibiting the perceptual object characteristic having that discrete value.

9. The process of claim 2, wherein the process action of classifying said objects in the workspace into one or more object classes based their perceptual object characteristics to create one or more base object filters, comprises, for a perceptual object characteristic that exhibits a continuous value, an action of creating a base object filter that identifies objects exhibiting the perceptual object characteristic that falls within a prescribed range of values, wherein said prescribed range of continuous values comprises values falling within a range starting with the minimum value of said perceptual object characteristic exhibited by objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, and ending with the maximum value of said perceptual object characteristic exhibited by objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks.

10. The process of claim 2, wherein the process action of classifying said objects in the workspace into one or more object classes based on their perceptual object characteristics to create one or more base object filters, comprises, for a perceptual object characteristic that exhibits a discrete value, an action of creating a base object filter that identifies objects not exhibiting the perceptual object characteristic having that discrete value.

11. The process of claim 2, wherein the process action of classifying said objects in the workspace into one or more object classes based on their perceptual object characteristics to create one or more base object filters, comprises, for a perceptual object characteristic that exhibits a continuous value, an action of creating a base object filter that identifies objects not exhibiting the perceptual object characteristic that falls within a prescribed range of continuous values, wherein said prescribed range of continuous values comprises values falling within a range starting with the minimum value of said perceptual object characteristic exhibited by objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, and ending with the maximum value of said perceptual object characteristic exhibited by objects specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks.

12. The process of claim 2, wherein the process action of classifying said objects in the workspace into one or more object classes based on their perceptual object characteristics to create one or more base object filters, comprises, for a perceptual object characteristic that exhibits a continuous value, an action of creating a plurality of base object filters each of which identifies objects exhibiting the perceptual object characteristic that falls within one of a plurality of a prescribed ranges of continuous values, wherein a clustering of the continuous values exhibited by the perceptual object characteristic of said collection of objects specified in the scene portion of the scene-reposition pairs in the received example task or tasks defines a series of continuous value ranges, and wherein each of said prescribed ranges of continuous values comprises one of said series of continuous value ranges.

13. A system for synthesizing a robotic task program, comprising:

one or more computing devices, wherein said computing devices are in communication with each other via a computer network whenever there are multiple computing devices; and

a computer program having program modules executable by the one or more computing devices, the one or more computing devices being directed by the program modules of the computer program to,

receive one or more example tasks, each example task comprising a scene-reposition pair, said scene portion of a scene-reposition pair comprising a collection of objects characterized by their orientation, location and perceptual object characteristics, and representing a starting configuration of the objects in a workspace associated with a robot, and said reposition portion of a scene-reposition pair comprising repositioning data for one or more of said objects, wherein the repositioning data for an object comprises a destination orientation, or destination location, or both and is indicative of a task that the robot is to perform on the object in the workspace,

generate a plurality of complete candidate robotic task programs in a domain specific language tailored to robotic manipulation tasks, each program comprising task instructions for causing the robot to reposition one or more of said objects in the workspace, and wherein each program represents a different complete set of task instructions consistent with the received example task or tasks,

rank the plurality of complete candidate robotic task programs generated based on the degree to which a candidate program causes the robot to reposition objects in a manner indicated by the scene-reposition pair or pairs of the received example task or tasks, and

whenever the top ranking candidate robotic task program accomplishes the repositioning specified in each of the scene-reposition pairs in the received example task or tasks, designate the top ranking candidate robotic task program as the synthesized robotic task program.

14. The system of claim 13, wherein the program module for generating a plurality of complete candidate robotic task programs, comprises sub-modules for:

classifying said objects in the workspace into one or more object classes based their perceptual object characteristics to create an object filter for each object which identifies that object;

identifying distinct destination locations based on said reposition portion of the scene-reposition pairs in the received example task or tasks; and

for each object specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, populating each of a group of prescribed reposition primitives with the object filter associated with the object and a distinct destination location.

15. The system of claim 14, wherein the sub-module for populating each of said group of prescribed reposition primitives with the object'"'"'s distinct destination location and the object filter associated with the object, comprises sub-modules for:

generating a move primitive which represents an instruction for a robot to move the object, as well as all other objects associated with the same object filter and not having a different distinct destination location associated therewith, to the object'"'"'s distinct destination location;

for each number in a sequence of numbers ranging between zero and the total number of objects associated with the same object filter and not having a different distinct destination location associated therewith, generating a number-limited move primitive which represents an instruction for a robot to move the object, as well as said number of other objects associated with the same object filter and not having a different distinct destination location associated therewith, to the object'"'"'s distinct destination location;

generating a distribute primitive which represents an instruction for a robot to move the object, as well as all other objects associated with the same object filter to one of a prescribed number of distinct destination locations, said distinct destination locations including the distinct destination location associated with the object and said prescribed number of distinct destination locations ranging from two up to the total number of identified distinct destination locations or the total number of objects associated with the same object filter, whichever is smaller; and

for each number in a sequence of numbers ranging between zero and the total number of objects associated with the same object filter, generating a number-limited distribute primitive which represents an instruction for a robot to move the object, as well as said number of other objects associated with the same object filter to a one of a prescribed number of distinct destination locations, said distinct destination locations including the distinct destination location associated with the object and said prescribed number of distinct destination locations ranging from two up to the total number of identified distinct destination locations or the total number of objects associated with the same object filter, whichever is smaller.

16. The system of claim 13, wherein the program module for generating a plurality of complete candidate robotic task programs, comprises sub-modules for:

classifying said objects in the workspace into one or more object classes based on their perceptual object characteristics to create an object filter for each object which identifies that object;

identifying distinct destination orientations based on said reposition portion of the scene-reposition pairs in the received example task or tasks; and

for each object specified as being repositioned in said reposition portion of the scene-reposition pairs in the received example task or tasks, populating each of a group of prescribed reposition primitives with the object filter associated with the object and a distinct destination orientation.

17. The process of claim 16, wherein the process action of populating each of said group of prescribed reposition primitives with the object'"'"'s distinct destination orientation and the object filter associated with the object, comprises:

generating a move primitive which represents an instruction for a robot to move the object, as well as all other objects associated with the same object filter and not having a different distinct destination orientation associated therewith, to the object'"'"'s distinct destination orientation;

for each number in a sequence of numbers ranging between zero and the total number of objects associated with the same object filter and not having a different distinct destination orientation associated therewith, generating a number-limited move primitive which represents an instruction for a robot to move the object, as well as said number of other objects associated with the same object filter and not having a different distinct destination orientation associated therewith, to the object'"'"'s distinct destination orientation;

generating a distribute primitive which represents an instruction for a robot to move the object, as well as all other objects associated with the same object filter to a one of a prescribed number of distinct destination orientations, said distinct destination orientations including the distinct destination orientation associated with the object and said prescribed number of distinct destination orientations ranging from two up to the total number of identified distinct destination orientations or the total number of objects associated with the same object filter whichever is smaller; and

for each number in a sequence of numbers ranging between zero and the total number of objects associated with the same object filter, generating a number-limited distribute primitive which represents an instruction for a robot to move the object, as well as said number of other objects associated with the same object filter to a one of a prescribed number of distinct destination orientations, said distinct destination orientations including the distinct destination orientation associated with the object and said prescribed number of distinct destination orientations ranging from two up to the total number of identified distinct destination orientations or the total number of objects associated with the same object filter, whichever is smaller.

18. The system of claim 13, wherein the program module for receiving one or more example tasks, comprises a sub-module for receiving a task that is designated as a negative example task, and wherein the program module for generating one or more candidate robotic task programs, comprises a sub-module for eliminating candidate robotic task programs that causes the robot to reposition objects in a manner indicated by the negative example task.

19. The system of claim 18, wherein whenever more than one candidate robotic task program is found to accomplish the repositioning specified in each of the scene-reposition pairs in the received example task or tasks, the program module for ranking the one or more candidate robotic task programs comprises a sub-module for further ranking these candidate robotic task programs according to their complexity with simpler programs being ranked higher than more complex programs, or according to the past history of tasks specified by users with tasks specified more often by users in the past being ranked higher than tasks specified less often, or both.

20. A computer-implemented process for synthesizing a robotic task program, comprising:

using a computer to perform the following process actions;

receiving one or more example tasks, each example task comprising a scene-reposition pair, said scene portion of a scene-reposition pair comprising a collection of objects characterized by their orientation, location and perceptual object characteristics, and representing a starting configuration of the objects in a workspace associated with a robot, and said reposition portion of a scene-reposition pair comprising repositioning data for one or more of said objects, wherein the repositioning data for an object comprises a destination orientation, or destination location, or both and is indicative of a task that the robot is to perform on the object in the workspace;

generating one or more candidate robotic task programs, each program comprising task instructions for causing the robot to reposition one or more of said objects in the workspace, and wherein each program represents a different set of task instructions consistent with the received example task or tasks;

ranking the one or more candidate robotic task programs generated based on the degree to which a candidate program causes the robot to reposition objects in a manner indicated by the scene-reposition pair or pairs of the received example task or tasks;

whenever the top ranking candidate robotic task program accomplishes the repositioning specified in each of the scene-reposition pairs in the received example task or tasks, designating the top ranking candidate robotic task program as the synthesized robotic task program; and

whenever more than one candidate robotic task program has been generated and the top ranking candidate robotic task program does not accomplish the repositioning specified in each of the scene-reposition pairs in the received example task or tasks,

a) combining the candidate robotic task programs in multiple ways to create a plurality of combined candidate robotic task programs,

b) ranking the combined candidate robotic task programs based on the degree to which a candidate program causes the robot to reposition objects in a manner indicated by the scene-reposition pair or pairs of the received example task or tasks,

c) whenever a current top ranking combined candidate robotic task program accomplishes the repositioning specified in each of the scene-reposition pairs in the received example task or tasks, designating the current top ranking combined candidate robotic task program as the synthesized robotic task program, and

d) whenever a current top ranking combined candidate robotic task program does not accomplish the repositioning specified in each of the scene-reposition pairs in the received example task or tasks,

combining the current combined candidate robotic task programs in multiple ways to create a plurality of new combined candidate robotic task programs,

ranking the new combined candidate robotic task programs based on the degree to which a candidate program causes the robot to reposition objects in a manner indicated by the scene-reposition pair or pairs of the received example task or tasks, and

repeating instructions c) and d) as appropriate until the current top ranking combined candidate robotic task program has been designated as the synthesized robotic task program.