Optimal network construction is a research topic with applications in several areas of science and technology: notable examples are the design of efficient phone networks among cities, the development of urban sewer layouts, or trace routing in Printed Circuit Board (PCB) design. In all these instances, "optimality" is defined as the minimization of a specific cost function, which depends on the type of network considered and on the constraints imposed by the problem.
The networks we consider are modeled by weighted graphs. A weighted graph G = (V, E, w) is a collection of nodes V logically interconnected by edges E that have costs (or "weights") w. If the network has a physical structure then the edges might be the links connecting the physical nodes (e.g., pipes and/or wires) and the weight of the edge might be proportional to the price per unit length/surface/volume of the material used. Conversely, if the nodes of the network are connected by intangible links (e.g. radio links) then the cost can be defined according to the specific technology used for transmission.
Many problems concerning weighted graphs have been presented. One of the most famous examples is the minimum spanning tree [8] (MST), where given a graph (referred to in the following as parent graph), find the shortest tree that interconnects all its nodes. If only a subset T ⇢ V of the nodes (referred to as terminals) of the parent graph requires interconnection, the problem is called the Steiner tree problem for graphs (STPG) [10] Although conceptually similar, Research sponsored by the Army Research Laboratory and accomplished under Cooperative Agreement Number W911NF-23-2-0014. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. This work was supported by the National Science Foundation under [IIS-1553063, 1932572, 2130793] 1 University of Houston, Houston, TX USA {fbernardini, atbecker}@uh.edu . Consider a set of terminals (green dots) and the vertices of a set of obstacles (pink polygons). A weighted graph is constructed by drawing edges (orange lines) between all pairs of nodes in line of sight, with their Euclidean lengths as weights. From such a graph the Steiner tree is extracted (solid blue lines) and the number of corners used provides an estimate of the number of nodes (blue dots) needed.
the two problems have different computational overhead: MST can be solved in polynomial time, while the STPG is Non-deterministic Polynomial-time (NP)-hard. Variants of this problem can be defined by a) embedding the terminals in a 2-or 3-dimensional vector space, b) leaving the number and position of additional non-terminal nodes to be determined and c) weighting each edge with some metric. If the metric chosen is the Euclidean distance then the problem is called Euclidean Steiner tree problem (ESTP), while if the metric is the L 1 norm (or "taxicab distance") then the problem is denoted as the rectilinear Steiner tree problem (RSTP). These problems, in the following referred to as xSTP, are generalizations of the STPG therefore share with it the same complexity class (NP-hard).
In their simplest formulation, ESTP and RSTP place non-terminal nodes everywhere in the environment space. If some regions of the space (polygons in 2D, polyhedrons in 3D) are forbidden then the problem takes the name of obstacle-avoiding Euclidean/Rectilinear Steiner tree (OAxSTP). Methods valid for xSTP in general will not solve for OAxSTP and then the problem becomes increasingly difficult with the number of obstacles and/or terminals.
We focus on OA Euclidean STP (OAESTP) where the density of obstacles is much larger than the density of terminals. The main assumption is that in this regime the solution of the OAESTP is well approximated by the solution of a specific STPG, where the parent graph is obtained by connecting all terminals and all vertices of the obstacles which are in line of sight (LoS). Some strategies based on adhoc heuristics are further introduced to improve the quality of the solution.
A possible application of this scenario may correspond to the construction of a communication network in a dense urban environment where buildings prevent line of sight (LoS) communication between terminals, forcing the network to adapt its shape around building walls. The nodes are assumed capable of performing highly directional transmissions, as studied by Egarguin et al. in [3], [4], [5], thus the communication links are graphically described by straight lines.
The construction of the network has two constraints: (a) the length of the network and (b) the number of nodes it involves. The length of the network provides information on the average distance between nodes of the network which corresponds to the cost of communication (see Friis formula [6]). The larger the distance, the higher the power required to transmit a signal within a given signal-to-noise ratio at the receiver (at a fixed frequency/wavelength). Conversely, the number of nodes corresponds to the number of agents required to constitute the network (the cost of the fleet). These two costs are concurrent, since increasing the number of agents and placing them in specific locations in general lowers communication costs. Conversely, decreasing the number of agents increases the average inter-drone distance, and with it the communication cost. The problem is then defined as a multi-objective optimization scheme (a bicriteria optimization). We contribute a solution of a heuristic optimization method that applies Yen's algorithm [21] to the STPG.
Section II reviews some of the existing results in network design with and without obstacles. Section III introduces the model and the methods used. Section IV compares the performance of the procedure presented with existing methods. Section V defines the bicriteria optimization problem and the method used to solve it. Section VI describes the applications of the method to two different urban scenarios. Finally, Sec. VII summarizes the results and outlines possible paths forward for this research.
II. RELATED PUBLICATIONS The origins of Steiner trees date back to the 17 th century [10] with the first studies on the Fermat-Torricelli point in a triangle, which can be considered an instance of the ESTP with three terminals. In the first half of the 20 th century this problem was generalized to a higher number of terminals, and eventually named after Jakob Steiner, a Swiss mathematician contemporary of Fermat and Torricelli. Since then a vast amount of literature on the topic has been produced and generalizations to higher-dimensional spaces or manifolds have been presented. A recent review of the state-of-the-art for exact and approximate solving methods can be found in Ljubic [12].
Significantly less literature is available on Steiner trees in the presence of obstacles. Heuristic algorithms, such as that of Armillotta & Mummolo [1], were already known in 1988 while in 1999 Rao [17] described some approximating techniques for Steiner trees introducing the "banyan" structure, a structure which is assumed to be no longer than (1 + ✏) of the exact Steiner tree length. In 1999 Zachariasen and Winter [22] described the first exact algorithm for the solution of the Euclidean Steiner tree in the presence of obstacles. In 2007 Asadi [2] considered an OAESTP where the terminals are contained inside a polygon. In 2010 Muller [13] proposed an improvement in the computation speed of Rao's method [17] by suitably selecting a subset of the obstacles' vertices. In 2021 Parque [15] described a hybrid approach combining hierarchical optimization with gradientfree stochastic optimization. Also in 2021, Rosenberg [19] proposed a genetic algorithm whose evolutionary operators are capable of adapting to the structure of the specific ESTP considered, but considers both solid (impenetrable) and soft (penetrable at an additional cost) obstacles.
Aside from its theoretical interest, the obstacle avoiding rectilinear Steiner tree problem (OARSTP) has several important practical applications. Hsie [9] defined and solved an OARSTP to improve the layout of an urban sewer network with respect to standard design techniques while Tang [20] provided a comprehensive review of the most recent advances in the routing problem in Very Large Scale Integration (VLSI) design. Garrote [7] determined disasteraware networks, by assigning a "cost" to different regions of the earth according to their natural disaster likelihood. Such regions, considered as soft obstacles, are then connected by solving an OAESTP which determines the network of minimum risk. Finally, multi-objective communication networks were studied by Levin [11] by means of a composite macroheuristic that starts with a spanning tree, clusters the nodes of the network, determines a Steiner tree over the clusters, and eventually optimizes that choice.
A search of the relevant literature showed examples of OAxSTP where the number of terminals N t was comparable or extremely larger than the number of obstacles N O , while the case N O N t was never explored. This work proposes to fill this gap by systematically exploring the case where the number of obstacles is arbitrarily high.
The method we use to build Steiner trees is a simplified version of the concepts expressed in [17] and [13] that makes use only of obstacle vertices. The ✏ of the (1 + ✏) approximation is argued to be the ratio between a characteristic "small distance" d and the length L of the Steiner tree, possibly proportional to the number of Steiner points (which itself is bounded by N t ).
We are inspired by urban scenarios, where two characteristic distances can be naturally defined: (a) the average street width d str and (b) the average building side d bdg . The urban map, minus the buildings, is then considered as an intrinsic irregular grid obtained as the union of many "tiles" corresponding to approximately rectangular crossroads and alleys of areas:
Assuming A c.r. ⇠ A al ⌘ A, then ✏ can be defined as
If A can be assumed constant across a city, ✏ will decrease if the number of terminals is kept constant but they are spread over a larger portion of the urban map.
The main difference between ESTP and STPG is that ESTP is defined in a continuous space; even in its simplest formulation without obstacles, the solution is found by displacing one or more additional nodes in the ambient space until a configuration of the network with minimum length is found. On the contrary, the structure of a STPG is fundamentally discrete and constrained to the terminals, nodes, and edges that are given as input. Despite this large difference, ultimately both the solutions of an ESTP and of a STPG are a discrete tree. In other words, for the ESTP the cardinality of the ambient space is not reflected in the cardinality of the solutions.
The continuous character of the ESTP allows it to update the list of its nodes and edges during the optimization process. For this reason it will have better or equal solutions than a STPG initialized with the same terminals and a parent graph over which to calculate the Steiner tree. The condition for the equality is that all nodes and edges contained in the solution of the ESTP are a subset of the parent graph of the STPG. This solution is not known a priori, thus an uneducated guess of the parent graph of the STPG will, in general, miss some crucial nodes or edges.
The solutions of a STPG and of an OAESTP can be compared by means of suitably defined "distances". Although not distances in the mathematical sense, these functions give quantitative information about how much two solutions differ and can point to where improvement is needed. The main requirement is that identical solutions have a distance of zero.
A first estimator can be the fraction of edges in common: let S and S 0 be two solutions
If the two solutions share the terminals then let A 2 be the area enclosed between them and A G the area of the convex hull of the graph. A second distance is defined as
Finally, if the terminals are displaced between two solutions but their number does not change then a third distance is defined as the area A 3 between the two solutions divided by the area A GG 0 of the convex hull of the two graphs G, G 0 that generate the solutions:
The main difference between A 2 and A 3 is that A 2 is defined using only edges already present in the solutions. Conversely, the closed polygons of A 3 are obtained introducing fictitious The two solutions S (dashed) and S 0 (solid) share terminals and two edges, but depart from each other in proximity of the n d3 point. D 3 : S and S 0 have the same number of terminals but they are displaced. In light blue the area contained between the two solutions, and a dotted line demarcates the convex hull of the points involved.
edges which connect pairs of corresponding terminals. Figure 2 shows a graphical example of the distances.
Distance (D.1) only counts edges which are perfectly overlapping. Therefore even if S 1 ! S 2 continuously, then D 1 will reach 0 in finite steps with a discontinuous profile. Conversely, distances (D.2) and (D.3) consider areas so tend to 0 continuously if S 1 ! S 2 in the same manner.
Distance (D.1) will find application in Sec. IV where the solutions obtained with different methods will be compared. Distances (D.1) and (D.2) will be used to justify the assumptions of Sec. III-C. Finally, (D.3) is necessary to consider the more general case where terminals are allowed to move, but otherwise is outside of the scope that we are presenting.
The non-terminal nodes of the solution of an OAESTP and of a STPG are of two types: a) nodes of degree 2 (in the following n d2 ) obtained by bending around an obstacle and b) Steiner points, i.e. nodes of degree 3 (n d3 ). Nodes of degree higher than 3 are ruled out in the OAESTP by the requirement that the edges connecting to a Steiner point describe angles of exactly 120 . For the STPG this is not true in general and nodes of higher degree cannot be ruled out a priori. For this reason, a statistical analysis has been performed considering the case of N t = [4,7] terminals and randomly initializing their positions for 1000 trials with the configuration of obstacles of Fig. 1. Only one solution containing a n d4 was present for N t = 4, 5, 2 for N t = 6 and 7 for N t = 7; no nodes of degree larger than 4 ever occurred. A n d4 is never optimal in an ESTP thus its presence implies a lack of additional vertices to form shorter networks with nodes of lower degree and extremely fortuitous placements of terminals. Following this reasoning it can be argued that increasing the density of obstacles (and therefore, the lattice of (2)) while keeping the terminal density low would decrease the likelihood of n d4 or higher, leaving solutions of STPG containing only nodes of degree up to three.
The method we present assumes a regime in which the density of obstacles ⇢ O is large compared to the density of terminals ⇢ t :
where A is the area of the region considered.
From the considerations of Sec. III-B, this choice decreases the likelihood of n d4 in the solutions of the STPG,
0 0.2 0.4 0.6 0.8 1 W-E [m] 0 0.2 0.4 0.6 0.8 1 N-S [m] Length: 2.34m -Nodes: 11 a), 0 th [Instance 7] 0 0.2 0.4 0.6 0.8 1 W-E [m] 0 0.2 0.4 0.6 0.8 1 N-S [m] Length: 2.47m -Nodes: 7 b), 0 th [Instance 10] 0 0.2 0.4 0.6 0.8 1 W-E [m] 0 0.2 0.4 0.6 0.8 1 N-S [m] Length: 2.87m -Nodes: 2 c), 0 th [Instance 20]
Fig. 3. Solutions of the instances considered in [19] at 0 th order of optimization: Instance #7 (a), #10 (b), #20 (c). Green dots are terminals and blue dots are nodes. The quality of the solutions is worse than those of [19] by 1-3%, compatible with the estimate of (5).
rendering the type of nodes that can be encountered homogeneous with those of the OAESTP. Furthermore if terminals are outnumbered by obstacles then their likelihood of having mutual LoS will decrease. Thus, the number of edges bending around obstacles (namely, n d2 ) increases. While the number N s of Steiner points in an OAESTP is bounded by the number of terminals (N s N t 2), the number of n d2 depends on the number of obstacles touched by the solution, thus increasing N O while keeping N t fixed decreases the ratio N nd3 /N nd2 . Finally, a continuous curve may be approximated by a discrete grid up to the grid's step. A higher density of obstacles' vertices constitutes an effective (although irregular) grid which can be considered to approximate the nodes of the Steiner tree up to the average distance between nearest neighbors. In regime (3) the above considerations support assuming the solutions of OAESTP and STPG are close in the sense of (D.1) or (D.2). In particular it is reasonable to expect that the n d2 will be captured correctly and that the main differences will be due to a misplacement of the exact Steiner points. This misplacement becomes less and less relevant as the ratio N nd3 /N nd2 decreases. Let R j > 0 be the increase in the length L of the network due to the j th misplaced n d3 , then assuming regime (3) is equivalent to assuming:
where hEi is the average length of an edge.
An estimate of the error can be obtained by considering three nodes placed on the vertices of an equilateral triangle of side 1. It is a well known fact that connecting the nodes directly takes a network of length 2, while connecting each node to the circumcenter of the triangle takes a network of length p 3, that is, a relative error L/L ' 13%. For each Steiner point approximated to a vertex, the solution obtained by the STPG is expected to increase the network cost by R j ' 0.13hEi .
(
This also implies that for N t terminals this error cannot be larger than 0.13(N t 2)hEi.
With the same notation of Sec. III, let O v be the set of all obstacles' vertices and T the set of all terminals. Then G = (V, E, w) is obtained by defining 1) V as the set of all obstacles' vertices and terminals:
2) E as the set of all edges connecting pairs of elements V without intersecting any obstacle. 3) w as the Euclidean lengths of each edge in E. Path minimization problems involving obstacles usually consider only edges tangent or bitangent to obstacles. Edges that would pierce the obstacle if they were continued after their endpoints, never belong to any shortest path between two points unless the endpoints themselves belong to some obstacle's contour. However, for trees this is not necessarily true and there may be instances where a piercing edge improves the solution of the STPG (see Fig. 3b). For this reason the method used in the following sections to solve the STPG will build E considering all edges that connect vertices in LoS and will be referred to as LoS-Vertices (LoSV).
Once a parent graph is defined, any solver capable of handling STPG may be used to find the solution. We integrated SCIP-Jack [18] in a custom MATLAB routine to solve the various instances of the problem. As assumed in Sec. III, the method is assumed to give its best results in the regime of (3). To enable a direct comparison we use the same instances with solid obstacles tested in [19] using the genetic algorithm method developed therein (called StOBGA). In particular we compare the instances numbered as #7, #10 and #20. In these instances the density of terminals is comparable to, or much larger than the density of obstacles, therefore they do not represent regime (3) and are not a setup where method LoSV is expected to outperform method StOBGA. However, the comparison still teaches valuable lessons for future developments, and can represent a lower bound for LoSV's performances.
TABLE I RESULTS COMPARISON WITH STOBGA METHOD [Instance #, # Terminals, # Obstacles] Problem [7,8,4] [10,10,12] [20,20,2] StOBGA 2.31 m 2.4211 m 2.80 m LoSV (0 th ) 2.34 m 2.4704 m (0 th ) 2.4240 m (1 st ) 2.4212 m (2 nd ) 2.87 m % 1.3 % 2.0 % (0 th ) 0.1 % (1 st ) < 0.005 % (2 nd ) 2.5 % D 1 (S Lo , S St ) 1 13/21 1 7/17 (0 th ) 1 14/17 (1 st ) 0 (2 nd ) 1 10/28
Figure 3 shows the results obtained by LoSV, while Table I compares them to those of StOBGA. As expected, the solutions obtained by LoSV have worse results than StOBGA within 3 %. However, LoSV's solutions to the instances with less terminals and more obstacles, #7 and #10, appear to reproduce more accurately the structure of StOBGA's solutions, i.e. they are closer in terms of distance (D.1) than the solutions of #20, which has 20 terminals and only 2 obstacles. Furthermore, all vertices present in StOBGA's solutions are also used by LoSV's solutions, suggesting the ability of LoSV to predict at least a superset of the n d3 of the exact solution.
The solution found with method LoSV can be considered as a 0 th order approximation of the OAESTP. Several heuristic rules can be applied to the 0 th order solution to improve the result. The optimization rules depend on the complexity of the structures that are formed during the optimization of the STPG, which is loosely proportional to the number of vertices of the polygon interested by the optimization (triangle, quadrangles and so on). A first-order approximation is obtained by the following actions:
1) 3-vertices: A three-point structure where one point is connected to the other two may admit a Steiner point of degree 3 if the angle between the two vertices is less than 120 . Alternatively, a non-terminal n d3 can be considered a 3-terminals proto-Steiner structure and its position can be varied if this improves the cost of the structure and the new location does not fall within an obstacle. 2) 4-vertices: Four point structures without additional Steiner points may be transformed into full Steiner topologies if this improves the length of the network. Alternatively, two n d3 directly connected form a 4terminals proto-Steiner structure and their position can be varied. 3) 5-or more vertices: Similar considerations can be put in practice for structures with higher number of vertices, or equivalently, for direct interconnections of more than two n d3 .
An application of these concepts can be seen in Fig. 4:
• The 0 th order solution, Fig. 4a, determines two proto-Steiner structures, with one and with three n d3 . • A first round of optimization, Fig. 4b, determines the optimal positions of the nodes of both structures assuming no obstacles and if the result does not lie within obstacles then adds them to the graph. The structure might not be optimal yet, and the addition of new nodes and edges can verify this situation. This is the case of the structures with one n d3 , while the other with three n d3 cannot be optimized further. • A second round of optimization, Fig. 4c, seeks for improvement on the new structure with one n d3 .
These optimization steps are performed using a standard gradient descent procedure. The total gain for this specific instance has been of ⇠2 %, mostly due to the optimization of the structure with three n d3 . The likelihood of encountering structures with higher number of vertices is expected to be low in the regime of (3). The 0.0487 m improvement is in line with that predicted by ( 5) assuming an average edge of hEi ' 0.1 and N s = 4 Steiner points:
0 0.2 0.4 0.6 0.8 1 W-E [m] 0 0.2 0.4 0.6 0.8 1 N-S [m] Length: 2.4704m -Nodes: 7 a), 0 th [Instance 10] 0 0.2 0.4 0.6 0.8 1 W-E [m] 0 0.2 0.4 0.6 0.8 1 N-S [m] Length: 2.4240m -Nodes: 8 b), 1 st [Instance 10] 0 0.2 0.4 0.6 0.8 1 W-E [m] 0 0.2 0.4 0.6 0.8 1 N-S [m] Length: 2.4212m -Nodes: 8 c), 2 nd [Instance 10]
Fig. 4. Application of the heuristics of Sec. IV-A to instance #10 of [19]. The 0 th order solution, (a), shows a suboptimal 5-vertices and a 3-vertices structure. In the 1 st order solution, (b), these structures are optimized using a gradient descent method. The 3-vertices structure requires addition of a node; therefore it may need further optimization. The 5-vertices structure is already optimal. In the 2 nd order solution the 3-vertices structure becomes optimal. The number of nodes required may vary between optimization steps.
The number of nodes needs not be constant during optimization; note that the 2 nd order solution uses 8 nodes while the 0 th order one uses only 7.
An important feature of the method is that once the map of the obstacles is known then a preliminary parent graph G 0 can be built. In the regime (3) G 0 makes up the most part of the parent graph G, lacking only terminals and the comparatively small set of edges which connect them to the vertices within LoS. If the terminals move then it is sufficient to remove those edges and recompute them with the new positions while leaving G 0 fixed. Furthermore, these rules only depend on the n d3 and its nearest neighbors. Thus they can be computed and applied independently by the node itself in a context of distributed computation.
The key takeaway from the results of Sec. IV-A and IV is that solutions of different length L have, in general, a different number of nodes N n . This implies the possibility of manipulating the number of nodes of a network by altering its length and viceversa.
Previously the term "solution" described a tree of minimum length. From now on, the term "solution" will describe a pair ( L, Ñn ), where L is the minimum length attainable within a given graph using exactly Ñn non-terminal nodes:
A generic non-optimal network (L, Ñn ) will have L L for a given Ñn .
Our main objective is to obtain control over the number of nodes used to build a network. Practical applications often require this type of control. For example: let obstacles and terminals be static and let N n (t) be the number the number of nodes available at any time t. The question is: can connectivity be ensured if N n (t) < N n (0)?
Conversely, let terminals or obstacles be dynamic, but let N n (t) = N n (0) be constant. The solution of the STPG in general will not have the same structure over time. In particular, the number of nodes required can change. In this case the question is if there exists at least one network (L, N n (0)) among which to pick that has minimum L.
The answer to both questions lies in the solution of the bicriteria optimization problem defined in Sec. I, which provides all possible best solutions ( L, Ñn ) at a given time, also referred to as the Pareto front. A solution belongs to the Pareto front if no solution with better L and Ñn exists, and if that is the case then the solution is said to be non-Paretodominated. If the Pareto front contains a solution with Ñn equal to the desired one, then the problem is solvable.
Let L be the solution of the STPG for a given parent graph G. By definition no other network can be shorter than L although the number of nodes Nn it involves needs not be the minimum possible. So let ( L, Nn ) be the corresponding pair in the bicriteria optimization problem.
From a Pareto domination perspective, only consider solutions with N n < N n, L as otherwise any network (L,
and would be Pareto-dominated by ( L, Nn ). Therefore, the Pareto front of the problem is determined by the set of all networks ( LNn , N n ) such that N n < Nn . In other words, the Pareto front is a subset of the set of all suboptimal networks, regardless of the number of nodes used. For what concerns the minimum value of N n for a STPG without obstacles, it would be 0 as all terminals are in line of sight, whereas in presence of obstacles it will depends on their placement relative to the terminals. If the network only has two terminals, therefore a path, then there exists a systematic method to determine all the suboptimal paths that connect the terminals within the parent graph G up to the k s th order (k s is a positive integer and k s = 1 corresponds to the optimal path). This method is called Yen's algorithm.
Although a version of Yen's algorithm is not known to exist for trees, it is possible to craft a heuristic version that suits our needs. Since it is a combination of LoSV and Yen's algorithm the method will be referred to as method LoSV-Yen. The first step of LoSV-Yen is to divide the original network ( L, Nn ) in branches. A branch is defined as a path on a graph whose endpoints are either terminals or n d3 . The second step is to define the list of operations that can be performed on the original network ( L, Nn ) or on the individual branches:
1) Apply Yen's algorithm to one of the branches up to the k th order. 2) Displace one of the n d3 from its current vertex to another vertex. 3) Modify the topology of the network by removing or adding n d3 and/or edges. Each application of 1) will generate k different branches while each application of 2) will produce just one different network. Therefore applying 1) to a network with p branches together with q displacements of n d3 will give rise to qk p new networks.
The effect of 3) is harder to predict. However, if the solutions are required to be close in the sense of the distance Branches connected to T1 and T2 are not varied as they have less than two nodes, so Yen's algorithm has been applied to the branch connecting to T1 using k = 30.
defined in (D.2) then this operation can be ruled out as well as large branch alterations/node displacements. The closeness requirement may arise if a third optimization criterion is introduced such as the cost of displacing a node. Under this assumption the operations on the network we analyzed will be limited to just 1) and 2). Among the new networks created by applying LoSV-Yen, all those with N n Nn will be discarded. Among the remaining, those with minimum length will constitute the approximate Pareto front.
For a finite k and a finite number of displacements only a fraction of all possible configurations will be explored, thus the Pareto front obtained in this manner can only be partial. However, increasing k and displacing the n d3 far from their initial points generates networks which are larger and will likely have a larger number of nodes, therefore they would not contribute to the Pareto front anyway.
A small configuration with N t = 3 terminals and N O = 6 obstacles is considered in Fig. 5. The solution determined by the solver for the STPG (a) can be decomposed in three branches with 5 nodes of which one is a n d3 . Branches with 0 or 1 nodes cannot improve the number of nodes without displacing one of the endpoints and thus are not varied.
In this section method LoSV is applied to instances with a larger number of obstacles. A large database of data to test the algorithm is provided by geomapping companies. The data used in the present work was retrieved from the website OpenStreetMap [14] and manipulated with the geomapping software QGIS® [16] to prepare it for use within MATLAB®. The plots shown in Fig. 6 represent a portion of downtown Houston, Texas along with the networks generated by method LoSV-Yen for the case of N t = 5 terminals.
The simulations showed that a plain application of Yen's algorithm to larger graphs (⇠400 obstacles, ⇠2000 nodes and ⇠28000 edges) is slow in providing results that differ significantly from the initial ones. The reason is that with more nodes there are more paths with comparable lengths that can be built in a neighborhood of the original path. Paths with less nodes, but a significantly larger length, may be never visited by the algorithm if the k (i,j) s chosen for the i th branch and for the j th node displacement is not high enough. This obviously increases the computation time.
However, most of the variations found by Yen's algorithm have a larger number of nodes and are discarded, and the procedure did not yield any meaningful new configuration (N n < Nn ) even for
To overcome the problem and obtain meaningful answers in a shorter time, a slight customization of Yen's algorithm has been applied. At each iteration of Yen's algorithm the first edge of the path is completely removed from the graph. This results in subsequent paths being pushed to perform more significant changes to their initial direction. This modification yielded 10 2 results with N n < Nn within a number of iterations
⇠ 10 7 and the outcome is shown in Fig. 6. The networks have the same structure as only operations 1) and 2) from Sec. V-A were applied.
The first part of our work focused on the OAESTP in presence of an arbitrarily large density of obstacles and a correspondingly lower density of terminals. Method LoSV was proposed which approximates the solution through a STPG using only obstacles' vertices. The error obtained by this solution is estimated to depend on the number of n d3 of the exact solution and therefore bounded by the number of terminals N t . Such error can be tolerated if comparable with or lower than other intrinsic errors of the chosen application or can be mitigated by applying heuristic rules to specific subsets of the solution of the STPG. Such heuristic rules depend on local properties of the graph and are suitable for a context of distributed computation.
The second part of our work deals with the bicriteria optimization problem of a network where length and number of nodes are concurrent costs. An approximate Pareto front of solutions ( L, Ñn ) is determined by applying method LoSV-Yen, a customized version of Yen's algorithm specialized to trees, to the shortest solution ( L, Nn ). We represent the first attempt to apply Yen's algorithm to Steiner trees and hopefully this will stimulate more formal approaches to the problem in the community.
Future paths forward of this research include allowing terminals to move and nodes to be placed over obstacles at an additional cost (soft obstacles). As the largest part of the computation is represented by the construction of the preliminary parent graph G 0 , further effort will be directed to the construction of efficient algorithms to test LoS between pairs of vertices. As geomapping companies provide a virtually unlimited pool of data, it is of interest to test the method with different urban morphologies and to create a common database of instances to compare the results with other methods. Finally, as mentioned in Sec. V-A, the problem can be expanded to a three-criteria optimization by introducing the cost of moving nodes among configurations determined by LoSV-Yen.
0 100 200 300 400 500 W-E [m] 0 100 200 300 400 N-S [m] Length: 830.87m -Nodes: 16 T1 T2 T3 T4 T5 0 100 200 300 400 500 W-E [m] 0 100 200 300 400 N-S [m] Length: 833.75m -Nodes: 13 T1 T2 T3 T4 T5 0 100 200 300 400 500 W-E [m] 0 100 200 300 400 N-S [m] Length: 843.72m -Nodes: 11 T1 T2 T3 T4 T5 0 100 200 300 400 500 W-E [m] 0 100 200 300 400 N-S [m] Length: 863.39m -Nodes: 8 T1 T2 T3 T4 T5 0 100 200 300 400 500 W-E [m] 0 100 200 300 400 N-S [m] Length: 925.26m -Nodes: 5 T1 T2 T3 T4 T5 5 6 7 8 9 10 11 12 13 14 15 16 N n [adim] 830 840 850 860 870 880 890 900 910 920 930 Length [m] Pareto front: N n VS Length S o l u t i o n s s p a c e Optimal pairs (LN ; N ) Pareto front
Fig. 6. Application of method LoSV-Yen to a setup with a large number of obstacles. The solution of the STPG yields a network with optimal length but with a number of nodes that needs not be the minimum. By means of branch alteration and n d3 displacement it is possible to lower the number of nodes, at the expense of the length of the network.