Pasar al contenido principal

SISTEMAS EFICIENTES DE RAZONAMIENTO AUTOMATICO CON INFORMACION INCOMPLETA E IMPRECISA BASADOS EN SAT Y CSP: DISEÑO E IMPLEMENTACION

TIN2009-14704-C03-01

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2009
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSIDAD DE LLEIDA
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

Resultados totales (Incluyendo duplicados): 6
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories

  • Ansótegui Gil, Carlos José
  • Bofill, Miquel
  • Palahí, Miquel
  • Suy, Josep
  • Villaret, Mateu
We introduce WSimply, a new framework for modelling and solving Weighted Constraint Satisfaction Problems (WCSP) using Satisfiability Modulo Theories (SMT) technology. In contrast to other well-known approaches designed for extensional representation of goods or no-goods, and with few declarative facilities, our approach aims to follow an intensional and declarative syntax style. In addition, our language has built-in support for some meta-constraints, such as priority and homogeneity, which allows the user to easily specify rich requirements on the desired solutions, such as preferences and fairness. We propose two alternative strategies for solving these WCSP instances using SMT. The first is the reformulation into Weighted SMT (WSMT) and the application of satisfiability test based algorithms from recent contributions in the Weighted Maximum Satisfiability field. The second one is the reformulation into an operation research-like style which involves an optimisation variable or objective function and the application of optimisation SMT solvers. We present experimental results of two well-known problems: the Nurse Rostering Problem (NRP) and a variant of the Balanced Academic Curriculum Problem (BACP), and provide some insights into the impact of the addition of meta-constraints on the quality of the solutions and the solving time., Research partially supported by the Generalitat de Catalunya under grant AGAUR 2009-SGR-1434, and the Ministerio de Economía y Competividad research projects TIN2008-04547, TIN2009-14704-C03-01, and TIN2010-20967-C04-01/03.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

RP-DeLP: a weighted defeasible argumentation framework based on a recursive semantics

  • Alsinet, Teresa
  • Béjar Torres, Ramón
  • Godo i Lacasa, Lluís
  • Guitart Bravo, Francesc
In this paper we first define a recursive semantics for warranted formulas in a general defeasible argumentation framework by formalizing a notion of collective (non-binary) conflict among arguments. The recursive semantics for warranted formulas is based on the fact that if the argument is rejected, then all arguments built on it should also be rejected. The main characteristic of our recursive semantics is that an output (extension) of a knowledge base is a pair of sets of warranted and blocked formulas. Arguments for both warranted and blocked formulas are recursively based on warranted formulas but, while warranted formulas do not generate any collective conflict, blocked conclusions do. Formulas that are neither warranted nor blocked correspond to rejected formulas. Second we extend the general defeasible argumentation framework by attaching levels of preference to defeasible knowledge items and by providing a level-wise definition of warranted and blocked formulas. Third we formalize the warrant recursive semantics for the particular framework of Possibilistic Defeasible Logic Programming, we call this particular framework Recursive Possibilistic Defeasible Logic Programming (\mbox{RP-DeLP} for short), and we show its relevance in the scope of Political debates. An RP-DeLP program may have multiple outputs in case of circular definitions of conflicts among arguments. So, we tackle the problem of which output one should consider for an RP-DeLP program with multiple outputs. To this end we define the maximal ideal output of an RP-DeLP program as the set of conclusions which are ultimately warranted and we present an algorithm for computing them in polynomial space and with an upper bound on complexity equal to P^{NP}. Finally, we propose an efficient and scalable implementation of this algorithm that is based on implementing the two main queries of the system, looking for valid arguments and collective conflicts between arguments, using SAT encodings. We perform an experimental evaluation of our SAT based approach when solving test sets of instances with single and multiple preference levels for defeasible knowledge., The authors are very thankful to the anonymous reviewers for their helpful and constructive comments. This research was partially supported by the Spanish projects ARINF (TIN2009- 14704-C03-01), TASSAT (TIN2010-20967-C04-03), EdeTRI (TIN2012-39348-C02-01) and AT (CONSOLIDER- INGENIO 2010, CSD2007-00022).
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Generating Hard Satisfiable Scheduling Instances

  • Argelich Romà, Josep
  • Béjar Torres, Ramón
  • Cabiscol i Teixidó, Alba
  • Fernàndez Camon, César
  • Manyà Serres, Felip
  • Gomes, Carla
We present a random generator of partially complete round robin timetables that produces exclusively satisfiable instances, and provide experimental evidence that there is an easy-hard-easy pattern in the computational difficulty of completing partially complete timetables as the ratio of the number of removed entries to the total number of entries of the timetable is varied. Timetables in the hard region provide a suitable test-bed for evaluating and fine-tuning local search algorithms, Research partially funded by the Generalitat de Catalunya under grant AGAUR 2009-SGR-1434, the Ministerio de EconomÍa y Competividad research projects AT CONSOLIDER CSD2007-0022, INGENIO 2010, ARINF TIN2009-14704-C03-01, TASSAT TIN2010- 20967-C04-01/03, and Newmatica INNPACTO IPT-2011-1496-310000 (funded by the Ministerio de Ciencia y Tecnología until 2011).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

