Dipartimento di Ingegneria dell’Informazione, https://ror.org/02q2d2610Università degli Studi di Brescia, Brescia, Italy"/>
Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
Submit Manuscript
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2025 Volume 40
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Optimally stable plan repair

  • Dipartimento di Ingegneria dell’Informazione, https://ror.org/02q2d2610Università degli Studi di Brescia, Brescia, Italy

More Information
  • Abstract: Plan repair is the problem of solving a given planning problem by using a solution plan of a similar problem. This paper presents the first approach where the repair has to be done optimally, that is, we aim at finding a minimum distance plan from an input plan; we do so by introducing a number of compilation schemes that convert a classical planning problem into another where optimal plans correspond to plans with the minimum distance from an input plan. We also address the problem of finding a minimum distance plan from a set of input plans, instead of just one plan. Our experiments using a number of planners show that such a simple approach can solve many problems optimally and more effectively than replanning from scratch for a large number of cases. Also, the approach proves competitive with ${\mathsf{LPG}\textrm{-}\mathsf{adapt}}$, a state-of-the-art approach for the plan repair problem.
  • 加载中
  • Bercher , P., Biundo , S., Geier , T., Hoernle , T., Nothdurft , F., Richter , F. & Schattenberg , B. 2014. Plan, repair, execute, explain - how planning helps to assemble your home theater. In Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, ICAPS 2014, Portsmouth, New Hampshire, USA, June 21–26, 2014. AAAI.

    Google Scholar

    Bidot , J., Schattenberg , B. & Biundo , S. 2008. Plan repair in hybrid planning In KI 2008: Advances in Artificial Intelligence, 169–176. Springer Berlin Heidelberg.

    Google Scholar

    Boella , G. & Damiano , R. 2002. A replanning algorithm for a reactive agent architecture. In Artificial Intelligence: Methodology, Systems, and Applications, 10th International Conference, AIMSA 2002, Varna, Bulgaria, September 4–6, 2002, Proceedings, Scott , D. (ed.). Lecture Notes in Computer Science 2443, 183–192. Springer.

    Google Scholar

    Bonet , B. 2010. Conformant plans and beyond: Principles and complexity. Artificial Intelligence 174(3-4), 245–269.10.1016/j.artint.2009.11.001

    Google Scholar

    Borrajo , D. & Veloso , M. 2021. Computing opportunities to augment plans for novel replanning during execution. In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling, ICAPS 2021, Guangzhou, China (virtual), August 2–13, 2021, Biundo , S., Do , M., Goldman , R., Katz , M., Yang , Q. & Zhuo , H. H. (eds), 51–55. AAAI Press.

    Google Scholar

    Cardellini , M., Dodaro , C., Galatà , G., Giardini , A., Maratea , M., Nisopoli , N. & Porro , I. 2023. Rescheduling rehabilitation sessions with answer set programming. Journal of Logic and Computation 33(4), 837–863.10.1093/logcom/exad014

    Google Scholar

    Cimatti , A., Pistore , M., Roveri , M. & Traverso , P. 2003. Weak, strong, and strong cyclic planning via symbolic model checking. Artificial Intelligence 147(1–2), 35–84.10.1016/S0004-3702(02)00374-0

    Google Scholar

    desJardins , M., Durfee , E. H., Jr., C. L. O. & Wolverton , M. 1999. A survey of research in distributed, continual planning. AI Magazine 20(4), 13–22.

    Google Scholar

    Fox , M., Gerevini , A., Long , D. & Serina , I. 2006. Plan stability: Replanning versus plan repair. In ICAPS, 212–221. AAAI.

    Google Scholar

    Fox , M. & Long , D. 2003. PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research 20, 61–124.10.1613/jair.1129

    Google Scholar

    Garrido , A., C., G. & Onaindia, E. 2010. Anytime plan-adaptation for continuous planning. In Proc. of P&S Special Interest Group Workshop (PLANSIG-10).

    Google Scholar

    Gerevini , A., Roubcková , A., Saetti , A. & Serina , I. 2013. On the plan-library maintenance problem in a case-based planner. In Case-Based Reasoning Research and Development - 21st International Conference, ICCBR 2013, Saratoga Springs, NY, USA, July 8–11, 2013, Proceedings, Delany , S. J. & Ontañón , S. (eds), Lecture Notes in Computer Science 7969, 119–133. Springer.

    Google Scholar

    Gerevini , A., Saetti , A. & Serina , I. 2011. An empirical analysis of some heuristic features for planning through local search and action graphs. Fundamenta Informaticae 107(2–3), 167–197.10.3233/FI-2011-399

    Google Scholar

    Gerevini , A. & Serina , I. 2010. Efficient plan adaptation through replanning windows and heuristic goals. Fundamenta Informaticae 102(3–4), 287–323.10.3233/FI-2010-309

    Google Scholar

    Goldman , R. P., Kuter , U. & Freedman , R. G. 2020. Stable plan repair for state-space htn planning. In Proceedings of the ICAPS-20 Workshop on Hierarchical Planning (HPlan 2020), 27–35.

    Google Scholar

    Grastien , A. & Scala , E. 2020. CPCES: A planning framework to solve conformant planning problems through a counterexample guided refinement. Artificial Intelligence 284, 103271.10.1016/j.artint.2020.103271

    Google Scholar

    Helmert , M. 2006. The fast downward planning system. Journal of Artificial Intelligence Research 26, 191–246.10.1613/jair.1705

    Google Scholar

    Höller , D., Bercher , P., Behnke , G. & Biundo , S. 2018. Htn plan repair using unmodified planning systems. In Proceedings of the 1st ICAPS Workshop on Hierarchical Planning (HPlan), 26–30.

    Google Scholar

    Höller , D., Bercher , P., Behnke , G. & Biundo , S. 2020. HTN plan repair via model transformation. In KI 2020: Advances in Artificial Intelligence - 43rd German Conference on AI, Bamberg, Germany, September 21–25, 2020, Proceedings, Lecture Notes in Computer Science 12325, 88–101. Springer.

    Google Scholar

    Ingrand , F. & Ghallab , M. 2017. Deliberation for autonomous robots: A survey. Artificial Intelligence 247, 10–44.10.1016/j.artint.2014.11.003

    Google Scholar

    Kaelbling , L. P., Littman , M. L. & Cassandra , A. R. 1998. Planning and acting in partially observable stochastic domains. Artificial Intelligence 101(1-2), 99–134.10.1016/S0004-3702(98)00023-X

    Google Scholar

    Katz , M., Sohrabi , S., Samulowitz , H. & Sievers , S. 2018. Delfi: Online planner selection for cost-optimal planning. IPC-9 planner abstracts, 57–64.

    Google Scholar

    Keyder , E. & Geffner , H. 2009. Soft goals can be compiled away. Journal of Artificial Intelligence Research 36, 547–556.10.1613/jair.2857

    Google Scholar

    Koenig , S. & Likhachev , M. 2002. D*lite. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28–August 1, 2002, Edmonton, Alberta, Canada, 476–483. AAAI Press/The MIT Press.

    Google Scholar

    Lipovetzky , N. & Geffner , H. 2017. Best-first width search: Exploration and exploitation in classical planning. In AAAI, 3590–3596. AAAI Press.

    Google Scholar

    Micheli , A., et al. 2024. Unified planning framework.

    Google Scholar

    Muñoz-Avila , H. & Cox , M. T. 2008. Case-based plan adaptation: An analysis and review. IEEE Intelligent Systems 23(4), 75–81.10.1109/MIS.2008.59

    Google Scholar

    Nebel , B. & Koehler , J. 1995. Plan reuse versus plan generation: A theoretical and empirical analysis. Artificial Intelligence 76(1-2), 427–454.10.1016/0004-3702(94)00082-C

    Google Scholar

    Percassi , F., Scala , E. & Vallati , M. 2023. Fixing plans for PDDL+ problems: Theoretical and practical implications. In Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling, Prague, Czech Republic, July 8–13, 2023, 324–333. AAAI Press.

    Google Scholar

    Pozanco , A., Borrajo , D. & Veloso , M. 2023. Generating replanning goals through multi-objective optimization in response to execution observation. In ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland. Frontiers in Artificial Intelligence and Applications 372, 1898–1905. IOS Press.

    Google Scholar

    Richter , S. & Westphal , M. 2010. The LAMA planner: Guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research 39, 127–177.10.1613/jair.2972

    Google Scholar

    Rintanen , J. 2004. Complexity of planning with partial observability. In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), June 3–7 2004, Whistler, British Columbia, Canada, 345–354. AAAI.

    Google Scholar

    Ruml , W., Do , M. B., Zhou , R. & Fromherz , M. P. J. 2011. On-line planning and scheduling: An application to controlling modular printers. Journal of Artificial Intelligence Research (JAIR) 40, 415–468.10.1613/jair.3184

    Google Scholar

    Saetti , A. & Scala , E. 2022. Optimizing the stability in plan repair via compilation. In Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling, ICAPS 2022, Singapore (virtual), June 13–24, 2022, 316–320. AAAI Press.

    Google Scholar

    Scala , E. 2014. Plan repair for resource constrained tasks via numeric macro actions. In ICAPS. AAAI.

    Google Scholar

    Scala , E. & Torasso , P. 2014. Proactive and reactive reconfiguration for the robust execution of multi modality plans. In ECAI. Frontiers in Artificial Intelligence and Applications 263, 783–788. IOS Press.

    Google Scholar

    Scala , E. & Torasso , P. 2015. Deordering and numeric macro actions for plan repair. In IJCAI, 1673–1681. AAAI Press.

    Google Scholar

    Smith , D. E. & Weld , D. S. 1998. Conformant graphplan. In AAAI/IAAI, 889–896. AAAI Press/The MIT Press.

    Google Scholar

    van der Krogt , R. & de Weerdt , M. 2005. Plan repair as an extension of planning. In Proc. of International Conference on Automated Planning and Scheduling (ICAPS-05), 161–170.

    Google Scholar

    Warfield , I., Hogg , C., Lee-Urban , S. & Muñoz-Avila , H. 2007. Adaptation of hierarchical task network plans. In Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference, May 7–9, 2007, Key West, Florida, USA, 429–434. AAAI Press.

    Google Scholar

    Yoon , S. W., Fern , A. & Givan , R. 2007. Ff-replan: A baseline for probabilistic planning. In ICAPS, 352. AAAI.

    Google Scholar

  • Cite this article

    Alessandro Saetti, Enrico Scala. 2025. Optimally stable plan repair. The Knowledge Engineering Review 40(1), doi: 10.1017/S0269888925100076
    Alessandro Saetti, Enrico Scala. 2025. Optimally stable plan repair. The Knowledge Engineering Review 40(1), doi: 10.1017/S0269888925100076
    shu
