KELPS

From RuleML Wiki
Jump to: navigation, search

KELPS[1][2] (Kernel of LPS) is the LPS core language including the reactive rules a simple domain theory and reducing the logic program (the knowledge of the agent) to a set of atoms.

1 Vocabulary and Meta-predicates

KELPS uses a sorted language in which constants and variables are assigned sorts. The argument places of function symbols and predicate symbols are correspondingly assigned sorts, so that formulas are well-formed only if the argument places are filled by terms of the allowed sort.

  • Predicate symbols are partitioned into (disjoint) sets representing fluent predicates, event predicates, auxiliary predicates and meta-predicates:
    • Fluent predicate symbols are extensional predicates, used to represent facts in the database of states.
    • Event predicates symbols are used to define atomic events (simple events). Atomic events can represent either externally generated events (environment events) or internally generated actions.
    • Auxiliary predicate symbols consist of builtin predicates that do not vary with time, such as max and min and others used for arithmetic (inequality, arithmetic equality, ...)
    • KELPS uses two meta-predicates: initiates and terminates. Fluents and events occur as terms when they are arguments of the meta-predicates.
      • initiates(E,R) - The occurence of event E initiates the fluent R.
      • terminates(E,R) - The occurence of event E terminates the fluent R .

1.1 Note on Implementation

  • A basic KELPS implementation would use sort, function, predicate, fluent as reserved words for vocabulary declarations, string, integer, float, symbol as basic sorts, initiates, terminates, consult, assert, retract, retractall, findall, ... as builtin predicates, usual comparison operators, <, ≤, =, !=, ≥, > usual arithmetic operators +, -, *, mod, div.

2 The Environment

KELPS language does not define symbols to explicitely define states and events. States are implicitely defined by the set of all extensional facts that are true at the time i; events are implicitely represented by the set of all atomic events that occur from time i-1 to i.

3 Auxiliary predicates

Arithmetic inequality and equality used in time constraints e.g., T1 ≤ T2, T+3 > T1

3.1 Note on Implementation

  • An implementation should come with an easy plugin architecture allowing for external builtin predicate libraries.

4 Causal theory

KELPS causal theory C = C_pre ∪ C_post is defined as in AI action theories, such as the event calculus but without frame axioms.

  • C_pre is a set of integrity constraints of the form ∀ X [antecedent(X) → false]. They are used to restrict the occurrence

and co-occurrence of sets of simple events. For example:

<!-- the system cannot ''dispatch''(the atomic action) the same Item to two different customers -->
dispatch(Cust1, Item, T) ∧ dispatch(Cust2, Item, T) ∧ Cust1 ≠ Cust2 → false

<!-- John cannot leave the house without taking the keys -->
leaveHouse(john, T) ∧ ¬ takeKeys (john,T) → false

<!-- If John takes the keys then it must leave the house ? -->

Integrity constraints in RuleML:

to do,
  • C_post is a simple logic program (only unit clauses) in the vocabulary of event calculus predicates initiates and terminates that specifies the extensional fluents that are initiated and terminated by atomic events i.e. set of initiates and terminates defined by (usually ground) atoms - initiates(atomicEvent, fluent) and terminates(atomicEvent, fluent).
<!-- 
    happens the atomic action sendInvoice with object item1 and actor john at time T 
     makes the fluent paymentDue( john, item1) true (i.e., initiates the fluent)
-->
initiates(sendInvoice(john, item1), paymentDue( john, item1))
initiates(sendInvoice(mary, item2), paymentDue( mary, item2))
...
<!-- 
    happens the atomic action paysInvoice with object item and actor john at time T 
     makes the fluent paymentDue( john, item, T) false (i.e. treminates the fluent)
-->
terminates(paysInvoice(Customer, Item), paymentDue(Customer, Item))

Using RuleML

to do,

5 Reactive Rules

Reactive rules (or simply rules) in R are sentences of the logical form:

∀X [antecedent(X) → ∃ Y consequent(X, Y)]

