Bakasp

Web service generator for ASP-based constraint solving.

usage:

• write the ASP backend
• get your users to provide their preferences
• watch the valid models.

Example

Let's imagine a web service to assign one of four characters to each of four players of a tabletop RPG.

Input base encoding:

1{ play(H, P): charc(P), ok(H,P) } 1 :- human(H).
1{ play(H, P): human(H), ok(H,P) } 1 :- charc(P).

Note that ok/2 atoms are expected for the program to behave normally, as well as charc/1 and human/1. They will all be derived from the configuration and user's input.

Here is a minimal working configuration, using that base encoding and providing informations on input data and website behavior:

{
    "base encoding": "1{ play(H, P): charc(P), ok(H,P) } 1 :- human(H). 1{ play(H, P): human(H), ok(H,P) } 1 :- charc(P).",
    "shows": "play/2",

    "users options": {
        "type": "restricted",
        "allowed": ["Pierre", "David", "Noémie", "Noa"]
    },
    "choices options": {
        "type": "multiple",
        "choices": ["Méléas", "Éléa", "Haringer", "Ina"],
        "data atoms": [
            "human({user})",
            "charc({choice})"
        ],
        "produced atoms": "ok({user},{choice})"
    }
}

By running python poc.py that-config.json, you will be serving an autogenerated website, allowing specific users to provide their choices, and to see the stable models. In that particular instance, each of the four user will be able to tell which character(s) she is wanting to play, so each model will describe a combination of human/character that fullfill everyone's wishes. If any exists.

Pages

The following pages constitute the web service interface, automatically generated from your configuration.

/

The index contains a description, and link to other pages.

/user

Allow for user to select its name.

/user/

Allow for user to indicate its choice(s).

/compilation

If configuration said so, it's the access to that page that provoke the compilation of models.

/results

The representation of given models.

/history

The list of changes and their influence on models.

/overview

The current choices of all users.

/configuration

Access to the full json configuration, if allowed by the said configuration.

/configuration/raw

Access to the input json configuration, if allowed by the said configuration.

More examples

See the examples/ directory, containing, among others:

• a team maker config, where users indicate who they want in their team, and N teams of equal number of players are formed, trying to content a maximum of peoples.
• a score-balanced team maker config, typically useful in laser tag, when you need, knowing the score of each participant, to equilibrate the teams compositions.
• a pairing config, where each user is to indicate characters he wants to play ; output is the pairing user/character allowed by constraints.
• a output control demo config, showing the capabilities of the model representation plugin system.
• a malformed config, just for you to see how not write your own, or to see how the program behave in presence of such mistypes.

Options

Global options

location

The base URL path to add before all system paths.

By default, at root, i.e. "/".

base encoding

The base ASP encoding that will be augmented with other atoms and shows described by the other options.

shows

List of atoms (or a string containing one atom and its arity) to #show, meaning those that will be shown in the output page.

engine

Future option that will allow to use other flavors of ASP, or other languages. Currently, the only valid value is not set, or ASP/clingo.

compilation

Must be one of direct access, specific access.

With direct access, the compilation of the models is performed each time the /results page is loaded, before the loading.

With specific access, the compilation of the models is performed each time the /compilation page is loaded.

generated pages

A list of string being the pages to be generated. Defaults to all pages, meaning: ["user", "overview", "compilation", "configuration"].

public pages

A list of string being the pages to be shown in the main page. If a page is shown but not generated, an error should be raised at website compilation.

Defaults to None, meaning equivalence with generated page option.

raise warnings

Defaults to true. If false, doesn't indicate possible discrepancies in the configuration file at website-compilation time.

raise errors

Defaults to true. If false, doesn't fail on malformed configuration file at website-compilation time.

template

The template name to use. Must be a directory in templates/ dir, containing the template html files.

Users options

type

Must be one of restricted, valid-id or convertible.

With restricted, allowed users field is expected to be a dict or list.

