Resource Allocation Optimization in Multi-Agent System

A Practical Implementation

In today’s increasingly interconnected world, multi-agent systems are becoming more prevalent in various domains from economics to computer networks.
One of the most fascinating challenges in these systems is how to optimally allocate limited resources among competing agents.
Let’s dive into a concrete example and solve it step by step using Python.

The Problem: Task Allocation in a Team of Robots

Imagine we have a team of robots (our agents) that need to complete various tasks in a warehouse.
Each robot has different capabilities and efficiencies for different tasks, and we need to allocate the tasks optimally to maximize overall efficiency.

This is a classic resource allocation problem in multi-agent systems.
We’ll model this as a linear optimization problem and solve it using Python’s powerful optimization libraries.

Let’s implement this solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from scipy.optimize import linear_sum_assignment
import pandas as pd
from matplotlib.colors import LinearSegmentedColormap
from pulp import LpMaximize, LpProblem, LpVariable, lpSum, LpStatus

# Set random seed for reproducibility
np.random.seed(42)

def simple_task_allocation():
    """
    A simple task allocation problem using the Hungarian algorithm
    """
    print("Example 1: Simple Task Allocation Using Hungarian Algorithm")
    print("="*60)
    
    # Define number of robots and tasks
    n_robots = 5
    n_tasks = 5
    
    # Generate random efficiency matrix (how good each robot is at each task)
    # Higher value means better efficiency
    efficiency_matrix = np.random.rand(n_robots, n_tasks)
    
    # For better visualization, scale values to be between 1 and 10
    efficiency_matrix = 1 + 9 * efficiency_matrix
    
    # Display the efficiency matrix
    print("Efficiency Matrix (Robot vs Task):")
    efficiency_df = pd.DataFrame(
        efficiency_matrix, 
        index=[f"Robot {i+1}" for i in range(n_robots)],
        columns=[f"Task {i+1}" for i in range(n_tasks)]
    )
    print(efficiency_df)
    print()
    
    # The Hungarian algorithm minimizes cost, so we need to convert efficiency to cost
    # We can do this by negating efficiency
    cost_matrix = -efficiency_matrix
    
    # Apply Hungarian algorithm
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    
    # Display the results
    total_efficiency = 0
    print("Optimal Allocation:")
    for i, j in zip(row_ind, col_ind):
        print(f"Assign Robot {i+1} to Task {j+1} (Efficiency: {efficiency_matrix[i, j]:.2f})")
        total_efficiency += efficiency_matrix[i, j]
    
    print(f"\nTotal Efficiency: {total_efficiency:.2f}")
    
    # Visualize the efficiency matrix and optimal allocation
    plt.figure(figsize=(10, 8))
    sns.heatmap(efficiency_matrix, annot=True, fmt=".2f", cmap="YlGnBu",
                xticklabels=[f"Task {i+1}" for i in range(n_tasks)],
                yticklabels=[f"Robot {i+1}" for i in range(n_robots)])
    
    # Highlight the optimal allocation
    for i, j in zip(row_ind, col_ind):
        plt.plot(j + 0.5, i + 0.5, 'ro', markersize=10)
    
    plt.title("Robot-Task Efficiency Matrix with Optimal Allocation", fontsize=14)
    plt.tight_layout()
    plt.show()

