-
Notifications
You must be signed in to change notification settings - Fork 1
ASP Based Successor Generation
A somewhat common operation in PDDLSIM is "Get Grounded Actions" (GGA), also known as Successor Generation, which is used to determine all valid grounded actions an agent can perform in a given state of the simulation. This page describes and details the current approach taken to solving this problem in a way somewhat efficient way, striking a balance between code complexity and avoiding scalability issues for actions with more than a couple of parameters.
Specifically, PDDLSIM currently employs Answer Set Programming (ASP), specifically using the Clingo solver, to solve this problem. To summarize, ASP and Clingo offer a way to define a logical problem, placing different constraints on data, and then find all data satisfying those constraints. From this description, one can quickly understand the applicability of ASP to this issue.
Note
Beyond this point, at least a basic working knowledge of Answer Set Programming is assumed. Without it, things won't make much sense.
In order to solve perform a GGA operation, PDDLSIM first creates an ASP problem, which is composed of several parts, the creation of which will be detailed later:
- The "objects" part, containing facts about the type of each object in the PDDL problem (as well as each constant in the domain), as well as about the type hierarchy of the PDDL domain (e.g., all objects of type
balloonare of typeobject) - The "simulation state" part, containing facts representing the current state of the problem (all predicates that are true)
- The "action definition" part, containing ASP rules which define the action's precondition, as well as show rules so that the resulting programs creates models corresponding to all valid instantiations of the action's parameters
Of course, of these parts, both the "objects" and "action definition" parts are invariant, and won't change over time. "simulation state", does change over time, as the state of the simulation changes. While it can be updated incrementally easily, it is currently regenerated each time, but is cached.
Once all ASP parts are ready, they are assembled into a full ASP program, and fed into Clingo to be solved. Clingo then returns a set of models, satisfying the program, which due to its construction, represent valid groundings of the action. These models are then finally converted into PDDLSIM action groundings, and are promptly returned.
The creation of the individual ASP parts is done in the pddlsim._asp module. To this end, _asp contains multiple functions that create these ASP parts, or modify existing ones. By invoking these functions, the proper ASP parts can be created. While different, all of these functions rely on two things:
- The
ASPPartclass, which represents a general ASP part one can modify (add statements to). ASPPart` creates ASP program parts directly using Clingo's AST API, meaning it is fairly low-overhead. - The
IDabstract class, and theIDAllocatorclass, which are used to give standardized names to identifiers in the ASP parts. To avoid collisions, and due to the fact Clingo uses different naming constraints than PDDLSIM, a conversion is required, and is facilitated byIDAllocator. There are different kinds ofIDs, for the different meanings of identifiers used in the ASP parts (as well as identifiers for ASP variables).IDAllocators can then be created for a specific kind of identifier, storing a bidirectional mapping between theseIDs, and the value being converted, which is often a PDDLSIMIdentifier,Variable,Object, etc.
As an interface for the creation of ASP parts, it is important to note that ASPPart offers only limited functionality: it cannot be used to create all possible ASP programs, but rather only a subset of them, that is needed for PDDLSIM's GGA functionality. A more precise understanding of what ASP features are used can be obtained by reading ASPPart's code.
As mentioned above, the "objects" part is composed of two "subsections": one, which assigned each object and constant in the PDDL problem a type, and another, which describes the domain's type hierarchy, i.e., what types are subtypes of others.
As an example, assume we have types person, location, house - location, park - location. Likewise, assume we have the objects bob emily - person, bobs-house - house, and playground - park. The ASP part for these types and objects would then be:
% Object types
type0(object0). % bob - person
type0(object1). % emily - person
type1(object2). % bobs-house - house
type2(object3). % playground - park
% Type hierarchy
type3(O) :- type0(O). % person - object
type4(O) :- type1(O). % house - location
type4(O) :- type2(O). % park - location
type3(O) :- type4(O). % location - objectThe comments are of course added for readability, but the actual generated part wouldn't have them. Note how the program doesn't use any of the identifiers of the objects/types, as described above. Instead, we have a mapping, s.t., for example, type0 corresponds to person, type3 corresponds to object (which all types are a subtype of), object3 corresponds to playground, etc.
Thanks to the type hierarchy section of the part, we get other facts about the objects that are implied thanks to the type hierarchy, like type3(object0), meaning bob is also of type object.
The "simulation state" part is simply a list of facts corresponding to predicates that compose the current simulation state. Continuing on our previous example, assume the following predicates hold: at(bob, bobs-house), at(emily, playground), and full(playground). Therefore, our "simulation state" part would look like:
predicate0(object0, object2). % at(bob, bobs-house)
predciate0(object1, object3). % at(emily, playground)
predicate1(object3). % full(playground)It is important to note that the = "predicate" is actually considered to be a condition in PDDLSIM, and so doesn't appear in simulation states, and likewise here.
The "action definition" part, as described before, consists of three subsections: a set of ASP rules that define each parameter of the action as a rule with a single argument, describing the value of that parameter, a set of ASP rules that define the precondition of the action with respect to these parameters (and an integrity constraint to ensure all models of the ASP program satisfy the precondition), and finally a set of show rules, so that the models returned by Clingo only consist of the parameter atoms defined in the first section.
As an example, assume we have the action move, with parameters ?p - person, ?from - location and ?to - location. Likewise, assume that the action's precondition is: (and (at ?p ?from) (not (= ?from ?to))). With this, the "action definition" part would look like:
% Define the parameter rules, and require each parameter take on exactly on object
1 { variable0(O) : type0(O) } 1.
1 { variable1(O) : type4(O) } 1.
1 { variable2(O) : type4(O) } 1.
% Define the precondition
rule0 :- variable0(T0), variable1(T1), predicate0(T0, T1). % (at ?p ?from)
rule1 :- variable1(T0), variable2(T1), T0 = T1. % (= ?from ?to)
rule2 :- not rule1. % (not (= ?from ?to))
rule3 :- rule0, rule2. % (and (at ?p ?from) (not (= ?from ?to)))
:- not rule3. % Filter models that don't satisfy the full precondition
% Only show the parameter atoms
#show variable0/1.
#show variable1/1.
#show variable2/1.Note that of course the precondition section can be simplified, but as it is automatically generated in a very procedural way, it is not.
By combining all of these ASP parts, we have the following ASP program:
% Object types
type0(object0). % bob - person
type0(object1). % emily - person
type1(object2). % bobs-house - house
type2(object3). % playground - park
% Type hierarchy
type3(O) :- type0(O). % person - object
type4(O) :- type1(O). % house - location
type4(O) :- type2(O). % park - location
type3(O) :- type4(O). % location - object
predicate0(object0, object2). % at(bob, bobs-house)
predciate0(object1, object3). % at(emily, playground)
predicate1(object3). % full(playground)
% Define the parameter rules, and require each parameter take on exactly on object
1 { variable0(O) : type0(O) } 1.
1 { variable1(O) : type4(O) } 1.
1 { variable2(O) : type4(O) } 1.
% Define the precondition
rule0 :- variable0(T0), variable1(T1), predicate0(T0, T1). % (at ?p ?from)
rule1 :- variable1(T0), variable2(T1), T0 = T1. % (= ?from ?to)
rule2 :- not rule1. % (not (= ?from ?to))
rule3 :- rule0, rule2. % (and (at ?p ?from) (not (= ?from ?to)))
:- not rule3. % Filter models that don't satisfy the full precondition
% Only show the parameter atoms
#show variable0/1.
#show variable1/1.
#show variable2/1.After generating the ASP program, it is fed into Clingo in the Simulation._get_groundings method. Specifically, a clingo.Control object is created and configured, and then fed the program parts. After this. the ASP program is grounded, and then finally, solved, using _yield=True in order to receive the models generated by Clingo as a generator.
Once this generator is created, we iterate over each model in it, and go over all symbols (parameter atoms) in it. These are then converted into the groundings PDDLSIM expects for an action.
It is true there are other possible solutions to this problem, and that a bespoke solution would be faster. This is in fact an item on PDDLSIM's roadmap. Avoiding the database-theory-centric bespoke implementation described in the roadmap however, which would take a long time to build, and require FFI, we have identified several other solutions:
- Use brute-force and try all possible groundings for an action
- Implement a simple join-based GGA
- Use an external library, such as
unified-planning
Of course, using brute-force is slow. Very slow. For actions of enough parameters (5, 6, etc.), and in problems with enough objects, the state space to search can grow to hundreds of thousands of possibilities long, many of which are obviously impossible, but which still require checking. Adding types to the action parameters reduces the state space, but doesn't solve the fundamental problems of this approach. The final set of grounded actions returned may be small, but many options are considered in the process.
Before switching to ASP, GGA was actually implemented using a very simple join-based technique in pure Python. The issues with such an approach, are that there are generalization issues to broader classes of action preconditions than just conjunctions of non-ground predicates. For the case of a general precondition, the best approach is to simplify it to a sum-of-products (disjunction of conjunction of atoms), and for each "product" of that "sum" separately run a join-based GGA algorithm. Of course, due to negation in preconditions, the algorithm used must properly handle negative predicates, which proves to be problematic. In the most pathological case, negative predicates require universal quantification in order to find a set of valid grounded actions. Of course, ideally, no implementation would actually do this for cases where some of the variables of that quantification are already handled by other parts of the "product". This efficiency constraint therefore renders any good implementation of this approach impractical in terms of simplicity, as approaches must slowly become heavier and heavier with database-theoretic and boolean algebra concepts.
Finally, usage of an external library, such as unified-planning was at one point considered, but was eventually rejected due to the overhead of constant translation between that library's types and concepts to PDDLSIM's ones, as well as the fact that this places possibly harmful coupling on PDDLSIM's GGA functionality, making the addition of new types of actions/preconditions more difficult.
Therefore, to summarize, PDDLSIM uses Answer Set Programming, via Clingo, as a kind of stop-gap measure, as long as a faster solution doesn't prove itself necessary. Clingo is a highly optimized ASP solver, and has decent performance characteristics, making it well suited for small-to-medium instances of GGA, which happen to comprise the vast majority of GGA problems. ASP is naturally not the perfect solution, but when considering the triangle of flexibility, ease-of-understanding, and performance, we have found it to be a decent choice.