Robust data association in high-outlier regimes

Establishing correspondence between two sets of data is a fundamental problem in robotics, and is required for fusing data across multiple DCIST agents to establish global situational awareness. Real-world data contains noise and outliers. The traditional linear assignment algorithms are not robust to high-outlier regimes, leading to incorrect correspondences. To address these issues,  members of the DCIST alliance developed CLIPPER (Consistent LInking, Pruning, and Pairwise Error Rectification), a framework for robust data association in the presence of noise and outliers. CLIPPER formulates the problem in a graph-theoretic framework using the notion of geometric consistency. State-of-the-art techniques that use this framework utilize either combinatorial optimization techniques that do not scale well to large-sized problems, or use heuristic approximations that yield low accuracy in high-outlier regimes. In contrast, CLIPPER uses a computationally efficient relaxation of the combinatorial problem and provides optimality guarantees for the generated solution. Low time complexity is achieved with an efficient projected gradient ascent approach. Experiments demonstrated that CLIPPER maintains a consistently low runtime of 15 ms where exact methods can require up to 24 s at their peak, even on small-sized problems with 200 associations. When evaluated on noisy point cloud registration problems, CLIPPER achieves 100% precision in 90% outlier regimes while competing algorithms begin degrading by 70% outliers. 

Capability: T1C1C

Points of Contact: Jonathan How (PI), Kaveh Fathian



Citation: P. C. Lusk, K. Fathian, J. P. How, “CLIPPER: A Graph-Theoretic Framework for Robust Data Association,” in IEEE ICRA, 2021.

Active Bayesian Multi-class Mapping from Range and Semantic Segmentation Observation

Many robot applications call for autonomous exploration and mapping of unknown and unstructured environments. Information-based exploration techniques, such as Cauchy-Schwarz quadratic mutual information (CSQMI) and fast Shannon mutual information (FSMI), have successfully achieved active binary occupancy mapping with range measurements. However, as we envision robots performing complex tasks specified with semantically meaningful objects, it is necessary to capture semantic categories in the measurements, map representation, and exploration objective. This work develops a Bayesian multi-class mapping algorithm utilizing range-category measurements. We derive a closed-form efficiently computable lower bound for the Shannon mutual information between the multi-class map and the measurements. The bound allows rapid evaluation of many potential robot trajectories for autonomous exploration and mapping. We compare our method against frontier-based and FSMI exploration and apply it in a 3-D photo-realistic simulation environment.

Capability: T3C1A: Active Multi-Robot Information Acquisition

Points of Contact: Nikolay Atanasov (PI) and Arash Asgharivaskasi



Citation: A. Asgharivaskasi and N. Atanasov, “Active Bayesian Multi-class Mapping from Range and Semantic Segmentation Observations,” IEEE International Conference on Robotics and Automation (ICRA), 2021.

Multi-robot Scheduling for Environmental Monitoring as a Team Orienteering Problem

We develop an evolutionary algorithm for solving the multi-robot orienteering problem where a team of cooperative robots aims to maximize the total information collected by visiting a subset of given nodes within a fixed budget on travel costs. Multi-robot orienteering problems are relevant to applications such as logistic delivery services, precision agriculture, and environmental sampling and monitoring. They consider the case where the information gain at each node is related to the service time each robot spends at the node. As such, they address a variant of the Orienteering Problem where the collected rewards are a function of the time a robot spends at a given location. They present a genetic algorithm solver to this cooperative Team Orienteering Problem with service-time dependent rewards. The researchers evaluate the approach over a diverse set of node configurations and for different team sizes. Lastly, they evaluate the effects of team heterogeneity on overall task performance through numerical simulations.

Capability: T3C4B Heterogeneous Multi-Robot Systems for Modeling & Prediction of Multiscale Spatiotemporal Processes

Points of Contact: M. Ani Hseih (PI) and Ariella Mansfield



Citation: A. Mansfield, S. Manjanna, D. G. Macharet, M. A. Hsieh “Multi-robot Scheduling for Environmental Monitoring as a Team Orienteering Problem.” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2021), September 2021.

Optimizing Non-Markovian Information Gain Under Physics-Based Communication Constraints

A recent paper by members of DCIST proposes an exploration method that maintains communication between all robot team members and a static base station. By maintaining communication while exploring, robots are kept up to date on the progress of other team members and important information—e.g., survivors in a search and rescue mission—are quickly transmitted to a static base station. Their method uses a combination of optimization and sampling to quickly find paths for each robot that maintains communication, then optimizes the paths to maximize the information gain relative to the total path cost. Their method is verified using a realistic communication model and obtains 2-5 times more information relative to a path’s cost than other state of the art works.

Capability: T3C2E: Adversarial network and motion synthesis 

Points of Contact: Neil Dantam (PI), Qi Han, John Rogers, and Matthew Schack 


Citation: M. A. Schack, J. G. Rogers, Q. Han, and N. T. Dantam, “Optimizing non-markovian information gain under physics-based communication constraints,” IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 4813–4819, 2021. 

Active Exploration and Mapping via Iterative Covariance Regulation over Continuous SE(3) Trajectories

