LLM-Modulo Planning Agents with External Plan Verification and Iterative Self-Repair
Keywords:
Automated Planning, Large Language Models, Planbench, External Verification, VAL, Iterative Self-Repair, Agent Safety, Test-Time ScalingAbstract
Large language models can translate natural-language goals into action sequences, but an action sequence is not a plan unless every precondition holds and the final state satisfies the goal. This study evaluates a modulo-style planning agent that assigns proposal generation to an LLM and delegates correctness to an external symbolic verifier. The evaluation used the PlanBench repository artifacts for Blocksworld: every stored GPT-4 candidate in four domain-size conditions and five prompt forms (6,000 direct plans), together with all 50 verifier-feedback trajectories containing 286 sequential candidates. Each candidate was parsed into PDDL actions and independently checked with VAL against the corresponding domain and problem file. Across the direct corpus, 934 of 6,000 candidates were valid (15.57%). Validity reached 27.53% in standard Blocksworld but only 3.60% after semantic obfuscation. State-tracking prompts were strongest in both conditions, while PDDL-form prompts did not compensate for weak state-transition reasoning. On the matched 50-instance repair set, direct execution completed 4 tasks (8%) and would have executed 46 invalid plans. A verifier gate preserved the same 8% completion while reducing invalid execution to zero through abstention. Iterative verifier-feedback repair completed 41 tasks (82%), repaired 37 of 46 initially invalid plans (80.43%), accepted no invalid plan, and required 5.72 candidate generations on average. Completion saturated after the ninth candidate; the paired gain was 74 percentage points with a 62-86 point bootstrap interval and exact McNemar p = 1.46 x 10^-11. The results establish a clear division of labor: formal verification supplies sound acceptance, while bounded feedback-driven regeneration converts safe rejection into high task completion.
References
[1] R. E. Fikes and N. J. Nilsson, "STRIPS: A new approach to the application of theorem proving to problem solving," Artificial Intelligence, vol. 2, nos. 3-4, pp. 189-208, 1971.
[2] D. McDermott et al., "PDDL - The Planning Domain Definition Language," Yale Center for Computational Vision and Control, New Haven, CT, Tech. Rep. CVC TR-98-003/DCS TR-1165, 1998.
[3] M. Ghallab, D. Nau, and P. Traverso, Automated Planning: Theory and Practice. San Francisco, CA, USA: Morgan Kaufmann, 2004.
[4] R. Howey, D. Long, and M. Fox, "VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL," in Proc. 16th IEEE Int. Conf. Tools with Artificial Intelligence (ICTAI), 2004, pp. 849-857.
[5] M. Helmert, "The Fast Downward planning system," Journal of Artificial Intelligence Research, vol. 26, pp. 191-246, 2006.
[6] W. Huang et al., "Language models as zero-shot planners: Extracting actionable knowledge for embodied agents," in Proc. 39th Int. Conf. Machine Learning (ICML), PMLR, vol. 162, 2022, pp. 9118-9147.
[7] M. Ahn et al., "Do as I can, not as I say: Grounding language in robotic affordances," in Proc. 6th Conf. Robot Learning (CoRL), PMLR, vol. 205, 2023, pp. 287-318.
[8] W. Huang et al., "Inner monologue: Embodied reasoning through planning with language models," in Proc. 6th Conf. Robot Learning (CoRL), PMLR, vol. 205, 2023, pp. 1769-1782.
[9] I. Singh et al., "ProgPrompt: Generating situated robot task plans using large language models," in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2023, pp. 11523-11530.
[10] J. Liang et al., "Code as policies: Language model programs for embodied control," in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2023, pp. 9493-9500.
[11] B. Liu et al., "LLM+P: Empowering large language models with optimal planning proficiency," arXiv:2304.11477, 2023.
[12] J. Wei et al., "Chain-of-thought prompting elicits reasoning in large language models," in Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 24824-24837.
[13] X. Wang et al., "Self-consistency improves chain of thought reasoning in language models," in Proc. Int. Conf. Learning Representations (ICLR), 2023.
[14] S. Yao et al., "ReAct: Synergizing reasoning and acting in language models," in Proc. Int. Conf. Learning Representations (ICLR), 2023.
[15] A. Madaan et al., "Self-Refine: Iterative refinement with self-feedback," in Advances in Neural Information Processing Systems, vol. 36, 2023.
[16] N. Shinn et al., "Reflexion: Language agents with verbal reinforcement learning," in Advances in Neural Information Processing Systems, vol. 36, 2023.
[17] S. Yao et al., "Tree of thoughts: Deliberate problem solving with large language models," in Advances in Neural Information Processing Systems, vol. 36, 2023, pp. 11809-11822.
[18] L. Gao et al., "PAL: Program-aided language models," in Proc. 40th Int. Conf. Machine Learning (ICML), PMLR, vol. 202, 2023, pp. 10764-10799.
[19] S. Hao et al., "Reasoning with language model is planning with world model," arXiv:2305.14992, 2023.
[20] T. Schick et al., "Toolformer: Language models can teach themselves to use tools," in Advances in Neural Information Processing Systems, vol. 36, 2023.
[21] S. Zhou, Z. Li, and E. Wang, "Evidence-Grounded RAG for Tokenized Trade Receivable Disclosure QA under U.S. Capital Market Standards," J. Adv. Comput. Syst., vol. 3, no. 7, pp. 41-57, Jul. 2023, doi: 10.69987/JACS.2023.30704.
[22] Y. Li, "Findable then Explainable: Retrieval-Summary Integration for Code Intelligence on a Lightweight CodeSearchNet Subset," J. Adv. Comput. Syst., vol. 4, no. 7, pp. 65-82, Jul. 2024, doi: 10.69987/JACS.2024.40706.
[23] Y. Wang, S. Du, Q. Xin, Y. He, and W. Qian, "Autonomous Driving System Driven by Artificial Intelligence Perception Fusion," Acad. J. Sci. Technol., vol. 9, no. 2, pp. 193-198, Feb. 2024, doi: 10.54097/e0b9ak47.
[24] K. Valmeekam, M. Marquez, A. Olmo, S. Sreedharan, and S. Kambhampati, "PlanBench: An extensible benchmark for evaluating large language models on planning and reasoning about change," in Advances in Neural Information Processing Systems, vol. 36, 2023, pp. 38975-38987.
[25] K. Valmeekam, M. Marquez, S. Sreedharan, and S. Kambhampati, "On the planning abilities of large language models: A critical investigation," in Advances in Neural Information Processing Systems, vol. 36, 2023, pp. 75993-76005.
[26] J. Nie and D. Zheng, "Ambiguity-Aware HDFS Log Anomaly Detection with Retrieval-Augmented Failure Narratives and Selective Refusal," J. Adv. Comput. Syst., vol. 3, no. 1, pp. 66-80, Jan. 2023, doi: 10.69987/JACS.2023.30105.
[27] Z. S. Zhong, R. Ma, and H. Zhao, "Human-Uncertainty Distillation for Calibrated Vision Models on CIFAR-10H," J. Adv. Comput. Syst., vol. 3, no. 2, pp. 77-89, Feb. 2023, doi: 10.69987/JACS.2023.30206.
[28] H. Zhang, "DriftGuard: Multi-Signal Drift Early Warning and Safe Re-Training/Rollback for CTR/CVR Models," J. Adv. Comput. Syst., vol. 3, no. 7, pp. 24-40, Jul. 2023, doi: 10.69987/JACS.2023.30703.
[29] Z. Zhong, M. Zheng, H. Mai, J. Zhao, and X. Liu, "Cancer image classification based on DenseNet model," J. Phys.: Conf. Ser., vol. 1651, no. 1, Art. no. 012143, Nov. 2020, doi: 10.1088/1742-6596/1651/1/012143.
[30] J. Chen, J. Xiong, Y. Wang, Q. Xin, and H. Zhou, "Implementation of an AI-based MRD Evaluation and Prediction Model for Multiple Myeloma," Front. Comput. Intell. Syst., vol. 6, no. 3, pp. 127-131, Jan. 2024, doi: 10.54097/zJ4MnbWW.
[31] K. Valmeekam, M. Marquez, and S. Kambhampati, "Can large language models really improve by self-critiquing their own plans?" in NeurIPS 2023 Workshop on Foundation Models for Decision Making, 2023.
[32] K. Stechly, M. Marquez, and S. Kambhampati, "GPT-4 does not know it is wrong: An analysis of iterative prompting for reasoning problems," in NeurIPS 2023 Workshop on Foundation Models for Decision Making, 2023.
[33] A. Ni, S. Iyer, D. Radev, V. Stoyanov, W.-T. Yih, S. Wang, and X. V. Lin, "LEVER: Learning to verify language-to-code generation with execution," in Proc. 40th Int. Conf. Machine Learning (ICML), PMLR, vol. 202, 2023, pp. 26106-26128.
[34] H. Zhang, "Risk-Aware Budget-Constrained Auto-Bidding under First-Price RTB: A Distributional Constrained Deep Reinforcement Learning Framework," J. Adv. Comput. Syst., vol. 4, no. 6, pp. 30-47, Jun. 2024, doi: 10.69987/JACS.2024.40603.
[35] E. B. Wilson, "Probable inference, the law of succession, and statistical inference," Journal of the American Statistical Association, vol. 22, no. 158, pp. 209-212, 1927.
[36] Q. McNemar, "Note on the sampling error of the difference between correlated proportions or percentages," Psychometrika, vol. 12, no. 2, pp. 153-157, 1947.
[37] A. G. S. Raj, H. Zhang, V. Abhyankar, S. Mukherjee, E. Zhang, J. Williams, R. Halverson, and J. M. Patel, "Impact of bilingual CS education on student learning and engagement in a data structures course," in Proc. 19th Koli Calling Int. Conf. Comput. Educ. Res., 2019, Art. no. 24, pp. 1-10, doi: 10.1145/3364510.3364518.
[38] Y. He, Y. Pan, Y. Wang, S. Du, and Q. Xin, "Intelligent Fault Analysis With AIOps Technology," J. Theory Pract. Eng. Sci., vol. 4, no. 1, pp. 94-100, Feb. 2024, doi: 10.53469/jtpes.2024.04(01).13.
[39] K. Xu, H. Zhou, H. Zheng, M. Zhu, and Q. Xin, "Intelligent classification and personalized recommendation of e-commerce products based on machine learning," in Proc. 6th Int. Conf. Computing and Data Science, Applied and Computational Engineering, vol. 64, no. 1, pp. 143-149, 2024, doi: 10.54254/2755-2721/64/20241365.
[40] Z. S. Zhong and S. Ling, "Improved theoretical guarantee for rank aggregation via spectral method," Inf. Inference: J. IMA, vol. 13, no. 3, Art. no. iaae020, Sep. 2024, doi: 10.1093/imaiai/iaae020.
[41] J. Wang, Q. Xin, Y. Liu, J. Wang, and T. Yang, "Predicting Enterprise Marketing Decision Making with Intelligent Data-Driven Approaches," J. Ind. Eng. Appl. Sci., vol. 2, no. 3, pp. 12-19, Jun. 2024, doi: 10.5281/zenodo.11357252.
[42] Q. Xin, R. Song, Z. Wang, Z. Xu, and F. Zhao, "Enhancing Bank Credit Risk Management Using the C5.0 Decision Tree Algorithm," J. Comput. Technol. Appl. Math., vol. 1, no. 4, pp. 100-107, Nov. 2024, doi: 10.5281/zenodo.14032041.
[43] S. Zhou, Z. Li, and E. Wang, "Long-Document RAG for Contractual and Insurance Clause Analysis in Receivables RWA Structures," J. Adv. Comput. Syst., vol. 4, no. 8, pp. 88-104, Aug. 2024, doi: 10.69987/JACS.2024.40810.
[44] T. Yang, Q. Xin, X. Zhan, S. Zhuang, and H. Li, "Enhancing Financial Services through Big Data and AI-Driven Customer Insights and Risk Analysis," J. Knowl. Learn. Sci. Technol., vol. 3, no. 3, pp. 53-62, Jul. 2024, doi: 10.60087/jklst.vol3.n3.p53-62.
[45] Q. Xin, Z. Xu, L. Guo, F. Zhao, and B. Wu, "IoT traffic classification and anomaly detection method based on deep autoencoders," in Proc. 6th Int. Conf. Computing and Data Science, Applied and Computational Engineering, vol. 69, no. 1, pp. 64-70, Jul. 2024, doi: 10.54254/2755-2721/69/20241511.
[46] Z. Ling, Q. Xin, Y. Lin, G. Su, and Z. Shui, "Optimization of Autonomous Driving Image Detection Based on RFAConv and Triplet Attention," in Proc. 2nd Int. Conf. Software Engineering and Machine Learning, Applied and Computational Engineering, vol. 77, pp. 210-217, 2024, doi: 10.54254/2755-2721/77/2024MA0067.
[47] B. Wang, Y. He, Z. Shui, Q. Xin, and H. Lei, "Predictive optimization of DDoS attack mitigation in distributed systems using machine learning," in Proc. 6th Int. Conf. Computing and Data Science, Applied and Computational Engineering, vol. 64, no. 1, pp. 94-99, May 2024, doi: 10.54254/2755-2721/64/20241350.
[48] J. Nie and D. Zheng, "Noisy-Neighbor-Aware VM Degradation Risk Modeling with Unsupervised Residual Fusion," J. Adv. Comput. Syst., vol. 4, no. 4, pp. 112-123, Apr. 2024, doi: 10.69987/JACS.2024.40409.
[49] Z. S. Zhong and S. Ling, "Uncertainty Quantification of Spectral Estimator and MLE for Orthogonal Group Synchronization," arXiv:2408.05944, Aug. 2024.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Tyler Ward, Yan Zhou, Stephanie Gray (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Creative Commons Attribution 4.0 International (CC BY 4.0).
This work is licensed under a 