Hierarchically Structured Scheduling and Execution of Tasks in a Multi-agent Environment

Diogo S. Carvalho, Biswa Sengupta

TL;DR

This paper tackles the complex problem of scheduling and executing tasks in dynamic warehouse environments using hierarchical deep reinforcement learning. They propose a novel approach that separates high-level task assignment from low-level task execution, enabling agents to learn efficient strategies in partially observable, multi-agent settings.

What Problem Does This Paper Address?

Warehouses and similar environments are characterized by a constant influx of dynamic tasks that need to be efficiently managed and executed by a workforce of agents (robots or humans). Traditional scheduling methods often struggle with the sheer scale and dynamism of these environments, leading to suboptimal resource allocation. Furthermore, real-world scenarios often involve partial observability for individual agents and the need for decentralized execution, making centralized planning difficult. This paper addresses the challenge of creating a robust and scalable system that can both intelligently schedule tasks and enable agents to effectively execute them in such complex, dynamic, and partially observable multi-agent settings.

Methods

The core of the paper's contribution lies in its hierarchical reinforcement learning (HRL) approach. This framework decomposes the problem into two distinct levels:

  • High-Level Scheduler (Centralized): A single agent is responsible for observing the entire environment state (including tasks, agents, and backlog) and generating a schedule. This schedule assigns tasks to individual low-level agents. The action space for this agent is designed to be linear with respect to the number of tasks and agents, avoiding the exponential growth that plagues traditional methods.
  • Low-Level Workers (Decentralized): Multiple agents are responsible for executing the tasks assigned to them by the high-level scheduler. These agents operate with partial observability, meaning they can only perceive a limited area around them. They learn to perform their assigned tasks based on their local observations and the schedule they receive.

The authors leverage deep reinforcement learning (DRL) for both levels. Specifically, they employ the Proximal Policy Optimization (PPO) algorithm. For the low-level agents, they explore both independent learning and shared experience learning, finding that shared experience leads to faster learning. They also consider a Decentralized Partially Observable Markov Decision Process (Dec-POMDP) setting where a hierarchy is not assumed, and agents must learn to cooperate with shared rewards and partial observability.

A key methodological aspect is the pre-training of the low-level agents on a static environment before training the high-level scheduler. This is done to mitigate the non-stationarity issues that arise when training both levels simultaneously, as the low-level agents' behavior can be unpredictable while the scheduler is still learning.

Datasets

The paper does not use pre-existing datasets. Instead, they introduce a simulated multi-agent grid world environment for training and evaluation. This environment is designed to mimic a warehouse setting with dynamic task arrivals, agent movement, and task execution. They provide details on the grid size, task representation (doors), agent representation (triangles), and observation capabilities.

Key Insights and Ideas

  • Hierarchical Decomposition is Crucial: Separating the scheduling (high-level) from execution (low-level) is essential for managing the complexity of dynamic multi-agent warehouse environments.
  • Linearizing the Action Space: The proposed recursive scheduling approach for the high-level agent effectively linearizes its action space, making it tractable for DRL.
  • Low-Level Pre-training Stabilizes Training: Pre-training the low-level agents in a static environment significantly improves the stability and performance of the high-level scheduler's training.
  • Shared Experience Benefits Low-Level Agents: In the low-level execution phase, agents that share experience and learn a common policy learn significantly faster than those learning independently.
  • Dec-POMDP is More Challenging: The Dec-POMDP setting, which removes the explicit hierarchy and schedule, is shown to be a harder problem, with agents learning quickly but plateauing at a lower performance level compared to the hierarchical approach.

Key Results

  • The high-level scheduler demonstrates the ability to learn and improve its performance as the number of agents increases.
  • While increasing the number of tasks assigned to each agent (buffer size) can improve performance, very large buffer sizes can lead to failure, potentially due to the increased environmental difficulty.
  • Low-level agents trained with shared experience learn significantly faster than those trained independently.
  • The hierarchical approach, even with its complexity, achieves better performance than the decentralized Dec-POMDP setting.
  • The paper shows that the proposed hierarchical method significantly outperforms a random scheduler.

Limitations and Future Work

  • Scalability with Large Buffer Sizes: The paper notes that increasing the buffer size (k) can lead to performance degradation, suggesting that the environment itself becomes too challenging. This indicates a potential limitation in scaling to very large task assignments per agent.
  • Environmental Complexity: The authors hypothesize that the difficulty of the environment itself, particularly with tasks appearing too frequently, might be a factor in some observed performance limitations.
  • Future Work:
    • Larger Warehouses: Extending the simulation to larger and more complex environments.
  • Heterogeneous Fleets and Tasks: Incorporating agents and tasks with different skill sets and requirements.
  • Multi-Agent Task Execution: Addressing tasks that require multiple agents to complete.
  • Task Prioritization: Implementing a system that can handle tasks with varying levels of priority.
  • Dynamic Workforce: Considering scenarios where the number of agents can change over time.
  • Advanced Architectures: Exploring additional hierarchy levels, latent embedded representations of actions, and graph neural networks for improved coordination and representation.

Summary updated

Abstract

In a warehouse environment, tasks appear dynamically. Consequently, a task management system that matches them with the workforce too early (e.g., weeks in advance) is necessarily sub-optimal. Also, the rapidly increasing size of the action space of such a system consists of a significant problem for traditional schedulers. Reinforcement learning, however, is suited to deal with issues requiring making sequential decisions towards a long-term, often remote, goal. In this work, we set ourselves on a problem that presents itself with a hierarchical structure: the task-scheduling, by a centralised agent, in a dynamic warehouse multi-agent environment and the execution of one such schedule, by decentralised agents with only partial observability thereof. We propose to use deep reinforcement learning to solve both the high-level scheduling problem and the low-level multi-agent problem of schedule execution. Finally, we also conceive the case where centralisation is impossible at test time and workers must learn how to cooperate in executing the tasks in an environment with no schedule and only partial observability.
BibTeX
@inproceedings{carvalho2022hierarchically,
  author = {Diogo S. Carvalho and Biswa Sengupta},
  title = {{Hierarchically Structured Scheduling and Execution of Tasks in a Multi-agent Environment}},
  booktitle = {Epia},
  year = {2022},
  doi = {10.1007/978-3-031-16474-3\_2},
}
Figure