Did you know ... Search Documentation:
Pack flux -- prolog/README

ALPprolog --- Action Logic Programs in Propositional Logic

Website: http://alpprolog.sourceforge.net

Status: Stable

Developer: conrad.drescher@web.de

ALPprolog is a Prolog implementation of an action programming language.

It requires ECLiPSe Prolog (available at http://www.eclipse-clp.org).

It implements a fragment of the theoretical framework of Action Logic Programs as described in

http://www.computational-logic.org/content/projects/wisslogpubs/DreSchiThi-FroCoS09.pdf

Overview

The fragment can be characterized as follows:

  • States are built from ground fluent (i.e. mutable) and non-fluent (also called auxiliary) properties using the logical connectives "and", "or", and "not". We assume that there are only finitely many objects in the domain and make a domain closure assumption. Hence states are a notational variant of classical propositional logic.
  • An ALPprolog program describes the strategy of an agent that executes the program online. Hence only simple substitutions are used for evaluating queries like e.g. ?- holds(safe(Cell)). In the offline setting reasoning by cases via disjunctive substitutions ensures that the Action Logic Program framework becomes logically complete.
  • The agent can execute two kinds of actions: Physical actions that affect the environment, and sensing actions that only affect the agent's knowledge thereof. Sensing actions may result in disjunctive information --- e.g. one of the surrounding cells might be safe, but it might not be clear which one. Physical actions are assumed to be deterministic, i.e. there are no disjunctive effects.

    World descriptions with ALPprolog

    With ALPprolog you can program strategies for autonomous agents in dynamic domains. ALPprolog programs are ordinary Prolog programs with two additional predicates:

  • holds/1 to test whether some state property holds currently
  • execute/1 to execute some action An ALP describing a breadth first naive planning strategy is the following:

    strategy :- holds(goal). strategy :- do(A), strategy.

    In words if the goal description is satisfied at the current state then the strategy was successful. Otherwise we randomly pick some action A and keep on searching. As one can see ALP programs are read as temporally ordered sequences from left to right.

    Required Files **

    The overall structure of an ALPprolog domain is as follows:

    (1) Create a module world.ecl --- describing the dynamic domain (2) Import this module into alpprolog.ecl (3) Create a file strategy.ecl importing world.ecl and alpprolog.ecl

    For illustration purposes with this distribution comes an implementation of the Wumpus world with the respective files wumpus_world.ecl and wumpus_strategy.ecl. Below is a brief explanation of the language features and their use.

    Sample Domain - Wumpus world **

    Let us first recall the wumpus world: The wumpus world is a well-known challenge problem in the reasoning about action community. It consists of a grid-like world: cells may contain pits, one cell contains gold, and one the fearsome Wumpus. The agent dies if she enters a cell containing a pit or the Wumpus. But she carries one arrow so that she can shoot the Wumpus from an adjacent cell. If the agent is next to a cell contain- ing a pit (the Wumpus), she can detect that one of the surrounding cells contains a pit (the Wumpus), but doesn't know which one: She perceives a breeze if she is in a cell next to a pit, and she perceives a stench if she is in a cell next to the Wumpus. She knows the contents of the already visited cells --- in particular she can detect the gold if she is in the same cell. Getting the gold without getting killed is the agent's goal.

    world.ecl: **

    A world description is composed as follows:

  • Describe the initial state as a ground formula in prime implicate form: A formula in conjunctive normal form is in prime implicate form iff it is closed under resolution, subsumption, and tautology deletion. This should be included as a Prolog fact: E.g.

    inital_state([at(agent,1),[at(wumpus,2),wumpus(3)]]).

    This Prolog fact describes the initial state

    at(agent,1) /\ ( at(wumpus,2) \/ at(wumpus,3) )

    We know where the agent is, but the exact location of the fearsome wumpus is unknown. This initial state talks about "fluents": These are the mutable properties of the dynamic domain. Formulas describing states are Prolog lists. If a list element is a term it is a singleton clause, if it is a list it is a disjunctive clause. A negated fluent is e.g. neg(alive(wumpus)).

  • Describe the actions, using action/3 facts. E.g. the fact
    action(shoot, [carries(agent,arrow), at(wumpus,Cell1), at(agent,Cell2), connected(Cell2,Cell1)], [neg(carries(agent,arrow)), neg(alive(wumpus))]).

    has the following meaning: The action "shoot" is possible if the agent is currently armed, and next to a cell containing the wumpus. Finally, the effects of the action are that the agent is no longer armed, and that the wumpus gets killed.

  • You can define as many additional auxiliary static properties of the domain as you like using Prolog clauses. These have to be listed in a fact

    aux([connected]).

    so that they can be distinguished from fluent properties (the default).

  • If the dynamic domain includes sensing then you have to first list the respective predicates, e.g.

    sensors([glitter,stench]).

    Describing sensor axioms is a little complicated. The meaning of an observation depends both upon the sensing result and the agent's current state. For example, the meaning of sensing whether an adjacent cell contains gold depends both on the observation (Yes/No) and the agent's current location. This is the sensor axiom for the wumpus agent that is trying to sense whether there is gold:

    sensor_axiom(glitter(X),[ [X-true] - [at(agent,Y)] - [at(gold,Y)],
    [X-false] - [at(agent,Y)]- [neg(at(gold,Y))] ]).

    This sensor has just two possible sensor values, true and false. The meaning of the sensing result depends on the agents current location at(agent,Y). If e.g. the sensing result was true then at(gold,Y) is adjoined to the current state description. If the meaning of the sensor result does not depend on the current state then the empty list may be used. In general, the meaning may be described by any formula in prime implicate form. Variables may be used provided that these can approriately grounded by evaluating the state condition against the agent's current state knowledge. A sensing action is performed simply by evaluating a non-ground sensed property.

    For sensing to work in simulation you also have to provide a predicate real_world/1. This is used by alpprolog.ecl to determine the appropriate sensing results.

    strategy.ecl: **

    A strategy is an arbitrary Prolog program, using the special predicates holds/1 and execute/1. See wumpus_strategy.ecl for an example.

    A Guide to the Distribution **

    The directory 'ALPprolog' contains the files

  • wumpus_strategy.ecl
  • wumpus_world_small.ecl
  • wumpus_world_big.ecl
  • alpprolog.ecl Compile 'wumpus_strategy.ecl' and call 'main'. You can choose a world size in the files 'wumpus_world_*.ecl' (from 4x4 to 32x32).

    The 'small' world contains fewer ground fluents in the agents state representation, and the 'bigger' one contains much more (allow some time for compilation).

    If you want to use 'big' instead of 'small' adapt both 'wumpus_strategy.ecl' and 'alpprolog.ecl'.

    The subdirectory 'FluxVersion' contains two subdirectories, 'Ground' and 'Nonground'. 'Ground' is essentially the same as 'ALPprolog', only using Flux for the reasoning instead. Again, if you want to use 'big' instead of 'small' adapt both 'wumpus_strategy.ecl' and 'flux.ecl'.

    'Nonground' uses quantification over variables to keep the state representation small, and is much more efficient. Compile 'wumpus.pl' and call 'main'. You can choose a world size in 'wumpus.pl'.