ECAI-2000 Conference Paper

[full paper]

Solving Permutation Constraint Satisfaction Problems with Artificial Ants

Christine Solnon

We describe in this paper Ant-P-solver, a generic constraint solver based on the Ant Colony Optimization (ACO) meta-heuristic. The ACO metaheuristic takes inspiration on the observation of real ants collective foraging behaviour. The idea is to model the problem as the search of a best path in a graph. Artificial ants walk trough this graph, in a stochastic and incomplete way, searching for good paths. Artificial ants communicate in a local and indirect way, by laying a pheromone trail on the edges of the graph. Ant-P-solver has been designed to solve a general class of combinatorial problems: permutation constraint satisfaction problems, the goal of which is to find a permutation of n known values, to be assigned to n variables, under some constraints. Many constraint satisfaction problems involve such global permutation constraints. Ant-P-solver capabilities are illustrated, and compared with other approaches, on three of these problems, i.e., the n-queens, the all-interval series and the car-sequencing problems.

Keywords: Constraint Satisfaction

Citation: Christine Solnon: Solving Permutation Constraint Satisfaction Problems with Artificial Ants. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.118-122.