OpenRaiser/Intern-Atlas huggingface dataset:
Motion Estimation in Occupancy Grid Maps in Stationary Settings Using Recurrent Neural Networks
Venue: arXiv cs.RO 2022
Year: 2022

In this work, we tackle the problem of modeling the vehicle environment as dynamic occupancy grid map in complex urban scenarios using recurrent neural networks. Dynamic occupancy grid maps represent the scene in a bird's eye view, where each grid cell contains the occupancy probability and the two dimensional velocity. As input data, our approach relies on measurement grid maps, which contain occupancy probabilities, generated with lidar measurements. Given this configuration, we propose a recurrent neural network architecture to predict a dynamic occupancy grid map, i.e. filtered occupancy and velocity of each cell, by using a sequence of measurement grid maps. Our network architecture contains convolutional long-short term memories in order to sequentially process the input, makes use of spatial context, and captures motion. In the evaluation, we quantify improvements in estimating the velocity of braking and turning vehicles compared to the state-of-the-art. Additionally, we demonstrate that our approach provides more consistent velocity estimates for dynamic objects, as well as, less erroneous velocity estimates in static area.
Model Pruning Enables Efficient Federated Learning on Edge Devices
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning (FL) allows model training from local data collected by edge/mobile devices while preserving data privacy, which has wide applicability to image and vision applications. A challenge is that client devices in FL usually have much more limited computation and communication resources compared to servers in a datacenter. To overcome this challenge, we propose PruneFL -- a novel FL approach with adaptive and distributed parameter pruning, which adapts the model size during FL to reduce both communication and computation overhead and minimize the overall training time, while maintaining a similar accuracy as the original model. PruneFL includes initial pruning at a selected client and further pruning as part of the FL process. The model size is adapted during this process, which includes maximizing the approximate empirical risk reduction divided by the time of one FL round. Our experiments with various datasets on edge devices (e.g., Raspberry Pi) show that: (i) we significantly reduce the training time compared to conventional FL and various other pruning-based methods; (ii) the pruned model with automatically determined size converges to an accuracy that is very similar to the original model, and it is also a lottery ticket of the original model.
Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width
Venue: arXiv cs.DS 2022
Year: 2022

