Autonomous agent scheduling

• US 10,496,095 B1
• Filed: 11/07/2017
• Issued: 12/03/2019
• Est. Priority Date: 11/07/2017
• Status: Expired due to Fees

• Current Assignee: U.S. Government As Represented By The Seceretary Of The Navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Bays, Matthew J., Wettergren, Thomas A.
• Primary Examiner(s): Paige, Tyler D
• Application Number:
  US15/806,131
• Time in Patent Office: 756 Days
• Field of Search: 701 2
• CPC Class Codes: B63G 2008/004 autonomously operating
• CPC Class Codes: B63G 2008/005 remotely controlled
• CPC Class Codes: B63G 8/001 Underwater vessels adapted for special purposes, e.g. unmanned underwater vessels; Equipment specially adapted therefor, e.g. docking stations self-propelled or direction controlled diving chambers with mechanical link to a base B63C11/42
• CPC Class Codes: B64C 39/024 of the remote controlled vehicle type, i.e. RPV
• CPC Class Codes: B64U 2101/00 UAVs specially adapted for particular uses or applications
• CPC Class Codes: B64U 2101/60 for transporting passengers; for transporting goods other than weapons
• CPC Class Codes: B64U 2201/10 autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS]
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

Methods are provided to obtain task allocation, planning, and scheduling necessary to ensure service agents can accomplish their tasks efficiently, while transport agents perform the necessary transport and refueling operations. The methods take a scheduling-centric approach, formally incorporate fuel constraints, and are generalized for an arbitrary number of service agents and transport agents. The methods provide for the formal definition of the novel simple agent transport problem, the unique modeling and constraint-based logic required for the docking, transport, and deployment of service agents and the resulting analysis. Tasks to be completed consist of a set of locations, and the agents must service each location set. The methods and systems incorporate Bayes risk to schedule slips and to the application of service agent-transport agent scheduling.

Claims

1. A method of optimizing task planning for a plurality of service agents and transport agents operating in a plurality of service areas, said method comprising the steps of:

formulating said task planning as a sequence of said service agents and said transport agents tasks and start times during a plurality of phases such that all of said areas are serviced, fuel limitations are observed during each of said plurality of phases and each of said service agents is docked with one of said transport agents at an end of a last phase of said plurality of phases, such that an end time of said last phase over all said agents is minimized;

constraining docking and deployment actions of said agents;

constraining fuel availability, fuel costs and fuel capacity of said agents;

constraining goals and capabilities of said agents;

constraining time dependency and wait times of said agents;

constraining transit and transport actions of said agents;

constraining servicing actions of said agents;

employing mixed-integer linear programming (MILP) techniques on a computer system to determine a task plan minimizing said end time based on said formulating and said constraining; and

communicating said task plan from said computer to said agents for execution of said plan.

2. The method of claim 1, further comprising the step of limiting a search space required by said MILP techniques.

3. The method of claim 2, wherein said step of limiting a search space comprises the step of reducing candidate dock, deploy and transit nodes of said service areas to a set of closest nodes providing one node per each of said service areas.

4. The method of claim 3, wherein said step of limiting a search space further comprises:

selecting a subset of nodes minimizing a distance traveled to visit each node in said subset;

and providing a dock and deploy point to each said service area.

5. The method of claim 4, wherein said step of employing MILP techniques comprises the step of solving a generalized traveling salesman problem partly encapsulated within optimizing said task planning.

6. The method of claim 2, wherein said step of limiting a search space comprises the step of eliminating transition edges between nodes of said service areas within a same service area.

7. The method of claim 6, wherein said step of eliminating transition edges comprises the step of eliminating intra-service area edges.

8. The method of claim 1, wherein said step of constraining docking and deployment actions comprises the steps of:

constraining said service agents to completing certain of said tasks when said service agents are at least one of docked and deployed;

constraining said service agents to being docked prior to being deployed;

tracking if said service agents are one of docked and deployed; and

constraining a number of said service agents docked at a given time by each of said transport agents.

9. The method of claim 1, wherein said step of constraining goals and capabilities comprises the steps of:

constraining each of said agents to prosecuting a single one of said goals during one of said phases; and

constraining scheduling of said agents for completion of one of said tasks to those said agents capable of completing said one of said tasks.

10. The method of claim 1, wherein said step of constraining time dependency and wait times comprises the steps of:

constraining a start time of a first of said phases to equal zero;

constraining a start time of a next one of said phases to being at least as great as an end time of a previous one of said phases;

defining an end time of one of said phases to include a start time of said one of said phases plus a duration of one of said tasks performed by one of said agents at one of said service areas;

constraining docking and deployment actions of a pair of said service agents and said transport agents to occur at a same time for each of said pair; and

