Hybrid ABM DEVS with MESA

[quaquel]

I have mentioned in various discussions the potential for hybrid ABM-Discrete Event scheduling. After finishing the new cell grid stuff and being a bit stuck on data collection, I decided to give it a go. The code uses ideas from the current devs scheduler and pydsol, which is a python port of the DSOL java library developed over the past 20 years by colleagues.

My draft code is here. The key classes are a new Simulator class (akin to a numerical integrator for ODEs, theoretically rooted in the work of Zeigler), the EventList, and SimEvent.

I also added so far 1 example: wolfsheep. The key thing is that I use ABM-style scheduling on the wolf and sheep.

    def step(self):
        self.get_agents_of_type(Sheep).shuffle(inplace=True).do("step")
        self.get_agents_of_type(Wolf).shuffle(inplace=True).do("step")
        self.simulator.schedule_event_relative(self.step, 1)

While the regrowth of the grass patches is handled through event scheduling. So, the grass patches are no longer activated each step to reduce a counter. Rather, I schedule events for when they are fully regrown.

    @fully_grown.setter
    def fully_grown(self, value):
        self._fully_grown = value

        if value == False:
            self.model.simulator.schedule_event_relative(self.set_fully_grown, self.grass_regrowth_time)

It is just a first rough example. I want to do Epstein's civil violence next, with jail time being handled through event scheduling. A key thing, however, is that wolf sheep on 100 ticks already has about half the runtime of the pure ABM implementation.

added 1: Currently, the core design uses next event time progression. To get AMB style behavior (i.e., incremental time progression), model.step schedules itself with a time increment of 1. A slightly more elaborate implementation might make this the default behavior for the ABMSimulator, while still allowing event scheduling. So, ABMSimulator schedules/always contains a model.step for each discrete time tick. From a user point of view, this might be more convenient.

added 2: I am slowly continuing to update the code. Incremental time progression has now been integrated, so in model.step it is no longer needed to schedule the next call to model.step. Moreover, I have given model.step events a higher priority so they always go first in a tick.

added 3: PR:

• support for discrete event scheduling #2066

[rht]

Existing discussions:

1. Initial proposal Enable DiscreteEventScheduler to handle system-level events and task interruptions #1893
2. Motivation NumFocus GSoC 2024 idea list #1997 (reply in thread)
3. Performance advantage of DEVS over ABM scheduling DEV SESSION [TUESDAY] 13 FEB -- 2130 UTC+8/1430 CET/1330 GMT/ 0830 EST #2027 (reply in thread)
4. Initial implementation (merged) Add DiscreteEventScheduler #1890

Will add more to the list when a new relevant / related discussion appears.
Note: I consent for the maintainers to edit this post for updating the list.

[rht]

Replying to #1997 (reply in thread)

Practically, it would involve a bit more than making a more comprehensive scheduler. Rather, it means rebuilding MESA on top of an EventTree. Practically, this might sound bigger than it. Zeigler makes a distinction between a model and a simulator. ...

Does DSOL/pydsol use the concept of EventTree? The term EventTree needs an elaboration itself, and I'm not sure if it is discussed in Zeigler 2018 either.

[quaquel]

pydsol uses "eventlist" instead of "event tree". So, I switched to using that as well. My original term in #1997 was simply incorrect.

Also, note that the formalism I use here is called event scheduling (see also Zeigler]

[Corvince]

Thank you @quaquel for putting this together!! Lots of interesting things in there and I am looking forward to diving into it

[EwoutH]

Some previous discussion, for reference:

• Add DiscreteEventScheduler #1890
• Enable DiscreteEventScheduler to handle system-level events and task interruptions #1893

It would be interesting how many goals from #1893 we can integrate.

[quaquel]

some quick thoughts

1. My implementation can cancel events, so this offers some basis upon which to build interruption. The key is that you need to know exactly which event to cancel.
2. My implementation allows you to schedule any callable, not just agent.step. So system level events are included by default. It might be possible/desirable to refine this. I currently only accept a callable, but you might make "AgentEvents" where you have the object (i.e., agent) and the method you want to schedule. This makes it easier to remove events belonging to a specific agent.
3. My implementation does not use weakrefs in contrast to DiscreteEventScheduler. So agent removal if they have still events scheduled won't work. Fixing this is straightforward and on my todo list.
4. Resumption logic seems more of an agent issue not an event scheduling issue.

[rht]

The list has been merged into #2032 (comment).

[wang-boyu]

I briefly discussed with my PhD advisor Andrew, and he likes the idea of making Mesa a hybrid simulation framework. Recently MASON (a JAVA ABM framework) has a discrete event simulation extension named MASON DES, aiming to provide such hybrid simulation modes (link to paper). There is a repository containing three example DES models (link to repo) but I couldn't find the source code for the DES extension. Perhaps it's not yet released.

For Mesa, I'm wondering if we'd like the DES part to be a separate extension (like MASON DES to MASON), or have it integrated within Mesa.

I just realized that there might be a slight difference between the goals. Do we want (1) just a discrete event scheduler, or (2) the capabilities to develop discrete event models in Mesa? For (1), we are still doing ABMs, but we can develop in DES-style; whereas (2) refers to a full-blown framework to do DES models (e.g., a queuing system).

[rht]

In what way is a flow library equipped with entities, etc, less expressive than an OOP discrete event framework? Is there a trade-off between expressiveness and performance? Is it similar to the situation with the current data collector being both not general and slow, and the new in-development API that is strictly better?

