/Layered-MAPF

A Layered Approach for Multi-Agent Path Finding

Primary LanguageShaderLab

A Layered Approach for Multi-Agent Path Finding

Simulation platform of a Layered Approach for Multi-Agent Path Finding (MAPF).

1. Introduction

Layered MAPF is a newly proposed algorithm for solving Multi-Agent Path Finding (MAPF) problems. This algorithm adopts a hybrid cloud-edge-terminal architecture, which consists of one centralized cloud server and multiple decentralized edge servers and terminals (robots). The robots plan their path using a two-level A* algorithm guided by heat maps, improving computing efficiency and avoiding most potential conflicts.

2. Demo

Demo videos can be found following this link: https://www.bilibili.com/video/BV1KG4y1n76b/

  • 2D Simulation View

  • 3D Simulation View

  • Heat Map Visualizer

    • Heat Map using T-Shape Generation Algorithm

    • Heat Map using Circle-Gaussian Generation Algorithm

  • Map Editor

    Edit grid map with MS Excel and save as csv files.

  • Map Converter

    Convert csv maps (including robot arrangements) to json files. The simulation program will read json files at runtime before the simulation begins.

  • Random Task Generator

    Generate random tasks given the json maps and corresponding robot arrangements.

3. Algorithm Architecture

Layered Architecture:

Flow Chart:

3.1 Offline Preprocessing Phase

Original Map:

Partitioned Map and Topological Map:

3.2 Online Scheduling Phase

Online Scheduling Phase: Two-level A* algorithm guided by heat maps

  • Heat Map Generation (For one single agent):

    • T-Shape Generation Algorithm is shown as an example.

  • Complete Heat Map (with all agents included):

4. Environment

  • Unity 2019.4.5f1

Please check the wiki to see how to use this program.