Towards a New Planning Domain Definition Language

[AdamSobieski]

This is a sketch of a new language for planning domains, problems, and solutions. This language is inspired by logic programming and by C, C++, C#, Java, and JavaScript. This language is not intended to be compiled but, instead, to be transpiled to a Semantic Web destination format, e.g., TriG.

By transpiling to a Semantic Web destination format, other new languages, e.g., one inspired by Python, can be similarly explored and created, transpiling to the same destination format, utilizing the same ontologies. In this way, multiple new planning domain definition languages can come to exist, alongside one another, solvers and planning algorithms consuming data from the destination format.

Defining Planning Domains

Predicates

This language supports first-class predicates and expressions.

using system;
using w3c.rdf;

namespace example
{
    public predicate foo<[world] ?w>(?x, ?y, ?z)
    {
        preconditions
        {
            holds(?w, { type(?x, Widget); });
            ...
        }
    }
}

Rules

This language supports first-class rules.

A logical equivalence rule could resemble:

using system;

namespace example
{
    public rule r123<[world] ?w>
    {
        forall ?x;
        forall ?y;
        forall ?z;

        consequent
        {
            holds(?w, { foo(?x, ?y, ?z); });
        }
        equivalent
        {
            ...
        }
    }
}

A first kind of logical implication rule could resemble:

using system;

namespace example
{
    public rule r123<[world] ?w>
    {
        forall ?x;
        forall ?y;
        forall ?z;

        consequent
        {
            holds(?w, { foo(?x, ?y, ?z); });
        }
        antecedent
        {
            ...
        }
    }
}

A second kind of logical implication rule could utilize a SPARQL-based language-integrated query { ... } construct:

using system;

namespace example
{
    public rule qr123<[world] ?w>
    {
        consequent
        {
            ...
        }
        query
        {
            ...
        }
    }
}

A third kind of logical implication rule could utilize SHACL-based shape constraints:

using system;

namespace example
{
    public rule shr123<[world] ?w>
    {
        consequent
        {
            ...
        }
        shape
        {
            ...
        }
    }
}

A fourth kind of logical implication rule could utilize JavaScript:

using system;
using w3c.rdf;

namespace example
{
    public rule jsr123
    <
        [auto][world][bind(*, system.world)]        ?w,
        [auto][bind(set::contains, system.self)]    ?set,
        [auto][bind(set::contains, system.element)] ?x
    >
    {
        preconditions
        {
            holds(?w, { type(?set, Set); });
        }
        consequent
        {
            holds(?w, { contains(?set, ?x); });
        }
        script
        {
            ...
        }
    }
}

Sets

This language supports first-class sets.

using system;

namespace example
{
    public set set123<[world] ?w, [self] ?s, [element] ?e>
    {
        contains
        {
            jsr123;
        }
    }
}

Knowledgebases

This language supports first-class knowledgebases, rules-enhanced collections of expressions.

using system;

namespace example
{
    public knowledgebase kb1<[self] ?s>
    {
        expressions
        {
            ...
        }
        rules
        {
            r123;
            ...
        }
    }
}

Queries

This language supports first-class queries. Queries could be utilized in some kinds of rules and could also be utilized as reusable language constructs outside of rules. Queries will support working with multiple local and remote knowledgebases. Queries will be nestable.

Language-integrated querying will probably be based on SPARQL/SPARUL and transpile using SPIN.

using system;

namespace example
{
    public query q123
    {
        ...
    }
}

Operators

This language supports first-class operators.

using system;
using system.agents;
using w3c.rdf;
using w3c.owl;

namespace example
{
    public operator move<[world] ?w>(?agent, ?from, ?to)
    {
        preconditions
        {
            holds(?w, {
                type(?agent, Agent);
                type(?from, Room);
                type(?to, Room);
                differentFrom(?from, ?to);
                location(?agent, ?from);
            });
        }
    
        effects
        {
            update(?w,
                remove({ location(?agent, ?from); }),
                add({ location(?agent, ?to); })
            );
        }
    }
}

