Grounding Schematic Representations

Some modeling languages such as PDDL allow the use of first-order variables in order to compactly represent several actions and state variables that have a similar form. Most planners, however, work on the ground representation, where all variables have been appropriately substituted by type-consistent objects.

Tarski allows the grounding of such lifted representations by implementing a variation of the strategy implemented by Malte Helmert in the Fast Downward planner (Helmert, Malte. “Concise finite-domain representations for PDDL planning tasks.” Artificial Intelligence 173.5-6 (2009): 503-535). Fast Downward incrementally grounds only those atoms and ground actions that are determined to be reachable from the initial state of the problem. This removes from consideration a (sometimes) large number of ground elements that will never be relevant for the problem. Determining such reachability precisely is as hard as planning itself, but Fast Downward overapproximates the set of reachable elements using the delete-free relaxation of the problem.

Helmert’s algorithm is based on a logic program (LP) that encodes such notion of reachability, and whose canonical model precisely encodes the set of reachable ground atoms and actions of the problem. Whereas Fast Downward solves the LP itself, Tarski generates the program and then relies on an off-the-shelf answer set solver to find the model for it. In particular, Tarski uses the tools provided by the Potassco ASP suite. These are neatly packaged for e.g. different versions of Ubuntu and can be installed easily with sudo apt install gringo.

Let us quickly show how to ground a standard Gripper problem encoded with the standard schematic representation:

[1]:
from tarski.io import PDDLReader

reader = PDDLReader(raise_on_error=True)
reader.parse_domain('./benchmarks/gripper.pddl')
problem = reader.parse_instance('./benchmarks/gripper_prob01.pddl')
lang = problem.language

We can get hold of the classes encapsulating the grounding process from the tarski.grounding module

[2]:
from tarski.grounding import LPGroundingStrategy
from tarski.grounding.errors import ReachabilityLPUnsolvable

and ground the instance of Blocks World with a one-liner

[3]:
grounder = LPGroundingStrategy(reader.problem)

We can inspect the results of the grounding process with ease. For the ground actions, we can query the grounding object for a dictionary that maps every action schema to a list tuples of object names that schema variables are to be bound to, as they were found to be reachable

[4]:
try:
    actions = grounder.ground_actions()
    for name, bindings in actions.items():
        print(f'Action schema {name} has {len(bindings)} reachable bindings:')
        print(", ".join(map(str, bindings)))
except ReachabilityLPUnsolvable:
    print("Problem was determined to be unsolvable during grounding")

---------------------------------------------------------------------------
CommandNotFoundError                      Traceback (most recent call last)
/tmp/ipykernel_610/1553028965.py in <module>
      1 try:
----> 2     actions = grounder.ground_actions()
      3     for name, bindings in actions.items():
      4         print(f'Action schema {name} has {len(bindings)} reachable bindings:')
      5         print(", ".join(map(str, bindings)))

~/checkouts/readthedocs.org/user_builds/tarski/checkouts/stable/src/tarski/grounding/lp_grounding.py in ground_actions(self)
     50             raise RuntimeError('Cannot retrieve set of ground actions from LPGroundingStrategy '
     51                                'configured with ground_actions=False')
---> 52         model = self._solve_lp()
     53         # This will take care of the case where there is not ground action from some schema
     54         groundings = dict()

~/checkouts/readthedocs.org/user_builds/tarski/checkouts/stable/src/tarski/grounding/lp_grounding.py in _solve_lp(self)
     66         if self.model is None:
     67             lp, tr = create_reachability_lp(self.problem, self.do_ground_actions, self.include_variable_inequalities)
---> 68             model_filename, theory_filename = run_clingo(lp)
     69             self.model = parse_model(model_filename, tr)
     70

~/checkouts/readthedocs.org/user_builds/tarski/checkouts/stable/src/tarski/reachability/clingo_wrapper.py in run_clingo(lp)
     12     gringo = shutil.which("gringo")
     13     if gringo is None:
---> 14         raise CommandNotFoundError("gringo")
     15
     16     with tempfile.NamedTemporaryFile(mode='w+t', delete=False) as f:

CommandNotFoundError: Necessary command "gringo" could not be found

Note that the grounder is sometimes able to determine that an instance is unsolvable during its reachability analysis, in which case it throws an exception. The astute reader may be now wondering why we only return the bindings rather than the grounded actions themselves. The reason is that doing so is not safe in general, as big instances (such as those commonly found on the IPC-18 benchmarks) result in thousands of ground operators, and is possible to exhaust the memory available to the Python interpreter.

To ameliorate that issue, we settle for returning instead the minimal amount of data necessary so users can decide how to instantiate ground operators efficiently.

To access the ground atoms, or state variables, identified during the grounding process, we use a similar interface

[5]:
try:
    lpvariables = grounder.ground_state_variables()
    for i, atom in lpvariables.enumerate():
        print(f'Atom #{i}: {atom}')
except ReachabilityLPUnsolvable:
    print("Problem was determined to be unsolvable during grounding")
---------------------------------------------------------------------------
CommandNotFoundError                      Traceback (most recent call last)
/tmp/ipykernel_610/2739632243.py in <module>
      1 try:
----> 2     lpvariables = grounder.ground_state_variables()
      3     for i, atom in lpvariables.enumerate():
      4         print(f'Atom #{i}: {atom}')
      5 except ReachabilityLPUnsolvable:

~/checkouts/readthedocs.org/user_builds/tarski/checkouts/stable/src/tarski/grounding/lp_grounding.py in ground_state_variables(self)
     31         will be the state variables "p(a)", "p(b)" and "p(c)".
     32         """
---> 33         model = self._solve_lp()
     34
     35         variables = SymbolIndex()

~/checkouts/readthedocs.org/user_builds/tarski/checkouts/stable/src/tarski/grounding/lp_grounding.py in _solve_lp(self)
     66         if self.model is None:
     67             lp, tr = create_reachability_lp(self.problem, self.do_ground_actions, self.include_variable_inequalities)
---> 68             model_filename, theory_filename = run_clingo(lp)
     69             self.model = parse_model(model_filename, tr)
     70

~/checkouts/readthedocs.org/user_builds/tarski/checkouts/stable/src/tarski/reachability/clingo_wrapper.py in run_clingo(lp)
     12     gringo = shutil.which("gringo")
     13     if gringo is None:
---> 14         raise CommandNotFoundError("gringo")
     15
     16     with tempfile.NamedTemporaryFile(mode='w+t', delete=False) as f:

CommandNotFoundError: Necessary command "gringo" could not be found

We note that in this case we do return the actual grounded language element. This is because the number of fluents is not generally subject to the same kind of combinatorial explosion that ground actions are. This assessment may change in the future.