OpenRaiser/Intern-Atlas huggingface dataset:
Ensuring Progress for Multiple Mobile Robots via Space Partitioning, Motion Rules, and Adaptively Centralized Conflict Resolution
Venue: arXiv cs.RO 2022
Year: 2022

In environments where multiple robots must coordinate in a shared space, decentralized approaches allow for decoupled planning at the cost of global guarantees, while centralized approaches make the opposite trade-off. These solutions make a range of assumptions - commonly, that all the robots share the same planning strategies. In this work, we present a framework that ensures progress for all robots without assumptions on any robot's planning strategy by (1) generating a partition of the environment into "flow", "open", and "passage" regions and (2) imposing a set of rules for robot motion in these regions. These rules for robot motion prevent deadlock through an adaptively centralized protocol for resolving spatial conflicts between robots. Our proposed framework ensures progress for all robots without a grid-like discretization of the environment or strong requirements on robot communication, coordination, or cooperation. Each robot can freely choose how to plan and coordinate for itself, without being vulnerable to other robots or groups of robots blocking them from their goals, as long as they follow the rules when necessary. We describe our space partition and motion rules, prove that the motion rules suffice to guarantee progress in partitioned environments, and demonstrate several cases in simulated polygonal environments. This work strikes a balance between each robot's planning independence and a guarantee that each robot can always reach any goal in finite time.
Are Gross Substitutes a Substitute for Submodular Valuations?
Venue: arXiv cs.GT 2022
Year: 2022

The class of gross substitutes (GS) set functions plays a central role in Economics and Computer Science. GS belongs to the hierarchy of {\em complement free} valuations introduced by Lehmann, Lehmann and Nisan, along with other prominent classes: $GS \subsetneq Submodular \subsetneq XOS \subsetneq Subadditive$. The GS class has always been more enigmatic than its counterpart classes, both in its definition and in its relation to the other classes. For example, while it is well understood how closely the Submodular, XOS and Subadditive classes (point-wise) approximate one another, approximability of these classes by GS remained wide open. Our main result is the existence of a submodular valuation (one that is also budget additive) that cannot be approximated by GS within a ratio better than $Ω(\frac{\log m}{\log\log m})$, where $m$ is the number of items. En route, we uncover a new symmetrization operation that preserves GS, which may be of independent interest. We show that our main result is tight with respect to budget additive valuations. Additionally, for a class of submodular functions that we refer to as {\em concave of Rado} valuations (this class greatly extends budget additive valuations), we show approximability by GS within an $O(\log^2m)$ factor.
Yoneda Hacking: The Algebra of Attacker Actions
Venue: arXiv cs.CR 2022
Year: 2022

Our work focuses on modeling the security of systems from their component-level designs. Towards this goal, we develop a categorical formalism to model attacker actions. Equipping the categorical formalism with algebras produces two interesting results for security modeling. First, using the Yoneda lemma, we can model attacker reconnaissance missions. In this context, the Yoneda lemma shows us that if two system representations, one being complete and the other being the attacker's incomplete view, agree at every possible test, they behave the same. The implication is that attackers can still successfully exploit the system even with incomplete information. Second, we model the potential changes to the system via an exploit. An exploit either manipulates the interactions between system components, such as providing the wrong values to a sensor, or changes the components themselves, such as controlling a global positioning system (GPS). One additional benefit of using category theory is that mathematical operations can be represented as formal diagrams, helpful in applying this analysis in a model-based design setting. We illustrate this modeling framework using an unmanned aerial vehicle (UAV) cyber-physical system model. We demonstrate and model two types of attacks (1) a rewiring attack, which violates data integrity, and (2) a rewriting attack, which violates availability.
PRISM: A Rich Class of Parameterized Submodular Information Measures for Guided Subset Selection
Venue: arXiv cs.CV 2022
Year: 2022

