# Bidirectional Long Short-Term Memory Neural Networks for Linear Sum Assignment Problems
## 3 Proposed Method
### System Model  
Figure 3 shows the proposed system architecture for solving an LSAP. A deep-learning-based BDLSTM model is first applied to the cost matrix of the LSAP. After that, a collision-avoidance algorithm is applied to solve any interference in the outputs of the proposed BDLSTM model. In the proposed BDLSTM model, the constraint in (3) is not taken into consideration, which guarantees that one job can be assigned to only one agent. This is because the proposed BDLSTM model solves each sub-assignment task as a separate classification problem. The collision-avoidance algorithm prevents one job from being assigned to multiple agents simultaneously.  
As described in Figure 4, in the proposed BDLSTM model, the cost matrix \(\mathbf{U}\) is divided into \(n\) sub-assignment tasks \(\mathbf{u}_{i}\), where \(i=1,...,n\) and \(\mathbf{u}_{i}\) is the cost vector for job \(i\). The \(\mathbf{u}_{i}\) are used as the input sequence of the BDLSTM model as \(\overrightarrow{\mathbf{h}}_{i}^{0}=\overleftarrow{\mathbf{h}}_{i}^{0}= \mathbf{u}_{i}\). After \(L\) consecutive BDLSTM layers to extract the features, all hidden states at the last layer \(\overleftarrow{\mathbf{h}}_{i}^{L}\) will be applied in an identical fully-connected layer with the softmax activation function to obtain the output matrix \(\mathbf{Y}=[\mathbf{y}_{1},...,\mathbf{y}_{n}]^{T}\):  
\[\mathbf{y}_{i}=\text{softmax}(\mathbf{W}_{y}\overleftarrow{\mathbf{h}}_{i}^ {l}+\mathbf{b}_{y}), \tag{12}\]  
where \(\mathbf{W}_{y}\) and \(\mathbf{b}_{y}\) are the weight matrix and bias of the output layer, respectively. After the BDLSTM model, a decision matrix can be obtained by \(\overline{\mathbf{Y}}=[\overline{\mathbf{y}}_{1},...,\overline{\mathbf{y}}_{ n}]^{T}\), where \(\overline{\mathbf{y}}_{i}\) is obtained by one-hot encoding of \(\mathbf{y}_{i}\). In collision avoidance, the collision cases in \(\overline{\mathbf{Y}}\) are corrected using the Hungarian algorithm by the following steps:  
* Step 1: Find jobs that are assigned to multiple or no agents.
* Step 2: Extract the cost values of jobs from Step 1 as a small LSAP.
* Step 3: Solve the LSAP from Step 2 using the Hungarian algorithm.
* Step 4: \(\overline{\mathbf{Y}}\) is modified into a decision matrix \(\mathbf{Z}\) using Step 3, where \(\mathbf{Z}\) is an \(n\) by \(n\) permutation matrix.  
For sequential data, FNNs, CNNs, and especially recurrent structures such as LSTM and BDLSTM are widely used and have achieved many successes. FNNs can be applied to every problem as the baseline architectures. CNNs are more complicated and have good performance in computer vision and some natural language processing tasks. On the other hand, LSTMs and BDLSTMs are recurrent structures built specifically for problems relating to sequential data. In the proposed method, BDLSTM is used to extract the features from the cost matrix \(\mathbf{C}\), and each classification is based on the information of the whole cost matrix. Compared to the FNN and CNN in [16], BDLSTM has memory cells, which can remember the relationship between the cost vectors of consecutive sub-assignment tasks.  
Figure 4: Proposed BDLSTM model.  
Figure 3: Proposed system model.