Hierarchical Planning for Vehicle Routing and Scheduling in Marsupial Robotic Systems

This letter presents a hierarchical planning approach to the vehicle routing and scheduling problem (VRSP) for marsupial robotic systems, a specialized class of heterogeneous robotic systems in which one type of mobile robot is capable of carrying another. While traditional VRSPs have been widely studied, the marsupial variant (MVRSP) has received relatively little attention. To address the NP-hard nature of MVRSP, this work introduces a hierarchical planning structure that decomposes the problem into two subproblems with reduced complexity: a high-level routing problem, formulated as a mixed-integer linear program (MILP), and a low-level scheduling problem, modeled in the Planning Domain Definition Language (PDDL). These subproblem solutions are integrated to generate complete mission plans. The proposed approach is validated through qualitative plan visualizations and quantitative Monte Carlo simulations in an autonomous subsea mapping scenario, where an unmanned surface vehicle carries multiple underwater vehicles. Results show that the hierarchical planner significantly improves both planning efficiency and solution quality compared to baseline methods.

• Publication year

  2026

• Venue

  IEEE Robotics and Automation Letters

• Publication date

  2026-01-01

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1109/LRA.2025.3630971
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• LaMMA-P: Generalizable Multi-Agent Long-Horizon Task Allocation and Planning with LM-Driven PDDL Planner

  2024influential reference
• Solving the Min-Max Clustered Traveling Salesmen Problem Based on Genetic Algorithm

  2023cited by this paper
• Influence of Team Interactions on Multi-Robot Cooperation: A Relational Network Perspective

  2023cited by this paper
• Adaptive Temporal Planning for Multi-Robot Systems in Operations and Maintenance of Offshore Wind Farms

  2023influential reference
• Optimizing Fuel-Constrained UAV-UGV Routes for Large Scale Coverage: Bilevel Planning in Heterogeneous Multi-Agent Systems

  2023cited by this paper
• Hierarchical Planning for Heterogeneous Multi-Robot Routing Problems via Learned Subteam Performance

  2022cited by this paper
• Multiple Mobile Robot Task and Motion Planning: A Survey

  2022cited by this paper
• Heuristics for a cash-collection routing problem with a cluster-first route-second approach

  2022cited by this paper
• Path and Trajectory Planning of a Tethered UAV-UGV Marsupial Robotic System

  2022cited by this paper
• Mission Planning for Underwater Survey with Autonomous Marine Vehicles

  2022cited by this paper
• Multi-agent deep reinforcement learning: a survey

  2021cited by this paper
• A Clustering Based Routing Heuristic for Last-Mile Logistics in Fresh Food E-Commerce

  2020cited by this paper
• Collaborative Mission Planning for Long-Term Operation Considering Energy Limitations

  2020cited by this paper
• Mars Helicopter Technology Demonstrator

  2018cited by this paper
• Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments

  2017cited by this paper
• Counterfactual Multi-Agent Policy Gradients

  2017cited by this paper
• A critical survey on marsupial robotic teams for environmental monitoring of water bodies

  2015cited by this paper
• A comprehensive taxonomy for multi-robot task allocation

  2013cited by this paper
• COLIN: Planning with Continuous Linear Numeric Change

  2012influential reference
• Algorithms for hierarchical clustering: an overview

  2012cited by this paper
• Forward-Chaining Partial-Order Planning

  2010influential reference
• Cooperative use of unmanned sea surface and micro aerial vehicles at Hurricane Wilma

  2008cited by this paper
• PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains

  2003influential reference
• Multirobot automated indoor floor characterization team

  1996cited by this paper
• Introduction to Abstract Mathematics

  1986cited by this paper

• No citing papers are available for this paper.