With ever-increasing dataset sizes, subset selection techniques are becoming increasingly important for a plethora of tasks. It is often necessary to guide the subset selection to achieve certain desiderata, which includes focusing or targeting certain data points, while avoiding others. Examples of such problems include: i)targeted learning, where the goal is to find subsets with rare classes or rare attributes on which the model is underperforming, and ii)guided summarization, where data (e.g., image collection, text, document or video) is summarized for quicker human consumption with specific additional user intent. Motivated by such applications, we present PRISM, a rich class of PaRameterIzed Submodular information Measures. Through novel functions and their parameterizations, PRISM offers a variety of modeling capabilities that enable a trade-off between desired qualities of a subset like diversity or representation and similarity/dissimilarity with a set of data points. We demonstrate how PRISM can be applied to the two real-world problems mentioned above, which require guided subset selection. In doing so, we show that PRISM interestingly generalizes some past work, therein reinforcing its broad utility. Through extensive experiments on diverse datasets, we demonstrate the superiority of PRISM over the state-of-the-art in targeted learning and in guided image-collection summarization
Siamese Labels Auxiliary Learning
Venue: arXiv cs.AI 2022
Year: 2022

In deep learning, auxiliary training has been widely used to assist the training of models. During the training phase, using auxiliary modules to assist training can improve the performance of the model. During the testing phase, auxiliary modules can be removed, so the test parameters are not increased. In this paper, we propose a novel auxiliary training method, Siamese Labels Auxiliary Learning (SiLa). Unlike Deep Mutual Learning (DML), SiLa emphasizes auxiliary learning and can be easily combined with DML. In general, the main work of this paper include: (1) propose SiLa Learning, which improves the performance of common models without increasing test parameters; (2) compares SiLa with DML and proves that SiLa can improve the generalization of the model; (3) SiLa is applied to Dynamic Neural Networks, and proved that SiLa can be used for various types of network structures.
Neuron Coverage-Guided Domain Generalization
Venue: arXiv cs.LG 2022
Year: 2022

This paper focuses on the domain generalization task where domain knowledge is unavailable, and even worse, only samples from a single domain can be utilized during training. Our motivation originates from the recent progresses in deep neural network (DNN) testing, which has shown that maximizing neuron coverage of DNN can help to explore possible defects of DNN (i.e., misclassification). More specifically, by treating the DNN as a program and each neuron as a functional point of the code, during the network training we aim to improve the generalization capability by maximizing the neuron coverage of DNN with the gradient similarity regularization between the original and augmented samples. As such, the decision behavior of the DNN is optimized, avoiding the arbitrary neurons that are deleterious for the unseen samples, and leading to the trained DNN that can be better generalized to out-of-distribution samples. Extensive studies on various domain generalization tasks based on both single and multiple domain(s) setting demonstrate the effectiveness of our proposed approach compared with state-of-the-art baseline methods. We also analyze our method by conducting visualization based on network dissection. The results further provide useful evidence on the rationality and effectiveness of our approach.
Axiomatic Explanations for Visual Search, Retrieval, and Similarity Learning
Venue: arXiv cs.LG 2022
Year: 2022

Visual search, recommendation, and contrastive similarity learning power technologies that impact billions of users worldwide. Modern model architectures can be complex and difficult to interpret, and there are several competing techniques one can use to explain a search engine's behavior. We show that the theory of fair credit assignment provides a $\textit{unique}$ axiomatic solution that generalizes several existing recommendation- and metric-explainability techniques in the literature. Using this formalism, we show when existing approaches violate "fairness" and derive methods that sidestep these shortcomings and naturally handle counterfactual information. More specifically, we show existing approaches implicitly approximate second-order Shapley-Taylor indices and extend CAM, GradCAM, LIME, SHAP, SBSM, and other methods to search engines. These extensions can extract pairwise correspondences between images from trained $\textit{opaque-box}$ models. We also introduce a fast kernel-based method for estimating Shapley-Taylor indices that require orders of magnitude fewer function evaluations to converge. Finally, we show that these game-theoretic measures yield more consistent explanations for image similarity architectures.
Online Partial Service Hosting at the Edge
Venue: arXiv cs.NI 2022
Year: 2022

