Heterogeneous graph attention networks to aid scheduling policies

As manufacturing facilities and warehouses increasingly seek to deploy teams of advanced robots, real-time scheduling solutions to coordinate human-robot collaboration are needed to realize the potential cost savings and productivity improvements. Georgia Tech’s new scheduling method offers a significant leap forward in the state of the art with a novel heterogeneous graph attention network model.

Called ScheduleNet, the model aims to efficiently coordinate multi-robot teams with fast, high-quality scheduling algorithms that satisfy the temporal and spatial constraints imposed by dynamic task specification as well as part and robot availability. ScheduleNet combines imitation learning (making use of expert demonstration on small problems) with graph neural networks in a non-parametric framework, which provides flexibility and increases performance. By building upon graph attention networks and imitation learning for multi-robot scheduling, ScheduleNet enables fast, near-optimal scheduling of robot teams of various sizes, while generalizing to large, unseen problems. In fact, experimental results showed that the network-based policy was able to find high-quality solutions for approximately 90 percent of testing problems involving scheduling 2 to 5 robots and up to 100 tasks. ScheduleNet’s performance further scales to problems of 10 robots and 200 tasks where exact methods fail frequently. These results—achieved with affordable computation costs and less computation time compared with exact solvers—significantly outperform prior state-of-the-art, approximate methods.

Solution Advantages
  • Superior performance: Outperforms approximate human-robot scheduling methods in both schedule optimization and total number of feasible schedules
  • Robust: Can autonomously learn scalable scheduling heuristics on multiple application domains and attains an order-of-magnitude improved computation speed compared with exact methods
  • Novel: Is the first method to leverage graph neural networks involving simple temporal network (STN)-based scheduling problems with spatial constraints
  • Flexible: Provides scalable, non-parametric scheduling in both number of tasks and number of robots, enabling expert solutions for small- to large-scale problems
Potential Commercial Applications
  • Manufacturing facilities
  • Warehouses
  • Smart manufacturing markets
  • Assembly-line processes
Background and More Information

Georgia Tech’s method of multi-robot scheduling seeks to overcome the limitations of conventional methods. Previous methods of scheduling robots to complete tasks with temporal and spatial constraints included using exact algorithms, which are computationally intractable for large-scale, dynamic coordination. Approximate methods have also traditionally been used, but these require domain experts to craft heuristics for each application—a time-consuming and inefficient task. By contrast, Georgia Tech’s method features automated learning that can be scaled from small to large scheduling problems across an unlimited number of tasks, robots, and task resources or locations.

ScheduleNet: Advancing Multi-Robot Coordination

Figure 1. An overview of ScheduleNet, which operates on a heterogeneous graph constructed by augmenting the simple temporal network (STN) of the problem and predicts Q-values for scheduling.

ScheduleNet: Advancing Multi-Robot Coordination

Figure 2. A meta-graph of the heterogeneous graph built from the STN by adding robot, location, state, and value nodes