New Zealand


Multi-Agent Path Finding (MAPF) is a well studied problem with many existing optimal algorithms capable of solving a wide variety of instances, each with its own strengths and weaknesses. 
While for some instances the fastest algorithm can be easily determined, not enough is known about their performance to predict the fastest algorithm for every MAPF instance, or what makes some instances more difficult than others. There is no clear answer for which features dominate the hardness of MAPF instances. 
In this work, we study how betweenness centrality affects the empirical difficulty of MAPF instances. To that end, we benchmark the largest and most complete optimal MAPF algorithm portfolio to date. We analyze the algorithms&#39; performance independently and as part of the portfolio, and discuss how betweenness centrality can be used to improve estimations of algorithm performance on a given instance of MAPF.

AAMAS 2022

Betweenness Centrality in Multi-Agent Path Finding

betweenness centrality

algorithm portfolio

multi-agent path finding

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).
<br>
<br>



A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).


Multi-Agent Path Finding (MAPF) is a well studied problem with many existing optimal algorithms capable of solving a wide variety of instances, each with its own strengths and weaknesses. 
While for some instances the fastest algorithm can be easily determined, not enough is known about their performance to predict the fastest algorithm for every MAPF instance, or what makes some instances more difficult than others. There is no clear answer for which features dominate the hardness of MAPF instances. 
In this work, we study how betweenness centrality affects the empirical difficulty of MAPF instances. To that end, we benchmark the largest and most complete optimal MAPF algorithm portfolio to date. We analyze the algorithms' performance independently and as part of the portfolio, and discuss how betweenness centrality can be used to improve estimations of algorithm performance on a given instance of MAPF.

technical paper


In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. 
In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.

Pareto optimal and popular house allocation with lower and upper quotas


Weighted voting games are typically used to model situations where a number of agents vote against or for a proposal. In such games, a proposal is accepted if a weighted sum of the votes exceeds a specified threshold. As the influence of a player over the outcome is not in general proportional to her assigned weight, various power indices have been proposed to measure each player's influence. The inverse power index problem is the problem of designing a weighted voting game that achieves a set of desirable influences as they are measured by a predefined power index. Recent work has shown that exactly solving the inverse power index problem is computationally intractable when the power index is in the class of semivalues --- a broad class that includes the popular Shapley value and Banzhaf index. In this work, we design efficient approximation algorithms for the inverse semivalue problem. We develop a unified methodology that leads to computationally efficient algorithms that solve the inverse semivalue problem to any desired accuracy. We perform an extensive experimental evaluation of our algorithms on both synthetic and real inputs. Our experiments show that our algorithms are scalable and achieve higher accuracy compared to previous methods in the literature.

Efficient Approximation Algorithms for the Inverse Semivalue Problem


Deep reinforcement learning (RL) has recently shown great promise in robotic continuous control tasks. Nevertheless, prior research in this vein center around the centralized learning setting that largely relies on the communication availability among all the components of a robot. However, agents in the real world often operate in a decentralised fashion without communication due to latency requirements, limited power budgets and safety concerns. By formulating robotic components as a system of decentralised agents, this work presents a decentralised multiagent reinforcement learning framework for continuous control. To this end, we first develop a cooperative multiagent PPO framework that allows for centralized optimisation during training and decentralised operation during execution. However, the system only receives a global reward signal which is not attributed towards each agent. To address this challenge, we further propose a generic game-theoretic credit assignment framework which computes agent-specific reward signals. Last but not least, we also incorporate a model-based RL module into our credit assignment framework, which leads to significant improvement in sample efficiency. We demonstrate the effectiveness of our framework on experimental results on Mujoco locomotion control tasks.

Multiagent Model-based Credit Assignment for Continuous Control


