Self-organisation in Constraint Problem Solving

Abstract : Constraint satisfaction (CSP) or constraint optimisation problems (COP) frameworks are well known and well addressed using classical methods coming from operations research and artificial intelligence. Nevertheless, when dynamics and distribution are added requirements, those approaches do not necessarily fit or need serious re-factoring to be efficient. The idea beneath this chapter is to exploit the intrinsic distributed and adaptive nature of self-organising systems to cooperatively solve distributed constraint based problems, in which constraints and variables can change at run-time, as environmental disturbances influence self-organising societies. In this chapter, several approaches, classical (or not), and their extensions, along with purely multi-agent and self-organising ones, are presented and evaluated in the light of certain characteristics such as distribution, decentralisation, locality, etc. We also argue and show that if we introduce self-organisation, we have benefits and better results. We then introduce one such self-organising approach, and we demonstrate its applicability to the n -queens case study.
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00674785
Contributor : Florent Breuil <>
Submitted on : Tuesday, February 28, 2012 - 11:08:01 AM
Last modification on : Thursday, June 27, 2019 - 4:27:48 PM

Identifiers

Citation

Pierre Glize, Gauthier Picard. Self-organisation in Constraint Problem Solving. Di Marzo Serugendo, Giovanna; Gleizes, Marie-Pierre; Karageorgos, Anthony. Self-organising Software, Springer Berlin Heidelberg, p. 347 - 377, 2011, Natural Computing Series, ⟨10.1007/978-3-642-17348-6_14⟩. ⟨emse-00674785⟩

Share

Metrics

Record views

189