Properties can be defined to exist on actions, instantiated operators, and accessor implementations can be provided, e.g., using JavaScript.

using system;
using system.agents;
using w3c.rdf;
using w3c.owl;

namespace example
{
    public operator move<[world] ?w>(?agent, ?from, ?to)
    {
        preconditions
        {
            holds(?w, {
                type(?agent, Agent);
                type(?from, Room);
                type(?to, Room);
                differentFrom(?from, ?to);
                location(?agent, ?from);
            });
        }

        properties
        {
            system.duration
            {
                get
                {
                    import { calculate_duration } from '...';

                    return calculate_duration(env['?w'], env['?agent'], env['?from'], env['?to']);
                }
            }
        }
    
        effects
        {
            update(?w,
                remove({ location(?agent, ?from); }),
                add({ location(?agent, ?to); })
            );
        }
    }
}

Classes

This language supports first-class classes or type definitions.

using system;
using w3c.rdf;

namespace example
{
    public class Widget<[world] ?w>
    {
        operator ctor()
        {
            effects
            {
                update(?w, {}, add(
                {
                    type(?this, ?self);
                    ...
                }));
            }
        }
    
        invariant
        {
            example.template1<?w, ?this, ?self>.r124;
            ...
        }

        operator dtor()
        {
            ...
        }
    }
}

Properties

This language might support first-class properties which extend binary predicates.

using system;
using w3c.rdf;

namespace example
{
    public property p<[world] ?w>([domain] ?d, [range] ?r)
    {
        preconditions
        {
            holds(?w, { type(?d, Room);
                        type(?r, Room); });
        }
    }
}

or

using system;
using w3c.rdf;

namespace example
{
    [property]
    public predicate p<[world] ?w>([domain] ?d, [range] ?r)
    {
        preconditions
        {
            holds(?w, { type(?d, Room);
                        type(?r, Room); });
        }
    }
}

Attributes

This language supports first-class attributes. Attribute definitions can augment or modify the transpilation output for attributed or decorated language constructs.

It remains to be determined whether the contents of constructs (e.g., sections, expressions, or rules) can be decorated, in particular if they are to be reified during transpilation.

In the following example, the attributes [world], [output], and [target] decorate the <> parameters so that they can, when omitted, be automatically bound to the correct arguments.

using system;
using w3c.rdf;
using w3c.rdfs;
using w3c.xsd;

namespace example
{
    public attribute comment<[world] ?w, [output] ?o, [target] ?t>(?content)
    {
        preconditions
        {
            holds(?w, { type(?content, string); });
        }

        effects
        {
            update(?o, {}, add({ w3c.rdfs.comment(?t, ?content); }));
        }
    }
}

Templates

This language supports first-class templates. Each language construct can be contained in a template. Templates can be nested.

using system;
using w3c.rdf;
using w3c.xsd;

namespace example
{
    [comment("This is a template.")]
    public template example_template<[world] ?tw, ?t>
    {
        preconditions
        {
            holds(?tw, { type(?t, nonNegativeInteger); });
        }

        content
        {
            [comment($"This is an operator with template argument {?t}.")]
            public operator example<[world] ?w>(?x, ?y)
            {
                preconditions
                {
                    holds(?w, { /* preconditions 1 */ });
    
                    if (holds(?tw, { ?t == 0; }) )
                    {
                        holds(?w, { /* preconditions 2 */ });
                    }
                    else
                    {
                        holds(?w, { /* preconditions 3 */ });
                    }

                    holds(?w, { /* preconditions 4 */ });
                }

                properties
                {
                    w3c.rdfs.comment
                    {
                        get
                        {
                            return $"This is an action with template argument {?t} and arguments {?x} and {?y}.";
                        }
                    }
                }

                effects
                {
                    if (holds(?tw, { ?t == 0; }))
                    {
                        ...
                    }
                    else
                    {
                        ...
                    }
                }
            }
        }
    }
}

