A comparison of distance metrics for the multi-objective pathfinding problem

Typically, there are two main ways of representing paths: The first is a variable-length chromosome representation of a solution which is often used with the graph-based problem representation (Jun and Qingbao 2010; Weise and Mostaghim 2021b). This approach represents a solution as a list of nodes varying in length when computing a path. The second approach is a fixed-length chromosome, representing the directions of travel, together with a list of nodes in a graph or a list of grid cells (Besada-Portas et al 2013; Beke et al 2020; Weise et al 2021). Grid-based representations for pathfinding problems are shown to be very practical for evolutionary algorithms (Ahmed and Deb 2013; Weise and Mostaghim 2021a). Such grid representations can be refined depending on the required resolution of the problem. Besides, they are often used for benchmarking purposes (Sturtevant 2012). Also, they can represent real-world problems by discretising the problem representation (Anguelov 2011). Grids typically consist of units with adjustable sizes (Anbuselvi 2013). A solution encoding can consist of a linked-list of units (Xiao and Michalewicz 1999), the directions (Weise et al 2021), or the coordinates of several waypoints (Weise et al 2020). Considering grids, we can introduce several constraints for movements on specific paths by defining an upper limit for movements (such as speed) on each unit. In this way, we can easily incorporate various linear and non-linear constraints on each unit to represent speed, ascent, obstacles, and others.

It is comparatively easy to convert a grid into a graph (also called lattice-graphs) by considering units as nodes and their contact-edges as the graph’s edges. This conversion is performed in several applications, e.g. the game industry. The commonly used \(\hbox {A}^*\) algorithm is an example of pathfinding on a grid which is transferred to a graph (Yap 2002), as its heuristic function can be defined as the Euclidean distance that can measured on a grid between the cell centres.

In general, compared to grid-based representations, graph-based representations allow higher flexibility in representing real-world problems, which can be considered heterogeneous, while grids are usually homogeneous. In this paper, we represent the pathfinding problem as a grid transferred to a graph. By employing the property-graph-data-model, we can assign various properties to each node (Rodriguez and Neubauer 2010)

The multi-objective pathfinding problem can be defined as follows. The goal is to find a set of k Pareto optimal paths \(P^{*}=\{p_1,\ldots ,p_{k}\}\) in a graph G(V, E) from a starting node \(n_S \in V\) to a pre-defined end node \(n_{End} \in V\), i.e., \(p_i=(n_S,\ldots ,n_{End})\), where each path is of a variable length K that is evaluated concerning a set of objective functions \(\vec {f}(p)\) which are to be minimised. Given this definition, we can use a variable-length chromosome representation to apply the proposed next distance metrics. Figure 1 depicts a graph which is superimposed on a grid (lattice-graph) in the left figure and two paths \(p_i\) and \(p_{i+1}\) in the right figure.

In Weise and Mostaghim (2021b), we proposed a benchmark suite, where we have defined five objective functions for a multi-objective pathfinding problem. Note that problems with more than three objectives are considered as many-objective (Köppen and Yoshida 2007).

The benchmark instances themselves are defined on a grid with a size of \((x_{max},y_{max})\); however, in the original study, the authors used a graph-based representation, where each grid-cell was represented by a node n in the set of vertices V in a graph G = (V, E). Neighbourhood relations between cells, set by a benchmark’s instance settings, are reflected in the set of edges E. Each edge defines if the traversal from one cell to one of its neighbours is allowed, as a directed graph is used.

Therefore, following the original study Weise and Mostaghim (2021b), the objective functions are defined for a list of nodes \(n\in N\), \(N\subseteq V\). A list of nodes, of variable length K, \(N_{i}=\left( n_{1},\ldots ,n_{K}\right)\) represents a path \(p_{i}\), that consists of a list of subsequent coordinates, i.e. \(p_{i}=(x_{1},\ldots ,x_{K})\), where \(x_{i}\in {\mathbb {R}}^2\). Therefore, each node’s \(n_{i}\) location is defined by a two-dimensional coordinate.

The paths are evaluated by: the length of a path, travel time, delay, smoothness (or curvature) of a path, and ascent (or elevation) of a path. In the following, the equations to compute each objective are shown:

