Tercio -- Task Allocation and Dispatching Subroutines

Technology #17215

Questions about this technology? Ask a Technology Manager

Download Printable PDF

Categories
Inventors
Professor Julie Shah
Department of Aeronautics and Astronautics
External Link (people.csail.mit.edu)
Matthew Gombolay
MIT Lincoln Laboratories
Ronald Wilcox
Department of Aeronautics and Astronautics
Managed By
Daniel Dardani
MIT Technology Licensing Officer
Publications
Fast Scheduling of Multi-Robot Teams with Temporospatial Constraints
Robotics: Science and Systems, June 2013

Applications

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.

Problem Addressed

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 problem (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.

Technology

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 program, 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%.

Advantages 

  • 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