OpenRaiser/Intern-Atlas huggingface dataset:
CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces
Venue: arXiv cs.MA 2022
Year: 2022

Multi-agent path planning (MAPP) in continuous spaces is a challenging problem with significant practical importance. One promising approach is to first construct graphs approximating the spaces, called roadmaps, and then apply multi-agent pathfinding (MAPF) algorithms to derive a set of conflict-free paths. While conventional studies have utilized roadmap construction methods developed for single-agent planning, it remains largely unexplored how we can construct roadmaps that work effectively for multiple agents. To this end, we propose a novel concept of roadmaps called cooperative timed roadmaps (CTRMs). CTRMs enable each agent to focus on its important locations around potential solution paths in a way that considers the behavior of other agents to avoid inter-agent collisions (i.e., "cooperative"), while being augmented in the time direction to make it easy to derive a "timed" solution path. To construct CTRMs, we developed a machine-learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions and then uses the learned model to sample the vertices of CTRMs for new, previously unseen problem instances. Our empirical evaluation revealed that the use of CTRMs significantly reduced the planning effort with acceptable overheads while maintaining a success rate and solution quality comparable to conventional roadmap construction approaches.
Beamforming Towards Seamless Sensing Coverage for Cellular Integrated Sensing and Communication
Venue: arXiv cs.IT 2022
Year: 2022

The sixth generation (6G) mobile communication networks are expected to offer a new paradigm of cellular integrated sensing and communication (ISAC). However, due to the intrinsic difference between sensing and communication in terms of coverage requirement, current cellular networks that are deliberately planned mainly for communication coverage are difficult to achieve seamless sensing coverage. To address this issue, this paper studies the beamforming optimization towards seamless sensing coverage for a basic bi-static ISAC system, while ensuring that the communication requirements of multiple users equipment (UEs) are satisfied. Towards this end, an optimization problem is formulated to maximize the worst-case sensing signal-to-noise ratio (SNR) in a prescribed coverage region, subject to the signal-to-interference-plus-noise ratio (SINR) requirement for each UE. To gain some insights, we first investigate the special case with one single UE and one single sensing point, for which a closed-from expression of the optimal beamforming is obtained. For the general case with multiple communication UEs and contiguous regional sensing coverage, an efficient algorithm based on successive convex approximation (SCA) is proposed to solve the non-convex beamforming optimization problem. Numerical results demonstrate that the proposed design is able to achieve seamless sensing coverage in the prescribed region, while guaranteeing the communication requirements of the UEs.
Problife: a Probabilistic Game of Life
Venue: arXiv cs.AI 2022
Year: 2022

This paper presents a probabilistic extension of the well-known cellular automaton, Game of Life. In Game of Life, cells are placed in a grid and then watched as they evolve throughout subsequent generations, as dictated by the rules of the game. In our extension, called ProbLife, these rules now have probabilities associated with them. Instead of cells being either dead or alive, they are denoted by their chance to live. After presenting the rules of ProbLife and its underlying characteristics, we show a concrete implementation in ProbLog, a probabilistic logic programming system. We use this to generate different images, as a form of rule-based generative art.
Backdoor Defense with Machine Unlearning
Venue: arXiv cs.CR 2022
Year: 2022

Backdoor injection attack is an emerging threat to the security of neural networks, however, there still exist limited effective defense methods against the attack. In this paper, we propose BAERASE, a novel method that can erase the backdoor injected into the victim model through machine unlearning. Specifically, BAERASE mainly implements backdoor defense in two key steps. First, trigger pattern recovery is conducted to extract the trigger patterns infected by the victim model. Here, the trigger pattern recovery problem is equivalent to the one of extracting an unknown noise distribution from the victim model, which can be easily resolved by the entropy maximization based generative model. Subsequently, BAERASE leverages these recovered trigger patterns to reverse the backdoor injection procedure and induce the victim model to erase the polluted memories through a newly designed gradient ascent based machine unlearning method. Compared with the previous machine unlearning solutions, the proposed approach gets rid of the reliance on the full access to training data for retraining and shows higher effectiveness on backdoor erasing than existing fine-tuning or pruning methods. Moreover, experiments show that BAERASE can averagely lower the attack success rates of three kinds of state-of-the-art backdoor attacks by 99\% on four benchmark datasets.
Crowd tracking and monitoring middleware via Map-Reduce
Venue: arXiv cs.DC 2022
Year: 2022

