# An Obstacle-Tolerant Path Planning Algorithm for Mobile-Anchor-Node-Assisted Localization
## 2 Related Works
### Offline Path Planning Algorithm  
At present, most offline path planning algorithms assume an obstacle-free environment [7; 12; 13; 14; 15; 16; 17; 18]. In [14], MAN comprises three anchor nodes and is based on the SCAN path trajectory to visit the entire \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Path Planning Algorithm** & **Type** & **NM** &
\begin{tabular}{c} **Localization** \\ **Method** \\ \end{tabular} & **CC** & **AC** & **Accuracy** \\ \hline SCAN [7], DOUBLE-SCAN [7] & Offline & Single & Range-based & Low & No & Low \\ Hilbert [7] & Offline & Single & Range-based & Low & Yes & High \\ CZ-curve [8] & Offline & Single & Range-based & Low & No & Low \\ CIRCLES and SCUNFS [12] & Offline & Single & Range-based & Low & No & Low \\ MACL [13] & Offline & Single & Range-based & Low & No & Low \\ GMAN [14] & Offline & Multiple & Range-based & Low & Yes & High \\ LMAT [15] & Offline & Single & Range-based & Low & Yes & High \\ PT [16] & Offline & Single & Range-free & Low & Yes & High \\ SCAN-based [17] & Offline & Single & Range-free & Low & Yes & High \\ MMN [19] & Online & Multiple & Range-based & High & No & Low \\ Li [20] & Online & Single & Range-based & High & No & Low \\ MBL (Lndg [19] & Online & Single & Range-based & High & No & Low \\ MBAL [22] & Online & Single & Range-based & High & No & Low \\ DREAMS [23] & Online & Single & Range-based & High & No & Low \\ Visibility Binary Tree (WT) [24] & Online & Single & Range-based & High & No & Low \\ BRF and BTG [25] & Online & Single & Range-based & High & No & Low \\ Snake-like [26] & Online & Single & Range-based & High & No & Low \\ Virtual Ruler [27] & Online & Multiple & Range-based & High & No & Low \\ \hline \hline \end{tabular} Note: NM—Number of MAN; CC—Communication Cost; AC—Area Full Coverage.  
\end{table} 
Table 1: Comparison of path planning algorithms. sensing field. However, the construction cost of a MAN is substantially high. [PERSON] et al. proposed a localization algorithm with a mobile anchor node based on trilateration (LMAT), where the MAN moves in the trajectory of an isosceles triangle and sets the three corners of this triangle as the beacon points; thereby, solving the beacon point collinearity problem [15]. In [7], the three path planning schemes, namely SCAN, DOUBLE-SCAN, and Hilbert are compared. In the SCAN scheme, a MAN moves in a straight line along the \(X\)-axis (or \(Y\)-axis). Thus, the SCAN method covers the entire sensing field, and is convenient to implement. However, the beacon point collinearity problem remains unresolved in this scheme. In the DOUBLE-SCAN scheme, a MAN travels in straight lines along the \(x\)- and \(y\)-axes. Compared to SCAN, DOUBLE-SCAN has excessively long path lengths, thereby resulting in high energy consumption in the MAN and unknown nodes. Hence, the Hilbert method divides a sensing field into \(4^{n}\) sub-squares, and the central point of each sub-square is linked by \(4^{n}\) line segments, thereby generating non-collinear beacon points for MANs. Compared to the SCAN and DOUBLE-SCAN schemes, the Hilbert scheme substantially reduces the total path length of a MAN. The CIRCLES and S-CURVES path-planning schemes were proposed in [12] to address the collinearity problem. In the CIRCLES scheme, the center of the sensing field is treated as the center of a circle, and a trajectory of a MAN is constructed thereafter from a few concentric circles of varying dimensions. The S-CURVES method is based on SCAN, although it alters the linear paths of a MAN into \"S\" shaped curves. Compared with SCAN, DOUBLE-SCAN, and Hilbert, the CIRCLES and S-CURVES methods can provide higher localization accuracy to the unknown nodes. [PERSON] et al. proposed a scheme called mobile anchor centroid localization (MACL) [13], which is similar to CIRCLES because the former also uses the center of the sensing field as a center. However, MANs are assigned a spiral trajectory instead, thereby resulting in shorter total path lengths than those of the CIRCLES method.