extfieldsofstudy:
Computer Science
Medicine

text:
Methodology of Using Terrain Passability Maps for Planning the Movement of Troops and Navigation of Unmanned Ground Vehicles †

The determination of the route of movement is a key factor which enables navigation. In this article, the authors present the methodology of using different resolution terrain passability maps to generate graphs, which allow for the determination of the optimal route between two points. The routes are generated with the use of two commonly used pathfinding algorithms: Dijkstra’s and A-star. The proposed methodology allows for the determination of routes in various variants—A more secure route that avoids all terrain obstacles with a wide curve, or a shorter route, which is, however, more difficult to pass. In order to achieve that, two functions that modify the value of the index of passability (IOP), which is assigned to the primary fields that the passability map consists of, have been used. These functions have a β parameter that augments or reduces the impact of the applied function on IOP values. The paper also shows the possibilities of implementation of the methodology for the movement of single vehicles or unmanned ground vehicles (UGVs) by using detailed maps as well as for determining routes for large military operational units moving in a 1 km wide corridor. The obtained results show that the change in β value causes the change of a course of the route as expected and that Dijkstra’s algorithm is more stable and slightly faster than A-star. The area of application of the presented methodology is very wide because, except for planning the movement of unmanned ground vehicles or military units of different sizes, it can be used in crisis management, where the possibility of reaching the area outside the road network can be of key importance for the success of the salvage operation.

Introduction
While planning military operations, the use of terrain properties is one of the key elements that should be taken into account. The ancient Chinese philosopher Sun Tzu, in his book entitled "The Art of War", dating from the Late Spring and Autumn Period (roughly 5th century BC), noted that "with regard to ground of this nature, be before the enemy in occupying the raised and sunny spots, and carefully guard your line of supplies. Then you will be able to fight with advantage". After many centuries, although the military techniques have developed significantly, the influence of terrain on the conducted operations still remains crucial, which has been proven in previous studies [1,2]. These publications demonstrate that proper use of terrain properties allows one to gain advantage, which is quite often the element that enables one to ultimately win the battle. Land cover and formation elements have to be taken into account in order to plan the movement of both whole military units and single vehicles. Currently, in the armed forces of countries that are members of the NATO (the North Atlantic Treaty Organization), terrain evaluation and the related passability analysis are realised in compliance with the provisions of standardisation documents [3][4][5], whose aim is to uniformise, and thus to increase the possibilities of interoperability between troops within the alliance. Pursuant to the provisions of these documents, land is divided into three basic passability classes (GO, SLOW GO, and NO GO terrain). This division is based on the analysis and evaluation of the influence of various classes of land cover and formation (relief, vegetation, hydrography, developed land, transport infrastructure, etc.) on the traction possibilities of vehicles. This approach allows the commander to plan the so-called avenues of approach for own and enemy troops. If possible, those routes should not cross NO GO and SLOW GO areas. In current military practice, these avenues of approach are introduced to the map manually, so the main aim of the authors, as discussed herein, is to automate this process.

Related Works
Studies on terrain passability and accessibility have been conducted by numerous scientists in various research institutions. Their research projects focus both on the influence of single terrain factors, such as vegetation [6][7][8] and soil [9][10][11][12] on passability conditions. Some of the studies also analyse the cumulative influence of all terrain elements on passability [13][14][15]. The publications that deserve special attention are those that present complete terrain passability models. In this respect, the NATO Reference Mobility Model (NRMM) is an important project related to Cross Country Movement. It was developed and validated in the 1960s and 1970s by U.S. Army Tank Automotive Research, Development, and Engineering Center (TARDEC) and Engineer Research and Development Center (ERDC). It has been revised and updated through the years. This model is used for modelling the movement possibilities for various types of military vehicles and it covers the whole area of operation planning, including: scenario, terrain, and vehicle data [16]. Detailed descriptions of the Next-Generation NRMM are provided in the final report [17,18]. This model is connected to several research projects on various aspects of Cross Country Movement. These include, among others, the publication [19] which describes a framework for a stochastic approach for vehicle mobility prediction over large regions for integration into a NRMM. On the other hand, a comparison of the NRMM with other models in terms of the ability of military vehicles to traverse soft soils was presented in [20]. An example analysis of the influence of weather on passability conditions is the publication [21], whose authors present the results of research on the passability of vehicles that move in areas covered with snow. This paper is an elaboration of the previous studies, where the team from the Military University of Technology proposed a system for automated generation of terrain passability and accessibility maps [22]. The conducted research deals with their application with the use of various sources of spatial data [23], discussed the problems of accuracy [24,25] and the methods of cartographic visualisation of the resulting maps [26]. Apart from that, the authors proposed methodologies, conducted tests and analyses on the application of artificial neural networks (multi-layer perceptron [27] and Kohonen Self Organizing Map [28]) to generate maps. Besides the analyses of passability on the operational level, which brought results in the form of generalised maps in a small scale, the authors also proposed methods to develop high-resolution (detailed) passability models, which allow users to plan the movement of individual vehicles [29,30] of a specific type. All the studies quoted above focused on developing maps that would reflect the actual terrain situation as accurately as possible, depending on their intended application. The advantage of these studies was the opportunity to analyse the terrain to make decisions defining the optimal corridors of movement for troops. However, they had to be entered on the map manually by the operator based on the analysis of the obtained passability map. The research presented here is an elaboration on the studies conducted so far, as it refers to the modification (transformation) of previously developed models (maps) to a form that will enable to define the route in a fully automated mode, taking the passability Sensors 2021, 21,4682 3 of 26 conditions into account. Although it might seem that the field of application is rather a niche, in fact the issues of defining routes for the cross country movement of vehicles is a subject of vivid interest in the academic circles. The related literature review is presented in [31]. It shows that the main area of focus of previous studies was the determination of optimal routes for the movement of autonomous robots (UGV-Unmanned Ground Vehicle) [32]. The authors of [33] used aviation photography for this purpose. Article [34] illustrates the applicability of the method through experiments with an unmanned ground vehicle in both structured and unstructured environments. The methodologies for defining movement routes for robots are also presented in works [35][36][37][38]. In this respect, the results of experiments that show non-standard solutions are particularly interesting. They doubtlessly include the method of defining routes through the cooperation between UGV and UAV (Unmanned Aerial Vehicle) presented in [39] and the use of ant colony algorithms for defining routes [40][41][42] also in military applications [43]. Current research focuses on the autonomous movement of vehicles in a dynamic environment, full of terrain obstacles [44][45][46]. Understandably, scientists pay special attention to considering obstacles caused by terrain formation, hence a large number of publications include Digital Terrain Models in the presented methodologies [47][48][49][50].
This study focuses on determining the paths for military purposes. This is connected with the Military Unit Path Finding Problem (MUPFP) which is the problem of finding a path from a starting point to a destination where a military unit has to move, or be moved, safely whilst avoiding threats and obstacles and minimizing path cost in some digital representation of the actual terrain [51,52]. An attempt to solve this issue taking into account military conditions (enemy position, terrain conditions, etc.) was presented in papers [53,54], whose authors additionally present proprietary software that generates routes automatically. The problem of modelling terrain accessibility and defining access routes is commonly addressed in strategic computer games. Such study is presented in publications [55,56]. On the other hand, the problems of military route planning in battlefield simulation are described in [57]. It is also worth mentioning the research on automated determination of movement paths for small groups of soldiers in urban areas [58].

Research Purpose
The studies presented above focused both on developing advanced terrain passability models, which would reflect the actual field conditions as accurately as possible, and the automated determination of movement paths for various types of vehicles, in military and non-military applications. The research presented here complements the studies listed in the previous section. The main research question which the authors were confronted with was the presentation of the methodology to convert the passability model that was developed and presented by the authors in numerous publications (including [22,24,27,29,30]) as the basis for the automated generation of the optimal path. This will doubtlessly lead to improved functionality and usability of the developed model. The article presents the results concerning route determination in various configurations for military operational units as well as for determining routes for single vehicles or even UGVs by using detailed passability maps. Another purpose of the research was to find a method of route generation in two basic configurations: longer, avoiding all terrain obstacles, and shorter, but harder to overcome. It allows for a variant approach to the planning process and selecting a route that can be fully defined as "optimal" in certain conditions. The authors present the methodology for generating such routes, along with the conducted practical tests. The last, but not least important aim of the research was to perform tests of route generation with the use of the two most commonly applied search algorithms: A* [59] and Dijkstra's [60]. The authors analysed and compared both the resulting routes and the time required to generate them.
The direct and fundamental aim of the conducted research is the development of methodologies and solutions, which allow to develop a kind of "navigation system" enabling the determination of optimal routes for cross country movement on the basis of generated passability maps. The presented solutions will be implemented in a geoportal used for visualisation of the terrain situation, passability maps, and routes generated on the basis of them. Taking advantage of the geoportal and web services will surely help users to plan actions connected with the cross country movement, which we deal with during military operations and crisis management. The research presented here is a continuation and extension of the conference paper [61].

