Preprints
PDF|arXiv This article presents a novel multi-agent spatial transformer (MAST) for learning communication policies in large-scale decentralized and collaborative multi-robot systems (DC-MRS). Challenges in collaboration in DC-MRS arise from: (i) partial observable states as robots make only localized perception, (ii) limited communication range with no central server, and (iii) independent execution of actions. The robots need to optimize a common task-specific objective, which, under the restricted setting, must be done using a communication policy that exhibits the desired collaborative behavior. The proposed MAST is a decentralized transformer architecture that learns communication policies to compute abstract information to be shared with other agents and processes the received information with the robot’s own observations. The MAST extends the standard transformer with new positional encoding strategies and attention operation that employs windowing to limit the receptive field for MRS. These are designed for local computation, shift-equivariance, and permutation equivariance, making it a promising approach for DC-MRS. We demonstrate the efficacy of MAST on decentralized assignment and navigation (DAN) and decentralized coverage control. Efficiently trained using imitation learning in a centralized setting, the decentralized MAST policy is robust to communication delays, scales to large teams, and performs better than the baselines and other learning-based approaches.PDF|arXiv Collaboration in large robot swarms to achieve a common global objective is a challenging problem in large environments due to limited sensing and communication capabilities. The robots must execute a Perception-Action-Communication (PAC) loop—they perceive their local environment, communicate with other robots, and take actions in real time. A fundamental challenge in decentralized PAC systems is to decide what information to communicate with the neighboring robots and how to take actions while utilizing the information shared by the neighbors. Recently, this has been addressed using Graph Neural Networks (GNNs) for applications such as flocking and coverage control. Although conceptually, GNN policies are fully decentralized, the evaluation and deployment of such policies have primarily remained centralized or restrictively decentralized. Furthermore, existing frameworks assume sequential execution of perception and action inference, which is very restrictive in real-world applications. This paper proposes a framework for asynchronous PAC in robot swarms, where decentralized GNNs are used to compute navigation actions and generate messages for communication. In particular, we use aggregated GNNs, which enable the exchange of hidden layer information between robots for computational efficiency and decentralized inference of actions. Furthermore, the modules in the framework are asynchronous, allowing robots to perform sensing, extracting information, communication, action inference, and control execution at different frequencies. We demonstrate the effectiveness of GNNs executed in the proposed framework in navigating large robot swarms for collaborative coverage of large environments.PDF|arXiv We propose MADP, a novel diffusion-model-based approach for collaboration in decentralized robot swarms. MADP leverages diffusion models to generate samples from complex and high-dimensional action distributions that capture the interdependencies between agents’ actions. Each robot conditions policy sampling on a fused representation of its own observations and perceptual embeddings received from peers. To evaluate this approach, we task a team of holonomic robots piloted by MADP to address coverage control—a canonical multi agent navigation problem. The policy is trained via imitation learning from a clairvoyant expert on the coverage control problem, with the diffusion process parameterized by a spatial transformer architecture to enable decentralized inference. We evaluate the system under varying numbers, locations, and variances of importance density functions, capturing the robustness demands of real-world coverage tasks. Experiments demonstrate that our model inherits valuable properties from diffusion models, generalizing across agent densities and environments, and consistently outperforming state-of-the-art baselines.
Journals
PDF|IEEE|arXiv We propose a new formulation for the multi-robot task allocation problem that incorporates (a) complex precedence relationships between tasks, (b) efficient intra-task coordination, and (c) cooperation through the formation of robot coalitions. A task graph specifies the tasks and their relationships, and a set of reward functions models the effects of coalition size and preceding task performance. Maximizing task rewards is NP-hard; hence, we propose network flow-based algorithms to approximate solutions efficiently. A novel online algorithm performs iterative re-allocation, providing robustness to task failures and model inaccuracies to achieve higher performance than offline approaches. We comprehensively evaluate the algorithms in a testbed with random missions and reward functions and compare them to a mixed-integer solver and a greedy heuristic. Additionally, we validate the overall approach in an advanced simulator, modeling reward functions based on realistic physical phenomena and executing the tasks with realistic robot dynamics. Results establish efficacy in modeling complex missions and efficiency in generating high-fidelity task plans while leveraging task relationships.PDF|IEEE|arXiv Coverage control is the problem of navigating a robot swarm to collaboratively monitor features or a phenomenon of interest not known a priori. The problem is challenging in decentralized settings with robots that have limited communication and sensing capabilities. We propose a learnable Perception-Action-Communication (LPAC) architecture for the problem, wherein a convolutional neural network (CNN) processes localized perception; a graph neural network (GNN) facilitates robot communications; finally, a shallow multi-layer perceptron (MLP) computes robot actions. The GNN enables collaboration in the robot swarm by computing what information to communicate with nearby robots and how to incorporate received information. Evaluations show that the LPAC models—trained using imitation learning—outperform standard decentralized and centralized coverage control algorithms. The learned policy generalizes to environments different from the training dataset, transfers to larger environments with more robots, and is robust to noisy position estimates. The results indicate the suitability of LPAC architectures for decentralized navigation in robot swarms to achieve collaborative behavior.PDF|IEEE|arXiv Presented at IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2024In this letter, we address the problem of exploration and metric-semantic mapping of multi-floor GPS-denied indoor environments using Size, Weight, and Power (SWaP) constrained aerial robots. Most previous work in exploration assumes that robot localization is solved. However, neglecting the state uncertainty of the agent can ultimately lead to cascading errors both in the resulting map and in the state of the agent itself. Furthermore, actions that reduce localization errors may be at direct odds with the exploration task. We propose a framework that balances the efficiency of exploration with actions that reduce the state uncertainty of the agent. In particular, our algorithmic approach for active metric-semantic SLAM is built upon sparse information abstracted from raw problem data, to make it suitable for SWaP-constrained robots. Furthermore, we integrate this framework within a fully autonomous aerial robotic system that achieves autonomous exploration in cluttered, 3D environments. From extensive real-world experiments, we showed that by including Semantic Loop Closure (SLC), we can reduce the robot pose estimation errors by over 90% in translation and approximately 75% in yaw, and the uncertainties in pose estimates and semantic maps by over 70% and 65%, respectively. Although discussed in the context of indoor multi-floor exploration, our system can be used for various other applications, such as infrastructure inspection and precision agriculture where reliable GPS data may not be available.PDF|IEEE|arXiv The line coverage problem involves finding efficient routes for the coverage of linear features by one or more resource-constrained robots. Linear features model environments such as road networks, power lines, and oil and gas pipelines. Two modes of travel are defined for robots: servicing and deadheading. A robot services a feature if it performs task-specific actions, such as taking images, as it traverses the feature; otherwise, it is deadheading. Traversing the environment incurs costs (e.g., travel time) and resource demands (e.g., battery life). Servicing and deadheading can have different cost and demand functions, which can be direction dependent. The environment is modeled as a graph, and an integer linear program is provided. As the problem is NP-hard, we design a fast and efficient heuristic algorithm, Merge-Embed-Merge (MEM). Exploiting the constructive property of the MEM algorithm, algorithms for line coverage of large graphs with multiple depots are developed. Furthermore, turning costs and nonholonomic constraints are efficiently incorporated into the algorithm. The algorithms are benchmarked on 100 road networks and demonstrated in experiments with aerial robots.PDF|Networks|arXiv Line coverage is the task of servicing a given set of one-dimensional features in an environment. It is important for the inspection of linear infrastructure such as road networks, power lines, and oil and gas pipelines. This paper addresses the single robot line coverage problem for aerial and ground robots by modeling it as an optimization problem on a graph. The problem belongs to the broad class of arc routing problems and is closely related to the rural postman problem (RPP) on asymmetric graphs. The paper presents an integer linear programming formulation with proofs of correctness. Using the minimum cost flow problem, we develop approximation algorithms with guarantees on the solution quality. These guarantees also improve the existing results for the asymmetric RPP. The main algorithm partitions the problem into three cases based on the structure of the required graph, i.e., the graph induced by the features that require servicing. We evaluate our algorithms on road networks from the 50 most populous cities in the world, consisting of up to 730 road segments. The algorithms, augmented with improvement heuristics, run within 3s and generate solutions that are within 10% of the optimum. We experimentally demonstrate our algorithms with commercial UAVs.PDF|IEEE|arXiv Presented at IEEE International Conference on Robotics and Automation (ICRA) 2022The area coverage problem is the task of efficiently servicing a given two-dimensional surface using sensors mounted on robots such as unmanned aerial vehicles (UAVs) and unmanned ground vehicles (UGVs). We present a novel formulation for generating coverage routes for multiple capacity-constrained robots, where capacity can be specified in terms of battery life or flight time. Traversing the environment incurs demands on the robot resources, which have capacity limits. The central aspect of our approach is transforming the area coverage problem into a line coverage problem (i.e., coverage of linear features), and then generating routes that minimize the total cost of travel while respecting the capacity constraints. We define two modes of travel: (1) servicing and (2) deadheading, which correspond to whether a robot is performing task-specific actions or not. Our formulation allows separate and asymmetric travel costs and demands for the two modes. Furthermore, the cells computed from cell decomposition, aimed at minimizing the number of turns, are not required to be monotone polygons. We develop new procedures for cell decomposition and generation of service tracks that can handle non-monotone polygons with or without holes. We establish the efficacy of our algorithm on a ground robot dataset with 25 indoor environments and an aerial robot dataset with 300 outdoor environments. The algorithm generates solutions whose costs are 10% lower on average than state-of-the-art methods. We additionally demonstrate our algorithm in experiments with UAVs.PDF|Elsevier This paper introduces a new approach for the design of planar six-bar mechanisms for the purpose of function generation. The structural error is formulated using the input-output relationship of such a mechanism. In addition to the conventional structural error, its derivative is minimised via numerical optimisation, leading to the novel concept of dual-order structural error, which lends itself naturally to a multi-objective formulation of the design problem. Furthermore, analytical conditions for the mobility of the mechanism are derived for two cases: mobility for the full cycle of the crank, and for any given subset of it, along with the identification of the kinematic branches. These conditions help confine the numerical search for the optimal designs to the feasible regions of the design space, leading to a very efficient computational scheme. The results obtained are better in accuracy as compared to the reported results in existing literature. The formulation and results are demonstrated in the context of the Watt-II and the Stephenson-III mechanisms.PDF|ASME This paper presents a novel analytical formulation for identifying the closest pair of points lying on two arbitrary cylinders in space, and subsequently the distance between them. Each cylinder is decomposed into four geometric primitives. It is shown that the original problem reduces to the computation of the shortest distance between five distinct combinations of these primitives. Four of these sub-problems are solved in closed form, while the remaining one requires the solution of an eight-degree polynomial equation. The analytical nature of the formulation and solution allows the identification of all the special cases, e.g., positive-dimensional solutions, and the curve of intersection when the cylinders interfere. The symbolic pre-computation of the results leads to a fast numerical implementation, capable of solving the problem in about 50 micro seconds (averaged over 1 million random instances of the most general case) on a standard PC. The numerical results are verified by repeating all the calculations in a general purpose commercial CAD software. The algorithm has significant potential for applications in the various aspects of robotics and mechanisms, as their links can be modeled easily and compactly as cylinders. This makes tasks such as path-planning, determination of the collision-free workspace etc. computationally easier.PDF This paper presents a detailed dynamic modeling of realistic four-legged robot. The direct and inverse kinematic analysis for each leg has been considered in order to develop an overall kinematic model of the robot, when it follows a straight path. This study also aims to estimate optimal feet force distributions of the said robot, which is necessary for its real-time control. Three different approaches namely, minimization of norm of feet forces (approach 1), minimization of norm of joint torques (approach 2) and minimization of norm of joint power (approach 3) have been developed. Simulation result shows that approach 3 is more energy efficient foot force formulation than other two approaches. Lagrange-Euler formulation has been utilized to determine the joint torques. The developed dynamic models have been examined through computer simulation of continuous gait of the four-legged robot.
Conferences
PDF|IEEE|arXiv The multi-objective coverage control problem requires a robot swarm to collaboratively provide sensor coverage to multiple heterogeneous importance density fields (IDFs) simultaneously. We pose this as an optimization problem with constraints and study two different formulations: (1) Fair coverage, where we minimize the maximum coverage cost for any field, promoting equitable resource distribution among all fields; and (2) Constrained coverage, where each field must be covered below a certain cost threshold, ensuring that critical areas receive adequate coverage according to predefined importance levels. We study the decentralized setting where robots have limited communication and local sensing capabilities, making the system more realistic, scalable, and robust. Given the complexity, we propose a novel decentralized constrained learning approach that combines primal-dual optimization with a Learnable Perception-Action-Communication (LPAC) neural network architecture. We show that the Lagrangian of the dual problem can be reformulated as a linear combination of the IDFs, enabling the LPAC policy to serve as a primal solver. We empirically demonstrate that the proposed method (i) significantly outperforms state-of-the-art decentralized controllers by 30% on average in terms of coverage cost, (ii) transfers well to larger environments with more robots, and (iii) is scalable in the number of IDFs and robots in the swarm.PDF|IEEE We propose a new formulation for the multi-robot task planning and allocation problem that incorporates (a) precedence relationships between tasks; (b) coordination for tasks allowing multiple robots to achieve increased efficiency; and (c) cooperation through the formation of robot coalitions for tasks that cannot be performed by individual robots alone. In our formulation, the tasks and the relationships between the tasks are specified by a task graph. We define a set of reward functions over the task graph’s nodes and edges. These functions model the effect of robot coalition size on task performance while incorporating the influence of one task’s performance on a dependent task. Solving this problem optimally is NP-hard. However, using the task graph formulation allows us to leverage min-cost network flow approaches to obtain approximate solutions efficiently. Additionally, we explore a mixed integer programming approach, which gives optimal solutions for small instances of the problem but is computationally expensive. We also develop a greedy heuristic algorithm as a baseline. Our modeling and solution approaches result in task plans that leverage task precedence relationships and robot coordination and cooperation to achieve high mission performance, even in large missions with many agents.PDF|Springer|arXiv This paper introduces the correlated arc orienteering problem (CAOP), where the task is to find routes for a team of robots to maximize the collection of rewards associated with features in the environment. These features can be one-dimensional or points in the environment, and can have spatial correlation, i.e., visiting a feature in the environment may provide a portion of the reward associated with a correlated feature. A robot incurs costs as it traverses the environment, and the total cost for its route is limited by a resource constraint such as battery life or operation time. As environments are often large, we permit multiple depots where the robots must start and end their routes. The CAOP generalizes the correlated orienteering problem (COP), where the rewards are only associated with point features, and the arc orienteering problem (AOP), where the rewards are not spatially correlated. We formulate a mixed integer quadratic program (MIQP) that formalizes the problem and gives optimal solutions. However, the problem is NP-hard, and therefore we develop an efficient greedy constructive algorithm. We illustrate the problem with two different applications: informative path planning for methane gas leak detection and coverage of road networks.PDF|Springer|Video The line coverage problem is the task of servicing a given set of one-dimensional features in an environment. Its applications include the inspection of road networks, power lines, and oil and gas lines. The line coverage problem is a generalization of the standard arc routing problems, and is NP-hard in general. We address the single robot line coverage problem where the service and deadhead costs are distinct and asymmetric. We model the problem as an optimization problem that minimizes the total cost of travel on a given graph. We present approximation algorithms to obtain bounded solutions efficiently, using the minimum cost flow problem. We build the main algorithm in stages by considering three simpler subproblems. The subproblems are based on the structure of the required graph, i.e., the graph induced by the features that require servicing. We first present an optimal algorithm for the case of Eulerian graphs with only required edges. Next we consider general graphs, not necessarily Eulerian, with only required edges and present a \(2\)-approximation algorithm. Finally, we consider the general case with both required and non-required edges. The approximation algorithm is dependent on the Asymmetric Traveling Salesperson Problem (ATSP), and is bounded by \( \alpha(C) + 2 \), where \( \alpha(C) \) is the approximation factor of the ATSP algorithm with \( C \) connected components. Our upper bound is also an improvement over the existing results for the asymmetric rural postman problem.PDF|IEEE The line coverage problem is the coverage of linear environment features (e.g., road networks, power lines), modeled as 1D segments, by one or more robots while respecting resource constraints (e.g., battery capacity, flight time) for each of the robots. The robots incur direction dependent costs and resource demands as they traverse the edges. We treat the line coverage problem as an optimization problem, with the total cost of the tours as the objective, by formulating it as a mixed integer linear program (MILP). The line coverage problem is NP-hard and hence we develop a heuristic algorithm, Merge-Embed-Merge (MEM). We compare it against the optimal MILP approach and a baseline heuristic algorithm, Extended Path Scanning. We show the MEM algorithm is fast and suitable for real-time applications. To tackle large-scale problems, our approach performs graph simplification and graph partitioning, followed by robot tour generation for each of the partitioned subgraphs. We demonstrate our approach on a large graph with 4,658 edges and 4,504 vertices that represents an urban region of about 16 sq. km. We compare the performance of the algorithms on several small road networks and experimentally demonstrate the approach using UAVs on the UNC Charlotte campus road network.PDF|IEEE|DoodleBots This paper presents algorithms to simultaneously compute the optimal assignments and formation parameters for a team of robots from a given initial formation to a variable goal formation (where the shape of the goal formation is given, and its scale and location parameters must be optimized). We assume the \( n \) robots are identical spheres. We use the sum of squared travel distances as the objective function to be minimized, which also ensures that the trajectories are collision free. We show that this assignment with variable goal formation problem can be transformed to a linear sum assignment problem (LSAP) with pseudo costs that we establish are independent of the formation parameters. The transformed problem can then be solved using the Hungarian algorithm in \( \mathcal O(n^3) \) time. Thus the assignment problem with variable goal formations using this new approach has the same \( \mathcal O(n^3) \) time complexity as the standard assignment problem with fixed goal formations. Results from simulations on 200 and 600 robots are presented to show the algorithm is sufficiently fast for practical applications.PDF|Springer|Slides This paper presents a method to compute the largest sphere inside the position workspace of a semi-regular Stewart platform manipulator that is free of gain- type singularities. The sphere is specific to a given orientation of the moving platform and is centred at a designated point of interest. The computation is performed in two parts; in the first part, a computer algebra system (CAS) is used to derive a set of exact symbolic expressions, which are then used further in a purely numerical manner for faster computation. The method thus affords high computation speed while retaining the exactness and generic nature of the results. The numerical results are validated against those obtained from an established numerical algebraic geometry tool, namely, Bertini, and are illustrated via an example.PDF|Slides This paper presents an approach for the design of parallel manipulators, from the perspective of optimal dynamic performance over a given safe working zone. It is shown that no single index is sufficient to fully quantify the dynamic performance of such a system. Two different indices are therefore developed from the study of the generic equation of motion of such systems. The resulting bi-objective optimisation problem is solved using a genetic algorithm-based numerical optimiser, namely, NSGA-II. The proposed algorithm is applied to an existing planar 3-RRR parallel manipulator, to obtain an improved design. It is found that the improved design, though obtained by optimising the intrinsic performance indices, perform better in terms of extrinsic dynamic indices, such as the required torque for tracking a set of given trajectories.PDF|Slides This paper introduces a new approach for the synthesis of planar six-bar mechanisms via multi-objective numerical optimisation. Using the input-output relationship of such a mechanism, the structural error is formulated. In addition to the structural error, its derivative is also included in the objectives, leading to results which are comparable in accuracy to the exact methods reported in existing literature, and better than the optimisation-based methods. Also, analytical conditions are derived for the identification of the candidate designs which are free of singularities, mobility or branch defects. The formulation and results are demonstrated in the context of a Stephenson-III mechanism, though these can be generalised to the six-bar mechanisms of other topologies.PDF Control of robots and mechanisms is a challenging task, more so with inaccurate models and error-prone mechanical elements. This work tries to compensate the errors, owing to different factors, which creep into the system and hamper its performance, by appropriately employing multiple control loops, utilising redundant feedback present in the manipulator design, in real time. It looks into the different control strategies and validate them with experimental analysis by tracking a trajectory.
Ph.D. Thesis
PDF Recent technological advances have facilitated the use of mobile robots for a wide range of coverage applications such as inspection and mapping of infrastructure, precision agriculture, and disaster management. With the proliferation of these tasks comes an increasing need for autonomous systems to efficiently gather data for analyzing the state of the environment. The dissertation answers the following fundamental question: How should resource-constrained robots traverse the environment to collect data from all the relevant features? These features of interest can be represented as points, lines or curves, and areas. This dissertation unifies simultaneous coverage of all three types of features into a novel generalized coverage framework, develops algorithms for efficient coverage using multiple mobile robots, and validates them in experiments.
The dissertation first comprehensively studies the line coverage problem, i.e., coverage of one-dimensional features with multiple resource-constrained robots. We model the environment as a graph and formalize line coverage as an optimization problem using integer linear programs (ILP). The problem is NP-hard, and therefore we design approximation algorithms with provable guarantees and heuristic algorithms for large graphs, validating them extensively in simulations and experiments. Extensions to the formulation and algorithms address large-scale environments and nonholonomic robots that cannot make point turns. These formulations of the line coverage problem lay the foundation for generalized coverage. Next, we show that we can transform the area coverage problem into a line coverage problem using computational geometry techniques and then generate routes using line coverage algorithms. Existing methods have significant inefficiencies due to their use of monotone polygons. Using the line coverage transformation allows polygons with obstacles that are not monotone while minimizing the number of turns for the robots. The transformation enables algorithmic advances in line coverage to be directly applied to area coverage. Finally, we formulate the generalized coverage problem and solve it by transforming both point and area features into line features in a unified framework. The algorithms demonstrate significantly improved performance over state-of-the-art solutions while additionally incorporating battery life constraints, nonholonomic robots, and multiple home locations for large-scale environments. We evaluate the performance of the algorithms on several real-world datasets in simulations and experiments. The algorithms are very fast and generate high-quality solutions for robotics applications.