This paper analyses 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. It is proven 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.
On the complexity of case-based planning / Liberatore, Paolo. - In: JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE. - ISSN 0952-813X. - STAMPA. - 17:3(2005), pp. 283-295. [10.1080/09528130500283717]
On the complexity of case-based planning
LIBERATORE, Paolo
2005
Abstract
This paper analyses 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. It is proven 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.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2005_11573-125699.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
325.09 kB
Formato
Adobe PDF
|
325.09 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
