Computer Science – Artificial Intelligence
Scientific paper
2001-11-14
Computer Science
Artificial Intelligence
Figure 3 modified
Scientific paper
The notion of arc consistency plays a central role in constraint satisfaction. It is known that the notion of local consistency can be extended to constraint optimisation problems defined by soft constraint frameworks based on an idempotent cost combination operator. This excludes non idempotent operators such as + which define problems which are very important in practical applications such as Max-CSP, where the aim is to minimize the number of violated constraints. In this paper, we show that using a weak additional axiom satisfied by most existing soft constraints proposals, it is possible to define a notion of soft arc consistency that extends the classical notion of arc consistency and this even in the case of non idempotent cost combination operators. A polynomial time algorithm for enforcing this soft arc consistency exists and its space and time complexities are identical to that of enforcing arc consistency in CSPs when the cost combination operator is strictly monotonic (for example Max-CSP). A directional version of arc consistency is potentially even stronger than the non-directional version, since it allows non local propagation of penalties. We demonstrate the utility of directional arc consistency by showing that it not only solves soft constraint problems on trees, but that it also implies a form of local optimality, which we call arc irreducibility.
Cooper Martin
Schiex Thomas
No associations
LandOfFree
Arc consistency for soft constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Arc consistency for soft constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arc consistency for soft constraints will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-355463