Example JavaScript for accessing and utilizing the above content to create an action instance might resemble:

var action = domain.get('example_template').template(kb, 0).get('example').template(world).instantiate(x, y);

Due to the expressiveness provided by first-class templates, both generic programming and dependent types are relevant.

Scripting

This language supports scripting, e.g., with JavaScript.

using system;

namespace example
{
    [language("text/javascript")]
    public script s123
    {
        source <https://www.example.org/scripts/s123.js>;
    }
}

Notes

URI Mappings

Using the attribute/decorator system described above, a goal is that this language can express mappings to and from existing Semantic Web schemas and ontologies, e.g., [uri(<...>)]. One possiblity, in these regards, is simply utilizing owl:sameAs.

There are multiple methodologies for obtaining URIs for language constructs. These will be useful for scenarios including transpiling expressions like: type(?x, example_template<123>.Widget).

And/or Scope Brackets

Nestable and/or brackets, e.g., and { ... }, or { ... }, and and { ... or { ... } ... }, could be language features.

using system;

namespace example
{
    public set set123<[world] ?w, [self] ?s, [element] ?e>
    {
        contains
        {
            or
            {
                and
                {
                    jsr123;
                    jsr124;
                }
                and
                {
                    jsr125;
                    jsr126;
                }
            }
        }
    }
}

Parameterization

Can utilize the <> brackets on arbitrary language constructs, e.g., rules, for declaring parameters. Each construct, then, should also be able to have a preconditions section for declaring constraints on these parameters.

Utilizing an attribute-based parameter modification system, e.g., [world], for describing explicit world parameters, as shown throughout the examples. These special attributes modify <> parameters so that they can, when omitted, be automatically bound to the correct arguments. Examples of these special attributes include: [world], [self], [element], [this], [target], [output], [domain], [range], [solver], and [state].

Decorators, Scopes, Binding, and Rules

It is noteworthy that, by utilizing binding-related decorators on the example rule definition, we can safely omit the <> arguments when utilizing rules in the set definition context:

using system;
using w3c.rdf;

namespace example
{
    public rule jsr123
    <
        [auto][world][bind(*, system.world)]        ?w,
        [auto][bind(set::contains, system.self)]    ?set,
        [auto][bind(set::contains, system.element)] ?x
    >
    {
        preconditions
        {
            holds(?w, { type(?set, Set); });
        }
        consequent
        {
            holds(?w, { contains(?set, ?x); });
        }
        script
        {
            ...
        }
    }
}

using system;

namespace example
{
    public set set123<[world] ?w, [self] ?s, [element] ?e>
    {
        contains
        {
            or
            {
                and
                {
                    jsr123;
                    jsr124;
                }
                and
                {
                    jsr125;
                    jsr126;
                }
            }
        }
    }
}

For reduced typing, [world] could be defined as having those semantics of [auto][world][bind(*, system.world)].

Interestingly, could utilize first-class resuable rules in binding-related metadata.

using system;
using w3c.rdf;

namespace example
{
    public rule pmr1<[world] ?w>
    {
        ...
    }

    public rule pmr2<[world] ?w>
    {
        ...
    }

    public rule pmr3<[world] ?w>
    {
        ...
    }

    public rule jsr123
    <
        [auto][world][bind(*, pmr1)]      ?w,
        [auto][bind(set::contains, pmr2)] ?set,
        [auto][bind(set::contains, pmr3)] ?x
    >
    {
        preconditions
        {
            holds(?w, { type(?set, Set); });
        }
        consequent
        {
            holds(?w, { contains(?set, ?x); });
        }
        script
        {
            ...
        }
    }
}

Templated Strings and URIs

A desired feature is to be able to utilize templated strings, $"...", and templated URIs, $<...>.

