Which Dynamic Constraint Problems Can Be Solved By Ants?

Koenraad Mertens, Tom Holvoet, Yolande Berbers

There exist a number of algorithms that can solve dynamic constraint satisfaction/optimization problems (DynCSPs or DynCOPs). Because of the large variety in the characteristics of DynCSPs and DynCOPs, not all algorithms perform equally well on all problems. In this paper, we present the Dynamic Constraint Optimization Ant Algorithm (DynCOAA). It is based upon the ant colony optimization (ACO) meta-heuristic that has already proven its merit in other dynamic optimization problems. We perform a large number of experiments to identify the dynamic constraint problems which our algorithm is most suited for. It turns out that this is a large class of problems, namely heterogeneous problems that change often. We find this to be common characteristics in real-world applications. For these problems, DynCOAA outperforms both the complete and non-complete traditional algorithms that were used for comparison.

Subjects: 7.1 Multi-Agent Systems; 15.2 Constraint Satisfaction

Submitted: Feb 10, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.