Using knowledge base update actions, ActHEX programs provide a convenient medium for modelling iteration and optimization tasks1. We can model optimization problems as a series of decision problems where each decision problem corresponds to an ActHEX program. The action atoms can coordinate these series of decision problems to find the optimal solution. An example can be the maximal clique problem.
Let G be a graph encoded by means of vertex and edge predicates. A fact size(n) (initially n = 1) is put within a knowledge base called clique, together with the following program:
in(X) v in(X) ← vertex(X). ← in(X), in(Y ), not edge(X, Y ),X != Y. ← &count[in](X),X < N, size(N).
At each call to this program, we find whether there exist a clique of size N2. If a clique of such a size exists, the selected execution plan removes former assertions for the size predicate and then the assertion size(N +1) is pushed to clique by means of an appropriate #assert action: clique is then executed again. The precedence value of the #execute action atom is the largest among the other action atoms which ensures that reexecution of the program is issued after all the changes to the program are done. Notice that execution terminates for some size N' (which is the optimal clique size augmented by 1) for which clique turns in an inconsistent program (having thus no execution schedules).
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log. 7, 3, 499-562.
Last edited 2013-04-23
General
dlvhex source code @ github.com
Description-Of-A-Project
Popular Plugins
Action Plugin
DecisionDiagrams Plugin
Description Logics Plugin
Description Logics Lite Plugin
MELD: Belief Merging Plugin
Nested HEX Plugin
MCSIE Plugin
String Plugin
dlvhex-semweb Project
Documentation
User Guide
README
doxygen
Writing Plugins in C++
Writing Plugins in Python