Hierarchical Planning for Vehicle Routing and Scheduling in Marsupial Robotic Systems
Donghyun Kim, Jinwhan Kim
AI summary
Problem
The Marsupial Vehicle Routing and Scheduling Problem (MVRSP) is NP-hard and computationally intractable for large-scale missions due to tight coupling between carrier routing and task agent scheduling. Traditional methods struggle to scale while preserving these critical inter-agent dependencies.
Approach
The problem is decomposed via clustering-based mission partitioning into a high-level routing subproblem solved with mixed-integer linear programming and a low-level scheduling subproblem modeled in PDDL, which are then integrated to generate complete plans.
Key results
- Two clustering-based partitioning methods that balance spatial distribution and workload
- A node-weighted cost formulation that mitigates fleet workload imbalance during routing
- A PDDL-based scheduling model that captures temporal and concurrency constraints
- Monte Carlo simulations showing significant gains in planning efficiency and solution quality over baselines
Why it matters
Enables scalable, interpretable coordination for heterogeneous carrier-task robot teams in large-scale missions like undersea surveying and disaster response.
Abstract
This letter presents a hierarchical planning ap- proach 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.