Multiagent Systems (cs.MA)

  • PDF
    In this paper, we study the optimal convergence rate for distributed convex optimization problems in networks. We model the communication restrictions imposed by the network as a set of affine constraints and provide optimal complexity bounds for four different setups, namely: the function $F(\xb) \triangleq \sum_{i=1}^{m}f_i(\xb)$ is strongly convex and smooth, either strongly convex or smooth or just convex. Our results show that Nesterov's accelerated gradient descent on the dual problem can be executed in a distributed manner and obtains the same optimal rates as in the centralized version of the problem (up to constant or logarithmic factors) with an additional cost related to the spectral gap of the interaction matrix. Finally, we discuss some extensions to the proposed setup such as proximal friendly functions, time-varying graphs, improvement of the condition numbers.
  • PDF
    In this paper, we aim to find a robust network formation strategy that can adaptively evolve the network topology against network dynamics in a distributed manner. We consider a network coding deployed wireless ad hoc network where source nodes are connected to terminal nodes with the help of intermediate nodes. We show that mixing operations in network coding can induce packet anonymity that allows the inter-connections in a network to be decoupled. This enables each intermediate node to consider complex network inter-connections as a node-environment interaction such that the Markov decision process (MDP) can be employed at each intermediate node. The optimal policy that can be obtained by solving the MDP provides each node with optimal amount of changes in transmission range given network dynamics (e.g., the number of nodes in the range and channel condition). Hence, the network can be adaptively and optimally evolved by responding to the network dynamics. The proposed strategy is used to maximize long-term utility, which is achieved by considering both current network conditions and future network dynamics. We define the utility of an action to include network throughput gain and the cost of transmission power. We show that the resulting network of the proposed strategy eventually converges to stationary networks, which maintain the states of the nodes. Moreover, we propose to determine initial transmission ranges and initial network topology that can expedite the convergence of the proposed algorithm. Our simulation results confirm that the proposed strategy builds a network which adaptively changes its topology in the presence of network dynamics. Moreover, the proposed strategy outperforms existing strategies in terms of system goodput and successful connectivity ratio.
  • PDF
    We introduce MAgent, a platform to support research and development of many-agent reinforcement learning. Unlike previous research platforms on single or multi-agent reinforcement learning, MAgent focuses on supporting the tasks and the applications that require hundreds to millions of agents. Within the interactions among a population of agents, it enables not only the study of learning algorithms for agents' optimal polices, but more importantly, the observation and understanding of individual agent's behaviors and social phenomena emerging from the AI society, including communication languages, leaderships, altruism. MAgent is highly scalable and can host up to one million agents on a single GPU server. MAgent also provides flexible configurations for AI researchers to design their customized environments and agents. In this demo, we present three environments designed on MAgent and show emerged collective intelligence by learning from scratch.
  • PDF
    The human brain is one of the most complex living structures in the known Universe. It consists of billions of neurons and synapses. Due to its intrinsic complexity, it can be a formidable task to accurately depict brain's structure and functionality. In the past, numerous studies have been conducted on modeling brain disease, structure, and functionality. Some of these studies have employed Agent-based approaches including multiagent-based simulation models as well as brain complex networks. While these models have all been developed using agent-based computing, however, to our best knowledge, none of them have employed the use of Agent-Oriented Software Engineering (AOSE) methodologies in developing the brain or disease model. This is a problem because without due process, developed models can miss out on important requirements. AOSE has the unique capability of merging concepts from multiagent systems, agent-based modeling, artificial intelligence, besides concepts from distributed systems. AOSE involves the various tested software engineering principles in various phases of the model development ranging from analysis, design, implementation, and testing phases. In this paper, we employ the use of three different AOSE methodologies for modeling the Multiple Sclerosis brain disease namely GAIA, TROPOS, and MASE. After developing the models, we further employ the use of Exploratory Agent-based Modeling (EABM) to develop an actual model replicating previous results as a proof of concept. The key objective of this study is to demonstrate and explore the viability and effectiveness of AOSE methodologies in the development of complex brain structure and cognitive process models. Our key finding include demonstration that AOSE methodologies can be considerably helpful in modeling various living complex systems, in general, and the human brain, in particular.
  • PDF
    Modeling personality is a challenging problem with applications spanning computer games, virtual assistants, online shopping and education. Many techniques have been tried, ranging from neural networks to computational cognitive architectures. However, most approaches rely on examples with hand-crafted features and scenarios. Here, we approach learning a personality by training agents using a Deep Q-Network (DQN) model on rewards based on psychoanalysis, against hand-coded AI in the game of Pong. As a result, we obtain 4 agents, each with its own personality. Then, we define happiness of an agent, which can be seen as a measure of alignment with agent's objective function, and study it when agents play both against hand-coded AI, and against each other. We find that the agents that achieve higher happiness during testing against hand-coded AI, have lower happiness when competing against each other. This suggests that higher happiness in testing is a sign of overfitting in learning to interact with hand-coded AI, and leads to worse performance against agents with different personalities.
  • PDF
    The combination of Artificial Intelligence (AI) and Internet-of-Things (IoT), which is denoted as AI-powered Internet-of-Things (AIoT), is capable of processing huge amount of data generated from a large number of devices and handling complex problems in social infrastructures. As AI and IoT technologies are becoming mature, in this paper, we propose to apply AIoT technologies for traffic light control, which is an essential component for intelligent transportation system, to improve the efficiency of smart city's road system. Specifically, various sensors such as surveillance cameras provide real-time information for intelligent traffic light control system to observe the states of both motorized traffic and non-motorized traffic. In this paper, we propose an intelligent traffic light control solution by using distributed multi-agent Q learning, considering the traffic information at the neighboring intersections as well as local motorized and non-motorized traffic, to improve the overall performance of the entire control system. By using the proposed multi-agent Q learning algorithm, our solution is targeting to optimize both the motorized and non-motorized traffic. In addition, we considered many constraints/rules for traffic light control in the real world, and integrate these constraints in the learning algorithm, which can facilitate the proposed solution to be deployed in real operational scenarios. We conducted numerical simulations for a real-world map with real-world traffic data. The simulation results show that our proposed solution outperforms existing solutions in terms of vehicle and pedestrian queue lengths, waiting time at intersections, and many other key performance metrics.
  • PDF
    We consider ordinal approximation algorithms for a broad class of utility maximization problems for multi-agent systems. In these problems, agents have utilities for connecting to each other, and the goal is to compute a maximum-utility solution subject to a set of constraints. We represent these as a class of graph optimization problems, including matching, spanning tree problems, TSP, maximum weight planar subgraph, and many others. We study these problems in the ordinal setting: latent numerical utilities exist, but we only have access to ordinal preference information, i.e., every agent specifies an ordering over the other agents by preference. We prove that for the large class of graph problems we identify, ordinal information is enough to compute solutions which are close to optimal, thus demonstrating there is no need to know the underlying numerical utilities. For example, for problems in this class with bounded degree $b$ a simple ordinal greedy algorithm always produces a ($b+1$)-approximation; we also quantify how the quality of ordinal approximation depends on the sparsity of the resulting graphs. In particular, our results imply that ordinal information is enough to obtain a 2-approximation for Maximum Spanning Tree; a 4-approximation for Max Weight Planar Subgraph; a 2-approximation for Max-TSP; and a 2-approximation for various Matching problems.
  • PDF
    Social storage systems are becoming increasingly popular compared to the existing data backup systems like local, centralized and P2P systems. An endogenously built symmetric social storage model and its aspects like the utility of each agent, bilateral stability, contentment, and efficiency have been extensively discussed in Mane et. al. (2017). We include heterogeneity in this model by using the concept of Social Range Matrix from Kuznetsov et. al (2010). Now, each agent is concerned about its perceived utility, which is a linear combination of its utility as well as others utilities (depending upon whether the pair are friends, enemies or do not care about each other). We derive conditions when two agents may want to add or delete a link, and provide an algorithm that checks if a bilaterally stable network is possible or not. Finally, we take some special Social Range Matrices and prove that under certain conditions on network parameters, a bilaterally stable network is unique.
  • PDF
    We consider the problem of computing a matching in a bipartite graph in the presence of one-sided preferences. There are several well studied notions of optimality which include pareto optimality, rank maximality, fairness and popularity. In this paper, we conduct an in-depth experimental study comparing different notions of optimality based on a variety of metrics like cardinality, number of rank-1 edges, popularity, to name a few. Observing certain shortcomings in the standard notions of optimality, we propose an algorithm which maximizes an alternative metric called the Area under Profile Curve ratio (AUPCR). To the best of our knowledge, the AUPCR metric was used earlier but there is no known algorithm to compute an AUPCR maximizing matching. Finally, we illustrate the superiority of the AUPCR-maximizing matching by comparing its performance against other optimal matchings on synthetic instances modeling real-world data.
  • PDF
    Cooperative multi-agent planning (MAP) is a relatively recent research field that combines technologies, algorithms and techniques developed by the Artificial Intelligence Planning and Multi-Agent Systems communities. While planning has been generally treated as a single-agent task, MAP generalizes this concept by considering multiple intelligent agents that work cooperatively to develop a course of action that satisfies the goals of the group. This paper reviews the most relevant approaches to MAP, putting the focus on the solvers that took part in the 2015 Competition of Distributed and Multi-Agent Planning, and classifies them according to their key features and relative performance.
  • PDF
    Multi-agent approach has become popular in computer science and technology. However, the conventional models of multi-agent and multicomponent systems implicitly or explicitly assume existence of absolute time or even do not include time in the set of defining parameters. At the same time, it is proved theoretically and validated experimentally that there are different times and time scales in a variety of real systems - physical, chemical, biological, social, informational, etc. Thus, the goal of this work is construction of a multi-agent multicomponent system models with concurrency of processes and diversity of actions. To achieve this goal, a mathematical system actor model is elaborated and its properties are studied.
  • PDF
    We present ongoing work on a tool that consists of two parts: (i) A raw micro-level abstract world simulator with an interface to (ii) a 3D game engine, translator of raw abstract simulator data to photorealistic graphics. Part (i) implements a dedicated cellular automata (CA) on reconfigurable hardware (FPGA) and part (ii) interfaces with a deep learning framework for training neural networks. The bottleneck of such an architecture usually lies in the fact that transferring the state of the whole CA significantly slows down the simulation. We bypass this by sending only a small subset of the general state, which we call a 'locus of visibility', akin to a torchlight in a darkened 3D space, into the simulation. The torchlight concept exists in many games but these games generally only simulate what is in or near the locus. Our chosen architecture will enable us to simulate on a micro level outside the locus. This will give us the advantage of being able to create a larger and more fine-grained simulation which can be used to train neural networks for use in games.
  • PDF
    This paper proposes a novel game-theoretical autonomous decision-making framework to address a task allocation problem for a swarm of multiple agents. We consider cooperation of self-interested agents and show that agents who have social inhibition can converge to a Nash stable partition (i.e., social agreement) using our proposed decentralised algorithm within polynomial time. The algorithm is simple and executable based on local interactions with neighbour agents under a strongly-connected communication network and even in asynchronous environments. We analytically present a mathematical formulation for computing the lower bound of a converged solution's suboptimality and additionally show that 50 % of suboptimality can be minimally guaranteed if social utilities are non-decreasing functions with respect to the number of co-working agents. Through numerical experiments, it is confirmed that the proposed framework is scalable, fast adaptable against dynamical environments, and robust even in a realistic situation where some of the agents temporarily somehow do not operate during a mission.
  • PDF
    Swarm robotic systems are currently being used to address many real-world problems. One interesting application of swarm robotics is the self-organized formation of structures and shapes. Some of the key challenges in the swarm robotic systems include swarm size constraint, random motion, coordination among robots, localization, and adaptability in a decentralized environment. Rubenstein et al. presented a system ("Programmable self-assembly in a thousand-robot swarm", Science, 2014) for thousand-robot swarm able to form only solid shapes with the robots in aggregated form by applying the collective behavior algorithm. Even though agent-based approaches have been presented in various studies for self-organized formation, however these studies lack agent-based modeling (ABM) approach along with the constraints in term of structure complexity and heterogeneity in large swarms with dynamic localization. The cognitive agent-based computing (CABC) approach is capable of modeling such self-organization based multi-agents systems (MAS). In this paper, we develop a simulation model using ABM under CABC approach for self-organized shape formation in swarm robots. We propose a shape formation algorithm for validating our model and perform simulation-based experiments for six different shapes including hole-based shapes. We also demonstrate the formal specification for our model. The simulation result shows the robustness of the proposed approach having the emergent behavior of robots for the self-organized shape formation. The performance of the proposed approach is evaluated by robots convergence rate.
  • PDF
    We introduce new theoretical insights into two-population asymmetric games allowing for an elegant symmetric decomposition into two single population symmetric games. Specifically, we show how an asymmetric bimatrix game (A,B) can be decomposed into its symmetric counterparts by envisioning and investigating the payoff tables (A and B) that constitute the asymmetric game, as two independent, single population, symmetric games. We reveal several surprising formal relationships between an asymmetric two-population game and its symmetric single population counterparts, which facilitate a convenient analysis of the original asymmetric game due to the dimensionality reduction of the decomposition. The main finding reveals that if (x,y) is a Nash equilibrium of an asymmetric game (A,B), this implies that y is a Nash equilibrium of the symmetric counterpart game determined by payoff table A, and x is a Nash equilibrium of the symmetric counterpart game determined by payoff table B. Also the reverse holds and combinations of Nash equilibria of the counterpart games form Nash equilibria of the asymmetric game. We illustrate how these formal relationships aid in identifying and analysing the Nash structure of asymmetric games, by examining the evolutionary dynamics of the simpler counterpart games in several canonical examples.
  • PDF
    Since their inception, Multi Agent Systems (MASs) have been championed as a solution for the increasing problem of software complexity. Communities of distributed autonomous computing entities that are capable of collaborating, negotiating and acting to solve complex organisational and system management problems are an attractive proposition. Central to this is the requirement for agents to possess the capability of interacting with one another in a structured, consistent and organised manner. This thesis presents the Agent Conversation Reasoning Engine (ACRE), which constitutes a holistic view of communication management for MASs. ACRE is intended to facilitate the practical development, debugging and deployment of communication-heavy MASs. ACRE has been formally defined in terms of its operational semantics, and a generic architecture has been proposed to facilitate its integration with a wide variety of diverse agent development frameworks and Agent Oriented Programming (AOP) languages. A concrete implementation has also been developed that uses the Agent Factory AOP framework as its base. This allows ACRE to be used with a number of different AOP languages, while providing a reference implementation that other integrations can be modelled upon. A standard is also proposed for the modelling and sharing of agent-focused interaction protocols that is independent of the platform within which a concrete ACRE implementation is run. Finally, a user evaluation illustrates the benefits of incorporating conversation management into agent programming.
  • PDF
    We develop an agent-based model to reproduce the size distribution of R\&D alliances of firms. Agents are uniformly selected to initiate an alliance and to invite collaboration partners. These decide about acceptance based on an individual threshold that is compared with the utility expected from joining the current alliance. The benefit of alliances results from the fitness of the agents involved. Fitness is obtained from an empirical distribution of agent's activities. The cost of an alliance reflects its coordination effort. Two free parameters $a_{c}$ and $a_{l}$ scale the costs and the individual threshold. If initiators receive $R$ rejections of invitations, the alliance formation stops and another initiator is selected. The three free parameters $(a_{c},a_{l},R)$ are calibrated against a large scale data set of about 15,000 firms engaging in about 15,000 R\&D alliances over 26 years. For the validation of the model we compare the empirical size distribution with the theoretical one, using confidence bands, to find a very good agreement. As an asset of our agent-based model, we provide an analytical solution that allows to reduce the simulation effort considerably. The analytical solution applies to general forms of the utility of alliances. Hence, the model can be extended to other cases of alliance formation. While no information about the initiators of an alliance is available, our results indicate that mostly firms with high fitness are able to attract newcomers and to establish larger alliances.
  • PDF
    The dynamics of agent-based systems provide a framework to face the complexity of pedestrian-vehicle interactions in future cities, in which the compliance to traffic norms plays a fundamental role. The data of an observation performed at a non-signalized intersection are presented to provide useful insights for supporting the future development of agent-based models. Results focus on drivers' compliance to crossing pedestrians, describing potentially conflictual interactions among heterogeneous agents. The discussion closes with the potential applications of the collected data set for modelling the phenomenon.
  • PDF
    In this work, leader follower consensus objective has been addressed with the synthesis of an event based controller utilizing sliding mode robust control. The schema has been partitioned into two parts viz. finite time consensus problem and event triggered control mechanism. A nonlinear multi agent system with non identical dynamics has been put forward to illustrate the robust capabilities of the proposed control. The first part incorporates matching of states of the followers with those of the leader via consensus tracking algorithm. In the subsequent part, an event triggered rule is devised to save computational power and restrict periodic updating of the controller involved while ensuring desired closed loop performance of the system. Switching of the event based controller is achieved via sliding mode control. Advantage of using switched controller like sliding mode is that it retains its inherent robustness as well as event triggering approach aids in saving energy expenditure. Efficacy of the proposed scheme is confirmed via numerical simulations.
  • PDF
    This two-part paper considers strategic topology switching for the second-order multi-agent system under attack. In Part I, we propose a strategy on switching times that enables the strategic topology-switching algorithm proposed in Part II to reach the second-order consensus in the absence of attacks. The control protocol introduced to the multi-agent system is governed only by the relative positions of agents. Based on the stability of switched linear systems, the strategy on the dwell time of topology-switching signal is derived. The primary advantages of the strategy in achieving the second-order consensus are: 1) the control protocol relies only on relative position measurements, no velocity measurements are needed; 2) the strategy has no constraint on the magnitude of coupling strength. Simulations are provided to verify the effectiveness of strategic topology switching in achieving the second-order consensus.
  • PDF
    This two-part paper considers strategic topology switching for the second-order multi-agent system under attack. In Part II, we propose a strategy on switching topologies to reveal zero-dynamics attack. We first study the detectability of zero-dynamics attack for the second-order multi-agent sys- tem under switching topology, which has requirements on the switching times and switching topologies. Based on the strategy on switching times proposed in Part I and the strategy on switching topologies proposed in Part II, a decentralized strategic topology-switching algorithm is derived. The primary advantages of the algorithm are: 1) in achieving consensus in the absence of attacks, control protocol does not need velocity measurements and the algorithm has no constraint on the magnitude of coupling strength; 2) in revealing zero-dynamics attack, the algorithm has no constraint on the size of misbehaving-agent set; 3) in revealing zero-dynamics attack, if the Xor graph generated by every two-consecutive topologies has distinct eigenvalues, only one output is enough for the algorithm. Simulation examples are provided to verify the effectiveness of the strategic topology- switching algorithm.
  • PDF
    Future electricity distribution grids will host a considerable share of variable renewable energy sources and local storage resources. Moreover, they will face new load structures due for example to the growth of the electric vehicle market. These trends raise the need for new paradigms for distribution grids operation, in which Distribution System Operators will increasingly rely on demand side flexibility and households will progressively become prosumers playing an active role on smart grid energy management. However, in present energy management architectures, the lack of coordination among actors limits the capability of the grid to enable the mentioned trends. In this paper we tackle this problem by proposing an architecture that enables households to autonomously exchange energy blocks and flexibility services with neighbors, operators and market actors. The solution is based on a blockchain transactive platform. We focus on a market application, where households can trade energy with their neighbors, aimed to locally balancing renewable energy production. We propose a market mechanism and dynamic transport prices that provide an incentive for households to locally manage energy resources in a way that responds to both pro-sumer and operator needs. We evaluate the impact of such markets through comprehensive simulations using power flow analysis and realistic load profiles, providing valuable insight for the design of appropriate mechanisms and incentives.
  • PDF
    We introduce an open-source software Aamks for fire risk assessment. This article focuses on a component of Aamks - an evacuation simulator named a-evac. A-evac models evacuation of humans in the fire environment produced by CFAST fire simulator. In the article we discuss the probabilistic evacuation approach, automatic planning of exit routes, the interactions amongst the moving evacuees and the impact of smoke on the humans. The results consist of risk values based on FED, F-N curves and evacuation animations.
  • PDF
    Election control considers the problem of an adversary who attempts to tamper with a voting process, in order to either ensure that their favored candidate wins (constructive control) or another candidate loses (destructive control). As online social networks have become significant sources of information for potential voters, a new tool in an attacker's arsenal is to effect control by harnessing social influence, for example, by spreading fake news and other forms of misinformation through online social media. We consider the computational problem of election control via social influence, studying the conditions under which finding good adversarial strategies is computationally feasible. We consider two objectives for the adversary in both the constructive and destructive control settings: probability and margin of victory (POV and MOV, respectively). We present several strong negative results, showing, for example, that the problem of maximizing POV is inapproximable for any constant factor. On the other hand, we present approximation algorithms which provide somewhat weaker approximation guarantees, such as bicriteria approximations for the POV objective and constant-factor approximations for MOV. Finally, we present mixed integer programming formulations for these problems. Experimental results show that our approximation algorithms often find near-optimal control strategies, indicating that election control through social influence is a salient threat to election integrity.
  • PDF
    A first step to reach Theory of Mind (ToM) abilities (attribution of beliefs to others) in synthetic agents through sensorimotor interactions, would be to tag sensory data with agent typology and action intentions: autonomous agent X moved an object under the box. We propose a dual arm robotic setup in which ToM could be probed. We then discuss what measures can be extracted from sensorimotor interaction data (based on a correlation analysis) in the proposed setup that allow to distinguish self than other and other/inanimate from other/active with intentions. We finally discuss what elements are missing in current cognitive architectures to be able to acquire ToM abilities in synthetic agents from sensorimotor interactions, bottom-up from reactive agent interaction behaviors and top-down from the optimization of social behaviour and cooperation.
  • PDF
    Collective adaptive systems are an emerging class of networked computational systems, particularly suited in application domains such as smart cities, complex sensor networks, and the Internet of Things. These systems tend to feature large scale, heterogeneity of communication model (including opportunistic peer-to-peer wireless interaction), and require inherent self-adaptiveness properties to address unforeseen changes in operating conditions. In this context, it is extremely difficult (if not seemingly intractable) to engineer reusable pieces of distributed behaviour so as to make them provably correct and smoothly composable. Building on the field calculus, a computational model (and associated toolchain) capturing the notion of aggregate network-level computation, we address this problem with an engineering methodology coupling formal theory and computer simulation. On the one hand, functional properties are addressed by identifying the largest-to-date field calculus fragment generating self-stabilising behaviour, guaranteed to eventually attain a correct and stable final state despite any transient perturbation in state or topology, and including highly reusable building blocks for information spreading, aggregation, and time evolution. On the other hand, dynamical properties are addressed by simulation, empirically evaluating the different performances that can be obtained by switching between implementations of building blocks with provably equivalent functional properties. Overall, our methodology sheds light on how to identify core building blocks of collective behaviour, and how to select implementations that improve system performance while leaving overall system function and resiliency properties unchanged.
  • PDF
    Although it is widely recognised that the presence of groups influences microscopic and aggregated pedestrian dynamics, a precise characterisation of the phenomenon still calls for evidences and insights. The present paper describes micro and macro level original analyses on data characterising pedestrian behaviour in presence of counter-flows and grouping, in particular dyads, acquired through controlled experiments. Results suggest that the presence of dyads and their tendency to walk in a line-abreast formation influences the formation of lanes and, in turn, aggregated observables, such as overall specific flow.
  • PDF
    The Simple Temporal Problem (STP) is a fundamental temporal reasoning problem and has recently been extended to the Multiagent Simple Temporal Problem (MaSTP). In this paper we present a novel approach that is based on enforcing arc-consistency (AC) on the input (multiagent) simple temporal network. We show that the AC-based approach is sufficient for solving both the STP and MaSTP and provide efficient algorithms for them. As our AC-based approach does not impose new constraints between agents, it does not violate the privacy of the agents and is superior to the state-of-the-art approach to MaSTP. Empirical evaluations on diverse benchmark datasets also show that our AC-based algorithms for STP and MaSTP are significantly more efficient than existing approaches.
  • PDF
    Stackelberg equilibria have become increasingly important as a solution concept in computational game theory, largely inspired by practical problems such as security settings. In practice, however, there is typically uncertainty regarding the model about the opponent. This paper is, to our knowledge, the first to investigate Stackelberg equilibria under uncertainty in extensive-form games, one of the broadest classes of game. We introduce robust Stackelberg equilibria, where the uncertainty is about the opponent's payoffs, as well as ones where the opponent has limited lookahead and the uncertainty is about the opponent's node evaluation function. We develop a new mixed-integer program for the deterministic limited-lookahead setting. We then extend the program to the robust setting for Stackelberg equilibrium under unlimited and under limited lookahead by the opponent. We show that for the specific case of interval uncertainty about the opponent's payoffs (or about the opponent's node evaluations in the case of limited lookahead), robust Stackelberg equilibria can be computed with a mixed-integer program that is of the same asymptotic size as that for the deterministic setting.
  • PDF
    Constructing a spatial map of environmental parameters is a crucial step to preventing hazardous chemical leakages, forest fires, or while estimating a spatially distributed physical quantities such as terrain elevation. Although prior methods can do such mapping tasks efficiently via dispatching a group of autonomous agents, they are unable to ensure satisfactory convergence to the underlying ground truth distribution in decentralized manner when any of the agents fail. Since the types of agents utilized to perform such mapping are typically inexpensive and prone to failure, this typically results in poor overall mapping performance in real-world applications, which can in certain cases endanger human safety. To address this limitation of existing techniques, this paper presents a Bayesian approach for robust spatial mapping of environmental parameters by deploying a group of mobile robots capable of ad-hoc communication equipped with short-range sensors in the presence of hardware failures. Our approach first utilizes a variant of the Voronoi diagram to partition the region to be mapped into disjoint regions that are each associated with at least one robot. These robots are then deployed in a decentralized manner to maximize the likelihood that at least one robot detects every target in their associated region despite a non-zero probability of failure. A suite of simulation results is presented to demonstrate the effectiveness and robustness of the proposed method when compared to existing techniques.
  • PDF
    This paper presents a novel decentralized high-dimensional Bayesian optimization (DEC-HBO) algorithm that, in contrast to existing HBO algorithms, can exploit the interdependent effects of various input components on the output of the unknown objective function f for boosting the BO performance and still preserve scalability in the number of input dimensions without requiring prior knowledge or the existence of a low (effective) dimension of the input space. To realize this, we propose a sparse yet rich factor graph representation of f to be exploited for designing an acquisition function that can be similarly represented by a sparse factor graph and hence be efficiently optimized in a decentralized manner using distributed message passing. Despite richly characterizing the interdependent effects of the input components on the output of f with a factor graph, DEC-HBO can still guarantee no-regret performance asymptotically. Empirical evaluation on synthetic and real-world experiments (e.g., sparse Gaussian process model with 1811 hyperparameters) shows that DEC-HBO outperforms the state-of-the-art HBO algorithms.
  • PDF
    This paper addresses a task allocation problem for a large-scale robotic swarm, namely swarm distribution guidance problem. Unlike most of the existing frameworks handling this problem, the proposed framework suggests utilising local information available to generate its time-varying stochastic policies. As each agent requires only local consistency on information with neighbouring agents, rather than the global consistency, the proposed framework offers various advantages, e.g., a shorter timescale for using new information and potential to incorporate an asynchronous decision-making process. We perform theoretical analysis on the properties of the proposed framework. From the analysis, it is proved that the framework can guarantee the convergence to the desired density distribution even using local information while maintaining advantages of global-information-based approaches. The design requirements for these advantages are explicitly listed in this paper. This paper also provides specific examples of how to implement the framework developed. The results of numerical experiments confirm the effectiveness and comparability of the proposed framework, compared with the global-information-based framework.
  • PDF
    Transportation problems of large urban conurbations inspire search for new transportation systems, that meet high environmental standards, are relatively cheap and user friendly. The latter element also includes the needs of disabled and elderly people. This article concerns a new transportation system PRT - Personal Rapid Transit. In this article the attention is focused on the analysis of the efficiency of the PRT transport network. The simulator of vehicle movement in PRT network as well as algorithms for traffic management and control will be presented. The proposal of its physical implementation will be also included.
  • PDF
    This paper presents novel Gaussian process decentralized data fusion algorithms exploiting the notion of agent-centric support sets for distributed cooperative perception of large-scale environmental phenomena. To overcome the limitations of scale in existing works, our proposed algorithms allow every mobile sensing agent to choose a different support set and dynamically switch to another during execution for encapsulating its own data into a local summary that, perhaps surprisingly, can still be assimilated with the other agents' local summaries (i.e., based on their current choices of support sets) into a globally consistent summary to be used for predicting the phenomenon. To achieve this, we propose a novel transfer learning mechanism for a team of agents capable of sharing and transferring information encapsulated in a summary based on a support set to that utilizing a different support set with some loss that can be theoretically bounded and analyzed. To alleviate the issue of information loss accumulating over multiple instances of transfer learning, we propose a new information sharing mechanism to be incorporated into our algorithms in order to achieve memory-efficient lazy transfer learning. Empirical evaluation on real-world datasets show that our algorithms outperform the state-of-the-art methods.
  • PDF
    Executing multiple applications on a single MPSoC brings the major challenge of satisfying multiple quality requirements regarding real-time, energy, etc. Hybrid application mapping denotes the combination of design-time analysis with run-time application mapping. In this article, we present such a methodology, which comprises a design space exploration coupled with a formal performance analysis. This results in several resource reservation configurations, optimized for multiple objectives, with verified real-time guarantees for each individual application. The Pareto-optimal configurations are handed over to run-time management which searches for a suitable mapping according to this information. To provide any real-time guarantees, the performance analysis needs to be composable and the influence of the applications on each other has to be bounded. We achieve this either by spatial or a novel temporal isolation for tasks and by exploiting composable NoCs. With the proposed temporal isolation, tasks of different applications can be mapped to the same resource while with spatial isolation, one computing resource can be exclusively used by only one application. The experiments reveal that the success rate in finding feasible application mappings can be increased by the proposed temporal isolation by up to 30% and energy consumption can be reduced compared to spatial isolation.
  • PDF
    Multi-winner approval elections are seen in a variety of settings ranging from academic societies and associations to public elections. In such elections, it is often the case that ballot-length restrictions are enforced; that is, where voters have a limit on the number of candidates which they can vote for. Despite this common feature, there does not seem to be any theoretical justification for ballot-length restrictions (Laslier and Van der Straeten, 2016). This work endogenously derives the set of voter best-response ballot lengths under complete information and with general assumptions on voter utilities and voting rules. These results provide justification for some ballot-length restrictions observed in practice, however when considering equilibrium outcomes our analysis shows that this justification is no longer valid. Equilibrium analysis is considered for voters with lazy and truth-bias second-order tendencies and the equilibrium solution concept is pure-Nash equilibria. The key insights show that ballot-length restrictions or institutional features which make voting costly may lead to instability in election outcomes when voters have diverse preferences, via the non-existence of equilibria. On the other hand, when equilibria do exist they satisfy desirable properties which are not guaranteed by equilibria attained under costless voting and in the absence of ballot-length restrictions. In summary our results highlight a stark trade-off between stable and desirable election outcomes.
  • PDF
    In this study we examined how the size of non-formal groups between organization members affect the transfer of knowledge in the context of the efficiency and effectiveness of this process. To analyse the dynamics of the transfer of knowledge the cellular automata model was used. The model is based on local interactions between members of the organization, that take place in the nearest neighbourhood. These groups of close neighbours are represented by von Neumann's neighbourhood (four nearest-neighbours) and Moore's neighbourhood (four nearest-neighbours and four next-nearest neighbours) and complex neighbourhood (four nearest neighbours, four next-nearest neighbours and four next-next-neighbours). The results of the simulation show the influence of the size of the neighbourhood on the efficiency of knowledge transfer.
  • PDF
    Solid waste management is one of the existing challenges in urban areas and it is becoming a critical issue due to rapid increase in population. Appropriate solid waste management systems are important for improving the environment and the well being of residents. In this paper, an Internet of Things (IoT) architecture for real time waste monitoring and collection has been proposed; able to improve and optimize solid waste collection in a city. Netlogo Multiagent platform has been used to simulate real time monitoring and smart decisions on waste management. Waste filling level in bins and truck collection process are abstracted to a multiagent model and citizen are involved by paying the price for waste collection services. Furthermore, waste level data are updated and recorded continuously and are provided to decision algorithms to determine the vehicle optimal route for waste collection to the distributed bins in the city. Several simulation cases executed and results validated. The presented solution gives substantial benefits to all waste stakeholders by enabling the waste collection process to be more efficient.
  • PDF
    Lu and Boutilier proposed a novel approach based on "minimax regret" to use classical score based voting rules in the setting where preferences can be any partial (instead of complete) orders over the set of alternatives. We show here that such an approach is vulnerable to a new kind of manipulation which was not present in the classical (where preferences are complete orders) world of voting. We call this attack "manipulative elicitation." More specifically, it may be possible to (partially) elicit the preferences of the agents in a way that makes some distinguished alternative win the election who may not be a winner if we elicit every preference completely. More alarmingly, we show that the related computational task is polynomial time solvable for a large class of voting rules which includes all scoring rules, maximin, Copeland$^\alpha$ for every $\alpha\in[0,1]$, simplified Bucklin voting rules, etc. We then show that introducing a parameter per pair of alternatives which specifies the minimum number of partial preferences where this pair of alternatives must be comparable makes the related computational task of manipulative elicitation \NPC for all common voting rules including a class of scoring rules which includes the plurality, $k$-approval, $k$-veto, veto, and Borda voting rules, maximin, Copeland$^\alpha$ for every $\alpha\in[0,1]$, and simplified Bucklin voting rules. Hence, in this work, we discover a fundamental vulnerability in using minimax regret based approach in partial preferential setting and propose a novel way to tackle it.
  • PDF
    This work targets the problem of odor source localization by multi-agent systems. A hierarchical cooperative control has been put forward to solve the problem of locating source of an odor by driving the agents in consensus when at least one agent obtains information about location of the source. Synthesis of the proposed controller has been carried out in a hierarchical manner of group decision making, path planning and control. Decision making utilizes information of the agents using conventional Particle Swarm Algorithm and information of the movement of filaments to predict the location of the odor source. The predicted source location in the decision level is then utilized to map a trajectory and pass that information to the control level. The distributed control layer uses sliding mode controllers known for their inherent robustness and the ability to reject matched disturbances completely. Two cases of movement of agents towards the source, i.e., under consensus and formation have been discussed herein. Finally, numerical simulations demonstrate the efficacy of the proposed hierarchical distributed control.
  • PDF
    Model-free decentralized optimizations and learning are receiving increasing attention from theoretical and practical perspectives. In particular, two fully decentralized learning algorithms, namely Trial and Error (TEL) and Optimal Dynamical Learning (ODL), are very appealing for a broad class of games. In fact, ODL has the property to spend a high proportion of time in an optimum state that maximizes the sum of utility of all players. And the TEL has the property to spend a high proportion of time in an optimum state that maximizes the sum of utility of all players if there is a Pure Nash Equilibrium (PNE), otherwise, it spends a high proportion of time in an optimum state that maximizes a tradeoff between the sum of utility of all players and a predefined stability function. On the other hand, estimating the mean fraction of time spent in the optimum state (as well as the mean time duration to reach it) is challenging due to the high complexity and dimension of the inherent Markov Chains. In this paper, under some specific system model, an evaluation of the above performance metrics is provided by proposing an approximation of the considered Markov chains, which allows overcoming the problem of high dimensionality. A comparison between the two algorithms is then performed which allows a better understanding of their performances.
  • PDF
    It has been well established the theoretical analysis for the noise-induced consensus of the local-rule based Hegselmann-Krause (HK) dynamics in finite space. However, when system states are allowed in the infinite space, severe mathematical difficulties arise, and the problem remains open. In this paper, we completely resolved the case when system states are allowed in the infinite space, and also the critical noise strength is given.

Recent comments