A recent paper by the members of the DCIST alliance develops a method for continuous-space optimal control of active information acquisition. They have developed “iterative Covariance Regulation (iCR)”, a novel method for an information-theoretic active perception performing multi-step forward-backward gradient descent. The problem is formalized as SE(3) trajectory optimization over a multi-step continuous control sequence of a robot’s linear and angular velocity inputs to minimize the differential entropy of a map state conditioned on a sequence of measurements (e.g., Lidar or RGB-D camera). To ensure that the covariance matrix evolution is differentiable with respect to the control sequence, they introduced a new differentiable field of view formulation for the sensing model, providing a smooth transition from unobserved to observed space in the environment. Finally, the gradient of the objective function with respect to the multi-step control input sequence is computed explicitly and the control trajectory is updated via gradient descent. iCR algorithm was tested in simulated active mapping experiments in comparison with two baseline methods and they observed that iCR achieves significantly larger reduction of the map uncertainty due to its continuous-space optimization.

Capability: T3C1D: Optimal control and reinforcement learning with information theoretic objectives

Points of Contact: Nikolay Atanasov (PI), Shumon Koga, and Arash Asgharivaskasi



Citation: S. Koga, A. Asgharivaskasi, and N. Atanasov “Active Exploration and Mapping via Iterative Covariance Regulation over Continuous SE(3) Trajectories”, In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2021.

Heterogeneous robot teams for modeling and prediction of multiscale environmental processes

We present a framework to enable a team of heterogeneous mobile robots to model and sense a multiscale system. Their approach proposes a coupled strategy, where robots of one type collect high-fidelity measurements at a slow time scale and robots of another type collect low-fidelity measurements at a fast time scale, for the purpose of fusing measurements together. The multiscale measurements are fused to create a model of a complex, nonlinear spatiotemporal process. The model helps determine optimal sensing locations and predict the evolution of the process. The researchers’ contributions are: i) consolidation of multiple types of data into one cohesive model, ii) fast determination of optimal sensing locations for mobile robots, and iii) adaptation of models online for various monitoring scenarios. They illustrate the proposed framework by modeling and predicting the evolution of an artificial plasma cloud. They also test the approach using physical marine robots adaptively sampling a process in a water tank.

Figure: Heterogeneous robots collecting different sensing information work to create a cohesive model of a time varying environment. Aerial vehicles collect low-fidelity sensor measurements, such as overhead images, over a wide area, and marine vehicles collect high-fidelity sensor measurements, such as current speeds, over a small area. Sensor measurements are unified into one model for estimation and prediction of a time varying process

Capability: T3C4B – Heterogeneous Multi-Robot Systems for Modeling and Prediction of Multiscale Spatiotemporal Processes

Points of Contact: M. Ani Hsieh (PI) and Tahiya Salam


Citation: T. Salam, M. A. Hsieh “Heterogeneous robot teams for modeling and prediction of multiscale environmental processes.” arXiv preprint arXiv:2103.10383, March 2021.

Resilience in multi-robot multi-target tracking with unknown number of targets through reconfiguration

A recent paper by members of the DCIST alliance addresses the problem of maintaining resource availability in a networked multi-robot team performing distributed tracking of an unknown number of targets. Robots receive and process sensor measurements locally and exchange information to cooperatively track a set of targets using a distributed Probability Hypothesis Density (PHD) filter. Each robot’s sensor measurement noise covariance matrix is used to quantify its sensing quality. If a robot’s sensor quality degrades, the team’s communication network is minimally reconfigured such that the robot with the faulty sensor may take better advantage of information from other robots to lessen the impact on overall team tracking performance. without enforcing a large change in the number of active communication links. Two PHD fusion methods are studied and four different Mixed Integer Semi-Definite Programming (MISDP) formulations (two formulations for each fusion method) are proposed to solve the problem.

Figure: Resilient target tracking. (Left) One of the tracker robots in the team experiences a sensor fault, thereby affecting the team’s tracking performance. (Right) The team has reconfigured to realize a new communication graph in 3D. Tracking performance has improved compared to what it was immediately after the robot’s sensor fault.

Capability: T2C3

Points of Contact: Gaurav Sukhatme (PI), Ragesh Kumar Ramachandran


Citation: R. K. Ramachandran, N. Fronda and G. S. Sukhatme, “Resilience in Multirobot Multitarget Tracking With Unknown Number of Targets Through Reconfiguration,” in IEEE Transactions on Control of Network Systems, vol. 8, no. 2, pp. 609-620, June 2021, doi: 10.1109/TCNS.2021.3059794.

Distributed Certifiably Correct Pose-Graph Optimization

