# An Obstacle-Tolerant Path Planning Algorithm for Mobile-Anchor-Node-Assisted Localization
## 2 Related Works
### Online Path Planning Algorithm  
The benefits of the online path planning algorithms are their environmental adaptability and flexibility because they do not require any prior knowledge of the environment. In addition, in the online path planning algorithms, the MAN's path trajectory depends on the density of requests sent by unknown sensor nodes, and the MAN does not visit the entire area; therefore, online path planning algorithms are advantageous in terms of rapid positioning and power savings.  
However, they are not suitable for applications that need full localization coverage. Online path planning algorithms are conducive to specific environments where sensors are distributed in special shapes (e.g., \"C\"- or \"L\"-shaped distributions) [19; 20; 21] and not isolated by obstacles [22; 23; 21]. However, for most applications in which unknown sensors are evenly distributed, online path planning algorithms fail to guarantee full coverage of sensors' localization because the MAN's path trajectory is not deterministic and depends on the density of requests sent by unknown sensor nodes [21; 24; 25]. In addition, the location of beacon points is not globally optimal, and therefore causes the unknown nodes to receive insufficient and inappropriate location messages, resulting in collinearity problems [26]. Therefore, online and offline path planning algorithms are applied to different scenarios.  
Moreover, the online path planning algorithms are costly on hardware and communication. Hardware-wise, to implement online path planning algorithms, the MAN requires additional equipment. In [20], the MAN must configure directional antennas to receive and transmit signals in different directions and communicate with the unknown nodes within different directions in a region. In [27], the MAN was fixed with a pair of ultrasound transmitters. Each unknown node was assumed to be equipped with an ultrasound receiver at the two ends of a vehicle. Thus, the MAN behaved as a virtual ruler that traveled in the monitoring area to provide distance measurements to pairwise unknown nodes. The disadvantage of MAN in this case, is that it must configure a pair of ultrasound transmitters. In [19], a new method of mobile anchor group consisting of five mobile beacons, called maximum multi-hop of nodes (MMNs) was proposed. However, the MAN group compared to a single MAN is more expensive owing to the communication cost (CC) because unknown nodes proactively send a localization \"request\" message to the MAN in the process of positioning. Therefore, the unknown nodes consume a higher CC than the offline path planning algorithms [19; 20; 21].  
Finally, a MAN must have high computing ability because it must make decisions (e.g., move paths or broadcast timing) during movements to deal with various situations, such as [21], where nodes would be clustered first, and MAN would visit these cluster heads based on the genetic algorithm. However, the computing complexity of MBL increases with the number of unknown nodes.  
In this paper, we propose an offline path planning algorithm, which ensures that all the unknown nodes can receive three location-information from the MAN, and which optimizes the number of beacon points; therefore the MAN broadcast packet times and unknown node received packet times are reduced.