Deep Reinforcement Learning for Swarm Systems

Maximilian Hüttenrauch; Adrian Šošić; Gerhard Neumann

Source-linked AI summary

Deep Reinforcement Learning for Swarm Systems

Maximilian Hüttenrauch, Adrian Šošić, Gerhard Neumann

arXiv:1807.06613v3Jul 17, 2018cs.MAcs.AIcs.LGeess.SYstat.ML

TL;DR

Deep RL for swarm systems needs a state representation that handles interchangeable agents and changing numbers of neighbors without the scaling problems of concatenation. The paper uses empirical mean embeddings of neighboring-agent observations, with histogram, RBF, and end-to-end neural-network feature spaces, and evaluates them on rendezvous and pursuit evasion. Neural-network mean embeddings learn faster, produce higher-quality policies, and support richer information exchange between neighboring agents.

Problem
Concatenated agent states scale poorly for large homogeneous swarms and do not exploit agent interchangeability or invariance to the number of agents.
Method
The paper represents neighboring-agent observations as samples from a distribution and feeds their empirical mean feature embedding into a decentralized policy.
Results
Neural-network mean embeddings enabled faster learning, higher-quality policies, and richer information exchange in rendezvous and pursuit evasion evaluations.
Takeaways & Limitations
Mean embeddings provide a compact, permutation-invariant state representation applicable to deep MARL with homogeneous agent groups.
Takeaways & Limitations
The histogram representation does not scale well with feature dimensionality, while the swarm model assumes permutation-invariant transition and observation models.

Abstract

from arXiv · show

Recently, deep reinforcement learning (RL) methods have been applied successfully to multi-agent scenarios. Typically, these methods rely on a concatenation of agent states to represent the information content required for decentralized decision making. However, concatenation scales poorly to swarm systems with a large number of homogeneous agents as it does not exploit the fundamental properties inherent to these systems: (i) the agents in the swarm are interchangeable and (ii) the exact number of agents in the swarm is irrelevant. Therefore, we propose a new state representation for deep multi-agent RL based on mean embeddings of distributions. We treat the agents as samples of a distribution and use the empirical mean embedding as input for a decentralized policy. We define different feature spaces of the mean embedding using histograms, radial basis functions and a neural network learned end-to-end. We evaluate the representation on two well known problems from the swarm literature (rendezvous and pursuit evasion), in a globally and locally observable setup. For the local setup we furthermore introduce simple communication protocols. Of all approaches, the mean embedding representation using neural network features enables the richest information exchange between neighboring agents facilitating the development of more complex collective strategies.

1. Introduction

Deep reinforcement learning for swarms must represent large, variable sets of neighboring agents while respecting their interchangeability. The paper proposes mean feature embeddings as a decentralized state representation and evaluates them on rendezvous and pursuit evasion.

Swarm agents have limited sensing and manipulation capabilities, so tasks must be solved collectively by multiple agents.
Deep RL becomes challenging as swarm size increases because each agent must process information about several other agents.The resulting information set can have high dimensionality and changing size.
Concatenated observations require fixed input dimensionality and disregard the permutation invariance of homogeneous agents.Image-based representations also increase dimensionality with added features and can suffer from pixel quantization.
The proposed mean feature embedding treats neighboring-agent observations as samples from a distribution, producing a representation invariant to agent order and perceived-neighbor count.Each agent uses a local view of the encoded distribution for decentralized policy decisions.
The paper instantiates mean embeddings with histograms, radial basis functions, and neural-network features learned end-to-end.It evaluates these representations with TRPO on rendezvous and pursuit evasion problems in global and local observation settings.
Agents using the mean-embedding representation learn faster and obtain higher-quality policies, indicating an efficient encoding of swarm state configuration.The representation can be integrated into existing neural-network architectures and deep RL algorithms.

2. Related Work

The paper situates mean-embedding swarm control within deep MARL and optimization-based coordination research. Its representation is intended as a compact component that can be incorporated into existing homogeneous-agent MARL approaches.

The contribution is a compact state representation designed for deep MARL settings with homogeneous agent groups.The authors frame the idea as largely orthogonal to other MARL research and compatible with existing approaches.
Prior deep MARL studies use image states, value-function methods, recurrent networks, centralized critics, or learned agent-policy embeddings across cooperative and competitive tasks.These studies include grid-world, particle-world, object-transportation, navigation, and robo-sumo environments.
Centralized action-value functions can scale poorly because their input space grows linearly with the number of agents.This motivates more scalable representations for large multi-agent systems.
Mean embeddings have also been used for centralized robot-swarm control, whereas this paper embeds each agent’s local view.The related centralized approach directly embeds the swarm configuration into a reproducing kernel Hilbert space.
Related optimization-based work derives decentralized control for rendezvous and formation control under limited communication and for reach-avoid games through pairwise interactions.

