SkeletonPlan: Experience-Guided Decision Skeletons over Compositional Constraint Programs

Neuro-symbolic mulit-agents methods have become a promising solution for Real-world agent planning which requires coordinating heterogeneous decisions under numerous explicit and implicit constraints. However, existing neuro-symbolic planners commonly expand planning requirements into lengthy collections of low-level constraints, obscuring the higher-level dependencies among decision families and increasing the representation burden placed on planning agents. They also solve the resulting models either jointly or through decompositions fixed before inference, preventing the solving structure from adapting to the feasibility bottlenecks of each instance; moreover, effective solving structures discovered for one instance are rarely abstracted and reused across related problems. To address these limitations, we propose SkeletonPlan, a neuro-symbolic multi-agent framework that combines a compositional representation of constraint structure with instance-adaptive organization of symbolic solving. First, SkeletonPlan represents recurring constraint patterns as executable compositions over typed and indexed variable families, making family-level dependencies explicit to planning agents while preserving deterministic compilation into the complete constraint model. Based on this structural representation, a constraint-guided skeleton agent selects interface families whose commitments are expected to shape downstream feasibility and constructs an instance-specific organization for symbolic solving; full-model completion verifies whether the selected commitments extend to a solution of the complete constraint system. Finally, SkeletonPlan learns an online structural memory from solver and evaluator feedback. The memory distills recurring observations, guidance, and exceptions into compact natural-language advice that informs route, interface, and support decisions on later instances, while concrete assignments and final validity remain the responsibility of the symbolic solver. Experiments on Travelplanner demonstrate that SkeletonPlan achieves state-of-the-art planning performance. while ablation studies confirm the respective contributions of compositional constraint representation, instance-adaptive skeleton construction, and online structural memory learning.