This talk outlines recent creations and implementations of Laplacians for distributed systems.

Cellular sheaves are a mathematical structure specifying consistency relations for data associated to vertices and edges of a graph, generalizing connection graphs and matrix weighted graphs. We consider the problem of learning such a sheaf from a collection of highly consistent or smooth signals associated to the vertices of the underlying graph.

We address the fundamental problem of goal-directed path planning in an uncertain environment represented as a probability (of occupancy) map. Most methods generally use a threshold to reduce the grayscale map to a binary map before applying off-the-shelf techniques to find the best path. This raises the somewhat ill-posed question, what is the right (optimal) value to threshold the map? We instead suggest a persistent homology approach to the problem-a topological approach in which we seek the homology class of trajectories that is most persistent for the given probability map. In other words, we want the class of trajectories that is free of obstacles over the largest range of threshold values. In order to make this problem tractable, we use homology in ℤ2coefficients (instead of the standard ℤ coefficients), and describe how graph search-based algorithms can be used to find trajectories in different homology classes. Our simulation results demonstrate the efficiency and practical applicability of the algorithm proposed in this paper.paper.

In this paper we consider a probabilistic model of a pursuit-evasion game on Rn, in which neither pursuer nor evader positions are known with certainty. Both parties are represented by normal distributions that evolve according to a Kalman filter as new sensor readings (observation from overhead camera/satellite images) are obtained. The objective is to design the control commands issued by the pursuer (which is executed noisily). The control commands issued by the evader are unknown - only sensor measurements are given. Even with such limited knowledge we prove boundedness of a distance between the pursuer's distribution and the evader's true distribution (one that takes into account the evader's control commands). Our simulation results support the claimed guarantees.

In this paper, we consider a multi-phased, minimalistic approach to mobile robot localization that constrains the robot's ability to sense its environment to a binary detection of uniquely identifiable landmarks having unknown position (e.g., a WiFi transceiver detecting network SSIDs). Central to the proposed solution are dual landmark and observation complexes (instances of simplicial nerve complexes), which can be iteratively built through local observations without any metric or time-sequenced information. We have shown that these complexes approximate the topology of the underlying physical environment. Specifically, the notion of a “hole” (i.e., a topological invariant) within these complexes naturally represents a physical structure (e.g., a building) that limits landmark visibility/communication with respect to the robot's location. Taking advantage of this property, we formulate a homological sensing model that operates on these constructs enabling the robot to “count” the number of structures in its vicinity using local homology computations as a pseudo-metric surrogate sensor. Our homological sensor is highlighted in the context of a Monte-Carlo localization algorithm that resolves robot location by correlating the measured number of topological invariants with an unlabeled, metric map location.

We present the mathematical framework and algorithms for multi-robot topological exploration of unknown environments in which the main goal is to identify the different topological classes of trajectories and thus efficiently distribute the task of exploration among different groups of robots. We consider two-dimensional configuration spaces. At any point in time, the robots' map consists of known, partially-mapped obstacles. The unknown, yet-to-be-explored area is mapped to a single point, thus giving us a quotient space. The topological classes on the quotient space allows us to define topological classes of trajectories connecting a robot pose to the unknown region in the original configuration space. Robots explore this configuration space choosing different homology classes when confronted by obstacles or walls. We illustrate the basic idea with simulations of small teams of robots. Experiments with a single robot illustrate the applicability of the method to robots that have small sensor footprints and limited computational resources. We also provide comparisons with a standard frontier-based algorithm.

Following Baryshnikov-Coffman-Kwak [1], we use network cyclic cellular automata to generate a decentralized protocol, with only a small fraction of sensors awake. The work here shows that waves of awake-state nodes turn corners and automatically solve pusuit/evasion-type problems without centralized coordination.

This paper defines and analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. The robot has no global sensors that would allow precise mapping or localization. Special information spaces are introduced for this particular model. Using these, strategies are presented to solve several tasks: 1) counting vertices, 2) computing the path winding number, 3) learning a combinatorial map, which is called the cut ordering, that encodes partial geometric information, and 4) solving pursuit-evasion problems.

We consider coverage problems in sensor networks of stationary nodes with minimal geometric data. In particular, there are no coordinates and no localization of nodes. We introduce a new technique for detecting holes in coverage by means of homology, an algebraic topological invariant. The impetus for these techniques is a completion of network communication graphs to two types of simplicial complexes: the nerve complex and the Rips complex. The former gives information about coverage intersection of individual sensor nodes, and is very difficult to compute. The latter captures connectivity in terms of inter-node communication: it is easy to compute but does not in itself yield coverage data. We obtain coverage data by using persistence of homology classes for Rips complexes. These homological invariants are computable: we provide simulation results.

In this paper we define a class of graph grammars that can be used to model and direct distributed robotic assembly or formation forming processes. We focus on the problem of synthesizing a grammar so that it generates a given, prespecified assembly. In particular, to generate an acyclic graph we synthesize a binary grammar (rules involve at most two parts), and for a general graph we synthesize a ternary grammar (rules involve at most three parts). We then show a general result that implies that no binary grammar can generate a unique stable assembly. We conclude the paper with a discussion of how graph grammars can be used to direct the synthesis of parts floating in a fluid or for self-motive robotic parts.