To deal with the underlying heterogeneous law enforcement problem
(LEPH), one needs to allocate police officers to dynamic tasks whose
locations, arrival times, and importance levels are unknown a priory.
Addressing this challenge and inspired by real police logs, this
research aims to solve the LEPH problem by using and comparing
three methods: Fisher market-based FMC_TAH+, swarm intelligence
HDBA, and Simulated Annealing SA algorithms. The three methods
were compared in this study for the performance measures that
are commonly used by law enforcement authorities. The results
indicate an advantage for FMC_TAH+ both in total utility and in the
average arrival time to tasks. Also, compared respectively to HDBA
and SA, FMC_TAH+ leads to 34% and 32% higher team utility in the
highest shift workload.

Towards addressing dynamic multi-agent task allocation in law enforcement


Multi-agent path planning (MAPP) in continuous spaces is a challenging problem with significant practical importance. One promising approach could first construct graphs approximating the spaces called roadmaps, then apply multi-agent pathfinding (MAPF) algorithms on those roadmaps to derive a set of conflict-free trajectories. While conventional studies have just utilized roadmap construction methods developed for single-agent planning, it remains largely unexplored what can serve as effective roadmaps for multiple agents and how we can construct them. To this end, we propose a novel concept of graph representations of the space named cooperative timed roadmaps (CTRMs). CTRMs enable each agent to focus on their important locations around potential solution paths, in a way to consider the behavior of other agents to avoid inter-agent collisions (i.e., "cooperative"), while being augmented in time direction to make it easy to derive a "timed" solution path. To construct CTRMs, we develop a machine learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions and uses the learned model to sample the vertices of CTRMs for new, previously-unseen problem instances. Our empirical evaluation revealed that the use of CTRMs significantly reduced the planning effort with acceptable overheads while maintaining its success rate and solution quality comparable to conventional roadmap construction approaches.

CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces


Planning for multi-robot coordination during long-horizon missions in complex environments requires considering robot resources, temporal constraints, and probabilistic uncertainty. This could be computationally expensive and impractical for online planning and execution. We propose a decoupled framework for temporal and probabilistic planning. At the high-level, we plan for multi-robot missions that require coordination amongst robots considering temporal and numeric constraints. The temporal plan is decomposed into low-level plans for individual robots. At the low-level, we perform online learning and adaptation due to unexpected probabilistic outcomes to achieve mission goals. Our framework learns over time from goal execution failures to improve the performance by (1) updating the learned domain model to reduce model prediction errors and (2) constraining the robot's capabilities which in turn improves goal allocation. The approach provides a solution to planning problems by pondering mission execution quality over implementation time. We demonstrate our approach to experiments involving a fleet of heterogeneous robots.

Planning, Execution, and Adaptation for Multi-Robot Systems using Probabilistic and Temporal Planning


A new mobile attention economy has emerged with the explosive growth of short-video apps such as TikTok. In this internet market, a short-video platform encourages its influencers to attract users by creating various short-form videos, and allows advertisers to display their short-video ads. There are two options for the advertisers: one is to bid for platform advert slots in a similar way to search engine auctions; the other is to pay an influencer to make engaging short videos and promote them through the influencer's channel. The second option will generate a higher conversion ratio if advertisers choose the right influencers whose followers match their target market. Although displaying influencer ads will generate less revenue, it is more engaging than platform ads, which is better for maintaining user traffic. Therefore, it is crucial for a platform to balance these factors by establishing a sustainable business agreement with its influencers and advertisers.
In this paper, we develop a two-stage solution for a platform to maximize short-term revenue and long-term user traffic maintenance. In the first stage, we estimate the impact of user traffic generated by displaying influencer ads and characterize the user traffic the platform should allocate to influencers for overall revenue maximization. We deploy an optimal $(1-1/e)$-competitive algorithm for ad slot allocation in the second stage. To complement this analysis, we examine the ratio of the revenue generated by our online algorithm to the optimal offline revenue. Our simulation results show that this ratio is 0.94 on average, which is much higher than $(1-1/e)$ and outperforms four baseline algorithms.