3. Background

The background introduces TRPO and mean embeddings as foundations for the proposed representation. Mean embeddings encode a distribution through an expected feature map or its empirical average, with finite feature spaces sufficient when only policy-relevant information is needed.

Trust Region Policy Optimization: TRPO optimizes control policies in reinforcement-learning problems formulated as Markov decision processes.An MDP specifies states, actions, transition dynamics, and rewards, with the objective of maximizing cumulative reward.
Trust Region Policy Optimization: TRPO parameterizes a neural-network policy and maximizes the expected advantage of the current policy subject to a fixed KL-divergence constraint.The approximate optimization uses conjugate gradients after linearizing the objective and quadratizing the constraint.
Mean Embeddings: A mean embedding represents a probability distribution through the expected value of a feature map.The feature map may be finite- or infinite-dimensional.
Mean Embeddings: Given observations drawn independently from a distribution, the empirical mean embedding estimates the expected feature map by averaging their feature representations.
Mean Embeddings: Characteristic kernels can uniquely identify a distribution from its mean embedding, but finite feature spaces can suffice when the goal is extracting policy-relevant information.

4. Deep Reinforcement Learning for Swarms

The paper formulates swarm control as centralized-learning/decentralized-execution and represents variable-sized neighbor observations with permutation-invariant mean feature embeddings. It compares neural-network, histogram, and radial-basis feature spaces, each producing a fixed-dimensional policy input.

Problem domain: Swarm policies are optimized centrally during learning but executed independently by homogeneous agents using a shared decentralized policy.The swarm MDP assumes identical agents and permutation-invariant transition and observation models.
Problem domain: A swarm MDP models identical agents with local observations, shared stochastic policies, coupled transitions, and a global cooperative reward.Each agent observes only information prescribed by the observation model, potentially through an interaction graph.
Observation requirements: Neighbor observations form unordered, variable-sized sets, so the policy encoding must remain invariant to agent indexing and applicable to changing swarm sizes.Dynamic local graph structure can change the number of observed neighbors, while full-system observation can involve different swarm sizes.
Mean feature embeddings: Mean feature embeddings treat neighbor observations as distribution samples and average feature activations into a fixed-dimensional representation independent of set size.The feature mapping φ determines the embedding space, which becomes the neural-network policy input.
Feature spaces: Neural-network feature mappings are learned end-to-end and can handle high-dimensional observations, whereas histogram and RBF representations use predefined feature spaces.A shallow one-layer ReLU network performed well in the reported experiments, while deeper networks remain possible.
Feature spaces: Histograms discretize observations into fixed bins, while RBF networks provide a soft-assigned histogram through basis-function activations.Hard histogram assignments can change abruptly when an agent crosses a bin boundary; both histogram and RBF approaches face dimensionality growth.

5. Experimental Results

Across rendezvous and pursuit-evasion experiments, neural-network mean embeddings generally learned faster and produced higher-quality policies than the other tested representations. Extended observations and communication improved performance, while changing swarm size and local observability exposed important differences between methods.

Rendezvous: NN+ achieved an approximately 10% higher average return than NN and RBF in rendezvous.Its steady-state mean distance was approximately twice as good, ∼4 × 10−2 versus ∼8 × 10−2, after around 200 time steps.
Rendezvous: NN+ reached comparable mean distances roughly 20 to 30 time steps earlier, corresponding to an improvement of ∼25%.
Rendezvous: The extended histogram and RBF representations failed to find rendezvous solutions, whereas neural-network embedding kept feature dimensionality linear rather than exponential.This produced a more compact representation that kept the learning problem tractable.
Rendezvous: Compared with the optimization-based controller, learned policies reduced rendezvous distance faster, although a small steady-state error remained.The optimization controller eventually reached zero mean distance but was suboptimal for the considered dynamics.
Rendezvous: Neural-network embeddings reduced inter-agent distances fastest and generalized from 20 training agents to executions with 100 and 10 agents.With 100 agents, the neural-network extended-set embedding was quickest and achieved the best overall performance.
Pursuit Evasion: In global pursuit evasion, all methods found successful strategies, but the extended-set neural-network mean embedding learned with fewer samples and produced better behavior.The learned policy first prevented the evader from expanding its Voronoi region, then surrounded and captured it.
Pursuit Evasion: In local pursuit evasion, neural-network mean embeddings showed a more noticeable performance advantage, especially with local communication protocols.The local setting required agents to infer evader distance and bearing from embeddings, while the reward supplied no distance guidance.

6. Conclusion

The paper proposes mean feature embeddings for swarm state representations and evaluates histogram, radial basis function, and neural-network variants across rendezvous and pursuit-evasion tasks.