Object-oriented Logic Programming

Logtalk is a useful reference material with respect to object-oriented logic programming.

Inheritance

There should be support for inheritance scenarios for at least the language constructs of class and property.

Modularity

This language will support multi-file modularity, the project structures of modern integrated development environments, and interoperation with Web-based resources. Digitally-signed compressed archives, e.g., OCF, could be of use for bundling modular planning domains and resources together.

Reification

A predicate can be described as a function which accepts as input a sequence of arguments (which meet preconditions) and outputs an element of a predicate-specific set of expressions. Each predicate-specific set of expressions is a subset of the set of all expressions. The set of all expressions could be related to the set rdf:Statement.

The indicated approach allows for a strongly typed, preconditions capable, predicate calculus model which supports reification and nestable expressions, e.g., foo(thing_1, thing_2, baz(thing_3)).

Forms of Rules

Utilizing a special builtin unary predicate, e.g., isvalid(?plan), isvalid(?self), or isvalid(?this), rules could be utilized for defining class invariants, plan preferences, and plan constraints.

It appears that there are forms of rules. As just mentioned, one form of rule uses holds(?world, { isvalid(?x); }); and another form of rule uses holds(?world, { contains(?set, ?element); });. Might these special forms of rules inherit from or extend a base form of rule resembling how property could inherit from or extend predicate?

Metalanguage and Metaprogramming

This language should provide the expressiveness for developers to be able to define new language constructs utilizing metalanguage and metaprogramming.

The property construct, for instance, resembles a binary predicate and adds the contextual keywords of ?domain and ?range. Similarly, the construct class could be defined by extending set.

This language intends to provide developers with metalanguage and metaprogramming features while simultaneously providing expressiveness for specifying transpilation outputs for new constructs. This could be accomplished by means of using attributes and decorators.

For most scenarios pertaining to the modeling of planning domains, problems, and solutions, developers could access and utilize those language constructs, described above, by means of typing using system;. For more advanced scenarios, developers could, instead or in addition, use metalanguage and metaprogramming capabilities to define their own first-class language constructs.

Sets, Concepts, and Categories

First-class sets could contain sections with which to define their indicator functions, membership functions, intensional definitions, or semantic descriptions.

Complex sets', concepts', or categories' definitions could, for instance, involve the utilization of one or more local or remote knowledgebases and, thus, the processing and combination of multiple implication-based, query-based, or scripting-based rules.

There are also to consider the computer-lexical definitions of abstract concepts and of concepts which might vary contextually. Concepts, sets, and categories can be considered with definitions involving systems' or intelligent agents' contexts, states, beliefs, desires, or intentions as arguments.

Modeling and Reasoning about Plans

Plans can be more than sequences of actions, they can resemble workflow or business process diagrams, containing, for instance, control flow constructs.

A plan ontology could enable more complex preferences and constraints to be be defined utilizing rules and queries.

Machine Ethics

Machine ethics is a part of the ethics of artificial intelligence concerned with adding or ensuring moral behaviors of man-made machines that use artificial intelligence, otherwise known as artificial intelligent agents. The capability for intelligent agents to reason about plans, stories, and other descriptions of activities and behavior, and abstractions thereof, could be useful for approaches to machine ethics.

Natural-language Processing

Natural-language processing scenarios will be supported by this language.

Natural-language Generation

Natural-language generation scenarios will be supported by this language.

In a simplification, planners could be provided with an input knowledgebase for contents to be said and an output knowledgebase, initially empty, for contents already said. The goal state, in this simplification, could be described as having an empty to-be-said knowledgebase and a filled already-said knowledgebase. The planning domain would include a large set of operators which produce natural language while moving contents from the one knowledgebase to the other.

More advanced models and approaches might include additional knowledgebases for: context-related data, models of the speaker, models of the intended audience, and stylistic and sentiment-related hints with which to vary the natural-language output. These hints pertaining to how to say portions of content could also be placed alongside those contents to be said.

