Clustering in Discrete Path Planning for Approximating Minimum Length Paths
Frank Imeson Stephen L. Smith

An SDP-Based Algorithm for

 Linear-Sized Spectral Sparsification
    Yin Tat Lee

Microsoft Research
 Redmond, USA


He Sun

The University of Bristol

Bristol, UK



    
=====================================================================================================








In this paper we consider discrete robot path planning problems on metric graphs.  We propose a clustering method, for the planning graph that significantly reduces the number of feasible solutions, yet retains a solution within a constant factor of the optimal.  By increasing the input parameter Γ, the constant factor can be decreased, but with less reduction in the search space.  We provide a simple polynomial-time algorithm for finding optimal s, and show that for a given Γ, this optimal is unique. We demonstrate the effectiveness of the clustering method on traveling salesman instances, showing that for many instances we obtain significant reductions in computation time with little to no reduction in solution quality.








§ INTRODUCTION


Discrete path planning is at the root of many robotic applications, from surveillance and monitoring for security, to pickup and delivery problems in automated warehouses. In such problems the environment is described as a graph, and the goal is to find a path in the graph that completes the task and minimizes the cost function.  For example, in monitoring, a common problem is to compute a tour of the graph that visits all vertices and has minimum length <cit.>. These discrete planning problems are typically  <cit.>, and thus there is a fundamental trade off between solution quality and computation time. In this paper we propose a graph clustering method, called , that can be used to reduce the space of feasible solutions considered during the optimization.  The parameter Γ serves to trade-off the feasible solution space reduction (and typically computation time) with the quality of the resulting solution.

The idea behind is to group vertices together that are in close proximity to each other but are also far from all other vertices. Figure <ref> shows an example of in an office environment. Given this clustering, we solve the path planning problem by restricting the path to visit vertices within each cluster consecutively (i.e., no path can visit any cluster more than once). This restriction reduces the number of possible solutions exponentially and thus reduces the amount of computational time needed to find good solutions.

Unlike other clustering methods, does not accept as input a desired number of clusters.  This means that some instances will have no clusters, while others will have many. In this way, s only explore natural structures within the problem instances instead of imposing structures onto the instance.   Additionally, when the graph is metric, we establish that for a given , the optimal path of the clustered planning problem is within a constant factor (dependent on Γ) of the true optimal solution.





  
Related work 
There are a number of clustering methods for Euclidean <cit.> and discrete <cit.> environments. Typically the objective of these algorithms is to find a set of equal (or roughly equal) non-overlapping clusters that are grouped by similarity (close in proximity, little to no outgoing edges, etc …), where each location in the graph is assigned to one cluster. For these methods, the desired number of clusters is given as an input parameter. In contrast, in , the idea is to simply find a specific form of clustering within the environment, if it exists. These s may be nested within one another.

There are other clustering methods that also look for specific structures within the graph such as community structures <cit.>, which is based on a metric that captures the density of links within communities to that between communities. In contrast, our clustering method is specifically designed to find structures that yield desirable properties for path planning on road maps.

The use of clustering to save on processing/time is done in a variety of different fields such as data mining <cit.>, parallel computer processing <cit.>, image processing <cit.>, and control <cit.> for path planning. In environments that have regions with a high degree of connectivity, such as electronic circuits, clustering is commonly used to identify these regions and then plan (nearly) independently in each cluster <cit.>. For path planning problems with repetitive tasks, one can cluster a set of popular robot action sequences into macros <cit.>, allowing the solver to quickly discover solutions that benefit from these action sequences. In applications such as sensor sweeping for coverage problems <cit.> or in the routing of multiple agents <cit.>, clustering has been used to partition the environment into regions that can again be treated in a nearly independent manner, reducing computation time.

There is some prior work on partitioning in discrete path planning. Multilevel refinement <cit.> is the process of recursively coarsening the graph by aggregating the vertices together to create smaller and smaller instances, for which a plan can be found more easily. The plan is then recursively refined to obtain a solution to the original problem. The idea in coarsening a graph is that the new coarse edges should approximate the transition costs in the original graph.  This differs from , which preserves the edges within the graph. There are a number of clustering approaches that aim to reduced the complexity of Euclidean and or planar problems <cit.>. is more general, in that it works on any graph, while the solution quality guarantees only hold for metric graphs.



  
Contributions The main contribution of this paper is the introduction of , a clustering method for a class of discrete path planning problems.  We establish that the solution to the corresponding clustered problem provides a min(2, 1 + 3/2Γ)-factor approximation to the optimal solution. We give some insight into the reduction of the search space as a function of the amount of clustering, and we provide an efficient algorithm for computing the optimal . We then use an integer programming formulation of the problem to demonstrate that for many problem instances the clustering method reduces the computation time while still finding near-optimal solutions.








§ PRELIMINARIES IN DISCRETE PATH PLANNING


In this section we define the class of problems considered in this paper, review some semantics of clusters, review the traveling salesman problem () <cit.> and define its clustered variant, the general clustered traveling salesman problem ().







 §.§ Discrete Path Planning

Given a graph G = V,E,w, we define a path as a non-repeating sequence of vertices in V, connected by edges in E. A cycle is a path in which the first and last vertex are equal, and for simplicity we will also refer to cycles as paths. Let 𝒫 represent the set of all possible paths in G. Then, abstractly, a path planning constraint defines a subset 𝒫_1 ⊆𝒫 of feasible paths. Given a set of constraints 𝒫_1, 𝒫_2, …, 𝒫_m, the set of all feasible paths is 𝒫_1 ∩𝒫_2 ∩⋯∩𝒫_m. In this paper we restrict our attention to the following class of constraints and planning problems.


	A constraint 𝒫_1 is order-free if, given any p∈𝒫_1, then all paths obtained by permuting the vertices of p are
	also in 𝒫_1.


[Discrete Path Planning Problem]
  Given a complete weighted graph G = V,E,w and a set of order-free constraints {𝒫_1, 𝒫_2, …, 𝒫_m }, find the minimum
  length feasible path.


