OpenRaiser/Intern-Atlas huggingface dataset:
An Iterative Approach for Collision Feee Routing and Scheduling in Multirobot Stations
Venue: arXiv cs.RO 2023
Year: 2023

This work is inspired by the problem of planning sequences of operations, as welding, in car manufacturing stations where multiple industrial robots cooperate. The goal is to minimize the station cycle time, \emph{i.e.} the time it takes for the last robot to finish its cycle. This is done by dispatching the tasks among the robots, and by routing and scheduling the robots in a collision-free way, such that they perform all predefined tasks. We propose an iterative and decoupled approach in order to cope with the high complexity of the problem. First, collisions among robots are neglected, leading to a min-max Multiple Generalized Traveling Salesman Problem (MGTSP). Then, when the sets of robot loads have been obtained and fixed, we sequence and schedule their tasks, with the aim to avoid conflicts. The first problem (min-max MGTSP) is solved by an exact branch and bound method, where different lower bounds are presented by combining the solutions of a min-max set partitioning problem and of a Generalized Traveling Salesman Problem (GTSP). The second problem is approached by assuming that robots move synchronously: a novel transformation of this synchronous problem into a GTSP is presented. Eventually, in order to provide complete robot solutions, we include path planning functionalities, allowing the robots to avoid collisions with the static environment and among themselves. These steps are iterated until a satisfying solution is obtained. Experimental results are shown for both problems and for their combination. We even show the results of the iterative method, applied to an industrial test case adapted from a stud welding station in a car manufacturing line.
FedFwd: Federated Learning without Backpropagation
Venue: arXiv cs.LG 2023
Year: 2023

In federated learning (FL), clients with limited resources can disrupt the training efficiency. A potential solution to this problem is to leverage a new learning procedure that does not rely on backpropagation (BP). We present a novel approach to FL called FedFwd that employs a recent BP-free method by Hinton (2022), namely the Forward Forward algorithm, in the local training process. FedFwd can reduce a significant amount of computations for updating parameters by performing layer-wise local updates, and therefore, there is no need to store all intermediate activation values during training. We conduct various experiments to evaluate FedFwd on standard datasets including MNIST and CIFAR-10, and show that it works competitively to other BP-dependent FL methods.
FusionAI: Decentralized Training and Deploying LLMs with Massive Consumer-Level GPUs
Venue: arXiv cs.DC 2023
Year: 2023

The rapid growth of memory and computation requirements of large language models (LLMs) has outpaced the development of hardware, hindering people who lack large-scale high-end GPUs from training or deploying LLMs. However, consumer-level GPUs, which constitute a larger market share, are typically overlooked in LLM due to their weaker computing performance, smaller storage capacity, and lower communication bandwidth. Additionally, users may have privacy concerns when interacting with remote LLMs. In this paper, we envision a decentralized system unlocking the potential vast untapped consumer-level GPUs in pre-training, inference and fine-tuning of LLMs with privacy protection. However, this system faces critical challenges, including limited CPU and GPU memory, low network bandwidth, the variability of peer and device heterogeneity. To address these challenges, our system design incorporates: 1) a broker with backup pool to implement dynamic join and quit of computing providers; 2) task scheduling with hardware performance to improve system efficiency; 3) abstracting ML procedures into directed acyclic graphs (DAGs) to achieve model and task universality; 4) abstracting intermediate represention and execution planes to ensure compatibility of various devices and deep learning (DL) frameworks. Our performance analysis demonstrates that 50 RTX 3080 GPUs can achieve throughputs comparable to those of 4 H100 GPUs, which are significantly more expensive.
Logic of subjective probability
Venue: arXiv cs.AI 2023
Year: 2023

In this paper I discuss both syntax and semantics of subjective probability. The semantics determines ways of testing probability statements. Among important varieties of subjective probabilities are intersubjective probabilities and impersonal probabilities, and I will argue that well-tested impersonal probabilities acquire features of objective probabilities. Jeffreys's law, my next topic, states that two successful probability forecasters must issue forecasts that are close to each other, thus supporting the idea of objective probabilities. Finally, I will discuss connections between subjective and frequentist probability.
A method based on hierarchical spatiotemporal features for trojan traffic detection
Venue: arXiv cs.NI 2023
Year: 2023

Trojans are one of the most threatening network attacks currently. HTTP-based Trojan, in particular, accounts for a considerable proportion of them. Moreover, as the network environment becomes more complex, HTTP-based Trojan is more concealed than others. At present, many intrusion detection systems (IDSs) are increasingly difficult to effectively detect such Trojan traffic due to the inherent shortcomings of the methods used and the backwardness of training data. Classical anomaly detection and traditional machine learning-based (TML-based) anomaly detection are highly dependent on expert knowledge to extract features artificially, which is difficult to implement in HTTP-based Trojan traffic detection. Deep learning-based (DL-based) anomaly detection has been locally applied to IDSs, but it cannot be transplanted to HTTP-based Trojan traffic detection directly. To solve this problem, in this paper, we propose a neural network detection model (HSTF-Model) based on hierarchical spatiotemporal features of traffic. Meanwhile, we combine deep learning algorithms with expert knowledge through feature encoders and statistical characteristics to improve the self-learning ability of the model. Experiments indicate that F1 of HSTF-Model can reach 99.4% in real traffic. In addition, we present a dataset BTHT consisting of HTTP-based benign and Trojan traffic to facilitate related research in the field.
Cooperative Filtering with Range Measurements: A Distributed Constrained Zonotopic Method
Venue: arXiv cs.MA 2023
Year: 2023

This article studies the distributed estimation problem of a multi-agent system with bounded absolute and relative range measurements. Parts of the agents are with high-accuracy absolute measurements, which are considered as anchors; the other agents utilize lowaccuracy absolute and relative range measurements, each derives an uncertain range that contains its true state in a distributed manner. Different from previous studies, we design a distributed algorithm to handle the range measurements based on extended constrained zonotopes, which has low computational complexity and high precision. With our proposed algorithm, agents can derive their uncertain range sequentially along the chain topology, such that agents with low-accuracy sensors can benefit from the high-accuracy absolute measurements of anchors and improve the estimation performance. Simulation results corroborate the effectiveness of our proposed algorithm and verify our method can significantly improve the estimation accuracy.
Immersive Technologies in Virtual Companions: A Systematic Literature Review
Venue: arXiv cs.HC 2023
Year: 2023

The emergence of virtual companions is transforming the evolution of intelligent systems that effortlessly cater to the unique requirements of users. These advanced systems not only take into account the user present capabilities, preferences, and needs but also possess the capability to adapt dynamically to changes in the environment, as well as fluctuations in the users emotional state or behavior. A virtual companion is an intelligent software or application that offers support, assistance, and companionship across various aspects of users lives. Various enabling technologies are involved in building virtual companion, among these, Augmented Reality (AR), and Virtual Reality (VR) are emerging as transformative tools. While their potential for use in virtual companions or digital assistants is promising, their applications in these domains remain relatively unexplored. To address this gap, a systematic review was conducted to investigate the applications of VR, AR, and MR immersive technologies in the development of virtual companions. A comprehensive search across PubMed, Scopus, and Google Scholar yielded 28 relevant articles out of a pool of 644. The review revealed that immersive technologies, particularly VR and AR, play a significant role in creating digital assistants, offering a wide range of applications that brings various facilities in the individuals life in areas such as addressing social isolation, enhancing cognitive abilities and dementia care, facilitating education, and more. Additionally, AR and MR hold potential for enhancing Quality of life (QoL) within the context of virtual companion technology. The findings of this review provide a valuable foundation for further research in this evolving field.
Decentralized shape formation and force-based interactive formation control in robot swarms
Venue: arXiv cs.MA 2023
Year: 2023

Swarm robotic systems utilize collective behaviour to achieve goals that might be too complex for a lone entity, but become attainable with localized communication and collective decision making. In this paper, a behaviour-based distributed approach to shape formation is proposed. Flocking into strategic formations is observed in migratory birds and fish to avoid predators and also for energy conservation. The formation is maintained throughout long periods without collapsing and is advantageous for communicating within the flock. Similar behaviour can be deployed in multi-agent systems to enhance coordination within the swarm. Existing methods for formation control are either dependent on the size and geometry of the formation or rely on maintaining the formation with a single reference in the swarm (the leader). These methods are not resilient to failure and involve a high degree of deformation upon obstacle encounter before the shape is recovered again. To improve the performance, artificial force-based interaction amongst the entities of the swarm to maintain shape integrity while encountering obstacles is elucidated.
Representations Matter: Embedding Modes of Large Language Models using Dynamic Mode Decomposition
Venue: arXiv cs.CL 2023
Year: 2023

Existing large language models (LLMs) are known for generating "hallucinated" content, namely a fabricated text of plausibly looking, yet unfounded, facts. To identify when these hallucination scenarios occur, we examine the properties of the generated text in the embedding space. Specifically, we draw inspiration from the dynamic mode decomposition (DMD) tool in analyzing the pattern evolution of text embeddings across sentences. We empirically demonstrate how the spectrum of sentence embeddings over paragraphs is constantly low-rank for the generated text, unlike that of the ground-truth text. Importantly, we find that evaluation cases having LLM hallucinations correspond to ground-truth embedding patterns with a higher number of modes being poorly approximated by the few modes associated with LLM embedding patterns. In analogy to near-field electromagnetic evanescent waves, the embedding DMD eigenmodes of the generated text with hallucinations vanishes quickly across sentences as opposed to those of the ground-truth text. This suggests that the hallucinations result from both the generation techniques and the underlying representation.
Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time
Venue: arXiv cs.DS 2023
Year: 2023