Language-design topics include ensuring the capability for developers to create multi-stage pipelines which migrate contents through a series of intermediate representations en route to natural-language output. Per the macro-planning (a.k.a. document planning) and micro-planning stages of natural-language generation, contents to be said might, initially, be stored in one large set, one large knowledgebase, and, subsequently, stored in a sequence of sets, each then smaller set representing the contents of a to-be-said section, paragraph, or sentence. Contents to be said could also be subsequently formulated into a hierarchical document outline, with each section and subsection potentially adorned with metadata such as intentions, objectives, or questions to be answered in generated text.

Language-design topics also include ensuring the capability for developers to create anytime algorithms for story and natural-language generation. Anytime algorithms are algorithms which produce initial solutions and which are expected to produce increasingly better solutions when provided with more computing time. In writing, the process of working with existing solutions and improving upon them is called revision.

Story Generation

Story generation scenarios will be supported by this language.

Story generation, abstractly, can be described as containing three stages or components: fabula generation (determining what happens in a story), syuzhet generation (determining how the story is told), and text rendering (generating the natural language).

External Components for Metrics, Scoring, and Evaluation

This language will support solvers' utilization of external components for the multicriteria evaluation of potential plans and outputs, in particular natural-language and story outputs.

Debugging and Tracing

The transpiling process and related ontologies should support the capability of attaching references to selections of source code files to transpiler output.

Ontologies for debugging, provenance, tracing, event logs, narrative, and process mining could be useful for supporting software development and debugging scenarios. These technologies under discussion could be additionally useful for training developers who are new to projects, providing them with interactive means of learning about projects' codebases, models, domains, data, and functionalities.

When automated planning solvers are utilized to produce outputs, e.g., natural-language generation and story generation, developers could be provided with means of navigating from selections of output content to relevant explanations of computational processes and to relevant highlighted selections of source code, models, domains, and data. Towards enabling these scenarios, natural-language and story outputs could be hypertext documents instead of text strings.

Other Features

Other features could result from brainstorming with syntactic options including: ${...}, %{...}, @{...}, {{...}}, and {(...)}. For example, %{...} could be utilized to indicate a scope for probabilistic language constructs and content.

[miquelramirez]

Hello @AdamSobieski,

very interesting, if daunting. I have got some questions for you below:

• How do the different constructs map onto PDDL 2.x? Some correspondences are obvious (e.g. rules and axioms/derived predicates). Others are not (e.g. the notion of "predicate" above is actually a logic meta-language statement like "world w satisfies first-order formula").
• What is the value of having knowledge bases when one has already domains?
• What is the rationale for having 'classes'? Are they meant to contain just unary predicates and functions (that map an instance/object to the class to a particular value)?
• What is exactly a "query"?

What would be very valuable at this stage is to see a simple PPI (like the instance 4-1 from the classic Blocks World IPC domain) implemented with this language.

[AdamSobieski]

Hello @miquelramirez,

How do the different constructs map onto PDDL 2.x?

In the sketch, the constructs are intended to transpile to Semantic Web datasets. Some of the constructs are inspired from PDDL, and others are offered as new ideas and conveniences.

The notion of "predicate" above is actually a logic meta-language statement like "world w satisfies first-order formula"

My thinking with the capability for multiple worlds, multiple knowledgebases, and using template parameters, was that we could provide more expressiveness than a type-strong predicate calculus system. We could specify relations that must hold for collections of input parameters to predicates for expressions to be valid.

What is the value of having knowledge bases when one has already domains?

I’m thinking about “multi-knowledgebase scenarios”, that operators could describe preconditions and effects utilizing multiple kbs, simultaneously, that kbs could be reified objects which operators could operate upon. So, an operator could receive an input parameter for a knowledgebase, ?kb, and utilize it wherever the world template parameter, e.g., ?w, is utilized in the examples, e.g., holds and update.

