MAPF-LNS2* algorithm based on fast repair and parallelization

Wenhao Geng; Niansheng Chen; Xiaoyong Song; Songlin Cheng

doi:10.1117/12.3025682

6 May 2024 MAPF-LNS2* algorithm based on fast repair and parallelization

Wenhao Geng, Niansheng Chen, Xiaoyong Song, Songlin Cheng

Proceedings Volume 13161, Fourth International Conference on Telecommunications, Optics, and Computer Science (TOCS 2023); 131610K (2024) https://doi.org/10.1117/12.3025682
Event: Fourth International Conference on Telecommunications, Optics and Computer Science (TOCS 2023), 2023, Xi’an, China

Abstract

Aiming at the problem of time loss caused by weight distribution imbalance in ALNS module of MAPF-LNS2 algorithm, ALNS+ module is proposed by introducing improvement rate statistics, time window, improvement rate trend judgment function and other mechanisms. Compared with the ALNS module, the ALNS+ module considers the recent improvement rate trend of the neighborhood search strategy, and switches to other neighborhood search strategies when the trend decreases, so as to repair the excessive weight allocation in time and reduce the time loss. The experimental results show that the ALNS+ module achieves a significant improvement in running time, and the maximum reduction is 65.1%. However, in scenarios such as denser agents, the execution success rate of the improved module has a significant downward trend. The PNS module was proposed to speed up the neighborhood repair process by introducing a parallelization method to parallel the neighborhood search process on multiple processor cores. The comparative experimental results show that the PNS module has a significant improvement in the success rate, with a maximum increase of 40%. By integrating the ALNS+ and PNS modules into the MAPF-LNS2 algorithm framework, the MAPF-LNS2* algorithm was proposed. The simulation results show that the MAPF-LNS2* algorithm effectively solves the problem of time loss in the MAPF-LNS2 algorithm, and effectively reduces the failure rate in the agent dense scene.

(2024) Published by SPIE. Downloading of the abstract is permitted for personal use only.

Citation Download Citation

Wenhao Geng, Niansheng Chen, Xiaoyong Song, and Songlin Cheng "MAPF-LNS2* algorithm based on fast repair and parallelization", Proc. SPIE 13161, Fourth International Conference on Telecommunications, Optics, and Computer Science (TOCS 2023), 131610K (6 May 2024); https://doi.org/10.1117/12.3025682

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available