New Zealand



We study strategic network formation games in which agents at- tempt to form (costly) links in order to maximize their network centrality. Our model derives from Jackson and Wolinsky’s symmetric connection model, but allows for heterogeneity in agent utilities by replacing decay centrality (implicit in the J-W model) by a va- riety of classical centrality measures, as well as game-theoretic measures of centrality. We are primarily interested in characteriz- ing the asymptotically pairwise stable networks, i.e. those networks that are pairwise stable for all sufficiently small, positive edge costs. We uncover a rich typology of stability:

- we give an axiomatic approach to network centrality that allows us to predict the stable network for a rich set of com- bination of centrality utility functions, yielding stable networks with features reminiscent of structural properties such as &quot;core periphery&quot; and &quot;rich club&quot; networks.
- We show that a simple variation on the model renders it universal, i.e. every network may be a stable network.
- We also show that often we can infer a significant amount about agent utilities from the structure of stable networks.

AAMAS 2022

Being Central on the Cheap: Stability in Heterogeneous Multiagent Centrality Games

asymptotically pairwise stable networks

centrality measures

strategic network formation

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



We study strategic network formation games in which agents at- tempt to form (costly) links in order to maximize their network centrality. Our model derives from Jackson and Wolinsky’s symmetric connection model, but allows for heterogeneity in agent utilities by replacing decay centrality (implicit in the J-W model) by a va- riety of classical centrality measures, as well as game-theoretic measures of centrality. We are primarily interested in characteriz- ing the asymptotically pairwise stable networks, i.e. those networks that are pairwise stable for all sufficiently small, positive edge costs. We uncover a rich typology of stability:

- we give an axiomatic approach to network centrality that allows us to predict the stable network for a rich set of com- bination of centrality utility functions, yielding stable networks with features reminiscent of structural properties such as "core periphery" and "rich club" networks.
- We show that a simple variation on the model renders it universal, i.e. every network may be a stable network.
- We also show that often we can infer a significant amount about agent utilities from the structure of stable networks.

technical paper


The potential of reinforcement learning (RL) to deliver aligned and performant agents is partially bottlenecked by the reward engineering problem. One alternative to heuristic trial-and-error is preference-based RL (PbRL), where a reward function is inferred from sparse human feedback. However, prior PbRL methods lack interpretability of the learned reward structure, which hampers the ability to assess robustness and alignment. We propose an online, active preference learning algorithm that constructs reward functions with the intrinsically interpretable, compositional structure of a tree. Using both synthetic and human-provided feedback, we demonstrate sample-efficient learning of tree-structured reward functions in several environments, then harness the enhanced interpretability to explore and debug for alignment.

Interpretable Preference-based Reinforcement Learning with Tree-Structured Reward Functions


As artificial agents become increasingly prevalent in our daily lives, it becomes imperative to equip them with an awareness of societal norms; specifically, the ability to account for and be considerate towards others they may cohabit with. In this work, we explore the ability for an agent trained through reinforcement learning to exhibit sympathetic behaviours towards another (independent) agent in the environment. We propose to achieve such behaviors by first inferring the reward function of the independent agent, through inverse reinforcement learning, and subsequently learning a policy based on a sympathetic reward function - a convex combination of the inferred rewards together with the agent's own rewards. The corresponding weighting function, which we refer to as the sympathy function, is computed online as a function of the estimated return of the agent's taken action relative to that of other possible actions it could have taken. We evaluate our approach on adversarial as well as assistive environment settings, and demonstrate the ability of our sympathetic agent to perform well at its own goal, while simultaneously giving due consideration to another agent in its environment. We also perform systematic ablation studies to identify the influence of the various components of our proposed framework.

Sympathy based Reinforcement Learning agents


As reinforcement learning (RL) continues to improve and be applied in situations alongside humans, the need to explain the learned behaviors of RL agents to end-users becomes more important. Strategies for explaining the reasoning behind an agent's policy, called policy-level explanations, can lead to important insights about both the task and the agent's behaviors. Following this line of research, in this work, we propose a novel approach that summarizes an agent's policy in the form of a directed graph with natural language descriptions. A decision tree based clustering method is utilized to abstract the state space of the task into fewer, condensed states which makes the policy graphs more digestible to end-users. This abstraction allows the users to control the size of the policy graph to achieve their desired balance between comprehensibility and accuracy. In addition, we develop a heuristic optimization method to find the most explainable graph policy and present it to the users. Finally, we use the user-defined predicates to enrich the abstract states with semantic meaning. We test our approach on five RL tasks, using both deterministic and stochastic policies, and show that our method is: (1) agnostic to the algorithms used to train the policies, and (2) comparable in accuracy and superior in explanation capabilities to existing baselines. Especially, when provided with our explanation graph, end-users are able to accurately interpret policies of trained RL agents 80% of the time, compared to 10% when provided with the next best baseline. We uploaded our code and datasets as supplementary material for ensuring the reproducibility of our research findings.