What is the rationale for having 'classes'? Are they meant to contain just unary predicates and functions (that map an instance/object to the class to a particular value)?

These could map to the types from PDDL. Additionally, these could have constructors and destructors as operators on them which could be useful when initializing or de-initializing problem instances.

What is exactly a "query"?

SPARQL has different kinds of queries: “ask”, “construct”, “describe”, and “select”. I’m thinking about functions which return Boolean results about the contents of one or more knowledgebases (the “ask” variety of query).

What would be very valuable at this stage is to see a simple PPI (like the instance 4-1 from the classic Blocks World IPC domain) implemented with this language.

Good idea! I found the IPC domains (e.g., https://github.com/potassco/pddl-instances/blob/master/ipc-2000/domains/blocks-strips-typed/domain.pddl).

Here is a preliminary, rough-draft, sketch of the Blocks World domain:

using system;
using w3c.rdf;
using w3c.owl;

namespace Blocks
{
    public class Block : Thing { }

    public predicate on<[world] ?w>(?x, ?y)
    {
        preconditions
        {
            holds(?w, { type(?x, Block); type(?y, Block); differentFrom(?x, ?y); });
        }
    }

    public predicate ontable<[world] ?w>(?x)
    {
        preconditions
        {
            holds(?w, { type(?x, Block); });
        }
    }

    public predicate clear<[world] ?w>(?x)
    {
        preconditions
        {
            holds(?w, { type(?x, Block); });
        }
    }

    public predicate handempty<[world ?w]>();

    public predicate holding<[world ?w]>(?x)
    {
        preconditions
        {
            holds(?w, { type(?x, Block); });
        }
    }

    public operator pickup<[world] ?w>(?x)
    {
        preconditions
        {
            holds(?w, { clear(?x); ontable(?x); handempty(); });
        }
        effects
        {
            update(?w, add({ holding(?x); }),
                    remove({ ontable(?x); clear(?x); handempty(); }));
        }
    }

    public operator putdown<[world] ?w>(?x)
    {
        preconditions
        {
            holds(?w, { holding(?x); });
        }
        effects
        {
            update(?w, add({ clear(?x); handempty(); ontable(?x); }),
                    remove({ holding(?x); }));
        }
    }

    public operator stack<[world] ?w>(?x, ?y)
    {
        preconditions
        {
            holds(?w, { holding(?x); clear(?y); });
        }
        effects
        {
            update(?w, add({ clear(?x); handempty(); on(?x, ?y); }),
                    remove({ holding(?x); clear(?y); }));
        }
    }

    public operator unstack<[world] ?w>(?x, ?y)
    {
        preconditions
        {
            holds(?w, { on(?x, ?y); clear(?x); handempty(); });
        }
        effects
        {
            update(?w, add({ holding(?x); clear(?y); }),
                    remove({ clear(?x); handempty(); on(?x, y?); }));
        }
    }
}

[AdamSobieski]

@miquelramirez, throughout the examples above, one can observe that the predicates in the preconditions and effects are defined with <[world] ?w> and then utilized without any <> arguments. What the [world] attributes on the ?w parameters (and similar attributes on other construct parameters) are doing resembles the proposed C# implicit keyword which intends to convenience developers and to reduce typing. I’m hoping to deliver all of the benefits of template arguments for developers without them having to manually type all of the template arguments which can be inferred in scopes and contexts. Other approaches include, but are not limited to, per-construct contextual keywords, where world would be a keyword instead of developers declaring and then using template parameters like ?w.

Also, as the envisioned language transpiles to the Semantic Web format of TriG, the forthcoming tasks are twofold. Firstly, to design the ontologies that this language transpiles into. Secondly, to design the language, maximizing readability and convenience.

It's a preliminary sketch. Comments, feedback, and ideas are welcomed!