Automated movement orchestration

• US 10,635,981 B2
• Filed: 02/17/2017
• Issued: 04/28/2020
• Est. Priority Date: 01/18/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Mital, Vijay, Abraham, Robin
• Primary Examiner(s): Cook, Brian S
• Assistant Examiner(s): Khan, Iftekhar A
• Application Number:
  US15/436,694
• Publication Number:
  US 20180203948A1
• Time in Patent Office: 1,166 Days
• Field of Search: 703 6
• CPC Class Codes: B25J 9/161 Hardware, e.g. neural networks, fuzzy logic, interfaces, processor
• CPC Class Codes: B25J 9/163 learning, adaptive, model based, rule based expert control
• CPC Class Codes: B25J 9/1694 characterised by use of sensors other than normal servo-feedback from position, speed or acceleration sensors, perception control, multi-sensor controlled systems, sensor fusion
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06N 3/008 based on physical entities controlled by simulated intelligence so as to replicate intelligent life forms, e.g. based on robots replicating pets or humans in their appearance or behaviour
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/82 using neural networks
• CPC Class Codes: G06V 10/84 using probabilistic graphical models from image or video features, e.g. Markov models or Bayesian networks
• CPC Class Codes: G06V 20/00 Scenes; Scene-specific elements control of digital cameras H04N23/60
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 40/16 Human faces, e.g. facial parts, sketches or expressions

Abstract

The automatic formulation of a plan for concurrent movement of physical entities within a physical space. A physical graph is used to formulate such a plan. The physical graph represents multiple physical entities that have been sensed in a physical space over time. A plan is then formulated based on an evaluation of that physical graph. Such plans are enabled by the semantic understanding of the physical space and its contents that the physical graph provides. The plan honors physical constraints of the physical space, and physical constraints of the physical entities that are moving within that physical space. The plan may be further orchestrated by communicating with the physical entities to provide instructions for movement. Then, movement is monitored to determine if the plan is being complied with. If the plan is not being complied with, further communications are made and/or an alternative plan is automatically constructed.

Claims

1. A computing system comprising:

one or more processors;

one or more computer-readable media having thereon computer-executable instructions that are structured such that, when executed by the one or more processors, cause the computing system to perform a method for formulating a plan for concurrent movement of a plurality of physical entities, the method comprising;

accessing a physical graph, the physical graph comprising information representing both location and movement of the plurality of physical entities within a physical space over time, the physical graph being part of a sensed feature store comprising a plurality of signal segments, each signal segment comprising a signal detected by a sensor from at least one of the plurality of physical entities located within the physical space, each signal segment associated with a time when the signal of the at least one physical entity was detected, the sensed feature store also storing a plurality of sensed features associated with the plurality of physical entities, each sensed feature also associated with a time and location within the physical space, the sensed feature store also storing a plurality of physical relationships of the plurality of physical entities determined by a comparison of data structures representing the plurality of physical entities within the sensed feature store;

evaluating the physical graph, physical constraints of the physical space, physical constraints of the plurality of physical entities sensed within the physical space, and one or more objectives for the plurality of physical entities to accomplish within the physical space; and

based on the evaluation, formulating a plan for movement of the plurality of physical entities that complies with the physical constraints of the physical space, complies with the physical constraints of the plurality of physical entities, complies with the physical relationships of the plurality of physical entities and that accomplishes at least one of the one or more objectives.

2. The computing system in accordance with claim 1, the evaluation also considering movement priority for each of at least one of the plurality of physical entities.

3. The computing system in accordance with claim 1, the evaluation also considering constraints in interaction of at least some of the plurality of physical entities.

4. The computing system in accordance with claim 3, the constraints in interaction comprising safety constraints.

5. The computing system in accordance with claim 3, the constraints in interaction comprising law of physics constraints.

6. The computing system in accordance with claim 1, the evaluation also considering which of the plurality of physical entities can be communicated with, the plan for movement providing instructions for movement around predicted movement of one or more physical entities that cannot be communicated with.

7. The computing system in accordance with claim 6, the evaluation also considering which of the plurality of physical entities are predicted to honor instructions for movement, the plan for movement providing instructions for movement around predicted movement of one or more physical entities that cannot be communicated with and one or more physical entities that are not predicted to honor instructions for movement.