constraining one of said service agents from being in a wait state at a certain location when said one service agent is at least in one of a state of being otherwise tasked, of waiting at a location other than said certain location and of having performed an action at a different location than said certain location.

11. The method of claim 1, wherein said step of constraining transit and transport actions of said agents comprises the steps of:

constraining transit of said agents from a first location to a next location to those of said agents having performed an action at said first location;

constraining movement of said agents between service areas and servicing of one of said service areas to those of said agents deployed;

constraining agents to be docked with agents capable of capturing agents to those of such agents previously located at a location of said capturing; and

constraining deployment of agents to those of such agents previously located at a location of said deployment.

12. The method of claim 1, wherein said step of constraining servicing actions of said agents comprises the steps of:

constraining one of said servicing actions at one of said service areas to when said one of said servicing actions is scheduled after at least one of a deployment action at a node within said one of said service areas and a move action to said one of said service areas;

constraining performance of one of said servicing actions to when said one of said service actions is scheduled while an agent performing said one of said service actions is deployed;

constraining each of said agents to prosecuting a single one of said goals during one of said phases;

constraining scheduling of said agents for completion of one of said tasks to those said agents capable of completing said one of said tasks; and

completion of each of said goals by said agents scheduled for completion of said tasks.

13. The method of claim 1, wherein said step of constraining time dependency and wait times of said agents comprises the steps of:

constraining an initial start time of one of said tasks to at least one of a scheduled start time of said one of said tasks and an end time of a previous one of said tasks, wherein said end time is taken as a start time of said previous one of said tasks and a duration of said previous one of said tasks;

constraining a start time of a next one of said phases to being at least as great as said end time plus a buffer time;

defining costs for a schedule slip when said end time exceeds said duration plus said buffer time and for a delay when said end time is less than said duration plus said buffer time;

optimizing, for each of said tasks, said buffer time to minimize said costs for each of said tasks;

constraining a time difference between said end time and said start time of said next one of said phases to at least said buffer time;

constraining a robust start time to include said start time plus a summation of each said buffer time;

defining an end time of one of said phases to include said robust start time of said one of said phases plus a duration of one of said tasks performed by one of said agents at one of said service areas;

constraining docking and deployment actions of a pair of said service agents and said transport agents to occur at a same time for each of said pair; and

constraining one of said service agents from being in a wait state at a certain location when said one service agent is at least in one of a state of being otherwise tasked, of waiting at a location other than said certain location and of having performed an action at a different location than said certain location.

14. The method of claim 13, wherein said step of constraining docking and deployment actions comprises the steps of:

constraining said service agents to completing certain of said tasks when said service agents are at least one of docked and deployed;

constraining said service agents to being docked prior to being deployed;

tracking if said service agents are one of docked and deployed; and

constraining a number of said service agents docked at a given time by each of said transport agents.

15. The method of claim 14, wherein said step of constraining goals and capabilities comprises the steps of:

constraining each of said agents to prosecuting a single one of said goals during one of said phases; and

constraining scheduling of said agents for completion of one of said tasks to those said agents capable of completing said one of said tasks.

16. The method of claim 15, wherein said step of constraining transit and transport actions of said agents comprises the steps of:

constraining transit of said agents from a first location to a next location to those of said agents having performed an action at said first location;

constraining movement of said agents between service areas and servicing of one of said service areas to those of said agents deployed;

constraining agents to be docked with agents capable of capturing agents to those of such agents previously located at a location of said capturing; and

constraining deployment of agents to those of such agents previously located at a location of said deployment.

17. The method of claim 16, wherein said step of constraining servicing actions of said agents comprises the steps of:

constraining one of said servicing actions at one of said service areas to when said one of said servicing actions is scheduled after at least one of a deployment action at a node within said one of said service areas and a move action to said one of said service areas;

constraining performance of one of said servicing actions to when said one of said service actions is scheduled while an agent performing said one of said service actions is deployed;

constraining each of said agents to prosecuting a single one of said goals during one of said phases;

constraining scheduling of said agents for completion of one of said tasks to those said agents capable of completing said one of said tasks; and

completion of each of said goals by said agents scheduled for completion of said tasks.

18. The method of claim 17, further comprising the step of limiting a search space required by said MILP techniques.

19. The method of claim 18, wherein said step of limiting a search space comprises the steps of:

reducing candidate dock, deploy and transit nodes of said service areas to a set of closest nodes providing one node per each of said service areas;

selecting a subset of nodes minimizing a distance traveled to visit each node in said subset;

providing a dock and deploy point to each said service area; and

solving a generalized traveling salesman problem partly encapsulated within optimizing said task planning.

20. The method of claim 18, wherein said step of limiting a search space comprises the step of eliminating transition edges between nodes of said service areas within a same service area.

21. The method of claim 20, wherein said step of eliminating transition edges comprises the step of eliminating intra-service area edges.