Torna
alla Home Page del corso Torna
alla pagina degli Elaborati
Torna
alla Home Page del corso Torna
alla pagina degli Elaborati
|
|
|
|
|
|
|
|
|
|
|
|
|
Introduzione
In questa sezione verranno illustrati tre tipi diversi di pianificatori: UCPOP, SHOP e Cplan.
La strategia di ricerca utilizzata da UCPOP è quella nello spazio dei piani: ci si muove da un piano all'altro aggiungendo ogni volta una nuova azione. Il piano da cui si inizia la ricerca non contiene alcuna azione ed è detto piano nullo; il piano finale è la soluzione al problema di pianificazione e contiene la sequenza di azioni che l'agente deve eseguire; i piani intermedi sono solo parzialmente specificati e contengono una sequenza di azioni che viene man mano arricchita fino ad ottenere quella finale. Il problema di pianificazione è formulato per mezzo di tre componenti: la descrizione del mondo, la descrizione dell'obiettivo e la descrizione delle azioni che l'agente può eseguire (teoria del dominio), il tutto è rappresentato con un'estensione del linguaggio proposizionale STRIPS (STanford Research Institute Problem Solver). Molto semplice da utilizzare, rivela però una limitata efficienza, specie per domini complessi.
Di diversa natura è invece il pianificatore SHOP (Simple Hierarchical Ordered Planner). Infatti, per la rappresentazione di un dominio complesso, quale potrebbe essere un dominio reale, si rende necessario l'utilizzo di un pianificatore gerarchico. Il semplice linguaggio STRIPS, infatti, porterebbe a piani dettagliati con un numero elevatissimo di passi. Uno spazio dei piani di tale lunghezza e complessità è tale da non consentire a tecniche di pianificazione strips-like di trovare una soluzione in un tempo ragionevole. Per ovviare a tale inconveniente si utilizza la tecnica della decomposizione gerarchica, nella quale un operatore astratto può essere decomposto in un gruppo di passi elementari. Shop è un sistema di pianificazione indipendente dal dominio ed è basato su un pianificatore HTN (Hierarchical Task-Network). L'algoritmo di SHOP è sound e completo per una vasta gamma di problemi. Molto efficiente anche per domini di una certa complessità, SHOP richiede una conoscenza del linguaggio abbastanza approfondita ed uno sforzo implementativo superiore a quello richiesto da UCPOP.
Cplan (a Constraint Programming Approachto
Planning) è stato concepito come metodologia efficiente, in termini
di velocità computazionale per la risoluzione di problemi di pianificazione.
Infatti il largo impiego di tecniche CSP per lo scheduling di attività
era già noto in ambito accademico, ed il passaggio dallo scheduling
alla pianificazione non si è rivelato complicato. CPLAN è
quindi un CSP-solver applicato alla pianificazione. La sua funzione è
quella di convertire un problema di pianificazione in un problema CSP e
di risolverlo poi con delle funzioni che sono denotate con GAC+CBJ, le
quali realizzano Propagazione Generalizzata di Arco Consistenza e Backjumpingsu
Conflitti Diretti.
Download relazionie
codici