Reinforcement Learning of Multi-robot Task Allocation for Multi-object Transportation with Infeasible Tasks

Task allocation can be formulated as a combinatorial optimization problem that aims to minimize the total travel distance, and can be solved using methods such as the Hungarian algorithm [7] or integer linear programming [8]. For these methods, it is necessary to provide the required resources (number of robots) for each task. However, obtaining this information in advance may not always be possible. In addition, while the tasks need to be feasible, there are cases in which the allocated resources are insufficient to execute tasks.

Metaheuristic methods [20, 21, 22], which were inspired by biological systems and natural processes, such as the division of labor in social insects, have been used to solve MRTA problems [6]. A commonly used approach is the threshold model [20, 21], in which each robot selects tasks using activation thresholds and a stimulus associated with each task based on local information. These methods are flexible and can be adapted to different conditions with varying number of robots and tasks. However, infeasible tasks may be allocated to robots, which can lead to decreased efficiency.

The auction algorithm is a commonly used method for task allocation among multi-robots [1], and has been studied using both centralized and decentralized approaches. With the centralized approach [23], an auctioneer allocates tasks to bidders. In contrast, Choi et al. (2009) [11] proposed a decentralized auction-based algorithm without an auctioneer. With this method, tasks are allocated based on a consensus algorithm that involves local communication among bidders (robots). However, their method focused on problems in which a single robot could execute each task.

Braquet and Bakolas (2021) [12] addressed a problem similar to that in our research. It focuses on the cases in which multiple robots are required for each task. Their method employed a consensus algorithm that is similar to that of Choi et al. (2009) [11] to estimate the lists of selected tasks, winning bids, and completed allocations. The robots allocate tasks to the robot with the highest bid among the unallocated robots based on the list of completed allocations. However, this method requires the probability of completing each task, which becomes computationally challenging when dealing with objects for which the resources required for completion are unknown.

Previous studies [24, 25, 26, 27, 28, 29] have focused on task allocation problems using MARL. These methods formulate task allocation as a Markov decision process and learn policies using learning algorithms, such as MADDPG [16]. However, these methods are designed for a fixed number of agents and tasks, rendering them ineffective under different conditions. To address this issue, policy models that only obtain neighboring agents and tasks have been utilized [14, 18]. In particular, a framework for task allocation in the presence of an unknown number of robots required for cooperative transportation was proposed in previous studies [14]. This proposed framework utilizes dynamic priorities for each task and global robot communication. However, if the tasks do not have sufficient resources (number of robots), the robots may encounter a deadlock scenario until the introduction of additional robots.

Our proposed framework, which is similar to the approach proposed by Shibata et al. (2022) [14], uses dynamic priorities, but in contrast to their method, it incorporates the learning of dynamic exclusion levels for each task by leveraging task experiences broadcasted from the cloud server. Dynamic exclusion levels are used in the output gate, which temporarily resets dynamic priorities. Therefore, if a robot encounters a deadlock with a specific object, the priority of that task is reset. In addition, when more cooperative robots are introduced, the reset for that object is released, enabling the robots to again be transported cooperatively.

The cloud server stores the overall task experience $E_{l}(t)$ for object $l$ in a scalable manner based on the number of robots. $E_{l}(t)$ can be expressed as follows:

$$E_{l}(t)=\int_{0}^{t}\left(\frac{\bigl{(}1-\sigma_{0}(|\bm{v}_{l}(\tau)|)\bigr{)}\cdot|\mathcal{C}_{l}(\tau)|}{N}\right)^{\kappa}\,d\tau.$$

(1)

Here, $|\mathcal{C}_{l}(t)|$ represents the number of robots connected to object $l$ at current time $t$, and $\bm{v}_{l}\in\mathbb{R}^{2}$ represents the velocity of object $l$. In addition, $\sigma_{0}$ is a step function with a threshold of $0$, and $\kappa$ is a positive constant.

To obtain exclusion levels that are scalable with the number of objects $M$, robot $i$ learns a static policy network model that outputs the target exclusion level ${\zeta_{i}^{l}}^{\ast}$ for $K(<M)$ neighboring objects $l\in\mathcal{N}^{\mathrm{Load}}_{i}$ as follows:

$${\zeta_{i}^{l}}^{\ast}=\pi_{i}^{\zeta}(o_{i}).$$

(2)