CAPS: Comprehensible Abstract Policy Summaries for Explaining Reinforcement Learning Agents


We address the problem of routing a team of drones and trucks over large-scale urban road networks. To conserve their limited flight energy, drones can use trucks as temporary modes of transit en route to their own destinations. Such coordination can yield significant savings in total vehicle distance traveled, i.e., truck travel distance and drone flight distance, compared to operating drones and trucks independently. But it comes at the potentially prohibitive computational cost of deciding which trucks and drones should coordinate and when and where it is most beneficial to do so. We tackle this fundamental trade-off by decoupling our overall intractable problem into tractable sub-problems that we solve stage-wise. The first stage solves only for trucks, by computing paths that make them more likely to be useful transit options for drones. The second stage solves only for drones, by routing them over a composite of the road network and the transit network defined by truck paths from the first stage. We design a comprehensive algorithmic framework that frames each stage as a multi-agent path finding problem and implement two distinct methods for solving them. We evaluate our approach on extensive simulations with up to 100 agents on the real-world Manhattan road network containing nearly 4500 vertices and 10000 edges. Our framework saves on more than 50% of vehicle distance traveled compared to independently solving for trucks and drones, and computes solutions for all settings within 5 minutes on commodity hardware.

Coordinated Multi-Agent Path Finding for Drones and Trucks over Road Networks


Formal models of multi-robot behaviour are fundamental to planning, simulation, and model checking techniques. However, existing models are invalidated by strong assumptions that fail to capture execution-time multi-robot behaviour, such as simplistic duration models or synchronisation constraints. In this paper we propose a novel multi-robot Markov automaton formulation which models asynchronous multi-robot execution in continuous time. Robot dynamics are captured using phase-type distributions over action durations. Moreover, we explicitly model the effects of robot interactions, as they are a key factor for the duration of action execution. We also present a scalable discrete-event simulator which yields realistic statistics over execution-time robot behaviour by sampling through the Markov automaton. We validate our model and simulator against a Gazebo simulation in a range of multi-robot navigation scenarios, demonstrating that our model accurately captures high-level multi-robot behaviour.

Context-Aware Modelling for Multi-Robot Systems Under Uncertainty


To become helpful assistants in our daily lives, robots must be able to understand the effects of their actions on their environment. A modern approach to this is the use of a physics simulation, where often very general simulation engines are utilized. As a result, specific modeling features, such as multi-contact simulation or fluid dynamics, may not be well represented. To improve the representativeness of simulations, we propose a framework for combining estimations of multiple heterogeneous simulations into a single one. The framework couples multiple simulations and reorganizes them based on semantically annotated action sequence information. While each object in the scene is always covered by a simulation, this simulation responsibility can be reassigned online. In this paper, we introduce the concept of the framework, describe the architecture, and demonstrate two example implementations. Eventually, we demonstrate how the framework can be used to extract semantic information from action executions on the humanoid robot Rollin’ Justin and how this information is used to assess whether an action sequence is executed successful or not.

Multi-Agent Heterogeneous Digital Twin Framework with Dynamic Responsibility Allocation for Complex Task Simulation


We study the computational complexity of multi-agent path finding (MAPF) on grid graphs.
Given a graph $G$ and a set of agents, each having a start and target vertex, the goal is to find collision-free paths minimizing the total distance traveled.
Formulations restricting $G$ to be a 2D grid are ubiquitous, as it conveniently allows for modeling well-structured environments (e.g., warehouses).
Previous hardness results had $G$ either (1) be a 2D grid or (2) have more than one vertex unoccupied by a agent, but never considered both properties simultaneously.
The most restricted result for property (2) was shown for (non-grid) planar graphs.
We refine previous results by proving that distance-optimal MAPF remains NP-hard for both properties simultaneously, thereby settling an open problem posed in Banfi et al. (2017).
We present a reduction directly from 3SAT using simple gadgets, making our proof arguably more comprehensible and informative.
We explain the potential benefits of these qualities towards positive results.
Furthermore, our result is the first linear-time/size reduction for the case where $G$ is planar, appearing nearly four decades after the first related result.
This allows us to go a step further and exploit the Exponential Time Hypothesis (ETH) to obtain an exponential lower bound for the running time.
To the best of our knowledge, this is the first application of ETH to show \textit{any} concrete lower bound for MAPF.
Finally, as a stepping stone, we also show hardness for the monotone case, in which agents move one by one with no intermediate stops.

