Source-linked AI summary
MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments
Zuxin Liu, Baiming Chen, Hongyi Zhou, Guru Koushik, Martial Hebert, Ding Zhao
TL;DR
Multi-agent planning must handle dynamic obstacles despite limited information and assumptions about their motion or homogeneity. MAPPER combines image-based obstacle representation, waypoint-guided local planning, and evolutionary reinforcement learning; across the reported settings, it outperforms LRA* and PRIMAL* in success rate.
Problem
Multi-agent planning approaches may rely on perfect information about dynamic obstacles or assume nearby agents are homogeneous, assumptions that may not hold in practice.
Source: §I · p. 1Method
MAPPER uses image-based obstacle representations, global-planner waypoints for local planning, and evolutionary reinforcement learning in mixed dynamic environments.
Source: §I · pp. 1–2Results
MAPPER’s success rate is the highest and consistently above 0.99 across various experiment settings, and it outperforms LRA* and PRIMAL* in success rate.
Source: C. Results · p. 6, §VI · p. 6Takeaways & Limitations
The reported results support MAPPER as a decentralized planning approach for mixed dynamic environments with varied obstacle behavior.
Source: §I · p. 1, §VI · p. 6
Abstract
from arXiv · showhide
Multi-agent navigation in dynamic environments is of great industrial value when deploying a large scale fleet of robot to real-world applications. This paper proposes a decentralized partially observable multi-agent path planning with evolutionary reinforcement learning (MAPPER) method to learn an effective local planning policy in mixed dynamic environments. Reinforcement learning-based methods usually suffer performance degradation on long-horizon tasks with goal-conditioned sparse rewards, so we decompose the long-range navigation task into many easier sub-tasks under the guidance of a global planner, which increases agents' performance in large environments. Moreover, most existing multi-agent planning approaches assume either perfect information of the surrounding environment or homogeneity of nearby dynamic agents, which may not hold in practice. Our approach models dynamic obstacles' behavior with an image-based representation and trains a policy in mixed dynamic environments without homogeneity assumption. To ensure multi-agent training stability and performance, we propose an evolutionary training approach that can be easily scaled to large and complex environments. Experiments show that MAPPER is able to achieve higher success rates and more stable performance when exposed to a large number of non-cooperative dynamic obstacles compared with traditional reaction-based planner LRA* and the state-of-the-art learning-based method.
I. INTRODUCTION
The introduction frames decentralized multi-agent planning as a response to scaling, communication, and unknown-obstacle challenges. MAPPER combines image-based obstacle representation, waypoint guidance, and evolutionary reinforcement learning for mixed dynamic environments.
I. INTRODUCTION
- Centralized planners can find collision-free paths when intentions are known in static environments, but may incur scaling, unknown-obstacle, communication, and infrastructure costs.The paper therefore focuses on decentralized planning where reliable communication between agents cannot be established.Source: §I · p. 1
- MAPPER plans in mixed dynamic environments without assuming homogeneous obstacles, representing their behavior with images to improve robustness across obstacle types.The representation encodes spatial and temporal information without explicit motion estimation and can generalize to arbitrary numbers of agents.Source: §I · pp. 1–2
- Global-planner guidance decomposes long-range navigation into easier waypoint-conditioned tasks, addressing reinforcement learning’s difficulty with long-horizon sparse rewards.The paper reports that this decomposition can greatly improve reinforcement-learning performance.Source: §I · pp. 1–2
- Evolutionary multi-agent reinforcement learning gradually eliminates low-performing policies to improve training efficiency and performance while scaling to large, complex environments.The approach is proposed to support training stability as well as performance.Source: §I · pp. 1–2
II. RELATED WORK
The related-work discussion contrasts decentralized planning approaches that depend on obstacle rules or motion assumptions with learning-based alternatives. It then formulates the problem as a partially observable multi-agent MDP.
A. Decentralized Path Planning in Dynamic Environment
- Decentralized reaction-based methods replan using avoidance rules, while trajectory-based methods estimate intentions; both can depend on perfect obstacle information or homogeneous behavior assumptions.The discussion also notes that complex local interactions may cause oscillation or freezing, and that component hyperparameters can require extra tuning.Source: A. Decentralized Path Planning in… · p. 2
B. Reinforcement Learning-based Planning
- Learning-based planning includes end-to-end policies and object-level representations; prior approaches face limits in agent scalability, explicit state estimation, temporal modeling, or non-cooperative obstacles.PRIMAL is identified as a similar image-based multi-agent method, but it does not consider non-cooperative obstacles or temporal information and uses centralized training.Source: B. Reinforcement Learning-based Planning · p. 2
A. Problem Formulation
- The problem is modeled as a partially observable N-agent MDP with shared state transitions, agent-specific observations, actions, policies, and rewards.Each agent seeks to maximize its expected return; γ is the discount factor and T is the time length.Source: A. Problem Formulation · p. 2
B. Advantage Actor Critic Algorithm
The paper uses advantage actor-critic (A2C) as the basis of its multi-agent evolutionary reinforcement-learning framework. A2C uses a stochastic policy and a value-function baseline to estimate the quality of actions and reduce gradient variance.
B. Advantage Actor Critic Algorithm
- A2C uses a stochastic policy to maximize expected episode return, a choice motivated by stochastic equilibrium policies in multi-agent MDPs.The paper also notes that policy-gradient methods usually have better convergence properties than value-based methods.Source: B. Advantage Actor Critic Algorithm · pp. 2–3
- A value-function baseline replaces the expected return with an advantage function to reduce policy-gradient variance.The paper describes the advantage function as having an unbiased estimation.Source: B. Advantage Actor Critic Algorithm · p. 3
- The actor produces actions from current observations, while the critic estimates the advantage by evaluating action quality.Both policy and value function are approximated with neural networks.Source: B. Advantage Actor Critic Algorithm · p. 3
IV. APPROACH
MAPPER frames navigation as decentralized planning with partial observations and describes how each agent represents its local surroundings. Its observation combines current positions, motion histories, and a global planner’s reference path.
IV. APPROACH
- The approach section introduces observation representation, action space, and reward design before detailing model architecture and training.Source: §IV · p. 3
A. Observation Representation
- Agents have limited sensing ranges, no inter-agent communication, and access to the static map for trajectory planning.They are assumed able to detect nearby agents and dynamic objects and estimate their relative positions.Source: A. Observation Representation · p. 3
- Three observation channels encode current obstacle and agent positions, time-ordered trajectories, and the global planner’s reference path.Trajectory points use grayscales to encode time, with earlier points assigned smaller values.Source: A. Observation Representation · p. 3
B. Action Space
The agent selects among discrete grid movements or waiting, and its reward combines navigation objectives with penalties. A reference-path penalty discourages deviation from the global planner’s route.
B. Action Space
- The agent has nine discrete actions: eight movement directions and waiting; an occupied target grid leaves it in place.Source: B. Action Space · p. 3
C. Reward Design
- The reward includes step, collision, and goal-reaching terms, with additional penalties for waiting and returning to the previous position.The wait penalty is intended to encourage exploration, while the return penalty discourages oscillation.Source: C. Reward Design · p. 3
- The off-route penalty is the negative distance from the agent to the closest point on the reference path, weighted by λ in the final reward.The final reward adds this weighted penalty to the step, collision, return, and goal-reaching terms.Source: C. Reward Design · p. 4
D. Model Architecture
MAPPER uses neural networks to estimate policy and value from observations and a selected waypoint. The global planner’s route is divided into sequential waypoint goals for local navigation.
D. Model Architecture
- The network processes the image-based observation and waypoint separately, then combines their features for policy and value estimation.The observation features are produced by convolution and max-pooling blocks before being flattened.Source: D. Model Architecture · p. 4
- A* generates a reference path, from which the agent selects waypoints at distance intervals and pursues them sequentially.The agent switches to the next waypoint after approaching the current one within a predefined range.Source: D. Model Architecture · p. 4
- The shared features feed separate policy and value networks; the policy network uses softmax to produce probabilities over actions.Source: D. Model Architecture · p. 4
E. Multi-Agent Evolutionary Reinforcement Learning
The evolutionary training approach addresses the scalability challenge of multi-agent reinforcement learning by training agents with A2C and periodically selecting among their policies. Lower-reward policies are more likely to be replaced by the current best policy.
E. Multi-Agent Evolutionary Reinforcement Learning
- As agent counts grow, the environment becomes more complex and policy-gradient variance may grow exponentially.Source: E. Multi-Agent Evolutionary… · p. 4
- Each agent begins with random weights and is trained separately with A2C; its rewards are accumulated over the latest k episodes.Source: E. Multi-Agent Evolutionary… · p. 4
- At selection, agents may retain their weights or replace them with the weights of the highest-reward agent; larger η makes lower-reward agents more likely to be updated.The method aims to gradually eliminate poor policies while maintaining good ones.Source: E. Multi-Agent Evolutionary… · p. 5
A. Experiment Settings
The experiments use a grid-world with static obstacles, goals, agents, and moving obstacles, including obstacles that ignore nearby agents. They compare MAPPER with reaction-based LRA* and learning-based PRIMAL*.
A. Experiment Settings
- Half of the dynamic obstacles ignore nearby agents, creating non-cooperative movement; each agent observes a 15 × 15 × 3 image within a 7-grid sensing range.Gray blocks are static obstacles, black blocks are goals, orange circles are agents, and blue triangles are dynamic obstacles; dynamic obstacles choose random goals and navigate using LRA* [28].Source: A. Experiment Settings · p. 5
- LRA* replans each step from local observations, updates its cost map, and uses a coordinator to resolve conflicts among agents’ planned paths.The benchmark replaces A* with D* lite for computational efficiency in dynamic environments.Source: A. Experiment Settings · p. 5
- PRIMAL* adapts PRIMAL’s observation representation and network architecture to the experiment while retaining its A3C training and goal-conditioned approach.The study also tests MAPPER variants without dynamic-obstacle trajectories or global-planner guidance.Source: A. Experiment Settings · p. 5
B. Training Details
Training progresses from short-range tasks to larger maps and more agents, while results compare MAPPER, its variants, and baselines across goal ranges and environment settings. MAPPER has the highest reported success rate across varied settings, and its guidance and trajectory features matter under different conditions.
B. Training Details
- Training advances from 4 agents and 10 dynamic obstacles on 20×20 maps with 7-grid goal sampling to 20 agents and 30 obstacles on 32×32 maps without range limits.The training uses a 0.0003 learning rate for MAPPER; PRIMAL* uses 0.00005 after the shared rate failed to converge for it.Source: B. Training Details · p. 5
C. Results
- In first-stage training, MAPPER has the smallest performance variance and fastest convergence, with final average reward and success rate superior to the compared methods.Fig. 3 compares success rate and average reward for MAPPER variants and PRIMAL*.Source: C. Results · p. 5, Figure 3 · p. 6
- The trajectory-free and guidance-free variants hardly converge with whole-map goal sampling in stage two, so their goal sample range is limited to 15 grids.Source: C. Results · p. 5
- MAPPER’s performance is not influenced by goal range, whereas removing global-planner guidance causes a large decline as goal distance increases.Fig. 4 compares MAPPER variants across goal sample ranges; removing trajectory information instead weakens performance in large environments with dynamic-obstacle interactions.Source: C. Results · p. 6, Figure 4 · p. 6
- MAPPER’s success rate is highest and consistently above 0.99 across varied settings, while it uses only local observations.Table II compares success rates across experiment settings; LRA* accesses agents’ intentions and resolves conflicts before acting.Source: C. Results · p. 6, Table II · p. 6
- Without trajectory information, the MAPPER variant performs well with few dynamic obstacles but poorly as environment complexity increases; without waypoint guidance, success is low even on a 20×20 map with 15 agents and 10 obstacles.Source: C. Results · p. 6
VI. CONCLUSION
MAPPER combines image-based dynamic-obstacle representations, waypoint-conditioned subtasks, and evolutionary reinforcement learning for decentralized planning in mixed dynamic environments. It outperforms LRA* and PRIMAL* in success rate across varied settings, but collisions can still occur in complex environments.
VI. CONCLUSION
- MAPPER uses image-based obstacle representations and waypoint-conditioned subtasks, with evolutionary training intended to scale while maintaining convergence.Source: §VI · p. 6
- Across varied experiment settings, MAPPER outperforms LRA* and PRIMAL* in success rate.Source: §VI · p. 6
- MAPPER may still collide with agents or dynamic obstacles in complex environments, motivating future work on safety-critical learning-based planning.Source: §VI · p. 6