New Zealand

Mohamad T. Shahab and Moustafa Elshafei (April 11th 2019). Distributed Optimization of Multi-Robot Motion with Time-Energy Criterion, Path Planning for Autonomous Vehicles - Ensuring Reliable Driverless Navigation and Control Maneuver, Umar Zakir Abdul Hamid, Volkan Sezer, Bin Li, Yanjun Huang and Muhammad Aizzat Zakaria, IntechOpen, DOI: 10.5772/intechopen.85668. 

Evolutionary optimization is a generic population-based metaheuristic that can be adapted to solve a wide variety of optimization problems and has proven very effective for combinatorial optimization problems. However, the potential of this metaheuristic has not been utilized in Distributed Constraint Optimization Problems (DCOPs), a well-known class of combinatorial optimization problems prevalent in Multi-Agent Systems. In this paper, we present a novel population-based algorithm, Anytime Evolutionary DCOP (AED), that uses evolutionary optimization to solve DCOPs. In AED, the agents cooperatively construct an initial set of random solutions and gradually improve them through a new mechanism that considers an optimistic approximation of local benefits. Moreover, we present a new anytime update mechanism for AED that identifies the best among a distributed set of candidate solutions and notifies all the agents when a new best is found. In our theoretical analysis, we prove that AED is anytime. Finally, we present empirical results indicating AED outperforms the state-of-the-art DCOP algorithms in terms of solution quality.

AAMAS 2020

An Anytime Evolutionary DCOP Algorithm

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

technical paper

Playing Games in the Dark: An approach for cross-modality transfer in reinforcements learning

Rationals vs Byzantine Players in Committee-Based Blockchains

Toward enabling next-generation robots capable of socially intelligent interaction with humans, we present a computational model of interactions in a social environment of multiple agents and multiple groups. The Multiagent Group Perception and Interaction (MGpi) network is a deep neural network that predicts the appropriate social action to execute in a group conversation (e.g., speak, listen, respond, leave), taking into account neighbors' observable features (e.g., location of people, gaze orientation, distraction, etc.). A central component of MGpi is the Kinesic-Proxemic-Message (KPM) gate, that performs social signal gating to extract important information from a group conversation. In particular, KPM gate filters incoming social cues from nearby agents by observing their body gestures (kinesics) and spatial behavior (proxemics). The MGpi network and its KPM gate are learned via imitation learning, using demonstrations from our designed social interaction simulator. Further, we demonstrate the efficacy of the KPM gate as a social attention mechanism, achieving state-of-the-art performance on the task of group identification without using explicit group annotations, layout assumptions, or manually chosen parameters.

MGpi: A Computational Model of Multiagent Group Perception and Interaction

Multi Agent Path Finding (MAPF) is the problem of planning paths for agents to reach their targets from their start locations, such that the agents do not collide while executing the plan. In safety-critical systems, the plan is typically checked by a human supervisor, who decides on whether to allow its execution. In such cases, we wish to convince the human that the plan is indeed collision free. To this end, we propose an \emph{explanation scheme} for MAPF, which bases explanations on simplicity of visual verification by human's cognitive process. The scheme decomposes a plan into segments such that within each segment, the paths of the agents are disjoint. Then, we can convince the supervisor that the plan is collision free using a small number of images (dubbed an \emph{explanation}). In addition, we can measure the simplicity of a plan by the number of segments required for the decomposition. We study the complexity of algorithmic problems that arise by the explanation scheme, as well as the tradeoff between the length (makespan) of a plan and its minimal decomposition. We also provide experimental results of our scheme both in a continuous and in a discrete setting.

Explainable Multi Agent Path Finding

