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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

131 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication2020 IEEE Symposium Series on Computational Intelligence (SSCI 2020)
PublisherIEEE Press
Pages2647-2654
Number of pages8
ISBN (Electronic)978-1-7281-2547-3
DOIs
Publication statusPublished - 5 Jan 2021
Event2020 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2020): held virtually - Canberra, Australia
Duration: 1 Dec 20204 Dec 2020

Conference

Conference2020 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2020)
CountryAustralia
CityCanberra
Period1/12/204/12/20

Keywords

  • automated guided vehicles
  • deep reinforcement learning
  • multi-agent path finding
  • path planning

Fingerprint Dive into the research topics of 'Combining Deep Reinforcement Learning with Search Heuristics for Solving Multi-Agent Path Finding in Segment-based Layouts'. Together they form a unique fingerprint.

Cite this