Model Agnostic solution of CSPs with Deep Learning

Negli ultimi anni, le tecniche di Deep Learning sono state notevolmente migliorate, permettendo di affrontare con successo numerosi problemi. Il Deep Learning ha un approccio sub-simbolico ai problemi, perciò non si rende necessario descrivere esplicitamente informazioni sulla struttura del problema per fare sì che questo possa essere affrontato con successo; l'idea è quindi di utilizzare reti neurali di Deep Learning per affrontare problemi con vincoli (CSPs), senza dover fare affidamento su conoscenza esplicita riguardo ai vincoli dei problemi. Chiamiamo questo approccio Model Agnostic; esso può rivelarsi molto utile se usato sui CSP, dal momento che è spesso difficile esprimerne tutti i dettagli: potrebbero esistere vincoli, o preferenze, che non sono menzionati esplicitamente, e che sono intuibili solamente dall'analisi di soluzioni precedenti del problema. In questi casi, un modello di Deep Learning in grado di apprendere la struttura del CSP potrebbe avere applicazioni pratiche rilevanti. In particolar modo, in questa tesi si è indagato sul fatto che una Deep Neural Network possa essere capace di risolvere il rompicapo delle 8 regine. Sono state create due diverse reti neurali, una rete Generatore e una rete Discriminatore, che hanno dovuto apprendere differenti caratteristiche del problema. La rete Generatore è stata addestrata per produrre un singolo assegnamento, in modo che questo sia globalmente consistente; la rete Discriminatore è stata invece addestrata a distinguere tra soluzioni ammissibili e non ammissibili, con l'idea che possa essere utilizzata come controllore dell'euristica. Infine, sono state combinate le due reti in un unico modello, chiamato Generative Adversarial Network (GAN), in modo che esse possano scambiarsi conoscenza riguardo al problema, con l'obiettivo di migliorare le prestazioni di entrambe.