CoT-Enhanced Multi-Agent Path Finding with LLMs

1. What problem are you going to solve?

We aim to address the Multi-Agent Path Finding (MAPF) problem. MAPF is a fundamental challenge involving the planning of paths for multiple agents, ensuring they can follow these paths concurrently without collisions. Application examples include autonomous aircraft towing vehicles, automated warehouse systems, office robots, and game characters in video games. Practical systems must find high-quality collision-free paths for such agents quickly.

2. Why did you decide to make it?

Existing MAPF algorithms fall into three main categories: reduction, rule-based, and search-based methods. Reduction-based methods transform MAPF into other well-studied problems like integer linear programming. Rule-based methods handle MAPF using primitive operations that dictate agent actions in various scenarios. Search-based methods employ heuristics, such as local search, and are dominant in practical applications.

While centralized search methods based on A* and M* algorithms are common, recent attention has turned to distributed frameworks combining reinforcement learning and imitation learning, yielding promising results. We approach this problem differently by leveraging the Chain-of-Thought (CoT) technique, an improved prompting method for LLMs. CoT enhances performance on complex reasoning tasks by incorporating intermediate reasoning steps, thereby significantly improving LLM's ability to solve difficult problems without model updates.

Our solution involves developing a multi-agent logistics framework based on a large language model (LLM). Traditional MAPF problems typically use abstract representations of agents, such as robots, trains, or planes. In contrast, our model integrates multiple individual models with advanced capabilities (e.g., logical reasoning, mathematical operations) to achieve genuine multi-agent collaboration.

3. How does it work?

• Data Engineering: We present a high-quality fine-tuning dataset of path-planning instructions, encompassing various scenarios and standard solution strategies.
• Modeling: We test the following baseline models: Qwen2-7B-Instruct and Llama-3-8B-Instruct. After evaluating these models, we fine-tune them using our curated high-quality dataset. This allows us to explore the impact of different data sources and input-output formats.
• Hardware and Software: We utilize ROCm™, AMD's open software AI stack, known for its potential to accelerate AI advancement similarly to CUDA, especially for LLM finetuning. AMD's recent "ROCm on Radeon" initiative extends support to AMD Radeon RX 7900 XTX and Radeon PRO W7900 GPUs. With ROCm's integration into PyTorch, a framework supporting automatic differentiation, backpropagation, tensor arithmetic, and Transformers, we have a robust foundation for achieving our optimizations.

Our project showcases a novel application of LLMs in solving the MAPF problem, highlighting the use of advanced techniques and state-of-the-art hardware. Visuals and videos demonstrating the model's performance and the setup process will be included to provide a comprehensive understanding of our work.

4. Step-by-Step Guide to Setting Up ROCm™ Software and PyTorch on Ubuntu

Step 1: Check Linux Version and Kernel Version

AMD updated the ROCm™ Software to version 6.1.2 on June 25, 2024. The installation instructions provided in this version detail the complete process for installing the AMD GPU ROCm™ software package. Before installation, ensure that your physical machine's Linux version and kernel version meet the ROCm™ Software installation requirements.

Retrieve Linux Distribution Information:

uname -m && cat /etc/*release

Output:

x86_64
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=22.04
DISTRIB_CODENAME=jammy
DISTRIB_DESCRIPTION="Ubuntu 22.04.4 LTS"
PRETTY_NAME="Ubuntu 22.04.4 LTS"
NAME="Ubuntu"
VERSION_ID="22.04"
VERSION="22.04.4 LTS (Jammy Jellyfish)"
VERSION_CODENAME=jammy
ID=ubuntu
ID_LIKE=debian
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
UBUNTU_CODENAME=jammy

Retrieve Linux Kernel Version:

uname -srmv

Output:

Linux 6.5.0-44-generic #44~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Tue Jun 18 14:36:16 UTC 2 x86_64

Step 2: Install ROCm™ Software 6.1.2

ROCm™ Software 6.1.2 Ubuntu Local Installation Instructions:

[More details please see ROCm™ Installation Guide]

ROCm supports two installation methods:

• Using the Linux distribution package manager (method used here)
• Running the `amdgpu-install` script

Both methods result in the same final installation.

• Using the distribution package manager allows users to install, upgrade, and uninstall using familiar commands and workflows. Third-party ecosystem support is similar to your OS package manager.
• The amdgpu-install script is a wrapper for the package manager. It installs the same packages as the package manager system. The installer automates the installation process of the AMDGPU and ROCm stack, including repository setup, system cleaning, updates, and driver and meta-package installation. Users unfamiliar with the package manager can choose this method to install ROCm.

Installation Steps:

1. Download and Convert Package Signing Key:

Create the directory if it doesn't exist yet.

sudo mkdir --parents --mode=0755 /etc/apt/keyrings

Download the key, convert the signing key to a fullkeyring required by apt and store in the keyring directory

wget https://repo.radeon.com/rocm/rocm.gpg.key -O - | \
gpg --dearmor | sudo tee /etc/apt/keyrings/rocm.gpg > /dev/null

Note: The GPG key may change; ensure to update it when installing a new version. If the key signature verification fails during the update, re-add the key to the apt repository as described above.

2. Register Kernel Mode Driver and Add AMD GPU Repository:

# For Ubuntu 22.04

echo "deb [arch=amd64 signed-by=/etc/apt/keyrings/rocm.gpg] https://repo.radeon.com/amdgpu/6.1.2/ubuntu jammy main" | sudo tee /etc/apt/sources.list.d/amdgpu.list

sudo apt update

3. Register ROCm:

# For Ubuntu 22.04

echo "deb [arch=amd64 signed-by=/etc/apt/keyrings/rocm.gpg] https://repo.radeon.com/rocm/apt/6.1.2 jammy main" | sudo tee --append /etc/apt/sources.list.d/rocm.list

echo -e 'Package: *\nPin: release o=repo.radeon.com\nPin-Priority: 600' | sudo tee /etc/apt/preferences.d/rocm-pin-600

sudo apt update

4. Install Kernel:

sudo apt install amdgpu-dkms
sudo reboot

5. Install ROCm:

sudo apt install rocm

6. Configure System Linker:

Indicate where the system linker can find the ROCm application shared objects

sudo tee --append /etc/ld.so.conf.d/rocm.conf <<EOF
/opt/rocm/lib
/opt/rocm/lib64
EOF
sudo ldconfig

7. Configure PATH:

Add the binary path to the PATH environment variable

export PATH=$PATH:/opt/rocm-6.1.2/bin

8. Verify Kernel Mode Driver Installation:

dkms status

Expected output:

amdgpu/6.7.0-1781449.20.04, 6.5.0-44-generic, x86_64: installed

9. Verify ROCm Installation:

/opt/rocm-6.1.2/bin/rocminfo
/opt/rocm-6.1.2/bin/clinfo

10. Verify Package Installation:

sudo apt list --installed

Expected output:

amdgpu-dkms-firmware/focal,now 1:6.7.0.60102-1781449.20.04 all [installed,automatic]
amdgpu-dkms/focal,now 1:6.7.0.60102-1781449.20.04 all [installed]
rocm-core/focal,now 6.1.2.60102-119~20.04 amd64 [installed,automatic]
rocm-smi-lib/focal,now 7.2.0.60102-119~20.04 amd64 [installed,automatic]
python3.10-dev/jammy-updates,jammy-security,jammy-security,jammy-updates,now 3.10.12-1~22.04.4 amd64 [installed,automatic]
python3.10-minimal/jammy-updates,jammy-security,jammy-security,jammy-updates,now 3.10.12-1~22.04.4 amd64 [installed,automatic]
python3.10/jammy-updates,jammy-security,jammy-security,jammy-updates,now 3.10.12-1~22.04.4 amd64 [installed,automatic]
python3/jammy-updates,jammy-security,jammy-security,jammy-updates,now 3.10.6-1~22.04 amd64 [installed,automatic]

Step 3: Install PyTorch

PyTorch is an open-source tensor library designed for deep learning. PyTorch on ROCm uses our MIOpen and RCCL libraries to provide mixed precision and large-scale training. To install PyTorch on ROCm, follow these steps:

1. Install Required Dependencies for Wheels Packages:

sudo apt update
sudo apt install libjpeg-dev python3-dev python3-pip
pip3 install wheel setuptools

2. Install Torch, Torchvision, and Torchaudio:

The command below uses the ROCm 6.1 PyTorch wheel. Modify accordingly if you need a different version of ROCm.

pip3 install --pre torch torchvision torchaudio --index-url https://download.pytorch.org/whl/nightly/rocm6.1/

3. Verify PyTorch Installation Using Unit Tests:

- Clone the PyTorch examples repository.

git clone https://github.com/pytorch/examples.git

- Navigate to the MNIST example folder.

cd examples/mnist

- Follow the instructions in the `README.md` file in this folder to install the required dependencies. Then run:

python3 main.py

Expected output:

Train Epoch: 14 [58240/60000 (97%)]     Loss: 0.010128
Train Epoch: 14 [58880/60000 (98%)]     Loss: 0.001348
Train Epoch: 14 [59520/60000 (99%)]     Loss: 0.005261
Test set: Average loss: 0.0252, Accuracy: 9921/10000 (99%)

The following is a video of our testing process with PyTorch installed running the MNIST dataset.

In addition, we ran the MNIST dataset using CPUs for comparison tests. Here is a video of the test.

Tip: You can monitor GPU usage using the radeontop tool.

Install AMD GPU Performance Monitoring Script:

sudo apt-get install radeontop

Launch the Script:

radeontop

Common Errors and Solutions

1. Permission Issue

pip install --upgrade peft

Solution: Use `sudo` to gain necessary permissions.

sudo pip install --upgrade peft

2. Missing Module peft:

ModuleNotFoundError: No module named 'peft'

Solution: Install the missing package.

sudo pip3 install peft

3. Missing Package Metadata for 'trl':

importlib.metadata.PackageNotFoundError: No package metadata was found for trl

Solution: Reinstall the required version.

sudo pip install trl>=0.8.6

4. Missing Module 'pydantic':

ModuleNotFoundError: No module named 'pydantic'

Solution: Reinstall the missing package.

sudo pip install pydantic

5. Undefined Name 'gr':

NameError: name 'gr' is not defined

Solution: Install the missing package.

sudo pip install gradio

This guide should help you set up ROCm™ Software and PyTorch on Ubuntu efficiently, along with troubleshooting common issues

5. Optimizing LLMs through Fine-Tuning with the AMD Radeon PRO W7900

Fine-tuning a model involves adjusting the parameters of a pre-trained or base model to adapt it to a specific task or dataset, which can improve the model's performance and accuracy. This process entails providing new data to the model and modifying its weights, biases, and certain parameters. This approach allows the new model to achieve better performance on the target task or dataset without the need to develop a model from scratch, thereby saving time and resources.

LLaMa-Factory, a recent prominent open-source project, has attracted significant attention from a large number of developers and researchers due to its efficiency and flexibility. This paper will provide a detailed demonstration of how to use the LLaMa-Factory framework for fine-tuning large language models.

In this video, we demonstrate how to leverage the AMD Radeon PRO W7900 GPU to fine-tune large language models using the Llama Factory library. You will see us step-by-step configuring the Llama Factory and walk through the entire fine-tuning process. This approach can effectively optimize model performance and enhance its capabilities for specific tasks.

The AMD Radeon PRO W7900 GPU provides powerful parallel computing capabilities, making it an ideal hardware solution for efficient large language model fine-tuning.

6. Exporting and Evaluating Fine-Tuned LLMs with AMD Radeon PRO W7900

In this video, we demonstrate exporting and evaluating a large language model (LLM) fine-tuned using Supervised Fine-Tuning (SFT) on the AMD Radeon PRO W7900 GPU.

First, we create a folder to export and save the fine-tuned model. We review the training progress through the loss curve and adjust the model file size. Next, we export the model, monitoring GPU utilization with Radeontop. We then test the fine-tuned model, updating the import path and evaluating its performance with English and Chinese inputs.

If you would like to learn more detailed information about this project, please visit our project homepage-1 and homepage-2.

7. Acknowledgement

I would like to express my sincere gratitude to the organizers of the AMD Pervasive AI Developer Challenge 2023 for providing the hardware support that enabled this project. Furthermore, I would like to convey my sincere appreciation to the diligent personnel of AMD China as well as the hardworking members of the Hackster community.

AMD, Yes!