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

/0 Comments/in /by

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

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

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

/0 Comments/in /by

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

Video: https://youtu.be/PpFMTGNJpaA

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

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, https://arxiv.org/pdf/1911.03721.pdf

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

/0 Comments/in /by

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: https://github.com/MIT-SPARK/Kimera. 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 (https://github.com/mit-acl/dpgo). 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

Video:

Kimera-Multi: Medfield Demonstration

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

Paper: 

https://arxiv.org/pdf/2011.04087.pdf 

https://arxiv.org/pdf/2106.14386.pdf 

Citation: 

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. DOI.org (Crossref), https://doi.org/10.1109/ICRA48506.2021.9561090.

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). arXiv.org, http://arxiv.org/abs/2106.14386.

Learning and Leveraging Environmental Features to Improve Robot Awareness

/0 Comments/in /by

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

Video: https://youtu.be/D-4S6hnFr2E

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

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

Coding for Distributed Multi-Agent Reinforcement Learning

/0 Comments/in /by

A recent paper by the members of the DCIST alliance develops a multi-agent reinforcement learning (MARL) algorithm which uses coding theory to mitigate straggler effects in distributed training. Stragglers are delayed, non-responsive or compromised compute nodes, which occur commonly in distributed learning systems, due to communication bottlenecks and adversarial conditions. Coding techniques have been utilized to speed up distributed computation tasks in the presence of stragglers, such as matrix multiplications and inverse problems. Their proposed coded distributed learning framework can be applied with any policy gradient method to train policies for MARL problems in the presence of stragglers. They develop a coded distributed version of multi-agent deep deterministic policy gradient (MADDPG), a state-of-the-art MARL algorithm. To gain a comprehensive understanding of the benefits of coding in distributed MARL, they investigated various coding schemes, including the maximum distance separable (MDS) code, random sparse code, replication-based code, and regular low density parity check (LDPC) code. All of these methods were implemented in simulation on several multi-robot problems, including cooperative navigation, predator-prey, physical deception and keep-away tasks. Their approach achieves the same training accuracy while significantly speeding up the training of policy gradient algorithms in the presence of stragglers.

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

Points of Contact: Nikolay Atanasov (PI), Baoqian Wang, and Junfei Xie

Video: https://youtu.be/B8WMjzRHoh0

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

Citation: B. Wang, J. Xie, and N. Atanasov “Coding for Distributed Multi-Agent Reinforcement Learning”, IEEE International Conference on Robotics and Automation (ICRA), 2021.

Intermittent Interactions on Multi-Agent Systems: Diffusion of Information and Consensus Control

/0 Comments/in /by

Recent works by members of the DCIST alliance investigate methods to handle consensus and broadcast of information tasks in networks of mobile robots subject to intermittent communication. The effort of this work is to alleviate the restriction of an all-time connected network, letting agents interact periodically and taking into consideration the uncertainty associated with those events. Hence, the time-varying communication topology is modeled as an inhomogeneous stochastic process with finite states and time-varying transition matrices belonging to a convex set. This modeling allows deriving new conditions for the consensus under stochastic interactions between robots. In the proposed methodology, the results follow from the transformation of the consensus problem into a stability problem of stochastic jumping systems, with the subsequent employment of the Lyapunov theory. The conditions are formulated in terms of convex optimization problems. In addition, the broadcasting of information in such a networked system is also investigated. To estimate the statistics of the broadcasting, the stochastic process associated with the changing topologies is utilized, but in this scenario governing a switching in an augmented state-space that maps the transmission of information in the network. The results are presented in the form of sufficient conditions for the convergence and lemmas used to estimate the expected time to the transmission of information between any two nodes in the network.

Left:  Time evolution for six agents interacting over a stochastic switching topology. Blue diamonds represent initial conditions and black solid lines the system’s trajectories. Middle and Right: Time evolution of the time-varying topology (up left), control signals (bottom left), and states (up and bottom right). On the time-varying topology (top left) topology 1 means all agents are disconnected, and the union of topology 2 and 3 form a connected graph.

Capability: T3C2D Synthesis of Time-Varying Communication Networks with Information Propagation Guarantees

Points of Contact: M. Ani Hsieh (PI), Xi Yu, Li Shen, and Thales C. Silva

Citation: 

Li Shen, Xi Yu, and M. Ani Hsieh. “Topology Control of a Periodic Time-varying Communication Network with Stochastic Temporal Links,” submitted to the 2022 American Control Conference, Under Review.

C. Silva and M. A. Hsieh, “Intermittent Interactions on Multi-Agent Systems: Diffusion of Information and Consensus Control” In preparation.

Intermittently Connected Mobile Robot Networks with Information Propagation Guarantees

/0 Comments/in /by

DCIST researchers pioneered strategies for teams of mobile robots to form intermittently connected communication networks by leveraging their mobility.  Robots assigned to monitor and patrol large urban environments can leverage their movements to carry information to other robots that are not within their communication ranges. Our work shows intermittent connectivity between pairs of robots can be achieved by synchronizing the robots’ motions and ensuring robots rendezvous or move into each other’s communication ranges periodically.  And while the network is not fully connected at any instance in time, it is guaranteed to be connected over a predetermined period of time ensuring the successful propagation of information across the entire network.  In addition, these strategies can be extended to guarantee resiliency of the mobile robot network in the presence of non-cooperative robots.  Resilience for a large intermittently connected mobile robot network is achieved by concatenating modular dynamic formations where each module is guaranteed to be resilient by design.

