RTAW: An Attention Inspired Reinforcement Learning Method for Multi-Robot Task Allocation in Warehouse Environments

Recent advancements in artificial intelligence (AI) and robotics have contributed to the widespread use of automation in warehouse environments. A recent case study by Honeywell¹¹1https://tinyurl.com/344p5e4y indicated more than a 50% rise in e-commerce sales after COVID-19 amidst existence of human labor shortage, thus proving the need of automating fulfillment and distribution centers/warehouses. Warehouse automation, widely being used by online retailers like Amazon, Alibaba, etc, can be performed by using multiple robots and a decision-making system. We are considering the task of picking and delivering a parcel from point A to point B [1]. By designing an appropriate multi-robot decision-making system, we can improve the task efficiency and throughput. The problem of designing such a system can be further divided into two parts: task allocation [2] and robot navigation [3]. Generally, greedy approaches are used to solve task allocation and multi-agent planning for navigation [4, 5].

We mainly deal with the problem of task allocation in multi-robot settings, which is popularly known as multi-robot task allocation (MRTA). This problem is widely studied in the literature using techniques from combinatorial optimization [2]. The problem of computing the optimal solution is NP-hard in general, and most practical solutions are based on greedy techniques [6, 5]. A comprehensive survey of MRTA problems is given in [7], which divides the problem into multiple categories depending on the robot types, task types, and task assignment to robots.

In this paper, we address the problem corresponding to the ST-SR-IA category, where we consider single-task robots (ST) which execute only a single task at any given time. All tasks are single robot tasks (SR) and task assignment is instantaneous (IA) where the task is instantaneously allocated at each decision timestep. This class of problems can be solved in polynomial time at each decision timestep [2]. Prior methods focus on developing a deterministic solution for task allocation for a given set of tasks and robots [8]. We are interested in a sequential-lifelong version of the problem where new tasks are continuously generated and task is allocated to a robot as soon as it becomes available. Our goal is to maximize the sum of utilities over time, that is, assign tasks at each instant in such a way that the total time taken to execute a specific number of tasks makespan as well as extra travel time TTD is minimized.

The existing state-of-the-art task allocation methods are mainly designed for multi-agent pickup and delivery (MAPD) and are primarily coupled with grid based navigation schemes, which are mostly designed for centralized systems [5]. Our method when combined with decentralised navigation algorithms can give rise to decentralised task-allocation and navigation with obstacle avoidance [9]. But the current practical warehouses uses only grid based navigation. Thus, this work focuses on the commonly occurring system in warehouses which is based on centralized task allocation and navigation.

Main Results: The novel components of our work include:

1. 1.

   We formulate (first time in literature) the MRTA problem in warehouse settings as a reinforcement learning problem. This require careful design of state, rewards, and actions for the problem to utilize any existing method to solve the problem.

2. 2.

   The selection of reward for MRTA problem is quite challenging and we propose to use total travel delay (TTD) as the reward after evaluating different rewards like task length, total time of robot travel, etc. Interestingly, only the TTD based rewards exhibit converging behavior.

3. 3.

   We propose a novel policy architecture that can handle a variable number of robots and tasks easily by forming useful global encoded representation using a mechanism inspired from attention. This is important because we can utilize the similar model to accommodate changes in the robot number during the execution process. with different number of robots. This also makes RTAW scalable to thousands of robots (Sec. III-C) in our simulations with constant space complexity and linear time complexity with respect to number of agents and tasks (cf. Appendix VII).

4. 4.

   We show extensive evaluations and compare against the state-of-the-art greedy baseline called myopic pickup distance minimization (MPDM) and regret-based task-selection (RBTS) for various navigation schemes, layouts and robots-number, and show an improvement of upto 10% (25 - 1000 sec) for 500 tasks. Our approach is trained with only single-agent A*, but works with other navigation schemes (SIPP and CBS). Hence it can be decoupled from the navigation system.

In the existing literature, multi-robot task allocation problem in warehouse environments is solved by standard optimization methods [7]. But in practice, tasks appear at different time instances, and robots’ availability also varies with time, which makes the problem challenging to solve via standard optimization methods. To address this issue, for the first time in this work, we formulate the multi-robot task allocation problem in warehouse environments as a reinforcement learning problem. The goal is to allocate tasks to multiple robots such that the tasks are performed in an efficient manner (i.e. resources like battery are better utilised and throughput is maximized). The formulation is challenging because it requires to define a Markov Decision Processes (MDP) for the problem. An MDP here is defined by a tuple $\mathcal{M}:=\left(\mathcal{S},\mathcal{A},R,{P},\gamma\right)$, where $\mathcal{S}$ denotes the finite state space, $\mathcal{A}$ denotes the finite action space, and $R(s,a)$ denotes the reward for state $s$ and action $a$ in $\mathcal{S}$ and $\mathcal{A}$, respectively. Further, ${P}$ represent the transition probability matrix where ${P_{a}(s,s^{\prime})}$ is the probability of transition to state $s^{\prime}\in\mathcal{S}$ from state $s\in\mathcal{S}$ after taking action $a\in\mathcal{A}$. Here, $\gamma\in(0,1)$ is the discount factor used to trade the near term reward with the long-term rewards in the RL formulation.