Materials and Methods
The determination of optimal routes was based on the passability maps whose development was presented in publication [22]. These maps are based on the division of terrain into primary fields of the same area. Each primary field is assigned an index of passability (IOP) value, which tells us whether the field is easy or difficult to pass. This value is the basis for the determination of the optimal route between two points. Moreover, different pathfinding algorithms (Dijkstra's and A star) were used and the IOP values were modified with the use of two functions that provide other variants of routes (shorter but harder to overcome and safer-easier to overcome and, in most cases, longer). The whole methodology will be described in detail in this section.

Area of Research
In order to show the universality of the presented methodology, the research was conducted on two kinds of terrain. The first area is located in the north-east corner of Poland near Suwalki city (54 • 06 N, 22 • 56 E) and there the determination of optimal routes was executed on the area of about 2500 square kilometers for the operational level of command. On the other hand, the second terrain is located in the west part of Warsaw (52 • 14 N, 21 • 00 E) and its surface area is only about 2 square kilometers. This analysis was conducted way more accurately on the basis of smaller primary fields (tactical level of command) and it was also enriched with the exclusion of impassable areas that came out of the microrelief analysis conducted with the use of the methodology that was widely described in [29] and of buildings. The location of areas of research is presented in Figure 1.
search algorithms: A* [59] and Dijkstra's [60]. The authors analysed and compared both the resulting routes and the time required to generate them.
The direct and fundamental aim of the conducted research is the development of methodologies and solutions, which allow to develop a kind of "navigation system" enabling the determination of optimal routes for cross country movement on the basis of generated passability maps. The presented solutions will be implemented in a geoportal used for visualisation of the terrain situation, passability maps, and routes generated on the basis of them. Taking advantage of the geoportal and web services will surely help users to plan actions connected with the cross country movement, which we deal with during military operations and crisis management. The research presented here is a continuation and extension of the conference paper [61].

Materials and Methods
The determination of optimal routes was based on the passability maps whose development was presented in publication [22]. These maps are based on the division of terrain into primary fields of the same area. Each primary field is assigned an index of passability (IOP) value, which tells us whether the field is easy or difficult to pass. This value is the basis for the determination of the optimal route between two points. Moreover, different pathfinding algorithms (Dijkstra's and A star) were used and the IOP values were modified with the use of two functions that provide other variants of routes (shorter but harder to overcome and safer-easier to overcome and, in most cases, longer). The whole methodology will be described in detail in this section.

Area of Research
In order to show the universality of the presented methodology, the research was conducted on two kinds of terrain. The first area is located in the north-east corner of Poland near Suwalki city (54°06′ N, 22°56′ E) and there the determination of optimal routes was executed on the area of about 2500 square kilometers for the operational level of command. On the other hand, the second terrain is located in the west part of Warsaw (52°14′ N, 21°00′ E) and its surface area is only about 2 square kilometers. This analysis was conducted way more accurately on the basis of smaller primary fields (tactical level of command) and it was also enriched with the exclusion of impassable areas that came out of the microrelief analysis conducted with the use of the methodology that was widely described in [29] and of buildings. The location of areas of research is presented in Figure 1.

Description of the Developed Methodology
In order to show the whole methodology used to determine optimal routes in different configurations, a block diagram was created. It is presented in Figure 2 and the successive steps of the process will be described in detail afterwards.

Description of the Developed Methodology
In order to show the whole methodology used to determine optimal routes in different configurations, a block diagram was created. It is presented in Figure 2 and the successive steps of the process will be described in detail afterwards.
The system developed by the authors [22], which has been enriched with an optimal route determination module and is now able to conduct the whole presented process. Its steps are described below. The system developed by the authors [22], which has been enriched with an optimal route determination module and is now able to conduct the whole presented process. Its steps are described below.

Block no. 1
To create a military passability map we have to take into account multiple factors that influence terrain passability. Due to the fact that there is no comprehensive database that stores all necessary information, we have to use some of them (Figure 2, 1). The most important data source was Vector Map Level 2 data (VML2). It is a spatial database created as part of a national initiative that covers the whole territory of Poland and corresponds to a military topographic map in a scale of 1:50,000-M755 series [62]. The content of this product is described by the DIGEST (Digital Geographic Information Exchange Standard) scheme, which is a standard for digital geographic information exchange between different data users, data producers, and countries [63]. The database is grouped into 11 thematic categories and includes all types of land cover, such as hydrography, vegetation, cultural, transportation, industrial, etc. Overall, there are 206 feature classes in the database developed for the territory of Poland. An example of VML2 is presented in Error! Reference source not found.a.
Another important factor is the type of soil that is crossed by troops. Their parameters are stored in the tactical soil map, which is a product released by the Military Geography Directorate in the form of SHP files. It is created on the basis of the soil-agricultural map in a scale of 1:100,000 and granulometric measurements of soils in Poland. However, the map does not take afforested areas into account. This product is designed mainly for conducting passability analysis of areas without a road network. An example of a tactical soil map is presented in Error! Reference source not found.b. To create a military passability map we have to take into account multiple factors that influence terrain passability. Due to the fact that there is no comprehensive database that stores all necessary information, we have to use some of them ( Figure 2, 1). The most important data source was Vector Map Level 2 data (VML2). It is a spatial database created as part of a national initiative that covers the whole territory of Poland and corresponds to a military topographic map in a scale of 1:50,000-M755 series [62]. The content of this product is described by the DIGEST (Digital Geographic Information Exchange Standard) scheme, which is a standard for digital geographic information exchange between different data users, data producers, and countries [63]. The database is grouped into 11 thematic categories and includes all types of land cover, such as hydrography, vegetation, cultural, transportation, industrial, etc. Overall, there are 206 feature classes in the database developed for the territory of Poland. An example of VML2 is presented in Figure 3a. Moreover, shuttle radar topographic mission data (SRTM) that are responsible for the elevation were applied to the system in a form of digital terrain model. These data are widely used in Polish Armed Forces and in the NATO countries. Their horizontal accuracy can reach about 30 m and vertical accuracy about 20 m. SRTM data are described  Another important factor is the type of soil that is crossed by troops. Their parameters are stored in the tactical soil map, which is a product released by the Military Geography Directorate in the form of SHP files. It is created on the basis of the soil-agricultural map in a scale of 1:100,000 and granulometric measurements of soils in Poland. However, the map does not take afforested areas into account. This product is designed mainly for conducting passability analysis of areas without a road network. An example of a tactical soil map is presented in Figure 3b.
Moreover, shuttle radar topographic mission data (SRTM) that are responsible for the elevation were applied to the system in a form of digital terrain model. These data are widely used in Polish Armed Forces and in the NATO countries. Their horizontal accuracy can reach about 30 m and vertical accuracy about 20 m. SRTM data are described accurately in publication [64] and they are visualized in Figure 3c.
On the other hand, in order to create a very accurate passability map, as in this research for the terrain in Warsaw, the base map in a scale of 1:500 was used. It contains the most detailed information that is available in Poland about all land cover elements such as the register of land and buildings, land development, and utility infrastructure. The map allows users to take account of all obstacles that may be located on a potential route. Its fragment is presented in Figure 3d.

Block No. 2
Maps of passability are created automatically by a system developed by the authors that was described in [22] (Figure 2, 2). Their development is based on the division of terrain into primary fields of the same area. In the presented research, these fields are squares. Other shapes were not taken into account because their change does not cause significant differences in the final output, which was shown quite clearly in [24]. However, various sizes of primary fields allowed for obtaining different detailed passability maps. It is essential for the possibility to use these maps for planning operations and determining routes for military units of various level of command because, taking into account the width of the movement corridor defined in instruction [3], it is easy to set a size of the primary fields of which the passability map should be built. All sizes with the corresponding troop sizes are presented in Table 1. In order to create a passability map, a value, which represents the possibility of overcoming this part of terrain, must be assigned to previously generated primary fields. This value is the index of passability (IOP), and it is computed on the basis of elements of land cover and landform (obtained from the data described in 2.2.1.) that are located within the analyzed primary field. The index may take a continuous value from 0 to 1, where 0 indicates completely impassable terrain and 1 wholly passable terrain with excellent tractive properties. The more objects (e.g., rivers, lakes, or forests) hinder the movement, the bigger negative impact they have on the IOP and inversely, the more they facilitate the movement (roads, bridges, tunnels, or open areas without any objects), the higher the value of the IOP. Examples of passability maps in different resolutions are presented in Table 2. In this research, the authors focused on the analysis on high resolution passability maps (2 × 2 m, 3 × 3 m, 5 × 5 m, and 10 × 10 m). On the other hand, to show the universality of presented methodology, an analysis on low resolution map (1000 × 1000 m) was also included. In order to create a passability map, a value, which represents the possibility of overcoming this part of terrain, must be assigned to previously generated primary fields. This value is the index of passability (IOP), and it is computed on the basis of elements of land cover and landform (obtained from the data described in 2.2.1.) that are located within the analyzed primary field. The index may take a continuous value from 0 to 1, where 0 indicates completely impassable terrain and 1 wholly passable terrain with excellent tractive properties. The more objects (e.g., rivers, lakes, or forests) hinder the movement, the bigger negative impact they have on the IOP and inversely, the more they facilitate the movement (roads, bridges, tunnels, or open areas without any objects), the higher the value of the IOP. Examples of passability maps in different resolutions are presented in Table 2. In this research, the authors focused on the analysis on high resolution passability maps (2 × 2 m, 3 × 3 m, 5 × 5 m, and 10 × 10 m). On the other hand, to show the universality of presented methodology, an analysis on low resolution map (1000 × 1000 m) was also included. In order to create a passability map, a value, which represents the possibility of overcoming this part of terrain, must be assigned to previously generated primary fields. This value is the index of passability (IOP), and it is computed on the basis of elements of land cover and landform (obtained from the data described in 2.2.1.) that are located within the analyzed primary field. The index may take a continuous value from 0 to 1, where 0 indicates completely impassable terrain and 1 wholly passable terrain with excellent tractive properties. The more objects (e.g., rivers, lakes, or forests) hinder the movement, the bigger negative impact they have on the IOP and inversely, the more they facilitate the movement (roads, bridges, tunnels, or open areas without any objects), the higher the value of the IOP. Examples of passability maps in different resolutions are presented in Table 2. In this research, the authors focused on the analysis on high resolution passability maps (2 × 2 m, 3 × 3 m, 5 × 5 m, and 10 × 10 m). On the other hand, to show the universality of presented methodology, an analysis on low resolution map (1000 × 1000 m) was also included. In order to create a passability map, a value, which represents the possibility of overcoming this part of terrain, must be assigned to previously generated primary fields. This value is the index of passability (IOP), and it is computed on the basis of elements of land cover and landform (obtained from the data described in Section 2.2.1) that are located within the analyzed primary field. The index may take a continuous value from 0 to 1, where 0 indicates completely impassable terrain and 1 wholly passable terrain with excellent tractive properties. The more objects (e.g., rivers, lakes, or forests) hinder the movement, the bigger negative impact they have on the IOP and inversely, the more they facilitate the movement (roads, bridges, tunnels, or open areas without any objects), the higher the value of the IOP. Examples of passability maps in different resolutions are presented in Table 2. In this research, the authors focused on the analysis on high resolution passability maps (2 × 2 m, 3 × 3 m, 5 × 5 m, and 10 × 10 m). On the other hand, to show the universality of presented methodology, an analysis on low resolution map (1000 × 1000 m) was also included.  The crucial functionality of the developed system is the possibility to modify the IOP values in order to choose a variant of the route that is the most suitable for our needs (Figure 2, 3). As a result, three different variants of routes may be generated:  The crucial functionality of the developed system is the possibility to modify the IOP values in order to choose a variant of the route that is the most suitable for our needs (Figure 2, 3). As a result, three different variants of routes may be generated:  The crucial functionality of the developed system is the possibility to modify the IOP values in order to choose a variant of the route that is the most suitable for our needs (Figure 2, 3). As a result, three different variants of routes may be generated:  The crucial functionality of the developed system is the possibility to modify the IOP values in order to choose a variant of the route that is the most suitable for our needs (Figure 2, 3). As a result, three different variants of routes may be generated:  The crucial functionality of the developed system is the possibility to modify the IOP values in order to choose a variant of the route that is the most suitable for our needs (Figure 2, 3). As a result, three different variants of routes may be generated:  The crucial functionality of the developed system is the possibility to modify the IOP values in order to choose a variant of the route that is the most suitable for our needs (Figure 2, 3). As a result, three different variants of routes may be generated:

Block No. 3
The crucial functionality of the developed system is the possibility to modify the IOP values in order to choose a variant of the route that is the most suitable for our needs (Figures 2 and 3). As a result, three different variants of routes may be generated:

1.
Finding the route directly from the computed IOP values. This variant may be called a starting variant because the index values are not modified before determining the route. This variant is presented below in Figure 4.
where β is a coefficient that amplifies or weakens the impact of the function on the IOP value, e is the Euler's number (e ≈ 2.71) and IOP is an original IOP value. Tests were performed for a β parameter ranging from 2 to 18 because lower or greater values did not significantly change the new IOPs. The use of Equation (1) allowed us to augment the differences between impassable and passable areas, which are visualized in Figure 5. This variant enables to determine a route that goes through an easy to overcome terrain and in most cases, it is longer than the route in the starting variant. 3.
Finding the route for modified IOP values by determination of their new values with use of the following equation: where ln marks the natural logarithm, IOP is an original IOP value, and the β parameter in this equation ranged from 2 to 24. Other values, similarly to the first function, did not significantly change the new IOPs. Thanks to this function, the IOPs distribution was flattened with a simultaneous decrease in the differences between passability indexes, which is presented in Figure 6. This solution enables to obtain a route which is significantly shorter but is leading through less passable areas. The crucial functionality of the developed system is the possibility to modify values in order to choose a variant of the route that is the most suitable for ou (Figure 2, 3). As a result, three different variants of routes may be generated:   The subsequent step of the process is the conversion of previously generated passability maps into a graph that consists of nodes and edges (Figure 2, 4). The methodology assumes that the centroids of primary fields are nodes and the connections between them are edges. On the basis of IOPs of neighboring primary fields, we are able to compute a cost value (Equation (3)) of the edge connecting the nodes that represent these fields. It is visualized in Figure 7.
where ln marks the natural logarithm, IOP is an original IOP value, and the β parameter in this equation ranged from 2 to 24. Other values, similarly to the first function, did not significantly change the new IOPs. Thanks to this function, the IOPs distribution was flattened with a simultaneous decrease in the differences between passability indexes, which is presented in Figure 6. This solution enables to obtain a route which is significantly shorter but is leading through less passable areas.
where ln marks the natural logarithm, IOP is an original IOP value, and the β parameter in this equation ranged from 2 to 24. Other values, similarly to the first function, did not significantly change the new IOPs. Thanks to this function, the IOPs distribution was flattened with a simultaneous decrease in the differences between passability indexes, which is presented in Figure 6. This solution enables to obtain a route which is significantly shorter but is leading through less passable areas.

Block no. 3
The subsequent step of the process is the conversion of previously generated passability maps into a graph that consists of nodes and edges (Figure 2, 4). The methodology assumes that the centroids of primary fields are nodes and the connections between them are edges. On the basis of IOPs of neighboring primary fields, we are able to compute a cost value (Equation (3)) of the edge connecting the nodes that represent these fields. It is visualized in Figure 7. Cost value will be used in the following steps to determine the optimal route ( Figure  2, 5) and it is calculated with use of Equation (3):  Cost value will be used in the following steps to determine the optimal route (Figure 2, 5) and it is calculated with use of Equation (3): where IOP 1 and IOP 2 are values of neighboring nodes of the currently analyzed edge. The lower the IOP values are, the bigger the cost is, and the more likely it is that the pathfinding algorithm will not choose this edge as a part of the optimal route. All computed cost values are assigned to edges and the graph prepared in this way can then be used in further steps.

Block No. 6
This step is used in high resolution analysis (for the tactical level of command). It uses the methodology described in [29] to generate impassable areas based on digital elevation models (DEM) in high resolution (Figure 2, 6). Additionally, the authors assumed that buildings are objects that cannot be passed by a vehicle, so they were also considered as impassable terrain. Having obtained such areas we are able to find and exclude nodes and edges from the graph that intersect them. This step is visualized in Figure 8.

Block no. 5
Cost value will be used in the following steps to determine the optimal route ( Figure  2, 5) and it is calculated with use of Equation (3): where IOP1 and IOP2 are values of neighboring nodes of the currently analyzed edge. The lower the IOP values are, the bigger the cost is, and the more likely it is that the pathfinding algorithm will not choose this edge as a part of the optimal route. All computed cost values are assigned to edges and the graph prepared in this way can then be used in further steps.

Block no. 6
This step is used in high resolution analysis (for the tactical level of command). It uses the methodology described in [29] to generate impassable areas based on digital elevation models (DEM) in high resolution (Figure 2, 6). Additionally, the authors assumed that buildings are objects that cannot be passed by a vehicle, so they were also considered as impassable terrain. Having obtained such areas we are able to find and exclude nodes and edges from the graph that intersect them. This step is visualized in Figure 8. As a result of the exclusion, the number of edges to be processed in further steps decreases. As a consequence, the duration of the whole process is shortened. In this research, the determination of impassable areas was conducted for the 1 m DEM resolution because this value turned out to be optimal for this kind of analysis [29]. Moreover, all areas covered by building objects that are located within the analyzed terrain were also included as impassable ones. Subsequently, regardless of the resolution of the graphs, all nodes and edges that intersected impassable areas were deleted from the route determination process. As a result of the exclusion, the number of edges to be processed in further steps decreases. As a consequence, the duration of the whole process is shortened. In this research, the determination of impassable areas was conducted for the 1 m DEM resolution because this value turned out to be optimal for this kind of analysis [29]. Moreover, all areas covered by building objects that are located within the analyzed terrain were also included as impassable ones. Subsequently, regardless of the resolution of the graphs, all nodes and edges that intersected impassable areas were deleted from the route determination process.

Block No. 7
On the basis of the generated graph, we are able to determine the optimal route between two points (Figure 2, 7). In the research discussed here, this operation was executed with the use of two pathfinding algorithms: Dijkstra's and A-star search algorithm. The first of them allows to find the shortest path in a graph with non-negative weights [60]. The use of this algorithm was presented in [65] where the authors demonstrated that the discussed algorithm managed to determine an optimal route between points randomly distributed within a city in Indonesia. Dijkstra's algorithm realizes the so-called greedy approach. In each iteration, one of the unvisited nodes, which can be reached with the lowest cost, is chosen. After the determination of a path to a specific node, it will not be modified during the execution of the rest of the algorithm. Dijkstra's algorithm is described in more detail in [66].
The second pathfinding algorithm used in this project was A-star. As opposed to Dijkstra's algorithm, A-star performs an informed search. It takes into account the location of the source and target node and thanks to that the routing query prefers links which are closer to the target node. A more detailed description of A-star is presented in [67]. Moreover, this algorithm was used by some researchers. A team from Slovakia used A-star for planning a path for a mobile robot and showed that this algorithm was the fastest to find the path [68]. Esat Dere and Akif Durdu, researchers from Turkey, used the discussed algorithm to find the shortest path in transportation systems and provided some interesting results [69]. The comparison of these two pathfinding methods is presented in Figure 9.
cuted with the use of two pathfinding algorithms: Dijkstra's and A-star search algorithm. The first of them allows to find the shortest path in a graph with non-negative weights [60]. The use of this algorithm was presented in [65] where the authors demonstrated that the discussed algorithm managed to determine an optimal route between points randomly distributed within a city in Indonesia. Dijkstra's algorithm realizes the so-called greedy approach. In each iteration, one of the unvisited nodes, which can be reached with the lowest cost, is chosen. After the determination of a path to a specific node, it will not be modified during the execution of the rest of the algorithm. Dijkstra's algorithm is described in more detail in [66].
The second pathfinding algorithm used in this project was A-star. As opposed to Dijkstra's algorithm, A-star performs an informed search. It takes into account the location of the source and target node and thanks to that the routing query prefers links which are closer to the target node. A more detailed description of A-star is presented in [67]. Moreover, this algorithm was used by some researchers. A team from Slovakia used A-star for planning a path for a mobile robot and showed that this algorithm was the fastest to find the path [68]. Esat Dere and Akif Durdu, researchers from Turkey, used the discussed algorithm to find the shortest path in transportation systems and provided some interesting results [69]. The comparison of these two pathfinding methods is presented in Figure 9.

Block no. 8
The final step of the process is to export the determined routes to a shapefile (SHP) format (Figure 2, 8). Thanks to this we can distribute the output to different systems or platforms where it can be analyzed. What is more, the developed methodology allows us to generate two kinds of output: the whole and the segmented route. As a segment we understand a part of the whole route within a primary field. The difference is presented in Figure 10.

Block No. 8
The final step of the process is to export the determined routes to a shapefile (SHP) format (Figure 2, 8). Thanks to this we can distribute the output to different systems or platforms where it can be analyzed. What is more, the developed methodology allows us to generate two kinds of output: the whole and the segmented route. As a segment we understand a part of the whole route within a primary field. The difference is presented in Figure 10.
cuted with the use of two pathfinding algorithms: Dijkstra's and A-star search algorithm. The first of them allows to find the shortest path in a graph with non-negative weights [60]. The use of this algorithm was presented in [65] where the authors demonstrated that the discussed algorithm managed to determine an optimal route between points randomly distributed within a city in Indonesia. Dijkstra's algorithm realizes the so-called greedy approach. In each iteration, one of the unvisited nodes, which can be reached with the lowest cost, is chosen. After the determination of a path to a specific node, it will not be modified during the execution of the rest of the algorithm. Dijkstra's algorithm is described in more detail in [66].
The second pathfinding algorithm used in this project was A-star. As opposed to Dijkstra's algorithm, A-star performs an informed search. It takes into account the location of the source and target node and thanks to that the routing query prefers links which are closer to the target node. A more detailed description of A-star is presented in [67]. Moreover, this algorithm was used by some researchers. A team from Slovakia used A-star for planning a path for a mobile robot and showed that this algorithm was the fastest to find the path [68]. Esat Dere and Akif Durdu, researchers from Turkey, used the discussed algorithm to find the shortest path in transportation systems and provided some interesting results [69]. The comparison of these two pathfinding methods is presented in Figure 9.

Block no. 8
The final step of the process is to export the determined routes to a shapefile (SHP) format (Figure 2, 8). Thanks to this we can distribute the output to different systems or platforms where it can be analyzed. What is more, the developed methodology allows us to generate two kinds of output: the whole and the segmented route. As a segment we understand a part of the whole route within a primary field. The difference is presented in Figure 10.  The whole route is the standard output while the segmented one can be used to monitor changes of terrain difficulties along the route in the form of a chart presenting e.g., the cumulative cost. All analyses are thoroughly discussed in Section 4.

Results
Due to the fact that this article concerns the possibility of using the presented methodology in navigation of UGVs (very detailed level), the main attention will be focused on the results from high resolution passability maps (terrain in Warsaw). However, the analysis for the area near Suwalki city (operational level of command) better shows the dependences between used functions (described in Section 2.2.4), which will be presented in further sections. In the analysis, routes between start and end points were generated and they went through two types of terrain: urban and undeveloped. The location of the used start and end points is presented in Figure 11. In white there are also shown areas excluded from the analysis (buildings and microrelief obstacles), which should be avoided by generated routes. The whole route is the standard output while the segmented one can be used to monitor changes of terrain difficulties along the route in the form of a chart presenting e.g., the cumulative cost. All analyses are thoroughly discussed in Section 4.

Results
Due to the fact that this article concerns the possibility of using the presented methodology in navigation of UGVs (very detailed level), the main attention will be focused on the results from high resolution passability maps (terrain in Warsaw). However, the analysis for the area near Suwalki city (operational level of command) better shows the dependences between used functions (described in Section 2.2.4.), which will be presented in further sections. In the analysis, routes between start and end points were generated and they went through two types of terrain: urban and undeveloped. The location of the used start and end points is presented in Figure 11. In white there are also shown areas excluded from the analysis (buildings and microrelief obstacles), which should be avoided by generated routes. The illustrations below show the optimal routes generated for different functions and for various β coefficients. Their values were adjusted in order to show the changes in the determined routes. Different parts of the chosen terrain and consequently, different distributions of IOP values make the functions influence the road determination disparately. Figure 12 shows the results for routes in the undeveloped area, Figure 13 presents the outcome for routes in the urban area and the optimal routes for the area near Suwalki city are shown in Figure 14. The illustrations below show the optimal routes generated for different functions and for various β coefficients. Their values were adjusted in order to show the changes in the determined routes. Different parts of the chosen terrain and consequently, different distributions of IOP values make the functions influence the road determination disparately. Figure 12 shows the results for routes in the undeveloped area, Figure 13 presents the outcome for routes in the urban area and the optimal routes for the area near Suwalki city are shown in Figure 14.  The generation times of routes are also a crucial factor in the analysis. They depend mainly on the resolution of the used passability map and slightly on the used algorithm. The whole process of generating a route was divided into two parts. The first one is the determination of a route and the second one is exporting the designated route to a Shapefile (SHP). Generation times on the example of a starting variant route in the undeveloped area are presented in Table 3 and the parameters of the server, on which all tests were carried out, are as follows:

Discussion
Generally speaking, the obtained results showed that the pathfinding algorithms used are able to determine optimal routes between two points. Optimal means that the routes were generated on the basis of a graph with weighted edges (cost values), which enabled us to choose the edges with the lowest cost. As a result of the exclusion of impassable areas obtained in microrelief analysis and buildings, unnecessary edges which were located on these parts of the terrain were removed from the graph. This operation ensures that the vehicle which will be moving along the determined route will not face an obstacle that will hinder or prevent the relocation. Different resolutions of the used passability maps, which were the basis for generating the graph, made the excluded areas more and more generalized, which forced the pathfinding algorithm to change the course of the route in some places. Such situations are presented in Figure 15. The generation times of routes are also a crucial factor in the analysis. They depend mainly on the resolution of the used passability map and slightly on the used algorithm. The whole process of generating a route was divided into two parts. The first one is the determination of a route and the second one is exporting the designated route to a Shapefile (SHP). Generation times on the example of a starting variant route in the undeveloped area are presented in Table 3 and the parameters of the server, on which all tests were carried out, are as follows:

Discussion
Generally speaking, the obtained results showed that the pathfinding algorithms used are able to determine optimal routes between two points. Optimal means that the routes were generated on the basis of a graph with weighted edges (cost values), which enabled us to choose the edges with the lowest cost. As a result of the exclusion of impassable areas obtained in microrelief analysis and buildings, unnecessary edges which were located on these parts of the terrain were removed from the graph. This operation ensures that the vehicle which will be moving along the determined route will not face an obstacle that will hinder or prevent the relocation. Different resolutions of the used passability maps, which were the basis for generating the graph, made the excluded areas more and more generalized, which forced the pathfinding algorithm to change the course of the route in some places. Such situations are presented in Figure 15. Moreover, the application of functions (1) and (2), which modify IOP values, enabled us to generate different variants of routes. The use of function (1) results in a route that is in most cases longer than the starting variant and crosses terrain that is easier to overcome. On the other hand, function (2) makes the routes shorter but much harder to overcome. All variants are presented in Figures 12-14, where the resulting routes clearly prove that with the increase of β coefficient with use of function (1) the obtained route usually becomes longer. It is noticeable that its course avoids the areas of worse passability. Along with the rise of the β coefficient, the route moves to areas that are easier to overcome, somehow avoiding impassable areas with a wider and wider curve. The reason for that is the stretch of IOPs distribution resulting in an augmentation of differences between them. In practice, this means that lower indexes of passability (from 0 to 0.5) become progressively lower, while indexes greater than 0.5 increase and become close to Moreover, the application of functions (1) and (2), which modify IOP values, enabled us to generate different variants of routes. The use of function (1) results in a route that is in most cases longer than the starting variant and crosses terrain that is easier to overcome. On the other hand, function (2) makes the routes shorter but much harder to overcome. All variants are presented in Figures 12-14, where the resulting routes clearly prove that with the increase of β coefficient with use of function (1) the obtained route usually becomes longer. It is noticeable that its course avoids the areas of worse passability. Along with the rise of the β coefficient, the route moves to areas that are easier to overcome, somehow avoiding impassable areas with a wider and wider curve. The reason for that is the stretch of IOPs distribution resulting in an augmentation of differences between them. In practice, this means that lower indexes of passability (from 0 to 0.5) become progressively lower, while indexes greater than 0.5 increase and become close to 1. The use of function (2) has an opposite effect-the determined route becomes shorter with the increase of β coefficient. Its shape is increasingly closer to the straight line between two points which connects the start and end points in the shortest way. The direct reason for that is an aggregation of IOPs distribution, which practically makes the differences between obtained indexes of passability smaller. These dependences are presented in Figures 16 and 17. usually becomes longer. It is noticeable that its course avoids the areas of wors bility. Along with the rise of the β coefficient, the route moves to areas that are overcome, somehow avoiding impassable areas with a wider and wider curve. son for that is the stretch of IOPs distribution resulting in an augmentation of dif between them. In practice, this means that lower indexes of passability (from become progressively lower, while indexes greater than 0.5 increase and become 1. The use of function (2) has an opposite effect-the determined route becomes with the increase of β coefficient. Its shape is increasingly closer to the straight tween two points which connects the start and end points in the shortest way. Th reason for that is an aggregation of IOPs distribution, which practically makes ferences between obtained indexes of passability smaller. These dependences sented in Figures 16 and 17.    As a result of the application of various functions, algorithms, and β coefficients, the generated routes have various statistics. The most representative ones, which best reflect the nature of the route, are shown in Figures 18-21. They present how the length of route and an estimator, which measures the "difficulty" of overcoming the route (average cost of overcoming 1 km of designated route), influence the change of β coefficient. In order to determine how the average cost of getting across each primary field changes, the standard deviation of the costs of overcoming the subsequent primary fields, followed by the route, was calculated. Charts are grouped in order to facilitate their analysis. High standard deviation demonstrates that the variability of passability conditions is great and occurs when function (2) is used. This makes the routes shorter and more difficult to overcome (the cost increases with the growth of the β coefficient). If function (1) is applied, the route, despite being longer, passes through the primary fields whose indexes of passability change slightly and whose passability is good or very good. Reversely to Dijkstra's algorithm, in A-star the length of routes generated with use of function (1) decreases with the growth of β coefficient. Dijkstra's algorithm tries in this case to avoid obstacles or areas that are harder to overcome by taking a wider and wider curve, while the A-star algorithm tries to find the shortest way that passes through the primary fields of reduced IOP values (result of function (1)). This behavior will be explained based on Figure 22.
One may clearly notice that function (1) amplifies the differences between IOP values and using greater and greater β coefficient results in a passability map that consists of primary fields of values close to 0 and 1. IOPs from 0 to 0.5 in the starting variant are converted into values close to 0 and IOPs from 0.5 to 1 into values closer to 1, which is visible in Figure 22a. As far as the course of the routes is concerned (Figure 22b), one may notice that the green dashed route, which was created on the basis of passability map of β = 18, crosses terrain that has worse passability on passability maps resulting from lower values of β coefficient (in case of Figure 22-β = 8) or from the starting variant. The expression 'worse passability' refers to a terrain which has lower IOP values, and consequently it is marked in more saturated color on the passability map. Such situations occur in area surrounded by a black dashed line in Figure 22. However, in the passability map of β = 18, which is corresponding to the designated green dashed route, the route does not cross the worse passable area.  In conclusion, the use of function (1) blurred the differences between IOP values from 0 to 0.5 and from 0.5 to 1. The A-star algorithm was searching for the shortest route in the end point direction and consequently, in greater β values it managed to find a route that was shorter than the previous ones and had a lower cost as well. This was due to the fact that the areas of slightly worse passability were converted with use of a function (1) into areas of a good passability. As a result, the A-star algorithm cannot be treated as fully secure, because for greater values of β coefficient in function (1) it can generate a route that leads through areas which actually have worse passability. In Dijkstra's algorithm this situation never happens, and it avoids all obstacles with an increasingly wide curve, which makes the resulting route more secure.   Figure 19 also shows the comparison of the two discussed algorithms, but this time for a higher resolution (5 m). Here, one may observe the same dependences in both outcomes. The length of routes in function (1) grows with the increase of β coefficient but in case of A-star algorithm the growth is not as steady as in Dijkstra's ( Figure 19b). The biggest fluctuation is in β = 8, where the length of a route unexpectedly drops. The rest of the statistics behave quite similarly.
As far as the Dijkstra's algorithm in different resolutions is concerned (Figure 20), all statistics have the same pattern. In function (1) the length of the routes grows, but the cost per 1 km and the cost standard deviation decrease steadily. The inverse situation may be observed in case of function (2). It is worth noticing that the generated routes become longer along with the growth of the pixel size of a passability map, e.g., in the 2 m resolution map the longest route is slightly over 2000 m long but in the 10 m resolution map the length of the longest route increases to approximately 2450 m. The standard deviation values also grow with the increase of the resolution. However, the statistics from Dijkstra's algorithm seem to be more stable than those from A-star, which is clearly visible in Figure 21.
(1) is applied, the route, despite being longer, passes through the primary fields whose indexes of passability change slightly and whose passability is good or very good. Reversely to Dijkstra's algorithm, in A-star the length of routes generated with use of function (1) decreases with the growth of β coefficient. Dijkstra's algorithm tries in this case to avoid obstacles or areas that are harder to overcome by taking a wider and wider curve, while the A-star algorithm tries to find the shortest way that passes through the primary fields of reduced IOP values (result of function (1)). This behavior will be explained based on Figure 22. One may clearly notice that function (1) amplifies the differences between IOP values and using greater and greater β coefficient results in a passability map that consists of primary fields of values close to 0 and 1. IOPs from 0 to 0.5 in the starting variant are converted into values close to 0 and IOPs from 0.5 to 1 into values closer to 1, which is visible in Figure 22a. As far as the course of the routes is concerned (Figure 22b), one may notice that the green dashed route, which was created on the basis of passability map of β = 18, crosses terrain that has worse passability on passability maps resulting from lower values of β coefficient (in case of Figure 22-β = 8) or from the starting variant. The expression 'worse passability' refers to a terrain which has lower IOP values, and consequently it is marked in more saturated color on the passability map. Such situations occur in area surrounded by a black dashed line in Figure 22. However, in the passability map of β = 18, which is corresponding to the designated green dashed route, the route does not cross the worse passable area.
In conclusion, the use of function (1) blurred the differences between IOP values from 0 to 0.5 and from 0.5 to 1. The A-star algorithm was searching for the shortest route in the end point direction and consequently, in greater β values it managed to find a route that was shorter than the previous ones and had a lower cost as well. This was due to the fact that the areas of slightly worse passability were converted with use of a function (1) into areas of a good passability. As a result, the A-star algorithm cannot be treated as fully secure, because for greater values of β coefficient in function (1) it can generate a route that leads through areas which actually have worse passability. In Dijkstra's algo-  (1); (b) Resulting routes from function (1) of given β coefficient.
As described earlier, in this situation the length of the routes decreases with the increase of the β coefficient (2 m and 3 m resolution). In 5 m and 10 m maps, the length behaves similarly to Dijkstra's algorithm (it is growing). Moreover, the cost per 1 km value is almost the same in each case but the standard deviation of costs is diversified. All its values become greater with the increase of the resolution, which proclaims that in lower resolutions the variability of passability conditions is more significant.
What is more, the cumulative cost charts, which are presented in Figure 23, offer other interesting results. They show the change of cost with the increase of the distance from start to end point. Charts were created for three variants of routes in four different situations (various parameters). The grey dashed lines mark the growth of the cost when it is stable and equal along the whole route, while the colored lines signify real values.
Various β coefficients of routes, which were the basis for creating the charts, were adjusted in order to show the changes between them and starting variant as clearly as possible. On the cumulative cost charts, one may see mainly that in most cases the routes are designated on the basis of edges of the same or close costs (the colored and dashed lines overlap largely). Such situation is visible in all cases of function (2), in the starting variant without the lowest resolution case (Figure 23d) and in function (1) in the highest resolution case (Figure 23a). The remaining charts are not as stable, and the highest volatility may be observed for function (1) in 5 m and 10 m resolution cases (Figure 23c,d). However, in most cases the cost in the early parts of the routes is smaller than the average value (the colored line is below the dashed line) and in the closing parts the cost becomes higher. It makes the charts concave in relation to the average value (grey dashed line). It means that the used algorithms mainly generate routes with gradually increasing cost. An example of that is shown in Figure 24.
One may easily notice that the trend line of costs is upward, which means that the further away we are moving, the higher the difficulty of moving along the designated route is becoming. Such a situation is present in most obtained results.
As far as the performance of the methodology is concerned (Table 3), the generation time of one route decreases due to the growth in the size of a primary field of the passability map used. The bigger the primary field is, the fewer edges the algorithm has to process to obtain a route between two points. It certainly has the biggest influence on the route generation time. It is also worth noting that in this research project, the routes were only about 2 km long and if the start and end points were much further apart, the generation of routes would also take much longer. Moreover, there is a slight difference between Dijkstra's and A-star algorithms. Despite the fact that the A-star algorithm needs to analyze fewer edges to find an optimal route (Figure 9), it works a little bit slower than Dijkstra's.
The comparison of the route determination times in different resolutions reveals that the A-star algorithm needs about 20-25% more time to determine the optimal route. With the increase of a distance between start and end point the route determination time in Dijkstra's algorithm can be significantly shorter. What is more, the longest part of the route generation process is the export of the designated route to an SHP file. It takes about 95% of the whole process. This is caused by the queries that are sent to the database (PostgreSQL in case of this research) in order to create a separate file containing selected graph edges. One may see that the SHP generation times in Dijkstra's and A-star algorithm are more or less the same, which means that this part of the process is independent from the used algorithm.

Conclusions
The methodology proposed in this article shows the way to obtain a graph that allows one to find the optimal route, on the basis of the developed passability map built of square primary fields. Due to the fact that the developed passability maps take into account most land cover elements, the generated route is credible and thanks to the use of Dijkstra's or A-star algorithm it can be treated as optimal. It turned out that modifying the indexes of passability, which are the basis for generating graphs, and consequently routes, was an interesting experiment. The use of function (1) allowed us to obtain a route that was usually longer, but crossing well passable areas. Routes generated with the use of function (2) were significantly shorter but they led through areas of worse passability. Such variant approach improves the possibility of planning the movement of troops or the determination of, e.g., UGV movement.
The detection of impassable areas allows users to remove edges that intersect them from the graph. This operation ensures that the designated route will not cross any areas that are impossible to overcome. The authors assumed that impassable areas are buildings and terrain with microrelief shapes that the vehicle may get stuck on. The methodology of detecting impassable areas due to the landform is presented in article [29].
The obtained results demonstrate that the change of the resolution of a passability map affects the courses of generated routes, as it was presented in Figure 15. The reason for that is the generalization of the passability map. In higher resolutions the routes in some cases may maneuver between dispersed impassable places while in lower resolution the degree of generalization is so big that the routes tend to completely avoid clusters of these areas (Figure 15, 1).
The change of the β coefficient in used functions allowed us to obtain different variants of the generated routes and to see how they behave for various β values. As it was expected, in most cases the routes become longer while increasing the β coefficient in function (1) and the routes become shorter with the increase of this parameter in function (2). However, in some cases the output routes do not follow this rule and their length decreases while augmenting β coefficient. This behavior happens only in the A-star algorithm and the reason of that has been described on the basis of Figure 19 in the previous section. This makes the Dijkstra's algorithm more secure because it always avoids areas that are harder to overcome. For greater β values in function (1), it never generates a route that crosses terrain of an actually worse passability. On the other hand, in very detailed passability maps (2 m and 3 m) in greater β values in function (1) the A-star algorithm generated routes that led through less passable areas. In this algorithm it is sufficient to set a small β value (not exceeding 8) in function (1) to obtain a route that meets the assumptions of this variant-longer but easier to overcome. Due to the fact that we do not know the exact value of β, which will cause the shortening of a route and lead it through areas that are harder to overcome, it is more secure to use Dijkstra's algorithm.
The cumulative cost charts also provide a good overview of the characteristics of the generated routes. From them ( Figure 23) one may conclude that the distribution of costs along the route was mainly stable. The cost line was in most cases close to a straight line connecting 0 and total cost value of a route. However, the A-star algorithm turned out to be not as stable as Dijkstra's. Taking into account parts (c) and (d), one may see in function (1) a high volatility of cost along the route. What is more, cost lines are mainly located below the average cost value line (grey dashed line), which means that the cost in initial parts of a route is lower and in further part there is a visible increase. This is confirmed by the chart presenting a trend line of the chosen route (Figure 24), where it is visibly growing. Such a situation happens for most of the generated routes.
Moreover, according to Table 3, which presents the results of the performance analysis, the generation time of the routes decreases due to the increase of a primary field size of the passability map. It has the biggest influence on generation time, and it happens because in lower map resolution the graph consists of fewer edges than in maps of higher resolution. As far as the used algorithms are concerned, despite having more primary fields to analyze, Dijkstra's algorithm is about 20% faster than A-star. A major part of the route generation time is the SHP file generation, which takes about 95% of the whole duration of the process. It is caused by the queries that are sent to the database in order to extract the selected edges and create a new file consisting only of a single route.
The presented methodology is universal because it can be used for planning the movement in a wide maneuver corridor (1 km) as well as for the several-meter corridor on the basis of detailed maps of passability. Analyzes showed that Dijkstra's algorithm is more convenient to use than A-star because it is more stable and works faster. It is worth mentioning that the module of route generation is an integral part of an IT system, which provides fully automated development of passability maps, their conversion into graphs, and also automated route generation. The area of application of the constructed system is very wide because, except for planning the movement of large military units or UGVs, the use of detailed passability maps is of key importance for crisis management, where the possibility of reaching the area outside the road network can be crucial for a success of the salvage operation.


extfieldsofstudy:
Computer Science
Engineering

text:
Diarization of Legal Proceedings. Identifying and Transcribing Judicial Speech from Recorded Court Audio

United States Courts make audio recordings of oral arguments available as public record, but these recordings rarely include speaker annotations. This paper addresses the Speech Audio Diarization problem, answering the question of"Who spoke when?"in the domain of judicial oral argument proceedings. We present a workflow for diarizing the speech of judges using audio recordings of oral arguments, a process we call Reference-Dependent Speaker Verification. We utilize a speech embedding network trained with the Generalized End-to-End Loss to encode speech into d-vectors and a pre-defined reference audio library based on annotated data. We find that by encoding reference audio for speakers and full arguments and computing similarity scores we achieve a 13.8% Diarization Error Rate for speakers covered by the reference audio library on a held-out test set. We evaluate our method on the Supreme Court of the United States oral arguments, accessed through the Oyez Project, and outline future work for diarizing legal proceedings. A code repository for this research is available at github.com/JeffT13/rd-diarization

Introduction
Courts of record across the United States have increasingly migrated to audio recordings as the primary format for the public dissemination of oral arguments. While audio recordings enable widespread access to important records, their utility is limited without transcription and diarization. This is true for both the academic research community and the legal industry: easy access to clean court proceeding text would both facilitate new academic research into the judiciary and contribute to new tools to improve access to affordable legal services.
Diarization answers the question of "Who spoke when?". Common approaches to the problem are derived from the speaker verification literature, and can be divided into either Text-Dependent Speaker Verification (TDSV) or Text-Independent Speaker Verification (TISV) [1]. Diarization of untranscribed legal proceedings is a TISV task, which is often more difficult than TDSV. Diarization is an open problem in speech processing; casual inspection of a variety of available commercial APIs for this purpose do not produce satisfactory results on legal audio, which is characterized by many unique speakers in a single recording, unequal durations of speech turns both within and across speakers, and unusually long audio recordings. But while these features render court proceeding diarization challenging for existing systems, there are important characteristics of these data that can facilitate diarization as well. In particular, the audio contains minimal background noise and overlapped speech. In addition, due to the judicial system's rich metadata, we know ex ante which speakers can be present in a given recording. Since most of the speakers for a given court system reoccur frequently, this renders our task as an open-set Speaker Identification problem [2]. We therefore look to implement a diarization pipeline that overcomes the challenging aspects of legal proceedings and exploits the advantageous ones.
To prototype and evaluate diarization strategies for the legal domain, we leverage data from the Oyez Project [3]. Oyez conveniently provides a publicly available database of thousands of transcribed, diarized, and time-stamped Supreme Court of the United States (SCOTUS) oral arguments retrievable through a public API. Each proceeding contains at least two lawyers in addition to some or all of the nine Supreme Court Justices.
This dataset is a useful benchmark for diarization in the legal domain. Records are typically between 40 and 80 minutes long, contain 8-13 speakers who speak in varied amounts, and contain mostly adult male voices, making TISV challenging 1 . These features are relatively unique among the datasets commonly used in diarization evaluation. Typically, diarization datasets emphasize challenges such as multiple settings (DIHARD [4], SITW [5]), multilingual conversation (CALL-HOME 2 ), or background noise (VOICES [6]). They do not contain a high percentage of reoccurring speakers, and so do not well represent our use case. The Broadcast News datasets ( [7], [8], [9]) have reoccurring speakers, but are small and in general contain very little interjection. This paper describes the creation of a simple and efficient diarization open-source tool 3 that considers the advantages and challenges in the legal domain, which we refer to as Reference-Dependent Speaker Verification (RDSV). We utilize a speech embedding network trained with the Generalized End-to-End Loss [1] to encode speech into d-vectors embeddings [10]. Next we use the Oyez annotated audio to generate a dictionary of speakers and their associated d-vectors, the Reference Audio Library (RAL). Finally, we perform cosine distance scoring [11] of the d-vectors from reference audio and target audio to perform diarization. Our embedder draws on the Resemblyzer 4 Voice Encoder. Our RDSV pipeline achieves a Diarization Error Rate (DER) of 13.8% on a held-out test set for speakers covered by the reference audio library. Section 2 reviews various strategies for TISV. Section 3 details the Voice Encoder, and Section 4 outlines the RDSV process which includes the RAL structure and Speaker Verification calculations. In Section 5 we investigate the separability of the judicial speech in court audio with the Voice Encoder and apply our pipeline to the Oyez SCOTUS data. In Section 6 we discuss the performance of our method and motivate future research on the topic of diarizing court proceedings.

Related Work
Text-Independent-Speaker-Verification (TISV) is commonly approached as two distinct tasks: (1) generating informative speaker representations, and (2) diarization strategies which use these representations to infer speaker labels. For a more complete survey of the study of diarization, particularly via deep learning, see Park et al. [12] and Bai et al. [13].
Speaker representations are typically extracted embeddings from one of the end layers of a NN trained to perform speaker verification or identification. These typically come in one of two variations, d-vectors (based on DNNs) [10] and x-vectors [14]. x-vectors extract embeddings from a time-delayed neural network with an intermediate pooling layer, trained to discriminate speakers from variable length segments. Relative to d-vectors, they gain from an intrinsic data augmentation process and the ability to embed variable-sized windows of audio, and achieve state-of-the-art performance on recent benchmarks [14].
Despite this advantage, we utilize d-vectors for our strategy for their relative simplicity of implementation. d-vectors are still one of the most prominent speaker representation extraction frameworks [12], so in this initial work we focused on testing whether we can achieve acceptable performance with this approach. 5 When it is possible to cast diarization as a speaker identification task for a predetermined set of speakers, one of the most widely used metrics is Probabilistic Linear Discriminant Analysis (PLDA). [15]. However, in our case, we have unknown speakers, so we use the cosine distance metric to cluster speaker embeddings for simplicity and transparency.
One could also employ a general unsupervised clustering algorithm to perform the speaker verification. Although there have been recent attempts to use deep learning for this purpose, from our initial exploration we found they can be computationally expensive and hard to manipulate. In this work we looked to explore if adequate diarization performance can be achieved in our use-case with a simple non-parametric representation; more sophisticated models can be a focus of future work.

Speech Embedding Network
Our method utilizes a speech embedding network trained with the Generalized End-to-End Loss [1] to encode speech into d-vectors [10]. This loss function can mimic the process of speaker enrollment and verification during training [16]. We build on previous implementations [17]. We use Resemble.AI's pre-trained Resemblyzer, a variant of the speaker encoder network [18], which we refer to as the Voice Encoder. These networks follow the general architecture and parameters of the Speaker Encoder in [1].
Resemble.AI trained their Voice Encoder on VoxCeleb1&2 [19,20] as well as the LibriSpeech-other [21] dataset, for a total of ∼ 5, 600 speakers in their training data. For comparison, there were ∼ 18, 000 speakers used in [1]. Their model is a three-layer LSTM network with a single linear layer and additional rectified linear activation function (ReLU) layer on top of the linear layer, normalizing projections between 0 and 1, as d-vector components fall between -1 and 1. In our fork 6 of the Resemblyzer we added the capability to retain speaker labels with d-vectors and process audio files that are too large to fit in GPU memory.
Our audio data is sampled at 16KHz and prepared for the encoder using the processing procedure of the Voice Encoder, which follows [22], unless otherwise specified. During Resemble.AI's training of the Voice Encoder, audio files are divided into single speaker utterances. In contrast, when we utilize their model for inference we do not segment the audio file, so our processing unit is the entire audio file. We refer to the entire audio file as the case or proceeding in this work for clarity.
First we perform Voice-Activity-Detection (VAD), which yields variable-length segments of voice activity across a case. During inference, we drop non-speech, concatenate the VAD segments into a single sequence and then split the sequence into non-overlapping windows which we refer to as "partial utterances". We convert the entire VAD sequence into a 40-bin melspectrogram and process these partial utterances, or range of mel-spectra, through the Voice Encoder. The encoder contains a hyperparameter rate to determine the size of the partial utterance window, or frequency at which we batch mel-spectra. It is defined as the number of non-overlapping windows per second.
The amount of audio (in time) represented by a single dvector can vary greatly with the rate. The maximum width for partial utterance window is 1600ms (set in training), so our rate is lower bounded to .625, producing a single d-vector for the full 1600ms window. The rate is also upper bounded at 100, where we are creating one d-vector for every mel-spectrum individually (which we produce in 10ms hops). A larger rate decreases the ratio of d-vectors that would contain speech from two speakers in the label retention process, but increases the computational cost to perform diarization with the d-vectors. We explore the ramifications of the rate parameter further in Section 5.

Reference Dependent Speaker Verification
The Voice Encoder is the only formal model necessary to perform the Reference Dependent Speaker Verification (RDSV) process for a set of audio recordings, but the procedure also requires some annotated data. Specifically, it requires an annotated Reference set (R), Development set (D) and Test set (T). R is used to generate our Reference Audio Library (RAL), D is used to tune the end-to-end diarization process (i.e. the embedding network and RDSV hyperparameters) and T is used for a final evaluation on heldout annotated data to benchmark the pipeline. A visualization of the pipeline including the data partitions can be seen in Figure 1. Note that the R set (orange arrows) must be processed before diarizing the D or T set (purple arrows). The Oyez project [3] offers an API to pull the audio for SCOTUS oral arguments and their accompanying transcriptions. This makes generating the dataset splits for our application simple. Note that the SCOTUS oral arguments are a good testbed for our system since almost every judge is present in almost every case. However, a large portion of the audio is the speech of lawyers who will not be present in our RAL.
It is important to pick informative cases for our R set. A Figure 1: Audio Diarization Pipeline case is a good choice for the R set if it contains adequate amounts of speech from target speakers which the RAL does not already contain. Since our focus is on diarizing the judicial speech in the audio, it is crucial to have adequate speech of the judges in the target audio. This is an easy requirement to meet for the SCOTUS, but will be much more challenging for other court systems as they have much larger populations of judges.

Reference Audio Library
The Reference Audio Library (RAL) is the dictionary of speakers found in the R set and the associated d-vectors for those speakers. The SCOTUS oral argument transcriptions are converted to Rich Transcription Time-Marked Files (RTTM) [23] annotations. Speaking intervals for a given speaker are extracted and a subsequence of d-vectors from the embedded audio file are created if it is above a minimum length parameter min audio len. We then take the average of the d-vectors in that subsequence as our representative d-vector for the speaking interval. This process is done for each speaking interval separately, so a speaker will be represented by multiple d-vectors, each d-vector representing a different speaking interval. We also set our RAL to only retain judges as speakers and drop any speaker that does not meet a minimum number of separate speaking intervals to reference, which is a parameter in our implementation min ref count. This parameter's only impact is to ensure we meet the minimum duration for each of the Supreme Court judges we plan to diarize.

Speaker Label Inference
Our objective in RDSV is to use the RAL embeddings for each judge to infer who is speaking at each time step in an unseen case. We do this using the cosine distance metric [11]. Our implementation creates an affinity matrix between the reference embeddings and the case, storing the dot product between each reference embedding and each time step of the continuous case embedding. Because d-vectors have unit norm, this amounts to the cosine similarity between the reference audio and target audio per judge. The speaker with the reference embedding that scores the highest similarity to the embedded target audio at a particular time step is chosen as the inferred speaker. If this were a closed-set Speaker Identification task, this would be sufficient. But since we assume our RAL will not account for every speaker, the diarization process includes two threshold hyperparameters, sim thresh and score thresh, used to label unrecognized voices. If the highest similarity score between a speaker reference and the target audio segment is under score thresh and the difference between that similarity score and the highest similarity score between the same target audio segment and the reference of any other speaker (judge) is above sim thresh, then we label this an unreferenced speaker.

Supreme Court Audio
We evaluate our pipeline on the SCOTUS oral arguments and transcriptions database, accessed through the Oyez project [3]. We pull all cases (with transcriptions) heard in one session from Supreme Court docket terms 16-18 7 . We allocate 3 unique cases from each docket 16 and 18 (6 total) into the both R and D set (12 total), which are used to analyze the Speech Embedding network and tune our diarization pipeline. We then allocate 25 cases from docket 17 as our test set, which are 58 minutes on average and are about 51 minutes each after VAD.

Speech Embedding Network Analysis
Because both speaker label quality and computational cost are impacted by the rate parameter, we test the quality of the Voice Encoder speaker representations for rate= [1,3,5,7].
To do this, we encode our R and D set for each rate and perform a multiclass one-vs-rest Logistic Regression with scikitlearn [24] to infer d-vector speaker labels. We train the model on only the d-vectors from the judicial speech found in the R set audio. We then evaluate the ensemble classifier's performance on the d-vectors from the full proceedings in our D set. We do this by thresholding the predicted probability from the classifier to predict a non-judge speaker at [.85, .9, .95]. We set our rate=5 for our diarization process as we found that a rate of 5 had the most stable accuracy as the threshold increased and the highest overall accuracy. We also visualize the d-vectors representing judicial speech from the cases in our R set for our lowest and optimal rate. We reduce our d-vectors to two dimensions using sklearn's tdistributed Stochastic Neighbor Embedding (tSNE) with a perplexity of 50 (default parameters otherwise). We then plot the shrunken d-vectors with their speaker labels to see how well our embeddings tend to cluster and if our d-vector labels are accurate. With the help of Figure 2 we can see that even our lowest rate performs reasonably, but there is significantly higher ratio of dispersed d-vectors in comparison to the higher rate. This supports our conclusion to use a higher rate rather than the minimum for our diarization pipeline.

Supreme Court Diarization
After embedding the R and D sets we tune our diarization process hyperparameters.
We To evaluate performance during tuning we use the DiarizationErrorRate (DER) in pyannote.metrics [25] with a collar of half a second, as most of the speaker turns tend to be on the longer side. We track the Average DER (µD) and DER standard deviation (σD) across all cases in the T set. Because our diarization process assigns all unreferenced speakers to a constant label, we also convert the groundtruth RTTM labels such that all speakers not members of the RAL get cast to a single label. Our primary metric for performance is µD, and we use the parameters that minimize the µD of the D set in processing our heldout test set. The optimal values found were score thresh= .85 and sim thresh= .1. Table 1 shows the diarization performance of our pipeline on the 25 cases in the test set, including the average amount of audio per case (AC) and average amount of audio after VAD (ACV) in minutes.  Figure 3 shows the output of our system for the first 10 minutes of a typical diarized test case. It includes our prediction (bottom) and the ground truth (top) with unreferenced speakers in our RAL converted to a single identifier. This short segment highlights the large ratio of lawyer speech to judicial speech. We reiterate that our focus is identifying the segments of judicial speech, so the diarization of lawyer speech is out of scope for this paper. We can see that our method does diarize our pre-referenced judges, and does quite well when the speaking segment is not too short, but occasionally struggles to identify a speaker, especially on short segments. This is particularly the case if a judge sounds similar to a lawyer or if limited references were available for that judge compared to the others (which is the case for Justice John G. Roberts).

Discussion & Summary
Our approach is an attempt to illustrate the usability of an audio processing pipeline that is domain-specific, exploiting simple, open-source, transparent implementations. By leveraging a pre-trained open-source model in Resemble.AI's Voice Encoder and computing cosine similarities for speaker verification, we achieve strong diarization performance on a real-world dataset with relatively uncommon characteristics: an average Diarization Error Rate of 13.8%, and a low variance and maximum diarization error rate of 19.8% 8 .
Our model is parsimonious; both the encoder and speaker verification scoring could evolve in complexity. Both x-vectors as speaker representations and using a neural network to learn the distance metric are the current state-of-the-art, and we look to apply these in future work. We also can consider commercial APIs (Google, IBM, etc.) for speech segmentation, as they seem to perform well. We believe better speech segment boundaries would help our RDSV pipeline correctly identify short speaking segments from speakers who sound similar to a more common speaker in the audio, which is a challenging situation for our pipeline.
We hope we have encouraged further research into the diarization of legal proceedings. Oral argument transcript text may shed light on a broad spectrum of judicial behaviors and biases, including race-based discrimination [26], court prediction [27], and partisan political bias [28]. Professionally, the legal industry relies on enormous corpora of indexed text, primarily of court decisions, that are largely hidden behind paywalls despite being public record. By making diarized transcripts publicly available, we can increase access to public records for those typically locked out of the legal discipline.