The Action Plugin and Action Addon Framework


An Example of Observe-Think-Act Cycle with ActHEX Programs

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).

References

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.

  1. The example is illustrative of knowledge update action constructs only and is not to be considered as an alternative proposal for choices and other optimization construct known in ASP.
  2. The external atom &count[in](X) can be seen as as equivalent to the DLV (Leone et al. 2006) aggregate construct #count{Y : in(Y)} = X.


Last edited 2013-04-23