MDP model $\mathcal{M}$ for the multi-robot task allocation problem: Let the time instance be $t\in\mathbb{N}$ and we consider a warehouse environment with the $M$ number of robots collectively denoted by $\mathcal{R}=\{1,2,\cdots,M\}$. A warehouse environment is represented by a specific $K\times K$ grid layout (shown in Fig. 2). In this work, we do not restrict ourselves to any particular layout, and our approach is applicable to all general layouts. In fact, models trained on dense layouts have shown to give good performance on sparse layouts as well. Our test layout and task generation are described in section 4. After the task allocation at $t$, the corresponding task is removed from the queue and a new task is added. To make the problem tractable, we assume that at each $t$, only one robot is available to be allocated one of the tasks. We accomplish this by adding a small Gaussian noise of mean $0.25$ and variance $0.25$ to the task completion time. This noise value is chosen to be in (1/100)th range of the task-completion-time range. This ensures that no two robots become available at the same point in time. All the other robots are currently performing the previously allocated tasks. We move from $t$ to $t+1$ as soon as a robot becomes available after completing a task.

State: Each task $i\in\mathcal{P}$ is represented by a tuple $(o_{i},d_{i},k_{i},l_{i})$, where $o_{i}$ is the origin of the task $i$, $d_{i}$ is the destination of task $i$, $k_{i}$ denotes the distance between the selected robot’s current position to $o_{i}$, and $l_{i}$ is the length (distance between $o_{i}$ and $d_{i}$) of the task. The origin $o_{i}$ and destination $d_{i}$ for each task $i$ are the coordinates sampled from the $2$D layout. Each robot $j\in\mathcal{R}$ is also represented by a tuple $(p_{j},r_{j})$, where $p_{j}$ is position ($X-Y$ coordinates) in the $2$D map and $r_{j}$ is the time left to complete the allocated task (i.e., the task completion time). Let $j_{sel}$ denotes the available robot for task allocation. Then, the state $s$ encapsulates the robots’ positions, their task completion times, and the task list $\mathcal{P}$, which consists of tuples $(o_{i},d_{i},k_{i},l_{i})$ for all the tasks and the selected robot $j_{sel}$. Collectively, we can write the state as $s:=\big{\{}(p_{j},r_{j})_{\forall j\in\mathcal{R}},(o_{i},d_{i},k_{i},l_{i})_{\forall i\in\mathcal{P}},j_{sel}\big{\}}$ and the collection of all possible states $s$ constitutes the state space $\mathcal{S}$.

Action: An action $a$ in the environment is to select which task to execute from the list of $N$ available tasks in the queue. We define a policy $\pi:\mathcal{S}\rightarrow\mathcal{D}(\mathcal{A})$ (here $\mathcal{D}$ denotes the set of possible distributions defined over $\mathcal{A}$) which takes the current state as input and outputs a distribution across the all possible actions $a\in\mathcal{A}$. Note that in our model, $\mathcal{A}$ constitutes the list of all available tasks from which we need to select a particular task for the selected robot $j_{sel}$. During the training time, we select the action $a\sim\pi(\cdots~{}|~{}s)$ where $\pi(\cdot~{}|~{}s)$ is the probability distribution across the tasks. During the test time, we select the action in a deterministic manner by choosing a task to accomplish with maximum probability in $\pi(\cdot~{}|~{}s)$. Further, we discuss the policy architecture in detail in Sec. II-A.

Reward: Designing an appropriate reward for the RL formulation is crucial because this reward eventually decides the behavior of the policy. We define the reward as the negative of the cost, which is the time a robot takes to reach the origin $o_{i}$ of the task from its current location. In this work, we use the navigation schemes to calculate the approximate cost of the path by making the robot run through that path. This makes sense because during the time of travel from the robot’s current location to the task origin, the robot is not serving any task, and hence we aim to minimize this time. Specifically, this is defined as total travel delay (TTD), which is the extra time the robot travels when it is not executing any task. Minimizing TTD would ultimately minimize the makespan in the lifelong task allocation. We note that other reward formulations are also possible (which we tried but didn’t work) such as the negative of total task-length defined as the time taken to move from the origin to the destination of task.

Another possibility of reward is the negative of total travel time which is sum of TTD and task-length. That is, the time to travel from robot position to task origin plus time to complete the task. We call it Reward-Travel Time. We observe there exists unique minima for TTD. For task-length based rewards, it becomes non-stationary and thus hard to learn. We compare the different reward schemes in Table I.

