%0 Conference Paper %1 alotaibi2019pathplanning %A Alotaibi, Ebtehal Turki Saho %B Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems %C Richland, SC %D 2019 %E Elkind, Edith %E Veloso, Manuela %E Agmon, Noa %E Taylor, Matthew E. %I International Foundation for Autonomous Agents and Multiagent Systems %K agent algorithms i40 multi path planning robot %P 158–160 %T A Complete Multi-Robot Path-Planning Algorithm: JAAMAS Track %X In the domain of multi-robot path-planning problems, robots must move from their start locations to their goal locations while avoiding collisions with each other. The goal of the research problem that has been tackled in 2 is to find complete solutions for multi-robot path-planning problem, the theoretical analyses already demonstrated the completeness of Push and Spin (PASp) algorithm. However, the PASp algorithm does not guarantee the optimality of the solution. In this work, some decisions are found within the complete solution that may optimize PASp performance. Two pluggable methods are proposed for this purpose; smooth operation, that aims to reduce the redundant moves in the generated paths, and heuristic search, that evaluates different alternative paths according to its occupancy by other robots. The improved version of PASp algorithm is referred to as PASp+ algorithm. The experimental results showed that, compared to PASp, Push and Swap (PAS), Push and Rotate (PAR), Bibox and the tractable multi-robot path-planning (MAPP) algorithms, adding heuristic search and smooth operation in PASp+ resulted a significant improvement shown in reducing the number of moves for all problem instances with high percentage reaches to 47.8%. However, in higher computation time. %@ 9781450363099

@inproceedings{alotaibi2019pathplanning, abstract = {In the domain of multi-robot path-planning problems, robots must move from their start locations to their goal locations while avoiding collisions with each other. The goal of the research problem that has been tackled in [2] is to find complete solutions for multi-robot path-planning problem, the theoretical analyses already demonstrated the completeness of Push and Spin (PASp) algorithm. However, the PASp algorithm does not guarantee the optimality of the solution. In this work, some decisions are found within the complete solution that may optimize PASp performance. Two pluggable methods are proposed for this purpose; smooth operation, that aims to reduce the redundant moves in the generated paths, and heuristic search, that evaluates different alternative paths according to its occupancy by other robots. The improved version of PASp algorithm is referred to as PASp+ algorithm. The experimental results showed that, compared to PASp, Push and Swap (PAS), Push and Rotate (PAR), Bibox and the tractable multi-robot path-planning (MAPP) algorithms, adding heuristic search and smooth operation in PASp+ resulted a significant improvement shown in reducing the number of moves for all problem instances with high percentage reaches to 47.8%. However, in higher computation time.}, added-at = {2020-04-01T12:42:10.000+0200}, address = {Richland, SC}, author = {Alotaibi, Ebtehal Turki Saho}, biburl = {https://www.bibsonomy.org/bibtex/2d72f030561b82d5f9030ee79ed19ac9f/porta}, booktitle = {Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems}, editor = {Elkind, Edith and Veloso, Manuela and Agmon, Noa and Taylor, Matthew E.}, interhash = {7a0e0619d248d2b10281d9fd0a404786}, intrahash = {d72f030561b82d5f9030ee79ed19ac9f}, isbn = {9781450363099}, keywords = {agent algorithms i40 multi path planning robot}, location = {Montreal QC, Canada}, numpages = {3}, pages = {158–160}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, series = {AAMAS ’19}, timestamp = {2020-04-01T12:43:03.000+0200}, title = {A Complete Multi-Robot Path-Planning Algorithm: JAAMAS Track}, year = 2019 }