End-to-end neural-network embeddings scale with increasing agent numbers, produce better policies, and often converge faster than the other approaches.The naive concatenation approach fails for larger system sizes.

Appendix A. Agent Kinematics

The appendix specifies single- and double-integrator agent models, discrete-time simulation, and the neighborhood and wall information available to each agent.

Single-integrator agents directly control linear and angular velocity, whereas double-integrator agents change velocity indirectly through acceleration.
The experiments model both agent dynamics in discrete time using finite differences.
Each agent senses neighboring-agent properties within its neighborhood, including inter-agent distance.
Each agent also has local information about its distance and bearing relative to the closest wall.

Appendix C. Task Specific Communication Protocols

Task-specific communication and observation protocols augment local agent information with neighborhood size, evader observations, and graph-based shortest-path information.

In rendezvous, an agent can additionally sense the size of its own neighborhood.
In pursuit evasion, agents sense an evader’s distance and bearing when the evader lies within the observation distance.
Agents are assumed able to compute a shortest path to an evader over a graph of connected agents.The path minimizes the sum of inter-agent distances along the graph path.
A PD controller transforms the consensus protocol’s high-level state manipulation for agents with double-integrator dynamics.Its parameters are tuned manually for good performance on the problem.

E.1 Rendezvous

The task objectives and reward settings are expressed through inter-agent or agent-evader distances, with global observability using maximum possible sensing cutoffs.

Rendezvous: The reward for rendezvous is defined using inter-agent distances.
Rendezvous: For global observability, the rendezvous cutoff distance equals the environment’s maximum possible inter-agent distance.
Rendezvous: The action penalty coefficient is β = −1 × 10−3, controlling how strongly high policy outputs are penalized.
Pursuit evasion: For a single evader, pursuit-evasion reward is expressed using the distance to the closest pursuer.The global observability setting uses the maximum possible agent-evader distance as the observation cutoff.

E.3 Pursuit Evasion with Multiple Evaders

For multiple evaders, pursuit uses a sparse reward based on evaders caught per time step, with capture determined by a distance threshold. The supplied figure passage instead concerns 20-agent rendezvous learning curves.

Reward function: The multiple-evader reward counts how many evaders are caught at each time step.It provides no additional guidance based on inter-agent distances.
Capture criterion: An evader is considered caught when the closest pursuer is within the threshold distance dt = 3.The closest-pursuer distance is defined as dmin,e = min(d1,e, . . . , dN,e).
Related evaluation: Figure 12 reports median average return ¯G from the top five trials for 20-agent rendezvous learning curves.It compares activation functions and layer numbers or sizes using RELU activation.
Reward notation: The reward expression uses E for the number of evaders and an indicator function.The supplied passages identify these components but do not show the complete displayed equation.

Appendix F. Policy Architectures

This section briefly summarizes the selected policy architectures and directs readers to Figure 1 for illustrations.

Policy architectures: The section summarizes the policy architectures selected for the experiments.The supplied passage characterizes this discussion as brief.
Policy architectures: Figure 1 contains illustrations of the policy architectures.The passage directs readers to the figure for visual representations.
Policy architectures: The architecture discussion is presented as a summary rather than a detailed architectural exposition.This follows the passage’s description of the section as briefly summarizing the chosen architectures.

F.1 Neural Network Embedding Policy

The paper compares several policy representations, including neural-network, histogram, radial-basis-function, and concatenation architectures. The neural embedding uses a 64-neuron RELU layer, while the alternative representations use specified feature constructions and policy networks.

Neural network embedding: The neural network mean feature embedding is evaluated across layer sizes and activation functions on rendezvous.Other experiments use the neural network mean feature embedding for agent i.
Neural network embedding: The neural embedding is the empirical mean of outputs from a single-layer feed-forward neural network.Its implementation uses 64 neurons with a RELU non-linearity h.
Alternative embeddings: The histogram embedding bins distance and bearing to other agents into eight bins per feature, producing a 64-dimensional vector.The construction is a two-dimensional histogram over distance and bearing space.
Alternative embeddings: The RBF representation uses M = 8 radial basis functions with evenly distributed centers in distance-and-bearing space.The supplied passage describes M2 contributions and defines the observation, center, and scale components.
Alternative embeddings: The histogram and RBF representations share a policy network structure illustrated in Figure 1b.The passage identifies the figure as the corresponding architectural illustration.
Concatenation policy: The concatenation policy first processes neighborhood observations with one 64-neuron RELU hidden layer.The resulting feature vector is concatenated with local properties oi_loc.
Concatenation policy: A second same-sized layer processes the combined features before mapping them to the action.The corresponding concatenation policy structure is shown in Figure 1c.