Tercio is a real-time task scheduler that can be used for optimizing labor resources in a wide host of fields, including health care, manufacturing and military operations.
In any field or operation, it is desirable to optimize the labor resources available such that multiple agents, both human and/or robot, can work on tasks in concert to maximize productivity. This resource integration must meet certain temporal and spatial constraints to support efficient and safe co-work. The multi-agent coordination problem with temporo-spatial constraints can be formulated as a mixed integer linear program (MILP). However, this approach is exponential in complexity and becomes computationally intractable for large-scale operations. The Inventors have developed Tercio, a new and efficient framework for real-time, near-optimal task scheduling that is scalable to large operations.
Tercio is a centralized task assignment and scheduling algorithm that scales to multi-agent, factory size problems and supports real-time planning with temporal and spatial-proximity constraints. Tercio takes as an input a set of tasks, temporal interval constraints, agents and an objective function. The algorithm first computes an optimal agent allocation by solving a mixed-integer problem, which includes terms for balancing the amount of work across each agent. Given the agent allocation and a task structure, Tercio sequences the tasks using an analytical test to ensure that all temporal constraints are satisfied. If the schedule is not within a user-specified process duration, Tercio attempts to find the next-best agent allocation. Once the schedule satisfies the temporal specifications, then agent and spatial-resource sequencing constraints are added to the problem. The resulting Simple Temporal Problem (STP), composed of the interval temporal constraints, is compiled into a dispatchable form which guarantees that for any consistent choice of a time point within a flexible window, a solution can be found through one-step propagation of interval bounds. This form maintains flexibility to increase robustness to disturbances, and has been shown to decrease the amount of time spent recomputing solutions in response to disturbances for randomly generated structured problems by up to 75%.
- Computes a multi-agent schedule that satisfies upperbound and lowerbound temporal deadlines as well as spatial restrictions on agent proximity in polynomial time
- Generates near-optimal task assignments and schedules for up to 10 agents and 500 tasks in less than 20 seconds on average, demonstrating superior scaling to previous approaches
- Returns flexible time windows for execution, increasing robustness to schedule disturbances