Need help with multi_agent_path_planning?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

About the developer

atb033
178 Stars 54 Forks MIT License 68 Commits 0 Opened issues

Description

This repository consists of the Python implementation of a few multi-robot path-planning algorithms.

Services available

!
?

Need anything else?

Contributors list

# 276,368
Robotic...
Shell
JavaScr...
CSS
61 commits

Multi-Agent path planning in python

Introduction

This repository consists of the implementation of some multi-agent path-planning algorithms in Python. The following algorithms are currently implemented:

Dependencies

Install the necessary dependencies by running

pip3 install -r requirements.txt

Centralized Solutions

In these methods, it is the responsibility of the central planner to provide a plan to the robots.

Prioritized Safe-Interval Path Planning

SIPP is a local planner, using which, a collision-free plan can be generated, after considering the static and dynamic obstacles in the environment. In the case of multi-agent path planning, the other agents in the environment are considered as dynamic obstacles.

Execution

For SIPP multi-agent prioritized planning, run:

cd ./centralized/sipp
python3 multi_sipp.py input.yaml output.yaml

Results

To visualize the generated results

python3 visualize_sipp.py input.yaml output.yaml 

To record video

python3 visualize_sipp.py input.yaml output.yaml --video 'sipp.avi' --speed 1

| Test 1 (Success) | Test 2 (Failure) | |:--------------------------------------:|:--------------------------------------:| | Success | Failure|

Reference

Conflict Based Search

Conclict-Based Search (CBS), is a multi-agent global path planner.

Execution

Run:

cd ./centralized/cbs
python3 cbs.py input.yaml output.yaml

Results

To visualize the generated results:

python3 ../visualize.py input.yaml output.yaml

| Test 1 (Success) | Test 2 (Success) | |:------------------------------------:|:------------------------------------:| |Success | Failure|

| 8x8 grid | 32x32 grid | |:-----------------------------------:|:-----------------------------------:| | Test 3 | Test 4|

Reference

Post-Processing

Post-processing with TPG

The plan, which is computed in discrete time, can be postprocessed to generate a plan-execution schedule, that takes care of the kinematic constraints as well as imperfections in plan execution.

This work is based on: Multi-Agent Path Finding with Kinematic Constraints

Once the plan is generated using CBS, please run the following to generate the plan-execution schedule:

cd ./centralized/scheduling
python3 minimize.py ../cbs/output.yaml real_schedule.yaml

Decentralized solutions

In this approach, it is the responsibility of each robot to find a feasible path. Each robot sees other robots as dynamic obstacles, and tries to compute a control velocity which would avoid collisions with these dynamic obstacles.

Velocity obstacles

Execution

cd ./decentralized
python3 decentralized.py -f velocity_obstacle/velocity_obstacle.avi -m velocity_obstacle

Results

  • Test 1: The robot tries to stay at (0, 0), while avoiding collisions with the dynamic obstacles
  • Test 2: The robot moves from (5, 0) to (5, 10), while avoiding obstacles

| Test 1|Test 2| | :------------: | :------------: | |Test1|Test2|

References

Nonlinear Model-Predictive Control

Execution

cd ./decentralized
python3 decentralized.py -m nmpc

Results

  • Test 1: The robot tries to stay at (0, 0), while avoiding collisions with the dynamic obstacles
  • Test 2: The robot moves from (5, 0) to (5, 10), while avoiding obstacles

| Test 1|Test 2| | :------------: | :------------: | |Test1|Test2|

References

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.