tswap

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 | | | ubuntu-latest | |

News

• Aug 2025: A toy Python implementation is now available: pytswap

Demo

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:
• ICAPS-22:

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).