Data-Driven Topological Motion Planning with Persistent Cohomology
Florian T. Pokorny and Danica Kragic
Centre for Autonomous Systems, KTH Royal Institute of Technology

Abstract— In this work, we present an approach to topological motion planning which is fully data-driven in nature
and which relies solely on the knowledge of samples in thefree configuration space. For this purpose, we discuss the useof persistent cohomology with coefficients in a finite field tocompute a basis which allows us to efficiently solve the path
planning problem. The proposed approach can be used bothin the case where a part of a configuration space is wellapproximated by samples and, more generally, with arbitrary
filtrations arising from real-world data sets. Furthermore, ourapproach can generate motions in a subset of the configuration
space specified by the sub- or superlevel set of a filtration
function such as a cost function or probability distribution.
Our experiments show that our approach is highly scalable inlow dimensions and we present results on simulated PR2 arm
motions as well as GPS trace and motion capture data.

I. I NTRODUCTION AND R ELATED W ORK
In recent years, the “data-driven approach” has provided
a paradigm shift in robotics: instead of hand-coded mathematical models of an idealized version of the environment,a multitude of techniques which build probabilistic models
from sampled data have been developed [1]. Within the
motion planning community, this development has been mirrored in the development of sampling based motion planningtechniques such as rapidly exploring random trees (RRTs)[2] and probabilistic roadmaps (PRMs) [3]. In this work
we consider how to determine not just a single collision
free trajectory between two points, but a collection ofhomotopy inequivalent trajectories given collision freesamples, where trajectories are called homotopy inequivalent
when they cannot be continuously deformed into one anotherwithout collisions. While motion planning approaches such
as RRT and PRM-based methods [2], [3] aim to generate
either just a collision-free path, or a path which is close to
optimal with respect to some cost, the underlying graphs
used in these approaches are only able to approximate thepath-connectivity of the free configuration space Cf andcannot capture higher order topological features such as thenumber of holes and voids. In particular, they do not capture
information about the homology or homotopy groups of Cf
besides path connectivity.
On the other hand, while classical analytical methods tomotion planning, such as the works of [4] and [5], [6]construct cell complexes which can be used to compute
homology groups of Cf to extract this type of information,these methods have not focused on generating trajectories
in distinct homotopy classes and assumed that a complete
and noise-free description of Cf is specified, for example interms of semi-algebraic functions.

Input

Filtration

Cohomology &Threshold Selection

MotionPlanning

dense samples orsparse samples

e.g. DC(X)persistent cohomology
topological constraints

graph annotation
lifted Dijkstra

Fig. 1: Overview of our data-driven topological motion planning approach.
A small number of recent works, including [7], [8], [9],[10], [11], have started to study motion planning algorithms
for trajectories with homotopy class constraints. In the caseof 2D configuration spaces, the cited works rely on differential forms computing the winding angle around representative
points inside the obstacles in the configuration space C
and this idea has been generalized to higher dimensions.
However, all these works rely on a specific basis of thefirst de Rham cohomology group in order to perform motion
planning and they require an explicit geometric reduction of
the obstacles in Cf to representative skeleta. Our approach,as outlined in Fig. 1, instead assumes only the availability ofsamples in Cf , obtained using random sampling, or from a
database of successfully executed prior motions. From thesesamples, a simplicial complex filtration is then extracted,
taking into account a distance, probability density, or costfunction. This part of our approach is closely related to [12]which introduced persistent homology as a tool for classifying pre-existing trajectories, but which did not consider
the motion planning problem itself. We utilize persistentcohomology rather than homology to determine 1-cocycles
representing large features in the filtration and to find a filtration threshold for motion planning. The resulting 1-cocycles
correspond to ‘fences’ in the configuration space using which
we are able to formulate the topological motion planningproblem by means of a cohomologically annotated graphserving as input to an efficient implicit graph representation
and a lifted Dijkstra algorithm we introduce here.
II. BACKGROUND AND N OTATION
Algebraic Topology Preliminaries: In this work, we
make use of cohomology with coefficients in a field F.
While infinite fields such as Q can be used for all persistentcohomology computations, the path planning algorithm we
propose performs a search over a finite search space onlyin the case when F is also finite. Most typically, we shallconsider the finite field Zp with p elements, where p is aprime and Zp = {0, 1, . . . , p − 1}. The binary field Z2 will

SymbolCK
Cp (K)∂p
Bp (K)Zp (K)Hp (K)
Hpi,j (K)F
π1 (Y )X

Explanation
configuration space
simplicial complex
p-chains of K
pth boundary operator
p-boundaries of K
p-cycles of K
pth homology grouppth (i, j) persistenthomology groupa finite field
1st fundamental group of Y
set of samples in Rd

Symbol
Cf
|K|
p
C (K)
δp
B p (K)Z p (K)H p (K)
p
Hi,j
(K)
Zp
Xr

Explanation
collision free c-space
support of K
p-cochains of K
pth coboundary operator
p-coboundaries of K
p-cocycles of K
pth cohomology grouppth (i, j) persistentcohomology groupfinite field {0, . . . , p − 1}for some prime p
union of r-balls around X

TABLE I: Summary of our notation

Fig. 2: A simplicial complex K in 2D, consisting of vertices, edges andtriangles is displayed in both parts of the figure. On the left, we display a
1-cycle c in red, such that [c] ∈ H1 (K) yields a basis for the 1-dimensional
H1 (K) with Z2 coefficients. Marked edges correspond to 1-simplices withcoefficient 1 in c. In the right figure, a 1-cochain ϕ is displayed, where themarked red edges correspond to 1-simplices on which ϕ takes the value 1,
while ϕ takes the value 0 on the remaining 1-simplices.
be used in our experiments since it can be implemented very
efficiently. The books [13], [14] provide a reference for the
relevant concepts from algebraic topology, and a summaryof our notation is provided in Table I.
Simplicial Complexes: Recall that a geometric ksimplex σ = [v0 , . . . , vk ] in Rd is a convex hull of k + 1
ordered affinely independent elements v0 , . . . , vk ∈ Rd anda convex hull of an ordered subset of these elements is calleda face τ of σ, indicated by τ 6 σ. We call k the dimensionof a k-simplex. In the special case of Z2 coefficients as in[12], the ordering can in fact be ignored. A (finite) simplicial
complex K is a non-empty set of simplices such that if σ ∈ Kand τ 6 σ, then τ ∈ K and if σ, σ 0 ∈ K then σ ∩ σ 0 is empty
or an element of K. We write |K| for set of points in Rd
contained in the union of all simplices in K. The set |K| isa topological space with the subspace topology from Rd .
(Co-)HomologyPwith Coefficients in F: A p-chain c iska formal sum c = i=1 λi σi of p-simplices {σi }ki=1 ⊂ Kwith λi ∈ F and Cp (K) denotes the F-vector space ofall p-chains. In particular, for finite geometric complexes,
1-chains are finite linear combinations of edges and 2chains are linear combinations of triangles. We denote
by C p (K) = Hom(Cp (K), F) the vector space of linear
maps from Cp (K) to F. Elements of C p (K) are called pcochains. When no confusion arises, we write Cp , C p for
Cp (K), C p (K) to simplify notation. For every geometricp-simplex
Pp σ = [v0 , . . . , vp ] let ∂σ be the p − 1-chain∂σ = i=0 (−1)i [v0 , . . . , vi−1 , vi+1 , . . . , vp ]. For each p ∈{0, . . . , d}, ∂ extends to a linear map ∂ : Cp → Cp−1 ,called the boundary operator. The coboundary operator δ :C p−1 → C p is defined dually by δ(ω)(c) = ω(∂(c)), forω ∈ C p−1 and c ∈ Cp . A p-chain c such that c = ∂ω forsome ω ∈ Cp+1 is called a p-boundary. And a p-chain csuch that ∂c = 0 is called a p-cycle. Similarly, a p-cochainϕ ∈ C p such that ϕ = δη for some η ∈ C p−1 is called ap-coboundary and a p-cochain ϕ such that δϕ = 0 is calleda p-cocycle. The vector spaces of p-boundaries and p-cycles
are denoted Bp and Zp respectively and the vector spacesof p-cochains and p-cocycles are denoted by B p and Z p
respectively. The p-th homology group of K is defined by
Hp (K) = Zp /Bp and the p-th cohomology group is definedby H p (K) = Z p /B p . For a cycle c ∈ Zp (cocycle ϕ ∈ Z p ),we denote by [c] ∈ Hp ([ϕ] ∈ H p ) the resulting element inhomology (cohomology). In the special case of F = Z2 , wecan easily visualize 1-chains as a collection of edges in K
which have non-zero coefficients in the chain. Similarly, a
1-cochain corresponds to a function assigning 0 or 1 to eachedge, and we can visualize the 1-cochain by displaying those
1-simplices on which it takes the value 1. See Fig. 2 for an
example. Note that each p-cycle c yields an element in Hp ,but this representative is only unique up to elements in Bp .
Similarly, p-cocycles define elements of H p only up to B p .
The importance of homology and cohomology in mathematics arises from the fact that they capture global topological properties about the topological space defined by |K|.
In particular both homology and cohomology are invariant
under continuous deformations of the space |K| (homotopies
of |K|). The universal coefficient theorem [13] in fact assertsthat Hp and H p are dual as vector spaces for field coefficients. In particular, for finite simplicial complexes, bp =dim(Hp ) = dim(H p ) is called the pth Betti number andcounts the number of connected components (b0 ), tunnels(b1 ), and higher dimensional voids in K. The left part of
Fig. 2 illustrates an example 1-cycle c lying in a simplicial
complex K and forming a basis of H1 (K) which is in thiscase 1-dimensional and where we pick F = Z2 coefficients.
|K| is in fact homotopy equivalent to a circle. We display a 1cocycle ϕ in the right part of that figure. Over Z2 , 1-cocycles
correspond to ‘picket fences’ [14]. Here, dim(H1 (K)) =dim(H 1 (K)) = 1 and [c] ∈ H1 (K) and [ϕ] ∈ H 1 (K) forma basis respectively.
Filtrations: While homology and cohomology are classical concepts [13], we now review the more recent developments of persistent (co-)homology [15], [16], which havelead to very efficient algorithms which can now also be
used also for the computation of classical (co-)homology.
Persistent (co-)homology is concerned with (co-)homology
in a multiscale setting. One of the origins of persistenceis the study of the topology of sublevel (or superlevel)sets of a function f : X → R defined on a topologicalspace X. Each sublevel set Xr = f −1 ((−∞, r]) yields a
topological space Xr , where Xr ⊆ Xr0 whenever r 6 r0 . Asr increases, homological features can be ‘born’ and disappear
or ‘die’ as the threshold r increases. Persistence provides acomputational mechanism for understanding these changes.
To make this precise, we work with a filtration K of finite
simplicial complexes in Rd , by which we mean a sequenceK : K1 ⊂ K2 ⊂ . . . ⊂ Kn = K∞ of finite simplicial
complexes. Typically, each filtration index i is associated toa real valued filtration value r so that Ki = f −1 (−∞, r].
For example, we can assign an arbitrary real value to eachvertex of Kn . Then the function f (σ) = maxi∈{0,...,k} f (vi )for an arbitrary k-simplex σ = [v0 , . . . , vk ] ∈ Kn gives rise
to a filtration of simplicial complexes when its sublevel setsare considered. When Ki = f −1 ((−∞, r]) we call r thefiltration value associated to the filtration index i.
Delaunay-Čech complexes: To model configuration
spaces from a finite sample of collision-free points X ⊂Cf , weSshall consider the family of union of balls spaces
Xr = x∈X {y ∈ Rd : kx − yk 6 r}, for r > 0. For each r,
Xr is homotopy equivalent to the Delaunay-Čech complex
DCr (X) [17], which is a simplicial complex defined for any
finite set X ⊂ Rd where each subset of d+1 point is affinely
independent. This assumption is generic in that a uniform
random sample satisfies this condition with probability one
and we can also enforce the condition by an arbitrarily
small perturbation of X. Let D(X) denote the simplicial
complex corresponding to the Delaunay triangulation of X
with simplices defined by D(X) = {[v0 , . . . , vk ] : vi ∈X, ∩ki=0 Vvi 6= ∅ for k ∈ {0, 1, . . . , d}}, where Vx denotes
the Voronoi cell containing x. For each k-simplex
σ =Tk[v0 , . . . , vk ] ∈ D(X), define f (σ) = min{r : i=1 Br (vi ) 6=∅}, where Br (x) = {y ∈ Rd : kx − yk 6 r}. The DelaunayČech complex DCr (X), for r > 0 is the sub-complexof D(X) defined by DCr (X) = f −1 ((−∞, r]). Since
DCr (X) is homotopy equivalent to Xr , we can compute
topological information about Xr from DCr (X) at all scalesr > 0. In particular, we are interested in persistent homology
and cohomology.
Persistent (Co-)Homology: Applying homology andcohomology to a filtration of simplicial complexes, we
obtain a sequence of induced linear maps on homology andcohomology respectively:
Hp (K) : Hp (K1 ) → Hp (K2 ) → . . . → Hp (Kn )H p (K) : H p (K1 ) ← H p (K2 ) ← . . . ← H p (Kn )for each p ∈ {0, . . . , d} and where the maps on homology
are induced by inclusion and we denote fpi,j : Hp (Ki ) →Hp (Kj ) for i 6 j for the resulting compositions of maps.
The maps on cohomology are induced by restriction ofpcochains and we denote the resulting linear maps by gi,j:H p (Kj ) → H p (Ki ), for i 6 j. The p-th persistent homology
group for i 6 j is given by Hpi,j = imfpi,j , so that nontrivial elements in Hpi,j correspond to homology classes bornat or before index i and which survive until at least index
j. The difference j − i is called the index persistence ofsuch a class. For us, Ki = f −1 ((−∞, ri ]), and rj − riis the persistence of the class. In fact, all the persistenthomology groups can be computed by a decomposition of
the persistence module into interval modules [19]. The p-th
persistence diagram captures the information about the birthand death of p-th homology classes as the filtration value
increases. It consists of multisets of points in the extended