where:

  • consequent(X, Y) is a disjunction consequent_1(X,Y) ∨ ... ∨ consequent_n(X,Y)
  • antecedent(X) and each consequent_i(X,Y) are conjunctions
  • antecedent(X) a conjunction of conditions each of which is either:
    • an event atom
    • a state condition (fluent)
    • a temporal constraint.
  • consequent_i(X,Y) a conjunction of conditions each of which is either:
    • an action atom
    • a state condition (fluent)
    • a temporal constraint.

A state condition is a formula of first-order logic (FOL) in the vocabulary of the fluent and auxiliary predicates, containing at most a single time variable, which is unbound. Operationally, the evaluation of a state condition can be understood as a query to the current extended state, where the time parameter refers to the current time.

5.1 Example: The shepherd and the wolf

seeWolf(shep, T) → cryWolf(shep, T+1)
cryWolf(shep, T) ∧ ¬ help(shep, T+1) → cryWolf(shep,T+2)

cryWolf(X, T) ∧ ¬ joker(X, T) → help(X, T+1).
cryWolf(X, T1) ∧ ¬wolf(T1) ∧ cryWolf(X, T2) ∧ ¬ wolf(T2) ∧ T1<T2 → assume(joker(X), T2+1).

initiates(assume(joker(X)), joker(X)).
  • shep - is a constant - the shepherd.
  • seeWolf is an external event symbol. seeWolf(shep, T) means that the event seeWolf occured at time T with the actor shep.
  • cryWolf is an action symbol. cryWolf(shep, T) means the cryWolf action event occurs at time T by the actor shep.
  • help is an extensional predicate symbol. help(john, 5) means john gets help at time 5.
  • wolf is an extensional predicate symbol. wolf(5) means there is a wolf at time 5.
  • T1 < T2 is a temporal constraint (simple time inequality)

The vocabulary of this example can be described as:

; sorts and composite sorts declarations
sort animal
sort wolf: animal
sort human: animal
sort joker: human

function joker(human): joker

; event predicate declarations
event seeWolf(human)
event cryWolf(human)
 
; extensional predicate declarations
predicate help(human)
predicate wolf(wolf)
predicate assume(joker)

; fluent declarations
fluent joker(human)

This include sorts declarations (i.e. sort animal) and inheritance (sort human: animal), event predicates declarations(event seeWolf(human)), extensional predicate declarations (predicate help(human)) as well as fluent declarations (fluent joker(human)).

This example in RuleML:

<?xml version="1.0" encoding="UTF-8"?>
<RuleML xmlns="http://ruleml.org/spec" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
  xsi:schemaLocation="http://ruleml.org/spec http://reaction.ruleml.org/1.0/xsd/eca.xsd"
  vocab="http://www.w3.org/2001/XMLSchema#">
<Assert >
  <!--
        seeWolf(shep, T) → cryWolf(shep, T+1)
        cryWolf(shep, T) ∧ ¬ help(shep, T+1) → cryWolf(shep,T+2)
        
        cryWolf(X, T) ∧ ¬ joker(X, T) → help(X, T+1).
        cryWolf(X, T1) ∧ ¬wolf(T1) ∧ cryWolf(X, T2) ∧ ¬ wolf(T2) ∧ T1<T2 → assume(joker(X), T2+1).
        
        initiate(assume(joker(X), joker(X))).
       -->
  <Rulebase>
    <Rule style="active">
      <on>
        <Event>
          <Expr>
              <Fun>seeWolf</Fun>
              <Ind>shep</Ind>
              <Var type="dateTime">T</Var>
          </Expr>
        </Event>
      </on>
      <do>
        <Action>
          <Expr>
              <Fun>seeWolf</Fun>
              <Ind>shep</Ind>
              <Expr>
                  <Fun>plus</Fun>
                  <Var type="dateTime">T</Var>
                  <Data>1</Data>
              </Expr>
          </Expr>
        </Action>
      </do>
    </Rule>
    <Rule style="active">
      <on>
        <Event>
          <Expr>
              <Fun>cryWolf</Fun>
              <Ind>shep</Ind>
              <Var type="dateTime">T</Var>
           </Expr>
        </Event>
      </on>
      <if>
        <Naf>
          <Atom>
            <Rel>help</Rel>
              <Ind>shep</Ind>
              <Expr>
                  <Fun>plus</Fun>
                  <Var type="dateTime">T</Var>
                  <Data>1</Data>
              </Expr>
           </Atom>
        </Naf>
      </if>
      <do>
        <Action>
          <Expr>
              <Fun>cryWolf</Fun>
              <Ind>shep</Ind>
              <Expr>
                  <Fun>plus</Fun>
                  <Var type="dateTime">T</Var>
                  <Data>2</Data>
              </Expr>
           </Expr>
        </Action>
      </do>
    </Rule>
  </Rulebase>