def resource_constrained_allocation():
    """
    A more complex resource allocation problem with constraints
    using linear programming
    """
    print("\nExample 2: Resource Constrained Allocation Using Linear Programming")
    print("="*60)
    
    # Define number of robots, tasks, and resource types
    n_robots = 4
    n_tasks = 6
    n_resources = 3
    
    # Generate random efficiency matrix
    efficiency_matrix = np.random.rand(n_robots, n_tasks) * 10
    
    # Generate random resource requirements for each task
    resource_requirements = np.random.randint(1, 6, size=(n_tasks, n_resources))
    
    # Generate random resource capacities for each robot
    resource_capacities = np.random.randint(5, 15, size=(n_robots, n_resources))
    
    # Display the data
    print("Task Efficiency Matrix (Robot vs Task):")
    efficiency_df = pd.DataFrame(
        efficiency_matrix, 
        index=[f"Robot {i+1}" for i in range(n_robots)],
        columns=[f"Task {i+1}" for i in range(n_tasks)]
    )
    print(efficiency_df)
    print()
    
    print("Resource Requirements for Each Task:")
    resource_req_df = pd.DataFrame(
        resource_requirements,
        index=[f"Task {i+1}" for i in range(n_tasks)],
        columns=[f"Resource {i+1}" for i in range(n_resources)]
    )
    print(resource_req_df)
    print()
    
    print("Resource Capacities for Each Robot:")
    resource_cap_df = pd.DataFrame(
        resource_capacities,
        index=[f"Robot {i+1}" for i in range(n_robots)],
        columns=[f"Resource {i+1}" for i in range(n_resources)]
    )
    print(resource_cap_df)
    print()
    
    # Create the optimization model
    model = LpProblem(name="robot-task-allocation", sense=LpMaximize)
    
    # Create decision variables
    # x[i,j] = 1 if robot i is assigned to task j, 0 otherwise
    x = {}
    for i in range(n_robots):
        for j in range(n_tasks):
            x[i, j] = LpVariable(name=f"x_{i}_{j}", cat="Binary")
    
    # Objective function: maximize total efficiency
    model += lpSum(efficiency_matrix[i, j] * x[i, j] for i in range(n_robots) for j in range(n_tasks))
    
    # Constraints:
    
    # 1. Each task can be assigned to at most one robot
    for j in range(n_tasks):
        model += lpSum(x[i, j] for i in range(n_robots)) <= 1
    
    # 2. Resource constraints for each robot
    for i in range(n_robots):
        for k in range(n_resources):
            model += lpSum(resource_requirements[j, k] * x[i, j] for j in range(n_tasks)) <= resource_capacities[i, k]
    
    # Solve the model
    model.solve()
    
    # Display results
    print(f"Status: {LpStatus[model.status]}")
    
    if LpStatus[model.status] == "Optimal":
        print("\nOptimal Allocation:")
        total_efficiency = 0
        allocation_matrix = np.zeros((n_robots, n_tasks))
        
        for i in range(n_robots):
            for j in range(n_tasks):
                if x[i, j].value() > 0.5:  # Binary variables might have small numerical errors
                    print(f"Assign Robot {i+1} to Task {j+1} (Efficiency: {efficiency_matrix[i, j]:.2f})")
                    allocation_matrix[i, j] = 1
                    total_efficiency += efficiency_matrix[i, j]
        
        print(f"\nTotal Efficiency: {total_efficiency:.2f}")
        
        # Calculate resource usage
        resource_usage = np.zeros((n_robots, n_resources))
        for i in range(n_robots):
            for j in range(n_tasks):
                if x[i, j].value() > 0.5:
                    for k in range(n_resources):
                        resource_usage[i, k] += resource_requirements[j, k]
        
        # Display resource usage
        print("\nResource Usage for Each Robot:")
        resource_usage_df = pd.DataFrame(
            resource_usage,
            index=[f"Robot {i+1}" for i in range(n_robots)],
            columns=[f"Resource {i+1}" for i in range(n_resources)]
        )
        print(resource_usage_df)
        
        # Calculate resource utilization percentage
        resource_util = resource_usage / resource_capacities * 100
        print("\nResource Utilization (%):")
        resource_util_df = pd.DataFrame(
            resource_util,
            index=[f"Robot {i+1}" for i in range(n_robots)],
            columns=[f"Resource {i+1}" for i in range(n_resources)]
        )
        print(resource_util_df)
        
        # Visualize the allocation and resource utilization
        fig, axes = plt.subplots(1, 2, figsize=(18, 8))
        
        # Plot allocation matrix
        sns.heatmap(allocation_matrix, annot=False, cmap="Blues", 
                   xticklabels=[f"Task {i+1}" for i in range(n_tasks)],
                   yticklabels=[f"Robot {i+1}" for i in range(n_robots)], ax=axes[0])
        
        # Add efficiency values where assigned
        for i in range(n_robots):
            for j in range(n_tasks):
                if allocation_matrix[i, j] > 0.5:
                    axes[0].text(j + 0.5, i + 0.5, f"{efficiency_matrix[i, j]:.1f}", 
                               ha='center', va='center', color='black', fontweight='bold')
        
        axes[0].set_title("Robot-Task Allocation", fontsize=14)
        
        # Plot resource utilization
        cmap = LinearSegmentedColormap.from_list('custom_cmap', ['white', 'lightgreen', 'green'], N=256)
        sns.heatmap(resource_util, annot=True, fmt=".1f", cmap=cmap, vmin=0, vmax=100,
                   xticklabels=[f"Resource {i+1}" for i in range(n_resources)],
                   yticklabels=[f"Robot {i+1}" for i in range(n_robots)], ax=axes[1])
        axes[1].set_title("Resource Utilization (%)", fontsize=14)
        
        plt.tight_layout()
        plt.show()
        
        # Plot task resource requirements
        plt.figure(figsize=(12, 6))
        bar_width = 0.25
        x = np.arange(n_tasks)
        
        for k in range(n_resources):
            plt.bar(x + k * bar_width, resource_requirements[:, k], 
                    width=bar_width, label=f'Resource {k+1}')
        
        plt.xlabel('Tasks')
        plt.ylabel('Resource Units Required')
        plt.title('Resource Requirements per Task')
        plt.xticks(x + bar_width, [f'Task {i+1}' for i in range(n_tasks)])
        plt.legend()
        plt.tight_layout()
        plt.show()