[rht]

For those with no institutional access to the MASON paper, here is a public link to it (or there is always Nexus Standard Template Construct, since Sci-Hub may be up, but has been frozen since 2020).

[quaquel]

You can think of a flow library as a domain-specific language. In a flow library, entities arrive in the system, are sent to queues, claim a resource/server for a specific time, release the resource, and flow to the next queue and server combination. This way of representing systems makes perfect sense for, e.g., modeling call centers or logistic systems. Typically, a flow library is also built on top of an event list, as presented here.

However, imagine building a microscopic discrete event simulation of cars on a highway or trams driving around a city. Here, you have objects (cars/trams) reacting to their environment and responding to this by accelerating and braking. All this is still easily expressible through event scheduling, but it makes no sense to express this through entities, queues, and processes. It can be done, as I know from personal experience, but it is torture.

Here's a nice historical fact: The first Object-oriented programming languages were discrete event simulation packages. OO emerged because of the "naturalness" of describing real-world phenomena for discrete event simulation. It was only later that computer scientists started to adopt OO ideas into the design of programming languages.

On the MASON paper, I read it yesterday. They talk about DES, but they really mean what I call a flow library. For example, they claim that DES cannot be used to model social phenomena. This is true for a flow library but is demonstrably not true for event scheduling in general.

[rht]

Here's a nice historical fact: The first Object-oriented programming languages were discrete event simulation packages. OO emerged because of the "naturalness" of describing real-world phenomena for discrete event simulation. It was only later that computer scientists started to adopt OO ideas into the design of programming languages.

That's even earlier than the earliest incarnation of modern OO paradigm in a programming language that I know of, Smalltalk (late 1960s), which views objects as tiny independent "computers" that interact with each other via message passing. Wikipedia said late 1950's was the earliest emergence the concept among the computer scientists.

Though to me, DEVS is more naturally described with message passing (which could be bidirectional) than pub-sub (which is a broadcast, where the sender needs not to be aware of the receivers), even though both are decentralized systems. I suppose the flow library design would be a centralized system?

An incarnation of message passing OOP in Python would be the object method invocation (Wikipedia article on OOP). But NetLogo's OOP syntax seems to be more explicit in conveying that it is a "message passing".

[quaquel]

My understanding is that discrete event simulation started with Simscript developed at the RAND corporation. Here you already see the use of an EventList, and entities with attributes. Simulate then builds on this and is considered the first object oriented language. Version I (1962) was targeted at simulations (like Simscript), vesrion II (1967) was a general purpose programming language. Simula had a great influence on the developers of both C++ and Java. Smalltalk actually appeared only in 1972, so a bit later.

[rht]

While the regrowth of the grass patches is handled through event scheduling.

Regarding with performance, I know it's less efficient with stepping all the GrassPatch's at each step, but I reformulated the step method as

def step(self):
    self.height = min(self.height + 1, self.model.grass_regrowth_time)
    self.fully_grown = self.height >= self.max_height

This version is about as concise as the DEVS version, while at the same time it can be vectorized, and hence can be a property layer bulk operation, instead of agent steps, which is fast as well. It makes me wonder if the framework language is not Python, but instead is in Rust, which one would be faster.

But this is a very specific example where the grass FSM dynamics is independent of its surroundings. If the grass patch growth rate depends on whether the surrounding is arid/fertile, then a property layer solution might be faster, because dependence on the nearest neighbor can be viewed as a geographical property instead of time-based property.

[quaquel]

I agree that for the WolfSheep model, implementing grass as a property layer is sensible.

However, the purpose here is to showcase event scheduling and how it can be combined with normal ABM-style scheduling. The purpose here, explicitly, is not to find the fastest implementation. For the fastest implementation, we can take a look once the DiscreteSpaces stuff has been merged and property grids are made to work within it. The fastest implementation is relevant for the benchmarks with other libraries.

Also, I added a second example using Epstein's civil violence model.

[rht]

The EventList's concrete implementation is based on EventListHeap in pydsol. a DEVS is more efficient than a simulation in ABM format if the number of events << number of ticks in ABM. If they are of the same order of magnitude, then the push operations on the heap tree become expensive.

For a hybrid framework, shouldn't the model step be separated from the EventList, because it happens at every tick anyway? The EventList may be reserved for rare events, and the current pop() of the heap shouldn't be cleared unless it is at the right tick.

[quaquel]

The developer of pydsol did extensive performance testing. The overhead should be really small, but it is worth testing.

The problem with separating model.step from the event list is that you must do additional bookkeeping. This implementation has a single source for truth about the simulation time.

[rht]

For a hybrid framework, shouldn't the model step be separated from the EventList, because it happens at every tick anyway? The EventList may be reserved for rare events, and the current pop() of the heap shouldn't be cleared unless it is at the right tick.

Never mind, this proposal is probably not faster than a heap push, because pushing to a heap is ensuring that the rare event happens at the right tick, and so is almost the same as having them separate, because the checking at each tick is almost the same as a single push operation on the heap that includes the ABM steps.

[rht]

I think the __cmp__ method of the SimEvent can be significantly sped up in Rust, if the EventList heap data storage is in Rust as well. Python comparator is usually slow.

[quaquel]

yes, if we go done the Rust route and integrate some kind of DEVS into MESA, it would be logical to port all this to Rust.