Emergency Response Management (ERM) is a critical problem faced by communities across the globe. Despite this, it is common for ERM systems to follow myopic decision policies in the real world. Principled approaches to aid ERM decision-making under uncertainty have been explored but have failed to be accepted into real systems. We identify a key issue impeding their adoption --- algorithmic approaches to emergency response focus on reactive, post-incident dispatching actions, i.e. optimally dispatching a responder \textit{after} incidents occur. However, the critical nature of emergency response dictates that when an incident occurs, first responders always dispatch the closest available responder to the incident. We argue that the crucial period of planning for ERM systems is not post-incident, but between incidents. This is not a trivial planning problem --- a major challenge with dynamically balancing the spatial distribution of responders is the complexity of the problem. An orthogonal problem in ERM systems is planning under limited communication, which is particularly important in disaster scenarios that affect communication networks. We address both problems by proposing two partially decentralized multi-agent planning algorithms that utilize heuristics and exploit the structure of the dispatch problem. We evaluate our proposed approach using real-world data, and find that in several contexts, dynamic re-balancing the spatial distribution of emergency responders reduces both the average response time as well as its variance.

On Algorithmic Decision Procedures in Emergency Response Systems in Smart and Connected Communities

Timely evacuation is a standard recommendation by local agencies before disaster events such as hurricanes, which have enough advance notice. However, it has been observed in many recent disasters (e.g., Sandy), that only a small fraction of the population evacuates in time. Recent work by social scientists has examined the factors that influence household evacuation decisions; in addition to individual factors it has been found that peer effect plays a role in this decision but in two opposing ways. Specifically, households are motivated to evacuate if their neighbors evacuate. However, if too many neighbors leave then some households have concerns of looting and crime, and they choose not to evacuate. This makes the dynamics of evacuation very complex. In this paper, we use a detailed agent based model to study the dynamics of evacuation in Virginia's coastal region. We use data from a large survey and social contagion and collective action theories to develop the model. We evaluate different strategies to increase evacuation.

Increasing Evacuation During Disaster Events

The challenge of developing powerful and general Reinforcement Learning (RL) agents has received increasing attention in recent years. Much of this effort has focused on the single-agent setting, in which an agent maximizes a predefined extrinsic reward function. However, a long-term question inevitably arises: how will such independent agents cooperate when they are continually learning and acting in a shared multi-agent environment? Observing that humans often provide incentives to influence others' behavior, we propose to equip each RL agent in a multi-agent environment with the ability to give rewards directly to other agents, via a learned incentive function. Each agent learns the incentive function by considering how the given incentives affect its own extrinsic objective, through the learning of agents who receive incentives. We demonstrate in experiments that such agents significantly outperform policy gradient agents and opponent-shaping agents in a small yet challenging general-sum Markov game. Our work points toward a more general research program of endowing agents with expanded capabilities for incentivizing others to ensure the common good in a multi-agent future.

Learning to Incentivize Other Learning Agents

This paper proposes an approach that aims to automatically visualize large-scale text-based online discussions. The ultimate goal is to develop an automatic visualization tool which helps to understand the content of large-scale text-based online discussions. To support this au- tomatic visualization tool, an effective discussion visualization approach is needed. Toward this end, we propose a discussion visualization method using D3.js which is a JavaScript libraly. The proposed method employs issue-based information system (IBIS), as a suitable format for struc- turing online discussions. By visualizing based on the IBIS discussion structure, it becomes possible to enhance the intuitive understanding of the contents of discussions and to find the active threads intuitively. In particular, this paper aims to support the understanding of specific topics that users are interested in. In order to evaluate the proposed approach, a set of experiments has been conducted on the data collected from the discussions in the online discussion support system called D-Agree. The experimental results demonstrate that the proposed approach is effective for supporting the understanding of discussion contents.

Downloads

Next from AAMAS 2020

Playing Games in the Dark: An approach for cross-modality transfer in reinforcements learning

Similar lecture

New Algorithms for Continuous Distributed Constraint Optimization Problems

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2020

Playing Games in the Dark: An approach for cross-modality transfer in reinforcements learning

Similar lecture

New Algorithms for Continuous Distributed Constraint Optimization Problems

Downloads