Service agent-transport agent task planning incorporating robust scheduling techniques

As the use of cooperative, heterogeneous teams of autonomous robots to perform tasks such as autonomous package delivery and long-duration ocean sampling becomes more prevalent, the is a quickly emerging need to study the high-level interaction of specialized robotic agents that perform service tasks, and specialized transport agents that transport the service agents between service areas. If the service routes, docking, and deployment schedules are not carefully planned, the overall schedule is inefficient at best, and possibly even infeasible due to fuel limitations at worst. We introduce a new problem in the area of scheduling and route planning operations called the service agent transport problem (SATP). Within the SATP, autonomous service agents must perform tasks at a number of locations. The agents are free to move between locations, however, the agents may also be transported throughout the region by a limited number of faster-moving transport agents. The goal of the SATP is to plan a schedule of service agent and transport agent actions such that all locations are serviced in the shortest amount of time. We believe the SATP formulation is unique because there is strong coupling between vehicle constraints as well as between the task allocation component of the problem and the scheduling component of the problem. We present a solution to the problem using a mixed-integer linear programming optimization framework and compare several complexity reduction heuristics to full optimization. Additionally, we include methods to account for relative uncertainty in the duration of planned tasks in such a manner as to balance the risk of schedule slips (conflicts) to the risk of creating an overly conservative and sub-optimal schedule. Published by Elsevier B.V.