A KobrA and OCL model for backward
state-space search planning and partial
order-planning with STRIPS
Ana Emília ([email protected])
Jairson Vitorino ([email protected])
Setembro, 2004
KobrA method overview
• Developed at Fraunhofer IESE
• Integrates:
– Component based development (CBD)
– Model-driven architecture (MDA)
– Product-line approach
• Komponents creation applied on a
recursive fashion
KobrA artifacts
Object Constraint Language
• Part of the UML standard.
• Formal Specification Language.
Precise semantics.
• (Quite) easy to read syntax.
• Why? Because UML is not enough!
An OCL Example
Natural language description
OCL statement
Age Vehicle´s owner must be at least 18
context Vehicle
inv: self. Owner. age >= 18
Nobody can have more than 3 vehicles
context Person
inv: self.fleet–>size <= 3
Everyone´s car is black
context Person
inv: self.fleet–>forAll(v | v.colour = #black)
Nobody can have more than 3 black vehicles
context Person
inv: self.fleet–>select(v | v.colour = #black)–>size <= 3
Nobody can have more than 3 black vehicles
context Person
inv: self.fleet–>iterate(v; acc:Integer=0
| if (v.colour=#black)
then acc + 1 else acc endif) <=3
A person younger than 18 cannot own a car
context Person
inv: age<18 implies self.fleet–>forAll(v | not v.oclIsKindOf(Car))
There is one red car
context Car
inv: Car.allInstances()->exists(c | c.colour=#red)
The Planning Problem
• Coming up with a sequence of actions that
will achieve a goal
• STRIPS planning language: comes in
propositional or first-order logic flavor
• STRIPS represents states, goals and
actions
StripsSearchPlanner
StripsSearchPlanner modelling
•
Strips_States
– Positive propositional literal conjunction
– Positive First-order literals conjunction
– Ground
– Function-free
– Closed-world assumption
•
Strips_Goal  Strips_States
•
Strips_actions
– Name
– Parameter_List
– Precondition
• Positive function free literals conjunction
• Literal.Variables  Parameter_List.Variables
– Effect
• Function freee literals conjunction
Basic algorithm
•
Do
1.
2.
3.
4.
•
Find Action A consistent and relevant if not possible
return failure
Goal.remove(A.effect.positiveLiterals)
Goal.add(A.precondition.PositiveLiterals)
If checkIfIsReached (InitialState) return Solution
While goal not achieved
StateSearchPlanner Komponent Specification
STRUCTURAL MODEL
StateSearchPlanner
<<Subject>>
Plan
State
0..*
Action
Name: string
ParameterList: List of
variables
Effect: List of Literals
Precondition: List of
Positive Literals
EffectPositiveLiterals()
EffectNegativeLiterals()
Current: List of
Positive Literals
Goal
StateSearchPlanner Komponent Realization
StateSearchPlanner Komponent
Realization Beahviour model
StateChart
Functional Model
OCL statement
Explanation
context StateSearchPlanner::predecessor():Action
pre true
pos result = self.avaliableActionList->select(a|true) and
self.actionList->size = self.actionList@pre->size + 1
O resultado do método predecessor() é uma ação e o
tamanho da lista de ações do plano é incrementado de
um.
context Action inv actionConsistentConstraint : self .
effect . literal -> forAll ( l | not l . isPositive implies not
self . owner . goal . current -> includes ( l ) )
Nenhum literal positive da ação Action pode ocorrer nos
literais do objetivo.
context Action inv actionRelevantConstraint : self .
effect . literal -> exists ( l | l . isPositive and self . owner
. goal . current -> includes ( l ) )
context
AvailableAction
inv
variablePreconditionConstraint : self . precondition .
literal -> includes ( parameterList . name ) implies self ->
includes ( parameterList . name )
context AvailableAction inv variableEffectConstraint :
self . effect . literal -> includes ( parameterList . name )
implies self -> includes ( parameterList . name )
A ação na lista de planos precisa ser relevante, isto é,
existe pelo menos um literal positivo do efeito que
também pertence aos literais do objetivo.
Todas as variáveis dos parâmetros das precondições
precisam pertencer a listas de parâmetros da ação.
Todas as variáveis dos parâmetros dos efeitos precisam
pertencer a listas de parâmetros da ação.
Functional Model
OCL statement
Explanation
context AvaliableAction ::effectPositiveLiterals() : List
pre true
post result = {1..self.effect.literal->size} -> iterate(x; y:List()=List{}
| if (self.effect.literal.isPositive) then y->includes(sef.effect.literal)
else y endiff )
O resultado do método
effectPositiveLiterals() é a lista de
literais positivos dos efeitos.
context AvaliableAction ::effectNegativeLiterals() : List
pre true
post result = {1..self.effect.literal->size} -> iterate(x; y:List()=List{}
| if not (self.effect.literal.isPositive) then y>includes(sef.effect.literal) else y endiif)
O resultado do método
effectNegativeLiterals() é a lista de
literais negativos dos efeitos.
context State inv : self . current -> forAll (L | L.isPositive = true )
Todos os literais do estado state (estado
inicial) são positivos
POPPlanner
StripsPOPPlanner modelling
•
Strips_States
– Positive propositional literal conjunction
– Positive First-order literals conjunction
– Ground
– Function-free
– Closed-world assumption
•
Strips_Goal  Strips_States
•
Strips_actions
– Name
– Parameter_List
– Precondition
• Positive function free literals conjunction
• Literal.Variables  Parameter_List.Variables
– Reserved actions: START and FINISH (POP algorithm)
– Effect
• Function freee literals conjunction
Actions set
•
•
Empty plan contains {START,FINISH}
START
– No precondition
– Effect: all literals composing the initial state
•
FINISH
– No effects
– Preconditions: literals composing the goal
Ordering constraints
• A<B
– Action A must be executed before action B
– A < B and B < A are not allowed (loops)
Causal Links
• A
p
B
– Effect of action A is precondition p of action B
– Cannot be canceled by other actions executed
between A and B execution
• Ex.: RightSock
RightSockOn
RightShoe
• C conflicts with causal link causal p:
– C has effect  p
– C may happen between A and B according to
ordering restrictions
StripsPOPPlanner Komponent Specification
STRUCTURAL MODEL
Ordering
previous: Action
Current : Action
State
POPPlan
*
Current: List of
Positive Literals
listOfOrederedActions:
Ordering
successor()
linearization()
Action
CausalLinks
precondition:literal
*
Constraints:
Goal.Instance  State.Instance
Goal
Name: string
ParameterList: List of
variables
Effect: List of Literals
Precondition: List of
Positive Literals
CLList
EffectPositiveLiterals()
EffectNegativeLiterals()
Actions.Precondition.variables  Action.ParameterList.Variables
0..1
StripsPOPPlanner Komponent Specification
STRUCTURAL MODEL
Ordering
previous: Action
Current : Action
*
1
State
POPPlan
Current: List of
Positive Literals
listOfOrederedActions:
Ordering
successor()
linearization()
Action
CausalLinks
precondition:literal
*
Goal
Name: string
ParameterList: List of
variables
Effect: List of Literals
Precondition: List of
Positive Literals
CLList
EffectPositiveLiterals()
EffectNegativeLiterals()
CL : List of CausalLinks
0..1
Constraints:Contex Ordering: Invariant
For All objects ordering O1 and O2 there cannot be
O1.previous=O2.current or O1.current = O2.previous. // this means NO LOOPS
StripsPOPPlanner Komponent Realization
Structural Model
StripsPOPPlanner Komponent Realization
Functional Model
Project Analysis
• KobrA:
– small problems, only on interaction
– Small structural models
– Knowledge in embedded in Constraints and methods
• OCL: Using OCL forces a better understanding of the model
and better specification
• Drawbacks:
– Lack of better examples of OCL
– Tool used (Poseidon) do not conform to OCL current
specification
– There is no Case tool for KobrA
Conclusions
• OCL captures some behaviour aspects
• OCL does not include side effects
• Further investigation is necessary to
use OCL in statechart and other
behavioural diagrams
• It may be necessary to extend KobrA
to provide bottom-up modeling and
better COTS integration