Left: The creation of a time-varying periodically connected in an urban environment by a team of mobile robots tasked to patrol different buildings.  Right: Two examples of time-varying networks formed using lattice modules.  Red nodes represent malicious agents.  Plots on the right show consensus formation in the network over time.

Capability: T3C2C Mobility to Extend Communication Networks 

Points of Contact: M. Ani Hsieh (PI), Xi Yu, Daigo Shishika, David Saldana

Paper: https://10.1109/LRA.2020.2967704, https://10.1109/TRO.2021.3088765 

Citation: X. Yu and M. A. Hsieh, “Synthesis of a time-varying communication network by robot teams with information propagation guarantees,” IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 1413–1420,2020.

Yu, D. Shishika, D. Saldana and M. A. Hsieh. “Modular Robot Formation and Routing for Resilient Consensus,” in the Proc. of the 2020 IEEE American Control Conference (ACC 2020), Jul 2020 (Virtual).

X. Yu, D. Saldana, D. Shishika, and M. A. Hsieh.“Resilient Consensus in Robot Swarms with Periodic Motion and Intermittent Communication,” in IEEE Transactions on Robotics and Automation (T-RO), 2021.

Learning Connectivity-Maximizing Network Configurations

/0 Comments/in /by

A recent paper by members of the DCIST alliance develops a data-driven method for providing mobile wireless infrastructure on demand to multi-robot teams requiring communication in order to collaboratively achieve a common objective. While a considerable amount of research has been devoted to this problem, existing solutions do not scale in a manner suitable for online applications for more than a handful of agents. To address this problem, the researchers propose a supervised learning approach with a convolutional neural network (CNN) that learns to place communication agents from an expert that uses an optimization-based strategy. After detailing training and CNN architecture choices, they demonstrate the performance of their CNN on canonical network topologies, randomly generated test cases, and larger teams not seen during training. They also show how the system can be applied to dynamic robot teams through a Unity-based simulation. Their approach provides connected networks orders of magnitude faster than the optimization-based scheme while achieving comparable performance.

Capability: T3C2A – Learning Configurations in Mobile Infrastructure on Demand

Points of Contact: Alejandro Ribeiro (PI) and Daniel Mox

Video: https://youtu.be/YLgxFJdN9hg

Paper: https://arxiv.org/abs/2112.07663

Citation: Daniel Mox, Vijay Kumar, and Alejandro Ribeiro. “Learning Connectivity-Maximizing Network Configurations.” arXiv preprint arXiv:2112.07663 (2021).

Dynamic Defender-Attacker Resource Allocation Game

/0 Comments/in /by

A recent paper by members of the DCIST alliance proposes a new resource allocation game that studies a dynamic, adversarial resource allocation problem in environments modeled as graphs. By combining ideas from Colonel Blotto games with a population dynamics model, the proposed formulation incorporates: (i) dynamic reallocation in time-varying situations, and (ii) the presence of adversarial agents. A blue team of defender robots are deployed in the environment to protect the nodes from a red team of attacker robots. The engagement is formulated a discrete-time dynamic game, where the robots can move at most one hop in each time step. The game terminates with the attacker’s win if any location has more attacker robots than defender robots at any time. The goal is to identify dynamic resource allocation strategies, as well as the conditions that determine the winner: graph structure, available resources, and initial conditions. The authors analyze the problem using reachable sets and show how the outdegree of the underlying graph directly influences the difficulty of the defending task. Furthermore, they provide algorithms that identify sufficiency of the attacker’s victory. The proposed model has a potential for being extended to various scenarios to study dynamic and adversarial engagement between robots with traversability constraints.

Capability: T2C1B: Distributed Control for Dynamic Resource Allocation in Adversarial Environments

Points of Contact: Daigo Shishika (PI), Scott Guan, Michael Dorothy 

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

Citation: Daigo Shishika, Yue Guan, Michael Dorohy, and Vijay Kumar, “Dynamic Defender-Attacker Blotto Game,” (under review), arXiv preprint, arXiv:2112.09890 (2021).

Cooperative Systems Design in Adversarial Environments

/0 Comments/in /by

The Colonel Blotto game describes a scenario where two opposing Colonels strategically allocate their limited resources across multiple battlefields. The game is compelling for a multitude of reasons, having numerous applications in military strategy. Optimal strategies in the Colonel Blotto game are highly complex – the game does not admit pure strategy equilibria in settings of interest. Mixed equilibria have been characterized for special setups in only a handful of landmark papers. These contributions, however, are almost exclusively in a complete information setting. In this thrust, we investigate incomplete and asymmetric information scenarios where the Colonels may have incomplete information regarding the battlefield valuations and the opposing Colonel’s budget. Focusing on the framework of General Lotto games, a well-known variant of Colonel Blotto, we provide a complete analytical characterization of the Bayesian Nash equilibria for all instances of this game. This characterization identifies the “value of information” in such domains, i.e., the performance improvement attainable by having better information.  Lastly, we explore the importance of information dissemination as a strategic component of decision-making in adversarial environments. That is, is it ever strategically advantageous to disclose information about one’s intentions in competitive scenarios.  Surprisingly, the answer is yes and we provide a characterization of when this is the case.

Capability: T2C1H 

Points of Contact: Jason R. Marden (PI), Keith Paarporn, Rahul Chandan 

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

Citation: K. Paarporn, R. Chandan, M. Alizadeh, and J. R. Marden. A General Lotto game with asymmetric budget uncertainty. 2021 (under review).  K. Paarporn et al., “Asymmetric battlefield uncertainty in General Lotto games,” 2021 (under review).