Download PDF

Article Metrics

Article views(102) PDF downloads(270)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Optimally stable plan repair

  • Dipartimento di Ingegneria dell’Informazione, https://ror.org/02q2d2610Università degli Studi di Brescia, Brescia, Italy

  • Received: 24 February 2025
  • Revised: 14 October 2025
  • Accepted: 29 October 2025
  • Published online: 26 November 2025
The Knowledge Engineering Review  40,  2025, 40(1)  |  Cite this article

Abstract: Abstract: Plan repair is the problem of solving a given planning problem by using a solution plan of a similar problem. This paper presents the first approach where the repair has to be done optimally, that is, we aim at finding a minimum distance plan from an input plan; we do so by introducing a number of compilation schemes that convert a classical planning problem into another where optimal plans correspond to plans with the minimum distance from an input plan. We also address the problem of finding a minimum distance plan from a set of input plans, instead of just one plan. Our experiments using a number of planners show that such a simple approach can solve many problems optimally and more effectively than replanning from scratch for a large number of cases. Also, the approach proves competitive with ${\mathsf{LPG}\textrm{-}\mathsf{adapt}}$, a state-of-the-art approach for the plan repair problem.

    HTML

    Acknowledgments

    • The authors declare none.

    Rights and permissions
    • This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.
References (41)
  • About this article
    Cite this article
    Alessandro Saetti, Enrico Scala. 2025. Optimally stable plan repair. The Knowledge Engineering Review 40(1), doi: 10.1017/S0269888925100076
    Alessandro Saetti, Enrico Scala. 2025. Optimally stable plan repair. The Knowledge Engineering Review 40(1), doi: 10.1017/S0269888925100076
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return