The two weighted graph problems Node Multiway Cut (NMC) and Subset Feedback Vertex Set (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects all cycles containing a vertex of a given set. We design a meta-algorithm that allows to solve both problems in time $2^{O(rw^3)}\cdot n^{4}$, $2^{O(q^2\log(q))}\cdot n^{4}$, and $n^{O(k^2)}$ where $rw$ is the rank-width, $q$ the $\mathbb{Q}$-rank-width, and $k$ the mim-width of a given decomposition. This answers in the affirmative an open question raised by Jaffke et al. (Algorithmica, 2019) concerning an XP algorithm for SFVS parameterized by mim-width. By a unified algorithm, this solves both problems in polynomial-time on the following graph classes: Interval, Permutation, and Bi-Interval graphs, Circular Arc and Circular Permutation graphs, Convex graphs, $k$-Polygon, Dilworth-$k$ and Co-$k$-Degenerate graphs for fixed $k$; and also on Leaf Power graphs if a leaf root is given as input, on $H$-Graphs for fixed $H$ if an $H$-representation is given as input, and on arbitrary powers of graphs in all the above classes. Prior to our results, only SFVS was known to be tractable restricted only on Interval and Permutation graphs, whereas all other results are new.
Never Worse, Mostly Better: Stable Policy Improvement in Deep Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

In recent years, there has been significant progress in applying deep reinforcement learning (RL) for solving challenging problems across a wide variety of domains. Nevertheless, convergence of various methods has been shown to suffer from inconsistencies, due to algorithmic instability and variance, as well as stochasticity in the benchmark environments. Particularly, despite the fact that the agent's performance may be improving on average, it may abruptly deteriorate at late stages of training. In this work, we study methods for enhancing the agent's learning process, by providing conservative updates with respect to either the obtained history or a reference benchmark policy. Our method, termed EVEREST, obtains high confidence improvements via confidence bounds of a reference policy. Through extensive empirical analysis we demonstrate the benefit of our approach in terms of both performance and stabilization, with significant improvements in continuous control and Atari benchmarks.
Distributed Attack-Robust Submodular Maximization for Multi-Robot Planning
Venue: arXiv cs.RO 2022
Year: 2022

In this paper, we design algorithms to protect swarm-robotics applications against sensor denial-of-service (DoS) attacks on robots. We focus on applications requiring the robots to jointly select actions, e.g., which trajectory to follow, among a set of available ones. Such applications are central in large-scale robotic applications, such as multi-robot motion planning for target tracking. But the current attack-robust algorithms are centralized. In this paper, we propose a general-purpose distributed algorithm towards robust optimization at scale, with local communications only. We name it Distributed Robust Maximization (DRM). DRM proposes a divide-and-conquer approach that distributively partitions the problem among cliques of robots. Then, the cliques optimize in parallel, independently of each other. We prove DRM achieves a close-to-optimal performance. We demonstrate DRM's performance in both Gazebo and MATLAB simulations, in scenarios of active target tracking with swarms of robots. In the simulations, DRM achieves computational speed-ups, being 1-2 orders faster than the centralized algorithms; yet, it nearly matches the tracking performance of the centralized counterparts. Since, DRM overestimates the number of attacks in each clique, in this paper we also introduce an Improved Distributed Robust Maximization (IDRM) algorithm. IDRM infers the number of attacks in each clique less conservatively than DRM by leveraging 3-hop neighboring communications. We verify IDRM improves DRM's performance in simulations.
The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs
Venue: arXiv cs.DB 2022
Year: 2022

We study the problem of query evaluation on probabilistic graphs, namely, tuple-independent probabilistic databases over signatures of arity two. We focus on the class of queries closed under homomorphisms, or, equivalently, the infinite unions of conjunctive queries. Our main result states that the probabilistic query evaluation problem is #P-hard for all unbounded queries from this class. As bounded queries from this class are equivalent to a union of conjunctive queries, they are already classified by the dichotomy of Dalvi and Suciu (2012). Hence, our result and theirs imply a complete data complexity dichotomy, between polynomial time and #P-hardness, on evaluating homomorphism-closed queries over probabilistic graphs. This dichotomy covers in particular all fragments of infinite unions of conjunctive queries over arity-two signatures, such as negation-free (disjunctive) Datalog, regular path queries, and a large class of ontology-mediated queries. The dichotomy also applies to a restricted case of probabilistic query evaluation called generalized model counting, where fact probabilities must be 0, 0.5, or 1. We show the main result by reducing from the problem of counting the valuations of positive partitioned 2-DNF formulae, or from the source-to-target reliability problem in an undirected graph, depending on properties of minimal models for the query.
A Closed Queueing Maintenance Network with Two Batch Policies
Venue: arXiv cs.PF 2022
Year: 2022

This paper discusses a maintenance network with failed items that can be removed, repaired, redistributed, and reused under two batch policies: one for removing the failed items from each base to a maintenance shop and the other for redistributing the repaired items from the maintenance shop to bases. This maintenance network can be considered a virtual closed queueing network, and the Markov system of each node is described as an elegant block-structured Markov process whose stationary probabilities can be computed by the RG-factorizations. The structure of this maintenance network is novel and interesting. To compute the closed queueing network, we set up a new nonlinear matrix equation to determine the relative arrival rates, in which the nonlinearity comes from two different groups of processes: the failure and removal processes and the repair and redistribution processes. This paper also extends a simple queueing system of a node to a more general block-structured Markov process which can be computed by the RG-factorizations. Based on this, the paper establishes a more general product-form solution for the closed queueing network and provides performance analysis of the maintenance network. Our method will open a new avenue for quantitative evaluation of more general maintenance networks.
FIS-GAN: GAN with Flow-based Importance Sampling
Venue: arXiv cs.LG 2022
Year: 2022

Generative Adversarial Networks (GAN) training process, in most cases, apply Uniform or Gaussian sampling methods in the latent space, which probably spends most of the computation on examples that can be properly handled and easy to generate. Theoretically, importance sampling speeds up stochastic optimization in supervised learning by prioritizing training examples. In this paper, we explore the possibility of adapting importance sampling into adversarial learning. We use importance sampling to replace Uniform and Gaussian sampling methods in the latent space and employ normalizing flow to approximate latent space posterior distribution by density estimation. Empirically, results on MNIST and Fashion-MNIST demonstrate that our method significantly accelerates GAN's optimization while retaining visual fidelity in generated samples.
A Penalized Inequality-Constrained Approach for Robust Beamforming with DoF Limitation
Venue: arXiv cs.IT 2022
Year: 2022

A well-known challenge in beamforming is how to optimally utilize the degrees of freedom (DoF) of the array to design a robust beamformer, especially when the array DoF is limited. In this paper, we leverage the tool of constrained convex optimization and propose a penalized inequality-constrained minimum variance (P-ICMV) beamformer to address this challenge. Specifically, a well-targeted objective function and inequality constraints are proposed to achieve the design goals. By penalizing the maximum gain of the beamformer at any interfering directions, the total interference power can be efficiently mitigated with limited DoF. Multiple robust constraints on the target protection and interference suppression can be introduced to increase the robustness of the beamformer against steering vector mismatch. By integrating the noise reduction, interference suppression, and target protection, the proposed formulation can efficiently obtain a robust beamformer design while optimally trading off various design goals. To numerically solve this problem, we formulate the P-ICMV beamformer design as a convex second-order cone program (SOCP) and propose a low complexity iterative algorithm based on the alternating direction method of multipliers (ADMM). Three applications are simulated to demonstrate the effectiveness of the proposed beamformer.
FASHION: Functional and Attack graph Secured HybrId Optimization of virtualized Networks
Venue: arXiv cs.NI 2022
Year: 2022

Maintaining a resilient computer network is a delicate task with conflicting priorities. Flows should be served while controlling risk due to attackers. Upon publication of a vulnerability, administrators scramble to manually mitigate risk while waiting for a patch. We introduce FASHION: a linear optimizer that balances routing flows with the security risk posed by these flows. FASHION formalizes routing as a multi-commodity flow problem with side constraints. FASHION formulates security using two approximations of risk in a probabilistic attack graph (Frigault et al., Network Security Metrics 2017). FASHION's output is a set of software-defined networking rules consumable by Frenetic (Foster et al., ICFP 2011). We introduce a topology generation tool that creates data center network instances including flows and vulnerabilities. FASHION is executed on instances of up to 600 devices, thousands of flows, and million edge attack graphs. Solve time averages 30 minutes on the largest instances (seconds on the smallest instances). To ensure the security objective is accurate, the output solution is assessed using risk as defined by Frigault et al. FASHION allows enterprises to reconfigure their network in response to changes in functionality or security requirements.
Good, Better, Best: Textual Distractors Generation for Multiple-Choice Visual Question Answering via Reinforcement Learning
Venue: arXiv cs.CV 2022
Year: 2022

Multiple-choice VQA has drawn increasing attention from researchers and end-users recently. As the demand for automatically constructing large-scale multiple-choice VQA data grows, we introduce a novel task called textual Distractors Generation for VQA (DG-VQA) focusing on generating challenging yet meaningful distractors given the context image, question, and correct answer. The DG-VQA task aims at generating distractors without ground-truth training samples since such resources are rarely available. To tackle the DG-VQA unsupervisedly, we propose Gobbet, a reinforcement learning(RL) based framework that utilizes pre-trained VQA models as an alternative knowledge base to guide the distractor generation process. In Gobbet, a pre-trained VQA model serves as the environment in RL setting to provide feedback for the input multi-modal query, while a neural distractor generator serves as the agent to take actions accordingly. We propose to use existing VQA models' performance degradation as indicators of the quality of generated distractors. On the other hand, we show the utility of generated distractors through data augmentation experiments, since robustness is more and more important when AI models apply to unpredictable open-domain scenarios or security-sensitive applications. We further conduct a manual case study on the factors why distractors generated by Gobbet can fool existing models.
FutureMapping 2: Gaussian Belief Propagation for Spatial AI
Venue: arXiv cs.AI 2022
Year: 2022

We argue the case for Gaussian Belief Propagation (GBP) as a strong algorithmic framework for the distributed, generic and incremental probabilistic estimation we need in Spatial AI as we aim at high performance smart robots and devices which operate within the constraints of real products. Processor hardware is changing rapidly, and GBP has the right character to take advantage of highly distributed processing and storage while estimating global quantities, as well as great flexibility. We present a detailed tutorial on GBP, relating to the standard factor graph formulation used in robotics and computer vision, and give several simulation examples with code which demonstrate its properties.
Perceived Intensities of Normal and Shear Skin Stimuli using a Wearable Haptic Bracelet
Venue: arXiv cs.RO 2022
Year: 2022

Our aim is to provide effective interaction with virtual objects, despite the lack of co-location of virtual and real-world contacts, while taking advantage of relatively large skin area and ease of mounting on the forearm. We performed two human participant studies to determine the effects of haptic feedback in the normal and shear directions during virtual manipulation using haptic devices worn near the wrist. In the first study, participants performed significantly better while discriminating stiffness values of virtual objects when the feedback consisted of normal displacements compared to shear displacements. Participants also commented that they could detect normal cues much easier than shear, which motivated us to perform a second study to find the point of subjective equality (PSE) between normal and shear stimuli. Our results show that shear stimuli require a larger actuator displacement but less force than normal stimuli to achieve perceptual equality for our haptic bracelets. We found that normal and shear stimuli cannot be equalized through skin displacement nor the interaction forces across all users. Rather, a calibration method is needed to find the point of equality for each user where normal and shear stimuli create the same intensity on the user's skin.
Building an Aerial-Ground Robotics System for Precision Farming: An Adaptable Solution
Venue: arXiv cs.RO 2022
Year: 2022

The application of autonomous robots in agriculture is gaining increasing popularity thanks to the high impact it may have on food security, sustainability, resource use efficiency, reduction of chemical treatments, and the optimization of human effort and yield. With this vision, the Flourish research project aimed to develop an adaptable robotic solution for precision farming that combines the aerial survey capabilities of small autonomous unmanned aerial vehicles (UAVs) with targeted intervention performed by multi-purpose unmanned ground vehicles (UGVs). This paper presents an overview of the scientific and technological advances and outcomes obtained in the project. We introduce multi-spectral perception algorithms and aerial and ground-based systems developed for monitoring crop density, weed pressure, crop nitrogen nutrition status, and to accurately classify and locate weeds. We then introduce the navigation and mapping systems tailored to our robots in the agricultural environment, as well as the modules for collaborative mapping. We finally present the ground intervention hardware, software solutions, and interfaces we implemented and tested in different field conditions and with different crops. We describe a real use case in which a UAV collaborates with a UGV to monitor the field and to perform selective spraying without human intervention.
Investigating the relationship between graph eigenvector ordering and the signal processing dual
Venue: arXiv cs.IT 2022
Year: 2022

Graph signal processing uses the graph eigenvector basis to analyze signals. However, these graph eigenvectors are typically linearly ordered (by total variation), which may not be reasonable for many graph structures. There have been structure based similarity metrics proposed in the literature that better capture the geometry of graph eigenvectors. On the other hand, there has been work that attempts to generalize the concept of duality to graph signal processing. The (signal processing) the dual graph captures the relationship between graph frequencies and is obtained by typically inverting the graph Fourier transform operation. In this work, we investigate the connections between these two concepts. We propose a dualness measure of two graphs, which quantifies how close the graphs are being (signal processing) duals of each other. We show that this definition satisfies some desirable properties and develop an algorithm based on coordinate descent and perfect matching to compute an approximation to dualness. By computing the dualness measure, we observe that for structured graphs, the similarity metric-based techniques give a better dual graph (and vice-versa for ER graphs), suggesting a potentially novel approach unifying the two methods.
Approval-Based Apportionment
Venue: arXiv cs.GT 2022
Year: 2022

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters can support multiple parties by casting approval ballots. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates instead of parties. Using techniques from both apportionment and multiwinner elections, we identify rules that generalize the D'Hondt apportionment method and that satisfy strong axioms which are generalizations of properties commonly studied in the apportionment literature. In fact, the rules we discuss provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity (also known as house monotonicity).
Bribery in Rating Systems: A Game-Theoretic Perspective
Venue: arXiv cs.GT 2022
Year: 2022

Rating systems play a vital role in the exponential growth of service-oriented markets. As highly rated online services usually receive substantial revenue in the markets, malicious sellers seek to boost their service evaluation by manipulating the rating system with fake ratings. One effective way to improve the service evaluation is to hire fake rating providers by bribery. The fake ratings given by the bribed buyers influence the evaluation of the service, which further impacts the decision-making of potential buyers. In this paper, we study the bribery of a rating system with multiple sellers and buyers via a game-theoretic perspective. In detail, we examine whether there exists an equilibrium state in the market in which the rating system is expected to be bribery-proof: no bribery strategy yields a strictly positive gain. We first collect real-world data for modeling the bribery problem in rating systems. On top of that, we analyze the problem of bribery in a rating system as a static game. From our analysis, we conclude that at least a Nash equilibrium can be reached in the bribery game of rating systems.
Fast Polynomial Kernel Classification for Massive Data
Venue: arXiv cs.LG 2022
Year: 2022

In the era of big data, it is desired to develop efficient machine learning algorithms to tackle massive data challenges such as storage bottleneck, algorithmic scalability, and interpretability. In this paper, we develop a novel efficient classification algorithm, called fast polynomial kernel classification (FPC), to conquer the scalability and storage challenges. Our main tools are a suitable selected feature mapping based on polynomial kernels and an alternating direction method of multipliers (ADMM) algorithm for a related non-smooth convex optimization problem. Fast learning rates as well as feasibility verifications including the efficiency of an ADMM solver with convergence guarantees and the selection of center points are established to justify theoretical behaviors of FPC. Our theoretical assertions are verified by a series of simulations and real data applications. Numerical results demonstrate that FPC significantly reduces the computational burden and storage memory of existing learning schemes such as support vector machines, Nyström and random feature methods, without sacrificing their generalization abilities much.