[AAMAS 2024] Multi-Agent Reinforcement Learning for Real-World Application (Part 1)

One of the largest and most influential international conferences in the field of multi-agent systems, the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) covers topics in robotics, game theory, multi-agent systems, reinforcement learning, social simulation and modeling, and more.

LG AI Research’s Data Intelligence (DI) Lab presented two papers at AAMAS 2024, “Naphtha Cracking Center Scheduling Optimization using Multi-Agent Reinforcement Learning”^[1] and “Agent-Oriented Centralized Critic for Asynchronous Multi-Agent Reinforcement Learning”^[2], and discussed various agent modeling and reinforcement learning algorithms for industrial applications of AI technology with researchers. This post will introduce (1) various applications of Multi-Agent Reinforcement Learning (MARL) and related studies, and (2) studies on efficient MARL methods for real-world problems, in two parts.

 

Multi-Agent Reinforcement Learning for Real-World Application Part 1 Data Intelligence Lab, Deunsol Yoon (this post) Part 2 Data Intelligence Lab Sunghoon Hong (Link)

 
This post will share two cases of the application of MARL presented at AAMAS 2024 to real-world problems. The first paper, “Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare^[1]”, is a paper on a MARL-based on-demand mobility routing algorithm for autonomous taxi services. The second paper, “Naphtha Cracking Center Scheduling Optimization using Multi-Agent Reinforcement Learning^[2]”, was published by us at LG AI Research and is a study on optimizing a naphtha cracking facility using MARL.

Reinforcement learning (RL) refers to the process of learning the optimal action policy that maximizes the sum of rewards an agent receives over the long term from interacting with the environment in a sequential decision problem. This process is usually modeled as a Markov Decision Process (MDP), which consists of the following:

1. State: Represents the state of the environment that the agent is currently in. For example, in a game of chess, the current placement of the pieces on the chessboard might be a state.

2. Action: Refers to an action that an agent can take. Depending on the state, an agent can choose different actions; for example, in chess, moving a single piece is an action.

3. Reward: The feedback an agent receives from the environment when it takes a certain action. Rewards indicate how good or bad an action is, and agents learn to earn high rewards. For example, in chess, you might earn a reward for capturing an opponent’s piece.

4. Transition Probability: Represents the probability of transitioning to the next state, given the current state and actions. This reflects the Markov property that the future state depends only on the current state and action.

In other words, the agent looks at the current state and chooses one possible action, which is rewarded by the environment, and learns which action leads to a better result. As the agent repeats these attempts, it finds the optimal policy.

Multi-agent reinforcement learning is the process of each agent learning its own policy in an environment where multiple agents exist. The state, actions, and rewards of each agent are defined independently, and each agent learns the optimal policy by interacting with other agents. For example, in a soccer game, each player (agent) cooperates or competes to achieve the end goal by kicking or passing the ball.

1. Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare

Recent advances in autonomous driving technology have drawn attention to autonomous taxi services. To maximize the efficiency of these services, many researchers are working to improve on-demand mobility routing algorithms. The paper to be introduced is “Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare” by Daniel Garces and Stephanie Gil of Harvard University.

Image 1. On-demand mobility routing problem^[1]

The on-demand mobility routing task aims to place shared vehicles, such as taxis, at optimal locations to minimize passenger wait times. As existing on-demand mobility routing algorithms are designed based on typical demand patterns, they often fail to effectively handle sudden changes in demand due to large-scale events (e.g., concerts, sporting events). If an event is being held at the orange dot, as shown in Image [1], and this information is not taken into account, it could end up predicting the wrong location for potential customers, as shown on the left, and have shared vehicles driving around far from the concert. Conversely, if the information about the event is taken into account, as shown on the right, it would be possible to efficiently dispatch vehicles to minimize the wait time for passengers.

Specifically, the authors defined the agent, state, action, and cost in the problem as follows.

1. Agent: Vehicle

2. State: Current location, requested locations of pick-ups, and the progress of other agents

3. Action: When waiting, an agent can move to a nearby intersection, remain at the current location, or accept a request. When fulfilling a request, it moves to the next route along the shortest route from its current location to the requested destination.

4. Cost: Number of currently pending requests

Therefore, the goal of the problem is for each agent (vehicle) to observe its current location, the location of the pick-up request, and the progress of other agents to perform actions such as moving to a nearby intersection, remaining at the current location, accepting a request, and fulfilling a request, with the objective of minimizing the number of pending requests.

The authors proposed a new framework that combines demand prediction using event data with multi-agent reinforcement learning to solve the problem of service demand spikes.

Demand forecasting framework:

1. Utilizes event data collected from the internet to forecast demand spikes.

2. Using event descriptions and reviews, predict the time of event occurrence and the demand at the event location.

Multi-agent reinforcement learning framework:

1. Effective routing is performed in a city-scale environment using a “one-agent-at-a-time rollout” approach based on demand prediction results.

Demand prediction framework

The demand forecasting framework utilizes the event processing module, demand prediction module, and demand assignment module to make demand predictions for pickup requests at each intersection in a city.

The event processing module collects and processes event information from the Internet. The main steps are as follows:

1. Event Data Collection: It collects data such as titles, descriptions, reviews, and schedules of events from the Internet, and uses the PredictHQ API and Google Maps to collect reviews related to events.

2. Sentence Embeddings: It converts the collected text data into sentence embeddings using the RoBERTa Large model.

3. Spectral Clustering: It groups similar reviews by spectral clustering using a Gaussian RBF kernel.

4. Cluster Averaging: It averages the embeddings from each cluster to produce a vector representing the event.

The demand forecasting module uses the event feature vector generated by the event processing module to predict taxi demand at a specific time and place.

1. Combining Feature Vectors: Generates input vectors by combining event feature vectors with spatial and temporal data, such as time of day and weather.

2. Neural Network-Based Prediction: Using the combined input vectors, a neural network predicts the hourly demand in each zone (sector). It uses only spatial and temporal data, such as time of day and weather, when there are no events, and uses data with event information when there are events.

3. Demand Distribution Generation: Generates minute-by-minute demand distributions for each zone based on the predicted demand.

The demand allocation module allocates the demand distribution generated by the demand prediction module to the intersection level. The main steps are as follows:

1. Local Maximum Occupancy Data: Estimates demand by intersection using the maximum capacity and occupancy schedules of places (e.g., restaurants, hotels, etc.) near each intersection.

2. Probabilistic Assignment: Maps the predicted demand to the intersection level. This creates a probability distribution of the demand that can occur at each intersection.

3. Demand Distribution Mapping: Assigns demand predictions from a specific zone to each intersection, which allows the fine-tuning of demand distribution to the intersection level.

 

Multi-Agent Reinforcement Learning Framework

The model-based reinforcement learning routing module utilizes demand predictions for pickup requests at each intersection in the city provided by the demand allocation module to route autonomous taxis. In a typical MARL algorithm, all agents learn simultaneously. Therefore, as the number of agents grows, the state-action space, the search space required for optimization, grows exponentially, making it difficult to train reliably on problems like on-demand mobility routing, where hundreds of agents may exist.

In this paper, instead of training and utilizing a neural network-based policy to select each agent’s actions, a no-training planning algorithm called “one-agent-at-a-time rollout” is utilized for routing. The algorithm optimizes each agent sequentially rather than simultaneously. This can significantly reduce computational cost as the search space grows linearly as the number of agents grows. Here is how a “one-agent-at-a-time rollout” works.

1. Initialize:

1. Initializes each agent’s initial behavior with a heuristic-based base policy.

2. A heuristic-based base policy is a computationally fast and simple policy, for example, a greedy policy that enables the agent to select the passenger closest to its current location and move to that location.

2. Sequential Optimization:

1. Only one agent is optimized at a time. For example, while agent A is being optimized, the other agents B and C follow the base policy.

2. Agent A simulates possible actions and evaluates the future cost of each action.

3. Action Selection:

1. Based on the simulation results, Agent A selects the optimal action that minimizes future costs.

2. The selected action is reflected in Agent A’s next state.

4. Repetition:

1. Agent B then is optimized. At this point, Agent A’s selected action is fixed, and Agent B optimizes its own action.

2. This process is repeated until all agents are sequentially optimized.

5. Action Update:

1. After every agent is optimized once, it updates the actions of all agents.

2. According to the above mechanism, all agents’ actions are updated, and then applied to the environment, resulting in the next state.

 

Image 2. Proposed overall framework^[1]

Image 3. Comparison of experiment results^[1]

 

Experiments using real rideshare data in the Manhattan area of New York City showed that the proposed method outperforms existing methods in terms of waiting time and the service request processing rate. The proposed method reduced the waiting time per service request from 25% to 75%. The proposed method also allowed the processing of 1% to 4% more service requests.

This paper demonstrated the possibility of maximizing the efficiency of autonomous taxi services by utilizing multi-agent reinforcement learning. In particular, this study can greatly expand the real-world applicability of the reinforcement learning field in the future. It has demonstrated that difficult real-world problems, such as a surge in demand due to large-scale events, can be overcome through the combination of reinforcement learning and demand forecasting technology. LG AI Research is also conducting various researches on how to apply these demand forecasting and optimization technologies to actual industries. In the future, it is expected that demand forecasting and optimization algorithms can be applied to various real-world problems such as logistics systems and product production processes within LG affiliates.

 

2. Naphtha Cracking Center Scheduling Optimization using Multi-Agent Reinforcement Learning

The Naphtha Cracking Center (NCC) is an important facility in the petrochemical industry, where a substance called naphtha, which is obtained from crude oil, is cracked and processed in high-temperature cracking furnaces to produce various products. Naphtha is shipped in from all over the world by ship to the dock where the NCC is located and is divided into multiple storage tanks for stable inventory management. The naphtha stored in multiple tanks is mixed properly in one tank to maintain the appropriate quality, and naphtha of the desired quality is decomposed through a high-temperature decomposition furnace to produce various sellable products depending on the setting.

 