0.4

0.2

0
0

0.2

0.4

Fig. 3: Top row: A point-cloud X ⊂ [0, 1]2 and the 1st persistence
diagram of the Delaunay-Čech filtration DC(X) with a single significant
point (0.031, 0.303) far above the diagonal and corresponding to the largehole in the middle of the point-cloud. Middle row: a 1-cycle c (over Z2 )corresponding to the significant point and the complex at the filtration value
0.031 (left figure) when the cycle first corresponds to a non-trivial element[c] in homology, at 0.150 (middle) and at the death filtration value of 0.303(right) when the class [c] becomes trivial in homology. Bottom row: a 1cocycle ϕ (over Z2 ) dual to the previous 1-cycle at the same filtrationintervals. Note how in the middle row, c is included into the subsequent
complexes for higher filtration values, while in the bottom row, the cocycle
is a result of restricting the co-cycle to smaller and smaller complexes.
upper left quadrant. Each point (ri , rj ) in the diagram corresponds to a homology class born at index i and surviving
until index j. Points that lie far above the diagonal have alarge persistence and are hence considered important features
distinct from smaller scale features due to noise. An example
is presented in Fig. 3. Classes born at index i and which
do not die at the final filtration index n are called essential
and are associated to points of the form (ri , ∞) in the plane,
extended formally to (R∪{∞})2 . The persistent cohomologyppgroups can be defined analogously by Hi,j
= im gi,j. In
fact, persistent homology and cohomology are dual [19] withidentical persistence diagrams. To compute a basis for thepersistent (co-)homology groups, we first assume without
loss of generality that the filtration K hasSbeen refined toja simplex-wise filtration, where Kj =i=1 σi , so that
Kj+1 = Kj ∪ {σj+1 } and we hence add a single simplex
in each step of the filtration. Given such a simplex-wise
filtration, several algorithms (see e.g. [20]) are available tocompute a basis of the persistent (co-)homology groups. We
shall use the standard left-to-right reduction algorithm [20]adapted for cohomology as described in [19] for this purpose.
Fig. 3 illustrates an example of a filtration and an associated(co-)homology basis.

Fig. 4: Leftmost figure: A simple free configuration space Cf in the shape of an annulus and two paths in blue and black between the marked points.

Center-left: A covering space of Cf , where the z coordinate is given by the signed winding angle around the center of the annulus. The lifted black andblue paths now do not terminate in the same lifted coordinate and can hence be distinguished easily in the covering space. The covering space winds andextends infinitely far in both positive and negative z direction allowing us to classify trajectories between the two points in Cf . Center-right: Z2 covering
space of Cf . Here, the red horizontal line is ‘glued’ to the green line, so that a trajectory winding twice around the hole in the center in Cf returns to thesame z-coordinate also in the covering space. A figure similar to the left three plots appears in [18], where a generalization of these covering spaces isused for motion planning. Right: Example of our Z2 covering space which is built from noisy samples. It consists of 2 sheets of the simplicial complex
DCr (X) which are glued along the indicated cohomology generator ϕ: Whenever the red line or blue line is crossed, we jump to the other layer in the
covering space. Making two full rotations around the hole hence results in returning to the same z-coordinate layer as in the smooth Z2 -covering space tothe left. Unlike the previous approaches, the underlying covering space is generated fully from sampled data and we do not require a potentially imprecise
numerical floating point integration to determine the analogue of the winding angle along a trajectory. The one-skeleton of this covering space precisely
consists of the graph G(DCr (X), Φ), Φ = (ϕ).

III. M ETHODOLOGY
Definition 3.1: Consider simplicial homology and cohomology over a finite field F. We call a tuple (K, Φ), where K
is a simplicial complex, Φ = (ϕ1 , . . . , ϕk ), and ϕi ∈ Z 1 (K)are such that [ϕ1 ], . . . , [ϕk ] ∈ H 1 (K) are linearly independent, a cohomologically annotated simplicial complex. For
a 1-chain γ, we call Φ(γ) = (ϕ1 (γ), . . . , ϕk (γ)) ∈ Fk thesignature of γ (a discrete analogue of the signature of [21]).
The pairing induced by evaluation of 1-cochains on 1chains yields a duality between H1 (K) and H 1 (K) over field
coefficients. In particular, for c, c0 ∈ Z1 (K), Φ(c) 6= Φ(c0 )implies [c] 6= [c0 ] ∈ H1 (K), and if Φ = (ϕ1 , . . . , ϕk ) yields
a basis of H 1 (K), it is also true that, if Φ(c) = Φ(c0 ) then[c] = [c0 ] ∈ H1 (K).
Lemma 3.2: Let γ, γ 0 be oriented paths of 1-simplices
between 0-simplices, s, t ∈ K, so that ∂γ = t − s = ∂γ 0 and
let (K, Φ = (ϕ1 , . . . , ϕk )) be a cohomologically annotatedsimplicial complex. If Φ(γ) 6= Φ(γ 0 ) then γ, γ 0 are nothomotopy equivalent in |K|.
Proof: Suppose Φ(γ) 6= Φ(γ 0 ). Then there exists j ∈1, . . . , k such that ϕj (γ) − ϕj (γ 0 ) = ϕj (γ − γ 0 ) 6= 0, butthen [γ − γ 0 ] 6= 0 ∈ H1 (K), since otherwise γ − γ 0 = ∂cfor some c ∈ C2 (K), but then ϕj (∂c) = (δ(ϕj ))(c) = 0,
since ϕj ∈ Z 1 (K) which implies ϕj (γ) − ϕj (γ 0 ) = 0. Since
γ − γ 0 is non-trivial in H1 (K) it is non-trivial in π1 (K) (via
Hurewicz’ theorem [13]). Since γ−γ 0 is non-trivial in π1 (K),the paths γ and γ 0 are not homotopy equivalent.
Definition 3.3: Denote by K1 the 1-skeleton of a cohomologically annotated simplicial complex (K, Φ =(ϕ1 , . . . , ϕk ) with 0-simplex set V (vertices) and 1-simplex
set E (edges). We define the covering graph correspondingto (K, Φ) to be the finite directed graph G = G(K, Φ) withvertex set W = {w = (v, λ) ∈ V × Fk : v ∈ V, λ ∈ Fk } andwhere an edge is inserted from (v, λ) to (v 0 , λ0 ) precisely
when there exists a 1-simplex e = [v, v 0 ] ∈ E such that
Φ(e) = λ0 − λ. For a vertex w = (v, λ) ∈ G, we denote by
Gw the maximal connected component of G containing w.

Note that, for each arc a = ((v, λ), (v 0 , λ0 )) ∈ G, there exists
a corresponding edge π(a) = (v, v 0 ) in K1 , and we have thefollowing result:Corollary 3.4: Suppose there exist two sequences of directed arcs in G(K, Φ) from (v, 0) to (v 0 , λ1 ) and to (v 0 , λ2 )respectively such that λ1 6= λ2 . Then the corresponding
trajectories t1 , t2 formed by sequences of edges of K1 under
the projection π : G → K1 are homotopy inequivalent.
Proof: We have Φ(t1 ) = λ1 6= λ2 = Φ(t2 ) and theresult follows from the previous lemma.
The search for homotopy inequivalent trajectories (up tohomology) can hence be reformulated as a graph search for
trajectories in G(K, Φ). Note that, for F = Zp , we are able
to synthesize trajectories winding up to p − 1 times aroundany particular tunnel/void specified by each cohomology
generator. In the case of Z2 , which can be very efficiently
implemented, we can in particular detect whether we passa corresponding set of obstacles ‘to the left or to the right’in 2D as well as its more complex generalization to higher
dimensions.
Efficient Implicit Graph Representation and Search:Suppose that we are computing cohomology over the field
F = Zp with p elements, where p is a prime. The coveringgraph G(K, Φ), for Φ = (ϕ1 , . . . , ϕk ) and K with |V | vertices and |E| edges then has |V |pk vertices and significantly
more edges than K1 . These graphs quickly grow too large to
fit into memory as k and p is increased. Our approach will
hence be to run a graph search using an efficient implicit
encoding of the graph. For this, we create an augmented
graph H = H(K, Φ) as follows: H has a node for eachvertex in K1 and a directed edge (v, v 0 ) and (v 0 , v) for eachedge (v, v 0 ) in K1 . All arcs are stored in an array H.arcs
and vertices in an array H.vertices. Each arc a = (v, v 0 )stores the index of its target vertex v 0 in a.target. We store
the distance a.dist = kv − v 0 k and the index of the next
arc with the same source vertex a.next out which is set
to −1 if there are no further arcs. For each vertex v, weAlgorithm 1 Lifted Dijkstra
1: procedure L IFTED D IJKSTRA(H(K, Φ = (ϕ1 , . . . , ϕk )), source id)2:
N ← number of vertices(H)pk
3:d ← (∞, ..., ∞) ∈ (R ∪ {∞})N4:f ← (f alse, ..., f alse) ∈ ZN
2 // frontier vertices5:s ← (f alse, ..., f alse) ∈ ZN
2 // solved vertices
6:
Q.insert(0, lif t(source id, 0)) // priority queue
7:
f [lif t(source id, 0)] ← true
8:d[lif t(source id, 0)] ← 0
9:while Q is not empty do
10:u id ← Q.extract min()11:
s[u id] ← true12:
f [u id] ← f alse13:
arc id ← H.vertices[π1 (u id)].f irst out
14:
while arc id 6= −1 do
15:a ← H.arcs[arc id]
16:
w id ← lif t(a.target, π2 (u id) + a.mask)17:
if s[w id] = f alse then18:
dist ← d[u id] + a.dist
19:
if dist < d[w id] then20:
d[w id] ← dist21:
if !f [w id] then22:
Q.insert(dist, w id)
23:
f [w id] ← true24:
arc id ← a.next out
return dstore the index of the first outgoing arc as v.f irst out. We
furthermore store the value of the augmentation Φ(a) ∈ Zkp
for a directed arc a = (v, v 0 ) in the edge data structure byencoding Φ(a) = (m1 , . . . , mk ) ∈ Zkp as a single unsigned
Pk
integer a.mask using code(m1 , . . . , mk ) = i=1 mi pi−1 ∈{0, . . . , pk − 1}. In our implementation, p = 2 and we use
a 16 bit integer for a.mask, allowing for 0 6 k 6 16.
Note that H efficiently encodes all required information
to explore a connected component of the covering graph
G = G(K, Φ): If K1 has |V | vertices then H has the same
number of vertices while G has |V |pk vertices. Let us denotethe vertices of H by v0 , . . . , v|V |−1 and the vertices of G by
w0 , . . . , w|V |pk −1 , where we identify the vertex (vi , λ) in
G with wlif t(i,λ) , where lif t(i, λ) = i + |V |code(λ). For
j ∈ {0, . . . , |V |pk − 1}, we define π1 (j) = j mod |V | ∈{0, . . . , |V |−1} and π2 (j) = code−1 (bj/|V |c)) ∈ Zkp . Then,if wj = (vi , λ), we have π1 (j) = i and π2 (j) = λ. Using
this encoding, the outgoing edges from (vi , λ) ∈ G are
precisely of the form (vj , λ + a.mask), where a = (vi , vj )is an edge in H and we hence only need to store H inmemory. Alg. 1 summarizes how this data structure can beused to perform Dijkstra’s algorithm on G using H. We
found that it was most efficient to use two boolean vectors
f, s ∈ Zn2 to keep track of the frontier and finalized vertex
set in Dijkstra’s algorithm. We also only fill the priority
queue Q (implemented using the sequence heap of [22]),containing vertices ordered by distance to the source vertex
vsource id , during the execution of the algorithm insteadof filling the queue at the initialization step. We observethat d, f, s still require O(|V |pk ) memory, as does Q in
the worst case. However, the constants are small and our
representation of G by means of H significantly reduces thememory overhead of storing the underlying graph G. Whenthe algorithm terminates, each vertex wj ∈ G reachable

from wlif t(source id,0) ∈ G satisfies d[j] 6= ∞ and d[j]then denotes the distance of the shortest path between these
vertices. We can then recover the shortest path in the usual
manner recursively from the vector of distances d. Note thata similar approach is clearly also applicable to algorithms
such as A* which we shall investigate in future work.
Summary of our approach: As outlined in Fig. 1, ourmotion planning approach consists of several steps: Givena point-cloud dataset X ⊂ Cf , we construct a filtration
K representing our data at all scales. In our experiments,
this is done by considering filtrations such as DCr (X),and filtrations arising from sub- and superlevel sets of afunction on X. We compute the persistent cohomology
cocycle generators for the filtration and determine a fixedfiltration paramter r resulting in a complex Kr in K. The
choice of r can be constrained by prior information about
X, e.g. by imposing constraints on the Betti numbers, suchas requiring that Kr contains a single connected component,
or by picking r, e.g. to fall in the mid-point of the lifetime of
the most persistent 1-cohomology generator (see also [23]).
While persistent cohomology and homology are abstractly
isomorphic, we require cohomology here since we utilize
a basis of 1-cocycles, which intuitively form fences in theconfiguration space, enabling us to distinguish how tunnels
in Cf are traversed by ‘counting fence intersections’ via thesignature Φ which is constructed by selecting a subset ofthese 1-cocyles to apply our cohomological graph annotationand motion planning. The choice of subset determines which
tunnels in Cf should be considered for topological motion
planning and a choice of the k most persistent 1-cocycles
alive at a filtration value allows us to consider only the kmost important obstacles/voids at a given scale.
Technical differences and relationship with previous
works: The graph G(K, Φ) proposed in our work forms
a discrete analogue of the covering space considered for
topological motion planning in [8], [9], [10]. These covering
spaces arose by annotating a trajectory’s coordinates with a
Rk valued integral of a collection of differential 1-forms.
In 2D, this corresponded to annotating these trajectories
by winding angles with respect to a collection of specified
points interior to obstacles. Fig. 4 illustrates this idea. A
similar illustration can also be found in the recent work[18], which used these winding coordinates modulo a primep, corresponding to quotienting the spiral in Fig. 4 after pfull rotations and gluing the ends together. Our approach isrelated to this idea since our finite field graph annotation
approach also corresponds to a similar quotienting (Fig. 4),
but is discrete (F) and data-driven in nature. The right partof Fig. 4 contrasts our approach to [18] in the case of Z2
coefficients. A key difference to these previous works isthat our approach does not require a numerical integration
but utilizes a F-valued signature instead which leads to anincreased efficiency. Furthermore, our approach does not require a procedure to skeletonize obstacles, resulting in novel
application domains such as a first example of topologicalmotion planning for a multijoint robot. Our implicit graphrepresentation in Alg. 1 constitutes a further difference and,

unlike in previous work, we can apply our approach both in
the case where Cf is densely sampled and in a scenario where
we are only given a sparse sample, e.g. from a collection ofcollision free trajectories. Unlike the works [8], [9], [10],[18], we introduce a persistent cohomology-based approachwith several types of filtrations.
IV. E XPERIMENTAL E VALUATION
Delaunay-Čech Filtrations in 2D: In our first experiment, we consider sufficiently dense sets of uniformly
sampled collision free points X ⊂ Cf ⊂ R2 , so that
Cf ' Xr for some r > 0. Here, Cf is constructed by
selecting random subsets of K of the obstacles displayedin the top left of Fig. 5. If we know a priori what someof the Betti numbers of Cf are (e.g. number of connectedcomponents and number of obstacles), we can compute thepersistence diagram and choose r to lie e.g. in the middleof the largest filtration interval satisfying these constraints[23]. If no prior information is available, one can choose r
to lie in a large interval in which the Betti numbers remain
constant. Real world information about sensor range can also
be taken into account to further constrain the choice of r.
To evaluate the performance of the proposed algorithm, we
sample between N = 10000 and one million collision freepoints lying at least at distance 0.01 from any of the obstaclesin the environment. This guarantees that for filtration valuesof r < 0.01 all edges in the skeleton of DCr (X) arethemselves collision free. The top left of Fig. 5 illustrates
a case where r = 0.03 > 0.01. In our experiments, we pick1
a filtration of r = 3N − 2 which empirically ensured thatthe resulting complex DCr (X) was connected and had thecorrect number of ‘holes’ corresponding to each obstacle.
Furthermore, we then have r < 0.01 for N > 90000,
guaranteeing global collision free solution trajectories in our
experiments for sufficiently large sample sizes. The bottom
part of the figure displays 64 overlaid solution trajectories
and the first persistence diagram for a world with 6 obstacles.
In Fig.6, we break down the computation times for N
between 10000 and 100000. We observe that, as the graphsize grows quickly with the number of obstacles, the graphsearch begins to dominate the total computation time fora large number of obstacles. Table II summarizes the total
computation times as the number of samples and the numberof obstacles varies. For each sample size less than 500000,
we repeat the experiment 10 times (with random subsets of k
obstacles) and report mean computation times and standard
deviations. The table shows that our approach is very fast
for small numbers of obstacles. Note also that Dijkstra’salgorithm computes the full distance vector using which any
trajectory from the source vertex to any other target vertex
and topological class can then be obtained (in less than 0.5s
for any query destination and sample size). Furthermore, foreach fixed source and target vertex, we find 2k topologicallydistinct solution trajectories when our world has k obstacles
and for 1 million samples and 10 obstacles and a given
source vertex, Dijksta’s algorithm returns information about
1.024 billion solution trajectories as stored in the returned

1

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

0
0

0.2

0.4

0.6

0.8

1

1

0

0.2

0.4

0.6

0.8

1

0.1

0.8

0.6

0.4

0.2

0

0
0

0.2

0.4

0.6

0.8

1

0

0.1

