A Bi-Level Path Planning Algorithm for Multi-AGV Routing Problem
Avoiding the multi-automated guided vehicle (AGV) path conflicts is of importance for the efficiency of the AGV system, and we propose a bi-level path planning algorithm to optimize the routing of multi-AGVs. In the first level, we propose an improved A* algorithm to plan the AGV global path in the...
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2020-08-01
|
Series: | Electronics |
Subjects: | |
Online Access: | https://www.mdpi.com/2079-9292/9/9/1351 |
_version_ | 1797556679865270272 |
---|---|
author | Zhiheng Yuan Zhengmao Yang Lingling Lv Yanjun Shi |
author_facet | Zhiheng Yuan Zhengmao Yang Lingling Lv Yanjun Shi |
author_sort | Zhiheng Yuan |
collection | DOAJ |
description | Avoiding the multi-automated guided vehicle (AGV) path conflicts is of importance for the efficiency of the AGV system, and we propose a bi-level path planning algorithm to optimize the routing of multi-AGVs. In the first level, we propose an improved A* algorithm to plan the AGV global path in the global topology map, which aims to make the path shortest and reduce the AGV path conflicts as much as possible. In the second level, we present the dynamic rapidly-exploring random trees (RRT) algorithm with kinematic constraints to obtain the passable local path with collisions in the local grid map. Compared to the Dijkstra algorithm and classic A* algorithm, the simulation results showed that the proposed bi-level path planning algorithm performed well in terms of the search efficiency, significantly reducing the incidence of multiple AGV path conflicts. |
first_indexed | 2024-03-10T17:05:18Z |
format | Article |
id | doaj.art-d711e8dffe344fd8a7fc86a4917d1674 |
institution | Directory Open Access Journal |
issn | 2079-9292 |
language | English |
last_indexed | 2024-03-10T17:05:18Z |
publishDate | 2020-08-01 |
publisher | MDPI AG |
record_format | Article |
series | Electronics |
spelling | doaj.art-d711e8dffe344fd8a7fc86a4917d16742023-11-20T10:50:26ZengMDPI AGElectronics2079-92922020-08-0199135110.3390/electronics9091351A Bi-Level Path Planning Algorithm for Multi-AGV Routing ProblemZhiheng Yuan0Zhengmao Yang1Lingling Lv2Yanjun Shi3School of Mechanical Engineering, Dalian University of Technology, Dalian 116024, ChinaSchool of Mechanical Engineering, Dalian University of Technology, Dalian 116024, ChinaSchool of Mechanical Engineering, Dalian University of Technology, Dalian 116024, ChinaSchool of Mechanical Engineering, Dalian University of Technology, Dalian 116024, ChinaAvoiding the multi-automated guided vehicle (AGV) path conflicts is of importance for the efficiency of the AGV system, and we propose a bi-level path planning algorithm to optimize the routing of multi-AGVs. In the first level, we propose an improved A* algorithm to plan the AGV global path in the global topology map, which aims to make the path shortest and reduce the AGV path conflicts as much as possible. In the second level, we present the dynamic rapidly-exploring random trees (RRT) algorithm with kinematic constraints to obtain the passable local path with collisions in the local grid map. Compared to the Dijkstra algorithm and classic A* algorithm, the simulation results showed that the proposed bi-level path planning algorithm performed well in terms of the search efficiency, significantly reducing the incidence of multiple AGV path conflicts.https://www.mdpi.com/2079-9292/9/9/1351AGVthe bi-level path planning algorithmA* algorithmkinematic constraint |
spellingShingle | Zhiheng Yuan Zhengmao Yang Lingling Lv Yanjun Shi A Bi-Level Path Planning Algorithm for Multi-AGV Routing Problem Electronics AGV the bi-level path planning algorithm A* algorithm kinematic constraint |
title | A Bi-Level Path Planning Algorithm for Multi-AGV Routing Problem |
title_full | A Bi-Level Path Planning Algorithm for Multi-AGV Routing Problem |
title_fullStr | A Bi-Level Path Planning Algorithm for Multi-AGV Routing Problem |
title_full_unstemmed | A Bi-Level Path Planning Algorithm for Multi-AGV Routing Problem |
title_short | A Bi-Level Path Planning Algorithm for Multi-AGV Routing Problem |
title_sort | bi level path planning algorithm for multi agv routing problem |
topic | AGV the bi-level path planning algorithm A* algorithm kinematic constraint |
url | https://www.mdpi.com/2079-9292/9/9/1351 |
work_keys_str_mv | AT zhihengyuan abilevelpathplanningalgorithmformultiagvroutingproblem AT zhengmaoyang abilevelpathplanningalgorithmformultiagvroutingproblem AT linglinglv abilevelpathplanningalgorithmformultiagvroutingproblem AT yanjunshi abilevelpathplanningalgorithmformultiagvroutingproblem AT zhihengyuan bilevelpathplanningalgorithmformultiagvroutingproblem AT zhengmaoyang bilevelpathplanningalgorithmformultiagvroutingproblem AT linglinglv bilevelpathplanningalgorithmformultiagvroutingproblem AT yanjunshi bilevelpathplanningalgorithmformultiagvroutingproblem |