Revenue and User Traffic Maximization in Mobile Short-Video Advertising


Motivated by a broad class of mobile intervention problems, we propose and study restless multi-armed bandits (RMAB) with network effects. In our model, arms are partially recharging and connected through a graph, so that pulling one arm also improves the state of neighboring arms, significantly extending the previously studied setting of fully recharging bandits with no network effects. Our model is motivated by mobile intervention applications, where mobile services visit different locations to provide interventions, relevant in a variety of domains including mobile health interventions and food security, in which network effects arise due to regular population movements (such as commuting between home and work). We show that network effects in RMABs induce strong reward coupling that is not accounted for by existing solution methods. We propose a new solution approach for networked RMAB that exploits concavity structure that arises under natural assumptions on the structure of intervention effects. We show that our proposed algorithm is optimal for a large class of networked RMAB settings, and empirically demonstrate that it consistently outperforms state-of-the-art baselines.

Networked Restless Multi-Armed Bandits for Mobile Interventions


Peer incentivation (PI) is a recent approach, where all agents learn to reward or to penalize each other which often leads to emergent cooperation. Current PI mechanisms implicitly assume a flawless communication channel in order to exchange rewards. These rewards are directly integrated into the learning process without any chance to respond with feedback. Furthermore, most PI approaches rely on global information which limits scalability and applicability to real-world scenarios, where only local information is accessible. In this paper, we propose Mutual Acknowledgment Token Exchange (MATE), a PI approach defined by a two-phase communication protocol to mutually exchange acknowledgment tokens to shape individual rewards. Each agent evaluates the monotonic improvement of its individual situation in order to accept or reject acknowledgment requests from other agents. MATE is a completely decentralized approach which only requires local communication and information. We evaluate MATE in three social dilemma domains. Our results show that MATE is able to achieve and maintain significantly higher levels of cooperation than previous PI approaches. In addition, we evaluate the robustness of MATE in more realistic scenarios, where agents can defect from the protocol and where communication failures can occur.

Emergent Cooperation from Mutual Acknowledgment Exchange


We propose Streaming Bandits, a Restless Multi-Armed Bandit(RMAB) framework in which heterogeneous arms may arrive and leave the system after staying on for a finite lifetime. Streaming Bandits naturally capture the health-intervention planning problem, where health workers must manage the health outcomes of a patient cohort while new patients join and existing patients leave the cohort each day. Our contributions are as follows: (1) We de-rive conditions under which our problem satisfies indexability, a pre-condition that guarantees the existence and asymptotic optimality of the Whittle Index solution for RMABs. We establish the conditions using a polytime reduction of the Streaming Banditsetup to regular RMABs. (2) We further prove a phenomenon that we call index decay — whereby the Whittle index values decrease for short residual lifetimes — driving the intuition underpinning our algorithm. (3) We propose a novel and efficient algorithm to compute the index-based solution for Streaming Bandits. Unlike previous methods, our algorithm does not rely on solving the costly finite horizon problem on each arm of the RMAB, thereby lowering the computational complexity compared to existing methods. (4) Finally, we evaluate our approach via simulations run on real-world data sets from a tuberculosis patient monitoring task and an intervention planning task for improving maternal healthcare, in addition to other synthetic domains. Across the board, our algorithm achieves a 2-orders-of-magnitude speed-up over existing methods while maintaining the same solution quality

Betweenness Centrality in Multi-Agent Path Finding

Downloads

Next from AAMAS 2022

Pareto optimal and popular house allocation with lower and upper quotas

Similar lecture

Multi-Agent Path Finding for Precedence-Constrained Goal Sequences

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Betweenness Centrality in Multi-Agent Path Finding

.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 2022

Pareto optimal and popular house allocation with lower and upper quotas

Similar lecture

Multi-Agent Path Finding for Precedence-Constrained Goal Sequences

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads