ADJ: tecniche di ricerca sistematica

Le tecniche di ricerca sistematica sono  basate su backtracking e sono in grado di esplorare in modo sistematico l’intero spazio di ricerca.
L’input è costituito da:

  • un dominio di pianificazione D definito da un insieme di operatori O;
  • un piano valido P per un problema PROB_ORIG in D, specificato da un insieme parzialmente ordinato di azioni;
  • un problema modificato PROB in D definito da un insieme di cambiamenti allo stato iniziale o allo stato finale di P.

L’output è un piano valido per PROB. Il metodo di adattamento sistematico utilizzato in ADJ identifica e risolve le inconsistenze presenti nel piano di input P, modificandone limitate porzioni. Un’inconsistenza, nel piano P, corrisponde a:

  • una precondizione non soddisfatta di una azione di P;
  • un goal del nuovo problema non realizzato da P;
  • ad una coppia di azioni in P mutuamente esclusive (ad esempio in seguito al cambiamento della situazione iniziale).

Le porzioni di P che vengono modificate sono delimitate da “finestre temporali” in cui sono presenti le inconsistenze. Ogni finestra di pianificazione è associata ad uno specifico (sotto)problema di pianificazione che viene risolto utilizzando un algoritmo di ricerca sistematica.

Durante la fase di adattamento una finestra temporale W può essere incrementalmente allargata fino a contenere, nel caso peggiore, l’intero piano; nel qual caso verrebbe effettuata una ripianificazione completa.

Al termine della fase di adattamento le azioni di P appartenenti alla finestra temporale W vengono sostituite da quelle del nuovo sottopiano calcolato. Questa tecnica è completa, nel senso che se il nuovo problema è risolvibile, allora la revisione del piano di input fornisce un piano corretto per il nuovo problema.