Robot $i$ sets the current exclusion levels $\zeta_{i}^{l}$ for other objects. The target exclusion levels for all objects $l(=\{1,\cdots,M\})$ are set as follows:

$${d_{i}^{l}}=\begin{cases}{\displaystyle{\zeta_{i}^{l}}^{\ast}},\hskip 9.95845pt\text{ $l\in\mathcal{N}^{\mathrm{Load}}_{i}$}\\ {\displaystyle\zeta_{i}^{l}},\hskip 18.49428pt\text{otherwise}\end{cases}.$$

Each robot $i$ utilizes partial observables $\bm{o}_{i}$, denoted as follows:

	$\displaystyle\bm{o}_{i}\!\!\!$	$\displaystyle=$	$\displaystyle\!\!\![\bm{x}_{i}^{\top},\bm{\phi}_{i}^{l_{i1}},\cdots,\bm{\phi}_{i}^{l_{iK}},\$		(3)
			$\displaystyle\bm{x}_{j_{i1}}^{\top},\bm{\phi}_{j_{i1}}^{l_{i1}},\cdots,\bm{\phi}_{j_{i1}}^{l_{iK}},\cdots,\bm{x}_{j_{iK}}^{\top},\bm{\phi}_{j_{iK}}^{l_{i1}},\cdots,\bm{\phi}_{j_{iK}}^{l_{iK}},\$
			$\displaystyle\bm{z}_{l_{i1}}^{\top},{\bm{z}_{l_{i1}}^{\ast}}^{\top},\bm{v}_{l_{i1}}^{\top},\cdots,\bm{z}_{l_{iK}}^{\top},{\bm{z}_{l_{iK}}^{\ast}}^{\top},\bm{v}_{l_{iK}}^{\top},\$
			$\displaystyle{E}_{l_{i1}},\cdots,{E}_{l_{iK}}]^{\top},$

which contains $K(<M)$ nearest robots $j\in\mathcal{N}^{\mathrm{Robot}}_{i}:=\{j_{i1},\cdots,j_{iK}\}$, objects $l\in\mathcal{N}^{\mathrm{Load}}_{i}:=\{l_{i1},\cdots,l_{iK}\}$, and task experience $E_{l}$ for the nearest objects.

Furthermore, for objects $l\notin\mathcal{N}^{\mathrm{Load}}_{i}$ that are outside the $K(<M)$ nearest neighbors of robot $i$, a mechanism is introduced to share the exclusion levels with other robots via the cloud server at time when $\sigma(\beta_{i})$. The timing was obtained by learning a static policy network model, which is denoted as follows:

$$\beta_{i}=\pi_{i}^{\beta}(o_{i})\in[0,1].$$

(4)

Based on the above, robot $i$ updates the exclusion levels for all objects $l(=\{1,\cdots,M\})$ using a consensus protocol via the cloud server:

$$\dot{\zeta_{i}^{l}}=k_{\zeta}({d_{i}^{l}}-\zeta_{i}^{l})+k_{\zeta}\sigma(\beta_{i})N(\max_{j}\zeta_{j}^{l}-\zeta_{i}^{l}).$$

(5)

Here, $k_{\zeta}$ is a positive constant,

$$\sigma(x)=\begin{cases}1,&\text{$x\geq 0.5$}\\ 0,&\text{otherwise}\end{cases}$$

is a step function with a threshold of $0.5$ for variable $x\in[0,1]$.

Each robot sequentially allocates objects using dynamic priorities [14].

Similar to the exclusion levels, to achieve scalable learning with a number of objects $M$, robot $i$ sets the target priorities of all objects $l(=\{1,\cdots,M\})$ as follows:

$$c_{i}^{l}=\begin{cases}{\displaystyle{\phi_{i}^{l}}^{\ast}},\hskip 9.95845pt\text{ $l\in\mathcal{N}^{\mathrm{Load}}_{i}$}\\ {\displaystyle\phi_{i}^{l}},\hskip 18.49428pt\text{otherwise}\end{cases},$$

where $\phi_{i}^{l}$ is the current priority of robot $i$ for object $l$; in addition, robot $i$ learns the target priorities ${\phi_{i}^{l}}^{\ast}$ for $K(<M)$ neighboring objects $l\in\mathcal{N}^{\mathrm{Load}}_{i}$ using a policy network model as follows:

$${\phi_{i}^{l}}^{\ast}=\pi_{i}^{\phi}(o_{i}).$$

(6)

Cooperation with robots that are not located nearby is required for handling heavy objects. Therefore, similar to the exclusion level, when the required timing is $\sigma(\alpha_{i})$, robot $i$ updates the priorities for all objects $l(=\{1,\cdots,M\})$ using a consensus protocol via a cloud server:

$$\dot{\phi_{i}^{l}}=k_{\phi}({c_{i}^{l}}-\phi_{i}^{l})+k_{\phi}\sigma(\alpha_{i})\sum_{j=1}^{N}(\phi_{j}^{l}-\phi_{i}^{l}).$$

(7)

Here, $k_{\phi}$ denotes a positive constant. In addition, the timing for sharing priorities with other robots is obtained by learning a static policy network as follows:

$$\alpha_{i}=\pi_{i}^{\alpha}(o_{i})\in[0,1].$$

(8)

The exclusion level $\zeta_{i}^{l}$ in Equation (5) is integrated with priority $\phi_{i}^{l}$ in Equation (7) using the output gate, as shown in Fig. 3. The integration is expressed as follows:

$$\hat{\phi_{i}^{l}}=\left(1-\sigma(\zeta_{i}^{l})\cdot\sigma_{\mathrm{\epsilon}}(E_{l})\right)\phi_{i}^{l}.$$

(9)

Here, $\sigma_{\mathrm{\epsilon}}$ is a step function with the threshold of a small positive constant $\mathrm{\epsilon}$. If object $l$ satisfies $\zeta_{i}^{l}\geq 0.5$ and $E_{l}\geq\mathrm{\epsilon}$, transportation is determined to be infeasible with the current resources, and its priority is reset.

Finally, robot $i$ selects the object with the highest priority among priorities $\hat{\phi}_{i}^{l}\ (l=1,\cdots,M)$ after the output gate in Equation (9):

$$l_{i}^{\ast}=\underset{l\in\{1,2,\cdots,M\}}{\operatorname{argmax}}\hat{\phi}_{i}^{l}.$$

Furthermore, the priorities of the objects that have reached their goals or are being transported by other robots are set to $0$. In addition, if an object is already allocated and is being transported, the update of all priorities is stopped.

As shown in Fig. 3, using Equation (2), (4), (6), and (8), a static policy network model of robot $i$ is as follows:

$$\bm{a}_{i}=\mathrm{\pi}_{i}(\bm{o}_{i}).$$

(10)

Here, $\bm{a}_{i}$ is

$$\bm{a}_{i}=\begin{bmatrix}{\phi_{i}^{l_{i1}}}^{\ast},\cdots,{\phi_{i}^{l_{iK}}}^{\ast},\alpha_{i},{\zeta_{i}^{l_{i1}}}^{\ast},\cdots,{\zeta_{i}^{l_{iK}}}^{\ast},\beta_{i}\end{bmatrix}^{\top}.$$

In this study, the MADDPG algorithm [16] was used to perform the centralized training of the policy network model of Equation (10).

Starting positions of the participants were randomly selected, and the target positions of each object were fixed for each simulation (Fig. 4). The carrying capacity of each robot was set to $1$. By the inclusion of $N$ robots cooperating to transport the same object, it becomes possible to transport an object with a weight of $N$.

In the training experiments (Training in Table I), $N(=3)$ robots and $M(=6)$ objects were used. The weights of the objects were set to three types, including objects that cannot be transported by $N$ robots, with weights $w_{l}\in\{1,N,N+1\}$. Among the six objects, three objects had a weight of $N+1$, whereas the remaining three objects were randomly chosen from weights of $1$ and $N$ with a $50\ \%$ probability.

We used the MADDPG code [30] and set the simulation parameters listed in Table II. In the proposed method, the numbers of neighboring robots and objects for each robot were set to $K=2$. The other parameters were set as follows: $\kappa=10$, $\mathrm{\epsilon}=1$, $k_{\phi}=0.2$, $k_{\zeta}=0.2$.

The validation experiments (refer to validations 1 and 2 in Table I) used $N(=6)$ robots and $M(=10)$ objects. Among these, two objects have an untransportable weight of $w_{l}=N+1(=7)$, whereas the remaining eight objects have weights of either $\{1,3\}$ or $\{1,6\}$. The proportion of objects with weights of $3$ or $6$ was selected using $\{0,50,100\ \%\}$ probabilities, and $100$ episodes were run, with each episode consisting of 1,000 steps.

