Complessità e Formulazione chimica – Riduzione – Part II

Considerazioni sulla Complessità

Nel seguito verranno presentati alcuni risultati relativi alla relazione presente tra complessità del planning indipendente dal dominio e la natura degli operatori utilizzati. Quindi verrà illustrata brevemente una particolare formalizzazione del problema della formulazione chimica mediante la quale è possible comprendere la complessità del problema considerato in questa tesi.

Condizioni per la Decidibilità

In letteratura sono presenti alcuni risultati relativi alla decidibilità del planning indipendente dal dominio in termini di condizioni sugli operatori utilizzati:

• Utilizzo di simboli di funzione;

• Utilizzo di liste di cancellazione;

• Esistenza di precondizioni negative;

• Restrizione a predicati proposizionali;

• Operatori associati all’istanza o prefissati;

• Operatori con effetti condizionali.

Nel primo esempio di planner presente in letteratura, lo STRIPS Planner, le liste di precondizioni, inserzione e rimozione degli operatori potevano contenere formule ben formate della logica del prim’ordine. La difficoltà nel ricavare una semantica ben definita per questa formulazione ha richiesto la definizione di alcune restrizioni, imponendo l’utilizzo di formule atomiche per tali liste ed esprimendo l’obiettivo mediante la congiunzione di formule atomiche o, al più, quantificate esistenzialmente.

In base a tali criteri, relativi agli operatori, è stata sviluppata una teoria comprensiva della complessità dei problemi di planning. Nel caso particolare del problema della formulazione chimica abbiamo le seguenti condizioni:

• Utilizzo di predicati proposizionali;

• Operatori associati all’istanza;

• Eliminazione delle liste di cancellazione;

• Presenza di precondizioni con formule atomiche negate.

La tabella 1.1 riassume parte dei risultati della teoria citata in precedenza, utilizzando le condizioni enunciate possiamo individuare la classe di complessità del nostro problema, rilevando il fatto che sia NP-Completo. Nella sezione successiva viene presentata una definizione alternativa, ma del tutto equivalente, del problema della formulazione chimica indipendente dal dominio applicativo al fine di illustrare un approccio plausibile per la risoluzione del problema oggetto della tesi; tale definizione viene infine ripresa nel capitolo 7 mostrando alcuni risultati non definitivi in relazione alla complessità del problema così definito.

1.1.7 Una Definizione Alternativa: CNF-Formulazione

In base a quanto riportato nel paragrafo precedente si è scelto di formalizzare in modo alternativo il problema della formulazione al fine di utilizzare alcuni risultati noti in letteratura, si vedano ad esempio SAT-Planner, CSP-Planner e Model-Checking Planner. In particolare, il primo approccio è sembrato quello più promettente date le diverse analogie, inoltre il potere espressivo delle formule proposizionali si presta efficacemente alla descrizione del problema. Una istanza generica del problema viene rappresentata utilizzando n caratteristiche ciascuna delle quali può assumere k valori discreti, unitamente ad un insieme di azioni di modifica. Gli obiettivi prestazionali vengono rappresentati mediante un’espressione booleana costituita da letterali, ciascuno dei quali indicante una particolare caratteristica e la performance desiderata. Ad esempio, nel particolare dominio applicativo considerato, quanto espresso dalla specifica di marketing, rispetto a ciascuna caratteristica, si traduce in un letterale che indica la variazione desiderata. E’ possibile specificare il trade off desiderato, relativamente alla variazione da ottenere, per la stessa caratteristica o per caratteristiche diverse disgiungendo i letterali corrispondenti. Mediante la congiunzione delle diverse espressioni, ricavate per ciascuna caratteristica, otteniamo un’espressione booleana in forma normale congiuntiva. Ogni assegnamento rappresenta uno o più interventi applicabili al composto così rappresentato. Il problema CNF-Formulazione consiste nel ricavare un assegnamento di verità che renda soddisfacibile l’espressione booleana in forma normale congiuntiva fornita in input.

Interpretazione del Composto

Nel seguito si mostra in termini formali come gli obiettivi prestazionali possano essere rappresentati mediante una espressione booleana. A ciascun composto sono associate n caratteristiche le quali possono assumere r valori discreti e pertanto possiamo costruire n·r variabili booleane che rappresentano tutte le caratteristiche per tutti i valori possibili. A titolo esemplificativo si consideri una variabile della forma p(n,d,c), dove le variabili n, d e c indicano rispettivamente la caratteristica, la proporzionalità e la correlazione desiderata rispetto alla specifica di marketing. La variabile n potrà assumere i valori discreti compresi in [1, n], associati a ciascuna caratteristica, mentre d potrà variare su [ ↑,↓ ] indicando rispettivamente la proporzionalità inversa e diretta. Infine la variabile c potrà assumere come valore uno dei simboli {w, g, s} ciascuno dei quali indica l’entità (weak, good o strong) della modifica sulla caratteristica. Ad esempio la variabile p(1, ↑ ,w) indica il fatto che si desidera ottenere un incremento weak della caratteristica p1. Per rappresentare la mescola obiettivo si costruisce un’espressione booleana i cui letterali saranno costituiti dalle variabili presentate sopra. In particolare, le modifiche volute vengono descritte inserendo letterali della forma p1, ↑ ,w. E’ possibile utilizzare più letterali per la stessa caratteristica specificando quindi più valori accettabili mediante la disgiunzione dei letterali associati; nel caso due caratteristiche siano equivalent ai fini del composto da ottenere è possibile specificare per entrambe i valori accettabili, quindi inserire nella stessa clausola i letterali associati.

