Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-23T01:15:24.223Z Has data issue: false hasContentIssue false

Programming finite-domain constraint propagators in Action Rules

Published online by Cambridge University Press:  02 August 2006

NENG-FA ZHOU
Affiliation:
Department of Computer and Information Science, CUNY Brooklyn College & Graduate Center, New York, NY, USA (e-mail: [email protected])

Abstract

In this paper, we propose a new language, called AR (Action Rules), and describe how various propagators for finite-domain constraints can be implemented in it. An action rule specifies a pattern for agents, an action that the agents can carry out, and an event pattern for events that can activate the agents. AR combines the goal-oriented execution model of logic programming with the event-driven execution model. This hybrid execution model facilitates programming constraint propagators. A propagator for a constraint is an agent that maintains the consistency of the constraint and is activated by the updates of the domain variables in the constraint. AR has a much stronger descriptive power than indexicals, the language widely used in the current finite-domain constraint systems, and is flexible for implementing not only interval-consistency but also arc-consistency algorithms. As examples, we present a weak arc-consistency propagator for the all_distinct constraint and a hybrid algorithm for n-ary linear equality constraints. B-Prolog has been extended to accommodate action rules. Benchmarking shows that B-Prolog as a CLP(FD) system significantly outperforms other CLP(FD) systems.

Type
Regular Papers
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)