The use of cables in aerial manipulation offers a lightweight and flexible alternative to rigid grasping mechanisms. However, achieving autonomous tying and secure transportation of objects with cables remains a significant challenge. In this work, we present a novel method for autonomously securing and transporting objects using multi-layer hitches formed in midair by a team of aerial robots. Building upon prior work on polygonal hitch formation, we extend the framework to include layered cable interlacing that increases frictional grip and enables secure object grasping. We introduce two new manipulation actions: multi-layer tying and autonomous object release, completing the pipeline for aerial grasping and transportation. We develop a capstan-based analytical model that establishes an exponential scaling law for the effect of cable layers and provides a conservative guideline. The formation algorithm operates in parallel, ensuring scalability to large teams with constant execution time. We validate our system through simulation and hardware experiments, demonstrating fully autonomous object tying, lifting, and releasing using cables alone without human intervention.

Many robotics applications benefit from being able to compute multiple geodesic paths in a given configuration space. Existing paradigm is to use topological path planning, which can compute optimal paths in distinct topological classes. However, these methods usually require nontrivial geometric constructions, which are prohibitively expensive in 3-D, and are unable to distinguish between distinct topologically equivalent geodesics that are created due to high-cost/curvature regions or prismatic obstacles in 3-D. In this article, we propose an approach to compute$k$geodesic paths using the concept of a novel neighborhood-augmented graph, on which graph search algorithms can compute multiple optimal paths that are topo-geometrically distinct. Our approach does not require complex geometric constructions, and the resulting paths are not restricted to distinct topological classes, making the algorithm suitable for problems where finding and distinguishing between geodesic paths are of interest. We demonstrate the application of our algorithm to planning shortest traversible paths for a tethered robot in 3-D with cable-length constraint.

Abstract In this paper, we address the problem of autonomous multi-robot mapping, exploration and navigation in unknown, GPS-denied indoor or urban environments using a team of robots equipped with directional sensors with limited sensing capabilities and limited computational resources. The robots have no a priori knowledge of the environment and need to rapidly explore and construct a map in a distributed manner using existing landmarks, the presence of which can be detected using onboard senors, although little to no metric information (distance or bearing to the landmarks) is available. In order to correctly and effectively achieve this, the presence of a necessary density/distribution of landmarks is ensured by design of the urban/indoor environment. We thus address this problem in two phases: (1) During the design/construction of the urban/indoor environment we can ensure that sufficient landmarks are placed within the environment. To that end we develop a filtration -based approach for designing strategic placement of landmarks in an environment. (2) We develop a distributed algorithm which a team of robots, with no a priori knowledge of the environment, can use to explore such an environment, construct a topological map requiring no metric/distance information, and use that map to navigate within the environment. This is achieved using a topological representation of the environment (called a Landmark Complex ), instead of constructing a complete metric/pixel map. The representation is built by the robot as well as used by them for navigation through a balanced strategy involving exploration and exploitation. We use tools from homology theory for identifying “ holes ” in the coverage/exploration of the unknown environment and hence guide the robots towards achieving a complete exploration and mapping of the environment. Our simulation results demonstrate the effectiveness of the proposed metric-free topological (simplicial complex) representation in achieving exploration, localization and navigation within the environment.

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.

This work deals with the problem of planning conflict-free paths for mobile robots in cluttered environments. Since centralized, coupled planning algorithms are computationally intractable for large numbers of robots, we consider decoupled planning, in which robots plan their paths sequentially in order of priority. Choosing how to prioritize the robots is a key consideration. State-of-the-art prioritization heuristics, however, do not model the coupling between a robot's mobility and its environment. This is particularly relevant when prioritizing between robots with different degrees of mobility. In this paper, we propose a prioritization rule that can be computed online by each robot independently, and that provides consistent, conflict-free path plans. Our innovation is to formalize a robot's path prospects to reach its goal from its current location. To this end, we consider the number of homology classes of trajectories, which capture distinct prospects of paths for each robot. This measure is used as a prioritization rule, whenever any robots enter negotiation to deconflict path plans. We perform simulations with heterogeneous robot teams and compare our method to five benchmarks. Our method achieves the highest success rate, and strikes a good balance between makespan and flowtime objectives.

In this paper we consider the problem of autonomous exploration of an unknown, GPS-denied environment using a swarm of robots with very limited resources and limited sensing capabilities. To that end we use a landmark complex, a simplicial complex utilizing an observation of landmarks, as a topological representation of the environment. Each robot is equipped with an omni-directional, limited-range sensor that can identify landmarks in the robot's neighborhood. The robots use the bearing angles to the landmarks for local navigation. Given a collection of identifiable landmarks, a landmark complex can then be cumulatively constructed to encapsulate the topological information of the environment. Under the assumption of sufficiently dense landmarks, we propose an exploration and exploitation strategy that guides the swarm of robots to explore an environment using only bearing measurements without any metric information. Lastly, we demonstrate the coordinate-free and localization-free navigation in the environment using the constructed landmark complex.

