Skip to main content

No project description provided

Project description

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:

Temporary Instructions for Running

Install poetry by running the following cmd (unix)

curl -sSL https://install.python-poetry.org | python3 -

Check install

poetry --version

If install isnt sourced, add to bash_rc (ubuntu) or bash_profile (mac), and source. (Clean this up if this is bad practice)

export PATH=$PATH:$HOME/.local/bin source ~/.bash_profile

Navigate to folder which contains pyproject.toml , and run

poetry install

poetry shell

Deactivate any other venvs including conda...

conda deactivate

Running

Run with the following,

sh scripts/lifelong_MAPF.sh

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

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

multi_agent_path_planning-0.1.0.tar.gz (6.7 MB view details)

Uploaded Source

Built Distribution

File details

Details for the file multi_agent_path_planning-0.1.0.tar.gz.

File metadata

  • Download URL: multi_agent_path_planning-0.1.0.tar.gz
  • Upload date:
  • Size: 6.7 MB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: poetry/1.4.0 CPython/3.8.10 Linux/5.15.0-69-generic

File hashes

Hashes for multi_agent_path_planning-0.1.0.tar.gz
Algorithm Hash digest
SHA256 6ed07762c1c26c92e7080337f8a8628c2eaf2d094526ecd08316b380d06d6fb3
MD5 8d6596ac80c2adc869b8302e141d3eee
BLAKE2b-256 9661d3c5838724c26e15b3b510a67f9681dc276ee252dd11fcbf9cf2476554b7

See more details on using hashes here.

File details

Details for the file multi_agent_path_planning-0.1.0-py3-none-any.whl.

File metadata

File hashes

Hashes for multi_agent_path_planning-0.1.0-py3-none-any.whl
Algorithm Hash digest
SHA256 e23379f84d3ddefad9deb995339dfe43842a8730957dfe355b4506a94d886c4d
MD5 346bb4e0de811bca88084fbbe39c52da
BLAKE2b-256 13c1567d68ca4eb40a853bed3eac6a3799dff8bf824dfc018b890116dccd2f91

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page