We consider the problem of service hosting where an application provider can dynamically rent edge computing resources and serve user requests from the edge to deliver a better quality of service. A key novelty of this work is that we allow the service to be hosted partially at the edge which enables a fraction of the user query to be served by the edge. We model the total cost for (partially) hosting a service at the edge as a combination of the latency in serving requests, the bandwidth consumption, and the time-varying cost for renting edge resources. We propose an online policy called $α$-RetroRenting ($α$-RR) which dynamically determines the fraction of the service to be hosted at the edge in any time-slot, based on the history of the request arrivals and the rent cost sequence. As our main result, we derive an upper bound on $α$-RR's competitive ratio with respect to the offline optimal policy that knows the entire request arrival and rent cost sequence in advance. We conduct extensive numerical evaluations to compare the performance of $α$-RR with various benchmarks for synthetic and trace-based request arrival and rent cost processes, and find several parameter regimes where $α$-RR's ability to store the service partially greatly improves cost-efficiency.
Dynamic collision avoidance for multiple robotic manipulators based on a non-cooperative multi-agent game
Venue: arXiv cs.RO 2022
Year: 2022

A flexible operation of multiple robotic manipulators in a shared workspace requires an online trajectory planning with static and dynamic collision avoidance. In this work, we propose a real-time capable motion control algorithm, based on non-linear model predictive control, which accounts for static and dynamic collision avoidance. The proposed algorithm is formulated as a non-cooperative game, where each robot is considered as an agent. Each agent optimizes its own motion and accounts for the predicted movement of surrounding agents. We propose a novel approach to formulate the dynamic collision constraints. Additionally, we account for deadlocks that might occur in a setup of multiple robotic manipulators. We validate our algorithm on a pick and place scenario for four collaborative robots operating in a common workspace in the simulation environment Gazebo. The robots are controlled by the Robot Operating System (ROS). We demonstrate, that our approach is real-time capable and, due to the distributed nature of the approach, easily scales to an arbitrary number of robot manipulators in a shared workspace.
Generative Adversarial Transformers
Venue: arXiv cs.CV 2022
Year: 2022

We introduce the GANformer, a novel and efficient type of transformer, and explore it for the task of visual generative modeling. The network employs a bipartite structure that enables long-range interactions across the image, while maintaining computation of linear efficiency, that can readily scale to high-resolution synthesis. It iteratively propagates information from a set of latent variables to the evolving visual features and vice versa, to support the refinement of each in light of the other and encourage the emergence of compositional representations of objects and scenes. In contrast to the classic transformer architecture, it utilizes multiplicative integration that allows flexible region-based modulation, and can thus be seen as a generalization of the successful StyleGAN network. We demonstrate the model's strength and robustness through a careful evaluation over a range of datasets, from simulated multi-object environments to rich real-world indoor and outdoor scenes, showing it achieves state-of-the-art results in terms of image quality and diversity, while enjoying fast learning and better data-efficiency. Further qualitative and quantitative experiments offer us an insight into the model's inner workings, revealing improved interpretability and stronger disentanglement, and illustrating the benefits and efficacy of our approach. An implementation of the model is available at https://github.com/dorarad/gansformer.
Autobahn: Automorphism-based Graph Neural Nets
Venue: arXiv cs.LG 2022
Year: 2022