The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science, representing fundamental challenges in string processing. Both problems can be solved in linear time using a classical model of computation, by means of very similar algorithms, both relying on the use of suffix trees. Very recently, two sublinear algorithms for LCS and LPS in the quantum query model have been presented by Le Gall and Seddighin~\cite{GallS23}, requiring $\tilde{\mathcal{O}}(n^{5/6})$ and $\tilde{\mathcal{O}}(\sqrt{n})$ queries, respectively. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this paper we present, for the first time, a $\tilde{\mathcal{O}}(\sqrt{n})$ quantum algorithm for both LCS and LPS working in the circuit model of computation. Our solutions are simpler than previous ones and can be easily translated into quantum procedures. We also present actual implementations of the two algorithms as quantum circuits working in $\mathcal{O}(\sqrt{n}\log^5(n))$ and $\mathcal{O}(\sqrt{n}\log^4(n))$ time, respectively.
Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Venue: arXiv cs.CG 2023
Year: 2023

Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known $n^{O(tw)}$-time algorithms cannot be improved to run in time $n^{o(tw)}$ unless ETH fails.
Deception Game: Closing the Safety-Learning Loop in Interactive Robot Autonomy
Venue: arXiv cs.RO 2023
Year: 2023

An outstanding challenge for the widespread deployment of robotic systems like autonomous vehicles is ensuring safe interaction with humans without sacrificing performance. Existing safety methods often neglect the robot's ability to learn and adapt at runtime, leading to overly conservative behavior. This paper proposes a new closed-loop paradigm for synthesizing safe control policies that explicitly account for the robot's evolving uncertainty and its ability to quickly respond to future scenarios as they arise, by jointly considering the physical dynamics and the robot's learning algorithm. We leverage adversarial reinforcement learning for tractable safety analysis under high-dimensional learning dynamics and demonstrate our framework's ability to work with both Bayesian belief propagation and implicit learning through large pre-trained neural trajectory predictors.
WindMill: A Parameterized and Pluggable CGRA Implemented by DIAG Design Flow
Venue: arXiv cs.AR 2023
Year: 2023

With the cross-fertilization of applications and the ever-increasing scale of models, the efficiency and productivity of hardware computing architectures have become inadequate. This inadequacy further exacerbates issues in design flexibility, design complexity, development cycle, and development costs (4-d problems) in divergent scenarios. To address these challenges, this paper proposed a flexible design flow called DIAG based on plugin techniques. The proposed flow guides hardware development through four layers: definition(D), implementation(I), application(A), and generation(G). Furthermore, a versatile CGRA generator called WindMill is implemented, allowing for agile generation of customized hardware accelerators based on specific application demands. Applications and algorithm tasks from three aspects is experimented. In the case of reinforcement learning algorithm, a significant performance improvement of $2.3\times$ compared to GPU is achieved.
FOR-instance: a UAV laser scanning benchmark dataset for semantic and instance segmentation of individual trees
Venue: arXiv cs.CV 2023
Year: 2023

