/tswap

Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution (ICAPS-22; AIJ-23)

Primary LanguageC++MIT LicenseMIT

tswap

MIT License

The code repository of the paper "Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution" (TSWAP; ICAPS-22 & AIJ-23).

  • It is written in C++(17) with CMake build and tested on MacOS 10.15.
  • The implementations include: the makespan optimal algorithm [1] and TSWAP (sub-optimal, complete).
platform status (master)
macos-latest test_macos
ubuntu-latest test_ubuntu

Demo

demo in a small field, flocking-like

demo in a large field

Building

git clone https://github.com/Kei18/tswap.git --recursive
cd tswap
mkdir build
cd build
cmake ..
make

Usage

TSWAP (sub-optimal complete)

./app -i ../sample-instance.txt -s TSWAP -o result.txt -v

FlowNetwork (makespan optimal, the result is saved in result.txt)

./app -i ../instances/random-32-32-20_70agents_1.txt -s FlowNetwork -v

You can find details and explanations for all parameters with:

./app --help

Please see instances/sample.txt for parameters of instances, e.g., filed, number of agents, time limit, etc.

Output File

This is an example output of ../instances/sample.txt. Note that (x, y) denotes location. (0, 0) is the left-top point. (x, 0) is the location at x-th column and 1st row.

instance=../instances/sample.txt
agents=100
map_file=arena.map
solver=TSWAP
solved=1
soc=1864
makespan=30
comp_time=91
internal_info=
elapsed_assignment:82
elapsed_path_planning:9
estimated_soc:1602
estimated_makespan:29
starts=(32,21),(18,22),(29,19),(26,24),[...]
goals=(39,4),(23,18),(46,2),(26,26),[...]
solution=
0:(32,21),(18,22),(29,19),(26,24),[...]
1:(32,20),(18,21),(30,19),(26,23),[...]
[...]

Visualizer

@Kei18/mapf-visualizer is available.

Experimental Environment

  • AIJ-23: v1.3
  • ICAPS-22: v1.2

Utilities

auto formatting with commit (by clang-format)

git config core.hooksPath .githooks && chmod a+x .githooks/pre-commit

Licence

This software is released under the MIT License, see LICENCE.txt.

Notes

  • NaiveTSWAP is a solver using the pseudo-code in the paper without modifications. TSWAP uses a priority queue to achieve efficient agents' moves.
  • Maps in maps/ are from MAPF benchmarks. When you add a new map, please place it in the maps/ directory.
  • The font in visualizer/bin/data is from Google Fonts.
  • Scripts for the experiments are in exp_scripts/.
  • tests/ include test scripts.
  • The implementation of ECBS-TA [2] can be obtained Wolfgang's excellent repository.

Reference

  1. Yu, J., & LaValle, S. M. (2013). Multi-agent path planning and network flow. In Algorithmic foundations of robotics X (pp. 157-173). Springer, Berlin, Heidelberg.
  2. Hönig, W., Kiesel, S., Tinka, A., Durham, J., & Ayanian, N. (2018). Conflict-based search with optimal task assignment. In Proc. Int. Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS).