APLANNING AND SCHEDULING PERSPECTIVE FOR DESIGNING
BUSINESS PROCESSES FROM DECLARATIVE SPECIFICATIONS
I ene Ba ba and Ca melo Del Valle
Depa amen o de Lenguajes y Sis emas In o m´
a icos
Uni e sidad de Se illa, A da Reina Me cedes s/n, 41012, Se ille, Spain
Keywo ds: Planning, Scheduling, Business P ocesses Managemen .
Abs ac : Usually, business p ocess models a e manually achie ed by business analys s and mos o cu en modelling
languages a e o impe a i e na u e. As a consequence, non-op imized o aul y models can be ob ained. This
wo k p oposes a planning based app oach o gi e business analys s assis ance o he p ocess models gene-
a ion. This app oach en ails he selec ion and he o de o he ac i i ies o be execu ed (planning), and he
esou ces alloca ion in ol ing empo al easoning (scheduling), bo h conside ing unc ion op imiza ion. The
p ocess in o ma ion is speci ied in a decla a i e way, ha is ansla ed in o he s anda d planning language
PDDL. A iendly g aphic language is used (ConDec-R, an ex ension o ConDec).
1 INTRODUCTION
In he pas ew yea s, mos o he o ganiza ions need
o adap o he new comme cial condi ions as well as
o espond o compe i i e p essu es, so he e exis s
an inc easing in e es in he e ec i e managemen
o business p ocesses (BP). BP Managemen (BPM)
suppo s BP using me hods, echniques, and so wa e
o design, enac , con ol and analyze p ocesses in-
ol ing humans, o ganiza ions, documen s and o he
sou ces o in o ma ion ( an de Aals e al., 2003).
Scheduling p oblems (B ucke and Knus , 2006)
en ails he sui able gene a ion o execu ion plans
o a se o asks ela ed by empo al and esou ce
cons ain s, op imizing some unc ions. In a wide
pe spec i e, in A i icial In elligence (AI) planning
(Ghallab e al., 2004), he asks o be execu ed a e no
es ablished a p io i, so i is necessa y o selec a sui a-
ble se o ac ions ha mus be execu ed in a co ec o -
de , gene ally op imizing some objec i es. In he pas
yea s, he e is an inc easing in e es in he applica-
ion o AI P&S echniques o au oma e he p oduc ion
and execu ion o BP (Kea ney e al., 2003; Gonz´
alez-
Fe e e al., 2009; Ba ba and Del Valle, 2010).
In BPM sys ems, in gene al, a use speci ies he
model h ough a modelling language, such as BPMN
(Whi e and e al., 2004). In o de o design a sui a-
ble model, he use mus deal wi h se e al aspec s,
such as he esou ce alloca ion, he asks p ope ies
o he ela ions be ween hem, possibly op imizing
some unc ions. In mos cases, he BP in o ma ion is
p o ided o he sys em h ough impe a i e modelling
languages. In his wo k, i is p oposed a decla a i e
language o he BP in o ma ion. The wo k (Fahland
e al., 2010) analyzes he di e ences be ween impe a-
i e and decla a i e p ocess modelling languages wi h
espec o build- ime modi ica ions (main ainabili y).
Se e al wo ks conce ning BP based on Linea
Tempo al Logic, LTL (Cla ke J . e al., 1999), can
be ound. (Pesic and an de Aals , 2006; an de
Aals and Pesic, 2006) p opose a g aphic ool o
modelling he p ocesses h ough some empla es ha
can be ansla ed o LTL o mulas. ConDec (Pesic
and an de Aals , 2006) is a decla a i e language
o speci y dynamic BP models using a g aphical no-
a ion which can be mapped o o mulas in LTL. In
his wo k, an ex ension o ConDec, named ConDec-
R (Sec . 2), has been de ined since ConDec does no
allow easoning abou esou ces di ec ly.
The Planning Domain De ini ion Language
(PDDL) (Ghallab and e al., 1998) is a (s anda d)
language o he speci ica ion o planning p oblems
and solu ions, so ha any gene ic planne ha sup-
po s PDDL is capable o sol e a wide scope o p o-
blems o di e en na u e speci ied h ough his lan-
guage. PDDL 2.2 (Ho mann and Edelkamp, 2005)
also allows handling o nume ic alues, du a i e ac-
ions, plan objec i e unc ions, de i ed p edica es and
imed ini ial li e als.
In Fig. 1, a g aphical ep esen a ion o he cu en
562
Ba ba I. and Del Valle C..
A PLANNING AND SCHEDULING PERSPECTIVE FOR DESIGNING BUSINESS PROCESSES FROM DECLARATIVE SPECIFICATIONS.
DOI: 10.5220/0003149005620569
In P oceedings o he 3 d In e na ional Con e ence on Agen s and A i icial In elligence (ICAART-2011), pages 562-569
ISBN: 978-989-8425-40-9
Copy igh c
2011 SCITEPRESS (Science and Technology Publica ions, Lda.)
Decla a i e P ocess In o ma ion
(ConDec-R)
Resou ce
A ailabili y
Name: N1
Role: R1
PDDL 2.2 Speci ica ion
ansla e
P&S
Planne 
PDDL 2.2 Plan
Business
Analys  Business
P ocess Model Wo k low
Engine
gi e assis ance
Domain P oblem
AI Planning and Scheduling
BPM Sys em
Name: N2
Role: R2
(de ine (p oblem a elCompany)
(:domain ConDec) (:objec s Recei e ... C edi -ca d -
ac Sec e a y
BookManage - ole S1 BM1 BM2 - es)
(:ini (= (n- imes- ecei e) 0)
me ic minimize ( o al- ime))
(:goal (and ( o all (?ac - ac i i y) (no ( o ced ?ac )))
(de ine (domain ConDec)
(: ypes ac es ole - objec )
(:p edica es ( o ced ?a - ac ) (locked ?a - ac )
(: unc ions (du a ion ?ac - ac ) (n- imes- ecei e) ...
(:du a i e-ac ion Ac -C edi -ca d
:pa ame e s (? - es ? ol - ole)
:du a ion (= ?du a ion (du a ion C edi -ca d))
0.001: (ACT-RECEIVE S1) [2.0000]
2002: (ACT-HOTEL BM1) [4.0000]
2.003.: (ACT-AIRLINE BM2) [3.0000]
5.004: (ACT-BOOKED-AIRLINE BM2)
[3.0000]
6.005: (ACT-BOOKED-HOTEL BM1) [4.0000]
10.006: (ACT-CREDIT-CARD S1) [3.0000]
13.007: (ACT-NOTIFY-BOOKED S1) [2.0000]
Business
Analys 
Figu e 1: An AI-based app oach o he gene a ion o business p ocess models.
app oach is shown. Fi s , he business analys p o-
ides he decla a i e p ocess in o ma ion h ough a
ConDec-R speci ica ion, ha is ansla ed o a PDDL
2.2 speci ica ion o be used as inpu o a planne
o ob aining a easible op imized BP execu ion plan.
Las ly, his PDDL 2.2 plan gi es he business analys
assis ance o he BP model gene a ion. The main
con ibu ions o his pape can be summa ized as:
•An applica ion o an AI-based app oach o sol-
ing he planning and scheduling o he asks in-
ol ed in he BP model h ough au oma ic plan-
ne s, in o de o gene a e BP execu ion plans.
This app oach conside s ask p ope ies, esou ces
alloca ion and he op imiza ion o some unc ions.
•A ansla ion om a o mal and widely used lan-
guage (LTL) o PDDL 2.2 o se e al empla es e-
la ed o BP de ini ions.
•An ex ension o a g aphic decla a i e language o
BP, including esou ces ea men .
The pape is o ganized as ollows: Sec . 2 ex-
plains he p oposed decla a i e language, Sec . 3 de-
ails he ansla ion om he decla a i e speci ica ion
o PDDL 2.2, Sec . 4 shows a case o s udy, and Sec .
5 p esen s some conclusions and u u e wo k.
2 DECLARATIVE
SPECIFICATION OF BP
In his wo k, he use mus p o ide he p ocess in-
o ma ion o he sys em in a decla a i e way. In o -
de o do his, an ex ension o ConDec (ConDec-R)
is used, including in o ma ion abou he esou ces e-
qui ed o he execu ion o he ac i i ies. ConDec
(Pesic and an de Aals , 2006) is a g aphical lan-
guage based on decla a i e speci ica ions o mode-
lling and enac ing dynamic BP. Fo he de ini ion o
ela ionships be ween ac i i ies, ConDec p oposes an
open se o cons ain s based on LTL. One impo -
an di e ence when modelling wi h ConDec is ha
a ConDec-ac i i y ep esen s mul iple execu ions o a
P&S-ac i i y, so ha a ConDec-ac i i y can be execu-
ed se e al imes.
The main con ibu ion o ConDec-R ega ding o
ConDec, is he easoning abou esou ces. Unlike
ConDec, in ConDec-R he ac i i ies execu ion e-
qui es esou ces o a speci ic ole, and he e a e se-
e al esou ces wi h he compe ences de ined by a
ole. This in o ma ion can be easily added o ConDec.
A ConDec-R p oblem speci ica ion mus include (an
example can be seen in Sec . 4):
•As in ConDec, he asks ha can be execu ed in
he BP enac men . In some cases, cons ain s
abou he numbe o imes ha one ac i i y mus
be execu ed a e speci ied (i appea s abo e he
associa ed ac i i y in he g aphical ep esen a-
ion).
•The ole o he equi ed esou ce and he es i-
ma ed du a ion o each ask, which a e speci ied
on he le side o he ask (ex ension o ConDec).
•A ailable esou ces wi h he compe ences o a
ole (ex ension o ConDec).
•As in ConDec, he ela ions be ween ac i i-
ies h ough cons ain empla es (pa ame e ized
g aphical ep esen a ions o LTL o mulas).
3 TRANSFORMATION FROM
CONDEC-R TO PDDL 2.2
PDDL (Ghallab and e al., 1998) is a (s anda d) lan-
guage o he speci ica ion o planning p oblems and
solu ions, so ha any gene ic planne ha suppo s
PDDL is capable o sol e a wide scope o p oblems
A PLANNING AND SCHEDULING PERSPECTIVE FOR DESIGNING BUSINESS PROCESSES FROM
DECLARATIVE SPECIFICATIONS
563
o di e en na u e speci ied h ough his language.
PDDL 2.2 (Ho mann and Edelkamp, 2005) speci i-
ca ions include a domain ile and a p oblem ile.
3.1 Domain Desc ip ion
A PDDL 2.2 domain con ains he ollowing i ems:
P edica es: They ep esen he p ope ies o ob-
jec s ha can be ue o alse. Se e al p edica es ha e
been conside ed o he BP execu ion plan gene a ion
(Table 1). Di e en p edica es o he empo al locks
o he ac i i ies a e used in o de o di e en ia e be-
ween he easons o he lock.
Func ions (Fluen s): They ep esen alues, ha
can a y o e ime, associa ed o objec s, allowing
handling o nume ic alues. We ha e used wo kind
o luen s:
(du a ion ?ac )
, ha is he cons an du-
a ion o he ac i i y
ac
; and
(n- imes-ac i i y)
ha ep esen s he numbe o imes ha an ac i i y has
been execu ed un il he cu en s a e.
Ac ions/Ope a o s (Du a i e): They allow he
e olu ion o he sys em by means o s a e changes.
Fo he BP execu ion plan gene a ion, he e exis s one
du a i e ac ion ep esen ing he execu ion o each ac-
i i y. In he p oposed app oach, he e exis s a PDDL
2.2 du a i e ac ion associa ed o each ConDec-R ac-
i i y, since bo h a e du a i e and, also, can be exe-
cu ed se e al imes. Fu he mo e, all he ac ions ha e
a base speci ica ion (Fig. 2) ha is ex ended h ough
p econdi ions and e ec s depending on he ela ions
in which he conce ning ac i i y is in ol ed (Sec .
3.3). Fo he execu ion o an ac i i y (Fig. 2), wo
condi ions
(:condi ion)
mus be sa is ied: i mus
no be locked o any eason, and he e mus exis a
ee esou ce wi h he ole equi ed by he ac i i y.
The p edica es
o ced
and
locked
a e used in o de
o ensu e he easibili y o he cons ain s es ablished
by he ConDec-R empla es. A e he ac i i y execu-
ion, some e ec s
(:e ec )
a e gi en: he
n- imes
unc ion is inc eased; he ac i i y becomes no o ced
o execu e; and he equi ed esou ce becomes busy
(only) du ing he ac i i y execu ion.
3.2 P oblem Desc ip ion
A PDDL 2.2 p oblem con ains he ollowing i ems:
Objec s: They ep esen he hings in he wo ld
ha a e no ewo hy o he speci ied p oblem. In he
cu en p oposal, h ee kinds o objec s can be dis in-
guished:
ac i i y
,
esou ce
and
ole
.
Ini ial S a e: Ini ially, all he esou ces a e consi-
de ed ee and he numbe o imes one ac i i y has
been execu ed is 0 ( luen
(n- imes-ac i i y)
).
Also, i is necessa y o include he p edica es
( ole
(:du a i e-ac ion Ac i i y
:pa ame e s (? - es ? ol - ole)
:du a ion (= ?du a ion (du a ion Ac i i y))
:condi ion (and (a s a (no (locked Ac i i y)))
(a s a (and ( ee ? )
( esou ces Ac i i y ? ol)
( ole ? ? ol))))
:e ec (and (a end (done Ac i i y))
(a end (inc ease (n- imes-ac i i y) 1))
(a end (no ( o ced Ac i i y)))
(a s a (no ( ee ? )))
(a end ( ee ? ))))
Figu e 2: PDDL 2.2 base speci ica ion o he
Ac i i y
ac ions.
Resou ce Role)
and
( esou ce Ac i i y Role)
o he ela ed objec s ha p esen hese ela ions,
oge he wi h he co esponding alue o he luen
(du a ion Ac i i y)
.
Goal: Things ha mus be ue a he end o he
plan. The e is a base goal speci ica ion, ha is ex-
ended depending on he ela ions be ween he ac i i-
ies (Sec . 3.3). The goal is eached when he e a e
no ac i i ies o be execu ed (
(:goal (and ( o all
(?ac - ac i i y) (no ( o ced ?ac )))))
).
Objec i e Func ion: Plan quali y measu es (me-
ics). In he cu en p oposal, he minimiza ion o
he o al ime o he plan is pu sued:
(:me ic
minimize ( o al- ime))
.
3.3 T ans o ma ion om ConDec-R
Templa es o PDDL 2.2
ConDec-R conside s he same empla es han ConDec
( an de Aals and Pesic, 2006). Fo a speci ic p ob-
lem, he ela ions be ween he ac i i ies can ex end
he base du a i e ac ion speci ica ion (Fig. 2); and he
base goal o he p oblem speci ica ion. As ollows,
he conside ed ela ions a e desc ibed, oge he wi h
he e ec hey ha e in he PDDL 2.2 speci ica ion:
I) Exis ence cons ain s:
1. EXISTENCE N(A):
A
mus be execu ed
mo e o equal han
N
imes. The goal
(>=
(n- imes-A) N)
is added.
2. ABSENCE N(A):
A
mus be execu ed less
han
N
imes. The goal
(< (n- imes-A) N)
is added.
3. EXACTLY N(A):
A
mus be execu ed
N
imes exac ly. The goal
(= (n- imes-A)
N)
is added.
II) Rela ion cons ain s:
1. RESPONDED EXISTENCE(A,B): I
A
is
execu ed, hen
B
also mus be execu-
ICAART 2011 - 3 d In e na ional Con e ence on Agen s and A i icial In elligence
564
Table 1: P edica es o he au oma ic gene a ion o op imized BP execu ion plans.
P edica e Desc ip ion
( o ced ?ac - ac i i y)
The ac i i y
ac
has o be execu ed be o e he end o he plan.
(locked- emp ?ac - ac i i y) ac
is empo a ily locked o be execu ed due o
al e na e
and
esponded absence
ela ions (Sec . 3.3).
(locked-chain ?ac - ac i i y) ac
is empo a ily locked o be execu ed due o
chain
ela ions
(Sec . 3.3).
(locked-pe m ?ac - ac i i y) ac
can no be execu ed anymo e.
(locked ?ac - ac i i y)
De i ed p edica e ha is de ined as he disjunc ion o
locked- emp
,
chain
and
pe m
.
( esou ces ?ac - ac i i y ? o - ole) ac
equi es a esou ce wi h he ole
o
o be execu ed.
( ole ? - esou ce ? o - ole)
The e exis s a esou ce
ha p esen s he ole
o
.
( ee ? - esou ce)
The esou ce
is ee.
(done ?ac - ac i i y)
The ac i i y
ac
has been execu ed.
ed. The goal
(o (= (n- imes-A) 0) (>
(n- imes-B) 0))
is added.
2. CO-EXISTENCE(A,B): The execu ion o
A
o ces he execu ion o
B
, and ice
e sa. The goal
(= (> (n- imes-A) 0)
(> (n- imes-B) 0))
is added.
3. RESPONSE(A,B): A e he execu ion o
A
,
B
mus be execu ed always. I leads o add an
e ec o he du a i e-ac ion associa ed o
A
:
(a end ( o ced B))
.
4. PRECEDENCE(A,B): Be o e
B
,
A
mus ha e
been execu ed. I leads o add a condi ion
o he ac ion associa ed o
B
:
(a s a
(done A))
.
5. SUCCESSION(A,B): Rela ions
Response(A,B)
and
P ecedence(A,B)
mus hold.
6. ALTERNATE RESPONSE(A,B): A e he
execu ion o
A
,
B
mus be execu ed, and be-
ween each wo execu ions o
A
, he e mus
be a leas one execu ion o
B
. I leads o add
wo e ec s o
A
:
(a end ( o ced B))
and
(a s a (locked- emp A))
; and one
e ec o
B
:
(a end (no (locked- emp
A)))
.
7. ALTERNATE PRECEDENCE(A,B): Be o e
he execu ion o
B
,
A
mus ha e been execu-
ed, and be ween each wo execu ions o
B
,
A
mus be execu ed. I leads o add: a condi ion
o
B
:
(a s a (done A))
; an e ec o
B
:
(a s a (locked- emp B))
; and an
e ec o
A
:
(a end (no (locked- emp
B)))
.
8. ALTERNATE SUCCESSION(A,B): Re-
la ions
Al e na e Response(A, B)
and
Al e na e P ecedence(A,B)
mus hold.
9. CHAIN RESPONSE(A,B): S aigh a e
A
,
B
mus be execu ed. I leads o add one
e ec o
A
o each ac i i y
C
ha does
no ma ch wi h
B
:
(a end (locked-chain
C))
; and one o
B
o each ac i i y
C
ha does no ma ch wi h
B
:
(a end (no
(locked-chain C)))
.
10. CHAIN PRECEDENCE(A,B): S aigh be-
o e
B
,
A
mus be execu ed. I leads o add an
e ec o
A
:
(a end (no (locked-chain
B)))
; and an e ec o all he ac i i-
ies di e en om
A
(e en
B
):
(a s a
(locked-chain B))
.
11. CHAIN SUCCESSION(A,B): Rela ions
Chain Response(A,B)
and
Chain P ecedence(A,B)
mus hold.
III) Nega ion cons ain s:
12. RESPONDED ABSENCE and NOT
CO EXISTENCE(A,B): I
B
is execu-
ed, hen
A
can no be execu ed, and ice
e sa. I leads o add an e ec o
A
:
(a
s a (locked-pe m B))
; and one o
B
:
(a s a (locked-pe m A))
.
13. NEGATION RESPONSE, NEGATION
PRECEDENCE, NEGATION SUCCES-
SION(A,B): A e he execu ion o
A
,
B
can
no be execu ed. I leads o add an e ec o
A
:
(a s a (locked-pe m B))
.
14. NEGATION ALTERNATE RES-
PONSE(A,B): Be ween wo execu ions
o
A
,
B
can no be execu ed. I leads o add
an e ec o
B
:
(a s a (when (done A)
(locked-pe m A)))
.
15. NEGATION ALTERNATE PRECE-
DENCE(A,B): Be ween wo execu ions
o
B
,
A
can no be execu ed. I leads o add
an e ec o
A
:
(a s a (when (done B)
(locked-pe m B)))
.
16. NEGATION ALTERNATE SUC-
CESSION(A,B): Rela ions
Nega ion
A PLANNING AND SCHEDULING PERSPECTIVE FOR DESIGNING BUSINESS PROCESSES FROM
DECLARATIVE SPECIFICATIONS
565
Al e na e Response(A,B)
and
Nega ion
Al e na e P ecedence(A, B)
mus hold.
I leads o add one e ec o
B
:
(a s a
(when (done A) (locked-pe m A)))
;
and one o
A
:
(a s a (when (done B)
(locked-pe m B)))
.
17. NEGATION CHAIN RESPONSE, NEGA-
TION CHAIN PRECEDEN- CE, NEGA-
TION CHAIN SUCCESSION(A,B):
B
can
no be execu ed s aigh a e he execu ion
o
A
. I leads o add an e ec o
A
:
(a
s a (locked-chain B))
; and an e ec
o all he ac i i ies bu
A
:
(a s a (no
(locked-chain B)))
.
The se o empla es can be ex ended ( an de
Aals and Pesic, 2006). One ex ension is he ela-
ion
mu ual subs i u ion
( an de Aals and Pesic,
2006), es ablishing ha , a leas , one o wo ac i i ies
should occu . Ano he ex ension co esponds o he
b anched cons ain s ( an de Aals and Pesic, 2006)
om one sou ce ac i i y o se e al sink ones, so he
ela ion is gi en be ween he sou ce and, a leas , one
o he sinks; o om se e al sou ce ac i i ies o one
sink, so he ela ion is gi en be ween, a leas , one
o he sou ces and he sink (examples in Sec . 4).
When he b anched cons ain has only one sou ce ac-
i i y, non-de e minis ic e ec s a e gi en o such ac-
i i y. The inclusion o non-de e minis ic e ec s can
be ea ed by s ochas ic planne s (Dean e al., 1995).
To he bes o ou knowledge, a p esen he e is no
an a ailable planne able o ea wi h all he ea-
u es equi ed: du a i e ac ions, simul aneous ac ion
execu ion, non-de e minis ic e ec s and op imiza ion.
In o de o o e come his p oblem, in his wo k, he
non-de e minis ic ConDec-R p oblem is au oma ica-
lly ansla ed o a se o de e minis ic ones ollowing
he algo i hm 1, so gene ic planne s can au oma ically
sol e he di e en de e minis ic p oblems.
The basic idea o Alg. 1 is explained as ollows:
each non-de e minis ic ela ion nd ( ,A,B,C), whe e
is he gi en ela ion, Ais he sou ce and B,Ca e
he sinks, means ha , a leas , one o ela ions (A,B)
o (A,C)mus be gi en. In o de o ea bo h pos-
sibili ies, wo de e minis ic p oblems a e sol ed, one
conside ing he de e minis ic ela ion (A,B), and he
o he one conside ing (A,C). I is necessa y o con-
side bo h possibili ies each ime he sou ce ac i i y is
execu ed, leading o a limi a ion in he ConDec-R p o-
blems o be ea ed wi h he p oposed app oach: he
maximum ca dinali y o he ac i i ies ha a e sou ce
o a non-de e minis ic ela ion, mus be speci ied in
he ConDec-R p oblem in o de o gene a e he co -
esponding de e minis ic p oblems in a sui able way.
Le nbe he numbe o non-de e minis ic ela ions
Algo i hm 1:De e minis ic ConDec-R p oblems.
inpu : a non de e minis ic p oblem
NDP <DR,NDR >
ou pu : a se o de e minis ic p oblems
DP <DR >
P obs ← {};
n←numbe o non-de e minis ic ela ions
conside ing he sou ce maximum ca dinali y;
o i←0 o 2n−1do
P ob ←NDP.DR ∪
DF omND
(i,NDP.NDR);
P obs ←P obs ∪P ob;
e u n P obs;
Func ion:
DF omND(
in i, se NDR
)
.
s← {};
o each nd ( ,A,B,C)in NDR do
em =i%2;
i em == 0 hen
s←s∪d ( ,A,B);
else
s←s∪d ( ,A,C);
i=i/2;
e u n s;
aking in o accoun he maximum ca dinali y o he
ac i i ies ha a e sou ce o a non-de e minis ic ela-
ion. Then, in gene al, 2nde e minis ic p oblems can
be gene a ed in o de o deal wi h all he possibili ies.
In Alg. 1, he inpu is a ConDec-R non-de e minis ic
p oblem (NDP), composed by a se o de e minis ic
ela ions (DR), and a se o non-de e minis ic ones
(NDR). As a esul , a se o de e minis ic p oblems
(DP), is ob ained. P obs is a se ha con ains 2nde-
e minis ic p oblems a he end o he algo i hm. The
unc ion (
DF omND
) is in cha ge o gene a ing di e-
en combina ions o de e minis ic ela ions o each
p oblem om he se NDR.
4 AN EXAMPLE
The Acme T a el Company p oblem is an adap a ion
o he one p esen ed in (Snell, 2002), ha was speci-
ied h ough DecSe Flow language in ( an de Aals
and Pesic, 2006). As ollows, he conside ed p oblem
is desc ibed:
1. Acme T a el ecei es an i ine a y om Ka la, he
cus ome .
2. A e checking he i ine a y o e o s, he p ocess
de e mines which ese a ions o make, simul a-
ICAART 2011 - 3 d In e na ional Con e ence on Agen s and A i icial In elligence
566

Recei e
Reques 
1
S
2
Ho el
Sea ch
BM
4 Compe
nsa ion
0..1
BM
2 Ai line
Sea ch
BM
3
Recei e
Failed
Ho el
BM
1
Recei e
Failed
Ai line
BM
1
No i y
Failu e
0..1
S
2
Book
Ai line
BM
2
Book
Ho el
BM
2
No i y
Booked
0..1
S
2 C edi 
Ca d
0..1
S
3
no - esponse
p ecedence
esponse
p ecedence
no - esponse
p ecedence
esponse
p ecedence
succession succession
p ecedence
p ecedence
no co-exis ence no 
co-exis ence
p ecedence no 
co-exis ence mu ual
subs i u ion esponse
esponse
succession
no - esponse no - esponse
Resou ce
A ailabili y
Name: BM1
Role: BM
Name: BM2
Role: BM
Name: S1
Role: S
11
Figu e 3: ConDec-R speci ica ion o Acme T a el Company.
neously asking o in o ma ion o he app op ia e
ai line and ho el agencies o make he app op ia e
ese a ions.
3. I any o he wo ese a ion asks ails, he
i ine a y is cancelled by pe o ming he ”compen-
sa e” ac i i y and Ka la is no i ied o he p oblem.
4. Acme T a el wai s o con i ma ion o he wo
ese a ion eques s.
5. Upon eceip o con i ma ion, Acme T a el no i-
ies Ka la o he success ul comple ion o he p o-
cess and sends he he i ine a y de ails.
6. Once Ka la is no i ied o ei he he success o ai-
lu e o he eques ed i ine a y, she may submi
ano he a el eques .
The ac i i ies in ( an de Aals and Pesic, 2006) a e
modelled as web se ices. Con e sely, in his wo k,
he ac i i ies a e asks ha need o use some sha ed
esou ces o be execu ed. Two oles a e conside ed:
Book Manage (BM) and Sec e a y (S). Also, i is es-
ima ed ha wo esou ces wi h ole Book Manage
(BM1 and BM2), and one wi h ole Sec e a y (S), will
be a ailable o he BP enac men . Conside ing ha
only one ins ance is execu ed a he same ime, he o-
al ime o he esul ing plan mus be minimized. In
Fig. 3 he ConDec-R model o he p oblem is shown.
As can be seen, ele en ac i i ies a e p esen ed:
Recei e Reques : A Sec e a y mus a end he clien
eques . This ac i i y will be done exac ly once.
Ho el Sea ch: A BM asks o in o ma ion o se e-
al ho el agencies o make he app op ia e ese -
a ion. A e he execu ion o Recei e Reques ,
i mus be execu ed always, and be o e i s exe-
cu ion, Recei e Reques mus ha e been execu ed
also ( ela ion succession).
(de ine (domain
ConDec)
(: equi emen s :adl : luen s :du a i e-ac ions)
(: ypes ac es ole - objec )
(:p edica es ( o ced ?a - ac ) (locked ?a - ac )
(locked- emp ?a - ac )... (done ?a - ac )
( ole ? - es ? o - ole) ( ee ? - es)
( esou ce ?a - ac ? o - ole))
(: unc ions (du a ion ?ac - ac ) (n- imes- ecei e) ...
(n- imes-c edi -ca d))
(:du a i e-ac ion Ac -C edi -ca d
:pa ame e s (? - es ? ol - ole)
:du a ion (= ?du a ion (du a ion C edi -ca d))
:condi ion (and (a s a (no (locked C edi -ca d)))
(a s a (and ( ee ? ) ( esou ces C edi -ca d ? ol)
( ole ? ? ol)))
(a s a (and (done Book-ho el) (done Book-ai line))))
:e ec (and (a s a (and (no ( o ced C edi -ca d))
(no ( ee ? ))))
(a end (and (done C edi -ca d)
(inc ease (n- imes-c edi -ca d) 1)
( ee ? )))
(a end ( o ced No i y-booked))
(a end (and (locked-pe m Ho el)
(locked-pe m Ai line)
(locked-pe m No i y- ailu e)))))
Figu e 4: PDDL 2.2 domain speci ica ion o he Acme
T a el Company.
Book Ho el: A BM mus book he app op ia e ese -
a ion. Ho el Sea ch has o be execu ed be o e i
(p ecedence).
Recei e Failed Ho el: A BM mus ecei e he ai-
lu e no i ica ion in he case i happens. Ho el
Sea ch has o be execu ed be o e i (p ecedence).
On he o he hand, a e Ho el Sea ch, one o he
ac i i ies Book Ho el o Rec. Failed Ho el mus be
execu ed (b anched esponse). Las ly, only one
o Book Ho el and Recei e Failed Ho el can be
A PLANNING AND SCHEDULING PERSPECTIVE FOR DESIGNING BUSINESS PROCESSES FROM
DECLARATIVE SPECIFICATIONS
567
(de ine (p oblem a elCompany)
(:domain ConDec)
(:objec s Recei e... - ac Sec e a y BookManage - ole
S BM1 BM2 - es)
(:ini (= (n- imes- ecei e) 0)...(= (du a ion C edi -ca d) 3)
( ee S)...( ole S Sec e a y)
( esou ces Recei e Sec e a y)...
( esou ces C edi -ca d Sec e a y)
(:me ic minimize ( o al- ime))
(:goal (and ( o all (?ac - ac i i y) (no ( o ced ?ac )))
(= (n- imes- ecei e) 1) (< (n- imes-compensa ion) 2)
(< (n- imes-no i y- ailu e) 2)
(< (n- imes-no i y-booked) 2)
(< (n- imes-c edi -ca d) 2)
(o (> (n- imes-c edi -ca d) 0)
(> (n- imes-no i y- ailu e) 0)))))
Figu e 5: PDDL 2.2 p oblem speci ica ion o he Acme
T a el Company.
execu ed (no co-exis ence).
Ai line Sea ch: A BM asks o in o ma ion o se e-
al ai line agencies o make he app op ia e ese -
a ion. As Ho el Sea ch, i p esen s a succession
ela ion o Recei e Reques .
Book Ai line: A BM mus book he app op ia e
ese a ion (p e iously de ec ed in Ai line
Sea ch). Ai line Sea ch has o be execu ed be o e
i (p ecedence).
Recei e Failed Ai line: A BM mus ecei e he ai-
lu e no i ica ion in he case i happens. I is in-
ol ed in he same ela ion ha Recei e Failed
Ho el, bu ega ding he ai line ac i i ies.
Compensa ion: A Sec e a y mus s udy he compen-
sa ion o he clien . This ac i i y has o be p e-
ceded o a leas one o Recei e Failed Ho el o
Ai line (b anched p ecedence ela ion). I can no
be execu ed a e nei he Ho el Sea ch no Ai line
Sea ch (no esponse).
No i y Failu e: A Sec e a y mus epo he ailu e.
I has o be p eceded by Compensa ion.
C edi Ca d: A Sec e a y p oceed o make he pay-
men . One o Book Ho el o Book Ai line has o be
execu ed be o e i (b anched p ecedence). Also,
a e Book Ho el and Book Ai line, i mus be exe-
cu ed ( esponse ela ions). One and only one o
No i y Failu e and C edi Ca d mus be execu ed
(no co-exis ence and mu ual subs i u ion). Also,
a e C edi Ca d, nei he Ho el Sea ch no Ai line
Sea ch can be execu ed (no esponse).
No i y Booked: A Sec e a y mus epo he in o -
ma ion abou he book o he clien . A e he exe-
cu ion o C edi Ca d, i mus be execu ed always,
and be o e i s execu ion, C edi Ca d mus ha e
been execu ed also (succession).
BPMN Elemen s
Exclusi e
Da a-Based
Ga eway
S a E en  End E en 
Pa allel
Ga eway
Figu e 6: Some BPMN elemen s.
Fo his example, a pa o he PDDL 2.2 domain
is shown in Fig. 4, including all he aspec s excep
ha only a ep esen a i e ac i i y (C edi Ca d) is spe-
ci ied as an example. Also, he PDDL 2.2 p oblem
speci ica ion is shown in Fig. 5. Taking he PDDL
2.2 speci ica ion as inpu , he planne sol es he p ob-
lem gene a ing he op imum execu ion plan: alloca -
ing he a ailable esou ces and empo a ily assigning
he s a and he end imes o he ac i i ies execu ion.
This plan can be used o guide he BP model design.
The Business P ocess Modelling No a ion
(BPMN) (Whi e and e al., 2004) is a s anda d o
modelling BP lows and web se ices, and p o ides
a g aphical no a ion o speci ying BP in a Business
P ocess Diag am (BPD). The BPD is composed, be-
ween o he s, by e en s, ga eways (Fig. 6), ac i i ies
and swimlanes. An e en ep esen s some hing ha
happens du ing he enac men o a BP and a ec s i s
execu ion low, speci ically he s a e en ini ia es
he low o he p ocess, while he end e en inishes
his low. Ga eways a e in cha ge o con olling
how sequence lows in e ac as hey con e ge o
di e ge wi hin a p ocess, speci ically he exclusi e
da a-based ga eway can be used as a decision poin
o as a way o me ge se e al sequence lows in o one;
while he pa allel ga eway p o ides a mechanism
o o k and synch onize he lows. Swim lanes a e
g aphic ways o o ganizing and ca ego izing he BP
ac i i ies, speci ically pools ep esen he pa icipan s
in a BP, and lanes a e used o o ganize he ac i i ies
wi hin a pool acco ding o oles o esou ces.
Taking in o accoun he PDDL 2.2 solu ions, an
op imized and easible BPMN can be designed (Fig.
7). I is composed by a pool named T a el Company
ha con ains h ee lanes, BM1, BM2 and S. In Fig. 7,
RFA is a boolean ha ep esen s a ail gi en du ing
he booking o he ai line, while RFH ep esen s he
same o he ho el booking.
5 CONCLUSIONS AND FUTURE
WORK
This wo k p oposes a PDDL 2.2 model o he op-
imal BP execu ion plan gene a ion when speci ying
he p ocess in o ma ion in a decla a i e way, apply-
ICAART 2011 - 3 d In e na ional Con e ence on Agen s and A i icial In elligence
568
T a el Company
Recei e
Reques 
Ho el
Sea ch
Ai line
Sea ch
Failed
Ho el
Book
Ho el
RFH
!RFH
Book
Ai line
Failed
Ai line
!RFA
RFA
C edi 
Ca d
Compen
sa ion
No i y
Booked
No i y
Failu e
RFH
BM1BM2 S
Figu e 7: BPMN o he Acme T a el Company.
ing an AI-based planning and scheduling app oach o
conside esou ces alloca ion and he minimiza ion o
he plan du a ion. The BP in o ma ion is p o ided
h ough a iendly g aphic language (ConDec-R).
As u u e wo k, i is in ended o de elop a ool
o he au oma ic gene a ion o p ocess models om
PDDL 2.2 plans. Fu he mo e, he use o di e en
AI-based app oaches o gene a e p ocess models om
decla a i e speci ica ions will be analyzed.
ACKNOWLEDGEMENTS
This wo k has been pa ially unded by he Con-
seje ´
ıa de Inno aci´
on, Ciencia y Emp esa o Jun a
de Andaluc´
ıa (P08-TIC-04095) and by he Span-
ish Minis e io de Ciencia e Inno aci´
on (TIN2009-
13714) and he Eu opean Regional De elopmen
Fund (ERDF/FEDER).
REFERENCES
Ba ba, I. and Del Valle, C. (2010). Planning and schedul-
ing o business p ocesses in un- ime: A epai plan-
ning example. In P oceedings o he 19 h In e na-
ional Con e ence on In o ma ion Sys ems De elop-
men (ISD 2010). Sp inge (in p ess).
B ucke , P. and Knus , S. (2006). Complex Scheduling
(GOR-Publica ions). Sp inge -Ve lag New Yo k, Inc.,
Secaucus, NJ, USA.
Cla ke J ., E., G umbe g, O., and Peled, D. (1999). Model
Checking. The MIT P ess.
Dean, T., Kaelbling, L. P., Ki man, J., and Nicholson, A. E.
(1995). Planning unde ime cons ain s in s ochas ic
domains. A i . In ell., 76(1-2):35–74.
Fahland, D., Mendling, J., Reije s, H., Webe , B., Wei-
dlich, M., and Zugal, S. (2010). Decla a i e e sus
impe a i e p ocess modeling languages: The issue o
main ainabili y. Lec u e No es in Business In o ma-
ion P ocessing, 43 LNBIP:477–488.
Ghallab, M. and e al. (1998). Pddl - he planning domain
de ini ion language. Technical epo , CVC TR-98-
003/DCS TR-1165.
Ghallab, M., Nau, D., and T a e so, P. (2004). Au oma ed
Planning: Theo y and P ac ice. Mo gan Kau mann,
Ams e dam.
Gonz´
alez-Fe e , A., Fe n´
andez-Oli a es, J., and Cas illo,
L. (2009). Jabbah: A ja a applica ion amewo k o
he ansla ion be ween business p ocess models and
h n. In In e na ional Compe i ion on Knowledge En-
ginee ing o Planning ICKEPS.
Ho mann, J. and Edelkamp, S. (2005). The de e minis-
ic pa o ipc-4: an o e iew. J. A i . In . Res.,
24(1):519–579.
Kea ney, P., Bo ajo, D., Ces a, A., Ma ino, N.,
and Mehandjie , N. (2003). Plane wo k-
low managemen &d oadmap. h p://
scalab.uc3m.es/∼dbo ajo/plane /wm- cu/Roadmap-
WM-phase-II.pd .
Pesic, M. and an de Aals , W. M. P. (2006). A decla a i e
app oach o lexible business p ocesses managemen .
In Business P ocess Managemen Wo kshops, pages
169–180. Sp inge .
Snell, J. (2002). Au oma ing business p ocesses and
ansac ions in web se ices: An in oduc ion o
bpelws, ws-coo dina ion, and ws- ansac ion. h p://
www.ibm.com/de elope wo ks/webse ices/lib a y/
ws-au obp/.
an de Aals , W. M. P. and Pesic, M. (2006). Decse low:
Towa ds a uly decla a i e se ice low language. In
LNCS 4184, pages 1–23.
an de Aals , W. M. P., e Ho s ede, A. H., and Weske, M.
(2003). Business p ocess managemen : A su ey. In .
Con . BPM 2003, P oceedings, pages 1–12.
Whi e, S. and e al. (2004). Business P ocess Modeling
No a ion (BPMN), Wo king d a , Ve sion 1.0.
A PLANNING AND SCHEDULING PERSPECTIVE FOR DESIGNING BUSINESS PROCESSES FROM
DECLARATIVE SPECIFICATIONS
569