Multi-Agent Ride-Sharing System Simulation

TLDR: Developed multi-agent ride-sharing system simulation with an ethically aligned order dispatcher using Golang programming language. Was complicated and tough but fun.

During my last year in Nanyang Technological University (NTU) in Singapore, all final year students are required to take a Final Year Project (FYP) as a fulfilment for a degree in Computer Science.

I chanced upon a project on matching passengers and drivers in Ride Sharing Systems (such as Grab, Uber, DiDi) through a novel order dispatch algorithm where it priorities the wellbeing of drivers and fair allocation of tasks with the consideration of drivers’ reputation ratings.

So I emailed the professor to ask what is the requirement of the project, and he said all I need to know is algorithms and data structures. So I thought it was pretty doable so I selected the project.

After the school has allocated the project to me, I went to look for my professor to enquire more about the project.

Wait.... what the.... a simulation?

I didn't expect that I need to build a simulation... (I have zero idea on how to build one), and it was not part of the specification of the project...

First thing first, like any other computer science students, we google the hell out of it. We found some potential projects in GitHub. We download the hell out of it. And realised we got some problems setting up the project in our environment (or computer), some features are broken, or it is not even what we are looking for.

Back to square one.

After some research for a few days, I realised what I needed to build for this project - Multi-agent ride-sharing system simulation.

Oof... huge words...

The simulation is also equipped with a map interface and inputs to tune the model.

Let's break it down into three parts.

• Multi-Agent
• Ride-Sharing System
• Simulation

Multi-Agent System

A Multi-Agent System is a system composed of multiple interacting intelligent agents. It is typically used to solve a problem that is difficult for an individual agent. But...what is an agent? The concept of an agent is used to indicate the purposive nature of human activity, and it is thus related to concepts such as intentionality, free will, and the power to achieve goals. In essence, an agent is a simplified version of a human that can achieve goals.

Some of the applications of Multi-Agent System expand to industrial applications such as manufacturing enterprise integration, supply chain management, manufacturing planning, scheduling, and control systems.

Ride-Sharing System

Ride-sharing has become a ubiquitous part of how we travel from one place to another, and in the last decade, it has increasingly been an important component in transportation infrastructure. At their core, these ride-sharing platforms reduce the friction in matching and dispatch for transportation. It is enabled by basing on the pairing of driver and passenger mobile applications; a typical transaction starting with a potential passenger opening his or her app and requesting a ride, following by a centralized dispatcher (just think like a smart program that decides which passenger to match which driver) that matches the passenger to a nearby driver if one is available.

In most ride-sharing systems, the driver holds a state. The above diagram shows the different states of driver's status with the transitions between states.

How does the status change for driver in a ride-sharing system?

1. The driver starts of with "Roaming" (driver drives around and wait for a task by centralized dispatcher)
2. If the driver is currently take into account of the centralized dispatcher for assigning tasks, the state of driver will change to "Allocating"
3. If the driver did not receive a task by the centralized dispatcher, the state of the driver goes back to "Roaming". If the driver receive a task, the state of the driver change to "Matching"
4. If the driver has a "Matching" state, the driver can choose to decline (and state changes to "Roaming") or accept the task (state changes to "Picking")
5. With the state of "Picking", the driver will now travel to the passenger's location and then the status of driver changes to "Fetching" once the driver has reached the passenger's location.
6. With the state of "Fetching", the passenger is with the driver and the driver is fetching to the passenger's desired destination.
7. Once the driver has successfully fetched the passenger to its desired destination, the status of driver turns to "Roaming", and it repeats.

There are other states to cater for multiple picking up of passengers (e.g UberPool, Grab Share) and additional states for allocating passengers to drivers, but the above logic flow is good enough for a driver's status in basic ride-sharing systems.

Simulation

I think we all know what is a simulation is, but for this context, the purpose of the simulation is to study the complex behaviour between the drivers, passengers and the dispatch order (where is assign passengers to drivers) and get insights into the eventual effects of many conditions and courses of actions. With every simulation, it is equipped with interface that can tune the characteristics and behaviours of the agents.

What's really next?

Multi-agent system is not new in the research world, and hence, there are toolkits and libraries available for researchers to deploy their model and hypothesis. I chanced upon a few of it.

Repast, SWARM and MASON

Building a multi-agent simulation model is definitely challenging because the researcher (or the developer) has to be well versed in programming languages such as Java and C++. Although there are a wide variety of toolkits such as Repast, SWARM and MASON (most of it is for agent-based modelling) that could greatly reduce the model construction time and allowing more time to be dedicated to research, researcher have to learn how to design and implement a model in the toolkit and the programming language the software uses.

