New Zealand

Carlos Astengo-Noguez, Gildardo Sanchez-Ante, Jose Ramon Calzada and Ricardo Sisnett-Hernandez (March 1st 2010). Multi-Robot Collective Path Finding in Dynamic Environments, Mobile Robots Navigation, Alejandra Barrera, IntechOpen, DOI: 10.5772/8983.

Kyle Stanhouse, Chris Kitts and Ignacio Mas (September 28th 2016). Time-Energy Optimal Cluster Space Motion Planning for Mobile Robot Formations, Recent Advances in Robotic Systems, Guanghui Wang, IntechOpen, DOI: 10.5772/64615.

Multi-Agent Path Finding (MAPF) plays an important role in many real-life applications where autonomous agents must coordinate to reach their goals without collisions. MAPF problems often take place in structured environments that are usually assumed to be static and known in advance. In this paper, we introduce C-MAPF, i.e., MAPF in Configurable environments, a novel variant of the MAPF problem in which the environment is configurable, namely its structure and topology can be controlled within some given constraints. Consider, for instance, a warehouse logistics application: the environment can be changed (at least to some degree) by the managers of the warehouse, for example by re-arranging the positions of the shelves or by removing or adding temporary walls. We study the properties of the C-MAPF problem and we devise two algorithms for solving it, both based on Conflict-Based Search (CBS), a state-of-the-art MAPF algorithm. First, we present Parallel CBS (P-CBS), that searches for a solution by simultaneously considering all the possible configurations of the environment. We then present Abstract CBS (A-CBS), an extended version of the CBS algorithm that solves C-MAPF problems by introducing a new type of conflict on the allowable configurations of the environment. We prove that our solvers are both complete and optimal and we experimentally assess their performance in different settings.


AAMAS 2020

Multi-Agent Path Finding in Configurable Environments

configurable environments

multi-robot systems

multi-agent path finding

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

AAAI 2025

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



technical paper

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

In many settings where multiple agents interact, the optimal choices for each agent depend heavily on the choices of the others.
These coupled interactions are well-described by a general-sum differential game, in which players have differing objectives, the state evolves in continuous time, and optimal play may be characterized by one of many equilibrium concepts, e.g., a Nash equilibrium.
Often, problems admit multiple equilibria.
From the perspective of a single agent in such a game, this multiplicity of solutions can introduce uncertainty about how other agents will behave.
This paper proposes a general framework for resolving ambiguity between equilibria by reasoning about the equilibrium other agents are aiming for.
We demonstrate this framework in simulations of a multi-player human-robot navigation problem that yields two main conclusions:
First, by inferring which equilibrium humans are operating at, the robot is able to predict trajectories more accurately, and second, by discovering and aligning itself to this equilibrium the robot is able to reduce the cost for all players.


Inference-Based Strategy Alignment for General-Sum Differential Games

Multiagent teams have been shown to be effective in many domains that require coordination among team members. However, finding valuable joint-actions becomes increasingly difficult in tightly-coupled domains where each agent's performance depends on the actions of many other agents. Reward shaping partially addresses this challenge by deriving more "tuned" rewards to provide agents with additional feedback, but this approach still relies on agents randomly discovering suitable joint-actions. In this work, we introduce Counterfactual Agent Suggestions (CAS) as a method for injecting knowledge into an agent's learning process within the confines of existing reward structures. We show that CAS enables agent teams to converge towards desired behaviors more reliably. We also show that improvement in team performance in the presence of suggestions extends to large teams and tightly-coupled domains.


The Power of Suggestion

Reinforcement learning systems require good representations to work well. For decades practical success in reinforcement learning was limited to small domains. Deep reinforcement learning systems, on the other hand, are scalable, not dependent on domain specific prior knowledge and have been successfully used to play Atari, in 3D navigation from pixels, and to control high degree of freedom robots. Unfortunately, the performance of deep reinforcement learning systems is sensitive to hyper-parameter settings and architecture choices. Even well tuned systems exhibit significant instability both within a trial and across experiment replications. In practice, significant expertise and trial and error are usually required to achieve good performance. One potential source of the problem is known as catastrophic interference: when later training decreases performance by overriding previous learning. Interestingly, the powerful generalization that makes Neural Networks (NN) so effective in batch supervised learning might explain the challenges when applying them in reinforcement learning tasks. In this paper, we explore how online NN training and interference interact in reinforcement learning. We find that simply re-mapping the input observations to a high-dimensional space improves learning speed and parameter sensitivity. We also show this preprocessing reduces interference in prediction tasks. More practically, we provide a simple approach to NN training that is easy to implement, and requires little additional computation. We demonstrate that our approach improves performance in both prediction and control with an extensive batch of experiments in classic control domains.

Improving Performance in Reinforcement Learning by Breaking Generalization in Neural Networks

Toll-Based Learning for Minimising Congestion under Heterogeneus Preferences

In multiagent problems that require complex joint actions, reward shaping methods yield good behavior by incentivizing the agents' potentially valuable actions. However, reward shaping often requires access to the functional form of the reward function and the global state of the system. In this work, we introduce the Exploratory Gaussian Reward (EGR), a new reward model that creates optimistic stepping stone rewards linking the agents potentially good actions to the desired joint action. EGR models the system reward as a Gaussian Process to leverage the inherent uncertainty in reward estimates that push agents to explore unobserved state space. In the tightly coupled rover coordination problem, we show that EGR significantly outperforms a neural network approximation baseline and is comparable to the system with access to the functional form of the global reward. Finally, we demonstrate how EGR improves performance over other reward shaping methods by forcing agents to explore and escape local optima.