We present a novel approach for solving pursuit-evasion problems where multiple pursuers with limited sensing capabilities are used to detect all possible mobile evaders in a given environment. We make no assumptions about the number, the speed, or the maneuverability of evaders. Our algorithm takes as input a map of the environment and sensor models for the pursuers. We then obtain a graph representation of an environment using a Čech Complex. Even with such a representation, the configuration space grows exponentially with the number of pursuers. In order to address this challenge, we propose an abstraction framework to partition the configuration space into sets of topologically similar configurations that preserve the space of possible evader locations. We validate our approach on several simulated environments with varying topologies and numbers of pursuers.

We focus on the problem of detecting anomalous run-time behavior of distributed applications from their execution logs. Specifically we mine templates and template sequences from logs to form a control flow graph (cfg) spanning distributed components. This cfg represents the baseline healthy system state and is used to flag deviations from the expected behavior of runtime logs. The novelty in our work stems from the new techniques employed to: (1) overcome the instrumentation requirements or application specific assumptions made in prior log mining approaches, (2) improve the accuracy of mined templates and the cfg in the presence of long parameters and high amount of interleaving respectively, and (3) improve by orders of magnitude the scalability of the cfg mining process in terms of volume of log data that can be processed per day. We evaluate our approach using (a) synthetic log traces and (b) multiple real-world log datasets collected at different layers of application stack. Results demonstrate that our template mining, cfg mining, and anomaly detection algorithms have high accuracy. The distributed implementation of our pipeline is highly scalable and has more than 500 GB/day of log data processing capability even on a 10 low-end VM based (Spark + Hadoop) cluster. We also demonstrate the efficacy of our end-to-end system using a case study with the Openstack VM provisioning system.

We consider the problem of deploying a swarm of mobile robots into an unknown environment for attaining complete sensor coverage of the environment. The robots have limited and noisy sensing capabilities and no metric or global information available to them. Using tools from algebraic topology, we formally describe the sensor coverage as a simplicial complex, deploy robots through the complex using bearing-based local controllers, and attain coverage while identifying and removing sensor redundancies. Despite the highly limited sensing capabilities and complete lack of global localization and metric information, we demonstrate that the proposed algorithm is complete, always terminates in a finite-sized environment, is guaranteed to attain complete coverage and is robust to sensor failures. The algorithm presented in this paper was demonstrated through simulation and proves to effectively cover and explore unknown indoor environments.

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 investigate the problem of navigation for a planar mobile robot tethered to a base by a flexible cable of length L. Obstacles present in the environment, coupled with the cable length constraint, makes the problem highly non-trivial. We adopt a topological approach along with graph search-based techniques to solve this problem, wherein we use the notion of a homotopy augmented graph to capture the information about the homotopy class of the cable. This lets us plan traversable optimal trajectories from an initial robot position and cable configuration to a final position of the robot. We demonstrate the algorithm by planning trajectories in several cluttered environments and with different cable lengths. As a demonstration of practical applicability, using a dynamic simulation testbed we simulate a robot-cable system following a planned trajectory.

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.

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.

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].)

Oil skimmers towed by two vehicles have been widely used for skimming of oil on the water surface. In this paper, we address the cooperative control of two autonomous surface vehicles for oil skimming and cleanings. We model the skimmer as a flexible, floating rope of constant length as well as discrete segmented model. We derive the equations governing the rope dynamics from first principles and demonstrate their application through simulations. We have performed field experiments with two autonomous surface vehicles that substantiate the proposed model and provides estimates of constants underlying the model. We propose a method for controlling the shape of the rope, and derive the conditions that maximize skimming efficiency.

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.

Abstract — The DPC algorithm developed in our previous work is an efficient way of computing optimal trajectories for multiple robots in a distributed fashion with timeparameterized constraints on the distances between pairs of robots. In the present work we extend DPC to the problem of multiple task execution. While this extended problem inherits all the objectives, complexities and constraints of the basic DPC algorithm, each robot is also given an unordered set of tasks that it has to execute before it reaches its goal. There is no specific order imposed on the tasks assigned to a particular robot. The algorithm decides the order of execution of the tasks such that an optimal solution is attained while the time-parametrized distance constraints are satisfied along with successful execution of the tasks. We solve this problem by designing a “State-task Graph ” that represents a product of the state-space graph and the task graph. We then develop an efficient heuristic function for performing searches in this graph. I.

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.

We present a search-based planning approach for controlling a quadrupedal robot over rough terrain. Given a start and goal position, we consider the problem of generating a complete joint trajectory that will result in the legged robot successfully moving from the start to the goal. We decompose the problem into two main phases: an initial global planning phase, which results in a footstep trajectory; and an execution phase, which dynamically generates a joint trajectory to best execute the footstep trajectory. We show how R* search can be employed to generate high-quality global plans in the high-dimensional space of footstep trajectories. Results show that the global plans coupled with the joint controller result in a system robust enough to deal with a variety of terrains.

With 90nm CMOS in production and 65nm testing in progress, power has been pushed to the forefront of design metrics. This paper will outline practical techniques that are used to reduce both leakage as well as active power in a standard-cell library based high-performance design flow. We will discuss the design and cost issues for using different power saving techniques such as: power gating to reduce leakage, multiple and hybrid threshold libraries for leakage reduction and multiple supply voltage based design. In addition techniques to reduce clock tree power will be presented as power consumed in clocks accounts for a significant portion of total chip power. Practical aspects of implementing these techniques will also be discussed.

We propose a novel procedure based on uninterpreted symbolic simulation for checking the scheduling step in high-level synthesis. The primary task in scheduling is the assignment of time steps or, equivalently, states to operations. Various transformations like operation reordering and loop unrolling may be performed in the process to meet the optimization criteria. The contribution of our proposal lied in its ability to efficiently handle loops and a wide range of loop transformations performed during scheduling. Our algorithm is based on loop invariant extraction using a combination of uninterpreted symbolic simulation and induction techniques. In spite of its wide scope, our procedure is relatively complete and practical. This work is a part of our effort to provide a suite of techniques for verifying the various steps involved in the high-level synthesis process. It is being implemented in an in-house verification system for checking equivalence of designs generated from high-level specifications through successive refinements. We present case studies to demonstrate the applicability of our approach. These case studies consist of examples where equivalence cannot be established using conventional FSM-based methods. By providing a viable automated equivalence checking technique for such examples, we improve on the state of the art.

We propose a complete procedure for verifying register-transfer logic against its scheduled behavior in a high-level synthesis environment Our proposal advances the state of the art because it is the first such verification procedure that is both complete and practical.Hardware verification is known to be a hard problem and the proposed verification technique leverages off the fact that highlevel synthesis -performed manually or by means of high-level synthesis software -proceeds from the algorithmic description of the design to structural RTL through a sequence of very well defined steps, each limited in its scope.The major contribution is the partitioning of the equivalence checking task into two simpler subtasks, verifying the validity of register sharing, and verifying correct synthesis of the RTL interconnect and control.While state space traversal is unavoidable for verifying validity of the register sharing, we automatically abstract out irrelevant portions oftbe design, significantly simpliQing the task that must be performed by a back-end model checker.The second task of verifying the RTL is not only shown to reduce to a combinational equivalence check,we present a novel and fast RTL technique for combinational equivalence check instead of using slower gate level techniques.The verification procedure has been applied to several large circuits, and is illustrated on the implementation of a sort algorithm.

This paper analyzes the effect of resource sharing and assignment on the clock period of the synthesized circuit. The assignment phase assigns or binds operations of the scheduled behavioral description to a set of allocated resources. We focus on control-flow intensive descriptions, characterized by the presence of mutually exclusive paths due to the presence of nested conditional branches and loops. We show that clustering multiple operations in the same state of the schedule, possibly leading to chaining of functional units (FUs) in the RTL circuit, is an effective way to minimize the total number of clock cycles, and hence total execution time. We present an assignment algorithm that is particularly effective for such design styles by minimizing data chaining and hence the clock period of the circuit, thereby leading to further reduction in total execution time. Existing resource sharing and assignment approaches for reducing the clock period of the resulting circuit either increase the resource allocation or use faster modules, both leading to leading to larger area requirements. In this paper we show that even when the type of available resource units and the number of resource units of each type is fixed, different assignments may lead to circuits with significant differences in clock period. We provide a comprehensive analysis of how resource sharing and assignment introduces long paths in the circuit. Based on the analysis, we develop an assignment algorithm that uses a high-level delay estimator to asign operations to a fixed set of available resources so as to minimize the clock period of the resultant circuit, with no or minimal effect on the area of the circuit. Experimental results on several conditional-intensive designs demonstrate the effectiveness of the assignment algorithm.

H-SCAN (1996) was presented as a low overhead design-for-testability strategy which is applicable to RT-level controller-data path circuits. However, from the view-point of practical use, there is a possibility that the area overhead of H-SCAN is larger than that of full-scan. Moreover, H-SCAN is unable to handle many features present in actual designs. In this paper, we propose a modified H-SCAN scheme, called "H-SCAN+", as an improved solution for actual designs. H-SCAN+ consists of several enhancements, including techniques to minimize scan design area overhead, handling of features present in actual designs, and techniques to significantly minimize the running time. We provide comprehensive results of applying H-SCAN+ to several actual RT-level designs.

