Generating Filmstrip Models from Actor-Based Systems Tony Clark Vinay Kulkarni, Souvik Barat Balbir Barn Sheffield Hallam University Tata Consultancy Services Research Middlesex University Sheffield, United Kingdom Pune, India London, United Kingdom T.Clark@shu.ac.uk {Vinay.Vkulkarni,Souvik.Barat}@tcs.com B.Barn@mdx.ac.uk Abstract—Actor-based systems are hard to analyse the actor structure and their individual behaviours. because of their inherent complexity arising from The structure is equivalent to a class diagram and large=scale concurrency and stochastic behaviour. the behaviour of each actor is defined as a state- History traces can be produced from such a system that describes what happened during execution lead- machine driven by the messages received by the as- ing to a challenge as to how the traces are processed. sociated actor. The models are translated into code This tool demonstration shows a novel actor-based that is executed to produce a knowledge-base that language ESL and its development environment EDB contains time-stamped actor-states. Mapping rules that has been extended to produce histories stored in are used to process the knowledge-base, producing temporal databases, and to use a logic programming language to construct graphical filmstrips from the a sequence of diagram models that are displayed databases. as a filmstrip. The user can then play the filmstrip Index Terms—Agent-based modeling backwards and forwards. The rest of this paper is structured as follows: I. I NTRODUCTION section II describes a simple case study that is modelled in section III; section IV describes the EDB (the ESL DeBugger) is a tool that supports ESL implementation of the simulation model and the analysis of simulation behaviours. Simulations the production of a knowledge-base; section V are represented as executable agent models repre- shows how the knowledge-base is transformed into sented using the actor-language ESL (Executable filmstrips and how they are displayed by EDB. Simulation Language). This demonstration shows Section VI places ESL and EDB in relation to other how agent models are represented in EDB and work. how executions can be captured as time-stamped facts in a knowledge-base. ESL supports logic programming in the form of rule-sets that are pa- rameterised with respect to knowledge-bases. The logic programming language provides temporal op- erators that are used to map temporal knowledge- bases to filmstrips. EDB provides graphical features for displaying and playing filmstrips forwards and backwards. We demonstrate these features using a simple case study involving customers in a shop. Figure 1 describes the overall EDB-based process for creating and interacting with filmstrips arising from actor-based simulation models represented in ESL. A simulation model is defined in terms of Fig. 1. Overall Process II. C ASE S TUDY III. I NPUT M ODELS Figure 2 shows a case study that is taken from ESL is a statically typed actor language. Actors [10]. A shop provides stock on the shop-floor. have behaviour types that are equivalent to com- Customers enter the shop and may browse until ponent interface types, and have behaviour defi- they either leave, seek help or decide on a purchase. nitions that are equivalent to module definitions. Items must be purchased at tills and multiple cus- Actor behaviour in ESL is implemented as message tomers are serviced via a queue. Shop assistants handling rules that can be generated from state may be on the shop-floor, helping a customer or machines. This section outlines the behaviour type may service a till. A queueing customer can only (structure) and behaviour (state-machine) models make a purchase when they reach the head of a that are derived from the case study. Figure 3 shows queue at a serviced till. A customer who waits too the behaviour types for the shop simulation. In long at an unserviced till, or for whom help is not addition to domain actors such as customer and assistant, the transactions at a till are represented available, will become unhappy and leave the shop. The shop would like to minimise unhappiness. as actors. Figure 4 shows the behaviour of the actors In addition the shop owner has noticed that stock represented as state machines. An actor receives is going missing. A criminal gang is known to be messages that are either sent by other actors or operating in the area. Typically they operate by are Time messages produced automatically by ESL. engaging all the assistants in a shop whilst one of Optionally, an actor can replace its behaviour when the gang members leaves the shop without paying it handles a message, for example this occurs in for the goods. figure 4(c) where a customer joins a till-queue. An actor-based implementation of the case study IV. ESL I MPLEMENTATION will necessarily have stochastic behaviour and therefore be difficult to verify. A formal approach ESL is a statically typed text-based language. to verification is often challenging to achieve due to Actor models, such as those described in the previ- the state explosion when simulations become large. ous section, are translated into ESL. EDB provides Furthermore, interacting with a running simulation support for ESL development in the form of static or producing printed output can either change the type checking. The following code fragment shows behaviour or overwhelm the developer. Our ap- how the shop models are translated into ESL. proach compliments such approaches by providing d a t a State = NotInShop( I n t ) | Browsing( I n t ) | Queuing( I n t , I n t ) a graphical representation of the simulation that can | SeekingHelp( I n t ) | GettingHelp( I n t , I n t ) be post-processed. | OnFloor( I n t ) | GoTill( I n t ) | AtTill( I n t , I n t ) | Helping( I n t , I n t ) | Raid | NoRaid; t y p e Customer = Act { e x p o r t state::State; getId::() → I n t ; help::(Assistant) → Void; Time( I n t ); SaleConcluded(); SaleTimedOut(); Helped() } t y p e Facts = KB[State]; facts::Facts = kb[Facts]{ NoRaid }; a c t customer(id:: I n t ,tills::Tills)::Customer { state::State = NotInShop(id); getId():: I n t = id; counter:: I n t = 0; helpedBy::Assistant = n u l l ; Time(n:: I n t ) when state = NotInShop(id) → Fig. 2. Shopping Simulation (Based On [10]) p r o b a b l y (probOfEnteringShop) { Fig. 3. Structure of Shop Actors state := Browsing(id); in the knowledge-base. facts.add(state,time++); } } V. F ILMSTRIP G ENERATION Actor states are defined as an algebraic data Filmstrips are produced by translating temporal type State as shown above. The states are used knowledge-bases into sequences of pictures. This is to control the behaviour of the actors and are achieved in a two-stage process: (1) the knowledge- also recorded in a knowledge-base for subsequent base is translated into a sequence of system states; processing by the filmstrip mapping rules. (2) each state is translated into a picture. Both Each actor has a behaviour type definition such as stages are performed using the features of ESL: (1) Customer containing the operation and message sig- temporal logic programming; (2) functional pattern nature. All message names are implicitly exported, matching. Mapping from a knowledge-base to a property names and operations are local in any sequence of system states is performed using the behaviour implementation unless they are exported rules shown in figure 5 where a history is created by the type. as a sequence of shop-states as defined by the rule The knowledge-base facts conforms to the type hist which is supplied with customer, assistant State and therefore contains time-stamped state and till identifiers. The hist rule uses the temporal information. operator next to step through the knowledge-base. At The behaviour definition customer shows a frag- each time-step, the rule state is used to construct a ment of the implementation of the customer be- shop-state. The rules in figure 5 show how the cOut haviour defined in figure 4. All actors in ESL are and raid components of the shop-state are extracted supplied with Time messages at regular intervals from the knowledge-base. A raid is detected by in order to drive the simulation. The customer rule isRaid when there is a current Raid state behaviour shows a message handler that responds recorded in the knowledge base; notice that is may to a Time message that occurs when the customer be necessary to step backwards in time through the is not in the shop and has a given probability of facts in the knowledge-base before the appropriate entering. Note how the change of state is recorded fact is found. The identifiers of customers who (a) Assistant Behaviour (b) Customer Behaviour (c) No Transactions Behaviour (d) Transacted Behaviour (e) No Tills Behaviour (f) A Till Behaviour (g) A Transaction Behaviour Fig. 4. Shop Actor Behaviour are currently outside the shop is calculated by the | Line( I n t , I n t , I n t , I n t , S t r ) | Image( I n t , I n t , I n t , I n t , S t r ) call getCStates(n,cIds,cOut) which extracts the | Text( I n t , I n t ,Str , S t r ) nth customer state and filters the list of customer t y p e Pics = [Picture( I n t , I n t ,[PictureElement])]; t y p e EDB = Act { identifiers for those customers currently in that Filmstrip(Str ,Pics) state. The calculation uses the rule recent to ensure } that the desired state is the most recent: this will be false if the particular customer is most recently The data type above shows the different picture in an alternative state. A fact f is currently in the elements that can be drawn on each frame of a film- knowledge-base if fact(f) is true. strip. The message Filmstrip(title,pictures) displays the sequence of pictures with a slider that t y p e PictureElement = Rectangle( I n t , I n t , I n t , I n t , S t r ) can be used to move forwards and backwards; mov- | Circle( I n t , I n t , I n t , S t r ) ing the slider changes the picture that is displayed. isRaid::( I n t ); t y p e Solver = Rules { isRaid(0) ← fact(NoRaid), !; hist([ I n t ],[ I n t ],[ I n t ],[ShopState]) isRaid(1) ← fact(Raid), !; }; isRaid(raid) ← prev[isRaid(raid)]; solver::Solver = rules { hist::([ I n t ],[ I n t ],[ I n t ],[ShopState]); getCStates::( I n t ,[ I n t ],[ I n t ]); hist(cIds,aIds,tIds,[s]) ← getCStates(_,[],[]) ← !; state(cIds,aIds,tIds,s), end, !; getCStates(n,[id|idsIn],[id|idsOut]) ← hist(cIds,aIds,tIds,[s|ss]) ← custStates(id,ss), state(cIds,aIds,tIds,s), !, nth[State](n,ss,s), n e x t [hist(cIds,aIds,tIds,ss)]; delete[State](s,ss,ss’), recent(id,s,ss’), !, custStates::( I n t ,[State]); getCStates(n,idsIn,idsOut); custStates(id,[NotInShop(id), getCStates(n,[id|idsIn],idsOut) ← Browsing(id), getCStates(n,idsIn,idsOut); SeekingHelp(id), GettingHelp(id,aId), recent::( I n t ,State,[State]); Queuing(id,tId)]); recent(id,f,fs) ← fact(f), !; recent(id,f,fs) ← facts(fs), !, f a l s e ; state::([ I n t ],[ I n t ],[ I n t ],ShopState); recent(id,f,fs) ← prev[recent(id,f,fs)]; state(cIds,aIds,tIds,Shop(cOut,f,b,h,t,raid)) ← isRaid(raid), facts::([State]); getCStates(0,cIds,cOut), facts([]) ← f a l s e , !; // extraction of f,b,h,t omitted. facts([f|fs]) ← fact(f), !; // listing continues in right-hand column. facts([_|fs]) ← facts(fs); } Fig. 5. Logic Rules for History Production toPicture(s::ShopState)::PictureElement = case s { Shop(cOut,aFloor,cBrowse,h,ts,raid) → l e t r e c customerOutside(ids::[ I n t ],x:: I n t )::[PictureElement] = i f ids = [] t h e n [] e l s e [Image(x,0,iconWidth,iconHeight,customerIcon), Text(x,(iconHeight+textHeight),head[ I n t ](ids)+’’,’’)] + customerOutside(tail[ I n t ](ids),x+iconWidth); ... i n Picture(pictureWidth,pictureHeight,customerOutside(cOut,0) + . . ) . }; show hist(cIds,aIds,tIds,history) from solver u s i n g facts { edb ← Filmstrip(’ShopFilmstrip’,[ toPicture(s) | s::ShopState ← history ]) } Fig. 6. Producing A Picture Once the simulation has completed and populated figure 7(c) shows customers have entered the shop the knowledge-base, the filmstrip is displayed by and started to browse and some are looking for help, sending a Filmstrip message to EDB. A rule-base notice also that gang members have also arrived; is paired with a knowledge-base using the show figure 7(d) shows a customer (5) queueing at till construct in EDB where show q from r using k 0, customers (2,3,6) are queueing at till 1 where c will try to establish fact q in rule base r us- assistant 1 is serving. ing knowledge-base k and then perform command c. Figure 6 shows a fragment of the function VI. R ELATED W ORK toPicture that maps system states to pictures using The use of MAS for system simulation has been pattern-matching functions. explored by a number of researchers, for example Interactions with the resulting filmstrip in EDB is in [5], [1], [9], [11], [4]. In [1], Bosse et al. shown in figure 7 where figure 7(a) shows the start present a generic language for the formal specifi- of time, figure 7(b) shows the situation after all the cation and analysis of dynamic properties of MAS customers and assistants have joined the simulation; that supports the specification of both qualitative (a) Start of Filmstrip (b) Customers and Assistants Arrive (c) Waiting for Help (d) Queuing and Being Served Fig. 7. Filmstrip Animation and quantitative aspects, and subsumes specification does not provide any help in animating the resultant languages based on differential equations. However, behaviour. Temporal logics have been used to spec- this is not an executable language. It has been ify the behaviour of MAS [3] and to analyse the specialised for simulation and has produced the specification for properties using theorem proving LEADSTO language [2] which is a declarative or model checking. Our approach uses a similar order-sorted temporal language where time is de- collection of temporal operators, however we are scribed by real numbers and where properties are applying the behaviour specifications post-hoc in modelled as direct temporal dependencies between order to investigate whether a given behaviour took properties in successive states. Though quite useful place. The need to analyse agent-based simulations in specifying simulations of dynamic systems, it is related to the field of agent-based system testing. As noted in [12] attempting to obtain assurance [5] Stephane Galland, Luk Knapen, Nicolas Gaud, Davy Janssens, Olivier Lamotte, Abderrafiaa Koukam, Geert of a system’s correctness by testing the system as a Wets, et al. Multi-agent simulation of individual mobility whole is not feasible. Our approach is intended to be behavior in carpooling. Transportation Research Part C: a pragmatic partial solution that is used selectively Emerging Technologies, 45:83–98, 2014. [6] Martin Kaufmann, Amin Amiri Manjili, Panagiotis Vage- in collaboration with a domain expert. Managing nas, Peter Michael Fischer, Donald Kossmann, Franz temporal data is becoming increasingly important Färber, and Norman May. Timeline index: A unified for many applications [7], [6]. Our work is related data structure for processing queries on temporal data in SAP HANA. In Proceedings of the 2013 ACM SIGMOD to process mining from the event logs that are International Conference on Management of Data, pages created by enterprise systems [8] where queries 1173–1184. ACM, 2013. can be formulated in terms of a temporal logic [7] Rudolf Kruse, Matthias Steinbrecher, and Christian Moewes. Temporal pattern mining. In Signals and and applied to data produced by monitoring real Electronic Systems (ICSES), 2010 International Conference business systems. on, pages 3–8. IEEE, 2010. [8] Margus Räim, Claudio Di Ciccio, Fabrizio Maria Maggi, R EFERENCES Massimo Mecella, and Jan Mendling. Log-based un- derstanding of business processes through temporal logic [1] Tibor Bosse, Catholijn M Jonker, Lourens Van der Meij, query checking. In OTM Conferences, pages 75–92. Alexei Sharpanskykh, and Jan Treur. Specification and Springer, 2014. verification of dynamics in cognitive agent models. In IAT, [9] Gabriel Santos, Tiago Pinto, Hugo Morais, Tiago M Sousa, pages 247–254. Citeseer, 2006. Ivo F Pereira, Ricardo Fernandes, Isabel Praça, and Zita [2] Tibor Bosse, Catholijn M Jonker, Lourens Van Der Meij, Vale. Multi-agent simulation of competitive electricity and Jan Treur. LEADSTO: a language and environment for markets: Autonomous systems cooperation for european analysis of dynamics by simulation. In German Confer- market modeling. Energy Conversion and Management, ence on Multiagent System Technologies, pages 165–178. 99:387–399, 2015. Springer, 2005. [10] Peer-Olaf Siebers and Uwe Aickelin. A first approach on [3] Nils Bulling and Wiebe Van der Hoek. Preface: Special modelling staff proactiveness in retail simulation models. issue on logical aspects of multi-agent systems. Studia J. Artificial Societies and Social Simulation, 14(2), 2011. Logica,(Special Issue), 2016, 2016. [11] Dhirendra Singh, Lin Padgham, and Brian Logan. Inte- [4] Philippe Caillou, Benoit Gaudou, Arnaud Grignard, grating BDI agents with agent-based simulation platforms. Chi Quang Truong, and Patrick Taillandier. A simple- Autonomous Agents and Multi-Agent Systems, 30(6):1050– to-use BDI architecture for agent-based modeling and 1071, 2016. simulation. In The Eleventh Conference of the European [12] Michael Winikoff and Stephen Cranefield. On the testa- Social Simulation Association (ESSA 2015), 2015. bility of BDI agent systems. J. Artif. Intell. Res.(JAIR), 51:71–131, 2014.