Gaussian Processes as Multiagent Reward Models

With the tremendous development of AI technologies, people will increasingly encounter software algorithms that supervise their work. Algorithmic management is the term for AI that performs the functions traditionally reserved for human managers (hiring, firing, providing evaluative feedback, and setting compensation). Although such algorithms indisputably perform management functions, they are often framed as support tools that facilitate worker autonomy. Perceptions of autonomy can enhance productivity, especially when the work holds intrinsic meaning for workers. But crowdwork often seems meaningless. More problematically, the meaning of the work must sometimes be obscured due to reasons of security or experimental control (when the workers serve as subjects in a psychological experiment). In this paper, we conduct an online experiment (N=560) to investigate how autonomy-perceptions and the meaningfulness of work interact to shape crowdworker motivation. As predicted, we find that workers are motivated when their work has meaning and algorithmic management is framed in a way that makes worker autonomy salient. However, when work holds no meaning, we find productivity is enhanced when algorithms are framed in a way that makes algorithm control salient. We also find evidence that providing meaning to the work can introduce systematic biases in crowdworker responses that could undermine accuracy in certain contexts.


The Effects of Autonomy and Task meaning in Algorithmic Management of Crowdwork

Agents can individually devise plans and coordinate to achieve common goals. Methods exist to factor planning problems into separate tasks and distribute the plan synthesis process, while reducing the overall planning complexity. However, merging distributedly generated plans becomes computationally costly when task plans are tightly coupled, and conflicts arise due to dependencies between plan actions. Existing methods either scale poorly as the number of agents and tasks increases, or do not minimize makespan, the overall time necessary to execute all tasks. A new algorithm, the Temporal Optimal Conflict Resolution Algorithm (TCRA*), is introduced to merge independently generated plans and optimally minimize the resulting makespan. A proof of optimality is provided and the algorithm is empirically evaluated across two heterogeneous multiagent domains against two baseline algorithms. The TCRA* results in better makespan across the problems solved, and a search relaxation constant allows the TCRA* to generate better plans with competitive processing time and memory usage. 


Optimal Temporal Plan Merging

Human players in professional team sports achieve high level coordination by dynamically choosing complementary skills and executing primitive actions to perform these skills. As a step toward creating intelligent agents with this capability for fully cooperative multi-agent settings, we propose a two-level hierarchical multi-agent reinforcement learning (MARL) algorithm with unsupervised skill discovery. Agents learn useful and distinct skills at the low level via independent Q-learning, while they learn to select complementary latent skill variables at the high level via centralized multi-agent training with an extrinsic team reward. The set of low-level skills emerges from an intrinsic reward that solely promotes the decodability of latent skill variables from the trajectory of a low-level skill, without the need for hand-crafted rewards for each skill. For scalable decentralized execution, each agent independently chooses latent skill variables and primitive actions based on local observations. Our overall method enables the use of general cooperative MARL algorithms for training high level policies and single-agent RL for training low level skills. Experiments on a stochastic high dimensional team game show the emergence of useful skills and cooperative team play. The interpretability of the learned skills show the promise of the proposed method for achieving human-AI cooperation in team sports games.

Hierarchical Cooperative Multi-Agent Reinforcement Learning with Skill Discovery

Networked public goods games model scenarios in which self-interested agents decide whether or how much to invest in an action that benefits not only themselves, but also their network neighbors.
Examples include vaccination, security investment, and crime reporting. While every agent's utility is increasing in their neighbors' joint investment, the specific form can vary widely depending on the scenario. A principal, such as a policymaker, may wish to induce large investment from the agents. Besides direct incentives, an important lever here is the network structure itself: by adding and removing edges, for example, through community meetings, 
the principal can change the nature of the utility functions, resulting in different, and perhaps socially preferable, equilibrium outcomes.
We initiate an algorithmic study of targeted network modifications with the goal of inducing equilibria of a particular form. We study this question for a variety of equilibrium forms (induce all agents to invest, at least a given set S, exactly a given set S, at least k agents), and for a variety of utility functions.
While we show that the problem is NP-complete for a number of these scenarios, we exhibit a broad array of scenarios in which the problem can be solved in polynomial time by non-trivial reductions to (minimum-cost) matching problems.



Inducing Equilibria in Networked Public Goods Games through Network Structure Modification

Reinforcement learning (RL) is a promising technique for optimizing traffic signal controllers that dynamically respond to real-time traffic conditions. Recent efforts that applied Multi-Agent RL (MARL) to this problem have shown remarkable improvement over centralized RL, with the scalability to solve large problems by distributing the global control to local RL agents. Unfortunately, it is also easy to get stuck in local optima because each agent only has partial observability of the environment with limited communication. To tackle this, we borrow ideas from feudal RL and propose a novel MARL approach combining with the feudal hierarchy. Specifically, we split the traffic network into several regions, where each region is controlled by a manager agent and the agents who control the traffic signals are its workers. In our method, managers coordinate their high-level behaviors and set goals for their workers in the region, while each lower-level worker controls traffic signals to fulfill the managerial goals. By doing so, we are able to coordinate globally while retain scalability. We empirically evaluate our method both in a synthetic traffic grid and real-world traffic network using the SUMO simulator. Our experimental results demonstrate that our approach outperforms the state-of-the-art in almost all evaluation metrics commonly used for traffic signal control.

Downloads

Next from AAMAS 2020

Inference-Based Strategy Alignment for General-Sum Differential Games

Similar lecture

MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

.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

Inference-Based Strategy Alignment for General-Sum Differential Games

Similar lecture

MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads