Complessità e Formulazione chimica – Definizione del Problema – Part I
Diversi problemi di importanza pratica possono essere considerati come problemi di planning, nel caso del problema della formulazione chimica si è scelto di seguire un approccio indipendente dal particolare dominio applicativo costruendo un planner in grado di adattarsi alla particolare istanza del problema.
In questo senso, si è reso necessario definire per il problema oltre che la descrizione dello stato iniziale e dell’obiettivo da raggiungere anche la specifica dichiarativa del mondo su cui si intende agire. Tale specifica ha un requisito fondamentale: deve essere sufficientemente generale da poter rappresentare qualsiasi dominio applicativo per il problema della formulazione. In particolare, si sono utilizzati i sistemi di riscrittura come strumento per modellare in modo generico le azioni da effettuare per la modifica del composto chimico oggetto di formulazione. Il carattere dichiarativo della regola di riscrittura fornisce un meccanismo naturale per la specifica di trasformazioni complesse. Il problema principale nei sistemi di riscrittura consiste nel provare la convergenza, ovvero verificare se due termini qualsiasi possano essere riscritti in un numero finito di passi in un’unica forma, detta forma normale. Nel contesto della formulazione chimica due soluzioni intermedie o finali vengono considerate equivalenti se possiedono caratteristiche e performance simili indipendentemente dallo loro composizione chimica o dalle azioni utilizzate. Si osservi, infine, che non si intende dimostrare la convergenza nei sistemi di riscrittura proposti, ma utilizzare le regole di riscrittura in essi definite per esplorare lo spazio di ricerca.
1.1 Definizione del Problema
Un problema di planning viene descritto da un insieme di azioni, ciascuna caratterizzata da precondizioni e postcondizioni, da uno stato iniziale del mondo e da una descrizione degli obiettivi che si intendono raggiungere. Il problema viene risolto ricavando un insieme specifico di azioni che, se applicate in un ordine prestabilito, trasformano lo stato iniziale in uno stato soddisfacente tali obiettivi. Questa visione del problema è quindi essenzialmente incentrata sulla ricerca delle azioni che con il dispendio minore di risorse consentano il raggiungimento degli obiettivi; le azioni costituiscono gli unici strumenti per agire sugli stati del mondo e la loro applicazione genera transizioni da uno stato all’altro.
1.1.1 Il Composto Chimico
Volendo generare una rappresentazione concettuale di un generico composto è naturale considerare innanzitutto gli elementi chimici che lo compongono. La conoscenza di ogni dominio applicativo, relativamente agli aspetti quantitativi, viene generalizzata e formalizzata utilizzando una struttura tassonomica in grado di classificare ogni componente e sottocomponente. In tale rappresentazione trovano posto gli elementi costitutivi: materie prime, ingredienti e ricette. In particolare, gli ingredienti costituiscono il punto d’unione tra materie prime e ricetta, inoltre vengono classificati utilizzando altre entità proprie del problema della formulazione: famiglie e sistemi. Tuttavia ciascun composto non può essere descritto semplicemente mediante la sua composizione chimica, per ottenere una rappresentazione completa del composto oggetto del processo di formulazione chimica occorre considerare le qualità di cui gode. La rappresentazione utilizzata sfrutta una gerarchia d’astrazione strutturando il composto in base alle tre dimensioni del problema: ingredienti, caratteristiche e performance. Per ciascuna di esse viene generata una astrazione in grado di rappresentare precisamente ogni composto relativamente alla dimensione considerata. Alla luce di quanto riportato è del tutto naturale considerare le modifiche applicabili al composto chimico relativamente ai tre livelli d’astrazione concettuale considerati, infatti ogni livello risulta costituito da elementi atomici che, una volta specificati, individuano univocamente il composto.
1.1.2 Le Azioni
Le azioni racchiudono la conoscenza specifica di domino relativamente alla trasformazione di un composto rispetto a particolari obiettivi prestazionali. L’applicazione di una determinata azione produce un nuovo composto, differente per composizione, che può non essere una soluzione per il problema specifico, tuttavia le azioni non possono snaturare il composto a cui vengono applicate rispettando la sua struttura ontologica.
La sintassi di ogni azione viene definita in modo simile alla definizione data per le regole dei sistemi di riscrittura. Una regola risulta costituita da un antecedente, che specifica una condizione sull’elemento del composto su cui si desidera intervenire, e da un conseguente, che specifica come riscrivere l’elemento considerato. Ad esempio, è necessario verificare l’applicabilità di un intervento rispetto al composto considerato, pertanto si rende necessario l’utilizzo dell’astrazione basata sugli ingredienti relativi al composto per verificare che tutti i vincoli necessari a preservare la struttura del composto siano soddisfatti.
Infine, risulta fondamentale garantire che la specifica di una regola di riscrittura preservi la correttezza ontologica del composto, ovvero produca a partire da un composto valido un nuovo composto, riscritto, altrettanto valido. A tale scopo, ciascuna regola può essere specificata indicando puntualmente tutti i termini implicati nella riscrittura, ovvero rappresentando nell’antecedente i parametri utili all’operatore presente nel conseguente. In questo modo ciò che viene modificato dalla regola è completamente determinato, pertanto è possibile definire la riscrittura in modo univoco; in questo senso la rappresentazione della conoscenza relativa al particolare dominio applicativo gioca un ruolo determinante perchè consente di individuare le situazioni che presentano ambiguità.
Alternativamente è possibile specificare le regole in modo rilassato omettendo la descrizione completa dei termini nell’antecedente oppure mediante una rappresentazione più generale, specificando comunque nel conseguente l’operatore da applicare e lasciando al sistema il compito di individuare i parametri corretti preservando la struttura e la validità del composto. Tali regole vengono utilizzate nel caso in cui si desideri gestire una classe particolare di composti chimici che presentano proprietà comuni utili agli obiettivi del sistema. Le azioni applicabili al composto chimico utilizzano i tre livelli d’astrazione concettuale già citati, per esempio nell’antecedente possono essere rappresentati gli ingredienti che devono essere necessariamente presenti nel composto chimico per poter applicare l’azione considerata. L’operatore presente nel conseguente agirà sull’astrazione relativa agli ingredienti, modificando la composizione chimica, e sulle astrazioni relative a caratteristiche e performance indicando come il composto sia cambiato dal punto di vista qualitativo dopo l’applicazione dell’intervento.
1.1.3 Lo stato iniziale
L’individuazione del composto iniziale è un processo strettamente in relazione alla natura del particolare dominio applicativo. In generale, tale compito può essere complesso quanto generare un nuovo composto soddisfacente gli obiettivi. E’ possibile specificare un insieme di regole di selezione in modo da ricavare rapidamente un composto iniziale, per esempio analizzando gli obiettivi prestazionali.
Un altro approccio possibile è istanziare il planner su un composto iniziale fittizio ed utilizzare la soluzione trovata come criterio per la selezione del composto iniziale.
1.1.4 Gli Obiettivi
Il composto chimico che si intende ricavare mediante l’applicazione delle azioni di modifica viene specificato in termini qualitativi, esplicitando però le caratteristiche desiderate mediante opportuni indici. A tale scopo si utilizzano le astrazioni concettuali relative alle caratteristiche ed alle performance, individuando così una classe di composti chimici aventi le stesse qualità ma differente composizione. In questi termini la specifica degli obiettivi viene ottenuta indipendentemente dal dominio applicativo in quanto le astrazioni considerate per tale specifica sono le stesse utilizzate per rappresentare un generico composto chimico. Sintatticamente è sufficiente indicare le performance o le caratteristiche che contraddistinguono il composto obiettivo mediante la congiunzione dei simboli che le rappresentano con la variazione desiderata.
1.1.5 La Ricerca della soluzione
L’obiettivo di ricavare un sistema automatico per la formulazione chimica indipendente dal domino applicativo impone di effettuare una prima classificazione dei domini possibili in base a due criteri:
• Soddisfacibilità: la difficoltà risiede nel ricavare una soluzione ammissibile per il problema indipendentemente dalla qualità.
• Ottimizzazione: è semplice ricavare una soluzione ammissibile, tuttavia la soluzione ottima non è semplicemente individuabile.
Per un dato dominio, ciascun criterio può contribuire in modo differente alla complessità del problema. Per esempio, nel secondo caso le soluzioni possono essere semplici da ricavare ma con costi inaccettabili. Tuttavia la ricchezza di struttura del problema della formulazione chimica permette di utilizzare la conoscenza relativa al domino applicativo per aumentare l’efficienza del processo di ricerca della soluzione. L’approccio seguito consta di due fasi:
• Generazione di un composto iniziale: nel caso in cui la componente di ottimizzazione sia rilevante, il criterio di selezione deve garantire una qualità sufficiente a ricavare soluzioni ammissibili con un costo accettabile.
• Riscrittura della soluzione iniziale: le regole vengono utilizzate per migliorare la qualità del composto iniziale rispetto agli obiettivi prestazionali.
Dal momento che lo spazio di ricerca associato al problema della formulazione non può essere esplorato sistematicamente in modo efficiente, si è scelto un approccio orientato alla ricerca locale utilizzando le tecniche note nell’ambito dell risoluzione di problemi combinatori. Le caratteristiche del dominio, la selezione del composto iniziale e le regole di riscrittura determinano quale algoritmo di ricerca utilizzare. Si osservi che l’ottenimento di una soluzione ammissibile dipende in larga misura dal composto iniziale prescelto, in quanto nel caso in cui il grafo di ricerca risulti sconnesso è possibile ricavare una soluzione scegliendo il composto iniziale che si trova nella componente del grafo contenente il massimo globale. In generale, però, non vi sono a disposizione dei generatori di composti iniziali così potenti, pertanto la soluzione ottima non può essere raggiunta con una singola ricerca. In effetti è possibile ritenere che composti chimici, chimicamente differenti ma con qualità simili, siano “vicini” quando il percorso che li unisce attraverso il grafo di ricerca è ragionevolmente breve (ovvero è necessario applicare poche regole) o equivalentemente poichè condividono gran parte della loro struttura. Tuttavia questa considerazione non consente di concludere che sia sempre possibile ricavare una soluzione accettabile a partire da un composto molto simile in termini qualitativi alla soluzione soddisfacente gli obiettivi prestazionali. Si può comunque utilizzare un generatore di composti iniziali poco efficiente combinandolo con una strategia a riavvio multiplo per eliminare tali problemi.