Many discrete path planning problems for single and multiple robots fall into this class, so long as they do not restrict the ordering of vertex visits (i.e., no constraints of the form “visit A before B”). Some examples include single and multi-robot traveling salesman problems, point-to-point planning, and patrolling.  As a specific example the is a problem where a robot is required to visit exactly one location in each non-overlapping set of locations <cit.>. This is naturally expressed in the above framework by having one constraint for each set: for each cluster V_i we have a constraint stating that exactly one vertex in V_i must be visited in the path. 

A metric discrete path planning problem is one where the edge weights in the graph G satisfy the triangle inequality: for v_a,v_b,v_c∈ V, we have w(v_a,v_c) ≤ w(v_a, v_b) + w(v_b, v_c).

To describe the number of feasible paths for a given planning problem, we use the phrase search space size. For example, a problem where we must choose an ordering of n locations has a search space size of n!, since there are n! combinations that a path may take. Note that as more constraints are added to the problem, the search space size can only be reduced, since a feasible path must lie in the intersection of all constraints.







 §.§ Clusters

A cluster is a subset of the graph's vertices, V_i ⊂ V. Given the clusters V_1 and V_2, we say V_1 is nested in V_2 if V_1 ⊆ V_2. The clusters V_1 and V_2 are overlapping if V_1 ∩ V_2 ≠∅, V_1 ⊈ V_2, and V_2 ⊈ V_1. A set of clusters (or clustering) is denoted by C = {V_1,…,V_m}. A clustering C = {V_1, V_2, …, V_m } is a nested if there exists some V_i ⊆ V_j for V_i, V_j ∈ C.

In this paper we seek to add clustering constraints to a discrete planning problem that reduce its search space size, but also retains low-cost feasible paths. The clustering constraints we consider are of the following form.


Given a graph G  = V,E,w and a cluster V_i ⊆ V, a feasible path p must visit the vertices within the cluster V_i consecutively. Formally, the vertices visited by p, V[p] are visited consecutively if there exists a path segment p' of p that visits every vertex in V_i ∩ V[p] and is of length |V_i ∩ V[p]|.


Note that in the above definition, it is not necessary for all of the vertices in V_i to be visited. It is just necessary to visit the vertices consecutively in V_i that are visited.







 §.§ Traveling Salesman Problems

The traveling salesman problem () is defined as follows: given a set of cities and distances between each pair of cities, find the shortest path that the salesman can take to visit each city exactly once and return to the first city (i.e., the shortest tour). A tour in a graph that visits each vertex exactly once is called a Hamiltonian cycle (regardless of path cost). The general clustered version of is the extension that requires the solution to visit the vertices within the clusters consecutively. The definition of these problems is as follows:

[Traveling Salesman Problem ()]
Given a complete graph G = V,E,w with edge weights w: E →_≥ 0, find a Hamiltonian cycle of G with minimum cost.  


[General-]
  Given a complete and weighted graph G = V,E,w along with a
  clustering C = {V_1,…, V_m}, find a Hamiltonian cycle of G with
  minimum cost such that the vertices within each cluster V_i are visited
  consecutively.


The traditional version of the restricts the clusters to be non-overlapping (and non-nested). For this paper we use the syntax to emphasize when we are solving a General-problem to refer to the traditional problem.








§ 


In this section, we define and show that the ed path planning problem provides a min(2, 1 + 3/2Γ) approximation of the original path planning problem. We then describe an algorithm for finding the optimal , and characterize the search space reductions.







 §.§ Definition of 

Below we define the notion of s, s, and the clustered discrete path planning problem. Then we pose the clustering problem as one of maximizing the search space reduction.


  
  Given a graph G = V,E,w and a cluster V_i ⊂ V, we define
  the following quantities for V_i relative to G:
  
    α_i    ≡min_v_a ∈ V_i, v_b ∈ V ∖ V_i (w(v_a, v_b), w(v_b, v_a)) 
    β_i    ≡max_v_a,v_b ∈ V_i, v_a ≠ v_b w(v_a, v_b) 
    Γ_i    ≡α_i/β_i,

  where α_i represents the minimum weight edge entering or exiting the
  cluster V_i, and β_i represents the maximum weight edge within V_i. The
  ratio Γ_i is a measure of how separated the vertices in V_i are from
  the remaining vertices in G.



  
  Given an input parameter Γ≥ 0 and a graph G = V,E,w, a
  clustering C = {V_1, V_2,…,V_m} is said to be a if
  and only if V is covered by V_1 ∪ V_2 ∪⋯∪ V_m; each V_i
  ∈ C has a separation Γ_i ≥Γ; and the clusters are
  either nested (V_i ⊆ V_j or V_j ⊆ V_i for all V_i, V_j ∈ C)
  or non-overlapping (V_i ∩ V_j = ∅).


The search space reduction for path planning problems comes from restricting paths to visit the clusters consecutively and our goal is to maximize that reduction. Thus we are interested in the following two problems.


  
  Given a discrete path planning problem P and a clustering
  C, the clustered version of the problem P' has
  the constraint that the path must visit the vertices within each
  cluster consecutively, in addition to all the constraints of P.



  
  Given a graph G = V,E,w and a parameter Γ > 0, find a
  C^* such that the search space reduction is maximized.



Note that in Definition <ref> overlapping clusters are not permitted. This is necessary for the problem in Definition <ref> to be well defined. In addition, we will see in the following section that clusters that have a separation of Γ_i > 1 cannot overlap.








 §.§ Solution Quality Bounds

