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.