# Run the examples
simple_task_allocation()
resource_constrained_allocation()

Understanding the Code: A Deep Dive

Let’s break down the two approaches I’ve implemented for resource allocation in multi-agent systems:

Example 1: Simple Task Allocation with Hungarian Algorithm

The first example demonstrates a classic one-to-one matching problem where each robot can be assigned to exactly one task to maximize overall efficiency.
This is perfectly suited for the Hungarian algorithm (implemented in Python as linear_sum_assignment).

The key components of this implementation are:

  1. Efficiency Matrix: We create a matrix where each cell represents how efficiently a particular robot can perform a specific task.
    Higher values indicate better performance.

  2. Cost Matrix Conversion: Since the Hungarian algorithm minimizes cost, we negate the efficiency values to convert the maximization problem into a minimization one.

  3. Optimal Assignment: The algorithm returns the row and column indices that give us the optimal assignment.

The mathematical formulation of this problem can be represented as:

$$\max \sum_{i=1}^{n} \sum_{j=1}^{m} e_{ij} \cdot x_{ij}$$

Subject to:
$$\sum_{j=1}^{m} x_{ij} = 1 \quad \forall i$$
$$\sum_{i=1}^{n} x_{ij} = 1 \quad \forall j$$
$$x_{ij} \in {0, 1} \quad \forall i,j$$

Where:

  • $e_{ij}$ is the efficiency of robot $i$ performing task $j$
  • $x_{ij}$ is a binary variable that equals 1 if robot $i$ is assigned to task $j$, and 0 otherwise

Example 2: Resource-Constrained Allocation with Linear Programming

The second example tackles a more complex scenario where tasks require various resources, and robots have limited resource capacities.
This requires linear programming to solve (using PuLP library).

Key components include:

  1. Multiple Resources: Each task requires different amounts of multiple resource types.

  2. Resource Constraints: Each robot has limited capacity for each resource type.

  3. Binary Variables: We use binary variables to represent whether a robot is assigned to a task.

The mathematical formulation can be expressed as:

$$\max \sum_{i=1}^{n} \sum_{j=1}^{m} e_{ij} \cdot x_{ij}$$

Subject to:
$$\sum_{i=1}^{n} x_{ij} \leq 1 \quad \forall j$$
$$\sum_{j=1}^{m} r_{jk} \cdot x_{ij} \leq c_{ik} \quad \forall i, k$$
$$x_{ij} \in {0, 1} \quad \forall i,j$$

Where:

  • $e_{ij}$ is the efficiency of robot $i$ performing task $j$
  • $x_{ij}$ is a binary variable that equals 1 if robot $i$ is assigned to task $j$
  • $r_{jk}$ is the amount of resource $k$ required for task $j$
  • $c_{ik}$ is the capacity of resource $k$ available to robot $i$

Visualizing the Results

