Combining Deep Reinforcement Learning with Search Heuristics for Solving Multi-Agent Path Finding in Segment-based Layouts

Robbert Reijnen, Yingqian Zhang, Wim P.M. Nuijten, Caglar Senaras, Mariana Goldak-Altgassen

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

131 Downloads (Pure)

Samenvatting

A multi-agent path finding (MAPF) problem is concerned with finding paths for multiple agents such that certain objectives, such as minimizing makespan, are reached in a conflict-free manner. In this paper, we solve a practical MAPF problem with automated guided vehicles (AGVs) for the conveying of luggage in segment-based layouts (MAPF-SL).Most existing algorithms for MAPF are mainly focused on grid environments. However, the conflict prevention problem is more challenging with segment-based layouts in which software is constrained to oversee that vehicles remain on predefined travel paths. Hence, the existing multi-agent path finding algorithms cannot be applied directly to solve MAPF-SL. In this paper, we propose an algorithm, called WHCA*S-RL, that combines Deep Reinforcement Learning (DRL) with a heuristic approach for solving MAPF-SL. DRL is used for determining travel directions while the heuristic approach oversees the planning in a segment-based layout. Our experiment results show that the proposed WHCA*S-RL approach can be successfully used for making path plans in which traffic congestion is both avoided and relieved. In this way, individual vehicles are found to reach goal destinations faster than the approach with search only.
Originele taal-2Engels
Titel2020 IEEE Symposium Series on Computational Intelligence (SSCI 2020)
UitgeverijIEEE Press
Pagina's2647-2654
Aantal pagina's8
ISBN van elektronische versie978-1-7281-2547-3
DOI's
StatusGepubliceerd - 5 jan 2021
Evenement2020 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2020): held virtually - Canberra, Australië
Duur: 1 dec 20204 dec 2020

Congres

Congres2020 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2020)
LandAustralië
StadCanberra
Periode1/12/204/12/20

Vingerafdruk Duik in de onderzoeksthema's van 'Combining Deep Reinforcement Learning with Search Heuristics for Solving Multi-Agent Path Finding in Segment-based Layouts'. Samen vormen ze een unieke vingerafdruk.

Citeer dit