ASP Taking Action

By Michael Fink
Vienna University of Technology,



The acthex formalism generalizes logic programs under the answer-set semantics, that may have access to external sources (aka hex-programs), by introducing action atoms in rule heads in order to effect an external environment. In this article we briefly motivate and review the main concepts of the framework. Prospective applications are dynamic in nature and may interleave reasoning with actual action execution. As a representative, we report on an academic challenge where the framework may be fruitfully applied.


One hammer never fits all nails. Despite its success as a declarative problem solving approach, not least due to availability of efficient solvers, this certainly also holds for declarative logic programming paradigms such as Answer Set Programming (ASP). Even if it is not a matter of expressivity, efficiency considerations may call for the use of dedicated algorithms (for instance, how about computing physical properties of 2-dimensional objects represented as convex polygons?). Moreover, current trends in computing, such as context awareness or distributed systems, raise the need to access external data sources, e.g., on the Web. Extensions of ASP, such as hex-programs [7], that incorporate external means of computation and sources of information have been developed precisely for that purpose. They have successfully been exploited for many applications, including querying data and ontologies [689], e-government [12], fuzzy answer set programming [10], multi-context reasoning [52], conditional planning [11].

However, dynamic systems impose further challenges. External atoms are purposely stateless (yielding a purely declarative semantics) and not intended to change the state of external sources. While dynamic systems are concerned with states that evolve over time and computation becomes stateful. A common way to couple declarative reasoning tasks with code that actually effects an exogenous environment is roughly to: wrap a declarative solver in a procedural language, execute it iteratively, and at each step parse its answer sets and establish ad-hoc links with effective code. For a less cumbersome and more rigorous interaction, a generalization of hex-programs called acthex [14] aims at tighter integration under declarative control, essentially by means of so-called action atoms in rule heads. In the following, we briefly review the main concepts of the acthex framework, before we turn to an academic challenge where we expect to fruitfully exploit acthex-programs to improve over an existing hex-based solution.

Programs with External and Action Atoms

The acthex formalism [14] generalizes hex programs [7] introducing dedicated action atoms in rule heads. Action atoms can actually operate on and change the state of an environment, which can be roughly seen as an abstraction of realms outside the logic program at hand. The acthex framework allows to conveniently design ASP-based applications by properly connecting logic-based decisions to actual effects thereof.

