Skip to main content

TASSAT 3: TEORIA Y APLICACIONES EN SATISFACTIBILIDAD Y OPTIMIZACION DE RESTRICCIONES

TIN2016-76573-C2-2-P

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprogram Subprograma Estatal de Generación de Conocimiento
Call Proyectos de I+D (Excelencia / Generación de Conocimiento)
Call year 2016
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSIDAD DE LLEIDA

Resultados relacionados

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

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication Artículo científico (JournalArticle)

Off-line synthesis of evolutionarily stable normative systems

  • Morales, Javier
  • Wooldridge, Michael
  • Rodríguez-Aguilar, Juan Antonio
  • López-Sánchez, Maite
Within the area of multi-agent systems, normative systems are a widely used framework for the coordination of interdependent activities. A crucial problem associated with normative systems is that of synthesising norms that will effectively accomplish a coordination task and that the agents will comply with. Many works in the literature focus on the on-line synthesis of a single, evolutionarily stable norm (convention) whose compliance forms a rational choice for the agents and that effectively coordinates them in one particular coordination situation that needs to be identified and modelled as a game in advance. In this work, we introduce a framework for the automatic off-line synthesis of evolutionarily stable normative systems that coordinate the agents in multiple interdependent coordination situations that cannot be easily identified in advance nor resolved separately. Our framework roots in evolutionary game theory. It considers multi-agent systems in which the potential conflict situations can be automatically enumerated by employing MAS simulations along with basic domain information. Our framework simulates an evolutionary process whereby successful norms prosper and spread within the agent population, while unsuccessful norms are discarded. The outputs of such a natural selection process are sets of codependent norms that, together, effectively coordinate the agents in multiple interdependent situations and are evolutionarily stable. We empirically show the effectiveness of our approach through empirical evaluation in a simulated traffic domain., Research supported by the H2020-MSCA-IF project number 707688 (EVNSMAS). Michael Wooldridge was supported by the European Research Council under Grant 291528 (RACE). Juan A. Rodríguez-Aguilar and Maite López-Sánchez were funded by projects TASSAT3: TIN2016-76573-C2-2-P and Collectiveware TIN2015-66863-C2-1-R (MINECO/FEDER)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication Contribución de congreso (ConferenceOutput)

Phase Transition in Realistic Random SAT Models

  • Ansotegui, Carlos
  • Bonet, María Luisa
  • Levy, Jordi
Phase-transition in random SAT formulas is one of the properties best studied by theoretical SAT researchers. There exists a constant rk depending on k such that, if we choose randomly a k-SAT formula over n variables and m clauses, it will be satisfiable with high probability, if m/n < r, and unsatisfiable, otherwise. However, this criterion is useless in practice, because real-world or industrial instances have some properties not shown in random formulas. In the last years, several models of realistic random formulas have been proposed. Here we discuss about the phase transition in these models, and about the size of unsatisfiability proofs. We observe that in these models, like in real-world formulas, there is not a sharp phase transition, the transition occurs for smaller values of r, and the proofs on unsatisfiable formulas are smaller than in the classical random model. We also discuss about the strategies used by modern SAT solvers to exploit these properties., Research partially supported by the EU H2020 Research and Innovation Program under the LOGISTAR project (Grant Agreement No. 769142) and the MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P) and TASSAT 3 (TIN2016-76573-C2-2-P).