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 |
git clone https://github.com/Kei18/tswap.git --recursive
cd tswap
mkdir build
cd build
cmake ..
make
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.
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),[...]
[...]
@Kei18/mapf-visualizer is available.
auto formatting with commit (by clang-format)
git config core.hooksPath .githooks && chmod a+x .githooks/pre-commit
This software is released under the MIT License, see LICENCE.txt.
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 themaps/
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.
- 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.
- 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).