Un esempio di specifica può essere Φ= (p(1, ↑ ,w) or p(1, ↑ ,g)) and ((p(2,↓,s) or p(3, ↑ ,w)) and p(4,↓,g). Tale formula indica la necessità di ottenere un composto in cui la proprietà p1 sia incrementata, p2 venga diminuita oppure p3 venga aumentata e p4 sia decrementata. In generale otteniamo un’espressione in forma normale congiuntiva costituita da più clausole avente al più n · r letterali.

Interpretazione delle Azioni

Nel seguito viene mostrato come rappresentare ciascun intervento mediante un assegnamento di verità. Si consideri un generico intervento sul composto, esso modificherà le caratteristiche del composto. In base agli effetti sulle caratteristiche di tale intervento è possibile costruire una espressione booleana utilizzando gli stessi criteri del paragrafo precedente. Quindi un intervento viene rappresentato come un assegnamento di verità T che soddisfa la clausola prima derivata. Infine, si osservi che la composizione di interventi permette di generare assegnamenti che rappresentano l’applicazione consecutiva di più interventi sul composto chimico.

Considerazioni Finali

L’approccio considerato sfrutta il potere espressivo delle formule proposizionali al fine di esprimere la struttura ed i vincoli del problema. Per stabilire il metodo da utilizzare per il problema della formulazione chimica è stato determinante valutare una limitazione di ogni SAT-Solver, consistente nel fatto che una istanza di SAT è vincolata ad una dimensione massima per l’oggetto che si desidera ottenere. Se la formula in input non è soddisfacibile è necessario generare, mediante estensione, una nuova formula in grado di esprimere tale dimensione. Congiuntamente a quanto riportato, vi è anche la difficoltà di rappresentazione ed implementazione della conoscenza acquisita in modo utile al SAT-Solver prescelto. Pur non costituendo un punto di arrivo, tale studio ha permesso di comprendere alcune delle problematiche relative alla complessità del problema fornendo spunti interessanti soprattutto per quel che riguarda le tecniche di approssimazione della soluzione.

7.3 Complessità di CNF-Formulazione

Nel seguito vengono illustrati alcuni risultati non definitivi relativi alla complessità del problema della formulazione chimica definito come riportato nel paragrafo 1.1.7. Si deve necessariamente precisare che nel seguito non si intende dimostrare alcunchè, ma solo presentare alcune riflessioni effettuate sul problema.

Il problema della formulazione chimica consiste nel ricavare, a partire da una composto iniziale e da un insieme di interventi, un nuovo composto avente determinate caratteristiche mediante l’applicazione di interventi che modificano i valori di tali caratteristiche. Nei paragrafi precedenti è stata presentata una possibile formalizzazione di tale problema rappresentando le caratteristiche associate ad un composto chimico e gli interventi agenti su di esso in termini di clausole booleane ed assegnamenti di verità.

Un possibile risultato teorico potrebbe consistere nel concludere che una istanza di SAT in forma normale congiuntiva si può trasformare in tempo polinomiale in una espressione booleana in forma normale congiuntiva, dimostrando l’appartenenza di CNF-Formulazione alla classe di complessità NP. A tale scopo occorre utilizzare il concetto di riduzione, si deve cioè precisare che cosa significa per un problema essere complesso almeno quanto un altro:

Definizione 7.3.0.1. Il linguaggio L1 è riducibile a L2 se esiste una funzione R, definita su stringhe, computabile da una macchina di Touring deterministica in spazio O(logn) tale che per tutti gli input x sia vero che x 2 L1 se e solo se R(x) 2 L2. La funzione R si dice una riduzione da L1 a L2.

Osserviamo che la richiesta di computabilità in spazio logaritmico corrisponde all’utilizzo di un algoritmo di riduzione avente tempo d’esecuzione polinomiale rispetto all’input.

Si consideri l’espressione booleana in forma normale congiuntiva ottenuta dall’istanza di SAT, indicandola con Z, in tempo polinomiale si può “scorrere” tale formula per ricavare quanti sono i letterali distinti, denotati con k. Si denota con ej il generico letterale di Z in posizione j. Viene generata una caratteristica per tale letterale denotandola con ci dove il pedice indica il letterale da cui è stata generata. I valori assumibili dalle caratteristiche vengono generate utilizzando gli stessi simboli usati per denotare i letterali di Z. Ciascun letterale viene denotato con cik dove l’indice i indica la caratteristica e l’indice k indica il valore assumibile. In effetti, si effettua una semplice rinominazione dei letterali dell’espressione Z. Si costruisce, infine, la tabella degli interventi possibili, come riportato in figura 7.1.

Dal momento che l’espressione Z contiene k letterali distinti, occorrerà un tempo comunque polinomiale rispetto alla dimensione dell’input. Si ottiene quindi un’istanza valida per CNF-Formulazione costituita da un’espressione in forma normale congiuntiva rappresentante gli obiettivi prestazionali da raggiungere e da un insieme di interventi di modifica da utilizzare per la risoluzione. Se l’espressione booleana contenuta nell’istanza di CNF-Formulazione è soddisfacibile deve esserlo anche quella di SAT, dal momento che è stata effettuata una semplice ridenominazione sui letterali, e viceversa.

Allo stesso modo un assegnamento di verità che soddisfi un’espressione deve necessariamente soddisfare anche l’altra. Infine si osservi che la tabella riportata in figura 7.1 permette di costruire tutti gli assegnamenti possibili per l’espressione fornita in input. (CVD)