THIS POST IS ARCHIVED

Modeling an Agent-Based Simulation in a Relational Database

The standard way to store and interact with the large amount of data that are central to the functioning of any modern business is through the use of a relational Knowledge Graph Management System (KGMS).

We will show how the relational model can be successfully exploited to model complex analytics scenarios while enjoying the same characteristics of clarity and flexibility as when modeling the data themselves.

We will do this by simulating the daily schedule of an airline company as an agent-based system, and we will show how modeling this system through a set of relationships and logical rules will let us focus directly on the inherent complexity of our model, taking away most of the incidental effort in actually implementing our simulation.

To do this, we will use our declarative modeling language, Rel. Rel provides a powerful abstraction to define relations; in this context, rules are loosely intended as complex relations that encode some logic.

Agent-Based Simulation (ABS)

We are modeling a complex system by simulating the behavior of a large number of interacting agents. The advantage of the approach lies in its simplicity: we only need to describe and characterize the agents, yet very complex dynamics can arise from the interactions between them. We will model this system by defining a set of relationships and simple rules to describe the behavior of the agents.

We start by identifying the agents using a set of entities such as aircrafts, airports, and pilots. The rules will encode the general behavior of the system (for example., flight A departs from airport A1 and lands in airport A2) and will let us specify some domain-specific knowledge and constraints (for example, a flight needs two pilots and at least three attendants).

It is generally hard to encode information like this using imperative programming languages. We will show how our declarative language Rel can be much more effective.

Simulating an Airline’s Flight Schedule

Our goal is to model the real-time flight schedule of an airline company at any given time. In the context of ABS, we can think of the fleet of the airline company as the agents (the aircrafts) interacting with the environment by flying between airports and being affected by the weather and other delay events. The interactions between aircrafts themselves are specified by a set of rules modeling flight delays.

High-Level Model

A very simple simulation of a flight schedule can be constructed using the following entities: Aircraft, Flight, Connection, and Airport. Each of these entities will have specific properties: for instance, each Flight has a departure time and each Airport has an international identifying code. In this simple picture, a set of aircraft fly between airports following some predefined connections. This is represented by the following ontology:

flights_ontology
Flight simulation ontology. Circles represent entities, rectangles represent properties. Relationships between entities are represented by the bold edges.

In Rel, we can define entities directly. For instance, the Aircraft entity is defined like this:

def aircrafts = {"AF1"; "AF2"; "AF3", …}
entity Aircraft aircraft_from_code = aircrafts

The attributes for each entity and the relationships between the entities can be modeled with Rel relations. For instance, we can define the Connection entity in terms of the airports served and available routes:

// available routes as a tuple of (origin, destination, travel_time)
def airport_routes = {
    ("ATL", "LGA", Minute[100]);
    ("ATL", "BOS", Minute[150]);
    ("ATL", "SFO", Minute[270]);
    …
}

entity Connection connections(origin, dest) =
    origin_code = airport:code[origin]
    and dest_code = airport:code[dest]
    and airport_routes(origin_code, dest_code, _)
    from origin_code, dest_code

This is an example of writing simple rules to model the behavior of the system. We only need to specify the relation by which a certain connection has an origin and a destination belonging to a set of available routes, and the KGMS will take care of the low-level details to abide by the rule.

In more realistic scenarios, we can include more entities such as Pilot, Passenger, and Gate. We can then code the domain-specific knowledge in the form of relations and rules between the entities, such as:

  • A flight needs exactly two pilots
  • An aircraft should be accessible from a gate 30 minutes before departure
  • A pilot cannot fly for more than six hours within a 24-hour day

Fully modeling the realistic operations of an airline company could easily increase the complexity of the system. At the same time, Rel provides a structured way to manage this complexity. Adding expert knowledge into the system is done by adding entities and relations.

Generating Data

To simulate the actual schedule of a specific airline, we can load the flight information into the database. Here, we generate a synthetic schedule directly in Rel. You can see how Rel lets us declaratively describe complex processes.

First, let’s generate random flights according to some simple rules:

  • Each aircraft makes four flights in a given day, identified by k = 1, …, 4;
  • The origin for the first flight of the day is chosen at random;
  • Subsequent flights start where the aircraft has landed, i.e., the origin of the following flight coincides with the dest of the previous flight;
  • dest is always chosen at random.

In Rel, this translates to:

// number of flights per day
def daily_flights = 4

entity Flight flight_from_conn = flight