Objective 1: Euclidean length. In the first objective function, the Euclidean lengths between two neighbours are summed.Objective 2: Expected delays. The second objective can be considered as a measurement of running in an accident or any other unexpected event. It is defined by the differences in \(v_{max}\) of two consecutive cells or nodes.Objective 3: Elevation. The third objective corresponds to the total positive ascent when traversing a path. Only positive values are considered, since this objective can represent fuel consumption to a certain extent.Objective 4: Travelling time. The fourth objective corresponds to the total time needed to traverse a path, and is defined by the distance between two nodes and the average \(v_{max}\).Objective 5: Smoothness. The last objective corresponds to the smoothness of the path. However, since we intend to minimise the objectives, a smaller objective value represents a more straight path. Similar to Oleiwi et al (2014) and Jun and Qingbao (2010), \(a \cdot b = \Vert {a}\Vert \Vert {b}\Vert cos(\theta )\) is inverted:For our evaluation, we take the same definitions for the obstacle-defining functions, \(v_{max}(n)\), and \(delay(n_i,n_{i+1})\) as in the original study (Weise and Mostaghim 2021b):The function \(v_{max}\) uses the node n’s coordinates that are denoted by x and y, \(n_i=(x_i,y_i)\). For more in-depth information and how h(n) is computed, the reader is referred to the original study (Weise and Mostaghim 2021b).

In analogy to the original study, we, furthermore, also compute paths from the cell or node with the coordinates of (1, 1) to cell with the coordinates of \(\left( x_{max},y_{max}\right)\), which are given by the specified benchmark instance problem.

It is noteworthy that all objectives, except the Smoothness, i.e. \(f_{5}\), can be computed for a path of length \(k\ge 2\), while at least three nodes are needed to compute the fifth objective. It is important, as this restricts several other pathfinding algorithms to solve the problem. Usually, edge weights are taken into account, which is only possible for the first four objectives, as the function value can be used as an edge weight in the underlying graph representing the problem.

As Shir noted, genetic algorithms typically suffer from loss of diversity within populations, resulting in a local optimum (Shir 2012). Niching methods address this problem by preserving diversity. In state-of-the-art algorithms, there are various methods for increasing or maintaining diversity. Crowding distance is an example of using the objective space to identify crowded areas. Individuals are measured by the average distance between their two neighbouring solutions (Deb et al 2002). More isolated solutions can be emphasized by using this measurement during the NSGA-II algorithm’s replacement and selection phase. Another technique is to use reference vectors. The solutions along such vectors are generally preferred, and their distribution within the objective space allows diversity to be maintained (Deb and Jain 2014). When optimizing more than three objectives, the latter methodology often serves as a good solution to problems with many objectives. However, study results indicate that performance can be affected not only by the number of objectives but also by the type of problem, requiring careful consideration when choosing an algorithm (Cai et al 2018; Weise and Mostaghim 2021b).

Moreover, if more than one solution can map to the same objective values in specific problems, such as multi-modal problems, other diversity measurements such as combining different metrics in the objective and decision space can be useful (Javadi et al 2020; Deb and Tiwari 2005). For instance, the many-objective pathfinding problem has close solutions in the objective space, though they are far apart in the decision space. The use of diversity-preserving measurements in decision space can, as a result, improve an algorithm’s performance (Shir et al 2009; Weise and Mostaghim 2021c). Shir states that diversity along the Pareto front does not necessarily result in the same diversity in the decision space among the Pareto set. Futhermore, a decision space-diverse set is of interest for a potential decision maker (Shir et al 2009; Ulrich et al 2010). In their work, Ulrich et al (2010) proposed a methodology to integrate the decision space diversity into a hypervolume based search. However, there are numerous difficulties in calculating a measure of diversity in the decision space, which is especially true if a variable-length representation represents the solution. The crowding distance, in addition to other metrics, such as the harmonic mean, can be used when the chromosomes are fixed-length (Javadi and Mostaghim 2021).

The Hausdorff distance, can be used to compute the distance between two sets of points without taking their flow into account. In Eq. 8 its formula is depicted. It is the greatest distance of all distances between points in one set and their nearest points in the other.

The Fréchet distance is a measurement of similarity for curves in a metric space. Eiter and Mannila described it by using a dog walk analogy (Eiter and Mannila 1994). A dog and its owner walk on two different paths, and both can vary their speed but cannot backtrack. Since there is a leash attached to both, the Fréchet distance can be defined as the shortest length of a leash, which is required for both to follow their paths as shown in Fig. 2. The dashed lines indicate the leash.