For the first example, we created a heatmap of the efficiency matrix with red circles highlighting the optimal assignments.
This makes it easy to see which robot is matched with which task.

For the resource-constrained example, we created multiple visualizations:

  1. Allocation Matrix: Shows which robot is assigned to which task along with the efficiency values.
Example 1: Simple Task Allocation Using Hungarian Algorithm
============================================================
Efficiency Matrix (Robot vs Task):
           Task 1    Task 2    Task 3    Task 4    Task 5
Robot 1  4.370861  9.556429  7.587945  6.387926  2.404168
Robot 2  2.403951  1.522753  8.795585  6.410035  7.372653
Robot 3  1.185260  9.729189  8.491984  2.911052  2.636425
Robot 4  2.650641  3.738180  5.722808  4.887505  3.621062
Robot 5  6.506676  2.255445  3.629302  4.297257  5.104630

Optimal Allocation:
Assign Robot 1 to Task 2 (Efficiency: 9.56)
Assign Robot 2 to Task 5 (Efficiency: 7.37)
Assign Robot 3 to Task 3 (Efficiency: 8.49)
Assign Robot 4 to Task 4 (Efficiency: 4.89)
Assign Robot 5 to Task 1 (Efficiency: 6.51)

Total Efficiency: 36.82

  1. Resource Utilization: Shows how much of each robot’s resource capacity is being used (as a percentage).
Example 2: Resource Constrained Allocation Using Linear Programming
============================================================
Task Efficiency Matrix (Robot vs Task):
           Task 1    Task 2    Task 3    Task 4    Task 5    Task 6
Robot 1  7.851760  1.996738  5.142344  5.924146  0.464504  6.075449
Robot 2  1.705241  0.650516  9.488855  9.656320  8.083973  3.046138
Robot 3  0.976721  6.842330  4.401525  1.220382  4.951769  0.343885
Robot 4  9.093204  2.587800  6.625223  3.117111  5.200680  5.467103

Resource Requirements for Each Task:
        Resource 1  Resource 2  Resource 3
Task 1           5           2           2
Task 2           4           2           2
Task 3           4           4           1
Task 4           5           5           2
Task 5           5           2           1
Task 6           4           4           4

Resource Capacities for Each Robot:
         Resource 1  Resource 2  Resource 3
Robot 1          13           5          13
Robot 2          11          13          12
Robot 3           5          12          12
Robot 4           7           5          12

Status: Optimal

Optimal Allocation:
Assign Robot 1 to Task 6 (Efficiency: 6.08)
Assign Robot 2 to Task 3 (Efficiency: 9.49)
Assign Robot 2 to Task 4 (Efficiency: 9.66)
Assign Robot 3 to Task 2 (Efficiency: 6.84)
Assign Robot 4 to Task 1 (Efficiency: 9.09)

Total Efficiency: 41.16

Resource Usage for Each Robot:
         Resource 1  Resource 2  Resource 3
Robot 1         4.0         4.0         4.0
Robot 2         9.0         9.0         3.0
Robot 3         4.0         2.0         2.0
Robot 4         5.0         2.0         2.0

Resource Utilization (%):
         Resource 1  Resource 2  Resource 3
Robot 1   30.769231   80.000000   30.769231
Robot 2   81.818182   69.230769   25.000000
Robot 3   80.000000   16.666667   16.666667
Robot 4   71.428571   40.000000   16.666667

  1. Task Resource Requirements: A bar chart showing how much of each resource is required by each task.

These visualizations help us understand the trade-offs and constraints in multi-agent resource allocation problems.

Practical Applications

This type of optimization is applicable in many real-world scenarios:

  • Cloud computing resource allocation
  • Supply chain management
  • Emergency service dispatch
  • Factory production planning
  • Network bandwidth allocation

By optimizing resource allocation, we can significantly improve efficiency and reduce costs in multi-agent systems.

Conclusion

Resource allocation in multi-agent systems represents a fascinating intersection of operations research and distributed computing.
The approaches demonstrated here—Hungarian algorithm for simple matching and linear programming for constrained optimization—provide powerful tools for solving these problems.

The key takeaway is that with the right mathematical formulation and optimization techniques, we can find efficient solutions to complex resource allocation problems, even with multiple constraints and objectives.