A Planning and Scheduling Perspective for Designing Business Processes from Declarative Specifications

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