Fréchet distance (Eiter and Mannila 1994) is mathematically defined as follows:Here, A and B are curves as a continuous mapping in a metric space S, defined as \(A : [0,1] \rightarrow S\) and \(B : [0,1] \rightarrow S\). The reparametrisations \(\alpha\) and \(\beta\) are non-decreasing functions from [0, 1] to [0, 1]. In other words, \(A(\alpha (t))\) and \(B(\beta (t))\) are the positions of the owner and the dog in time-step t and they are non-decreasing as the two entities cannot move backwards. The function d is the distance metric in S, e.g. Euclidean distance, and hence it describes the length of the leash between the dog and the owner. Eventually, the Fréchet distance is obtained by computing the infimum (greatest lowest bound) of all parameterizations \(\alpha\) and \(\beta\) of [0, 1] of the maximum over all t of the distance d in S between \(A(\alpha (t))\) and \(B(\beta (t))\). Alt and Godau studied the computational properties of the measurement (Alt and Godau 1995), initially introduced by Fréchet (1906). They specified an algorithm to compute the distance \(\delta _F\) in time \({\mathcal {O}}(ab\log ^2 ab)\), where a and b are the number of segments of two curves (Eiter and Mannila 1994). Eiter and Mannila proposed a variation of the distance metric, i.e., the coupling distance, or discrete Fréchet distance \(\delta _{dF}\), which provides a good approximation of \(\delta _F\) in time \({\mathcal {O}}(ab)\). They also show that \(\delta _{dF}\) is an upper bound of \(\delta _F\). They approximate the two curves A and B by polygonal curves, which is, intuitively, a list of supporting points. Those points specify the endpoints of line segments. The sequence of segment endpoints of a polygonal curve P is denoted as \(\sigma (A)=(u_1,\ldots ,u_a)\). A coupling L between A and B is defined as a sequence \(L=(u_{c_1},v_{d_1}),(u_{c_2},v_{d_2}),\ldots ,(u_{c_m},v_{d_m})\) of distinct pairs of \(\sigma (A) \times \sigma (B)\), with respect to \(c_1=1,d_1=1,c_m=a,d_m=b\). The coupling respects the order of points. Eventually, the length of the coupling is defined as \(||L||=\max \limits _{i=1,\ldots ,m}d(u_{c_i},v_{d_i})\); hence the longest connection in L and the discrete Fréchet distance as shown in Eq. 10 (Eiter and Mannila 1994).In more recent works, subquadratic algorithms were developed to approximate the discrete Fréchet distance (Bringmann and Mulzer 2016). The authors developed an algorithm that runs in \({\mathcal {O}}(n \log n + \frac{n^2}{\alpha })\), where n is the number of points and \(\alpha \in [1,n]\) is the approximation. The two curves have to have the same number of nodes. Chan and Rahmati (2018) also proposed an approximation algorithm resulting in \({\mathcal {O}}(n \log n + \frac{n^2}{f^2})\), where f denotes the approximation and is \(f\in [1,n]\). In this paper, we use all points of the two curves. We can therefore use the original methodology by Eiter and Mannila (1994). Using the more recent approaches with all points would result in \(\alpha =f=n\), resulting in \({\mathcal {O}}(n \log n)\). However, the polygonal curves in this paper are not constituted of the same number of nodes. We, therefore, use Eiter and Mannila’s approach.

Compared to the Hausdorff distance, the Fréchet distance accounts for the flow of the curves, while the Hausdorff distance measures the distance from one point in one curve to the closest on the second curve. For the remainder of the paper, we refer to the discrete Fréchet distance. As we define a path in this work as \(p_i=(n_s,\ldots ,n_{End})\), we can represent it by analogy to the definition of \(\delta _{dF}\); hence \(p_i=\sigma (A)\) and \((n_s,\ldots ,n_{End})=(u_1,\ldots ,u_a)\), where \(n_s=u_1\), \(n_{s+1}=u_2\), \(n_{End}=u_a\). In other words, A represents a continuously defined curve and \(\sigma (A)\) are the segment endpoints. Since a path in a graph is defined by its nodes, every node \(n_i\in p_i\) is, in fact, a segment endpoint.

