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.
Figures & tables
Fig. 1: Planner Comparison in Home Environment: Two robots are tasked to reach remote and pillow with the exact locations of these objects unknown. A myopic approach searches the nearest locations first, until the task is completed, leading to poor behavior. Our approach utilizes learning with a model-based planning framework to best guide the robots for efficient task completion. See further discussion in Section VII .
Fig. 2: Overview of our approach: For a joint-action at specifying what container each robot should travel towards and interact with to find task-relevant objects, the robot team concurrently travels towards the assigned containers—until one of the robots reaches and searches a container. The outcomes of each joint action transition the robot’s belief state based on whether any task-relevant objects were found on the container. The dfa Mφ keeps track of the overall task progress and transitions based on what objects have been interacted with and what objects are still needed to complete the task.
Fig. 3: Results: Partially known P roc thor environments The table shows the average cost accrued in 400 experiments in randomly selected tasks for each planner. We see that our planner improves over the cost over learned and non-learned baselines. Scatter plots shows results for our approach versus learned and non-leared baselines for 1, 2, and 3 robots. The statistics for all the results show benefits of our learning augmented model-based planner.
Fig. 4: Simulation experiments in small, medium, and large environments for 3 robots. (a) Task: Interact with a pillow , a tabletopdecor , and a book . (b) Task: Interact with either a dishsponge or a toiletpaper , then interact with a plate , then interact with a creditcard . (c) Task: Interact with a desklamp , a faucet , a plate , and a newspaper . In all these tasks, across different environment sizes, our MR planner improves cost over non-learned and learned baselines.
Fig. 5: Robots are tasked with order-dependent tasks with strict temporal constraints: (a) interacting with cellphone then toiletpaper , and (b) interacting with fork then bowl . Robots in our model-based planner (a) wait to interact with the object when searching for remaining objects does not improve task-completion cost, and (b) continue to search for other task-relevant objects when waiting to interact with the found object would increase the task-completion cost. The baselines search for all task-relevant objects and then resolve temporal dependencies of the task.
Fig. 6: As the number of robots increase, our planner coordinates robots effectively, divides efforts between the team to improve cost for both (a) complex order-dependent tasks and (b) order-independent tasks.
Fig. 7: Real-world Demonstration: For the task of reaching either ( laptop or wallet ) then remote then tv in a home with a two-robot team, our learning-informed model-based planner outperforms the non-learned myopic planner in terms of navigation costs.
Real-world robots often operate in settings where objective priorities depend on the underlying context of operation. When the underlying context is unknown apriori, multiple robots may have to coordinate to gather informative observations to infer the context, since acting based on an incorrect context can lead to misaligned and unsafe behavior. Once the underlying true context is inferred, the robots optimize their task-specific objectives in the preference order induced by the context. We formalize this problem as a Multi-Robot Context-Uncertain Stochastic Shortest Path (MR-CUSSP), which captures context-relevant information at landmark states through joint observations. Our two-stage solution approach is composed of: (1) CIMOP (Coordinated Inference for Multi-Objective Planning) to compute plans that guide robots toward informative landmarks to efficiently infer the true context, and (2) LCBS (Lexicographic Conflict-Based Search) for collision-free multi-robot path planning with lexicographic objective preferences, induced by the context. We evaluate the algorithms using three simulated domains and demonstrate its practical applicability using five mobile robots in the salp domain setup.
Collaborative Robotics and Intelligent Systems (CoRIS) Institute, Oregon State University, Corvallis, OR 97331, USA · Khoury College of Computer Sciences, Northeastern University, Boston, MA 02115, USA
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.
As robots are increasingly deployed in groups and share workspaces to execute real-world tasks, planning their concurrent motions around complex manipulation skills becomes essential. These skills involve continuous physical execution and may exhibit stochastic behavior, resulting in variable execution times and uncertain continuous trajectories. Existing planners either limit execution to single-robot scenarios, rely on open-loop paths, or use post-hoc scheduling that prevents dynamic coordination. In this paper, we address this gap by integrating stochastic skills into sampling-based multi-robot planning by formulating the problem as a Markov Decision Process (MDP) over a multi-modal composite roadmap. For stochastic skills, solving the MDP yields a reactive policy that allows controllable robots to dynamically adapt their motions in response to other robots' execution of manipulation skills. By resolving skill uncertainty directly at planning time, this approach avoids the pessimism of conservative baselines and unlocks robust, dynamic multi-robot coordination. Code for the planners is available at https://www.vhartmann.com/stochastic-skills.
William Schnyder, Valentin N. Hartmann, Stelian Coros