Collaborative Task and Path Planning for Heterogeneous Robotic Teams using Multi-Agent PPO

1. Problem Statement

The paper addresses the challenge of collaborative task and path planning for heterogeneous robotic teams in extraterrestrial exploration scenarios (e.g., planetary surface missions).

• Context: Single robots have limited capabilities. Effective exploration requires teams of specialized robots (e.g., drones, rovers, legged robots) with different locomotion and sensing skills to perform tasks in parallel.
• Core Challenge: The problem involves a complex combinatorial optimization task that combines:
  1. Target Allocation: Assigning specific tasks to specific robots based on their skill sets.
  2. Path Planning: Determining efficient trajectories for each robot.
  3. Scheduling: Coordinating the execution order to avoid conflicts and exploit synergies (e.g., collaborative tasks requiring multiple robots simultaneously).
• Constraints:
  • Dynamic Environments: New targets may appear, or terrain may change, requiring online replanning.
  • Computational Limits: Space missions have strict real-time constraints and limited onboard computing power.
  • Scalability: Classical exact methods (like exhaustive search) suffer from exponential scaling with the number of agents and targets, making them infeasible for real-time replanning.

2. Methodology

The authors propose a learning-based approach using Multi-Agent Proximal Policy Optimization (MAPPO) to unify path planning, task allocation, and scheduling into a single framework.

A. Environment and Formulation

• Grid World: The environment is modeled as a discrete 2D grid.
• Agents & Skills: Agents possess specific skill sets. Targets require specific skills, categorized as:
  • OR-type: Solved by any single agent with the required skill.
  • AND-type: Requires multiple agents with specific skills to be present at the target simultaneously (collaborative).
• Observations: Each agent receives a fixed-size observation vector containing:
  • Relative positions of all agents and targets.
  • Encoded skill sets of all agents and targets.
  • Target types (AND/OR).
  • Note: The observation size is fixed based on the maximum number of agents/targets, simplifying network input but limiting dynamic scalability.

B. Reward Function

The reward signal is a weighted sum of several components designed to guide behavior:

1. Attraction Reward (AR): A potential field encouraging agents to move toward unsolved targets they can solve.
2. Target Reward (TR): A fixed payout when a target is solved (shared among all agents to encourage cooperation).
3. Wrong Target Cost (WC): A penalty for agents stepping on targets they cannot solve (prevents wasted effort).
4. Step Cost (SC): A small penalty for every movement step to encourage efficiency.
5. Solve Time Cost (TC): A cost that decreases as more targets are solved, incentivizing speed.
6. Terminal Bonus (TB): A reward for solving all targets within the episode.

C. Training Strategy

To prevent agents from converging to a degenerate policy (staying still to avoid penalties), training is split into two phases:

1. Bootstrap Phase: Agents learn basic navigation to targets using AR, TR, and WC. Step and time costs are initially disabled.
2. Refinement Phase: All reward terms are activated to optimize for efficiency, speed, and team effort.

D. Network Architecture

• Algorithm: MAPPO (Centralized Training, Decentralized Execution).
• Structure: Actor-Critic with Gated Recurrent Units (GRUs) wrapped by dense layers.
  • Critic: Centralized; takes concatenated observations of all agents to learn a joint value function.
  • Actor: Decentralized; outputs action probabilities for individual agents based on their local observations.

3. Key Contributions

1. Unified Learning Framework: A MAPPO-based system that simultaneously solves target allocation, path planning, and scheduling for heterogeneous teams, unlike previous methods that separate these steps.
2. Scalability vs. Runtime: Demonstrates that while training is computationally intensive, the inference time is constant ($O(1)$) regardless of problem size, making it suitable for real-time space applications.
3. Online Replanning: Validated the ability to handle dynamic environments by using the observation buffer to replace solved targets with newly detected ones, allowing for continuous replanning without retraining.
4. Open Source: The learning framework is released as open source.

4. Results

The method was benchmarked against Exhaustive Search (ES) (optimal solutions) on a 32x32 grid with 3 agents and varying numbers of targets (5, 6, 7).

• Performance Quality:
  • Success Rate: Achieved >90% success rate across policies.
  • Optimality: The learned policies achieved 86% of the optimal solution quality regarding solve time and 92% regarding total team effort (movement cost).
  • Trend: Performance slightly decreased as the number of targets increased, reflecting growing problem complexity.
• Inference Time:
  • RL Policy: Constant inference time (~milliseconds), independent of the number of targets.
  • Exhaustive Search: Exponential increase in computation time as targets/agents increase.
  • Trade-off: The complexity is shifted from runtime to training time. Training takes significantly longer than ES solving, but this is a one-time cost.
• Replanning:
  • Policies trained with dynamic target injection performed similarly to static policies, proving the system can adapt to new tasks online without explicit retraining.

5. Significance and Limitations

Significance:

• Real-Time Capability: The constant inference time makes this approach viable for space missions where communication delays prevent ground-based replanning and onboard computers have limited power.
• Heterogeneous Coordination: Successfully handles the complexity of different robot types and collaborative (AND-type) tasks, which are difficult for classical algorithms to solve efficiently.
• Future-Proofing: Offers a pathway to autonomous planetary exploration where robots must adapt to unknown terrains and discoveries in real-time.

Limitations:

• Fixed Observation Size: The current architecture requires a fixed input size, limiting the maximum number of agents and targets the policy can handle. It cannot generalize to arbitrary team sizes without retraining or architectural changes (e.g., Graph Neural Networks).
• Training Cost: The shift of complexity to the training phase requires significant GPU resources and time.
• Reward Tuning: The system is sensitive to reward weights; tuning becomes more difficult as the number of targets increases.

Conclusion:
The paper presents a robust, learning-based alternative to classical planning for multi-robot space exploration. By leveraging MAPPO, it achieves near-optimal coordination with the critical advantage of real-time, constant-time inference, enabling autonomous teams to adapt to dynamic, unknown environments.