## 3 Problem Formulation  
The problem of multi-robot task allocation and navigation is defined in the context of a differential drive mobile robot moving in a 2D plane with both static and dynamic obstacles and other moving robots (all robots are homogeneous). The map is unknown; thus, each robot has a 360\({}^{\circ}\) laser scanner mounted on it. The goal locations are laid out in the environment. The number of goal locations equals the number of robots denoted by \(N\). We use the term ego-robot to describe the current robot whose perspective is used to perform the measurements and the robot whose perspective is used by the policy to compute actions.  
Each robot \(i\)--where \((1\leq i\leq N)\)--at time step \(t\) receives an observation \(O_{i}^{t}\) and calculates the output command \(a_{i}^{t}\), which drives the robot from the start position \(P_{i}\) towards the goal position \(G_{i}\). The observation is drawn from a probability distribution \(p\left(O_{i}^{t}|s_{i}^{t},a_{i}^{t}\right)\), which depends on the underlying system state and previous action. The observation for each robot is composed of four parts: \(O_{i}^{t}=\left[o_{e}^{t},o_{o}^{t},o_{l}^{t},o_{aux}^{t}\right]\), where \(o_{e}^{t}\) is the relative positions of all the goals in the ego-robot's local polar coordinates, \(o_{i}^{t}\) is the relative positions of all the goals in the other moving robots' local polar coordinates, \(o_{i}^{t}\) is the 2D laser scanner measurements, while \(o_{aux}^{t}\) is a vector containing the current time of the robot starting from the beginning of the robot's motion and the robot's previous actions \(a_{i}^{t-1}\). The observation only provides partial information about the robot's state and the other robots' states, which leads the robot to predict the other robots' intent.  
Given the observations, each robot calculates its own action independently. The action is composed of two parts: \(a_{i}^{t}=[v_{l}^{t},v_{r}^{t}]\), where \(v_{l}^{t}\) is the robot's linear velocity and \(v_{r}^{t}\) is the robot's rotational velocity. The actions are sampled from two distributions produced by a policy \((\pi)\), which is copied across all the robots:  
\[a_{i}^{t}\sim\pi_{\theta}(a_{i}^{t}|O_{i}^{t}) \tag{1}\]  
where \(\theta\) denotes the parameters of the policy. The output action guides the robot closer towards the goal that the policy selected while avoiding collisions on the way to the goal within the time limit between two observations. The target allocation is done in a way that the policy does not explicitly select one of the goals, but outputs the actions that drive the robot towards the selected goal position.  
The problem is formulated as a partially observable Markov decision process (POMDP) [17], in which a sequence of observations and actions is done by each robot forming a trajectory \(\tau_{i}\) from its start position \(P_{i}^{0}\) till the goal position chosen by the policy \(g_{i}\), where \(t_{i}^{g}\) is the traveled time. The POMDP is episodic, and each episode ends either by one of the robots having a collision, all the robots successfully reaching the unique goals' positions, or the maximum episode duration \(T_{max}\) being exhausted.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Paper** & **MRTA** & **Navigation** \\ \hline [PERSON] et al. [8] & ✓ & X \\ [PERSON] et al. [10] & X & ✓ \\ [PERSON] et al. [11] & X & ✓ \\ [PERSON] et al. [12] & X & ✓ \\ [PERSON] et al. [13] & X & ✓ \\ Our proposed method & ✓ & ✓ \\ \hline \hline \end{tabular}
\end{table}
Table 1: The summary of the presented works from the literature that either perform multi-robot task allocation (MRTA) or navigation using DRL.  
The main objective is to find an optimal policy that minimizes the expectation of the total arrival time of all robots to their goals successfully, defined as:  
\[\underset{\pi_{\theta}}{\text{argmin}}\left(E\left[\underset{i}{\text{argmax}} \left(t_{i}^{\beta}|\pi_{\theta}\right)\right]\right) \tag{2}\]