With valid-id, allowed users field is expected to be none or empty.

With convertible, allowed users field is expected to be a pure python function taking the user string as input, and returning its uid.

allowed

Must be a dict, linking human representation of user uid to its (unique) ASP representation, or a list, when human and ASP representations are equivalent for all choices.

If the user type is not restricted, that option is to be left blank or non-provided.

Choices options

default

By default, the user is generated with these combinations.

May be "all", none, empty list, or a list of choices (if choice type allows for many choices to be made).

If the given default choice is not compatible with the choice type (e.g. a list for a single choice), errors will be raised.

type

May be one of single, multiple, at least 1, at least <N> (with N an integer > 0), at most <K> (with K an integer > 1), or <N> to <K>.

Obviously, 1 to 1 is equivalent to single. Finally, 0 or 1 is a valid, more explicit alias to at most 1.

choices

Must be a dict, linking human representation of choice to its (unique) ASP representation, or a list, when human and ASP representations are equivalent for all choices.

produced atoms

These atoms are produced for each user, depending of made choices.

data atoms

Data atoms are other atoms produced from the input and choices, but, in opposition to produced atoms, they are all produced, at website compilation time, from all possible {user} and {choice} values.

They are useful to specify the user and choices entities only once, in the configuration, without having to write them explicitely in the base encoding.

Output options

max models

Integer, zero or more, describing the maximal number of models the output page will show. If set to zero, there is no limit to the number of models shown on output page.

See model selection option for controlling which models are shown.

model selection

This options only takes effect when the total number of models exceed the max limit set by max models option.

if this option is set to first, #max models models output by the solver are taken (with clingo, it's implemented by sending the -n N option).

if this option is set to sampling, #max models models are randomly drafted from the set of all models.

model repr

This option allows to finely control how each model is rendered on the output page.

The very basic value for it is "standard". Now, there is other possibilities.

Appart for the special value standard, this option must be a list, where each item is a dict. And each dict must provide a kind key, providing a string being the name of a valid model representation plugin.

See ModelReprPlugin subclasses, the configuration example trying to show all capabilities of that option and the following example of valid value for model repr:

"output options": {
    "model header repr": [
        {
            "kind": "title",
            "index": true,
            "uid": true
        }
    ],
    "model footer repr": [
        {
            "kind": "raw",
            "shows": "all"
        },
        {
            "kind": "table/2",
            "rows": "user",
            "columns": ["blue", "red"],
            "source": "team/columns,rows",
            "caption": "Show in which team (blue or red) is each user."
        },
    ],
    "header repr": [
        {"text": "This is shown before the {len(models)} models list"},
        {
            "kind": "table/2",
            "rows": "user",
            "columns": "choice",
            "source": "choice/row,columns",
            "caption": "Each row indicates which users a particular user wanted to have in its team."
        }
    ],
    "footer repr": [
        {"text": "This is shown after the models list (which took {runtime_compilation_repr} to compile)"},
    ]
}

# (note that header and footer are also configurable using the same constructions)

This model representation is broken in three parts:

• a title, that will show the solution index and its uid
• a raw list of (all) atoms
• a binary table in two dimensions, where rows are users, 2 columns blue and red, and relationships between rows and columns are given by team/2 atoms, with the first arg being the column, and the second the row. Hence, team(1,2) will indicate that user 2 is associated to blue (considering the second team is numbered 2).

The default representation, standard, looks like this :

"output options": {
    "model header repr": [
        {"kind": "title", "index": True, "uid": True },
    ],
    "model footer repr": [
        {"kind": "raw", "shows": "all" },
        {"kind": "table/2", "rows": "user", "columns": "choice", "source": "assoc/rows,columns" },
    ],
    "header repr": [
        {"kind": "text", "text": "{nb_models} models found in {compilation_runtime_repr}."}
    ],
    "footer repr": [
        {"kind": "text", "text": "{('All solutions share '+str(len(common_atoms.atoms))+'atoms.') if common_atoms.atoms else 'There is no common atoms across solutions.'}"}
    ]
}

