Research

Overview

My research program focuses on designing distributed, scalable coordination algorithms for multi-robot systems (multi-agent systems) that exhibit resilience to various robot failures. A critical challenge in this domain is addressing a broad spectrum of adversarial scenarios, ranging from hardware failures (e.g., battery depletion, sensor malfunction/noise, packet loss) to software failures such as random malfunctions or the presence of malicious/deceptive robots.

Much existing literature on multi-robot coordination typically assumes well-behaved agents. Consequently, if a part of the system fails, many pre-existing approaches either cease to function or fail to deliver desired performance. My work directly tackles the complexity introduced by faulty robots being indistinguishable members of the multi-robot system. This distinguishes my problem significantly from multi-robot Game Theory, where agents strategically compute best responses knowing others' non-cooperative behaviors to find a Nash equilibrium. Similarly, it differs from Robust Control, which primarily concerns designing systems insensitive to bounded modeling errors or uncertainties. Instead, my research devises systemic methods to design efficient distributed algorithms for each agent, even without prior knowledge of which neighbors are faulty.

In the scenarios I consider, the system comprises two groups: a cooperative coalition and a team of faulty robots. A primary challenge in designing a distributed motion control strategy for each agent, leveraging only local resources, is the inability to discern faulty neighbors from cooperative ones. Under such conditions, a strategy optimal under the assumption of full cooperation may be inadequate. My work, therefore, emphasizes developing the safest yet efficient strategies. This leads to a fundamental question guiding my work: "What constitutes the most reliable and efficient coordination strategy when cooperative agents cannot discriminate between healthy and faulty neighbors?" Accordingly, performance criteria must solely reflect the efforts of cooperative agents, excluding contributions from faulty robots. By leveraging the inherent redundancy in local resources (e.g., sensor inputs, communication with neighbors), I have found beneficial ways to enhance system robustness through efficient algorithm development.

Thus far, I have investigated robust versions of several crucial multi-robot coordination tasks, specifically rendezvous and sensor coverage, among others (e.g., formation control, distributed estimation, flocking, surveillance, space exploration). For algorithm design, I have incorporated classical techniques from computational and discrete geometry. My developed algorithms collectively minimize a cost function that is sensitive only to fault-free agents. I provide analytical proofs to guarantee the desired robustness and minimal energy requirements, often proving convergence via nonlinear analysis techniques. Numerical results further demonstrate the superior robustness of my proposed algorithms against arbitrarily failing robots in the system, particularly when compared to existing techniques. These advancements often involve tradeoffs, such as increased computational time or reasonably restrictive assumptions on the interconnection topology of the multi-robot system.

Past Projects

A Large-scale Heterogeneous Multi-vehicle Package Pickup and Delivery

This study introduces a groundbreaking, hierarchical solution framework for large-scale Pickup and Delivery Problems (PDPs). Our approach optimally integrates heterogeneous fleets of unmanned vehicles and multiple warehouses to maximize operational efficiency. The formidable combinatorial optimization problem is systematically decomposed into smaller, manageable sub-problems, each assigned to a designated warehouse. These are then efficiently solved using approximate algorithms or heuristics, rendering our method inherently distributed and parallelizable. To orchestrate complex inter-warehouse goods transportation, we propose a novel sequential strategy derived from Mixed Integer Programs (MIPs). Crucially, we provide an asymptotic, probabilistic performance guarantee validated under mild, non-restrictive assumptions. Extensive numerical simulations unequivocally demonstrate our approach's exceptional scalability and high efficiency in terms of both time and energy, showcasing its practical applicability to real-world PDPs and proving substantial advantages over existing methods.

GitHub

Building High-accuracy Precipitation Maps from Windshield Wiper Measurements

