Graphs have been used extensively to model networks of robot or sensor networks [1, 2]. One of the fundamental algebraic tools relevant to graphs is the graph Laplacian matrix, the spectrum of which encodes the connectivity of the graph [3]. In weighted graphs, one assigns non-negative, real-valued weights or importance to each edge of the graph, with a zero weight on an edge being equivalent to the edge being non-existent, thus allowing a continuum between different graph topologies. Furthermore, for robot or mobile sensor networks, the real-valued weights naturally correspond to the separation or distance between pairs of agents (with the weights being inversely related to the distances so that agents that are closer to each other are strongly connected, while agents that are farther from each other are weakly connected). A weighted graph Laplacian can be constructed accordingly, and real-valued optimization objectives can be formulated to control the connectivity of a network [4, 5].

Many robotics applications benefit from being able to compute multiple locally optimal paths in a given configuration space. Examples include path planning for of tethered robots with cable-length constraints, systems involving cables, multi-robot topological exploration & coverage, and, congestion reduction for mobile robots navigation without inter-robot coordination. Existing paradigm is to use topological path planning methods that can provide optimal paths from distinct topological classes available in the underlying configuration space. However, these methods usually require non-trivial and non-universal geometrical constructions, which are prohibitively complex or expensive in 3 or higher dimensional configuration spaces with complex topology. Furthermore, topological methods are unable to distinguish between locally optimal paths that belong to the same topological class but are distinct because of genus-zero obstacles in 3D or due to high-cost or high-curvature regions. In this paper we propose an universal and generalized approach to multiple, locally-optimal path planning using the concept of a novel neighborhood-augmented graph, search-based planning in which can compute paths that are topo-geometrically distinct. This approach can find desired number of locally optimal paths in a wider variety of configuration spaces without requiring any complex pre-processing or geometric constructions. Unlike the existing topological methods, resulting optimal paths are not restricted to distinct topological classes, thus making the algorithm applicable to many other problems where locally optimal and geometrically distinct paths are of interest. We demonstrate the use of our algorithm to planning for shortest traversible paths for a tethered robot in 3D with cable-length constraint, and validate the results in simulations and real robot experimentation.

Autonomous vehicles are expected to travel in urban environments in the future for increased safety and overall efficiency. They could be of different car brands running different navigation & communication systems that do not share their route-choosing processes or travel data, either due to lack of communication or due to privacy restrictions. To avoid traffic congestion, such as those caused by non-cooperating human drivers nowadays, independent autonomous vehicles need to have a method for distributing traffic in the environment without communication. Motivated by this real-world scenario, in this paper we consider the problem of path planning for a large number of privacy-aware robots in a complex, cluttered indoor or urban environment with uncertainties (other unpredictable agents such as pedestrians), where the robots need to be well-distributed throughout the environment and avoid congestion in any region, but are not allowed to communicate or share their location data or intents with other robots. This is relevant to avoiding congestion in distributed vehicle routing problems when a vehicle's location/intent cannot be shared either due to lack of communication or due to privacy restrictions.

The use of cables for aerial manipulation has shown to be a lightweight and versatile way to interact with objects. However, fastening objects using cables is still a challenge and human is required. In this work, we propose a novel way to secure objects using hitches. The hitch can be formed and morphed in midair using a team of aerial robots with cables. The hitch's shape is modeled as a convex polygon, making it versatile and adaptable to a wide variety of objects. We propose an algorithm to form the hitch systematically. The steps can run in parallel, allowing hitches with a large number of robots to be formed in constant time. We develop a set of actions that include different actions to change the shape of the hitch. We demonstrate our methods using a team of aerial robots via simulation and actual experiments.

Homotopy classes of trajectories, arising due to the presence of obstacles, are defined as sets of trajectories that can be transformed into each other by gradual bending and stretching without colliding with obstacles. The problem of exploring/finding the different homotopy classes in an environment and the problem of finding least-cost paths restricted to a specific homotopy class (or not belonging to certain homotopy classes) arises frequently in such applications as predicting paths for unpredictable entities and deployment of multiple agents for efficient exploration of an environment. In [Bhattacharya, Kumar, Likhachev, AAAI 2010] we have shown how homotopy classes of trajectories on a two-dimensional plane with obstacles can be classified and identified using the Cauchy Integral Theorem and the Residue Theorem from Complex Analysis. In more recent work [Bhattacharya, Likhachev, Kumar, RSS 2011] we extended this representation to three-dimensional spaces by exploiting certain laws from the Theory of Electromagnetism (Biot-Savart law and Ampere's Law) for representing and identifying homotopy classes in three dimensions in an efficient way. Using such a representation, we showed that homotopy class constraints can be seamlessly weaved into graph search techniques for determining optimal path constrained to certain homotopy classes or forbidden from others, as well as for exploring different homotopy classes in an environment. (This is a condensed, non-technical overview of work previously published in the proceedings of Robotics: Science and Systems, 2011 conference [Bhattacharya, Likhachev, Kumar, RSS 2011].)

Goal-directed path planning is one of the basic and widely studied problems in the field of mobile robotics. Homotopy classes of trajectories, arising due to the presence of obstacles, are defined as sets of trajectories that can be transformed into each other by gradual bending and stretching without colliding with obstacles. The problem of finding least-cost paths restricted to a specific homotopy class or finding least-cost paths that do not belong to certain homotopy classes arises frequently in such applications as predicting paths for dynamic entities and computing heuristics for path planning with dynamic constraints. In the present work, we develop a compact way of representing homotopy classes and propose an efficient method of graph search-based optimal path planning with constraints on homotopy classes. The method is based on representing the environment of the robot as a complex plane and making use of the Cauchy Integral Theorem. We prove optimality of the method and show its efficiency experimentally.