You may introduce new plugins in their directory, and use them in your configuration file.

insatisfiability message

Defaults to "that program is unsatisfiable".

Overview options

The overview page indicates all current selected data.

public

Default to true. If false, the overview page URL is not indicated in main page.

type

Type(s) of overview. Possible values are: raw, table.

Multiple may be given, as a list.

Default to raw and table.

Configuration options

This json data is the configuration itself.

No option for the moment.

Main page options

title

String that will be set as h1 title in the main page.

description

String going just under the title, and before all technical links.

ROADMAP

Basic features

• configuration is loaded from file, and default values are added if necessary
• add options in the config
  • support of numbered choice types
  • support it in the UI too: https://www.plus2net.com/javascript_tutorial/checkbox-limit.php
  • support for sampling
• don't recompile the models if nothing changed
• website is running and all pages are accessible
• show a working website, with working forms
• working example use case
• table representation of rel/2-types models
• have templates/ dir, where multiple templates can live. Allow each configuration file to specify the template to use
• examples
  • choose your character, a simple one-to-one pairing with binary preferences.

doable in less than a day

• doc for newcomers
• doc for non technical users
• in restricted user mode, allow to only provide user names. Uid can be decided internally. Same goes for choices.
• when choices are presented, widget are in the state representing current choices (meaning, checkboxes are checked).
• provide ASP base encoding in a file, as a filepath, instead of being inlined (thus unreadable) in the json.
• choices must be described by a text set in configuration
• allow for saving current sever state, so it can be stopped and restarted without data loss
• provide to each model a unique, human-readable identifier that allows to reference it, even if model order is changed, or if models are removed or added after choices changes. (done with hashname module, based on a sorted view of clyngor models)
• each model has a copy2clipboard button, to easily share their result in the most sensible way.
• allow users to get the list of new and lost models their preferences created. (an history page, saying «USER changed its preferences, leading to N new models and L lost models»)
• implement other choices types
  • ranking, an order of proposition
  • independant ranking, to implement the majority judgment (many proposition may have the same rank)
• implement other model representations
  • majority judgment
• plugin system for asp models -> html repr
• implement funny plugins
  • biseau
  • matplotlib
  • stats over all models
• examples
  • make balanced teams, allowing each user to select other users he wants to be with.
  • make balanced teams, grouping users depending of their personal score, trying to get N teams of same score. (laser tag example)
  • choose your character, a one-to-one pairing with ranked preferences.
  • choose your character among many, a maybe-to-one pairing with ranked preferences, and group optimization based on roles.
  • restaurant choice based on ranks (majority judgment demo)
  • organize a tabletop game evening (game & dishes preferences)
• Bakasp As A Service: enable one app to run many configurations, enable to create ones, etc.

Needs a good amount of work

• multiple choices scheme: users may have to prodive multiple informations for a single service to behave correctly. This needs a complete rethink of how to handle forms and output atoms.

  • a first approach: choice become in json config a list of choices, asked one by one to the user.

• support for python instead of ASP

  • function taking atoms (in json format?) as input, yielding atoms (in json format?) as output
  • function taking atoms (in json format?) as input, yielding html representation

• allow a model to be debuggable (automatically) with SPOCK method

• when unsatisfiable, propose degraded models where one (randomly chosen ?) constraint is ignored.

• plugin system for other parts of the soft ? forms maybe ?

• implement other model representations

  • when multiple metrics are used, show the solutions in a pareto front (Without using asprin ; pareto front computation is made by hand, without minimizations and maximizations)

• examples

  • carpooling for lunch (multiple cars, multiple restaurants, each human has its preferences of restaurants, not all have a car, trying to minimize the number of used car -> may need an exploration of paretto front)
  • placement of peoples for dinner (needs complex forms)

• roover: an high-level DSL to define ASP search space.