Fig. 5: Random subsets of the obstacles displayed in the top left (in black)are used in our experiments and we generate uniform random samples
in the domain [0, 1]2 ⊂ R2 which are at least of distance 0.01 fromeach obstacle (outside the gray region). Initial and terminal positions areindicated as green and red points respectively. In the top right, we illustrate
an example set of two solution paths in the case of a single obstacle, with
10000 samples (in green) and with a filtration value of 0.03. Note that, since
0.03 > 0.01, DC0.03 (X) can have edges that connect two collision freesamples, but which are not themselves entirely collision free as illustrated
in the top right part of this subfigure. For smaller filtration values, as in thebottom left, where we used 100000 samples and r = 0.0095, all edges areguaranteed to be collision free. 64 = 26 homotopy inequivalent trajectories
are shown overlayed onto each other. The bottom right diagram illustrates
the associated first persistence diagram. The six points in the dashed region
correspond to the obstacles and the dashed lines intersect at (r, r).

Fig. 6: Computation times (in s, vertical axis) for 2D experiments

are broken into components: black: Delaunay triangulation computationin CGAL [24] and computation of the Delaunay-Čech filtration, blue:
Computation of the persistent cohomology H 1 generators, green: graphconstruction and Dijkstra’s algorithm. Each group of bars illustrates thetime required (in seconds) for 0, 3, and 6 obstacles (left to right). The
numbers of samples in thousands are shown along the horizontal axis.

distance vector in less than 12 minutes, and with 210 = 1024
homotopy inequivalent trajectories per source/target vertex
pair. This in particular differs from the work in [11], wherea smaller set of homotopy inequivalent trajectories (up to 10)
was discovered incrementally in an unbounded search space.
PR2 Arm Motions: In this experiment, we simulate a
PR2 robot using OpenRave [25]. The robot is placed next
to a vertical bar obstacle as shown in red in Fig. 7 andwe keep all but the 4 major arm joints of the left arm
fixed. Our task is to determine trajectories of the left arm
between the indicated initial and final configurations. For
this purpose, we uniformly sampled 200000 collision free
joint-configurations of the PR2’s left arm. This results in aSamples Filtration

Number of obstacles

DC∞(X)
Edges

Triangles

10000
20000
30000
40000
50000
60000
70000
80000
90000
1000000.03000.02120.01730.01500.01340.01220.01130.01060.01000.009529971.98 ± 3.49
59970.50 ± 3.38
89969.42 ± 3.63
119968.88 ± 3.53
149968.55 ± 3.64
179967.89 ± 3.57
209967.09 ± 3.60
239966.45 ± 3.60
269966.75 ± 3.79
299966.78 ± 3.46

19972.98 ± 3.49
39971.50 ± 3.38
59970.42 ± 3.63
79969.88 ± 3.53
99969.55 ± 3.64
119968.89 ± 3.57
139968.09 ± 3.60
159967.45 ± 3.60
179967.75 ± 3.79
199967.78 ± 3.46

5000001000000

0.00420.00301499960.55 ± 4.85 999961.55 ± 4.85
2999963.00 ± 4.26 1999964.00 ± 4.26

00.1297 ± 0.0018
0.2769 ± 0.0148
0.4286 ± 0.0298
0.5545 ± 0.0098
0.7559 ± 0.0082
0.9425 ± 0.0091
1.1292 ± 0.0204
1.3227 ± 0.0187
1.5387 ± 0.0514
1.7163 ± 0.0190

1
0.1311 ± 0.0014
0.2857 ± 0.0059
0.4530 ± 0.0032
0.5581 ± 0.0049
0.7676 ± 0.0116
0.9490 ± 0.0133
1.1448 ± 0.0136
1.3321 ± 0.0243
1.5475 ± 0.0344
1.7443 ± 0.0333

2
0.1352 ± 0.0020
0.2956 ± 0.0048
0.4673 ± 0.0074
0.5747 ± 0.0054
0.7827 ± 0.0113
0.9805 ± 0.0125
1.1756 ± 0.0176
1.3800 ± 0.0159
1.5833 ± 0.0197
1.7917 ± 0.0232

3
0.1427 ± 0.0014
0.3133 ± 0.0064
0.4954 ± 0.0072
0.6111 ± 0.0081
0.8315 ± 0.0125
1.0299 ± 0.0205
1.2429 ± 0.0272
1.4470 ± 0.0235
1.6919 ± 0.0165
1.9048 ± 0.0350

40.1603 ± 0.0020
0.3539 ± 0.0062
0.5518 ± 0.0227
0.6833 ± 0.0070
0.9315 ± 0.0119
1.1488 ± 0.0113
1.3777 ± 0.0187
1.6081 ± 0.0156
1.8799 ± 0.0164
2.1205 ± 0.0113

50.1978 ± 0.0022
0.4351 ± 0.0065
0.6034 ± 0.0060
0.8380 ± 0.0098
1.1254 ± 0.0094
1.3957 ± 0.0229
1.6838 ± 0.0227
1.9603 ± 0.0153
2.2838 ± 0.0156
2.5949 ± 0.0148

6
0.2786 ± 0.0028
0.5647 ± 0.0356
0.8364 ± 0.0057
1.1396 ± 0.0161
1.5342 ± 0.0098
1.8948 ± 0.0145
2.2823 ± 0.0172
2.6818 ± 0.0278
3.1904 ± 0.0317
3.6863 ± 0.0306

11.2779
25.1642

11.566225.4774

12.199326.427713.011128.7711

14.4668
32.368918.2660
40.2058

26.4173
58.0553780.4395 ± 0.0026 0.6848 ± 0.0250
0.8391 ± 0.0070 1.4587 ± 0.0108
1.3104 ± 0.0170 2.2778 ± 0.0169
1.7841 ± 0.0207 3.1182 ± 0.0564
2.3750 ± 0.0192 4.2110 ± 0.0396
2.9609 ± 0.0153 5.3004 ± 0.0548
3.6670 ± 0.0324 6.6847 ± 0.1007
4.3383 ± 0.0385 8.0440 ± 0.1235
5.2207 ± 0.0629 9.7655 ± 0.1574
6.0790 ± 0.0795 11.3504 ± 0.1101

44.8978
98.776785.7563181.7561

9
1.2819 ± 0.0036
2.7556 ± 0.0198
4.3247 ± 0.0383
6.0961 ± 0.1002
8.3736 ± 0.1390
10.6218 ± 0.1129
13.3552 ± 0.0845
16.1658 ± 0.1101
19.5922 ± 0.1564
22.8980 ± 0.2842

10
2.5497 ± 0.0129
5.5616 ± 0.0425
8.8125 ± 0.0802
12.5567 ± 0.1999
17.2210 ± 0.1442
22.3609 ± 0.2281
28.2221 ± 0.2014
33.6077 ± 0.3051
40.1525 ± 0.2844
46.5861 ± 0.3633

