Asynchronous Decentralized Prioritized Planning

In this work we designed an asynchronous decentralized variant of prioritized planning scheme. The algorithm exploits the inherent parallelism of distributed systems and allows for a speed up of the computation process. We provide a proof of correctness of the algorithm and experimentally evaluate them on synthetic domains. Further we deploy the algorithm as a conflict resolution technique for a multi-UAV system.

Conference:

M. Čáp, P. Novák, M. Selecký, J. Faigl, and J. Vokřínek, “Asynchronous decentralized prioritized planning for coordination in multi-robot system,” in Intelligent robots and systems (IROS), 2013, 2013.
[Bibtex]

@inproceedings{cap_2013_b,
author = "Michal \v{C}\'{a}p and Peter Nov\'{a}k and Martin Seleck\'{y} and Jan Faigl and Ji\v{r}\'{i} Vok\v{r}\'{i}nek",
title = "Asynchronous Decentralized Prioritized Planning for Coordination in Multi-Robot System",
booktitle = "Intelligent Robots and Systems ({IROS}), 2013",
year = "2013",
webpage = {http://michalcap.net/adpp/},
video={https://www.youtube.com/watch?t=1&v=Y4ZEErSyCF8},
slides = "http://michalcap.net/wp-content/papercite-data/pdf/cap_2013_b-slides.svg",
}

Workshop:

M. Čáp, P. Novák, J. Vokřínek, and M. Pěchouček, “Asynchronous decentralized algorithm for space-time cooperative pathfinding,” in Spatio-temporal dynamics workshop (stedy), sfb/tr 8 spatial cognition center report, no. 030-08/2012, 2012.
[Bibtex]

@inproceedings{cap_2012_b,
author = {Michal \v{C}\'{a}p and Peter Nov\'{a}k and Ji\v{r}\'{i} Vok\v{r}\'{i}nek and Michal P\v{e}chou\v{c}ek},
title = {Asynchronous Decentralized Algorithm for Space-Time Cooperative Pathfinding},
booktitle = {Spatio-Temporal Dynamics Workshop (STeDy), SFB/TR 8 Spatial Cognition Center Report, No. 030-08/2012},
year = {2012},
webpage = {http://michalcap.net/adpp/}
}

Source code: The experimental environment used to generate the results in the latter two papers can be downloaded here.

Videos

Overview video

Real-world environment

At the begining of each video, the task of each agent is shown as a thin blue arrow. Then, the multi-robot cooperative pathfinding algorithm AD-RPP is started. Note that since the parallel execution is simulated in one thread, the computation time in the video does not correspond to the wall-clock time. The thick lines in color represent the current trajectory of each agent, the red circles are spatio-temporal conflicts between the trajectories. When the solution is found, we show simulated execution of the final trajectories.

Synthetic scenarios

At the begining of each video, the objectives of each agent are shown as a thin black arrow. Then, the cooperative pathfinding algorithm IADPP is started. Note that since the parallel execution is simulated in one thread, the computation time in the video does not correspond to the wall-clock time. The thick dotted lines in color represent the current trajectory of each agent, the red circles are spatio-temporal conflicts between the trajectories. When the solution is found, we simulate the execution of the final trajectories.