17 March 2025 in IEEE Transactions on Robotics
We present Splat-Nav, a real-time robot navigation pipeline for Gaussian Splatting (GSplat) scenes, a powerful new 3D scene representation. Splat-Nav consists of two components: 1) Splat-Plan, a safe planning module, and 2) Splat-Loc, a robust vision-based pose estimation module. Splat-Plan builds a safe-by-construction polytope corridor through the map based on mathematically rigorous collision constraints and then constructs a Bézier curve trajectory through this corridor. Splat-Loc provides real-time recursive state estimates given only an RGB feed from an on-board camera, leveraging the point-cloud representation inherent in GSplat scenes. Working together, these modules give robots the ability to recursively re-plan smooth and safe trajectories to goal locations. Goals can be specified with position coordinates, or with language commands by using a semantic GSplat. We demonstrate improved safety compared to point cloud-based methods in extensive simulation experiments. In a total of 126 hardware flights, we demonstrate equivalent safety and speed compared to motion capture and visual odometry, but without a manual frame alignment required by those methods. We show online re-planning at more than 2 Hz and pose estimation at about 25 Hz, an order of magnitude faster than Neural Radiance Field (NeRF)-based navigation methods, thereby enabling real-time navigation. We provide experiment videos on our project page at https://chengine.github.io/splatnav/. Our codebase and ROS nodes can be found at https://github.com/chengine/splatnav.
2 January 2023 in IEEE Transactions on Robotics
In this article, we present a distributed algorithm to solve a class of multirobot task assignment problems. We formulate task assignment as a mathematical optimization and solve for optimal solutions with a variant of the consensus alternating direction method of multipliers (C-ADMM). We provide C-ADMM-based algorithms for both the primal and dual problem formulations and show the advantages of each form depending on the problem specifics. In our algorithm, each robot solves a series of local optimization problems and communicates the results to its local neighbors, ultimately converging to an optimal task assignment in problems with linear objective functions and an optimal solution of the relaxed problem in convex problems. While many other distributed algorithms require a central station for their implementation, in our algorithm, each robot only communicates with its one-hop neighbors. In linear task assignment problems, our algorithm converges to the optimal task assignment, unlike many other distributed algorithms for this problem, which yield suboptimal solutions. We demonstrate our algorithms in task assignment problems over a variety of communication network topologies, where we show that our inexact dual algorithm is at least 60% faster than other distributed algorithms, which produce an optimal task assignment. In addition, our dual algorithm attains a 69% speedup in computation time compared to a notable distributed variant of the Hungarian method (Chopra et al., 2017). We also apply our algorithm to a multi-unmanned-aerial-vehicle persistent surveillance problem, showing its suitability for problems involving periodic task assignments.
13 February 2024 in IEEE Robotics & Automation Magazine
Distributed optimization provides a framework for deriving distributed algorithms for a variety of multi-robot problems. This tutorial constitutes the first part of a two-part series on distributed optimization applied to multi-robot problems, which seeks to advance the application of distributed optimization in robotics. In this tutorial, we demonstrate that many canonical multi-robot problems can be cast within a distributed optimization framework, such as multi-robot simultaneous localization and mapping (SLAM), multi-robot target tracking, and multi-robot task assignment problems. We identify three broad categories of distributed optimization algorithms: distributed first-order (DFO) methods, distributed sequential convex programming, and the alternating direction method of multipliers (ADMM). We describe the basic algorithmic structure of each category and provide representative algorithms within each category. We then work through a simulation case study of multiple drones collaboratively tracking a ground vehicle. We compare solutions to this problem using a number of different distributed optimization algorithms. In addition, we implement a distributed optimization algorithm in hardware on a network of Raspberry Pis communicating with XBee modules to illustrate robustness to the challenges of real-world communication networks.
1 February 2024 in IEEE Robotics & Automation Magazine
Although the field of distributed optimization is well developed, relevant literature focused on the application of distributed optimization to multi-robot problems is limited. This survey constitutes the second part of a two-part series on distributed optimization applied to multi-robot problems. In this article, we survey three main classes of distributed optimization algorithms—distributed first-order (DFO) methods, distributed sequential convex programming methods, and alternating direction method of multipliers (ADMM) methods—focusing on fully distributed methods that do not require coordination or computation by a central computer. We describe the fundamental structure of each category and note important variations around this structure, designed to address its associated drawbacks. Further, we provide practical implications of noteworthy assumptions made by distributed optimization algorithms, noting the classes of robotics problems suitable for these algorithms. Moreover, we identify important open research challenges in distributed optimization, specifically for robotics problem.
21 April 2023 in IEEE Transactions on Automatic Control
We present a distributed model predictive control method which enables a group of agents to compute their control inputs locally, while communicating with their neighbors over a communication network. While many distributed model predictive control methods require a central station for some coordination or computation of the optimization variables, our method does not require a central station, making our approach applicable to a variety of communication network topologies. With our method, each agent solves for its control inputs without solving for the control inputs of other agents, allowing for efficient optimization by each agent, unlike some other distributed methods. Further, our method attains linear convergence to the optimal control inputs in convex model predictive control problems, improving upon the sub-linear convergence rates provided by some other distributed methods such as dual decomposition methods. Moreover, our algorithm provides a closed-loop controller for convex model predictive control problems with affine constraints. We demonstrate our method in both convex and non-convex model predictive control problems in wireless transceiver alignment and satellite deployment, where we show robustness of our method to time delays.
8 July 2024 in IEEE Transactions on Signal Processing
We present a distributed quasi-Newton (DQN) method, which enables a group of agents to compute an optimal solution of a separable multi-agent optimization problem locally using an approximation of the curvature of the aggregate objective function. Each agent computes a descent direction from its local estimate of the aggregate Hessian, obtained from quasi-Newton approximation schemes using the gradient of its local objective function. Moreover, we introduce a distributed quasi-Newton method for equality-constrained optimization (EC-DQN), where each agent takes Karush-Kuhn-Tucker -like update steps to compute an optimal solution. In our algorithms, each agent communicates with its one-hop neighbors over a peer-to-peer communication network to compute a common solution. We prove convergence of our algorithms to a stationary point of the optimization problem. In addition, we demonstrate the competitive empirical convergence of our algorithm in both well-conditioned and ill-conditioned optimization problems, compared to existing distributed first-order and second-order methods. Particularly, in ill-conditioned problems, our algorithms achieve a faster computation time for convergence, while requiring a lower communication cost, across a range of communication networks with different degrees of connectedness.