We introduce Automorphism-based graph neural networks (Autobahn), a new family of graph neural networks. In an Autobahn, we decompose the graph into a collection of subgraphs and apply local convolutions that are equivariant to each subgraph's automorphism group. Specific choices of local neighborhoods and subgraphs recover existing architectures such as message passing neural networks. Our formalism also encompasses novel architectures: as an example, we introduce a graph neural network that decomposes the graph into paths and cycles. The resulting convolutions reflect the natural way that parts of the graph can transform, preserving the intuitive meaning of convolution without sacrificing global permutation equivariance. We validate our approach by applying Autobahn to molecular graphs, where it achieves results competitive with state-of-the-art message passing algorithms.
Masked Face Recognition: Human vs. Machine
Venue: arXiv cs.CV 2022
Year: 2022

The recent COVID-19 pandemic has increased the focus on hygienic and contactless identity verification methods. However, the pandemic led to the wide use of face masks, essential to keep the pandemic under control. The effect of wearing a mask on face recognition (FR) in a collaborative environment is a currently sensitive yet understudied issue. Recent reports have tackled this by evaluating the masked probe effect on the performance of automatic FR solutions. However, such solutions can fail in certain processes, leading to performing the verification task by a human expert. This work provides a joint evaluation and in-depth analyses of the face verification performance of human experts in comparison to state-of-the-art automatic FR solutions. This involves an extensive evaluation by human experts and 4 automatic recognition solutions. The study concludes with a set of take-home messages on different aspects of the correlation between the verification behavior of humans and machines.
Developing NOMA to Next Generation Multiple Access (NGMA): Future Vision and Research Opportunities
Venue: arXiv cs.IT 2022
Year: 2022

As a prominent member of the next generation multiple access (NGMA) family, non-orthogonal multiple access (NOMA) has been recognized as a promising multiple access candidate for the sixth-generation (6G) networks. This article focuses on applying NOMA in 6G networks, with an emphasis on proposing the so-called "One Basic Principle plus Four New" concept. Starting with the basic NOMA principle, the importance of successive interference cancellation (SIC) becomes evident. In particular, the advantages and drawbacks of both the channel state information based SIC and quality-of-service based SIC are discussed. Then, the application of NOMA to meet the new 6G performance requirements, especially for massive connectivity, is explored. Furthermore, the integration of NOMA with new physical layer techniques is considered, followed by introducing new application scenarios for NOMA towards 6G. Finally, the application of machine learning in NOMA networks is investigated, ushering in the machine learning empowered NGMA era.
Enabling Visual Action Planning for Object Manipulation through Latent Space Roadmap
Venue: arXiv cs.RO 2022
Year: 2022

We present a framework for visual action planning of complex manipulation tasks with high-dimensional state spaces, focusing on manipulation of deformable objects. We propose a Latent Space Roadmap (LSR) for task planning which is a graph-based structure globally capturing the system dynamics in a low-dimensional latent space. Our framework consists of three parts: (1) a Mapping Module (MM) that maps observations given in the form of images into a structured latent space extracting the respective states as well as generates observations from the latent states, (2) the LSR which builds and connects clusters containing similar states in order to find the latent plans between start and goal states extracted by MM, and (3) the Action Proposal Module that complements the latent plan found by the LSR with the corresponding actions. We present a thorough investigation of our framework on simulated box stacking and rope/box manipulation tasks, and a folding task executed on a real robot.
Alleviation of Temperature Variation Induced Accuracy Degradation in Ferroelectric FinFET Based Neural Network
Venue: arXiv cs.LG 2022
Year: 2022

This paper reports the impacts of temperature variation on the inference accuracy of pre-trained all-ferroelectric FinFET deep neural networks, along with plausible design techniques to abate these impacts. We adopted a pre-trained artificial neural network (N.N.) with 96.4% inference accuracy on the MNIST dataset as the baseline. As an aftermath of temperature change, a compact model captured the conductance drift of a programmed cell over a wide range of gate biases. We observed a significant inference accuracy degradation in the analog neural network at 233 K for an N.N. trained at 300 K. Finally, we deployed binary neural networks with "read voltage" optimization to ensure immunity of N.N. to accuracy degradation under temperature variation, maintaining an inference accuracy of 96%. Keywords: Ferroelectric memories
Distributed Dynamic Map Fusion via Federated Learning for Intelligent Networked Vehicles
Venue: arXiv cs.LG 2022
Year: 2022

