Hierarchical Planning for Heterogeneous Multi-Robot Routing Problems via Learned Subteam Performance

A recent paper by members of the DCIST alliance proposes a new hierarchical planner for task allocation problems where tasks correspond to heterogeneous multi-robot routing problems defined on different areas of a given environment. The researchers tackled this complex planning problem with a novel planner which breaks down the complexity of the original problem into two subproblems: the high-level problem of allocating robots to routing tasks, and the low-level problem of computing the actual routing paths for each subteam. The planner uses a Graph Neural Network (GNN) as a heuristic to estimate subteam performance for specific coalitions on specific routing tasks. It then iteratively refines the estimates to the real subteam performances as solutions of the low-level problems become available. On a testbed problem having an area inspection problem as the base routing task, the experiments show that the new hierarchical planner is able to compute optimal or near-optimal (within 7%) solutions approximately 16 times faster (on average) than an optimal baseline that computes plans for all the possible allocations in advance to obtain precise routing times. The experiments also show that a GNN-based estimator can provide an excellent trade-off between solution quality and computation time compared to other baseline (non-learned) estimators.

Capabilities: T2C1 E+G (Simultaneous Task Assignment and Planning)

Points of Contact: Nicholas Roy (PI) and Jacopo Banfi

Video: N/A

Paper: https://ieeexplore.ieee.org/document/9705621

Citation: J. Banfi, A. Messing, C. Kroninger, E. Stump, S. Hutchinson, N. Roy. “Hierarchical Planning for Heterogeneous Multi-Robot Routing Problems via Learned Subteam Performance.” IEEE Robotics and Automation Letters, to appear (2022).

CORSAIR: Convolutional Object Retrieval and Symmetry-AIded Registration

This paper considers online object-level mapping using partial point-cloud observations obtained online in an unknown environment. We develop an approach for fully Convolutional Object Retrieval and Symmetry-AIded Registration (CORSAIR). Our model extends the Fully Convolutional Geometric Features (FCGF) model to learn a global object-shape embedding in addition to local point-wise features from the point-cloud observations. The global feature is used to retrieve a similar object from a category database, and the local features are used for robust pose registration between the observed and the retrieved object. Our formulation also leverages symmetries, present in the object shapes, to obtain promising local-feature pairs from different symmetry classes for matching. We present results from synthetic and real-world datasets with different object categories to verify the robustness of our method.

Capability: T1C1A: Multi-Modal Representations of Knowledge

Points of Contact: Nikolay Atanasov (PI) and Qiaojun Feng

Video: https://youtu.be/uIr4Q08BKqo 

Paper: https://arxiv.org/pdf/2103.06911

Citation: T. Zhao, Q. Feng, S. Jadhav and N. Atanasov, “CORSAIR: Convolutional Object Retrieval and Symmetry-AIded Registration,” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2021

Robust multimodal data association

A fundamental problem in robotic perception is matching identical objects or data, with applications such as loop closure detection, place recognition, object tracking, and map fusion. The problem becomes more challenging when matching is done jointly across multiple, multimodal sets of data, however, the robustness and accuracy of matching in the presence of noise and outliers is greatly improved in this setting. At present, multimodal techniques do not leverage multiway information, and multiway techniques do not incorporate different modalities, leading to inferior results. To address this issue, members of the DCIST alliance developed a principled mixed-integer quadratic framework to formulate the multimodal, multiway data association, and a novel algorithm, called Multimodality association matrIX fusER (MIXER), to find solutions. MIXER uses a continuous relaxation in a projected gradient descent scheme that guarantees feasible solutions of the integer program are obtained efficiently. Experiments demonstrated that correspondences obtained from MIXER are more stable to noise and errors than state-of-the-art techniques. Tested on a robotics dataset, MIXER resulted in a 35% increase in the accuracy of data association (measured as the F1 score) when compared to the best alternative.

Capability: T1C1C

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

Video: NA

Paper: https://arxiv.org/pdf/2111.14990.pdf

Citation: P. C. Lusk, R. Roy, K. Fathian, J. P. How, “MIXER: A Principled Framework for Multimodal, Multiway Data Association,” in IEEE ICRA workshop on robust perception, 2021.

ELLIPSDF: Joint Object Pose and Shape Optimization with a Bi-level Ellipsoid and Signed Distance Function Description

A recent paper by members of the DCIST alliance develops a method for tightly coupled object shape and pose optimization. Inspired by DeepSDF, which uses neural networks to regress a Signed Distance Function (SDF) description of object shape, they propose a bi-level object shape model named ELLIPSDF, to support joint object pose and shape optimization. At the coarse level, ELLIPSDF uses an ellipsoid model as it provides simple geometric constraints for object pose and scale initialization. A latent shape vector and an SDF neural network decoder are used at the fine level. The bi-level object model of ELLIPSDF allows initialization of object pose and scale from multi-view bounding-box measurements, followed by joint pose and ellipsoid-SDF shape optimization. ELLIPSDF was validated via large-scale experiments on the ScanNet dataset with multiple object categories.

Figure: Visualization of intermediate ELLIPSDF stages. First column: RGB image, depth image, instance segmentation (yellow), fitted ellipse (red) for a chair in ScanNet scene 0461. Second column: mean shape and ellipsoid with initialized pose. Third column: optimized fine-level and coarse-level shapes with optimized pose.

 

Capability: T1C1A – Multi-Modal Representations of Knowledge

Points of Contact: Nikolay Atanasov (PI) and Mo Shan 

Video: https://youtu.be/qVqr8j5E0ho

Paper: https://arxiv.org/pdf/2108.00355.pdf

Citation: M. Shan, Q. Feng, Y. Jau and N. Atanasov, “ELLIPSDF: Joint Object Pose and Shape Optimization with a Bi-level Ellipsoid and Signed Distance Function Description,” IEEE/CVF International Conference on Computer Vision (ICCV), 2021.

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

Video: https://youtu.be/QYLHueMhShY

Paper: https://arxiv.org/pdf/2011.10202.pdf

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

Video: https://youtu.be/_73vd4Jk41E

Paper: https://arxiv.org/pdf/2101.01831.pdf

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

Video: https://drive.google.com/file/d/1brjo6cXhx3aWEE3A7HTCfOsLkXSeEOHm/view?usp=sharing  

Paper: https://scalar.seas.upenn.edu/wp-content/uploads/2021/12/Mansfield_IROS2021.pdf 

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 

Paper: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9387108 

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

Video: https://youtu.be/Qgt64a0bOiA

Paper: https://arxiv.org/pdf/2103.05819.pdf

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

Paper: https://arxiv.org/pdf/2103.10383.pdf

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