In this paper the Constraint Satisfaction Ant Algorithm (CSAA) framework is presented. The underlying infrastructure and the ants behavior are described in detail. The CSAA framework is an ant-based system for solving discrete Constraint Satisfaction Problems (CSP) and Partial Constraint Satisfaction Problems (PCSP). CSPs and PCSPs are used among others to design facility layouts and schedule workflow and repairs. Ant-based systems use stochastic decision making and positive feedback processes to reach their goal. Ant algorithms have already proven their value in solving various optimization problems. In this paper we show that they are also useful for more general constraint reasoning. We combined the strengths of ant-based systems -flexibility, the ability to adapt to changes - with heuristics from traditional constraint reasoning in order to obtain a flexible, yet efficient algorithm. The flexibility is used to continuously improve on the solution. This aspect of the framework gives the algorithm a great advantage over traditional solving methods when constraints and/or variables are added or removed at run-time. This becomes important when for example workflow should change dynamically according to user demands.
展开▼