In this section, we show that when the graph G is metric and Γ > 1, then the solution to the Γ-clustered path planning problem provides a min(2, (1 + 3/2Γ))-factor approximation to the optimal.





  
  Given a metric discrete path planning problem P with optimal solution p^*
  and cost c^*, a C = {V_1, V_2, …, V_m } where
  Γ > 1, then the optimal solution (p')^* to the clustered problem P'
  over the same set of vertices is a solution to P with cost (c')^* ≤min(2, 1 + 3/2Γ) c^*.


To prove the main result, we begin by proving the first half of the bound (c')^* ≤ 2c^*. We do this by using an minimum spanning tree (MST) to construct a feasible solution for P'.


  
  Given a metric graph G and a C, with Γ > 1, every
  MST will have exactly one inter-set edge for each cluster V_i ∈ C.




  We prove the above result by contradiction. Suppose the MST has at least two
  inter-set edges connected to V_i. Thus, there are at least two sets of
  vertices in V_i that are not connected to each other using intra-set edges.
  We can then lower the cost of the MST by removing one of these inter-set edges
  of weight ≥α_i and replace it with an intra-set edge of weight
  ≤β_i < α_i. This highlights the contradiction and thus every
  MST will have exactly one inter-set edge for each cluster V_i ∈ C.






  
  Consider a metric discrete path planning problem P with an optimal solution
  path p^* and cost c^*. Then given a C = {V_1, V_2,
  …, V_m } with Γ > 1, the optimal solution (p')^* for the
  clustered problem P' over the same set of vertices V[p^*] is a solution to
  P with cost (c')^* ≤ 2 c^*.



  To prove the above result, we will use the MST approach described below and in
  <cit.> to construct a path p' over the set
  of vertices in V[p^*]. This approach yields a solution p' for P' that
  has our desired cost bound, c' ≤ 2c^* <cit.>.
  The MST procedure is described below.
  
  
    
  * Find a minimum spanning tree for the vertices V[p^*].
    
  * Duplicate each edge in the tree to create a Eulerian graph.
    
  * Find an Eulerian tour of the Eulerian graph.
    
  * Convert the tour to a : if a vertex is visited more than once, after the first visit, create a
          shortcut from the vertex before to the one after, i.e., create a tour
          that visits the vertices in the order they first appeared in the tour.
  
  
  What remains is to prove that the above tour is a feasible solution for P'. First we
  note that the above approach yields a single tour of all the vertices in
  V[p^*], i.e., there are no disconnected tours. Next we note that
  Lemma <ref> states that every MST uses exactly one inter-set
  edge for each cluster V_i ∈ C. Thus when the edges are duplicated and a
  Eulerian tour is found, there are only two inter-set edges used for each V_i
  ∈ C. Furthermore short-cutting the path does not change the number of
  inter-set edges used by the tour, thus the final solution p' only has
  one incoming and one outgoing edge for each cluster V_i ∈ C and so it is a
  clustered solution for P' that satisfies the bound since the approach
  also yields a solution with cost c' ≤ 2c^*.


Next we prove the second half of the bound (c')^* ≤(1 + 3/2Γ)c^* by using Algorithm <ref> to construct a feasible solution p' for P'. Additionally we use a modified graph Ĝ defined in Definition <ref> to show that the cost of this solution satisfies our desired bound.







  
  Given a feasible path p for P and a cluster V_i ∈ C that is not
  visited consecutively, then p_i ←deform(p,V_i) does visit
  V_i consecutively and any subsequent deformed paths p_i+n+1←deform(p_i+n,V_i+n+1) also visit V_i consecutively, for n
  ∈_> 0.



  By construction V_i is visited consecutively in p_i ←deform(p,V_i). The remaining claim that V_i continues to be
  visited consecutively is proven by showing that the number of inter-set edges
  for V_i in the subsequent paths remains the same.
  
  We prove this result by contradiction. Suppose there is a sequence 
  v_a, v_b∈ p_j-1 for some j > i such that v_a, v_b ∈ V_i
  and v_a is no longer connected to v_b in p_j←deform(p_j-1,V_j); that is, v_a, v_b∉p_j.
  
  This would mean that one or more vertices were inserted in between v_a and
  v_b, thus creating a new inter-set edge. In Algorithm <ref>, this
  cannot happen in lines 5-7 since the path for the 1^st vertex to the
  k^th is unchanged. This also cannot happen in lines 8-9 since
  this part of the algorithm is only connecting vertices within the cluster
  V_j together. Finally, this cannot happen in lines 11-13, since the
  path is not changing the order of the appearance of v_a and v_b (no
  insertions, just deletions).
  
  Thus there are no additional inter-set edges created by
  Algorithm <ref> for cluster V_i, which highlights our
  contradiction. Therefore all subsequent paths must also visit V_i
  consecutively.



  
  When Algorithm <ref> is applied to p^* iteratively for each V_i
  ∈ C to generate the solution p', the solution is unique despite the order
  that deform(p,V_i) was called for all V_i ∈ C. Furthermore the
  order of the clusters is determined by their first appearance in p.
  
  This follows from the method in which Algorithm <ref> reorders
  the vertices within the tour. Specifically, the order of vertices within each cluster V_i is preserved as deform(p,V_i) is
  called as is the ordering of the remaining vertices.






  
  Consider a feasible path p for P that has 2(n+1) ≥ 4 inter-set edges
  for V_i such that Γ_i > 1 and n ∈_≥ 0.
  Then the cost to deform p into p' ←deform(p,V_i) is c'
  - c ≤ (2n+1)β_i.



  In this proof we analyze the cost to deform p into p', which is a result
  of calling p' ←deform(p,V_i)
  (Algorithm <ref>). There are three types of deformations that
  result from the algorithm: 1) there are short cuts created within the
  cluster; 2) there are short cuts created outside of the cluster; and 3) there
  is a new outgoing edge for the cluster. These deformations are illustrated in
  Figure <ref> and a classification of the edges in the figure are
  as follows: 1) edges v_3, v_4 and v_6, v_7 are short cuts
  within the cluster; 2) edges v_10, v_11 and v_12, v_13
  are short cuts outside of the cluster; and 3) edge v_8, v_9 is the new
  outgoing the edge for the cluster.

  We start by examining the incurred cost to short cut paths within the cluster.
  Consider a path segment v_a, v_b, v_c, …, v_x, v_y, v_z of p
  such that v_a is directly connected to v_z in p' with the edge
  v_a, v_z and v_a, v_z ∈ V_i. The incurred cost of each of these
  edges is ≤β_i due to the fact that the cost of any intra-set edge
  has weight ≤β_i. There are n such shortcuts of this nature
  incurred from performing deform(p,V_i) (n captures the
  number of extra visits to the cluster), and so the total incurred cost for
  this type of shortcut is ≤ nβ_i.

  Next we examine the incurred cost to short cut paths outside of the cluster.
  Consider a path segment v_a, v_b, v_c, …, v_x, v_y, v_z of p
  such that v_a is directly connected to v_z in p' with the edge
  v_a, v_z, v_a, v_z ∉V_i and v_b, v_c, …, v_y ∈ V_i.
  The incurred cost for each of these short cuts is again ≤β_i. This
  is due to the metric property of G: The cost of the direct path from
  v_a to v_z is less than or equal to any path from v_a to v_z,
  specifically c(v_a, v_z) ≤ c(v_a, v_b) + c(v_b, v_y) + c(v_y, v_z) ≤
  c(v_a, v_b) + β_i + c(v_y, v_z). Thus the incurred cost Δ, of this
  shortcut is bounded by the difference between the cost of the new edges in
  p' and the removed edges in p^*, namely:
  
  
    Δ   = c(v_a, v_z) - c(v_a,v_b) - c(v_y, v_z) 
       ≤ c(v_a, v_b) + β_i + c(v_y, v_z) - c(v_a,v_b) - c(v_y, v_z) 
       ≤β_i

  
  There are n such shortcuts of this nature incurred by
  deform(p,V_i), and so the total incurred cost for this type of
  shortcut is also ≤ nβ_i.

  Lastly we examine the incurred cost of the new outgoing edge. Consider the
  path v_a, v_b, v_c, …, v_x, v_y, v_z of p such that
  v_b,v_c is the first outgoing edge of V_i and v_x,v_y is the
  last outgoing edge of V_i, thus v_x, v_c is the new outgoing edge.
  Then due to the metric property we know that c(v_x, v_c) ≤ c(v_x,v_b) +
  c(v_b,v_c) ≤β_i + c(v_b,v_c). The incurred cost of this deformation
  is the difference between the cost of the new edge v_x,v_c and the
  removed edge v_b,v_c (this edge has not been considered in any
  previous incurred cost calculation):
  
  
    Δ   = c(v_x, v_c) - c(v_b,v_c) 
       ≤β_i + c(v_b,v_c) - c(v_b,v_c) 
       ≤β_i


  This accounts for all of the incurred costs, and so the total cost to deform
  p into p' via deform(p,V_i) is c' - c ≤ (2n+1)β_i.