This study presents a groundbreaking approach to significantly enhance rainfall field estimates by seamlessly integrating real-time windshield wiper observations from a fleet of nearly 70 connected vehicles with conventional weather radar data. Existing precipitation measurement methods frequently contend with spatial and temporal uncertainties, thus compromising their utility for high-precision applications like flash flood prediction. Connected vehicles emerge as a transformative solution, furnishing precise, localized insights into rainfall timing and intensity via their wiper activity.

Through rigorous empirical analysis of co-located vehicle dashboard camera footage, we unequivocally demonstrate that wiper measurements offer superior predictive capability for binary rainfall state (rain/no-rain) compared to traditional rain gauge or radar-based measurements. Capitalizing on this pivotal finding, we developed a novel Bayesian filtering framework. This framework dynamically refines a radar-derived prior with binary wiper (on/off) observations, yielding robust probabilistic rainfall field estimates. Our results compellingly reveal that the generated data product is exceptionally effective at detecting low-intensity rainfall regions, which are frequently overlooked or underestimated by radar alone.

Scientific Reports 2019 | GitHub

Robust Environmental Mapping by Mobile Sensor Networks

This research introduces an innovative and resilient Bayesian methodology for critical spatial environmental mapping, directly addressing a fundamental deficiency in current approaches: their inability to sustain performance when autonomous agents inevitably experience operational failures. Such commonplace failures, particularly prevalent with economical, fault-prone mapping robots, severely diminish real-world mapping accuracy and can introduce substantial safety hazards. Our proposed solution employs a distributed system of mobile robots equipped with short-range sensors and an ad-hoc communication architecture, explicitly engineered for enhanced resilience against individual hardware malfunctions. The cornerstone of our method involves the strategic decomposition of the mapping region through a specialized Voronoi diagram variant. This is subsequently followed by a decentralized robot deployment strategy meticulously optimized to maximize the aggregate target detection probability within each delineated sub-region, even amidst the ongoing failure of constituent agents. Comprehensive simulations provide compelling evidence of our approach's superior effectiveness and significantly enhanced robustness when contrasted with state-of-the-art techniques.

ICRA 2018 | GitHub

Dynamic Taxi Routing Problem

This study proposes a novel Dynamic Taxi Routing (DTXR) policy tailored for Mobile-on-Demand (MoD) Systems, designed to maintain robust performance across the entire spectrum of traffic load conditions. The core of our innovation lies in a new vehicle-demand assignment methodology meticulously crafted to efficiently manage dynamic pickup-delivery demand pairs. By rigorously extending and applying asymptotic probabilistic results established in prior research on Dynamic Traveling Salesperson Problems (DTSP) and Dynamic Vehicle Routing Problems (DVRP), we formally derive the theoretical performance bounds for our proposed policies under various limiting regimes. A significant theoretical contribution is the proven guarantee that our policy attains performance within a constant factor of the global optimum in the heavy load limit, while simultaneously demonstrating inherent stability under all conceivable load conditions. To empirically validate the practical effectiveness and scalability of the proposed policy, an extensive suite of numerical simulations, parameterized by real-world yellow cab operational data, is systematically conducted and analyzed.

A Matrix Representation of Dial-A-Ride Problem

This paper develops a novel and computationally highly efficient algorithm for the Multiple Vehicle Pickup and Delivery Problem (MVPDP), specifically designed to minimize total tour cost. Central to this is a new 0–1 Integer Quadratic Programming (IQP) formulation that provides an exact solution to the MVPDP. Notably, this IQP model fundamentally reduces the required constraints and decision variables compared to contemporary Mixed Integer Linear Programming (MILP) approaches. Ensuring its computational tractability, we establish a set of sufficient conditions guaranteeing the convexity of this formulation upon integer variable relaxation. Furthermore, we delineate a transformation method to convert any non-convex MVPDP IQP into an equivalent convex representation. Comprehensive simulated and real-world experiments conclusively demonstrate the unparalleled computational efficacy of this convex IQP method over existing MILP formulations.

arXiv Paper | Source Code