Efficient robotic extraterrestrial exploration requires robots with diverse capabilities, ranging from scientific measurement tools to advanced locomotion. A robotic team enables the distribution of tasks over multiple specialized subsystems, each providing specific expertise to complete the mission. The central challenge lies in efficiently coordinating the team to maximize utilization and the extraction of scientific value. Classical planning algorithms scale poorly with problem size, leading to long planning cycles and high inference costs due to the combinatorial growth of possible robot-target allocations and possible trajectories. Learning-based methods are a viable alternative that move the scaling concern from runtime to training time, setting a critical step towards achieving real-time planning. In this work, we present a collaborative planning strategy based on Multi-Agent Proximal Policy Optimization (MAPPO) to coordinate a team of heterogeneous robots to solve a complex target allocation and scheduling problem. We benchmark our approach against single-objective optimal solutions obtained through exhaustive search and evaluate its ability to perform online replanning in the context of a planetary exploration scenario.
Figures & tables
Fig. 1 : An illustrative plan for a collaborative robot fleet with different specializations, such as flying, walking, or driving. During the mission the drone and the legged robot find new tasks and replan to minimize mission time.
Fig. 2 : This figure illustrates the complete workflow, highlighting both the execution (green) and training (yellow) phases. The execution block details the network architectures and the placement of the replanning step. The training block shows the MAPPO update sequence. The colored arrows differentiate data flow, specifying whether it applies to all agents, a single agent, or represents aggregated data for training. Furthermore, the environment is visualized as a grid, including the agents and targets with their provided or required skills (colored dots). The targets are marked with a green square, which can have a black border indicating a collaborative target (AND type).
Training
AR
TR
WC
SC
TC
BR
Bootstrap
✓
✓
✓
\crossproduct
\crossproduct
\crossproduct
Refinement
✓
✓
✓
✓
✓
✓
TABLE I : Activated rewards during training. AR: Attraction Reward, TR: Target Reward, WC: Wrong Target Cost, SC: Step Cost, TC: Solve Time Cost, BR: Bonus Reward
Π5T
Π6T
Π7T
nENV
16’384 / 30’720
16’384 / 26’880
16’384 / 24576
nSTEPS
128
128
128
nTRAIN
572 / 1271
572 / 2034
1668 / 3814
nMINI
16 / 32
16 / 28
16 / 32
Seed
2 / 4
2
2
TABLE II : Modified MAPPO training parameters in top-down order are environments trained in parallel / max steps per environment , epochs / batch size / random generator seed .
CAR
wAR
wTR
wWC
wSC
wTC
wTB
Π5T
0.0075
1.0
1.0
0.25
0.3
0.5
0.2
Π6T
0.0075
1.0
1.0
0.25
0.3
0.5
0.2
Π7T
0.04
1.0
1.0
0.25
0.3
0.5
0.2
TABLE III : Reward weights for the baseline policy.
Π5T
Π6T
Π7T
Msuccess
0.99
0.95
0.91
MstRL / MstES1
0.86
0.81
0.73
MtteRL / MtteES2
0.92
0.91
0.84
TABLE IV : Performance comparison between three policies with a different number of targets, and the optimal solutions ES1 w.r.t. solve time (st) and ES2 w.r.t. the total team effort (tte). Optimal performance would be represented by a value of 1.
Fig. 3 : RL inference and training time measurements compared to the inference time of the ES approach with respect to the trained policies by number of solved targets.
Msuccess
Mst
Mtte
Π5T
84.2 %
85.70 ± 20.1
232.5 ± 72.8
Π5T5R
84.1 %
85.73 ± 20.9
220.0 ± 81.3
TABLE V : Baseline policy Π5T versus a policy Π5T5R that was trained including the possibility of obtaining new targets during an episode. Simulated over 1000 random (seed=10) environments with an episode length of 128.
Long-horizon task planning for heterogeneous multi-robot systems is essential for deploying collaborative teams in real-world environments; yet, it remains challenging due to the large volume of perceptual information, much of which is irrelevant to task objectives and burdens planning. Traditional symbolic planners rely on manually constructed problem specifications, limiting scalability and adaptability, while recent large language model (LLM)-based approaches often suffer from hallucinations and weak grounding-i.e., poor alignment between generated plans and actual environmental objects and constraints-in object-rich settings. We present Scale-Plan, a scalable LLM-assisted framework that generates compact, task-relevant problem representations from natural language instructions. Given a PDDL domain specification, Scale-Plan constructs an action graph capturing domain structure and uses shallow LLM reasoning to guide a structured graph search that identifies a minimal subset of relevant actions and objects. By filtering irrelevant information prior to planning, Scale-Plan enables efficient decomposition, allocation, and long-horizon plan generation. We evaluate our approach on complex multi-agent tasks and introduce MAT2-THOR, a cleaned benchmark built on AI2-THOR for reliable evaluation of multi-robot planning systems. Scale-Plan outperforms pure LLM and hybrid LLM-PDDL baselines across all metrics, improving scalability and reliability. Project website: https://github.com/honda-research-institute/Scale_Plan
Piyush Gupta, Sangjae Bae, Jiachen Li +1
Honda Research Institute, San Jose, CA 95134, USA. · Georgia Institute of Technology, Atlanta, GA 30332, USA.
We want a multi-robot team to complete complex tasks in minimum time where the locations of task-relevant objects are not known. Effective task completion requires reasoning over long horizons about the likely locations of task-relevant objects, how individual actions contribute to overall progress, and how to coordinate team efforts. Planning in this setting is extremely challenging: even when task-relevant information is partially known, coordinating which robot performs which action and when is difficult, and uncertainty introduces a multiplicity of possible outcomes for each action, which further complicates long-horizon decision-making and coordination. To address this, we propose a multi-robot planning abstraction that integrates learning to estimate uncertain aspects of the environment with model-based planning for long-horizon coordination. We demonstrate the efficient multi-stage task planning of our approach for 1, 2, and 3 robot teams over competitive baselines in large ProcTHOR household environments. Additionally, we demonstrate the effectiveness of our approach with a team of two LoCoBot mobile robots in real household settings.
Abhish Khanal, Abhishek Paudel, Hung Pham +1
Department of Computer Science, George Mason University, Fairfax, VA, 22030, USA.
Efficient task allocation for large-scale Heterogeneous Multi-Robot Systems (HMRS) is critical, yet dealing with complex temporal logic tasks in partially known environment (PKE) remains a computational bottleneck. Existing approaches often struggle to balance exploring uncertain regions and exploiting known resources, while also suffering from exponential computational complexity. To address these issues, this paper presents a robust planning framework that simultaneously handles high-level logical constraints and environmental uncertainty without sacrificing scalability. We formulate the problem as a min-max regret optimization, proposing a Region-Binding Atomic Proposition (RbAP) to capture resource uncertainty within the automaton structure. To solve this, we propose the Extended Planning Decision Tree (E-PDT) equipped with a novel Regret-based Branch-and-Bound (BnB) strategy. Unlike traditional methods that rely on prior probabilities or worst-case analysis, our approach dynamically prunes suboptimal policies, effectively balancing the need for information gathering (exploration) and task completion (exploitation). Theoretical analysis confirms the feasibility and completeness of our approach. Extensive numerical and physical experiments demonstrate that the proposed framework achieves near-linear scalability with respect to the number of robots and types, significantly outperforming MILP-based baselines in both solution quality and computational efficiency.