Image 4. Naphtha Cracking Center (NCC)

 

Naphtha Cracking Center Optimization

The NCC scheduling task involves determining how to operate various processes within the NCC over a given period. The goal of scheduling is the final profit and constraint satisfaction. Previous studies optimized each process individually^[4,5,6], and in reality, experts were distributed in each process and manually decided how to operate each process, making it difficult to optimize profit or satisfy various constraints in an integrated manner. Therefore, this study proposed a method to comprehensively operate and further optimize the entire process with a single AI model based on multi-agent reinforcement learning.

 

Image 5. NCC scheduling optimization conceptual diagram^[2]

 

We models NCC operation as a multi-agent system consisting of three agents: receipt, blending, and furnace.

 

1. Observation: Each agent may observe some or all of the following: the price of naphtha and its products, information about upcoming naphtha receipts, the quantity and quality (composition) of naphtha inventory in each storage tank, and the production of each product.

2. Receiving agent action: Decides which storage tank to store naphtha from ships entering the dock

3. Blending agent action: Determines how to blend naphtha stored in multiple storage tanks into one blending tank

4. Furnace agent action: Decides how to set control variables such as temperature and pressure of the furnace

5. Reward: Profit (= [Total sales revenue] – [Energy cost] – [Naphtha raw material cost]) and constraint satisfaction
   
   

$\mathit{\text{Reward}}\mathit{=}\mathit{\text{Profit}}\mathit{-}\mathit{\sum }_{\mathit{c}\mathit{\in }\mathit{\text{Constraints}}}{w}_{\mathit{c}}\mathit{\cdot }{\mathit{\text{Cost}}}_{\mathit{c}}$

$Profit=Revenue-Energy usage -Naphtha \cos t$

These agents must work together to perform optimal scheduling for the common goal of maximizing profit while satisfying their individual constraints. Constraints typically consist of satisfying upper and lower limits on the amount of naphtha in each storage tank and maintaining naphtha component stability, constraining when actions change, and satisfying upper and lower limits on the control variables in the furnace.

 

Asynchronous Multi-Agent Reinforcement Learning

To train MARL agents for the NCC system defined above, a simulator of the NCC scheduling environment was developed. This simulator informs a set of observations and rewards of each agent in a given environment, as they decide on their action.

 

Image 6. NCC scheduling reinforcement learning environment simulator^[2]

 

While most of the requirements to train an agent have been met with the simulator described above, the MARL algorithm still needs to be improved. This is due to one of the main constraints in NCC scheduling, the “action change timing constraint.” This means that in reality, not only does it take different amounts of time to perform one action in each process, but changing actions too frequently may be impossible for the actual operator to do, so actions can only be changed when certain conditions are met. In other words, while a typical MARL environment assumes that all agents perform actions of the same duration at the same time, this study deals with an Asynchronous MARL problem where each agent performs actions of different durations at different times.

 

Image 7. Synchronous vs. Asynchronous MARL comparison^[2]

 

While most of the requirements to train an agent have been met with the simulator described above, the MARL algorithm still needs to be improved. This is due to one of the main constraints in NCC scheduling, the “action change timing constraint.” This means that in reality, not only does it take different amounts of time to perform one action in each process, but changing actions too frequently may be impossible for the actual operator to do, so actions can only be changed when certain conditions are met. In other words, while a typical MARL environment assumes that all agents perform actions of the same duration at the same time, this study deals with an Asynchronous MARL problem where each agent performs actions of different durations at different times.

 

Deployment

Through the above methods, LG AI Research trained an AI model for MARL-based NCC scheduling optimization and is attempting field application in collaboration with LG Chem. First, to improve usability for field experts, we developed a web service with a simple UI to make it easy for non-AI experts to use. Based on this, the field can easily generate schedules with the AI scheduler through web services, and the generated schedules are applied to field operations after reviewing various aspects such as profitability and stability by experts. Currently conducting an internal test, we found that the AI scheduler shows high profit and constraint satisfaction, which bodes well for future use at industrial sites.

 

Image 8. NCC scheduling service example

 

Conclusion

So far, this post has taken a closer look at the studies presented at AAMAS 2024 that utilized MARL to solve real-world problems. With the recent increase in interest in reinforcement learning, Researches on MARL have been gaining traction. In particular, the naphtha scheduling optimization study is significant as it provides a new example of solving a real-world industrial problem through the cooperation of multiple reinforcement learning agents. Furthermore, it is expected that various real-world problems such as optimizing the production process of products can be solved based on reinforcement learning in the future. LG AI Research will continue to lead the way in developing technology in the field of applied research by discovering new problems in real industries and creating applicable AI technologies.

 

▶Agent-Oriented Centralized Critic for Asynchronous Multi-Agent Reinforcement Learning

▶Naphtha Cracking Center Scheduling Optimization using Multi-Agent Reinforcement Learning

▶24시간 일하는 AI가 석유화학 공장에 도입되면 생기는 일