We introduce the modified graph Ĝ in the following definition to aid with our ongoing proof of the bound.





  
  Given a graph G and a C, the modified graph Ĝ is
  a copy of G with the following modifications: if v_a, v_b is an
  inter-set edge with v_a ∈ V_i and v_b ∈ V_j then ĉ(v_a, v_b) =
  c(v_a, v_b) + 3/2max(β_i, β_j), otherwise ĉ(v_a, v_b)
  = c(v_a, v_b), where β_i and β_j are as defined in
  Definition <ref>.



  
  Consider a feasible path p for P and a V_i such that
  Γ_i > 1. Then the cost to deform p into p' ←deform(p,V_i) in Ĝ is ĉ' - ĉ≤ 0.



  In this proof we analyze the cost to deform p into p'in Ĝ, which
  is a result of single call p' ←deform(p,V_i)
  (Algorithm <ref>).
  
  From Lemma <ref> we see that the cost to deform p into p' with
  respect to G is c' - c ≤ (2n+1)β_i, where there are 2(n+1) ≥ 4
  inter-set edges for V_i in p. The cost of p in Ĝ is
  
  
    ĉ≥ c + 2(n+1)(3/2)β_i = c + 3(n+1)β_i

  
  and the cost of p' in Ĝ is
  
    ĉ' ≤ c' + 2(3/2β_i) ≤ c + (2n+1)β_i + 3β_i.

  
  Thus
  
  
    ĉ' - ĉ   ≤ (2n+1)β_i + 3β_i - 3(n+1)β_i 
       =    2nβ_i + β_i + 3β_i - 3nβ_i - 3β_i 
       =    β_i - nβ_i

  
  and since n ≥ 1 (otherwise we did not need to deform the path), then
  ĉ' - ĉ≤ 0.



  
  Given a metric discrete path planning problem P with optimal solution cost
  c^*, Γ > 1 and a C = {V_1, V_2, …, V_m },
  then the optimal solution (p')^* to the clustered problem P' over the same
  set of vertices is a solution to P with cost (c')^* ≤ (1 +
  3/2Γ) c^*.



To prove the above result we will work with the modified graph Ĝ (defined in Definition <ref>) and use the result from Lemma <ref> to show that there exists a clustered solution in Ĝ that has the same cost or lower than ĉ(p^*). Then we will relate (c')^* to c^*.

First we show that there exists a clustered solution p' that satisfies the following:


    ĉ(p') ≤ĉ(p^*)


To find a solution p' that satisfies the above we will use Algorithm <ref> to deform p^* into p'. The deform algorithm is called for each V_i ∈ C in any order as p_i+1 = deform(p_i,V_i) to form a solution for P' (see Lemma <ref>). For each call of p_i+1 = deform(p_i,V_i) the incurred cost ĉ(p_i) - ĉ(p_i+1) ≤ 0 (see Lemma <ref>). Thus after the series of calls, we have a clustered solution p' satisfying


    ĉ(p') ≤ĉ(p^*).


Next we relate c(p^*) to ĉ(p^*) by observing the following for an inter-set edge v_a, v_b∈ p^*:


    ĉ(v_a, v_b)    = c(v_a, v_b) + 3/2max(β_i, β_j) 
       = c(v_a, v_b) + 3/2max(α_i/Γ_i, α_j/Γ_j) 
       ≤( 1 + 3/2max(1/Γ_i, 1/Γ_j) ) c(v_a, v_b) 
       ≤( 1 + 3/2Γ) c(v_a, v_b)


The above inequality for ĉ(p^*) is true for each edge v_a, v_b∈ p^*, inter-set edge or not. Therefore


    ĉ(p^*) ≤( 1 + 3/2Γ) c(p^*).


Due to the construction of Ĝ and how ĉ(p') ≤ĉ(p^*) we deduce that


    (c')^* ≤ĉ(p^*),


since


    (c')^* ≤ c(p') ≤ĉ(p') ≤ĉ(p^*).


Therefore we have


    (c')^* ≤( 1 + 3/2Γ) c^*.






  The proof of the main result in Theorem <ref> directly follows from Lemma <ref> and Lemma <ref>.  







We have not fully characterized the tightness of the bounds from Lemma <ref> and Lemma <ref>, but we we have a lower bound, which is illustrated in Figure <ref>. In this example, the graph is scale-able (we can add vertices three at a time). The clustered and non-clustered solutions for this example have a cost relation of


    lim_|V| →∞ (c')^* = ( 1 + 2/2Γ + 1) c^*.


We also provide the graph in Figure <ref> to show how the gap changes as Γ varies.

The bound for this graph is obtained as follows. Let n = |V|/3 - 1 for |V|/3∈_>0. Then the optimal non-clustered solution cost is (recall that Γ = α/β):


    p^*    = v_1, v_2, v_3, v_4, v_6, v_5, …
    
      c^*    = α + β + α + n(2α + β) 
       = ( n+1 )( 2α + β) 
       = ( n+1 )( 2 + 1/Γ) α


The optimal clustered solution is:


    (p')*      = v_1, v_2, v_3, v_5, v_6, …, v_4, v_7, …
    
      (c')^*     = α + β + 2nβ + α + n(2α + β) 
       = 2α + 3β - 2β + n(2α + 3β) 
       = (n+1)(2α + 3β) - 2β
       = ( (n+1)(2 + 3/Γ) - 2/Γ) α


As the instance grows (|V| →∞, which implies n →∞), we have the following: 

    lim_n →∞ (c')^*
             =  (n+1)(2 + 3/Γ) - 2/Γ/( n+1 )(2 + 1/Γ) c^*  
       =  ( 2 + 3/Γ/2 + 1/Γ) c^*  
       =  ( 1 + 2/2Γ + 1) c^*













 §.§ Finding s

Before we describe our method for finding optimal (s), we describe a few properties of s.






  §.§.§ Overlap

A special property of is that when Γ > 1, there are no overlapping clusters. Specifically there are no two clusters V_i and V_j with Γ_i > 1 and Γ_j > 1 that have a non-zero intersection unless one cluster is a subset of the other. 


  
  Given a graph G, clusters V_i and V_j with separations Γ_i
  > 1 and Γ_j > 1 (defined in Definition <ref>), then
  V_i ∩ V_j is non-empty if and only if V_i ⊆ V_j or V_j
  ⊆ V_i.



  We prove the above result by contradiction. Before we begin, recall that edges
  cut by the cluster V_i have edge weights ≥α_i and edges within
  the cluster have edge weights ≤β_i. Let us assume that V_i and
  V_j overlap and are not nested. Without loss of generality let β_j ≤β_i. Then there exists an edge v_a, v_b with weight w(v_a, v_b)
  ≤β_j for v_a ∈ V_i ∩ V_j and v_b ∈ V_j ∖ (V_i ∩
  V_j). Since this edge does not exist in the cluster V_i but it
  is cut by V_i, then it must be the case that w(v_a, v_b) ≥α_i.
  However, this edge does exist in the cluster V_j and so α_i ≤β_j, since w(v_a, v_b) ≤β_j. This result highlights the
  contradiction: Γ_i = α_i/β_i≤β_j/β_i≤β_i/β_i = 1.







  §.§.§ Uniqueness

The non-overlapping property for s with Γ > 1 implies that there exists a unique maximal clustering set C^* (more clusters equals more reductions in the search space size). This result follows from the simple property that if a cluster V_i exists and does not exist in our clustering C^*, then we must be able to add it to C^* to get additional search space reductions.


  
  Given graph G and a parameter Γ > 1, the problem of finding a
  C^* that maximizes the search space reduction has a unique
  solution C^*. Furthermore C^* contains all clusters V_i with separation
  Γ_i ≥Γ.



  We use contradiction to prove that C^* is unique. Suppose there exists two
  different s C_1 and C_2 that maximize the search space
  reductions for a given Γ > 1. Then, there is a cluster V_1 that is in
  C_1 and not in C_2 (or vice versa). This implies that either V_1 is
  somehow incompatible with C_2, which we know is not the case due to
  Lemma <ref> (i.e., clusters do not overlap unless one is a subset
  of the other) or this cluster can be added to C_2. This is a contradiction,
  which proves the first result. The second result directly follows since adding
  a cluster can only further reduce the search space size of the problem.



  
  Given a graph G and two clustering parameters Γ_i > Γ_j > 1,
  the optimal clustering C^*_j for Γ_j is a superset of any
  clustering for Γ_i.



  We prove this result by contradiction. Suppose we have a clustering C_i for
  Γ_i and the optimal clustering C_j^* for Γ_j, for which there
  exists a cluster V_1 in C_i that is not in C_j^*. Then by the definition
  of s V_1 must satisfy Γ_1 ≥Γ_i and since
  Γ_i > Γ_j then Γ_1 ≥Γ_j, which makes V_i a
  cluster that should be added to C_j^*. This contradicts
  Proposition <ref> and thus proves the result.



  There exists a minimum Γ^* > 1 and its optimal C^*
  that is a superset of all other s for Γ > 1.



  This result follows directly from Corollary <ref>, when we
  consider Γ^* to be the smallest ratio of edge weights in the graph
  G (find the two edges that give us the smallest ratio). Then for every
  cluster with a separation parameters Γ_i > 1, it must also be greater
  than or equal to Γ^* since Γ_i itself is a ratio of existing edge
  weights in the graph G. Thus by Corollary <ref>, C^*
  must be superset of any other for some Γ > 1.







  §.§.§ An Approach For Finding s

Given an input Γ > 1, Algorithm <ref> computes the optimal s, i.e., the with maximum search space reduction. Informally the algorithm deletes edges in the graph from largest to smallest (line 6-7) to look for s. It uses a minimum spanning tree () to keep track of when the graph becomes disconnected, and when it does the disconnected components are tested to see if they qualify as s (line 9-11). Regardless, any non-trivial sized disconnected component (or not) is added back to the queue (line 13-14), so that it can be broken and tested again to find of all nested s.




  
  Given G and a Γ > 1, Algorithm <ref> finds the optimal
  C^* in O(|V|^3) time.



  The proof is two fold, first we show that Algorithm <ref> runs
  in polynomial time and second we show that it finds the optimal
  . For this proof let n = |V|.

  Minimum spanning trees can be found O(n^2) time <cit.>
  (line 3). The rest of the algorithm modifies the from line 3, which
  originally has n edges and so the while loop for the rest of the algorithm
  can only run at most n times (we can't remove more than n edges). Finding
  the largest edge(s) and removing them in line 6 and 7 takes O(n) time.
  Creating the induced subgraph and finding the maximum edge cost in lines 9 and
  10 takes O(n^2) time. Testing if the subgraph is a clique (line 11) takes
  O(n^2) time. Thus lines 1 to 3 run in O(n^2) time and lines 4 to 14 run in
  O(n· n^2), which means the entire algorithm runs in O(n^3) time or
  O(|V|^3).
  
  Next we show that Algorithm <ref> finds the optimal
  . To do so, we will show that V[m'] does indeed represent a
  with separation Γ' ≡α/β (line
  11) as defined by Definition <ref> and then we  finish
  by showing that the algorithm does not omit any candidate clusters, thus
  proving the theorem by leveraging Proposition <ref>.

  Let us start by understanding how to find s and how we use
  s in the algorithm. A with separation Γ_i > 1 is a
  subgraph of G that is connected with intra-edge weights less than the
  inter-edge weights connected to the rest of the graph. Thus one method of
  searching for s is to delete all edges in the graph of weight
  ≥α and if there is a disconnected subgraph in G then and only
  then is it a possible . We can use s to more efficiently
  keep track of these deleted edges. By definition, an is tree that connects
  vertices within the graph with minimum edge weight. If we remove edges
  of size ≥α in the graph to search for disconnected sub-graphs, then
  the graph is disconnected if and only if the is disconnected. This
  follows by considering the cut needed to disconnect these two sub-graphs (the
  minimum weight edge cut, shares the same weight cut by the ). Thus we can
  instead search for s by disconnecting the . Furthermore if
  we disconnected the by incrementally removing the largest edge(s) of
  weight α from the tree then we know that induced sub-graphs of the
  newly disconnected trees have at least one inter-set edge of size α.
  Line 9 in the Algorithm creates the induced subgraph G' of a disconnected
  tree (m' ∈ M'), line 10 measures its β, and if G' is a clique and
  meets the separation criterion (Γ' ≥Γ) then V[m'] is indeed
  a (by definition), thus it is added to the clustering C in
  line 12. 
  
  Next we show that the Algorithm did not omit any candidate clusters. We have
  already argued that only disconnected trees need to be considered for
  s, thus what is left to show is that the algorithm tests every
  possible value of α to disconnect the tree.  This is true since it
  considers every edge in the original . This is because every disconnected
  tree of size two or more is added back to M in line 14 until every edge
  originally in the is removed in line 7. 

  Therefore this algorithm finds all of the candidate s and
  Proposition <ref> tells us that it is the unique optimal
  for the given Γ > 1.








 §.§ Search Space Reduction

The last remaining question is to determine how much the clustering approach reduces the search space. In general, this is difficult to answer since it depends on the particular constraints of the path planning problem.  However, to get an understanding of the search space reduction, consider the example of with a non-nested clustering (nesting would result in further search space reductions). Let r be the ratio of the non-clustered search space size N_0, to the clustered search space size N_1, for a graph with vertices V and a clustering C = { V_1, V_2, …, V_m }. Then, the ratio (derived from counting the number of solutions) is as follows:


    r ≡N_0/N_1 = |V|!/m! ∏_i^m |V_i|!

To further simplify the ratio consider the case where all clusters are equally sized (for all V_i, V_j ∈ C, |V_i| = |V_j|):


  Given a graph G and a clustering C = {V_1, V_2, …, V_m} such that
  |V_i| = |V_j| for all i,j ∈ [1,m] then the ratio r of the search
  space size for the original problem to the cluster problem is
  [The big-Ω notation states that for large enough
  |V| the ratio r is at least k (̇m!)^x-1 for some constant k.]
  
  
    r = Ω( (m!)^x-1),

  
  where x = |V|/m.



  The number of solutions for the (directed) problem is N_0 = |V|! and
  the number of solutions for the problem is: N_1 = m! (
  |V|/m ! )^m (these results come from counting the number of
  possible solutions). First let us bound |V|! = (mx)!:
  
  
    |V|!     =    ∏_i=m^1∏_j=0^x-1( ix - j ) 
       =    ∏_i=m^1∏_j=0^x-1 (i) ( x - j/i) 
       ≥∏_i=m^1∏_j=0^x-1 (i) ( x - j ) 
       =    ( ∏_i=m^1 i^x ) ( ∏_j=0^x-1 ( x - j ) )^m 
       =    (m!)^x(x!)^m

  We now use the fact that |V|! ≥ (m!)^x(x!)^m to prove the main result: 
  
  
    r    ≡N_0/N_1  =       |V|!/m!(x!)^m≥(m!)^x (x!)^m/m! (x!)^m  =       (m!)^x-1

  
  Thus r = Ω( (m!)^x-1).


To get an idea of the magnitude of r, consider an instance of size |V|=100 divided into four equal clusters. The clustered problem has a feasible solution space of size N_1 ≈  1.49 × 10^-56 N_0, where N_0 is the feasible solution space size of the non-clustered problem. However, N_1 is still extremely large at about 1.39 × 10^102.








§ EXPERIMENTS


In this section we present experimental results that demonstrate the effectiveness of for solving discrete path planning problems. We focus on metric instances drawn from the established library  <cit.>, which have a variety of problem types (the first portion of the instance name indicates the type and the number  indicates the size). The tests were conducted with Γ = 1.000001, for which Theorem <ref> implies that the solution to the clustered problem gives a min(2, 1 + 3/2Γ)-factor approximation to the instance. However, we will see that the observed gap in performance is considerably smaller.

To test the effectiveness of the clustering method, we perform on each instance and recorded both the runtime and the number of clusters found. This gives us an idea of whether or not instances from have a structure that can be exploited by . Then, we use standard integer programming formulations for both the original instance and the general clustered version of the instance (). We solve each instance three times using the solver Gurobi <cit.> and recorded the average solver time and solution quality. All instances were given a time budget of 900 seconds, after which they were terminated and the best solution found in that run was outputted. The instances reported in this paper are the 37 instances that were solved to within 50% of optimal and have s. The remaining instances are not reported as they would have required more than 900 seconds to provide a meaningful comparison.

Additionally we demonstrate on an office environment to gain insight into the structure of s.







 §.§ Integer Programming Formulation

The clustering algorithm was implemented in Python and run on an Intel Core i7-6700, 3.40GHz with 16GB of RAM. The integer programming (IP) expression of the problem and clustered problem is solved on the same computer with Gurobi, also accessed through python. The results of both of these approaches is found in Table <ref> and summarized in Figure <ref>.

The following is the IP expression used for the clustered and non-clustered path planning problems, where each variable e_a,b∈{0,1}:



    minimize
       ∑_a=1^|V|∑_b=1^|V| e_a,b w(v_a, v_b) 
    subject to
       ∑_b=1^|V| e_a,b = 1, 
             for each  a ∈{ 1,2,…, |V| }
       ∑_a=1^|V| e_a,b = 1,
             for each  b ∈{ 1,2,…, |V| }
       ∑_∀ v_a ∈ V_i, v_b ∉V_i
            e_a,b = 1,
             for each  i ∈{ 1,2,…, m }
       ∑_∀ v_a ∉V_i, v_b ∈ V_i
            e_a,b = 1,
             for each  i ∈{ 1,2,…, m }
       ∑_e_a,b∈ E'
            e_a,b≤ |E'|-1,
             for each subtour  E'


The formulation was adapted from a IP formulation found in <cit.>, where the Boolean variables e_a,b represent the inclusion/exclusion of the edge v_a, v_b from the solution.

Constraints <ref> and <ref> restricts the incoming and outgoing degree of each vertex to be exactly one (the vertex is visited exactly once). Similarly constraints  <ref> and  <ref> restrict the incoming and outgoing degree of each cluster to be exactly one (these constraints are only present in the clustered version of the problem). Constraint <ref> is the subtour elimination constraint, which is lazily added to the formulation as conflicts occur due to the exponential number of these constraints. For each instance, we seed the solver with a random initial feasible solution.







 §.§ Results

Figure <ref> shows the ratio of time spent finding clusters with respect to total solver time. In all instances this time is less than 6% and most is less than 1%. Additionally as the total solver time grows, the ratio gets smaller (Time02 is for instances that use the full 900 seconds). This approach is able to find s on 63 out of 70 instances. In total it found 3700 non-trivial s (i.e., clusters with |V_i| ≥ 2), which is promising since the library contains a variety of different applications.

Figure <ref> and Table <ref>, shows that for instances that do not time out the solution path costs found by the clustering approach are close to optimal (Cost01 is close to 1 in the figure and the instances from burma14 to pr107 are almost all within 1% error as shown in the table). Furthermore when the solver starts to time out (exceeds its 900 second time budget) the solution quality of the approach starts to surpass the solution quality of the non-clustered approach (as shown by Cost02 in the figure). We attribute this trend to the fact that the clustered approach needs less time to search its feasible solution space and thus is able to find better quality solutions faster than its counterpart. In instances gr202, kroB200, pr107, tsp225, and gr229 the clustering approach does very well compared to the non-clustering approach, enabling the solver to find solutions within 1% of optimal for the first three instances and solutions within 6% of optimal for the latter two instances, while the non-clustered approach exceeds 8% of optimal in the first three instances and 28% of optimal for the latter two instances.

On average the approach is more efficient than the non-clustered approach, which is highlighted in Figure <ref> and Table <ref>. For the results that do not time out (Time01 in the figure) we often save more than 50% of the computational time, while maintaining a near optimal solution quality (Cost01 in the figure). For instances that require most or all of the 900 seconds (harder instances) the time savings can be quite large. This is particularly clear from the table when we compare the easy instances burma14 up to st70 that have an average time savings of around 60% to the harder instances kroA100, gr96, bier127, and ch130, which all have a time savings of more than 95%. For the instances that both time out (Time02 in the figure), the time savings is not present since both solvers use the full 900 seconds.

From these results we can see that when the approach does not time out, we usually save time and when the approach does time out we often find better quality solutions as compared to the non-clustered approach.


  It is worth emphasizing that we are not necessarily recommending solving instances in this manner. We are simply using as an illustrative example
  to show how can be used to reduce computation time in a given
  solver. Many discrete path planning problems are solved with IP solvers and as
  such we hope our results help provide some insight as to how would work on other path planning problems. In general unless the solver
  approach (IP or not) takes advantage of the clustering, there is no
  guarantee that a computation saving will be achieved.








 §.§ Clustering Real-World Environments

As shown in Figure <ref> we have also performed on real-world environments.  The figure shows the floor-plan for a portion of one floor of the Engineering 5 building at the University of Waterloo.  Red dots denote the locations of desks within the environment. We encoded the environment with a graph, where there is a vertex for each red dot and edge weights between vertices are given by the shortest axis-aligned obstacle free path between the locations (obstacle-free Manhattan distances). The figure shows the results of clustering for Γ = 1.000001. We see that locations that are close together are formed into clusters unless there are other vertices in close proximity.

A path planning problem on this environment could be robotic mail delivery, where a subset of locations must be visited each day. The clusters could then be visited together (or visited using the same robot).














§ CONCLUSION


In this paper we presented a new clustering approach called . We have shown how it can be used to approximate the discrete path planning problems to within a constant factor of min(2, 1 + 3/2Γ), more efficiently than solving the original problem. We verify these findings with a set of experiments that show on average a time savings and a solution quality that is closer to the optimal solution than it is to the bound. For future directions we will be investigating other path planning applications, which includes online path planning with dynamic environments.



10

url@samestyle








smith2011optimal
S. L. Smith, J. Tůmová, C. Belta, and D. Rus, “Optimal path planning
  for surveillance with temporal-logic constraints,” The International
  Journal of Robotics Research, vol. 30, no. 14, pp. 1695–1708, 2011.

gouveia2015load
L. Gouveia and M. Ruthmair, “Load-dependent and precedence-based models for
  pickup and delivery problems,” Computers & Operations Research,
  vol. 63, pp. 56–71, 2015.

jain1988algorithms
A. K. Jain and R. C. Dubes, Algorithms for clustering data.1em
  plus 0.5em minus 0.4emPrentice-Hall, Inc., 1988.

karypis1999chameleon
G. Karypis, E.-H. Han, and V. Kumar, “Chameleon: Hierarchical clustering using
  dynamic modeling,” Computer, vol. 32, no. 8, pp. 68–75, 1999.

kernighan1970efficient
B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning
  graphs,” Bell system technical journal, vol. 49, no. 2, pp. 291–307,
  1970.

guha2000rock
S. Guha, R. Rastogi, and K. Shim, “Rock: A robust clustering algorithm for
  categorical attributes,” Information systems, vol. 25, no. 5, pp.
  345–366, 2000.

katselis2016clustering
D. Katselis and C. L. Beck, “Clustering fully and partially observable graphs
  via nonconvex optimization,” in American Control Conference, 2016,
  pp. 4930–4935.

blondel2008fast
V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding
  of communities in large networks,” Journal of statistical mechanics:
  theory and experiment, vol. 2008, no. 10, p. P10008, 2008.

berkhin2006survey
P. Berkhin, “A survey of clustering data mining techniques,” in
  Grouping multidimensional data.1em plus 0.5em minus 0.4emSpringer, 2006, pp. 25–71.

meyerhenke2009new
H. Meyerhenke, B. Monien, and T. Sauerwald, “A new diffusion-based multilevel
  algorithm for computing graph partitions,” Journal of Parallel and
  Distributed Computing, vol. 69, no. 9, pp. 750–761, 2009.

gao2010kernel
S. Gao, I. W.-H. Tsang, and L.-T. Chia, “Kernel sparse representation for
  image classification and face recognition,” in European Conference on
  Computer Vision, 2010, pp. 1–14.

jin2012multi
X. Jin, S. Gupta, J. M. Luff, and A. Ray, “Multi-resolution navigation of
  mobile robots with complete coverage of unknown and complex environments,”
  in American Control Conference, 2012, pp. 4867–4872.

karypis1998fast
G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for
  partitioning irregular graphs,” SIAM Journal on Scientific Computing,
  vol. 20, no. 1, pp. 359–392, 1998.

backstrom2014automaton
C. Bäckström, A. Jonsson, and P. Jonsson, “Automaton plans,”
  Journal of Artificial Intelligence Research, vol. 51, no. 1, pp.
  255–291, 2014.

levihn2013foresight
M. Levihn, L. P. Kaelbling, T. Lozano-Perez, and M. Stilman, “Foresight and
  reconsideration in hierarchical planning and execution,” in IEEE/RSJ
  International Conference on Intelligent Robots and Systems, 2013, pp.
  224–231.

das2014mapping
A. Das, M. Diu, N. Mathew, C. Scharfenberger, J. Servos, A. Wong, J. S. Zelek,
  D. A. Clausi, and S. L. Waslander, “Mapping, planning, and sample detection
  strategies for autonomous exploration,” Journal of Field Robotics,
  vol. 31, no. 1, pp. 75–106, 2014.

ryan2008exploiting
M. R. K. Ryan, “Exploiting subgraph structure in multi-robot path planning,”
  Journal of Artificial Intelligence Research, pp. 497–542, 2008.

chevalier2009comparison
C. Chevalier and I. Safro, “Comparison of coarsening schemes for multilevel
  graph partitioning,” in International Conference on Learning and
  Intelligent Optimization, 2009, pp. 191–205.

karp1977probabilistic
R. M. Karp, “Probabilistic analysis of partitioning algorithms for the
  traveling-salesman problem in the plane,” Mathematics of operations
  research, vol. 2, no. 3, pp. 209–224, 1977.

haxhimusa2009approximative
Y. Haxhimusa, W. G. Kropatsch, Z. Pizlo, and A. Ion, “Approximative graph
  pyramid solution of the E-TSP,” Image and Vision Computing,
  vol. 27, no. 7, pp. 887–896, 2009.

applegate2006traveling
D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, The Traveling
  Salesman Problem: A Computational Study.1em plus 0.5em minus
  0.4emPrinceton University Press, 2006.

noon1993efficient
C. E. Noon and J. C. Bean, “An efficient transformation of the generalized
  traveling salesman problem,” Information Systems and Operational
  Research (INFOR), vol. 31, no. 1, pp. 39–44, 1993.

korte2012combinatorial
B. Korte, J. Vygen, B. Korte, and J. Vygen, Combinatorial
  optimization.1em plus 0.5em minus 0.4emSpringer, 2012, vol. 2.

prim1957shortest
R. C. Prim, “Shortest connection networks and some generalizations,”
  Bell system technical journal, vol. 36, no. 6, pp. 1389–1401, 1957.

reinelt1991tsplib
G. Reinelt, “TSPLIB–a traveling salesman problem library,” ORSA
  Journal on computing, vol. 3, no. 4, pp. 376–384, 1991.

optimization2012gurobi
G. Optimization et al., “Gurobi optimizer reference manual,” 2012.
  [Online]. Available: <http://www.gurobi.com>


gouveia1999asymmetric
L. Gouveia and J. M. Pires, “The asymmetric travelling salesman problem and a
  reformulation of the miller–tucker–zemlin constraints,” European
  Journal of Operational Research, vol. 112, no. 1, pp. 134–146, 1999.