To evaluate the scalability and versatility of the proposed method, we used the following two criteria:

• •

  Success rate: The percentage of episodes in which all objects reached their goals within the total number of steps.

• •

  Transportation time: The average number of steps (seconds) until all transportable objects reached their goals for the episodes in which they succeed in transportation.

Furthermore, in an additional validation experiment (refer to Validation 3 in Table I), the number of robots was varied from $3$ to $6$ during each episode to evaluate the effectiveness of the proposed method.

The training performance of the proposed method was evaluated based on the average cumulative reward over $3$ training runs. The results were compared with those of a method that used only the dynamic priority mechanism [14] without DE and $E_{l}$), as shown in Fig. 5. Here, DE in the figure refers to dynamic exclusion.

The average cumulative reward of the method using only the dynamic priority mechanism [14] was low because the robots became stuck in a deadlock while gathering around objects that could not be transported.

However, the proposed method achieved high cumulative rewards and did not cause deadlocks. It is believed that the output gate in Equation (9), which is controlled by the dynamic exclusion in Equation (5), effectively avoids deadlock.

Fig. 7 shows the validation results obtained when increasing the number of robots and objects compared to the learning phase, with the weights of the objects remaining the same. For comparison, the results excluding the dynamic exclusion (DE) and $E$ inputs from the proposed method are shown in red and yellow, respectively. When using only the dynamic priority mechanism [14] without DE and $E$, there were cases in which objects could not be transported because of deadlock occurrences with infeasible objects, resulting in a success rate below $100\ \%$. However, the proposed method achieved successful transportation in shorter times than the other methods under all conditions. Furthermore, the proposed method reduced the transportation time when there were fewer heavy objects. This indicates that both individual and cooperative transportation occurred simultaneously, depending on the composition of the objects. These results demonstrated the scalability of the proposed method.

Fig. 7 shows the validation results obtained when increasing the number of robots and objects compared to the learning phase, including the case where there are unlearned weight values for the objects. Even for objects with unlearned weights ($=6$), the proposed method successfully completed the transport tasks. This demonstrates the versatility of the proposed method.

In Fig. 7 and 7, the policies obtained from the learning of methods removing either the DE or $E$ input from the proposed method resulted in a significant decrease in the success rate. For the method without DE (shown by the red bars in the figures), even when the ratio of weights $3$ to $6$ is zero (i.e., all objects except for infeasible ones can be transported individually with weight $1$), deadlock occurs because of the infeasible objects, and the success rate does not reach 100 %. For the method without $E$ input (shown by the yellow bars in the figures), when the ratio of weights $3$ to $6$ was $0$, the success rate reached $100\ \%$. However, when heavy objects are transported cooperatively, the success rate decreases to $0\ \%$. From these results, it can be inferred that the removal of DE results in the loss of deadlock avoidance functionality, and the removal of the $E$ input resulted in the loss of cooperative transportation capability.

We confirmed the effect of temporarily resetting the priority using output gates through an experiment (Validation 3) in which robots were added within an episode. Fig. 8 shows the results sampled during a $2,000$ s episode. In Fig. 8 (a)–(c), $3$ cooperating robots were able to transport objects weighing up to $3$ before encountering a deadlock with objects weighing $6$. In Fig. 8 (d)–(f), with $3$ additional robots, all robots cooperate to transport all objects weighing $6$.

Fig. 9 shows the number of robots connected to objects $l=1,\cdots,10$ as $|\mathcal{C}_{l}|$, and the values of the output gates $\sigma_{i}\cdot\sigma_{\mathrm{\epsilon}}$ for each robot $i=1,\cdots,6$. The results of the output gates are shown in Fig. 9 (c); evidently, the priority of objects weighing $6$ was temporarily excluded. Consequently, they were able to transport objects weighing $1$ and $3$ to the goal early without encountering a deadlock. Furthermore, after the addition of $3$ robots, the output gates were released, allowing the $6$ robots to collaboratively transport objects weighing $6$.

Fig. 10 shows the task experiences $E_{8}$ and $E_{9}$ for objects $l=8$ and $l=9$ with a weight of $6$. After $3$ robots were added at $1,000$ s, the current task experiences were recalculated with $N=6$ and the values decreased. Consequently, the temporary exclusions were released. Normalization and recalculation of task experiences using current number of robots $N$ enables the proposed method to handle objects with a weight of $6$.