Large socio-technical systems are complex to comprehend in their entirety because information exchanges between system components lend an emergent nature to the overall system behaviour. Although Individual system component behaviour may be known at the outset, such components may exhibit uncertainty and further exacerbate issues of a priori prediction of the overall system behaviour. Multi-agent systems and the use of simulation is a possible recourse in such situations however, simulation results need to be correctly interpreted so as to nudge the overall system behaviour towards a desired objective. We propose a solution wherein the system is modelled as a set of actors exchanging messages, a simulation engine producing execution trace for an actor as its history, and a querying mechanism to identify patterns that may span across individual actor histories to ascertain property of the overall system. The proposed solution is evaluated using a representative sample from real life.
Organisations and socio-technical systems can be simulated using MultiAgent Systems [5,10,9] where such a model of an organisation is constructed in terms of independent goal-directed agents that concurrently engage in tasks, both independently and collaboratively forming an executable model that produce simulation results representing the organisation. A key aspect is analysis of simulation outputs [6]. An important reason for using agents for simulation is that the systems of interest are complex, for example because they involve socio-technical features [8]. As a result, the simulations exhibit emergent behaviour that must be analysed in a variety of initially unforeseen ways in order to construct models that explain features of interest. Such analysis may be used to validate the simulation model by comparing it against observable truth, may be used to sense-check the results of the simulation, or may be used to guide modi cations to the simulation model so that it better meets the original requirements.
Our work on simulation has led to the design of a simulation workbench built around an actor language [11] called ESL [4]. The language ESL is used to construct agent-based simulation models that are run to produce histories. Each history contains a sequence of events produced by the behaviour of the agents in the simulation and thereby captures their emergent behaviour. A history is a temporal database of facts describing the states of, and communications between, agents in the simulation.
The challenge is to provide a suitable technology that allows the temporal database to be interrogated in order to support the sense-making described above. We describe an approach to the construction and interrogation of simulation histories. History construction is achieved by extending the standard operational actor model of computation [7] in order to capture temporal events during simulation execution. History interrogation is achieved by extending standard logic programming with temporal operators that are de ned in terms of a supplied history containing time-stamped events.
The approach is de ned in terms of meta-interpreters for both construction, in section 2, and interrogation, in section 3. The approach has been implemented by extending the ESL language with history and interrogation features; the implementation is brie y described in section 4 and used to implement and interrogate the simulation of a retail shop. 2
An agent-based simulation model consists of agents, each of which has local knowledge, goals and behaviour. Such a model can be operationalised in terms of the actor model of computation whereby each actor has an independent thread of control, has a private state and communicates with other actors via asynchronous messages to either update a local variable or change behaviour.
ESL is a text-based language that compiles to an actor-based VM. Actor behaviour can be represented using state machines as shown in gure 1 where gure 1(a) is a state machine representation of the ESL actor de nition in gure 1(b). The rest of this paper will use state machine representation for actors with transitions between states labelled M[Q]/A where M is a message, Q is a guard condition, and A is an action. Note that not all ESL programs can be represented as state machines, however this is su cient for the behaviours considered in this paper.
Figure 2 shows a model of actor program states that is suitable to dene the construction of histories. The model is expressed as a collection act name(x:Int)::B { export a; // public interface . a::Int = 0; // public variable . b::A = new A(x); // initialised local. s::State = S0; // state variable .
M1(y::Int) // message handler .
when s = S0 and
a < 10 // message guard. ! {a := a + 1; //// umpedsastaege vaarcitiaobnle..
s := S1; // change state. b M2(y -1); // send message .
b := new A(x+1) // actor creation . } M1(y::Int) when s = S1 !
s := s0 } (a) Actor Machine (b) ESL Actor of ESL type de nitions. All details relating to how variables are managed within an actor has been elided and can be understood in terms of standard operational models of programming languages. The term State( a,db,t) represents the state of an executing actor con guration where a is a set of actors, db is a history database, and t is the current time. We are interested in specifying how db is constructed through the conventional operational semantics of actors. This is achieved by de ning a single-step operational semantics: s2=step(s1) where system state s1 performs an execution step in order to become state s2. The complete execution of a system can be constructed by repeated application of step.
It is useful in simulations to be able to refer to global time via a clock. This can be used to schedule future computation or to allow actors to perform joint actions. To support the notion of global time, each actor in our operational model receives a regular Time message where each global time unit is measured in machine instructions. This mechanism seems to be fair and, although is not related to real-time, provides a basis for time that is useful in a simulation. To support this, each actor has an instruction count that, when reached, halts the actor. When all actors have been halted, global time is increased, and a message is sent to all actors.
A history database db is created from an initial con guration of actors a by repeated application of step until a terminal state is achieved such that all actors are exhausted and have no pending messages, db=run(a): isTerminal :: (ESL) ! Bool; isTerminal(State(a,_,_)) = allTerminated(a); allTerminated :: (Set{Actor}) ! Bool; allTerminated(set{}) = true; allTerminated(set{a | as}) = isTerminated(a) and allTerminated(as); isTerminated::(Actor) ! Bool; isTerminated(Machine(_,[],_,[],_)) = true; isTerminated(_) = false; run::([Actor ]) ! DB; run(a) = repeat(step ,State(a,[],0),isTerminal)
Summarising, a history is a collection of facts of the form Fact(t,f) where t is a timestamp and f is a term representing an actor execution step. The next section describes how the histories are interrogated using a temporal extension to standard relational programming. 3
Simulations consist of many autonomous agents with independent behaviour and motivation. Consequently, system behaviour is di cult to predict. Furthermore, the highly concurrent nature of the actor model of computation makes the simulation di cult to instrument in order to detect situations of interest. Therefore, we propose the construction of simulation histories as a suitable approach to simulation interrogation. Given such a history we would like to construct queries that determine whether particular relationships exist, where the relationships are de ned in terms of the key features of actor computation. Logic programming, as exempli ed by Prolog, would seem to be an ideal candidate for the construction of such queries, however standard Prolog does not provide intrinsic support for expressing the temporal features of the histories that are generated in section 2.
This section describes a variation on standard Prolog that incorporates both temporal features and simulation histories. The logic programming language is presented as a meta-interpreter written in a nontemporal subset of itself that is a statically typed version of Prolog: append [T] :: ([T],[T],[T]); append [T]([] ,l,l) !; append [T]([x|l1],l2 ,[x|l3 ])
append [T](l1 ,l2 ,l3); length [T] :: ([T],Int); length [T]([] ,0) !; length [T]([h|t],n)
length [T](t,m), n := m + 1; member [T] :: (T ,[T]); member [T](x ,[x|_]); member [T](x ,[_|l]) member [T](x,l); subset [T] :: ([T],[T]); subset [T]([] ,[]); subset [T]([x|l],[x|s])
subset [T](l,s); subset [T](l,[_|s])
subset [T](l,s); lookup [V] :: (Str,V,[ Bind(Str,V)]); lookup [V](n,v ,[ Bind(n,v) | _]); lookup [V](n,v ,[_|env ]) lookup [V](n,v,env); The examples above are standard Prolog rules that have been elaborated with static type information that is checked by the ESL Workbench before execution. The rules length and member use parametric polymorphism over the type T of elements in a list. The rule lookup is parametric with respect to the type of the bindings in the environment list.
The rules shown above do not reference simulation history facts. In order to support rules over histories we introduce new rule features based on temporal logic. The following data type Body describes the elements that can occur in a rule body: data Value = Term(Str,[ Value ]) | Var(Str) | I(Int) | S(Str); data Body = Call(Str,[ Value ]) | Is(Str, Value) | Start | End | Next ([ Body ]) | Prev ([ Body ]) | Always ([ Body ]) | Eventually ([ Body ]) | Past ([ Body ]) | Forall ([ Body],Value , Value ); The terms Call and Is represent standard Prolog body elements; all other elements are extensions to standard Prolog. The extensions all relate to current time which is the time-stamp associated with the facts in the history: type Time = Int; type Entry = Fact(Time ,Str,[ Value ]); type DB = [Entry ]; Elements Start and End are satis ed when the current time is 0 and the end of the history respectively. An element Next(es) is satis ed when the elements es are satis ed in current time +1, similarly Prev(es) in current time 1. An element Always(es) is satis ed when the elements es are satis ed at all times from now, similarly Past(es) all times before now. Element Eventually(es) is satis ed when es are satis ed at some time in the future.
Figure 3 de nes a meta-interpreter for the history query language. Given a query q(v1,: : :,vn), a program prog, a database db and a history end time t, the query is satis ed when call(0,t,db,'q',[v1,: : :,vn],prog) is satis ed with respect to the de nitions given in gure 3.
The meta-interpreter is based on a standard operational semantics for Prolog that is extended with features to process the supplied database (the de nition of Forall is omitted, but is consistent with standard Prolog). The rule call is used to process a body element of the form Call(n,vs) where n is the name of a fact and vs are the arguments. Conventional Prolog processes such a call using the de nition of call de ned on lines 11 { 16 where a rule named n with an appropriate arity is found in the program and is supplied with the argument values using matchs.
Figure 3 extends conventional Prolog rule calling by allowing the fact to be present in the history at the current time (lines 9-10). Therefore, the facts in the history become added to the facts that can be conventionally deduced using the rules.
The semantics of the additional types of body elements are processed by the try rule (lines 89{115) by modifying the value of the current time appropriately, For example, the rule for Next (lines 91{94) fails if the end of the history has been reached, otherwise it attempts to satisfy the elements es after incrementing the current time by 1.
An example rule is customers where customers(cs) is satis ed when cs is a list of all the customer actor identi ers in the history: 1 customers :: ([Int]); 2 customers ([]) end , !; 3 customers(cs) 4 forall[actor(a,'customer ',_)](a,cs '), next[customers(cs '')], 5 append[Int](cs',cs'',cs);
Line 2 de nes that there can be no customers if we are at the end of the history. Lines 3{5 de ne how to extract the customer identi ers from this point in the history: line 4 uses forall to match all database facts of the form actor(a,'customer',_) where this fact has been added to the database when a new customer actor is created. Then, next is used to advance the time so that cs'' are all the customer actors from this point onwards. 4
We have described an approach to constructing and interrogating agentbased simulation histories. History construction is de ned by identifying the key operational features of the actor model of computation and then extending an actor interpreter with a database of temporal facts, each of which is based on a key operational feature. History interrogation is performed by extending a standard Prolog interpreter with language features for processing the facts in a temporal database. The approach has been implemented within ESL where we have extend the ESL VM to produce histories and then integrated a query language, a Prolog VM extended with features to process histories (as de ned in section 3).
This section provides an overview of the implementation, describes a simulation that produces a history, and shows how the query language can interrogate the history. 4.1
ESL compiles to a virtual machine that is similar to the Java VM where actors are the equivalent of objects. The ESL VM manages a history that is automatically updated when actors are created, change behaviour, updated and send messages. Given the scale of simulations, it is important that the history is represented as e ciently as possible, both for construction and interrogation. Figure 4 shows the Java classes that are used to implement the history.
Once constructed, a history is interrogated by the ESL query language that compiles to a VM which is based on a standard Warren Abstract Machine [14].
In a WAM, Choice-points are represented as pointers into a frame on a fail stack. The ESL query language VM extended the fail stack with a new form of fail-frame that indexes the history. For example, a query actor (a,b,t) relates to actor creation events where a is the unique identi er, b is the behaviour, and t is the time, any of which may be logic variables. Therefore the query potentially represents a choice point. The VM creates a fail-frame corresponding to the choice point and indexes the 0-th fact that matches the supplied values, if this subsequently fails by returning to the fail-frame, then the index is incremented. A history is any Java object that implements the following interface which is used by the call and fail mechanism within the VM: 1 public interface DB { 2 boolean hasFact(String name ,int arity ,int time ,int index ,Machine machine); 3 Object getFactArg(String name ,int arity ,int time ,int index ,int argNumber ,Machine machine ); 4 int endOfTime (); 5 }
The method hasFact is used by the query VM when performing a call to determine whether the hitsory database contains a fact corresponding to the call. The rst time this occurs the supplied index is 0. If this succeeds then the VM constructs a fail-frame that captures the name, arity, time and the next index: 1. Each time the fail-frame is used for backtracking, the index is incremented. The method getFactArg is used to extract the individual fact arguments and subsequently unify them in the query VM. 4.2
In this paper we use a case study that is based on existing work on agentbased organisation simulations [12] and as such is seen as a reference example. The case study will be used to demonstrate the construction of an agent model that produces a history and the subsequent interrogation via a query. The query is chosen to demonstrate the utility of logic programming using the ESL query language and will also be analysed in terms of its e ciency based on the implementation described in the previous section.
Case study description: A shop provides stock on the shop- oor. Customers enter the shop and may browse until they either leave, seek help or decide on a purchase. Items must be purchased at tills and multiple customers are serviced via a queue. Shop assistants may be on the shop- oor, helping a customer or may service a till. A queueing customer can only make a purchase when they reach the head of a queue at a serviced till. A customer who waits too long at an unserviced till, or for whom help is not available, will become unhappy and leave the shop. The shop would like to minimise unhappiness. In addition the shop owner has noticed that stock is going missing. A criminal gang is known to be operating in the area. Typically they operate by engaging all the assistants in a shop whilst one of the gang members leaves the shop without paying for the goods.
An ESL simulation can be modelled using structure and behaviour diagrams which are variations on class and state machine diagrams respectively. The structure of the shop simulation is shown in gure 5 in which we make the distinction between behaviour types and behaviours. The di erence between these two concepts corresponds to the di erence between software module types and modules in that a behaviour type is an interface de nition and a behaviour provides an implementation of the interface. There may be many actors that are instances of the same behaviour.
The model shown in gure 6 organises a shop as a collection of customers, assistants and tills. Each till is an actor that is associate with a sequence of transactions, also represented as actors. Each transaction may be serviced by sending it a Do message, or may be delayed, by sending it a Wait message. When a transaction is successfully terminated the corresponding actor will change its behaviour to transacted which means that it acts as a proxy for the next transaction in the queue.
In addition to normal customers, the simulation represents a special type of customer called gangMember. These unscrupulous actors are organised by a gang leader to occupy sales assistants in order that the leader can steal merchandise. We will not explicitly consider the behaviour of the gang leader, however we will be interested in examining the simulation history in order to detect potential gang member behaviour.
Figure 6 shows the behaviour de nitions for the shop simulation actors. The simulation is driven by Time messages and all actors implement a Time transition for all states; the empty transitions arising from Time are omitted. Time is used in gure 6(g) to show how customers waiting at a till can time out and ultimately leave the shop. The value supplied to a (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 transaction is tLim which determines how long a customer is prepared to wait without a sale being concluded.
Customers who leave the shop because they have waited too long to be serviced at a till are deemed to be unhappy. the shop is interested in how to organise its assistants, sales and oor-walking strategies in order to minimise unhappy customers. Figure 7 shows the ESL Workbench output from two di erent simulation con gurations. The Workbench can generate a display based on actor states during the simulation, gure 7 shows the nal output. Figure 7(a) shows the result of 10 customers, 5 tills and 3 sales assistants where roughly 75% of the customers are left unhappy. The number of assistants has been increased to 5 in gure 7(b) where the situation is reversed. note that the simulation has many (a) Shop with 10 Customers, 5 Tills and 3 Assistants (b) Shop with 10 Customers, 5 Tills and 5 Assistants random elements and therefore each run is di erent, but the two outputs characterise the relative di erences. 5
Simulation of multi agent systems (MAS) is quite close to the problem we are addressing. Several simulation approaches have been suggested but none seem to address the querying need. In [2], Bosse et al. present a generic language for the formal speci cation and analysis of dynamic properties of MAS. This language supports the speci cation of both qualitative and quantitative aspects, and therefore subsumes speci cation languages based on di erential equations. However, this is not an executable language. In fact, it has been specialised for simulation domain leading to LEADSTO language[3]. The LEADSTO is essentially a declarative order-sorted temporal language extended with quantitative notions (like integer, and real). Time is considered linear, continuous, described by real values. Dynamics is modelled as direct temporal dependencies between state properties in successive states. Though quite useful in specifying simulations of dynamic systems, it does not provide any help in querying the resultant behaviour. Bosse et al. further propose a multi-agent model for mutual absorption of emotions to investigate emotion as a collective property of a group using simulation[1]. It provides mathematical machinery to validate a pre-de ned property over simulation trace. However, there is no support for temporal logic operators in specifying a property.
Sukthankar and Sycara, in contrast, propose an algorithm to recognize team behaviour from spacio-temporal traces of individual agent behaviours using dynamic programming techniques[13]. Though quite close as regards the solution space, this result lays strong emphasis on team behaviour thus hinting collaboration. Our proposed machinery is neutral to the nature of environment - collaborative or competitive or both. Vasconcelos et al. present mechanisms based on rst-order uni cation and constraint solving techniques for the detection and resolution of normative con icts concerning adoption and removal of permissions, obligations and prohibitions in societies of agents[15]. Though we too propose Prolog based realisation for querying generated histories, our focus is more quantitative. 6
In this paper, we have sought to address the challenge of analysing simulations that exhibit emergent behaviour for unforseen conditions. Our basic architectural approach to this problem was to extend our actor based language ESL with a Prolog based meta interpreter that is able to execute queries over simulation histories. The extensions to ESL and the Prolog variant include new rule features based on temporal logic that reference simulation history facts that are both global across the system or local to speci c actors within the system. The technology was evaluated using a reference case study. While we recognise the limitations of such an evaluation approach, the case study is su ciently realistic in generating rich and complex simulation histories. Our long-term goal for this research is the construction of robust, scaleable, encompassing technology that complex dynamic decision making situations that deal with uncertainty and emergent behaviour. 4. Tony Clark, Vinay Kulkarni, Souvik Barat, and Balbir Barn. Actor monitors for adaptive behaviour. In Ravi Prakash Gorthi, Santonu Sarkar, Nenad Medvidovic, Vinay Kulkarni, Atul Kumar, Padmaja Joshi, Paola Inverardi, Ashish Sureka, and Richa Sharma, editors, Proceedings of the 10th Innovations in Software Engineering Conference, ISEC 2017, Jaipur, India, February 5-7, 2017, pages 85{95. ACM, 2017. 5. Jacques Ferber and Olivier Gutknecht. A meta-model for the analysis and design of organizations in multi-agent systems. In Multi Agent Systems, 1998. Proceedings.
International Conference on, pages 128{135. IEEE, 1998.
6. Paul A Fishwick. Computer simulation: growth through extension. Transactions
of the Society for Computer Simulation, 14(
arXiv preprint arXiv:1008.1459, 2010.
8. Tom McDermott, William Rouse, Seymour Goodman, and Margaret Loper.
Multilevel modeling of complex socio-technical systems. Procedia Computer Science,
16:1132{1141, 2013.
9. Geo rey P Morgan and Kathleen M Carley. An agent-based framework for active
multi-level modeling of organizations. 2016.
10. David V Pynadath and Milind Tambe. An automated teamwork infrastructure for
heterogeneous software agents and humans. Autonomous Agents and Multi-Agent
Systems, 7(
De nite programs. In ILPS, pages 633{652. Citeseer, 1994.
15. Wamberto W Vasconcelos, Martin J Kollingbaum, and Timothy J Norman.
Normative con ict resolution in multi-agent systems. Autonomous Agents and
MultiAgent Systems, 19(