# Navigation of Autonomous Tug via Evolutionary Algorithms with Radar Plot Fitness Evaluation
## 2 Determining a Local Passage Route Using Evolutionary Algorithms
In turn, dynamic constraints have a certain degree of uncertainty related, firstly, to the methods used on ships to detect and determine the direction of movement of other ships, i.e., radar with ARPA attachment, systems using LIDAR [10; 26], optical sensors imaging in visible light and/or infrared [10] and information distributed using the Automatic Identification System (AIS) [39]. The position of the own ship is determined using available GNSS systems, such as GPS [10] and is also burdened with a certain error, while information on speed may come from both the GNSS system and from the log or logs on board the ship. If the generated individual does not meet these conditions, several solutions can be applied. One approach is penalization in the objective function--routes violating constraints are assigned a lower fitness value, which reduces their chances of participating in crossbreeding. Alternatively, such routes can be rejected completely and replaced with new ones, generated randomly or through mutations and crossbreeding of existing individuals. The fitness evaluation of an individual in the ship route planning algorithm should assess the route's quality in terms of its traversal efficiency, considering the total route length compared to the shortest path between start and destination points, the travel time, and the number and magnitude of required maneuvers. The second factor in the assessment of fitness is the degree of safety of the designated route, taking into account whether the route does not violate static constraints and whether it bypasses static constraints at an appropriate distance. The safety assessment is usually defined in binary terms and only says whether the route is safe or not. To determine the passage route, it is necessary to know the starting and ending points. The length of the route \(L_{r}\) consisting of \(n\) sections is equal to the sum of the lengths of the sections of this route:  
\[L_{r}=\sum_{i=1}^{n}L_{i} \tag{1}\]  
where  
\(L_{i}\)--length of \(i\)-th section, and  
\(n\)--number of route sections. During the route, the ship will change course after reaching the turning points, and the total change in course \(\theta_{k}\) expressed in degrees will be equal to:  
\[\theta_{t}=\sum_{k}^{n-1}\theta_{k} \tag{2}\]  
where  
\(\theta_{k}\)--course change at of \(k\)-th waypoint, and  
\(n\)--number of route sections. Assuming that the ship's speed on a given section of the route will be constant, the total time to complete the route \(t_{t}\) will be the sum of the products of the speed on a given section and its length:  
\[t_{t}=\sum_{i}^{n}L_{i}\cdot v_{i} \tag{3}\]  
where  
\(L_{i}\)--length of \(i\)-th section, and  
\(v_{i}\)--ship speed while travelling the \(i\)-th section. Figure 1 shows an example route between two points, consisting of 3 sections and 2 waypoints. One other ship is also visible, crossing the planned course. The need to avoid it is dictated by the rules of the Convention on the International Regulations for Preventing Collisions at Sea (COLREG) [40], which specify the behavior of ships when meeting during navigation. Evolutionary Algorithm Determining a Local Passage Route Using a Radar Method of Fitness Estimation  
The presented algorithm is an extension of the classic genetic algorithm, in which instead of a simple method of assessing fitness, an innovative method based on a radar chart was used. The principle of operation of this method is based on the assessment of the surface area encompassed by the radar chart of the parameters of a given passage route represented by an individual included in the population undergoing evolution. The advantage of this method is the possibility of easily introducing many criteria for assessing the fitness of individuals, which allows the algorithm to be adapted to the specific conditions of determining a given local route. The presented algorithm uses five criteria for assessing the fitness of a given individual.