// we define the `flight` relation as a constructor for the `Flight` entity;
// the following applies when `k`=1
def flight(conn, aircraft, 1) =
	// sort the aircrafts to associate an index `i` to each `aircraft`
	sort[Aircraft](i, aircraft),
	// choose a random connection `i` for the ith sorted aircraft
	conn = randomchoice[i, Connection]
	from i

// `flight` relation for `k` > 1
def flight(conn in Connection, aircraft in Aircraft, k in range[2, daily_flights, 1]) =
	flight(previous_conn, aircraft, k-1)
	and connections(_, scale, previous_conn)
	and conn = randomchoice[1, connections[scale, _]]
	from previous_conn, scale

Tracking Flights and Modeling Delays

We assume that each aircraft is either flying or boarding and no other phases are modeled (i.e., we don't directly model landing, disembarking, and idle phases in the airport). For each flight we have a boarding_time and a departure_time and the flight status is a simple Rel relation:

def flights_status[time, f in Flight] = "boarding",
    time >= flight:boarding_time[f]
    and time < flight:departure_time[f]

def flights_status[time, f in Flight] = "flying",
    time >= flight:departure_time[f]
    and time < flight:departure_time[f] + flight:duration[f]

Delays are attached to the flights and are saved in the database. We assume that delays are always applied to the boarding_time of the upcoming flight, indirectly affecting the departure_time, but in principle we can add the delay at any stage of the flight. In this picture, delays not happening at boarding time can be propagated to the right flight with adequate rules (for example, a delay during the flying phase will impact the boarding time of the subsequent flight with the same aircraft).

Constructing the delay of one flight also impacts the following flights using the same aircraft (this is the purpose of the previous_flight relation). The flight_delays relation models the delay events stored in the database.

def previous_flight[f] =
    prev:
        flight_from_conn(_, aircraft, k-1, prev)
        and flight_from_conn(_, aircraft, k, f)
    from aircraft, k in range[2, daily_flights, 1]

// `<++ Minute[0]` is used to set the default value to `Minute[0]`
// if there are no `flight_delays` for flight `f`
def flight:delay[f in Flight] =
    flight_delays[f] <++ Minute[0],
    flight_from_conn(_, _, 1, f)

def flight:delay[f in Flight] =
    flight:delay[prev] + (flight_delays[f] <++ Minute[0]),
    prev = previous_flight[f]
    from prev

We are now able to track the status of scheduled flights at any given time. A simple graph visualization is provided below, where the nodes represent the airports served by the airline company and the arrows represent flights.

flight-graph
Flight graph. Arrows represent active flights.

Simulating the Impact of a Storm

With the agent-based simulation in place, we can now show how to explore different scenarios by adding rules and relations to our model.

A key feature of Rel that makes this exploration simple is the way the system reactively updates its state after changes in the data, or with the addition of new rules and relations. This is made possible by the reactive and declarative nature of the language, two fundamental features that make Rel both elegant and expressive.

As an example, let’s see how to define delays caused by a storm. Let’s assume that a storm has a duration of 60 minutes, and it impacts all the flights that are scheduled to board in that span of time. We can model the delays we’re adding to the database as follows:

// storm in MIA
def storm_location = a in Airport: airport:code(a, “MIA”)
def storm_time = parse_datetime["09:30 01-03-2022", "HH:MM dd-mm-yyyy"]

def impacted_flights[f] =
    flights_status[storm_time, f] = "boarding"
    and flight:conn(f, conn)
    and connections(storm_location, _, conn)
    from conn

def insert[:flight_delays] = f in impacted_flights:
    if flight_delays[f] > Minute[0] then
        flight_delays[f] + Minute[60]
    else
        Minute[60]
    end

Looking at the status of active flights a couple of hours after the storm, we can see that flights leaving from the airport location and subsequent flights from connected airports have been disrupted (the red arrows signify delayed flights).

graph-after-storm
Flight graph after a storm in MIA. Red arrows represent delayed flights.

Unlocking Enterprise Knowledge

We have demonstrated a simple way to simulate different scenarios of a specific business operation. All enterprises have the knowledge that describes their operations scattered in database tables, Excel spreadsheets, or directly passed down among domain experts.

When it comes to analytics and data manipulation tasks, in most cases we are forced to pull the data out of the database and use other software applications to explore it. This is not due to a shortcoming of the relational model, but rather of the relational KGMS in use.

With our RKGMS and declarative modeling language, Rel, the relational model can be successfully exploited to model complex analytics scenarios while enjoying the same characteristics of clarity and flexibility as when modeling the data themselves.

To learn more about Rel’s syntax, see the Rel Primer section of our documentation.