New Zealand


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.

AAMAS 2022

Refined Hardness of Distance-Optimal Multi-Agent Path Finding

grid graphs

multi-robot motion planning

np-hardness

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

technical paper


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.

Trajectory Coordination based on Distributed Constraint Optimization Techniques in Unmanned Air Traffic Management


The popularity of mobility-on-demand (MoD) systems boosts the need for online collective multiagent planning, where spatially distributed servicing agents are planned to meet dynamically arriving demands. For city-scale MoDs with a population of agents, it is necessary to find a balance between computation time (i.e., real-time) and solution quality (i.e., the number of demands served). Directly using an offline policy can guarantee real-time, but cannot be dynamically adjusted to real agent and demand distributions. On the other hand, search-based online planning methods are adaptive. However, they are computationally expensive and cannot scale up.

In this paper, we propose a principled online multiagent planning method, which reuses and improves the offline policy in an anytime manner. We first model MoDs as a collective Markov Decision Process ($\mathbb{C}$-MDP) where the history collective behavior of agents affects the joint reward. We propose a novel state value function to evaluate the policy, and a gradient ascent (GA) technique to improve the policy. We show that GA-based policy iteration (GA-PI) on local policy can converge to global optima of $\mathbb{C}$-MDP. Finally, given real-time information, the offline policy is used as the default plan and GA-PI is used to improve it and generate an online plan. Experimentally, the proposed offline policy reuse method significantly outperforms standard online multiagent planning methods on MoD systems like ride-sharing and security traffic patrolling in terms of computation time and solution quality.

Online Collective Multiagent Planning by Offline Policy Reuse with Applications to City-Scale Mobility-on-Demand Systems


The use of norms to guide and coordinate interactions has gained tremendous attention in the multiagent community. However, as the interest moves towards dynamic socio-technical systems, where human and software agents interact and interactions are required to adapt to the human's changing needs, new challenges arise. For instance, different agents (human or software) might not have the same understanding of what it means to violate a norm (e.g., what characterizes hate speech), or that their understanding of a norm might change over time (e.g., what constitutes an acceptable response time). The challenge is to address these issues by learning the meaning of a norm violation from the limited interaction data. For this, we propose a framework that learns and updates the meaning of a norm violation from interaction data through a combination of ensemble and incremental learning techniques. Ensemble learning handles the imbalance class distribution of the interaction stream, and incremental learning is used to continuously update the ensemble models as community members interact, which is an essential feature to keep the ensemble models in accordance with the latest community view on the meaning of norm violation. We evaluate the proposed approach in the use case of Wikipedia article edits, where interactions revolve around editing articles and the norm in question is prohibiting vandalism. Results show that the proposed framework can learn the meaning of a norm violation in a setting with data imbalance and concept drift.

Ensemble and Incremental Learning for Norm Violation Detection


The evolving relationship between humans and technology entails increasing concerns about the impact on ethical issues such as bias, unfairness, and lack of accountability. There is thus a need for consistent responses to multiple-user social dilemma that arise during interactions in sociotechnical systems, where combinations of humans and technical agents work together as ethical duos. The outcomes of these systems can be evaluated by the values that participating humans hold, which in turn influence the development of norms used to guide acceptable behaviour. However, when values are misjudged or norms conflict, systematic methodologies are needed to resolve the dilemmas that arise in satisfactory ways.

Adapting a macro-ethics perspective, in which ethics is addressed through the governance of sociotechnical systems with multiple agents rather than the actions of single agents, we propose that ethical principles can be mechanised in a way that considers a variety of contextual inputs to produce a satisfactory outcome. The application of these ethical principles would enable practitioners to think analytically and systematically about the multiple-user social dilemmas that occur in these systems to resolve them in satisfactory ways. In order to achieve this, we need to formulate new ways of (1) developing consistent responses to multiple-user social dilemmas, (2) categorizing ethical principles used in AI, and (3) systematically operationalizing ethical principles.

Macro Ethics for Governing Equitable Sociotechnical Systems


We develop a learning-based algorithm for the distributed formation control of networked multi-agent systems governed by unknown, nonlinear dynamics. The proposed algorithm integrates neural network-based learning with adaptive control in a two-step procedure. In the first step, each agent learns a controller, represented as a neural network, using training data that correspond to a collection of formation tasks and agent parameters. These parameters and tasks are derived by varying the nominal agent parameters and the formation specifications of the task in hand, respectively. In the second step of the algorithm, each agent incorporates the
trained neural network into an online and adaptive control policy in such a way that the behavior of the multi-agent closed-loop system satisfies a user-defined formation task. Both the learning phase and the adaptive control policy are distributed, in the sense that each agent computes its own actions using only local information from its neighboring agents.

Non-Parametric Neuro-Adaptive Coordination of Multi-Agent Systems

This paper tackles the problem of learning generalizable congestion-mitigation strategies in simple representations of traffic. In particular, we look to mixed-autonomy ring roads as depictions of instabilities common to many generic settings, and ask the question: What features are needed to ensure that policies here can be adapted to typical multi-lane highways? To answer this, we study the implications of the scale of the source task and the modeling of pseudo-lane change events within it on the transferability of policies learned to complex networks. Our findings suggest that negating the effects of boundary conditions and introducing lane changes that approximately match trends in more complex systems can significantly improve the generalizability of learned behaviors.

Learning Generalizable Multi-Lane Mixed Autonomy Control Strategies in Single-Lane Settings


The Belief Desire Intention model is a widely used architecture for
developing rational agents. Because of its expressiveness, the task
of programming a BDI agent can be challenging, especially when
applied to safety-critical scenarios. In such scenarios, it is important
to provide a safeguard for the critical behaviour of the agent. In this
poster, we summarise how to extend the agent’s reasoning cycle
in the BDI model with safety shields. A safety shield works as a
sandbox for the agents’ plans that is enforced at runtime so that the
agent behaves according to a safety formal specification. A runtime
monitor is automatically synthesised from a shield to detect any
failure that is within the scope of the shielded plan.

Safety Shields, an Automated Failure Handling Mechanism for BDI Agents

We introduce the Forecasting Argumentation Framework (FAF), a novel argumentation framework for forecasting informed by recent judgmental forecasting research. FAFs comprise update frameworks which empower (human or artificial) agents to argue over time with and about probability of scenarios, whilst flagging perceived irrationality in their behaviour with a view to improving their forecasting accuracy. FAFs include three argument types with future forecasts and aggregate the strength of these arguments to inform estimates of the likelihood of scenarios. We provide an example of an implementation of FAFs for supporting forecasting agents.

Refined Hardness of Distance-Optimal Multi-Agent Path Finding

Downloads

Next from AAMAS 2022

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

Similar lecture

Multi-Agent Path Finding for Precedence-Constrained Goal Sequences

Refined Hardness of Distance-Optimal 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

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

Similar lecture

Multi-Agent Path Finding for Precedence-Constrained Goal Sequences

Downloads