Jason Derenick

Initial sensor topology (i.e. Cech Complex) for a team of 58 robots on the plane.

Cycles bounding topological holes are identified and weighted simplices are introduced among 2--hop neighbors to facilitate coverage repair

Hole-free sensor topology generated by the proposed algorithm.

The sensor coverage problem is among the most fundamental coordination problems involving multi-agent systems. In recent years, the robotics and wireless sensor network communities have begun exploring the utility of algebraic topology for providing a solution. Algebraic topology is especially attractive since it provides a mathematical toolkit for taxonimizing topological spaces without any need for metric information (e.g. GPS, relative localization, relative pose estimates, etc.). It has already been applied to wireless sensor networks yielding impressive algorithms which afford metric-free coverage verification and even hole "localization". Such approaches have only recently emerged, and, as a result, they have almost exclusively been focused upon static network topologies. However, the question still remains: "How can algebraic topology and its constructs be utilized for the control and coordination of mobile robot teams?"

In this research, the first steps are taken towards addressing this question by coupling abstract simplicial complexes with relative metric information (in this case, relative pose estimates) to facilitate combinatorial control. Specifically, we consider what may be called the coverage-repair problem and formulate a greedy, distributed, discrete-continuous algorithm for repairing coverage holes in the sensor topology. Intuitively, agents postulate in an abstract topological space to generate a desired simplicial complex (i.e. the Cech complex) that is ultimately used to govern team behavior via novel simplicial control laws. In contrast to traditional agent-based controllers, the role of a simplicial control policy is to implicitly control agents by explicitly controlling the higher-dimensional simplices they comprise. In our initial results, we consider position-based simplicial control and meld it with recent results for metric-free coverage verification and hole-localization to yield our algorithm. The figures illustrate an application of our distributed algorithm to repair two coverage holes in a team of 58 robots operating on the plane.

Little Ben utilized a large sensor suite including a GPS/INS system for pose, along with LIDARs and a stereo camera head for perception.

Ben safely navigates on NQE Area A. He ultimately qualified early for the final event, receiving the fourth poll position.

Ben crosses the finish line, completing the DARPA Urban Challenge. He was one of only six robots to complete the 55 mile race.

The University of Pennsylvania, Lehigh University and ATL @ Lockheed Martin recently joined forces, forming the Ben Franklin Racing Team and submitted an entry to the 2007 DARPA Urban Challenge. Our vehicle was a modified 2006 Toyota Prius named "Little Ben." Among the sensors utilized by Ben was a Velodyne 3-D LIDAR, a small collection of Sick and Hokuyo LIDARs and a Bumblebee II stereo camera head. On November 3, 2007, Ben took fourth place and was one only six robots to successfully complete the 57 mile DARPA Urban Challenge course. It was the only track B (not funded by DARPA) robot to do so. Of an original field comprised of 89 entrants, Ben was ultimately only one of eleven robots to qualify for the final event.

Lehigh's efforts were focused on developing robust approaches for real-time perception (both active and passive) in urban environments. In addition to providing a portion of the low-level architecture for interfacing with the Sick LD/LMS laser range-finders (later polished and released as The Sick LIDAR Matlab/C++ Toolbox), we implemented real-time algorithms for accurate terrain classification and traffic line extraction - using the Sick LMS LIDARs and a hood mounted Bumblebee II. A video of the LIDAR-based classification and line detection process can be seen here.

The initial visibility and network proximity graphs for a team of eight robots tracking five mobile targets.

The trajectories for the robot team as given by our approach. In this case, the team ultimately converges to an optimal configuration.

The final visibility and network proximity graphs. The objective was to maximize the total number of sensor tracks.

In this work, we exploit results from spectral graph theory which state that the connectivity of a weighted graph is directly related to the second-smallest eigenvalue of its associated weighted graph Laplacian. The notion of optimality in this case is loosely defined as minimizing some convex objective function subject to constraints that ensure the full connectivity of both the network proximity graph and what we call the sensor visibility graph. In a visibility graph, each point-to-point sensor track corresponds to a single edge in the graph where nodes are comprised of the full set of system agents and targets. Using semi-definite programming (SDP), we propose a discrete time framework that ensures both network connectivity as well as full target coverage (each target is tracked by at least a single member of the team) while minimizing some arbitrary objective during each time step.

Extensions to this work include ensuring k-Coverage and a relaxation suitable for large-scale tracking scenarios. In the former, combinatory graphs are used to ensure each target in the system is tracked by at least k members of the robot team. Regarding the latter, network connectivity requirements are relaxed to obtain a second-order cone formulation of the tracking problem. This relaxation can be solved much more efficiently than its SDP counterpart.

Although many different convex objectives are appropriate, (e.g. minimizing the trace of the covariance corresponding to confidence measures in believed target positions) we opt to consider maximizing connectivity of the visibility graph. In other words, we aim to seek an evolving trajectory that after each iteration aims to increase the number of active sensor tracks, while maintaining network connectivity. A simple simulation is shown in the above figures for a team of eight robots tracking five targets in R³.

