Heterogeneous Graph Attention Networks for Scalable Multi-Robot Scheduling with Temporospatial Constraints

Zheyuan Wang, Matthew Gombolay


Robot teams are increasingly being deployed in environments, such as manufacturing facilities and warehouses, to save cost and improve productivity. To efficiently coordinate multi-robot teams, fast, high-quality scheduling algorithms are essential to satisfy the temporal and spatial constraints imposed by dynamic task specification and part and robot availability. Traditional solutions include exact methods, which are intractable for large-scale problems, or application-specific heuristics, which require expert domain knowledge to develop. In this paper, we propose a novel heterogeneous graph attention network model, called ScheduleNet. By introducing robot- and proximity-specific nodes into the simple temporal network encoding temporal constraints, we obtain a heterogeneous graph structure that is nonparametric in the number of tasks, robots and task resources or locations. We show that our model is end-to-end trainable via imitation learning on small-scale problems, generalizing to large, unseen problems. Empirically, our method outperforms the existing state-of-the-art methods in a variety of testing scenarios.

Live Paper Discussion Information

Start Time End Time
07/16 15:00 UTC 07/16 17:00 UTC

Virtual Conference Presentation

Paper Reviews

Review 1

The paper presents a method for learning Q-values for solving multirobot task allocation and scheduling problems. The scheduling constraints are expressed with task start time, end time and duration. The scheduling problem is formalized as an MDP with a Q function that is learned by an heterogeneous graph attention network. The graph attention network is built as an extension of STNs. The learning process uses schedules built by experts or produced by exact optimization methods. The optimization function used for most of the experiments is the makespan, but some results are reported for a different function. Since the data are synthetic it is hard to map them to specific robotics applications. The paper mentions that the robots are manipulators working on a large piece. The paper is generally clear and well organized. It would have been useful to mention a few additional things in the paper: (1) an indication on the number of robots expected. Since the method is centralized the number will likely be limited. (2) some more details on how the method will be used, i.e. offline at the planning stage or online at execution time? what sensor information is available to the robots?