Refined Hardness of Distance-Optimal Multi-Agent Path Finding


Ineffective traffic signal control is one of the major causes of congestion in urban road networks. Dynamically changing traffic conditions and live traffic state estimation are fundamental challenges that limit the ability of the existing signal infrastructure in rendering individualized signal control in real-time. We use deep reinforcement learning (DRL) to address these challenges. Due to economic and safety constraints associated training such agents in the real world, a practical approach is to do so in simulation before deployment. Domain randomisation is an effective technique for bridging the \textit{reality gap} and ensuring effective transfer of simulation-trained agents to the real world. In this paper, we develop a fully-autonomous, vision-based DRL agent that achieve adaptive signal control in the face of complex, imprecise, and dynamic traffic environments. Our agent uses live visual data from an intersection to extensively perceive and subsequently act upon the traffic environment. Employing domain randomisation, we examine our agent's generalisation capabilities under varying traffic conditions in both the simulation and the real-world environments. In a diverse validation set independent of training data, our traffic control agent reliably adapted to novel traffic situations and demonstrated a positive transfer to previously unseen real intersections despite being trained entirely in simulation.

Fully-Autonomous, Vision-based Traffic Signal Control: from Simulation to Reality


On-demand ride-pooling (e.g., UberPool, GrabShare) services focus on serving multiple different customer requests using each vehicle, i.e., an empty or partially filled vehicle can be assigned requests from different passengers with different origins and destinations. On the other hand, in Taxi on Demand (ToD) services (e.g., UberX), one vehicle is assigned to only one request at a time. On-demand ride pooling is not only beneficial to customers (lower cost), drivers (higher revenue per trip) and aggregation companies (higher revenue), but is also of crucial importance to the environment as it reduces the number of vehicles required on the roads. 

Since each vehicle has to be matched with a combination of customer requests, the matching problem in ride pooling is significantly more challenging. Due to this complexity, most existing solutions to ride-pooling problem are myopic in that they either ignore future impact of current matches or the impact of other taxis in the expected revenue earned by a taxi. In this paper, we build on an approximate dynamic programming framework to consider impact of other taxis on the value of a taxi (expected revenue earned until end of horizon) through a novel hierarchical value decomposition framework. On a real world city scale taxi data set, we show an improvement of up to 10\% in requests served compared to existing best methods for ride pooling.

Hierarchical Value Decomposition for Effective On-demand Ride-Pooling


In this paper, we explore a multiagent-based deconfliction strategy in Unmanned Air Traffic Management (UTM), as to equip autonomous unmanned aerial vehicles (UAV) with decision capabilities to update their trajectories (4D contracts) when facing unpredictable events or when priority trajectories are added to the flight space. Indeed, current initiatives for UTM envision a multi-layered management system where the lowest one is composed of either autonomous UAV or human-operated one, that may have to react to incidents and emergencies, while sticking to the contracted 4D trajectories. We propose here an agent-based approach, where UAVs, being aware of close potential conflicts provided by the UTM communication layer, can negociate directly, without central UTM control, to update trajectories and solve resulting conflicts in a decentralized manner, as to avoid access to a central decision bottleneck and to provide reactive deconfliction. We propose both uncoordinated and coordinated behaviors, that we experimentally evaluate on dense scenarios within a limited area with numerous 4D contracts, potential incidents and emergency procedures.

Being Central on the Cheap: Stability in Heterogeneous Multiagent Centrality Games

Downloads

Next from AAMAS 2022

Interpretable Preference-based Reinforcement Learning with Tree-Structured Reward Functions

Similar lecture

Parameterized Algorithms for Kidney Exchange

Being Central on the Cheap: Stability in Heterogeneous Multiagent Centrality Games

.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

Interpretable Preference-based Reinforcement Learning with Tree-Structured Reward Functions

Similar lecture

Parameterized Algorithms for Kidney Exchange

Downloads