Skip to content

atb033/multi_agent_path_planning

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

79 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.

python3 -m pip 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 (5, 5), 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 (5, 5), 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