8. The computing system in accordance with claim 6, the evaluation considering which of the plurality of physical entities are predicted to honor instructions for movement, the plan for movement providing instructions for movement around predicted movement of one or more physical entities that are not predicted to honor instructions for movement.

9. The computing system in accordance with claim 1, the method further comprising:

communicating with one or more of the plurality of physical entities to affect movement of at least one of the plurality of physical entities.

10. The computing system in accordance with claim 9, addressing of the communication occurring by physical status rather than by explicitly identifying the one or more of the plurality of physical entities that are to be communicated with.

11. The computing system in accordance with claim 9, the communication comprising explicit instructions.

12. The computing system in accordance with claim 9, the communication comprising context from which the physical entity that was communicated with may infer an appropriate physical movement.

13. The computing system in accordance with claim 9, the method further comprising:

further monitoring movement of the plurality of physical entities.

14. The computing system in accordance with claim 13, the method being repeatedly performed in order to dynamically adjust the plan for movement based on the further monitoring of the movement of the plurality of physical entities.

15. The computing system in accordance with claim 1, a constraint of the physical space comprising a physical channel through which at least some of the physical entities can move, the plan for moving comprising sequencing of physical entities through the physical channel.

16. The computing system in accordance with claim 1, the one or more objectives including at least one routing objective expressed by a particular physical entity.

17. The computing system in accordance with claim 1, a physical constraint for a particular physical entity comprising space needed for the particular physical entity.

18. The computing system in accordance with claim 1, a physical constraint for a particular physical entity comprising movement capability for the particular physical entity.

19. A method for formulating a plan for concurrent movement of a plurality of physical entities, the method comprising:

accessing a physical graph, the physical graph comprising information representing both location and movement of the plurality of physical entities within a physical space over time, the physical graph being part of a sensed feature store comprising a plurality of signal segments, each signal segment comprising a signal detected by a sensor from at least one of the plurality of physical entities located within the physical space, each signal segment associated with a time when the signal of the at least one physical entity was detected, the sensed feature store also storing a plurality of sensed features associated with the plurality of physical entities, each sensed feature also associated with a time and location within the physical space, the sensed feature store also storing a plurality of physical relationships of the plurality of physical entities determined by a comparison of data structures representing the plurality of physical entities within the sensed feature store;

evaluating the physical graph, physical constraints of the physical space, physical constraints of the plurality of physical entities sensed within the physical space, and one or more objectives for the plurality of physical entities to accomplish within the physical space; and

based on the evaluation, formulating a plan for movement of the plurality of physical entities that complies with the physical constraints of the physical space, complies with the physical constraints of the plurality of physical entities, complies with the physical relationships of the plurality of physical entities, and that accomplishes at least one of the one or more objectives.

20. A computer program product comprising one or more computer-readable storage devices having thereon computer-executable instructions that are structured such that, when executed by the one or more processors, cause the computing system to perform a method for formulating a plan for concurrent movement of a plurality of physical entities, the method comprising:

accessing a physical graph, the physical graph comprising information representing both location and movement of the plurality of physical entities within a physical space over time, the physical graph being part of a sensed feature store comprising a plurality of signal segments, each signal segment comprising a signal detected by a sensor from at least one of the plurality of physical entities located within the physical space, each signal segment associated with a time when the signal of the at least one physical entity was detected, the sensed feature store also storing a plurality of sensed features associated with the plurality of physical entities, each sensed feature also associated with a time and location within the physical space, the sensed feature store also storing a plurality of physical relationships of the plurality of physical entities determined by a comparison of data structures representing the plurality of physical entities within the sensed feature store;

evaluating the physical graph, physical constraints of the physical space, physical constraints of the plurality of physical entities sensed within the physical space, and one or more objectives for the plurality of physical entities to accomplish within the physical space; and

based on the evaluation, formulating a plan for movement of the plurality of physical entities that complies with the physical constraints of the physical space, complies with the physical constraints of the plurality of physical entities, complies with the physical relationships of the plurality of physical entities, and that accomplishes at least one of the one or more objectives.