This study examines a novel planning problem for multiple agents that cannot share holding resources, named Offline Time-Independent Multiagent Path Planning (OTIMAPP) . Given a graph and a set of ...start-goal pairs, the problem to be addressed is assigning a path to each agent, such that every agent eventually reaches its destination without blocking others, regardless of when each agent starts and finishes each own action. This motivation stems from timing uncertainties, including the reality gaps between planning and robot execution. In contrast to conventional solution, concepts of multirobot path planning that rely on timings, once OTIMAPP solutions are obtained, they can be executed without any synchronization between robot actions. Moreover, there is a theoretical guarantee that all robots eventually reach their destinations, provided they avoid interrobot collisions. This study attempts to establish OTIMAPP both theoretically and practically. Specifically, we present a formalization of the problem, solution conditions based on a categorization of deadlocks, computational complexities showing that OTIMAPP is computationally intractable, practical relaxation of the solution concept, two algorithms to solve OTIMAPP based on multiagent pathfinding algorithms, empirical results showing large OTIMAPP instances can be solved to some extent, as well as robot demonstrations of asynchronous OTIMAPP execution.
Parallel and Asynchronous Smart Contract Execution Liu, Jian; Li, Peilun; Cheng, Raymond ...
IEEE transactions on parallel and distributed systems,
2022-May-1, 2022-5-1, Letnik:
33, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Today's blockchains suffer from low throughput and high latency, which impedes their widespread adoption of more complex applications like smart contracts. In this article, we propose a novel ...paradigm for smart contract execution. It distinguishes between consensus nodes and execution nodes: different groups of execution nodes can execute transactions in parallel; meanwhile, consensus nodes can asynchronously order transactions and process execution results. Moreover, it requires no coordination among execution nodes and can effectively prevent livelocks. We show two ways of applying this paradigm to blockchains. First, we show how we can make Ethereum support parallel and asynchronous contract execution without hard-forks . Then, we propose a new public, permissionless blockchain. Our benchmark shows that, with a fast consensus layer, it can provide a high throughput even for complex transactions like Cryptokitties gene mixing. It can also protect simple transactions from being starved by complex transactions.
Reaction systems are a model of interactive computation, where the interaction between a system — itself built up of a number of reactions — and its environment is modelled through context sequences ...provided by the environment. The standard execution semantics of reaction systems is synchronous, i.e., at each computational step all the enabled reactions are executed. In this paper, we ‘de-synchronise’ such an execution model by allowing only a subset of enabled reactions to be executed. We then study the resulting asynchronous model assuming two fundamental execution policies. The first one allows any subset of reactions to be executed, and the second one draws each subset from a pre-defined pool. We also introduce and discuss the notion of persistence of reactions and sets of reactions in the resulting models of asynchronous reaction systems. In particular, we demonstrate that reaction persistence can be implemented.
Summary
Although the Kalman filter algorithms are well suited to be executed on most digital systems, they become slow when applied to large‐scale dynamic systems. Therefore, efficient execution of ...Kalman filter for the time‐critical and large‐scale applications is of the essence. This work aims to address this necessity by developing a novel framework to improve the performance of a generalized Kalman filter with unknown inputs (GKF‐UI) using multithreaded‐multicore processors and machine learning (ML) classification methods. An asynchronous execution model based on OpenMP message‐passing framework is developed and integrated with a novel supervised ML‐based thread classifier for the GKF‐UI algorithm to enhance execution efficiency. The experimental results show that the proposed approach can achieve up to 35.5× speedup over the serial single‐threaded implementations with no losses in the accuracy or changes to the generality of the filter structure. Moreover, this framework can play a significant role in realizations of computational advantages in large‐scale systems as well as for the time‐critical prediction applications.
In this overview paper, we present the work of the Goal-Oriented Long-Lived Systems Lab on multi-robot systems. We address multi-robot systems from a decision-making under uncertainty perspective, ...proposing approaches that explicitly reason about the inherent uncertainty of action execution, and how such stochasticity affects multi-robot coordination. To develop effective decision-making approaches, we take a special focus on (i) temporal uncertainty, in particular of action execution; (ii) the ability to provide rich guarantees of performance, both at a local (robot) level and at a global (team) level; and (iii) scaling up to systems with real-world impact. We summarise several pieces of work and highlight how they address the challenges above, and also hint at future research directions.
Multi-robot systems (MRSs) are becoming increasingly important in various domains. However, effective communication and coordination among multiple robots remain significant challenges. In this ...letter, we introduce a novel architecture for multi-robot decision-making and control based on multi-agent reinforcement learning (MARL). Our architecture can accommodate heterogeneous robots operating asynchronously in different scenarios. We propose an improved practical Q-value mixing network (Qrainbow), which builds on value-decomposition networks and applies the multi-head attention mixer of Qatten and effective components from Rainbow, such as double network, dueling network, and prioritized experience replay. To migrate the algorithm to MRS, we fuse macro-action into Qrainbow and make a slight change to the process of calculating the loss function, enabling Qrainbow to work in asynchronous scenarios. We evaluate our architecture in both the benchmark environment for MARL and a multi-robot environment with varying layouts. In terms of convergence speed and final result, Qrainbow outperforms other state-of-the-art MARL algorithms. Additionally, our architecture achieves superior performance in reducing time costs and avoiding collisions between robots in homogeneous and heterogeneous multi-robot cooperation tasks.
This paper introduces the first asynchronous, task-based formulation of the polar decomposition and its corresponding implementation on manycore architectures. Based on a new formulation of the ...iterative QR dynamically-weighted Halley algorithm (QDWH) for the calculation of the polar decomposition, the proposed implementation replaces the original and hostile LU factorization for the condition number estimator by the more adequate QR factorization to enable software portability across various architectures. Relying on fine-grained computations, the novel task-based implementation is also capable of taking advantage of the identity structure of the matrix involved during the QDWH iterations, which decreases the overall algorithmic complexity. Furthermore, the artifactual synchronization points have been weakened compared to previous implementations, unveiling look-ahead opportunities for better hardware occupancy. The overall QDWH-based polar decomposition can then be represented as a directed acyclic graph (DAG), where nodes represent computational tasks and edges define the inter-task data dependencies. The StarPU dynamic runtime system is employed to traverse the DAG, to track the various data dependencies and to asynchronously schedule the computational tasks on the underlying hardware resources, resulting in an out-of-order task scheduling. Benchmarking experiments show significant improvements against existing state-of-the-art high performance implementations (i.e., Intel MKL and Elemental) for the polar decomposition on latest shared-memory vendors' systems (i.e., Intel Haswell/Broadwell/Knights Landing, NVIDIA K80/P100 GPUs and IBM Power8), while maintaining high numerical accuracy.
In database and large-scale data analytics, recursive aggregate processing plays an important role, which is generally implemented under a framework of incremental computing and executed ...synchronously and/or asynchronously. We identify three barriers in existing recursive aggregate data processing. First, the processing scope is largely limited to monotonic programs. Second, checking on conditions for monotonicity and correctness for async processing is sophisticated and manually done. Third, execution engines may be suboptimal due to separation of sync and async execution. In this paper, we lay an analytical foundation for conditions to check if a recursive aggregate program that is monotonic or even non-monotonic can be executed incrementally and asynchronously with its correct result. We design and implement a condition verification tool that can automatically check if a given program satisfies the conditions. We further propose a unified sync-async engine to execute these programs for high performance. To integrate all these effective methods together, we have developed a distributed Datalog system, called PowerLog. Our evaluation shows that PowerLog can outperform three representative Datalog systems on both monotonic and non-monotonic recursive programs.
FBBeam: An Erlang-based IEC 61499 Implementation Prenzel, Laurin; Provost, Julien
2019 IEEE 17th International Conference on Industrial Informatics (INDIN),
2019-July, Letnik:
1
Conference Proceeding
Odprti dostop
The IEC 61499 is a modeling language for distributed control systems. Despite numerous research results existing on this topic, industry acceptance is lacking. This paper aims to investigate the ...benefits of reusing an existing soft real-time runtime system for the implementation of the IEC 61499. For this purpose, FBBeam, a compiler that automatically converts IEC 61499 models to Erlang source code, was implemented. Possible execution semantics are presented and compared to the Erlang execution model. An initial case study examines the scalability of a multi-tasking runtime environment. The results indicate that Erlang is able to utilize multiple CPU cores efficiently and can distribute the load dynamically. FBBeam represents an opportunity to reutilize an existing runtime environment for research on dynamic updating, distribution, monitoring, maintenance, and fault-tolerance for Industry 4.0 or Cyber Physical Production Systems.
PDF