In addition to constants (also used for predicate names) and variables, acthex programs build on external predicate names (prefixed by &) and action predicate names (prefixed by #).

An external atom is of the form


where Y1,,Yn and X1,,Xm are lists of (input and output) terms. Formally, its semantics is given by an associated boolean function f&g of arity n + m + 1. Intuitively, given an interpretation I (for ordinary atoms) and n + m ground terms, the corresponding ground external atom evaluates to true under I if tf&g returns 1.

An action atom is of the form

where #g is an action predicate name, Y1,,Yn is a list of input terms of fixed length in(#g) = n. Moreover, attribute o ∈{b,c,cp} is called the action option that identifies an action as brave, cautious, or preferred cautious, while optional integer attributes r, w, and l are called precedence, weight, and level of #g, respectively. Semantically, action atoms are assigned an n + 2-ary action function f#g. It takes an environment state E, an interpretation I, and n ground terms as its input and returns an environment state E, thus intuitively capturing the execution of the corresponding ground action. A rule r is of the form

α1∨ … αk ← β1,…,βn, not βn+1,…,not βm

where body elements β are (ordinary) atoms or external atoms, and head elements α are (ordinary) atoms or action atoms. An acthex program is a finite set of rules.

Example 1 The acthex program P1 = {#robot[goto,charger]{b,1}&sensor[bat](low); #robot[clean,kitchen]{c,2}night; #robot[clean,bedroom]{c,2}day; night day} uses action atom #robot to control a robot, and an external atom &sensor to access sensor data. Intuitively, precedence 1 of action atom #robot[goto,charger]{b,1} should make the robot recharging its battery, if necessary, before cleaning actions.

acthex semantics. An acthex program P is evaluated wrt. a fixed state (snapshot) of the external environment E using the following steps:

  1. answer sets of P are determined wrt. E, and the set of best models is a subset of the answer sets determined by an objective function (taking into account level and weight associated with action atoms);
  2. any (best) model originates a set of corresponding execution schedules S, i.e., a sequence of actions to execute (taking into account actions’ options and preferences);
  3. executing the actions of (and sequentially according to) a selected schedule S yields another (not necessarily different) state Eof the environment, called the observed execution outcome; finally
  4. the process may be iterated starting at (i), by considering a snapshot E′′, which can be different from Edue to exogenous actions (in so-called dynamic environments).

Answer Sets are defined similarly to hex programs [7], i.e., using Herbrand interpretations, the grounding of P wrt. the Herbrand universe, and the FLP reduct, where ground action atoms in rule heads are treated like ordinary atoms as far as answer set computation is concerned.

An implementation of the acthex framework has been realized as an extension to the dlvhex system. Compared to the workflow of an answer set solver, it also computes execution schedules and executes one of it according to the semantics of acthex programs given a selection policy of execution schedules (e.g., first computed), and executable code provided for action predicates. A toolkit facilitates the development of libraries of action predicates with some example libraries available.

Several problems of practical importance and dynamic nature fit the realm of potential acthex applications, including knowledge base updates, reactive reasoning over changing data, the interleaving of (re-)planning with actual plan execution, logic-based agent programming, etc. For the remainder of this article, however, let us focus on an interesting academic challenge.

Angry Birds AI Competition – a Challenge

Angry Birds is a very popular video game where the main goal is to shoot at some pigs by means of birds of different characteristics from a slingshot. The game field (which is static until the player moves) features some structures that shelter pigs. Structures can be very complicated and can involve a number of different object categories with different properties, like wood, ice, stone, etc. The game scenario evolves largely complying with physics laws on a bi-dimensional plane; thus, it is possible, in principle, to infer how a structure will change if hit at a certain position by a certain bird.

The Angry Birds AI Competitionsare designed to test the abilities of Angry Birds artificial agents, playing on a variety of levels, on the Google Chrome version of the game. The competition runs on a client/server architecture, where the server runs an instance of the game for each participating agent. Each agent runs on a client computer, and communicates with the server according to a given protocol that allows agents to fetch screenshots of their game state at any time. An artificial player can also obtain the current high scores for each level, and can prompt the server for executing a shot, which will in turn be performed in the corresponding game state. The long term goal of the Competition is to foster the building of AI agents that can play any new level better than the best human players. In order to successfully solve this challenge, participants are solicited to combine different areas of AI such as computer vision, knowledge representation and reasoning, planning, heuristic search, and machine learning. Successfully integrating methods from these areas is indeed one of the great challenges of AI.

In a joint effort of two groups at Technische Universität Wien (TUWIEN) and Università della Calabria (UNICAL) we have developed a participating, logic programming based agent [3]. It is called AngryHEX and realized using hex-programs. Our agent builds on the Base Framework provided by the organizers and extends it with declarative means for decision making modules. Declarative logic programming kicks in on two different layers for AngryHEX: the tactics layer, which plans shots, and decides how to complete a level; and the strategy layer, which decides the order of levels to play and possible multiple attempts to solve the same level.


Tactics. The tactics layer is declaratively realized by a hex-program that computes optimal shots based on information about the current scene and on domain knowledge modeled as part of the program. Its input comprises scene information encoded as a set of logic program facts (position, size and orientation of pigs, ice, wood and stone blocks, slingshot, etc.); its output are answer sets that contain a dedicated atom describing the target to hit, and further information about the required shot. Physics simulation results and other information are accessed via external atoms. For instance, the following rule intuitively represents the likelihood that an object O2 falls when O1 is hit, where the fact whether O1 can push O2 at all depends on an external (physics) computation taken into account by the external atom &canpush.

pushDamage(O2,P1,P) ← pushDamage(O1,_,P1),

              P1 > 0, &canpush[ngobject](O1,O2),

              pushability(O2,P2), P = P1 * P2 / 100.

Stragegy. This layer decides, at the end of each level, which level to play next. This layer is also realized declaratively as an (ordinary) ASP program encoding our strategy on three priority levels: (1) each available level is played once; (2) levels where the agent score differs most from the current best score are selected; (3) levels where AngryHEX achieved a score higher than the current best scores and that have the minimum difference from the best score, are selected. For each level, the strategy layer keeps track of previously achieved scores and previously selected initial target objects.

AngryHEX performed very well in the 2013 Competition at IJCAI, reaching semifinals. Notably, AngryHEX kept the first place out of 20 participants, in both the two qualification rounds. Benchmarking performed by the Competition Organizer after the Competition also shows AngryHEX ranking with the best score in the first 21 levels of the ‘Poached Eggs’ level set. The agent also participated in the 2014 Competition at ECAI this year with minor improvements, finishing quarterfinalist and outperforming the 2013 winner (which participated unmodified however).

The competitions revealed several aspects for AngryHEX improvement. A very important issue for its competitivness, which became clear already in 2013 but more obvious this year, is to consider tactics on a more global scale beyond shot by shot analysis. Here is where acthex may kick in: rather than calling dlvhex iteratively for (a single) shot analysis, an acthex-program might suitably represent and encode planning over a sequence of shots taking, e.g., the order and type of available birds into account. Also, interleaving its execution with monitoring and re-planning after performing individual shots might increase its robustness in case of unexpected outcomes. Since it is precisely for capabilites like these that acthex sets out to facilitate it would be a natural next step to evolve AngryHEX into an acthex agent.


The acthex framework is a promising generalization of hex-programs, i.e., logic programs under the answer-set semantics with access to external sources, aiming at the realization of reasoning tasks for dynamic systems under declarative control. Beyond evaluating acthex in academic settings like the presented Angry Birds AI Competition, an interesting application (and hot topic) would for instance be the implementation of approaches to stream reasoning. In addition to applying the framework as a driving force for further development, also interesting theoretical issues, such as regarding program termination, branching in the environment space (e.g., due to nonmonotonic actions), or incorporating parallel execution schedules remain for future work.



[1]   Selen Basol, Ozan Erdem, Michael Fink, and Giovambattista Ianni. HEX Programs with Action Atoms. In Manuel Hermenegildo and Torsten Schaub, editors, Technical Communications of the 26th International Conference on Logic Programming (ICLP’10), volume 7 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24–33, Dagstuhl, Germany, 2010. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[2]   Gerd Brewka and Thomas Eiter. Equilibria in Heterogeneous Nonmonotonic Multi-Context Systems. In Robert C. Holte and Adele Howe, editors, 22nd AAAI Conference on Artificial Intelligence (AAAI’07), pages 385–390. AAAI Press, 2007.

[3]   Francesco Calimeri, Michael Fink, Stefano Germano, Giovambattista Ianni, Christoph Redl, and Anton Wimmer. Angryhex: an artificial player for angry birds based on declarative knowledge bases. In Matteo Baldoni, Federico Chesani, Paola Mello, and Marco Montali, editors, Proceedings of the Workshop Popularize Artificial Intelligence co-located with the 13th Conference of the Italian Association for Artificial Intelligence (AI*IA 2013), Turin, Italy, December 5, 2013., volume 1107 of CEUR Workshop Proceedings, pages 29–35., 2013.

[4]   Thomas Eiter, Michael Fink, Giovambattista Ianni, Thomas Krennwallner, and Peter Schüller. Pushing Efficient Evaluation of HEX Programs by Modular Decomposition. In James Delgrande and Wolfgang Faber, editors, 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’11), volume 6645 of LNAI, pages 93–106. Springer, May 2011.

[5]   Thomas Eiter, Michael Fink, Peter Schüller, and Antonius Weinzierl. Finding explanations of inconsistency in multi-context systems. Artif. Intell., 216:233–274, 2014.

[6]   Thomas Eiter, Giovambattista Ianni, Thomas Lukasiewicz, Roman Schindlauer, and Hans Tompits. Combining answer set programming with description logics for the semantic web. Artificial Intelligence, 172(12-13):1495–1539, 2008.

[7]   Thomas Eiter, Giovambattista Ianni, Roman Schindlauer, and Hans Tompits. A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer-Set Programming. In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, 19th International Joint Conference on Artificial Intelligence (IJCAI’05), pages 90–96. Professional Book Center, 2005.

[8]   Robert Hoehndorf, Frank Loebe, Janet Kelso, and Heinrich Herre. Representing default knowledge in biomedical ontologies: application to the integration of anatomy and phenotype ontologies. BMC Bioinformatics, 8:377, 2007.

[9]   Marco Marano, Philipp Obermeier, and Axel Polleres. Processing RIF and OWL2RL within DLVHEX. In Pascal Hitzler and Thomas Lukasiewicz, editors, 4th International Conference on Web Reasoning and Rule Systems (RR’10), volume 6333 of LNCS, pages 244–250. Springer, 2010.

[10]   Davy Van Nieuwenborgh, Martine De Cock, and Dirk Vermeir. Computing fuzzy answer sets using dlvhex. In Verónica Dahl and Ilkka Niemelä, editors, 23rd International Conference on Logic Programming (ICLP’07), volume 4670 of LNCS, pages 449–450. Springer, 2007.

[11]   Davy Van Nieuwenborgh, Thomas Eiter, and Dirk Vermeir. Conditional planning with external functions. In Chitta Baral, Gerhard Brewka, and John S. Schlipf, editors, 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’07), volume 4483 of LNCS, pages 214–227. Springer, 2007.

[12]   Hande Zirtiloǧlu and Pinar Yolum. Ranking semantic information for e-government: complaints management. In 1st International Workshop on Ontology-supported Business Intelligence (OBI’08), number 5 in OBI’08, page 7. ACM, 2008.