160.3689
361.8256

329.8708
696.8684

TABLE II: Summary of 2-dimensional topological motion planning experiments. We report the total time (in seconds) required to compute all data

structures, persistent homology and to execute the lifted Dijkstra algorithm for a fixed source vertex. For up to 100000 samples, each experimental setting
is repeated 10 times with a random subset of k obstacles. For larger sample sizes, we report timing results of a single trial. Edge and triangle numbers areaveraged over all trials and number of obstacle settings. We also report standard deviations where applicable.

simplicial 2-skeleton (we do not require higher dimensional
simplices to compute H 1 ) filtration with 3675821 edges and12703304 triangles in 4 dimensions which models the space
Xr of unions of balls of radius r around the samples at all
scales r > 0. Note that the resulting data structure yields ahighly detailed model of the 4 dimensional free configuration
space. The computation of the Delaunay triangulation took
37.6s, the 2-skeleton extraction 32.2s and the DelaunayČech filtration computation took 8.38s. The resulting first
persistence diagram is displayed in the top left part of Fig.7
and was computed in 159.8s. We can clearly see the redpoint indicating a particularly large persistence interval. At
filtration r = 0.11, the simplicial complex is path-connected
and H 1 (DCr (X)) has dimension 4716 (equal to the numberof points in the top right area bordered by the dashed lines
intersecting at (r, r)). We chose the cohomology generator
corresponding to the red most persistent interval among
these as our cohomological annotation and computed shortest
trajectories between the indicated initial and terminal arm
configuration. The graph construction and search took 2.1s.
We find two topologically inequivalent shortest paths illustrated in the second and third row of the figure respectively.
The difference between these trajectories can be observed byconsidering the second picture in each column. The PR2’sleft upper arm is lowered in the first trajectory to pass
the obstacle while the upper arm is extended upwards inthe second solution trajectory. These two trajectories areclearly not homotopy equivalent – continuously deforming
one into the other would require a horizontal posture of theupper arm resulting in a collision with the red obstacle.
The selected large persistence interval corresponds to a
cohomology class which is generated by a thick tunnel/void
in the 4D configuration space corresponding to collisionsof the PR2’s left elbow with the obstacle. The chosen 1cocycle yields a ‘fence’ which is pierced by the first solution
trajectory but not by the second. While this example may
be considered simple, no previously known method is – tothe best of our knowledge – currently able to synthesize
such types of homotopy-inequivalent solution trajectories in
an automated sampling-driven manner. Our method hence
makes available a new wealth of trajectory classes. In caseone of the trajectories becomes obstructed due to changing
environment conditions, the robot could for example fallback to the previously computed second trajectory solution.

0.5

0
0

0.5

Fig. 7: Top-left: first persistence diagram for Delaunay-Čech filtration of
200000 uniform collision free joint-configuration samples X of the left arm
in R4 . At selected filtration value of r = 0.11, DCr (X) has one connectedcomponent and dim(H 1 (DCr (X))) = 4716 (number of points in theupper left dashed region), with a persistence interval with particularly large
persistence marked in red.

Note also that any continuous optimization of a trajectory ineach homotopy class will have to remain within its initialhomotopy class. Our trajectory solutions can hence be used
to provide initializations to optimizers such as CHOMP [26].
Trajectory datasets: Here, we study applications of
our approach in the case where we are given point-clouds
consisting of real-world trajectories. Unlike before, such a
point-cloud X does not necessarily represent a dense sample
of Cf . Instead, the intrinsic shape of Xr gives rise to holes
which might be due to obstacles or parts of space not coveredby X.
Racecar dataset: The first trajectory dataset consistsof 3324 GPS data points X ⊂ R2 of a racecar driving
around a racetrack [27] and is displayed in the top leftof Fig. 8, with its first persistence diagram displayed to

150
40

0.4

100
20
0.2

50

0

0
0

50

100

150

0

20

40
0
0

150

150

100

100

50

50

0

0.2

0.4

0
0

50

100

150

0

50

100

150

Fig. 8: Top: Racecar GPS point-cloud and first persistence diagram withr = 3.276 marked by dashed lines. Bottom left: DCr (R) and overlaid
found shortest paths at r = 3.276. Bottom right: a solution trajectory forr = 4.0.

the right. By investigating the 0th persistence diagram, wefind that Xr ' DCr (X) is connected for r > 2.26. For
r = 3.276, dim(H 1 (Xr )) = 1 and we obtain the graysimplicial complex in the bottom left. We find two solution
trajectories (in red and black) between the indicated points
which generalize the recorded trajectories (all computed inless than 0.5s). When we increase the filtration value to r =4, dim(H 1 (Xr )) = 2 and we obtain 4 solution trajectories.
An example such trajectory is displayed in the bottom rightof the figure. Note how this trajectory represents a reasonable
solution generalizing the recorded trajectory behavior if weallow ourselves to trust that samples of distance less than orequal to 4 will be path-connected in Cf .
Motion capture dataset: We recorded the set of 3D
trajectories displayed in Fig. 9 using a Nest of Birds motion
capture rig. The trajectory set consists of two motion primitives displayed in blue and red respectively and contains
8998 data-points X ⊂ R3 . In this experiment, we illustrate
how our topological motion planning approach enables us
to synthesize new motions which combine the behaviorof these two classes. The two voids in this data-set areclearly visible as two points with large persistence in thefirst persistence diagram in the top right of Fig. 9. The
dashed lines intersect at (0.085, 0.085). We computed thecorresponding 4 homotopy inequivalent solution trajectories
displayed in the bottom left of the figure (total computationtime: less than 6s). Note that the yellow and blue trajectories
correspond to an optimized shortest path in the red and blue
motion primitive respectively. Additionally, we are able torecover novel motion behavior mixing the two primitives as
indicated by the red and black trajectory which traverse both
voids either to the left or to the right. We believe that an
investigation of our approach together with large motion capture/gesture databases might be of interest, especially sinceDCr (X) and persistent cohomology generators can in thatcase be computed offline, reducing the online computation

Fig. 9: Top left: 3D motion capture data of two motion primitives. Topright: associated first persistence diagram with marked filtration value r =0.085. Bottom left: Four shortest homotopy inequivalent solution trajectories
at this filtration value are displayed on top of the gray data points. Bottom
right: A cost function defined by the distance to the blue threat/obstacle
yields a sub-filtration with only two solution trajectories at r = 0.78.