Although the Fréchet distance is a metric that results in a dissimilarity measurement of two curves, there is another metric that can find the best match between two signals and determine their distance (Müller 2007). The Dynamic Time Warping (DTW) measures similarities between temporal sequences. However, we can use the approach to determine a distance between two paths, which are sequences of locations. In Eq. 11 the formal definition of the DTW distance is shown. For its computation, a local cost measurement d(a, b) is needed that describes the similarity between two points \(a\in A\) and \(b\in B\), e.g., the Euclidean distance. A cost matrix C(A, B) can be built by computing d(a, b) for each pair of a and b. The goal is to find an optimal warping path \(p^{*}\) of the two curves A of length R and B of length S that the overall cost (Eq. 11a) of a warping path p is minimal (Eq. 11c). An (R, S)-warping path p is a path in the cost matrix that runs along a valley of low cost (Müller 2007). As the matrix’ values represent cost, the warping path is the one obtaining the least combined costs, if it can go through the matrix’ cells (Eq. 11c). In this path, the element \(a_{r_{\ell }}\in A\) is assigned to the element \(b_{s_{\ell }}\in B\). To compute \(\delta _{dtw}\), dynamic programming has been used. Figure 3 shows two curves and their respective distance values using each of the three proposed metrics. In all three metrics, the function \(d(\cdot ,\cdot )\) represents the Euclidean distance between two points.

In the experiments, we examine the proposed approaches on the benchmark test suite ASLETISMAC (Weise and Mostaghim 2021b). We consider a two-dimensional space with three obstacle types (NO, LA, CH), with K3 neighbourhood, enabled backtracking, and grid sizes of \(\{15,20,24,26,28,30\}\). NO indicates no obstacles, while LA and CH introduce bulk and chequerboard obstacles, as shown in Fig. 6. In this way, CH constraints the decision space to a few feasible paths. The K3 neighbourhood restricts the number of possible neighbours to eight, i.e., all surrounding cells. All these combinations result in 84 test instances. Given a solution represented by a path N of length K as \(N=(n_i,n_{i+1},\ldots ,n_K)\), i.e., is a list of nodes, we evaluate it by five objectives to be minimised: (1) Euclidean length, (2) Delays, (3) Elevation, (4) Travelling time and (5) Smoothness (Curvature). The details can be found in Weise and Mostaghim (2021b).

We use the same operators for pathfinding as in Weise and Mostaghim (2021b) i.e., a one-point crossover, which creates new offspring chromosomes by crossing two parent paths at one common point. We also use the proposed perimeter mutation for the mutation operator, which mutates the middle point of two arbitrary points within a specific network distance inside a given maximum radius and reconnects the paths afterwards. Consequently, we compare the algorithms with the three incorporated distance metrics to each other. Although it is a many-objective optimisation problem, we consider a smaller computational budget than our previous studies, as we have observed that the quality of results changes only marginally after 100 generations. With that decision, we want to take time performance considerations into account by sacrificing quality. Furthermore, we use a population size of 100, to further account for fewer function evaluations. In real-world applications, obtaining results in a short amount of time is often a requirement. For the experiments, we calculate the \(\hbox {IGD}^+\) indicator that is a distance measurement between the obtained front of non-dominated solutions and the known true Pareto reference front (Ishibuchi et al 2015). Furthermore, we report the respecting wins, losses and ties of each algorithm of all problem instances.

To assess the quality of solutions in the decision space, we also employ the IGDX indicator (Aimin Zhou et al 2009), which measures the distance between the known Pareto-set and the found solutions. Again, we compare the results of the algorithms to each other and test for statistical significance using Bonferroni correction, as we perform multiple comparisons. Our null hypothesis states, that the populations have equal medians.

Naturally, it is not trivial to compare an exact algorithm to a meta-heuristic. However, since the running time of the multi-objective Dijkstra is directly related to the number of nodes and edges, we have decided to combine running times with the quality of results of the algorithms to compare them. Therefore, we make use of the indicator values. Our comparison metric is \(\lambda _{I}=median(t_{I})\cdot (1+median({{\rm I}}))\), i.e., the median run time \(t_{I}\) of an algorithm on a problem times the median indicator value I added to 1. With such a metric, we take the suboptimality of meta-heuristics into account. However, the indicator value I for the optimal algorithm is naturally 0, where I is the \(\hbox {IGD}^+\) or IGDX indicator.

Figure 7 illustrates the median values and standard error of the IGDX and \(\hbox {IGD}^+\) indicators respectively, concerning the instance sizes and obstacle settings. Each row in the figure shows a different obstacle profile, i.e. NO, CH, or LA.