Recent work by members of the DCIST alliance presents the first certifiably correct algorithm for distributed pose-graph optimization (PGO), the backbone of modern collaborative simultaneous localization and mapping (CSLAM) and camera network localization (CNL) systems. The proposed method is based upon a sparse semidefinite relaxation that provably provides globally-optimal PGO solutions under moderate measurement noise (matching the guarantees enjoyed by state-of-the-art centralized methods), but is amenable to distributed optimization using the low-rank Riemannian Staircase framework. To implement the Riemannian Staircase in the distributed setting, the paper develops Riemannian block coordinate descent (RBCD), a novel method for (locally) minimizing a function over a product of Riemannian manifolds. The paper also proposes the first distributed solution verification and saddle escape methods to certify the global optimality of critical points recovered via RBCD, and to descend from suboptimal critical points (if necessary). All components of the proposed approach are inherently decentralized: they require only local communication, provide privacy protection, and are easily parallelizable. Extensive evaluations on synthetic and real-world datasets demonstrate that the proposed method correctly recovers globally optimal solutions under moderate noise, and outperforms alternative distributed techniques in terms of solution precision and convergence speed.

Capability: T1C1C

Points of Contact: Jonathan How (PI), Yulun Tian



Citation: Y. Tian, K. Khosoussi, D. M. Rosen and J. P. How, “Distributed Certifiably Correct Pose-Graph Optimization,” in IEEE Transactions on Robotics, Dec. 2021,

Kimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems

Recent work by members of the DCIST alliance presents Kimera-Multi, a multi-robot system that (i) is robust and capable of identifying and rejecting incorrect inter and intra-robot loop closures resulting from perceptual aliasing, (ii) is fully distributed and only relies on local (peer-to-peer) communication to achieve distributed localization and mapping, and (iii) builds a globally consistent metric-semantic 3D mesh model of the environment in real-time, where faces of the mesh are annotated with semantic labels. Kimera-Multi is implemented by a team of robots equipped with visual-inertial sensors. Each robot builds a local trajectory estimate and a local mesh using Kimera, an open-source library developed under DCIST: When communication is available, robots initiate a distributed place recognition procedure to detect inter-robot loop closures. Subsequently, robots perform distributed trajectory estimation using distributed pose graph optimization (PGO), a technology recently developed under DCIST ( Distributed PGO, in combination with a newly developed distributed graduated non-convexity technique, allows the robots to accurately estimate their trajectories by leveraging inter-robot loop closures while being robust to outliers. Finally, each robot uses its improved trajectory estimate to correct the local mesh using mesh deformation techniques.

Kimera-Multi has been tested in photo-realistic simulations, SLAM benchmarking datasets, and challenging outdoor datasets collected using ground robots. Kimera-Multi has been demonstrated to (i) outperform the state of the art in terms of robustness and accuracy, (ii) achieve estimation errors comparable to a centralized SLAM system while being fully distributed, (iii) is parsimonious in terms of communication bandwidth, (iv) produces accurate metric-semantic 3D meshes, and (v) is modular and can be also used for standard 3D reconstruction (without semantic labels) or for trajectory estimation (without reconstructing a 3D mesh).


Capability: T1C1

Points of Contact: Luca Carlone (PI), Jonathan How (PI), Yun Chang, Yulun Tian


Kimera-Multi: Medfield Demonstration

Kimera-Multi: a System for Distributed Multi-Robot Metric-Semantic SLAM 



Chang, Yun, et al. “Kimera-Multi: A System for Distributed Multi-Robot Metric-Semantic Simultaneous Localization and Mapping.” 2021 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2021, pp. 11210–18. (Crossref),

Tian, Yulun, et al. “Kimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems.” IEEE Transactions on Robotics (T-RO), 2021 (to appear).,

Learning and Leveraging Environmental Features to Improve Robot Awareness

A recent paper by the members of the DCIST alliance studies how global dynamics and knowledge of high-level features can inform decision-making for robots in flow-like environments. Specifically, they investigate how coherent sets, an environmental feature found in these environments, inform robot awareness within these scenarios. The proposed approach is an online environmental feature generator which can be used for robot reasoning. They compute coherent sets online with techniques from machine learning and design frameworks for robot behavior that leverage coherent set features. The researchers demonstrate the effectiveness of online methods over offline methods. Notably, they apply these online methods for robot monitoring of pedestrian behaviors and robot navigation through water. Environmental features such as coherent sets provide rich context to robots for smarter, more efficient behavior.

Figure: Diagram of interplay between data, transfer operators, kernel methods, and environmental features. Transfer operators represent dynamical systems, where a state is lifted to a high-dimensional space and this lifting provides physical properties of the system. Many systems are defined by data exhibiting complex patterns, such as two nested rings, flows in oceans, taxi trajectories, and biological behaviors. Kernel methods transform this data to an alternative space with the use of kernel functions. Data is then easier to interpret, such as by separating two nested rings or by creating a Gram matrix for use in a kernel algorithm. Transfer operators are represented through kernel methods by embedding dynamical systems into a kernel space. Kernel algorithms extract environmental features from transfer operators, such as where humans tend to congregate in crowds, areas of gyres in oceans, or patterns of blood flow in hearts

Capability: T3C4B – Heterogeneous Multi-Robot Systems for Modeling and Prediction of Multiscale Spatiotemporal Processes

Points of Contact: M. Ani Hsieh (PI), Tahiya Salam, and Victoria Edwards



Citation: T. Salam, V. Edwards, M. A. Hsieh “Learning and Leveraging Environmental Features to Improve Robot Awareness.” arXiv preprint arXiv:2109.06107, September 2021.