cost of synthesizing new trajectories to just graph-search.
The bottom right part of Fig. 9 illustrates how a costfunction can be combined with our approach (see also [12]).
Observing that, for r = 0.085, DCr (X) provides a goodmodel for our point-cloud, consider now the emergenceof an agent indicated by the blue dot in the figure. To
adapt our trajectory planning approach, we can define a costfunction c : R3 → R, e.g. by c(x) = exp(−d(a, x)2 ) anda new filtration Fr of the complex DCr (X) where a ksimplex [v0 , . . . , vk ] has filtration value maxi∈0,...,k c(vi ).
For r = 0.78, Fr does not contain any simplex involving
any of the black vertices, allowing for only the two indicatedsolution trajectories, while for large filtrations, we recover all
the solutions shown in the bottom left. We believe that theinvestigation of such data-driven sub-filtrations expressing
multiscale constraints arising from cost, likelihood and navigability functions provides an interesting direction for future
work.
V. C ONCLUSION
In this work, we have introduced the use of persistentcohomology with finite field coefficients as a tool for datadriven homotopy-aware motion planning. Our experiments
show that our technique can be used with large sample
sizes in low dimensions and we have demonstrated that
we can plan topologically distinct trajectories in application
domains in which topological motion planning techniques
were previously not applicable. In future work, we intend toinvestigate the combination of our methods with probabilistic
and cost based filtrations as well as the use of alternatives
to the underlying Delaunay-Čech complexes.

R EFERENCES[1] S. Thrun, W. Burgard, and D. Fox, “Probabilistic robotics,” 2005.
[2] S. M. LaValle and J. J. Kuffner, “Rapidly-Exploring Random Trees:
Progress and Prospects,” in Algorithmic and Computational Robotics:
New Directions, B. R. Donald, K. M. Lynch, and D. Rus, Eds.
Wellesley, MA: A K Peters, 2001, pp. 293–308.
[3] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration
spaces,” IEEE Trans. on Robotics and Automation, vol. 12, no. 4, pp.
566–580, 1996.
[4] J. T. Schwartz and M. Sharir, “On the piano movers problem. II. General techniques for computing topological properties of real algebraic
manifolds,” Advances in Applied Mathematics, vol. 4, no. 3, pp. 298–
351, 1983.
[5] J. Canny, The complexity of robot motion planning. MIT press, 1988.
[6] J.-C. Latombe, Robot Motion Planning. Springer, 1991.
[7] S. Bhattacharya, V. Kumar, and M. Likhachev, “Search-based path
planning with homotopy class constraints,” in Proc. of The TwentyFourth AAAI Conf. on Artificial Intelligence, 11-15 July 2010.
[8] S. Kim, K. Sreenath, S. Bhattacharya, and V. Kumar, “Optimal
trajectory generation under homology class constraints,” in 51st IEEE
Conf. on Decision and Control, 10-13 Dec 2012.
[9] S. Bhattacharya, M. Likhachev, and V. Kumar, “Identification andrepresentation of homotopy classes of trajectories for search-based
path planning in 3D,” in Proc. of Robotics: Science and Systems, 2730 June 2011.
[10] S. Bhattacharya, D. Lipsky, R. Ghrist, and V. Kumar, “Invariants forhomology classes with application to optimal search and planningproblem in robotics,” Annals of Mathematics and Artificial Intelligence(AMAI), April 2013.
[11] S. Bhattacharya, M. Likhachev, and V. Kumar, “Topological constraints in search-based robot path planning,” Autonomous Robots,vol. 33, no. 3, pp. 273–290, October 2012.
[12] F. T. Pokorny, M. Hawasly, and S. Ramamoorthy, “Multiscale topological trajectory classification with persistent homology,” in Proceedingsof Robotics: Science and Systems, July 2014.
[13] A. Hatcher, Algebraic topology. Cambridge University Press, 2002.

[14] H. Edelsbrunner and J. L. Harer, Computational topology: an introduction. AMS Bookstore, 2010.
[15] H. Edelsbrunner and J. Harer, “Persistent homology-a survey,” Contemporary mathematics, vol. 453, pp. 257–282, 2008.
[16] G. Carlsson, “Topology and data,” Bull. Amer. Math. Soc. (N.S.),
vol. 46, no. 2, pp. 255–308, 2009.
[17] U. Bauer and H. Edelsbrunner, “The Morse theory of Čech andDelaunay filtrations,” in Proc. of the Thirtieth Annual Symp. on Comp.
Geometry, ser. SOCG’14. New York, NY, USA: ACM, 2014, pp.
484:484–484:490.
[18] S. Bhattacharya, R. Ghrist, and V. Kumar, “Persistent homology forpath planning in uncertain environments,” Preprint, June 2014.
[19] V. De Silva, D. Morozov, and M. Vejdemo-Johansson, “Dualities
in persistent (co) homology,” Inverse Problems, vol. 27, no. 12, p.
124003, 2011.
[20] U. Bauer, M. Kerber, and J. Reininghaus, “PHAT (Persistent Homology Algorithm Toolbox),” http://code.google.com/p/phat/.
[21] S. Bhattacharya, M. Likhachev, and V. Kumar, “Topological constraints in search-based robot path planning,” Autonomous Robots,vol. 33, no. 3, pp. 273–290, October 2012, dOI: 10.1007/s10514-0129304-1.
[22] P. Sanders, “Fast priority queues for cached memory,” ACM Journalof Experimental Algorithmics, vol. 5, pp. 312–327, 1999.
[23] F. T. Pokorny, C. H. Ek, H. Kjellström, and D. Kragic, “Persistenthomology for learning densities with bounded support,” in Advancesin Neural Information Processing Systems 25, P. Bartlett, F. Pereira,C. Burges, L. Bottou, and K. Weinberger, Eds., 2012, pp. 1826–1834.
[24] “C GAL,
Computational
Geometry
Algorithms
Library,”
http://www.cgal.org.
[25] R. Diankov and J. Kuffner, “OpenRAVE: A Planning Architecture forAutonomous Robotics,” Robotics Institute, Pittsburgh, PA, Tech. Rep.
CMU-RI-TR-08-34, Jul. 2008.
[26] N. Ratliff, M. Zucker, J. A. Bagnell, and S. Srinivasa, “Chomp: Gradient optimization techniques for efficient motion planning,” in Robotics
and Automation, 2009. ICRA’09. IEEE International Conference on.
IEEE, 2009, pp. 489–494.
[27] KTH Racing, Formula Student Team, KTH Royal Institute of Technology, Stockholm, Sweden, 2012.