After this investment of time, there is a chance that the desired functionality is not up to standard or is not possible to implement. In addition to using toolkits, researchers are restricted to the design framework supported by the toolkits and may be unable to extend or integrate additional tools. And let's be real - the installation and setup portion of these toolkits is not noob-friendly... So, I decided to take the challenge by building the multi-agent simulation from ground-up, so I have full complete control over every aspect of the model.

JavaScript

The first thought came into my mind for what kind of programming language to use to develop this system is Javascript! Javascript would be a great programming language because it can be used in both front and back end. Also, there is a clear example that it is possible to create such system with JavaScript.

But, I suck at JavaScript even though I have used in used it in many of my past projects. (but I still it for this project!) Moving on!

Golang

And then, I chanced upon Golang, a programming language by Google. It is typically used for large-scale network servers and big distributed systems but one of the main reasons why I chose Golang supports both multi-threading environment and concurrency. This can be achieved using Goroutines.

Goroutines are functions or methods that run concurrently with other functions or methods. It can be thought of as lightweight threads. The cost of creating a Goroutine is tiny when compared to a thread in Java programming language.

This is probably the key to simulate a bunch of agents in the simulation.

And Golang's syntax looks pretty easy and straightforward to me!

No Fancy Tech Stack over here

As mentioned earlier, the simulation requires an interface. Hence, let's split into two parts - front end (user interface) and back end (simulation).

Here are the finalized tools, libraries and programming language I will be using to build the Multi-agent ride-sharing system simulation.

For the front end, I will be using mainly JavaScript programming language with ReactJS, react-map-gl (mapbox) and Deck GL.

For the back end, I will be using Golang with Gonum (graphs, graph traversal, and path search algorithms) and Paulmach/Orb ( geospatial tools and functions).

The communication protocol for both front and back end is WebSocket.

Overpass-turbo to extract out the roads from a defined boundary set by me. For this project, I will be extracting out the network of roads in Chengdu, China.

General Approach

The notion of the environment is a primary concept in agent and multi-agent systems, being the computational or physical place where agents are situated and providing the basic ground for defining the notions of agent perception, action, and the interaction. Hence, the network of roads serves an environment for drivers to drive on.

How do I generate agents (or drivers) on the environment? First of all, the driver agents have a set of attributes that emulate the basic characteristics of a driver such as driver status (roaming, picking up, fetching passenger, etc), fatigue, rating, etc. Besides attributes, there is a set of policies defined for the driver agents to achieve the goal - pick up and fetch passengers to their desired location. This can be achieved by using Golang's Goroutines.

First version

During development, I faced many concurrency issues in my code, complicated integration between the user interface and simulation, and implementing Quadtree for mapping passengers to the closest road, but it turns out great!

What am I seeing over here?

The moving dots are drivers but they hold different colours (explained in the caption below the gif). The black dots are appearing in an order with respect to the simulation time. These black dots are customers (or passengers to-be). The red lines represent the road where the drivers can drive on.

There are other input fields available for the researcher to tune the models, spawn drivers, and interact with the simulation settings.

What's next after first version?

The next step is to scale it - a bigger road network for drivers to drive and more customers (or passengers appearing on the map).

However, there are few (possibly major) changes needed to be done.

1. The network of roads (the red lines) are served in the front end and the simulation needs to communicate with the front end for the location of the drivers, which could slow down the drivers in a computational approach. Hence, I have to port over the network of roads to the simulation and it will be definitely smoother while running the simulation.
2. Every time I start the user interface (ReactJS), I had a function to load the network of roads but it takes a few seconds (about 10 seconds) which is pretty annoying for me if I made minor changes at the interface. Porting of the network of roads to the simulation will solve this issue.
3. Ugly user interface. I will be using react bootstrap to beautify it. Custom CSS takes too much time from me and I cannot guarantee it will look nice too!
4. The display of the drivers on the map seems kinda laggy or delayed. I use Deck GL (uses WebGL) to improve the update speed of the drivers' location on the map. All in all, during the running of simulation, WebSocket communication is strictly used for updating of drivers' and passengers' locations on the map.

Final version

That's all!

This post only scratches the surface of this project. If you want to know the

1. intricacies of how the passenger match with drivers works using Golang,
2. an analysis of how the drivers' well being (fatigue, reputation, etc) affect their income earned (How ethical is the proposed dispatch order algorithm?)
3. how the driver travels computationally
4. implementation of virus mechanism in ride-sharing system and the results

Drop me a message at my LinkedIn, and I write in my next post! Oh yes, feedbacks and comments are always appreciated! :)

If you would like to take a look at the source code, its over here for the user interface and here for the simulation.

Thank you for reading!