The technology of dynamic map fusion among networked vehicles has been developed to enlarge sensing ranges and improve sensing accuracies for individual vehicles. This paper proposes a federated learning (FL) based dynamic map fusion framework to achieve high map quality despite unknown numbers of objects in fields of view (FoVs), various sensing and model uncertainties, and missing data labels for online learning. The novelty of this work is threefold: (1) developing a three-stage fusion scheme to predict the number of objects effectively and to fuse multiple local maps with fidelity scores; (2) developing an FL algorithm which fine-tunes feature models (i.e., representation learning networks for feature extraction) distributively by aggregating model parameters; (3) developing a knowledge distillation method to generate FL training labels when data labels are unavailable. The proposed framework is implemented in the Car Learning to Act (CARLA) simulation platform. Extensive experimental results are provided to verify the superior performance and robustness of the developed map fusion and FL schemes.
Matroid Secretary Is Equivalent to Contention Resolution
Venue: arXiv cs.DS 2022
Year: 2022

We show that the matroid secretary problem is equivalent to correlated contention resolution in the online random-order model. Specifically, the matroid secretary conjecture is true if and only if every matroid admits an online random-order contention resolution scheme which, given an arbitrary (possibly correlated) prior distribution over subsets of the ground set, matches the balance ratio of the best offline scheme for that distribution up to a constant. We refer to such a scheme as universal. Our result indicates that the core challenge of the matroid secretary problem lies in resolving contention for positively correlated inputs, in particular when the positive correlation is benign in as much as offline contention resolution is concerned. Our result builds on our previous work which establishes one direction of this equivalence, namely that the secretary conjecture implies universal random-order contention resolution, as well as a weak converse, which derives a matroid secretary algorithm from a random-order contention resolution scheme with only partial knowledge of the distribution. It is this weak converse that we strengthen in this paper: We show that universal random-order contention resolution for matroids, in the usual setting of a fully known prior distribution, suffices to resolve the matroid secretary conjecture in the affirmative. Our proof is the composition of three reductions. First, we use duality arguments to reduce the matroid secretary problem to the matroid prophet secretary problem with arbitrarily correlated distributions. Second, we introduce a generalization of contention resolution we term labeled contention resolution, to which we reduce the correlated matroid prophet secretary problem. Finally, we combine duplication of elements with limiting arguments to reduce labeled contention resolution to classical contention resolution.
GANav: Efficient Terrain Segmentation for Robot Navigation in Unstructured Outdoor Environments
Venue: arXiv cs.RO 2022
Year: 2022

We propose GANav, a novel group-wise attention mechanism to identify safe and navigable regions in off-road terrains and unstructured environments from RGB images. Our approach classifies terrains based on their navigability levels using coarse-grained semantic segmentation. Our novel group-wise attention loss enables any backbone network to explicitly focus on the different groups' features with low spatial resolution. Our design leads to efficient inference while maintaining a high level of accuracy compared to existing SOTA methods. Our extensive evaluations on the RUGD and RELLIS-3D datasets shows that GANav achieves an improvement over the SOTA mIoU by 2.25-39.05% on RUGD and 5.17-19.06% on RELLIS-3D. We interface GANav with a deep reinforcement learning-based navigation algorithm and highlight its benefits in terms of navigation in real-world unstructured terrains. We integrate our GANav-based navigation algorithm with ClearPath Jackal and Husky robots, and observe an increase of 10% in terms of success rate, 2-47% in terms of selecting the surface with the best navigability and a decrease of 4.6-13.9% in trajectory roughness. Further, GANav reduces the false positive rate of forbidden regions by 37.79%. Code, videos, and a full technical report are available at https://gamma.umd.edu/offroad/.