The FOR-instance dataset (available at https://doi.org/10.5281/zenodo.8287792) addresses the challenge of accurate individual tree segmentation from laser scanning data, crucial for understanding forest ecosystems and sustainable management. Despite the growing need for detailed tree data, automating segmentation and tracking scientific progress remains difficult. Existing methodologies often overfit small datasets and lack comparability, limiting their applicability. Amid the progress triggered by the emergence of deep learning methodologies, standardized benchmarking assumes paramount importance in these research domains. This data paper introduces a benchmarking dataset for dense airborne laser scanning data, aimed at advancing instance and semantic segmentation techniques and promoting progress in 3D forest scene segmentation. The FOR-instance dataset comprises five curated and ML-ready UAV-based laser scanning data collections from diverse global locations, representing various forest types. The laser scanning data were manually annotated into individual trees (instances) and different semantic classes (e.g. stem, woody branches, live branches, terrain, low vegetation). The dataset is divided into development and test subsets, enabling method advancement and evaluation, with specific guidelines for utilization. It supports instance and semantic segmentation, offering adaptability to deep learning frameworks and diverse segmentation strategies, while the inclusion of diameter at breast height data expands its utility to the measurement of a classic tree variable. In conclusion, the FOR-instance dataset contributes to filling a gap in the 3D forest research, enhancing the development and benchmarking of segmentation algorithms for dense airborne laser scanning data.
Federated Orthogonal Training: Mitigating Global Catastrophic Forgetting in Continual Federated Learning
Venue: arXiv cs.LG 2023
Year: 2023

Federated Learning (FL) has gained significant attraction due to its ability to enable privacy-preserving training over decentralized data. Current literature in FL mostly focuses on single-task learning. However, over time, new tasks may appear in the clients and the global model should learn these tasks without forgetting previous tasks. This real-world scenario is known as Continual Federated Learning (CFL). The main challenge of CFL is Global Catastrophic Forgetting, which corresponds to the fact that when the global model is trained on new tasks, its performance on old tasks decreases. There have been a few recent works on CFL to propose methods that aim to address the global catastrophic forgetting problem. However, these works either have unrealistic assumptions on the availability of past data samples or violate the privacy principles of FL. We propose a novel method, Federated Orthogonal Training (FOT), to overcome these drawbacks and address the global catastrophic forgetting in CFL. Our algorithm extracts the global input subspace of each layer for old tasks and modifies the aggregated updates of new tasks such that they are orthogonal to the global principal subspace of old tasks for each layer. This decreases the interference between tasks, which is the main cause for forgetting. We empirically show that FOT outperforms state-of-the-art continual learning methods in the CFL setting, achieving an average accuracy gain of up to 15% with 27% lower forgetting while only incurring a minimal computation and communication cost.
AlphaZero Gomoku
Venue: arXiv cs.AI 2023
Year: 2023

In the past few years, AlphaZero's exceptional capability in mastering intricate board games has garnered considerable interest. Initially designed for the game of Go, this revolutionary algorithm merges deep learning techniques with the Monte Carlo tree search (MCTS) to surpass earlier top-tier methods. In our study, we broaden the use of AlphaZero to Gomoku, an age-old tactical board game also referred to as "Five in a Row." Intriguingly, Gomoku has innate challenges due to a bias towards the initial player, who has a theoretical advantage. To add value, we strive for a balanced game-play. Our tests demonstrate AlphaZero's versatility in adapting to games other than Go. MCTS has become a predominant algorithm for decision processes in intricate scenarios, especially board games. MCTS creates a search tree by examining potential future actions and uses random sampling to predict possible results. By leveraging the best of both worlds, the AlphaZero technique fuses deep learning from Reinforcement Learning with the balancing act of MCTS, establishing a fresh standard in game-playing AI. Its triumph is notably evident in board games such as Go, chess, and shogi.
UniSA: Unified Generative Framework for Sentiment Analysis
Venue: arXiv cs.CL 2023
Year: 2023

Sentiment analysis is a crucial task that aims to understand people's emotional states and predict emotional categories based on multimodal information. It consists of several subtasks, such as emotion recognition in conversation (ERC), aspect-based sentiment analysis (ABSA), and multimodal sentiment analysis (MSA). However, unifying all subtasks in sentiment analysis presents numerous challenges, including modality alignment, unified input/output forms, and dataset bias. To address these challenges, we propose a Task-Specific Prompt method to jointly model subtasks and introduce a multimodal generative framework called UniSA. Additionally, we organize the benchmark datasets of main subtasks into a new Sentiment Analysis Evaluation benchmark, SAEval. We design novel pre-training tasks and training methods to enable the model to learn generic sentiment knowledge among subtasks to improve the model's multimodal sentiment perception ability. Our experimental results show that UniSA performs comparably to the state-of-the-art on all subtasks and generalizes well to various subtasks in sentiment analysis.
High Frequency, High Accuracy Pointing onboard Nanosats using Neuromorphic Event Sensing and Piezoelectric Actuation
Venue: arXiv cs.ET 2023
Year: 2023

As satellites become smaller, the ability to maintain stable pointing decreases as external forces acting on the satellite come into play. At the same time, reaction wheels used in the attitude determination and control system (ADCS) introduce high frequency jitter which can disrupt pointing stability. For space domain awareness (SDA) tasks that track objects tens of thousands of kilometres away, the pointing accuracy offered by current nanosats, typically in the range of 10 to 100 arcseconds, is not sufficient. In this work, we develop a novel payload that utilises a neuromorphic event sensor (for high frequency and highly accurate relative attitude estimation) paired in a closed loop with a piezoelectric stage (for active attitude corrections) to provide highly stable sensor-specific pointing. Event sensors are especially suited for space applications due to their desirable characteristics of low power consumption, asynchronous operation, and high dynamic range. We use the event sensor to first estimate a reference background star field from which instantaneous relative attitude is estimated at high frequency. The piezoelectric stage works in a closed control loop with the event sensor to perform attitude corrections based on the discrepancy between the current and desired attitude. Results in a controlled setting show that we can achieve a pointing accuracy in the range of 1-5 arcseconds using our novel payload at an operating frequency of up to 50Hz using a prototype built from commercial-off-the-shelf components. Further details can be found at https://ylatif.github.io/ultrafinestabilisation