Navigation Graph. Our method could be used with discrete information received from a people tracker, however, it is equally well suited for use on general occupancy grids. In our case the input scenario is given as a collection of discrete people poses, (x, y, θ), in the 2D workspace, see Fig.2 (left). To frame the motion planning task as a graph search problem, we build the navigation graph G of the scenario from the Voronoi diagram VD, gen- erated considering as obstacles also the people poses, see Fig.2 (middle). We create two additional vertices for the initial robot position and goal position, and connect them to the closest point of the Voronoi diagram, see Fig.2 (right). In the navigation graph, built in this way, different paths from the initial robot position to the goal position belong to different homotopy classes. — ∈ ≤ The graph G(V,E) consists of a set of nodes (or vertices) V and a set of edges E. In this work, N is the number of nodes in the graph and M the number of edges. We associate to each edge eij, connecting the node vj to its neighbor vi, an attribute or cost cij. E(vj) denotes the set of incoming and outgoing edges of vj. We compute the set of homotopy classes by running our random walk based algorithm on G. A walk w of length k 1 in a graph is a sequence of nodes v1, v2, . . . , vk, where each pair of nodes is connected by an edge, (vi−1, vi) E for 1 < i k . The adjacency matrix A of G expresses the topology of the graph and is defined as [A]ij = 1 if (vi, vj) ∈ E, i /= j ( 0 otherwise classes in a Voronoi diagram; Walks are usually referred to as paths.