This paper presents H-SCAN, a practical testing methodology that can be easily applied to a high-level design specification. H-SCAN allows the use of combinational test patterns without the high area and test application time overheads associated with full-scan testing. Connectivities between registers existing in an RT-level design are exploited to reduce the area overhead associated with implementing a scan scheme. Test application time is significantly reduced by using the parallelism inherent in the design, and eliminating the pin constraint of parallel scan schemes by analyzing the test responses on-chip using existing comparators. The proposed method also includes generating appropriate sequential test vectors from combinational test vectors generated by a combinational ATPG program. Application of H-SCAN to RT-level designs and fault simulation using the test patterns generated by H-SCAN shows fault coverage comparable to full-scan testing, with significant reduction in test area overhead and test application time when compared to a traditional gate-level full-scan implementation.

This paper addresses the problem of true delay estimation during high level design. The true delay is the delay of the longest sensitizable path in the resulting circuit, as opposed to the topological delay which is the delay of the longest path in the circuit. The existing delay estimation techniques either estimate the topological delay, which may be pessimistic if the longest path is unsensitizable or false, or estimate the true delay using gate-level timing analysis which may be prohibitively expensive. Resource sharing in high level synthesis can create false paths in the circuit implementation. Hence, determining the clock period using topological delay can be unduly conservative, resulting in excessive hardware to meet tight timing specifications. In this paper, we introduce an efficient technique to compute an estimate of the true delay. The proposed technique relies on partitioning the paths in the circuit and topological delay computation, and not on path sensitization. The paths in the implementation are partitioned into two sets given the high level information on scheduling and resource sharing: the complete determining path set (CDP/sub R/) and the nondetermining path set (NDP/sub R/). We prove that the delay of the longest path in CDP/sub R/ is lower bounded by the true delay and upper bounded by the topological delay of the circuit. Consequently, an estimate of the true delay of the resulting circuit can be computed by measuring the topological delay of the longest path in CDP/sub R/. We have developed a Functional delay ESTimation tool (FEST). Experimental results on a set of benchmarks reveal the following: approximately 50% of all paths are in NDP/sub R/ and can be ignored for true delay estimation, and the true delay estimates are on the average 15% less than the topological delay. The high level true delay estimates are accurate, as verified by comparing with the true delays obtained by gate-level timing analysis on actual implementations. Furthermore, results reveal that high level true delay estimation can be done very fast, even when gate-level true delay estimation becomes infeasible.

Abstract- This paper analyzes the effect of resource sharing and assignment on the clock period of the synthesized circuit. We focus on behavioral specifications with mutually exclusive paths, due to the presence of nested conditional branches and loops. It is shown that even when the set of available resources is fixed, different assignments may lead to circuits with significant differences in clock period. We provide a comprehensive analysis of how resource sharing and assignment introduces long paths in the circuit. Based on the analysis, we develop an assignment algorithm which uses a high-level delay estimator to assign operations to a fixed set of available resources so as to minimize the clock period of the resultant circuit. Experimental results on several conditionalintensive designs demonstrate the effectiveness of the assignment algorithm. I.

Abstract- This paper presents a new method,based on Markov chain analysis, to evaluate the performance of schedules of behavioral specifications. The proposed performance measure is the expected number of clock cycles required by the schedule for a complete execution of the behavioral specification for any distribution of inputs. The measure considers both the repetition of operations (due to loops) and their conditional execution (due to conditional branches). We propose an efficient technique to calculate the metric. We introduce a loop-directed scheduling algorithm (LDS). The algorithm produces schedules such that the expected number of clock cycles, required by the schedule for a complete execution of the behavioral specification, is minimized. Experimental results on several conditional and loop-intensive specifications demonstrate the relevance and effectiveness of both the performance measure and the scheduling algorithm. I.

This paper introduces a technique to transform a given register-transfer level (RT-level) design, consisting of control logic and data path, into a functionally equivalent, minimized design which is 100% testable under full-scan at the gate level. The proposed RT-level optimization technique uses the RT-level structure and exploits the interaction between the control and the data path. Our approach maintains the RT-level design hierarchy while performing RT-level transformations of initially specified data path, followed by resynthesis of control using don't cares extracted from the data path. Experiments with several RTL benchmarks demonstrate the effectiveness of the technique in generating fully testable designs. In addition, comparison with logic-level techniques show the advantages of the proposed technique as an optimizing tool to produce circuits with reduced area and delay.>