Multi-objective Task Assignment and Multiagent Planning with Hybrid GPU-CPU Acceleration

Thomas Robinson, Guoxin Su

Introduction

In the field of Multiagent Systems (MAS), coordinating a fleet of autonomous agents to perform complex tasks remains a significant computational challenge. Most modern frameworks utilize Markov Decision Processes (MDPs) to account for the inherent uncertainty of real-world environments. However, these models frequently encounter the "state-space explosion" problem: as the number of agents increases, the complexity of the joint state space grows exponentially, rendering centralized planning intractable for large-scale operations.

Furthermore, real-world missions often involve conflicting objectives, such as minimizing completion time while maximizing the probability of success. Identifying the Pareto-optimal solutions—where one objective cannot be improved without degrading another—is traditionally computationally expensive. This paper addresses the Multi-Objective Random Assignment and Planning (MORAP) problem, proposing a framework that achieves linear scalability and significant speedups through mathematical decentralization and hybrid hardware acceleration.

Methodology

1. Mathematical Decentralization

The core innovation of this research is the proof that the MORAP problem, typically modeled as a massive centralized system, can be decomposed into independent agent-task pairs. By decentralizing the problem, the authors shift the computational complexity from exponential to linear relative to the number of agents ($n$). This allows the system to handle hundreds of agents in scenarios where centralized models would fail due to memory exhaustion.

2. Point-Oriented Pareto Computation

Rather than attempting to map the entire Pareto frontier—an exhaustive and often unnecessary process—the authors developed a point-oriented algorithm. This approach focuses on a specific target point (e.g., "Can the task be completed in under 10 minutes with 95% reliability?").

The solution space for these objectives is shown to be a convex polytope. Leveraging this property, the algorithm uses iterative linear programming techniques to converge on the target point. If the specific requirements are infeasible, the system identifies the closest possible alternative, providing a practical solution for mission-critical planning.

3. Hybrid GPU-CPU Architecture

To implement this decentralized approach at scale, the researchers developed a high-performance framework using Rust for safe concurrency and CUDA for GPU acceleration. The architecture treats the CPU and GPU as a unified resource pool.

A key feature of this system is its "work-stealing" load balancer. Because the decentralized models are independent (an "embarrassingly parallel" problem), they can be processed simultaneously across different hardware cores. If a CPU core completes its assigned tasks early, it "steals" work from a busy queue, ensuring maximum hardware utilization and minimizing idle time.

Experimental Evaluation

The framework was evaluated using a Robotic Mobile Fulfillment System (RMFS) simulation, representing a smart warehouse environment.

  • Environment: Robots were tasked with picking up racks and moving them to workstations in $6 \times 6$ and $12 \times 12$ grid worlds.
  • Scalability: Testing ranged from 2 to 100 agents.
  • Benchmarks: The system was compared against industry-standard probabilistic model checkers, including Prism and Storm.

Key Results

  • Linear Scalability: While centralized models crashed due to memory errors at approximately 50 agents in a $6 \times 6$ grid, the decentralized approach successfully managed 100 agents without performance degradation.
  • Hardware Speedups: In a $12 \times 12$ warehouse with 30 agents, the hybrid GPU-CPU approach completed iterations in approximately 15 seconds. In contrast, a single-core CPU implementation timed out, demonstrating the necessity of parallel acceleration for large-scale tasks.
  • Competitive Efficiency: Even in single-agent scenarios where the decentralization advantage was minimized, the custom Rust/CUDA implementation remained faster than or competitive with Prism and Storm.

Discussion and Future Work

The research identifies a primary bottleneck in the PCIe bus: for very small models, the time required to transfer data to the GPU can exceed the actual computation time. Future iterations of the framework may utilize CUDA streams to overlap data transfer with computation, effectively hiding this latency.

Currently, the framework focuses on "co-safe LTL" properties—tasks that must be completed in finite time. The authors plan to extend this work to $\omega$-regular properties, which would enable the modeling of infinite-horizon tasks such as continuous environmental monitoring or long-term facility maintenance.

By combining mathematical decomposition with modern parallel computing, this framework provides a robust path forward for deploying large-scale, multi-objective robotic fleets in complex industrial environments.

Summary updated

Abstract

Allocation and planning with a collection of tasks and a group of agents is an important problem in multiagent systems. One commonly faced bottleneck is scalability, as in general the multiagent model increases exponentially in size with the number of agents. We consider the combination of random task assignment and multiagent planning under multiple-objective constraints, and show that this problem can be decentralised to individual agent-task models. We present an algorithm of point-oriented Pareto computation, which checks whether a point corresponding to given cost and probability thresholds for our formal problem is feasible or not. If the given point is infeasible, our algorithm finds a Pareto-optimal point which is closest to the given point. We provide the first multi-objective model checking framework that simultaneously uses GPU and multi-core acceleration. Our framework manages CPU and GPU devices as a load balancing problem for parallel computation. Our experiments demonstrate that parallelisation achieves significant run time speed-up over sequential computation.
BibTeX
@inproceedings{robinson2023multi,
  author = {Thomas Robinson and Guoxin Su},
  title = {{Multi-objective Task Assignment and Multiagent Planning with Hybrid GPU-CPU Acceleration}},
  booktitle = {NFM},
  year = {2023},
  doi = {10.1007/978-3-031-33170-1\_16},
}
Figure