Method and system for mission planning via formal verification and supervisory controller synthesis

• US 10,249,197 B2
• Filed: 03/28/2016
• Issued: 04/02/2019
• Est. Priority Date: 03/28/2016
• Status: Active Grant

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Castillo-Effen, Mauricio, Johnson, Timothy Lee, Durling, Michael Richard
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): Greene, Daniel L
• Application Number:
  US15/082,885
• Publication Number:
  US 20170277203A1
• Time in Patent Office: 1,100 Days
• CPC Class Codes: B64C 39/024 of the remote controlled vehicle type, i.e. RPV
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G08G 5/0039 Modification of a flight plan

Abstract

A system, medium, and method, including receiving a set of formalized requirements for accomplishing a mission; allocating, by the processor using architecture synthesis, constraint solving, and compositional verification techniques, a role to each of a plurality of assets comprising a team of autonomous entities, the team to execute specific tasks according to their role to accomplish the mission; and generating, by the processor using controller synthesis and verification techniques, automata for accomplishing the mission for the plurality of assets, the automata being encoded to confer an ability to dynamically react to external inputs during a run-time execution of the automata by the plurality of assets.

Claims

1. A method implemented by a computing system in response to execution of program instructions by a processor of the computing system, the method comprising:

receiving, by at least one decomposition module of a mission planning module, a set of formalized requirements generated by a requirements formalization engine for accomplishing a mission;

allocating, by a processor of the decomposition module, using architecture synthesis, constraint solving, and compositional verification techniques, a role to each of a plurality of assets comprising a team of autonomous entities responsible to accomplish the mission, each of the plurality of assets of the team to execute specific tasks according to their allocated role to accomplish the mission;

generating, by a processor of at least one supervisory controller synthesis module using controller synthesis and formal verification techniques, automatically and in response to the set of formalized requirements and the roles allocated to the plurality of assets, a mission plan for accomplishing the mission by the plurality of assets, the mission plan being generated to automatically and dynamically react to external inputs during a run-time execution of the mission plan by the plurality of assets to execute tasks according to their allocated role to accomplish the mission plan;

sending the generated mission plan to the plurality of assets for the plurality of assets to, during a run-time execution of the mission plan, execute tasks in reaction to the external inputs and according to their allocated role to accomplish the mission;

wherein the method further comprises generating a plurality of contracts between the plurality of assets, where the plurality of contracts represents obligations the plurality of assets has with each other and the coordination required to fulfill those obligations; and

wherein the breaking or breaching of at least one contract among the plurality of contracts triggers a change in mission templates to be executed by the plurality of assets.

2. The method of claim 1, wherein the set of formalized requirements are generated based on at least one mission requirement, key performance metric, key performance objective, and combinations thereof for the mission.

3. The method of claim 1, further comprising:

generating, by the at least one decomposition module, a hierarchy of mission plans for the team of autonomous entities, wherein the at least one decomposition module is responsible for generating portions of the mission plan corresponding to the hierarchy of mission plans that will be executed by each of the plurality of assets.

4. The method of claim 1, further comprising decomposing, by the at least one decomposition module, the mission into at least two sub-sets of tasks, where the sub-sets of tasks are to be accomplished by a sub-set of the plurality of assets.

5. The method of claim 1, further comprising deriving, by the at least one decomposition module, obligations specifying required dependencies between the plurality of assets that are relevant to the accomplishment of the mission, wherein the obligations are used in generating the mission plan to accomplish the mission.

6. The method of claim 1, wherein the plurality of assets switch between different mission templates according to changes in external inputs.

7. The method of claim 1, further comprising algorithmically generating, by the at least one supervisory controller synthesis module, automata comprising the mission plan for each of the plurality of assets, the automata specifying tasks to be executed by each of the plurality of assets to accomplish the mission.

8. The method of claim 7, further comprising the plurality of assets cooperating to execute the automata in a coordinated run-time.

9. A system comprising:

at least one decomposition module of a mission planning module to;

receive a set of formalized requirements generated by a requirements formalization engine for accomplishing a mission; and

allocate, by a processor of the decomposition module, using architecture synthesis, constraint solving, and compositional verification techniques, a role to each of a plurality of assets comprising a team of autonomous entities to be responsible of accomplishing the mission, each of the plurality of assets of the team to execute specific tasks according to their allocated role to accomplish the mission; and

at least one supervisory controller synthesis module to;