</Assert>
</RuleML>

5.2 Example: Conway Game of Life

  • Grid of square cells, each of which is in one of two possible states, alive or dead.
  • At each step in time, the following transitions occur:
    • Any live cell with fewer than two live neighbours dies, as if caused by under-population.
    • Any live cell with two or three live neighbours lives on to the next generation.
    • Any live cell with more than three live neighbours dies, as if by overcrowding.
    • Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
  • The initial pattern (system initial state) constitutes the seed of the system.
alive(Cell, T) ∧ aliveNeighboursNumber(Cell, N, T) ∧ N < 2   → retract(alive(Cell), T+1)
alive(Cell, T) & and; aliveNeighboursNumber(Cell, N, T) ∧ N > 3   → retract(alive(Cell), T+1)
¬ alive(Cell, T) ∧ aliveNeighboursNumber(Cell, N, T) ∧ N = 3  → assert(alive(Cell), T+1)

aliveNeighboursNumber(Cell, N, T) ← N = getAliveNeighboursNumber(Cell,T)

Predicate aliveNeighboursNumber(Cell, N, T) (the number of alive neighbours of C at time T is N ) can be defined by means of a pure logic program or using a simple logic program invoking a third party function (i.e., aliveNeighboursNumber(Cell, N, T) ← N = getAliveNeighboursNumber(Cell,T))

5.3 Example: Orders and deliveries

<!-- 
-->
orders(C, Item, T1) ∧ reliable(C, T1) → [
                          [dispatch(C, Item, T2) ∧ sendInvoice(C, Item, T3) ∧ T1 < T2 ≤ T3 ≤ T1 + 3] 
                               ∨
                          [sendApology(C, Item, T4) ∧ T1 < T4 ∧ T1 + 5] 
                        ]

Another variant of the above rule

<!-- 
happens C order Item at time T1, 
if C is reliable 
then do
dispatch item to C at time T2 and send invoice to C  no later than 3 days after the order time (T1)
-->
orders(C, Item, T1) ∧ reliable(C, T1) → 
                          [dispatch(C, Item, T2) ∧ sendInvoice(C, Item, T3) ∧ T1 < T2 ≤ T3 ≤ T1 + 3] 
    
           
<!-- 
happens C order Item at time T1, 
if C is NOT reliable 
then do
sendApology to C at time T2 no later than 5 days after the order time (T1)
-->
orders(C, Item, T1) ∧ ¬ reliable(C, T1)  → [sendApology(C, Item, T2) ∧ T1 < T2 ≤ T1 + 5] 

<!-- 
happens C order Item and item is NOT delievered within 3 days from order time 
then send apologies in no later 5 days from order time 
-->

orders(C, Item, T) and ¬ delivered(C,Item, T+3)   -> sendApology(C, Item, T1) and T1=< T+5

initiates (dispatch(C, Item),  delivered(C,Item))

These rules in RuleML

TO DO

6 References

  1. F. Sadri and R. Kowalski, LPS and its Kernel KELPS: Logic-Based State Transition Frameworks, RuleML Webinar, January 22, 2015
  2. R. Kowalski and F. Sadri,Programming in Logic Without Logic Programming, http://www.doc.ic.ac.uk/~rak/papers/KELPS%202015.pdf