On the Complexity of Case-Based Planning
<|reference_start|>On the Complexity of Case-Based Planning: We analyze the computational complexity of problems related to case-based planning: planning when a plan for a similar instance is known, and planning from a library of plans. We prove that planning from a single case has the same complexity than generative planning (i.e., planning "from scratch"); using an extended definition of cases, complexity is reduced if the domain stored in the case is similar to the one to search plans for. Planning from a library of cases is shown to have the same complexity. In both cases, the complexity of planning remains, in the worst case, PSPACE-complete.<|reference_end|>
@article{liberatore2004on,
    title={On the Complexity of Case-Based Planning},
    author={Paolo Liberatore},
    journal={arXiv preprint arXiv:cs/0407034},
    year={2004},
    doi={10.1080/09528130500283717},
    archivePrefix={arXiv},
    eprint={cs/0407034},
    primaryClass={cs.AI cs.CC}
}