Team charged with reaching an objective goal position in a non-convex workspace, while maintaining a desired shape configuration.

Phase I - A high-level planner selects the best path (using a coarse shortest path algorithm) to reach the objective position in the tessellated workspace.

Phase II - Second-order cone programming is used to efficiently identify optimal collision-free trajectories over the chosen path, minimizing distance travelled.

In this work, we investigated the optimal coordination of multi-robot teams subject to convex and non-convex workspace constraints. In the former case, optimal solutions are obtained in linear time (in-practice) with respect to both environment size and formation size. Key to obtaining this result is the ability to formulate the corresponding problem as a second-order cone program (SOCP). In the latter case, a multi-phase hybrid optimization approach inspired by model predictive control techniques is proposed. During Phase I, a suitable path is generated via a high-level planning algorithm over the tessellated workspace using a predetermined optimization horizon length. During Phase II, SOCP is again used to identify optimal trajectories, this time over the selected path in the given workspace. Once again, using SOCP with standard preprocessing approaches reveals that linear time performance w.r.t. the team size (or optimization horizon length, depending upon which is preferred) is readily obtainable. Our approach guarantees against collisions with static obstacles and environmental boundaries. Theoretical bounds are also established for both scenarios using an interior-point method geared for SOCPs.

A team charged with obtaining an optimal {4,4} tessellation using our decentralized approach for optimal formation control.

Propagation of optimal solution through the visibility network as nodes observe the relative pose of neighbors to locally solve the problem.

The {4,4} tessellation that minimizes the total distance traveled by the team.

In this work, we propose centralized, distributed, and decentralized techniques for optimal formation control of robot teams and wireless sensor networks. Our definition of optimality is defined as either minimizing the total distance that the team must travel or minimizing the maximum distance that any member travels to obtain its objective position. In formulating the centralized approach, we employ second-order cone programming (SOCP) to find the optimal similarity transformation that maps a set of control points defining the desired shape geometry to an equivalent representation in the team's configuration space. Additionally, we establish theoretical complexity bounds that highlight the efficacy of this approach for real-time robotics. Performance in-practice scales linearly with formation size.

These results are extended to both computationally distributed and hierarchically decentralized approaches. In the former, the team is modeled as an overlay network and solves the problem by having each node simply perform computations associated with the constraints and variables it introduces into the system. Employing a hierarchical cluster-based messaging structure, expected per-node computational and storage complexities are constant. The number of expected overlay messages scales logarithmically with formation size. Theoretical bounds are also established. The approach was implemented on a team of six Sony Aibos that were charged with obtaining a delta formation (video below).

The proposed decentralized approach exploits our novel (non-relaxed) formulation of shape as an affine set. The dimensionality of the corresponding nullspace is four which maps to the translation, rotation, and scale components of the optimal similarity transformation. Thus, embedding four more linear equalities makes the optimization problem fully-constrained and solvable via closed-form methods. Exploiting the fact that local observations facilitate additional constraints, we propose a propagating leader/follower approach that provides constant per-node computational complexity - independent of formation size. This approach is illustrated in the figures above for a team of 100 robots charged with obtaining an optimal {4,4} tessellation (video below).

Gimli (a "hybrid" FSO/RF node) using his on-board inclinometer and Garmin GPS to navigate to a target waypoint. Sensor data was fused using an Extended Kalman Filter (EKF).

Gimli's pan-tilt mechanism holding his FSO transceiver. The pan-tilt device is used to align the optical heads on respective link partners.

Consider a scenario where the infrastructure of a metropolitan area network (MAN) is incapacitated by a man-made or natural disaster (e.g. an earthquake). MAN connectivity could be automatically restored by a team of autonomous mobile robots if each were equipped with a communications medium capable of patching the broken links. However, in this case the link distance and throughput requirements might be of such magnitude to render radio frequency (RF) based approaches ineffective.

We predict that such throughput intensive scenarios will lead to the emergence of hybrid FSO/RF based mobile ad-hoc network (MANET) architectures. The benefits of such a model are obvious. An FSO link in any network provides a high throughput channel over which time sensitive data can be transmitted. Many commercially available FSO devices already provide throughput rates in the Gbps range. Additionally, FSO provides constant throughput over a much longer range than RF-based channels.

Several challenges must be addressed before such a network model can be realized. These include a means by which deployed robots can autonomously establish optical links over long distances and the formulation of a mobile network architecture that can exploit high throughput FSO channels. Our work offers solutions to these problems in the form of hierarchical link acquisition and routing protocols. The heart of our link acquisition system (LAS) is a vision-based alignment phase for locating robot link partners via high zoom camera systems. Identification is accomplished in real-time using a multi-resolution image representation and normalized intensity distribution (NID) as a similarity metric. Our routing protocol relies upon the Hierarchical State Routing (HSR) model adapted to the FSO/RF paradigm. Our most recent work has focused on eliminating the use of NID. In particular, we seek to utilize a robust scale-independent feature-based tracker, such as Lowe's SIFT.