Genetic algorithms for navigation beacon placement design

This post is based on my master’s thesis, in which the goal was to implement a genetic algorithm for beacon placement design.

Genetic algorithms are not a new concept, and neither is locating objects based on distance measurements. But the usage of genetic algorithms for designing various sensor networks has been an active area of research in recent decades. Designing the placement of sensors within navigation networks is often a human process that requires expert knowledge and could benefit from automation.

Location determination

In a perfect world, errors do not exist, and the determined location of our object is a single point, as shown in Figure 1(a). However, in the real world, each distance measurement will have an inherent error and we end up with an area where the object could be located, as shown in Figure 1(b). The placement of the beacons will impact this area, with a poor placement increasing it, as shown in Figure 1(c). A commonly used representation of this inaccuracy is the Horizontal Dilution of Precision (HDOP), which has its origins in GPS development.

Figure 1: Trilateration. a) 3 distance measurements b) 3 distance measurements with errors c) 3 distance measurements with errors and poor placement

Placement design

Deciding the placement of beacons is a complex problem and is most often done by hand with expert knowledge. It is an example of a combinatorial explosion. As the number of placement positions and beacons increases, the number of possible solutions increases in a combinatorial manner. Heuristic methods that do not evaluate all possible solutions are required for any realistically sized problems.

Any algorithm needs some metric to optimize. HDOP would be a good candidate for this if it were not for its computational complexity. The well-seen metric is lighter to compute but should still provide a decent representation of the placement of beacons. Whether a point is well-seen, is based on its inclusion within the convex hull of visible beacons. An example with 3 beacons is shown in Figure 2.

Figure 2: Well-seen visualization. 3 beacons in blue with limited range.

Adding on to the basic structure of a genetic algorithm can be done to improve results. A modified version was implemented. It involved the addition of speciation, which involves grouping solutions based on the number of beacons, and tournament selection, which is a more advanced way of selecting the best solutions.

The benefits of genetic algorithms in comparison to simpler algorithms, as well as the suitability of the well-seen metric as an alternative to HDOP, were shown. Additionally, speciation provided improvements in some situations, but possible changes to the implementation could be examined further. An example of a final solution is shown in Figure 3, with several visibility obstructions and beacon placement areas outside the region requiring navigation.

Figure 3: Genetic algorithm optimisation result

Based on the results found in the Master’s thesis, manual expert work could be replaced with genetic algorithms when placing the beacons. Genetic algorithms also seem to produce better results than simpler algorithms.