RP-DeLP: a weighted defeasible argumentation framework based on a recursive semantics

  • Alsinet, Teresa
  • Béjar Torres, Ramón
  • Godo i Lacasa, Lluís
  • Guitart Bravo, Francesc
In this paper we first define a recursive semantics for warranted formulas in a general defeasible argumentation framework by formalizing a notion of collective (non-binary) conflict among arguments. The recursive semantics for warranted formulas is based on the fact that if the argument is rejected, then all arguments built on it should also be rejected. The main characteristic of our recursive semantics is that an output (extension) of a knowledge base is a pair of sets of warranted and blocked formulas. Arguments for both warranted and blocked formulas are recursively based on warranted formulas but, while warranted formulas do not generate any collective conflict, blocked conclusions do. Formulas that are neither warranted nor blocked correspond to rejected formulas. Second we extend the general defeasible argumentation framework by attaching levels of preference to defeasible knowledge items and by providing a level-wise definition of warranted and blocked formulas. Third we formalize the warrant recursive semantics for the particular framework of Possibilistic Defeasible Logic Programming, we call this particular framework Recursive Possibilistic Defeasible Logic Programming (\mbox{RP-DeLP} for short), and we show its relevance in the scope of Political debates. An RP-DeLP program may have multiple outputs in case of circular definitions of conflicts among arguments. So, we tackle the problem of which output one should consider for an RP-DeLP program with multiple outputs. To this end we define the maximal ideal output of an RP-DeLP program as the set of conclusions which are ultimately warranted and we present an algorithm for computing them in polynomial space and with an upper bound on complexity equal to P^{NP}. Finally, we propose an efficient and scalable implementation of this algorithm that is based on implementing the two main queries of the system, looking for valid arguments and collective conflicts between arguments, using SAT encodings. We perform an experimental evaluation of our SAT based approach when solving test sets of instances with single and multiple preference levels for defeasible knowledge., The authors are very thankful to the anonymous reviewers for their helpful and constructive comments. This research was partially supported by the Spanish projects ARINF (TIN2009- 14704-C03-01), TASSAT (TIN2010-20967-C04-03), EdeTRI (TIN2012-39348-C02-01) and AT (CONSOLIDER- INGENIO 2010, CSD2007-00022).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Generating Hard Satisfiable Scheduling Instances

  • Argelich Romà, Josep
  • Béjar Torres, Ramón
  • Cabiscol i Teixidó, Alba
  • Fernàndez Camon, César
  • Manyà Serres, Felip
  • Gomes, Carla
We present a random generator of partially complete round robin timetables that produces exclusively satisfiable instances, and provide experimental evidence that there is an easy-hard-easy pattern in the computational difficulty of completing partially complete timetables as the ratio of the number of removed entries to the total number of entries of the timetable is varied. Timetables in the hard region provide a suitable test-bed for evaluating and fine-tuning local search algorithms, Research partially funded by the Generalitat de Catalunya under grant AGAUR 2009-SGR-1434, the Ministerio de EconomÍa y Competividad research projects AT CONSOLIDER CSD2007-0022, INGENIO 2010, ARINF TIN2009-14704-C03-01, TASSAT TIN2010- 20967-C04-01/03, and Newmatica INNPACTO IPT-2011-1496-310000 (funded by the Ministerio de Ciencia y Tecnología until 2011).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories

  • Ansótegui Gil, Carlos José
  • Bofill, Miquel
  • Palahí, Miquel
  • Suy, Josep
  • Villaret, Mateu
We introduce WSimply, a new framework for modelling and solving Weighted Constraint Satisfaction Problems (WCSP) using Satisfiability Modulo Theories (SMT) technology. In contrast to other well-known approaches designed for extensional representation of goods or no-goods, and with few declarative facilities, our approach aims to follow an intensional and declarative syntax style. In addition, our language has built-in support for some meta-constraints, such as priority and homogeneity, which allows the user to easily specify rich requirements on the desired solutions, such as preferences and fairness. We propose two alternative strategies for solving these WCSP instances using SMT. The first is the reformulation into Weighted SMT (WSMT) and the application of satisfiability test based algorithms from recent contributions in the Weighted Maximum Satisfiability field. The second one is the reformulation into an operation research-like style which involves an optimisation variable or objective function and the application of optimisation SMT solvers. We present experimental results of two well-known problems: the Nurse Rostering Problem (NRP) and a variant of the Balanced Academic Curriculum Problem (BACP), and provide some insights into the impact of the addition of meta-constraints on the quality of the solutions and the solving time., Research partially supported by the Generalitat de Catalunya under grant AGAUR 2009-SGR-1434, and the Ministerio de Economía y Competividad research projects TIN2008-04547, TIN2009-14704-C03-01, and TIN2010-20967-C04-01/03.