This paper presents the design, implementation, and operation of a novel distributed fault-tolerant middleware. It uses interconnected WSNs that implement the Map-Reduce paradigm, consisting of several low-cost and low-power mini-computers (Raspberry Pi). Specifically, we explain the steps for the development of a novice, fault-tolerant Map-Reduce algorithm which achieves high system availability, focusing on network connectivity. Finally, we showcase the use of the proposed system based on simulated data for crowd monitoring in a real case scenario, i.e., a historical building in Greece (M. Hatzidakis' residence).The technical novelty of this article lies in presenting a viable low-cost and low-power solution for crowd sensing without using complex and resource-intensive AI structures or image and video recognition techniques.
Towards Remote Robotic Competitions: An Internet-Connected Task Board and Dashboard
Venue: arXiv cs.RO 2022
Year: 2022

In this work we present a platform to assess robot platform skills using an internet-of-things (IoT) task board device to aggregate performances across remote sites. We demonstrate a concept for a modular, scale-able device and web dashboard enabling remote competitions as an alternative to in-person robot competitions. We share data from nine robot platforms located across four continents in three manipulation task categories of object localization, object insertion, and component disassembly through an organized international robot competition - the Robothon Grand Challenge. This paper discusses the design of an electronic task board, the strategies implemented by the top-performing teams and compares their results with a benchmark solution to the presented task board. Through this platform, we demonstrate fully remote, online competitions can generate innovative robotic solutions and tested a tool for measuring remote performances. Using the open-sourced task board code and design files, the reader can reproduce the benchmark solution or configure the platform for their own use case and share their results transparently without transporting their robot platform.
Pearl: Parallel Evolutionary and Reinforcement Learning Library
Venue: arXiv cs.LG 2022
Year: 2022

Reinforcement learning is increasingly finding success across domains where the problem can be represented as a Markov decision process. Evolutionary computation algorithms have also proven successful in this domain, exhibiting similar performance to the generally more complex reinforcement learning. Whilst there exist many open-source reinforcement learning and evolutionary computation libraries, no publicly available library combines the two approaches for enhanced comparison, cooperation, or visualization. To this end, we have created Pearl (https://github.com/LondonNode/Pearl), an open source Python library designed to allow researchers to rapidly and conveniently perform optimized reinforcement learning, evolutionary computation and combinations of the two. The key features within Pearl include: modular and expandable components, opinionated module settings, Tensorboard integration, custom callbacks and comprehensive visualizations.
End-to-end Person Search Sequentially Trained on Aggregated Dataset
Venue: arXiv cs.CV 2022
Year: 2022

In video surveillance applications, person search is a challenging task consisting in detecting people and extracting features from their silhouette for re-identification (re-ID) purpose. We propose a new end-to-end model that jointly computes detection and feature extraction steps through a single deep Convolutional Neural Network architecture. Sharing feature maps between the two tasks for jointly describing people commonalities and specificities allows faster runtime, which is valuable in real-world applications. In addition to reaching state-of-the-art accuracy, this multi-task model can be sequentially trained task-by-task, which results in a broader acceptance of input dataset types. Indeed, we show that aggregating more pedestrian detection datasets without costly identity annotations makes the shared feature maps more generic, and improves re-ID precision. Moreover, these boosted shared feature maps result in re-ID features more robust to a cross-dataset scenario.
On-The-Fly Solving for Symbolic Parity Games
Venue: arXiv cs.LO 2022
Year: 2022

Parity games can be used to represent many different kinds of decision problems. In practice, tools that use parity games often rely on a specification in a higher-order logic from which the actual game can be obtained by means of an exploration. For many of these decision problems we are only interested in the solution for a designated vertex in the game. We formalise how to use on-the-fly solving techniques during the exploration process, and show that this can help to decide the winner of such a designated vertex in an incomplete game. Furthermore, we define partial solving techniques for incomplete parity games and show how these can be made resilient to work directly on the incomplete game, rather than on a set of safe vertices. We implement our techniques for symbolic parity games and study their effectiveness in practice, showing that speed-ups of several orders of magnitude are feasible and overhead (if unavoidable) is typically low.
A singular Riemannian geometry approach to Deep Neural Networks I. Theoretical foundations
Venue: arXiv cs.LG 2022
Year: 2022

Deep Neural Networks are widely used for solving complex problems in several scientific areas, such as speech recognition, machine translation, image analysis. The strategies employed to investigate their theoretical properties mainly rely on Euclidean geometry, but in the last years new approaches based on Riemannian geometry have been developed. Motivated by some open problems, we study a particular sequence of maps between manifolds, with the last manifold of the sequence equipped with a Riemannian metric. We investigate the structures induced trough pullbacks on the other manifolds of the sequence and on some related quotients. In particular, we show that the pullbacks of the final Riemannian metric to any manifolds of the sequence is a degenerate Riemannian metric inducing a structure of pseudometric space, we show that the Kolmogorov quotient of this pseudometric space yields a smooth manifold, which is the base space of a particular vertical bundle. We investigate the theoretical properties of the maps of such sequence, eventually we focus on the case of maps between manifolds implementing neural networks of practical interest and we present some applications of the geometric framework we introduced in the first part of the paper.
Variability aware Golden Reference Free methodology for Hardware Trojan Detection Using Robust Delay Analysis
Venue: arXiv cs.AR 2022
Year: 2022

Many fabless semiconductor companies outsource their designs to third-party fabrication houses. As trustworthiness of chain after outsourcing including fabrication houses is not established, any adversary in between, with malicious intent may tamper the design by inserting Hardware Trojans (HTs). Detection of such HTs is of utmost importance to assure the trust and integrity of the chips. However, the efficiency of detection techniques based on side-channel analysis is largely affected by process variations. In this paper, a methodology for detecting HTs by analyzing the delays of topologically symmetric paths is proposed. The proposed technique, rather than depending on golden ICs as a reference for HT detection, employs the concept of self-referencing. In this work, the fact that delays of topologically symmetric paths in an IC will be affected similarly by process variations is exploited. A procedure to chose topologically symmetric paths that are minimally affected by process variations is presented. Further, a technique is proposed to create topologically symmetric paths by inserting extra logic gates if such paths do not exist in the design intrinsically. Simulations performed on ISCAS-85 benchmarks establish that the proposed method is able to achieve a true positive rate of 100% with a false positive rate less than 3%. In our experimentation, We have considered the maximum of 15% intra-die and 20% inter-die variations in threshold voltage (Vth).
Learning Semantics for Visual Place Recognition through Multi-Scale Attention
Venue: arXiv cs.CV 2022
Year: 2022

In this paper we address the task of visual place recognition (VPR), where the goal is to retrieve the correct GPS coordinates of a given query image against a huge geotagged gallery. While recent works have shown that building descriptors incorporating semantic and appearance information is beneficial, current state-of-the-art methods opt for a top down definition of the significant semantic content. Here we present the first VPR algorithm that learns robust global embeddings from both visual appearance and semantic content of the data, with the segmentation process being dynamically guided by the recognition of places through a multi-scale attention module. Experiments on various scenarios validate this new approach and demonstrate its performance against state-of-the-art methods. Finally, we propose the first synthetic-world dataset suited for both place recognition and segmentation tasks.
Reinforcement Learning Textbook
Venue: arXiv cs.LG 2022
Year: 2022

This textbook covers principles behind main modern deep reinforcement learning algorithms that achieved breakthrough results in many domains from game AI to robotics. All required theory is explained with proofs using unified notation and emphasize on the differences between different types of algorithms and the reasons why they are constructed the way they are.
Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
Venue: arXiv cs.DM 2022
Year: 2022

Twin-width is a newly introduced graph width parameter that aims at generalizing a wide range of "nicely structured" graph classes. In this work, we focus on obtaining good bounds on twin-width $\text{tww}(G)$ for graphs $G$ from a number of classic graph classes. We prove the following: - $\text{tww}(G) \leq 3\cdot 2^{\text{tw}(G)-1}$, where $\text{tw}(G)$ is the treewidth of $G$, - $\text{tww}(G) \leq \max(4\text{bw}(G),\frac{9}{2}\text{bw}(G)-3)$ for a planar graph $G$ with $\text{bw}(G) \geq 2$, where $\text{bw}(G)$ is the branchwidth of $G$, - $\text{tww}(G) \leq 183$ for a planar graph $G$, - the twin-width of a universal bipartite graph $(X,2^X,E)$ with $|X|=n$ is $n - \log_2(n) + \mathcal{O}(1)$ . An important idea behind the bounds for planar graphs is to use an embedding of the graph and sphere-cut decompositions to obtain good bounds on neighbourhood complexity.
Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise
Venue: arXiv cs.LG 2022
Year: 2022

We give tight statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. In particular, suppose that all labels are corrupted with probability at most $η$. We show that for arbitrary $η\in [0,1/2]$ every SQ algorithm achieving misclassification error better than $η$ requires queries of superpolynomial accuracy or at least a superpolynomial number of queries. Further, this continues to hold even if the information-theoretically optimal error $\mathrm{OPT}$ is as small as $\exp\left(-\log^c(d)\right)$, where $d$ is the dimension and $0 < c < 1$ is an arbitrary absolute constant, and an overwhelming fraction of examples are noiseless. Our lower bound matches known polynomial time algorithms, which are also implementable in the SQ framework. Previously, such lower bounds only ruled out algorithms achieving error $\mathrm{OPT} + ε$ or error better than $Ω(η)$ or, if $η$ is close to $1/2$, error $η- o_η(1)$, where the term $o_η(1)$ is constant in $d$ but going to 0 for $η$ approaching $1/2$. As a consequence, we also show that achieving misclassification error better than $1/2$ in the $(A,α)$-Tsybakov model is SQ-hard for $A$ constant and $α$ bounded away from 1.
Evolution Gym: A Large-Scale Benchmark for Evolving Soft Robots
Venue: arXiv cs.RO 2022
Year: 2022

Both the design and control of a robot play equally important roles in its task performance. However, while optimal control is well studied in the machine learning and robotics community, less attention is placed on finding the optimal robot design. This is mainly because co-optimizing design and control in robotics is characterized as a challenging problem, and more importantly, a comprehensive evaluation benchmark for co-optimization does not exist. In this paper, we propose Evolution Gym, the first large-scale benchmark for co-optimizing the design and control of soft robots. In our benchmark, each robot is composed of different types of voxels (e.g., soft, rigid, actuators), resulting in a modular and expressive robot design space. Our benchmark environments span a wide range of tasks, including locomotion on various types of terrains and manipulation. Furthermore, we develop several robot co-evolution algorithms by combining state-of-the-art design optimization methods and deep reinforcement learning techniques. Evaluating the algorithms on our benchmark platform, we observe robots exhibiting increasingly complex behaviors as evolution progresses, with the best evolved designs solving many of our proposed tasks. Additionally, even though robot designs are evolved autonomously from scratch without prior knowledge, they often grow to resemble existing natural creatures while outperforming hand-designed robots. Nevertheless, all tested algorithms fail to find robots that succeed in our hardest environments. This suggests that more advanced algorithms are required to explore the high-dimensional design space and evolve increasingly intelligent robots -- an area of research in which we hope Evolution Gym will accelerate progress. Our website with code, environments, documentation, and tutorials is available at http://evogym.csail.mit.edu.
AutoMC: Automated Model Compression based on Domain Knowledge and Progressive search strategy
Venue: arXiv cs.LG 2022
Year: 2022

Model compression methods can reduce model complexity on the premise of maintaining acceptable performance, and thus promote the application of deep neural networks under resource constrained environments. Despite their great success, the selection of suitable compression methods and design of details of the compression scheme are difficult, requiring lots of domain knowledge as support, which is not friendly to non-expert users. To make more users easily access to the model compression scheme that best meet their needs, in this paper, we propose AutoMC, an effective automatic tool for model compression. AutoMC builds the domain knowledge on model compression to deeply understand the characteristics and advantages of each compression method under different settings. In addition, it presents a progressive search strategy to efficiently explore pareto optimal compression scheme according to the learned prior knowledge combined with the historical evaluation information. Extensive experimental results show that AutoMC can provide satisfying compression schemes within short time, demonstrating the effectiveness of AutoMC.
Do Smart Glasses Dream of Sentimental Visions? Deep Emotionship Analysis for Eyewear Devices
Venue: arXiv cs.CV 2022
Year: 2022

Emotion recognition in smart eyewear devices is highly valuable but challenging. One key limitation of previous works is that the expression-related information like facial or eye images is considered as the only emotional evidence. However, emotional status is not isolated; it is tightly associated with people's visual perceptions, especially those sentimental ones. However, little work has examined such associations to better illustrate the cause of different emotions. In this paper, we study the emotionship analysis problem in eyewear systems, an ambitious task that requires not only classifying the user's emotions but also semantically understanding the potential cause of such emotions. To this end, we devise EMOShip, a deep-learning-based eyewear system that can automatically detect the wearer's emotional status and simultaneously analyze its associations with semantic-level visual perceptions. Experimental studies with 20 participants demonstrate that, thanks to the emotionship awareness, EMOShip not only achieves superior emotion recognition accuracy over existing methods (80.2% vs. 69.4%), but also provides a valuable understanding of the cause of emotions. Pilot studies with 20 participants further motivate the potential use of EMOShip to empower emotion-aware applications, such as emotionship self-reflection and emotionship life-logging.
Challenges in Migrating Imperative Deep Learning Programs to Graph Execution: An Empirical Study
Venue: arXiv cs.SE 2022
Year: 2022

Efficiency is essential to support responsiveness w.r.t. ever-growing datasets, especially for Deep Learning (DL) systems. DL frameworks have traditionally embraced deferred execution-style DL code that supports symbolic, graph-based Deep Neural Network (DNN) computation. While scalable, such development tends to produce DL code that is error-prone, non-intuitive, and difficult to debug. Consequently, more natural, less error-prone imperative DL frameworks encouraging eager execution have emerged but at the expense of run-time performance. While hybrid approaches aim for the "best of both worlds," the challenges in applying them in the real world are largely unknown. We conduct a data-driven analysis of challenges -- and resultant bugs -- involved in writing reliable yet performant imperative DL code by studying 250 open-source projects, consisting of 19.7 MLOC, along with 470 and 446 manually examined code patches and bug reports, respectively. The results indicate that hybridization: (i) is prone to API misuse, (ii) can result in performance degradation -- the opposite of its intention, and (iii) has limited application due to execution mode incompatibility. We put forth several recommendations, best practices, and anti-patterns for effectively hybridizing imperative DL code, potentially benefiting DL practitioners, API designers, tool developers, and educators.