We also report the number of Pareto-optimal solutions for each problem instance on the right axis, which we obtained using the exact approach. From a graphical perspective, it is visible that the results vary depending on the type and size of the problem instance. It is noteworthy that in the instance of LA P1 BT K3 (bottom left) of size 28, the algorithms using Fréchet and DTW distance obtain a small IGDX value, compared to a relatively high \(\hbox {IGD}^+\) value. This indicates that solutions near the optimal solutions in the decision space have been found, that are, however, of low quality in the objective space. For the multi-objective pathfinding problem, we have shown that solutions close to the optimum in decision space are not necessarily close to the optimum in terms of the respective objective values. However, the same two algorithms obtain a worse IGDX value on instance size 30 for the same map type, while the algorithm incorporating the Hausdorff distance can still obtain a low value. Nevertheless, in the other two obstacle settings, using the Hausdorff distance is not as stable as the other two distance metrics regarding IGDX values, as backtracking is allowed, and therefore, the metrics taking the flow of a curve into account give better results. If a path gets closer to its origin, whereas another path does not, the Hausdorff distance is not always able to compute their similarity. As a result, the outcome can be small although the Fréchet and DTW distance give higher values, as the paths are more distinct. Concerning the \(\hbox {IGD}^+\) indicator, all three algorithms obtained similar values. The indicators’ results show that using the proposed niching methodology can improve the quality of solutions in terms of closeness to the true Pareto-set, while there is still room for improvement regarding the objective values. However, as we have limited the search to 10,000 function evaluations, which is comparatively low for many-objective optimisation problems, the results in terms of \(\hbox {IGD}^+\) were expected. In this study, the search process took particularly measurements in the decision space to minimise the objective functions. We, therefore, do not see much improvement in the objective space that is measured using \(\hbox {IGD}^+\). The underlying problem is deceptive, which can result in paths that are close to an optimal solution in the decision space (measured using IGDX) but far from the optimum in the objective space. For a real-world application, the impact would be, that a slight perturbation when executing or traversing a path can result in a severe deterioration in terms of objective functions. Future research can work on more advanced methodologies, that focus on local optimisation, as there is only a small portion of the path that needs to be changed to result in better objective values.

Table 1 shows the wins, losses, and ties of each algorithm on all the 84 test problems. Again, the differences concerning the two performance indicators can be seen, as the majority of outcomes regarding \(\hbox {IGD}^+\) are ties, while several instances have a definite winner, comparing the IGDX values.

In Fig. 8 we compare two variants of the algorithm using \(\delta _{dF}\), i.e. (1) taking the median value of all distances to other paths, denoted by FD-MED, and (2) taking the minimum value of the distances, denoted by FD-MIN. The two variants are again compared concerning IGDX (Fig. 8a) and \(\hbox {IGD}^+\) (Fig. 8b). Interestingly, while in terms of \(\hbox {IGD}^+\) FD-MED wins or is of the same quality as FD-MIN, the latter wins in several instances when comparing regarding IGDX. The reason is that the min() approach can work better for local optimisation since the closest paths are used as a reference.

A more detailed view can be seen in Fig. 9, where the respective indicator values over different sizes for a specific instance type are depicted. Clearly, FD-MIN obtains better or similar values when comparing the IGDX values, while it gets outperformed by FD-MED with respect to \(\hbox {IGD}^+\).

When analysing the results, it becomes clear that the high number of ties indicates room for improvement. The high number of ties are a result of the path similarity sorting. Sorting, given two subsets of distinct paths with relatively short distance values inside the subset, will result in a short distance value for each path, although the two sets can be apart from each other.

We also compared the performance of the algorithms to an exact approach as we want to evaluate the quality and running time, when we only allow a small computational budget of 10,000 evaluations. Figure 10 shows the values of the proposed \(\lambda\)-performance for the two employed quality indicators. The y-axis is on a logarithmic scale. In the left graph, \(\lambda _{IGDX}\) shows that the proposed approach has a better value from instance sizes of 26 onwards, while the values are lower from size 28 for \(\lambda _{IGD^{+}}\), compared to the exact approach. Nevertheless, a trend is visible that shows lower \(\lambda\) values for larger map sizes. That is to be expected as the running time for the exact approach grows quadratically. Interestingly, the DTW approach achieved the best performance in most runs. Although it is computationally expensive, it can diversify the solution set better since it is more sensitive to path differences. Nevertheless, the \(\lambda\) indicator is an approximation that cannot be used to make decisions about significant differences between algorithms.