State-Transitions: At current state $s_{t}$, we have a task list in queue $\mathcal{P}$ and one available robot (say $i\in\mathcal{R}$). At this state, we take action $a_{t}$ according to a policy $\pi(\cdot~{}|~{}s_{t})$ that decides which task would be allocated to the free robot. The selected task is removed from the list, new task gets added to the list, and the robot becomes unavailable. Our algorithm will wait until next robot becomes available which would mark our new state $s_{t+1}$. Note that the state transitions happens at irregular intervals.

In this section, we describe our implementation and analyze its performance in different settings by varying the number of robots, task generation schemes, layouts and navigation schemes. During training, we use two different navigation techniques to compute the cost for the RL environment: direct navigation and A*. In the direct navigation approach, the Euclidean distance between the robot position and task origin is used to evaluate the cost at each instant $t$. In the A* navigation, the A* algorithm is used to calculate the distance. We compare our method (RTAW) with minimum pickup distance minimization (MPDM) and regret based task selection as our baselines. Both these baselines are used in sequential single-item auctions.

MPDM algorithm chooses the task that is closest to the robot. It is optimal if there is only one robot in the system and the task utility equals the distance of the robot to the task start position (see [10] for a more in depth discussion). MPDM is the only baseline used for comparison in the literature for decoupled task allocation and navigation [24]. The other state-of-the-art [5] solutions for warehouse environments are based on coupled task allocation and navigation. Therefore, they cannot be directly applied. We present a modified version of RBTS used in [5] inspired from [30, 31].

RBTS: For every task in the list, find the distance to the closest robot. Subtract the distance of the selected robot to each of these tasks with the previous quantity. Choose the task with the maximum value (i.e. maximum regret).

For all experiments, we run the test on a fixed task set by fixing the seed of the random number generator and report TTD values for them. We train our model on the Nvidia GeForce RTX $2080Ti$ GPU with $11$GB of memory, for $4$ different environments and batch size of $32$. We run the training for $4$ million iterations which takes around $12$ hours with A* navigation algorithm. The network architecture is not bulky with GPU usage less than 5-10 %. Refer to appendix for the training curves and hyper-parameters tuning. Next, we describe the different experimental settings and discuss the experimental results in detail.

Our final reward function based on TTD exhibits better behavior than previous reward functions based on task-length. This is because task-length is a fixed quantity and does not aid in learning. It makes it hard to compute the optimal function, whereas TTD has shown to exhibit good converging behavior. We observe that we do not get good improvement for all the seeds values. There are some cases, when our model performs similar to greedy strategy. But such cases are not frequent, as shown in our results. When we compute an average over multiple runs, we always see a clear improvement. Some hyper-parameters played an important role in formulating the problem and the performance of the learning method. We choose a high $\gamma$ value as close as possible to 1 because we want to take actions that result in higher future reward and not emphasise only the immediate reward (which happens in the greedy method). We used entropy regularisation to aid the learning and deal with complex environment (i.e., larger robots, more tasks, compact layout). We reduce the entropy coefficient to help in the learning process. More details are given in the supplementary material.

Our RTAW algorithm has some limitations. One issue is handling the variable load capacity of the robots. Our current approach makes a assumption that a robot executes only one task (going from point A to point B) at a time. Another assumption we make is that robots always finish their task and are ready in terms of performing the next task right away. But this may not hold in practice due to robot’s state, battery charging etc. Our current approach can handle variable number of robots so in-order to accommodate new robots coming in and leaving the system, we just need to maintain separate system that keeps track of the total number of robots. Currently, we assume that the robots are similar or homogeneous, that is, all robots travel with same velocity and acceleration, but this is may not be the case always in the real world.

We considered a problem of multi-robot task allocation (MRTA) in warehouse environment and proposed a novel and state-of-the-art RL-based solution we called RTAW. RTAW is general and can be applied to arbitrary warehouse layouts. We have evaluated the performance of RTAW on multiple layouts and under different experimental settings, where the number of robots is varied from $10$ to $1000$. We observe that our method outperforms prior techniques based on greedy and regret-based strategies and the computational complexity scales linearly with the number of robots. Furthermore, RTAW can be combined with any centralized or decentralized navigation approach.

We analyze the performance of our method for one task allocation. The time taken for one forward pass of the model is plotted as a function of number of robots (keeping number of tasks fixed) in Figure. 4(a). The time taken for one forward pass of the model is plotted as a function of the number of tasks (keeping number of robots fixed) in 4(b). From the plots, we see that our method is scalable and linear in both number of agents and number of tasks. Our baseline greedy method is liner but regret-based is exponential.

The number of weights parameters do not change with increase in the number of the agents or tasks. Hence, it is constant in space complexity.

We have included the training curves for the cumulative reward return for the proposed method (RTAW) under different experimental settings considered in the main body of this work. The reward is received after sampling the action from a categorical distribution during training. After every $2k$ time steps we evaluate the model $20$ times and plot the mean and median graph of reward. In the following figures, y-axis denotes the cumulative reward return and x-axis denotes the number of episodes. Hyper-parameters used for training are mentioned in the Table IX.