automatically generate by a processor thereof using controller synthesis and formal verification techniques in response to the set of formalized requirements and the roles allocated to the plurality of assets, a mission plan for accomplishing the mission by the plurality of assets according to their allocated role to accomplish the mission plan, the mission plan being generated to automatically and dynamically react to external inputs during a run-time execution of the mission plan by the plurality of assets;

send the generated mission plan to the plurality of assets for the plurality of assets to, during a run-time execution of the mission plan, execute tasks in reaction to the external inputs and according to their allocated role to accomplish the mission;

wherein the decomposition module generates a plurality of contracts between the plurality of assets, where the plurality of contracts represents obligations the plurality of assets has with each other and the coordination required to fulfill those obligations; and

wherein the breaking or breaching of at least one contract among the plurality of contracts triggers a change in mission templates to be executed by the plurality of assets.

10. The system of claim 9, wherein the set of formalized requirements are generated based on at least one mission requirement, key performance metric, key performance objective, and combinations thereof for the mission.

11. The system of claim 9, further comprising:

generating, by the at least one decomposition module, a hierarchy of mission plans for the team of autonomous entities, wherein the controller is responsible for generating portions of the mission plan corresponding to the hierarchy of mission plans that will be executed by each of the plurality of assets.

12. The system of claim 9, further comprising decomposing, by the at least one decomposition module, the mission into at least two sub-sets of tasks, where the sub-sets of tasks are to be accomplished by a sub-set of the plurality of assets.

13. The system of claim 9, further comprising deriving, by the at least one decomposition module, obligations specifying required dependencies between the plurality of assets that are relevant to the accomplishment of the mission, wherein the obligations are used in generating the mission plan to accomplish the mission.

14. The system of claim 9, further comprising generating, by the at least one supervisory controller synthesis module, automata comprising the mission plan for each of the plurality of assets, the automata specifying tasks to be executed by each of the plurality of assets to accomplish the mission.

15. The system of claim 14, further comprising the plurality of assets cooperating to execute the automata in a coordinated run-time.

16. The system of claim 14, further comprising the plurality of assets cooperating to execute the automata in a coordinated run-time.

17. A non-transitory, computer-readable medium storing instructions thereon, the medium comprising:

program instructions to receive, by at least one decomposition module of a mission planning module, a set of formalized requirements generated by a requirements formulization engine for accomplishing a mission;

program instructions to allocate, by a processor of the decomposition module, using architecture synthesis, constraint solving, and compositional verification techniques, a role to each of a plurality of assets comprising a team of autonomous entities to be responsible of accomplishing the mission, each of the plurality of assets of the team to execute specific tasks according to their role to accomplish the mission; and

program instructions to generate, by a processor of at least one supervisory controller synthesis module using controller synthesis and formal verification techniques automatically and in response to the set of formalized requirements and the roles allocated to the plurality of assets, a mission plan for accomplishing the mission by the plurality of assets, the mission plan being generated to automatically and dynamically react to external inputs during a run-time execution of the mission plan by the plurality of assets to execute tasks according to their role to accomplish the mission plan;

program instructions to send the generated mission plan to the plurality of assets for the plurality of assets to, during a run-time execution of the mission plan, execute tasks in reaction to the external inputs and according to their allocated role to accomplish the mission;

wherein the medium further comprises program instructions to generate a plurality of contracts between the plurality of assets, where the plurality of contracts represents obligations the plurality of assets has with each other and the coordination required to fulfill those obligations; and

wherein the breaking or breaching of at least one contract among the plurality of contracts triggers a change in mission templates to be executed by the plurality of assets.

18. The system of claim 17, wherein the set of formalized requirements are generated based on at least one mission requirement, key performance metric, key performance objective, and combinations thereof for the mission.

19. The system of claim 17, further comprising:

program instructions to generate, by the at least one decomposition module, a hierarchy of mission plans for the team of autonomous entities, wherein the at least one decomposition module is responsible for generating portions of the mission plan corresponding to the hierarchy of mission plans that will be executed by each of the plurality of assets.

20. The system of claim 17, further comprising decomposing, by the at least one decomposition module, the mission into at least two sub-sets of tasks, where the sub-sets of tasks are to be accomplished by a sub-set of the plurality of assets.

21. The system of claim 17, further comprising deriving, by the at least one decomposition module, obligations specifying required dependencies between the plurality of assets that are relevant to the accomplishment of the mission, wherein the obligations are used in generating the mission plan to accomplish the mission.

22. The system of claim 17, further comprising generating, by the at least one supervisory controller synthesis module, automata comprising the mission plan for each of the plurality of assets specifying tasks to be executed by each of the plurality of assets to accomplish the mission.