Automatic guided vehicles (AGVs) are an important component of workshop logistics distribution systems. With the continuous increase in human cost, unmanned workshops are becoming increasingly popular, and an increasing number of AGVs are being applied to workshop logistics distribution systems. However, with the increasing number of AGVs in the workshop, planning a path quickly for each AGV is challenging, and the response time of multi-AGV fast path planning cannot meet actual requirements. To solve this problem, a multi-AGV fast path planning method based on an improved conflict-based search (ICBS) algorithm is proposed. First, the path planning problem is analyzed, and the environment expression, task, objective and constraint models are established. Subsequently, a two-layer ICBS algorithm is proposed to achieve fast path planning. At the bottom layer, an improved A* algorithm is adopted, and the selection strategy of the nodes is changed when multiple minimum values are equal. In the upper layer, the conflict number, conflict objective and conflict constraint sets are established. Three priority rules including Most Conflicts First (MCF) rule, Earliest Conflict First (ECF) rule, Single Search for Conflict Point (SSCP) rule are used. And a conflict elimination strategy is proposed. Finally, the superiority of the algorithm-solving is verified based on benchmark and actual workshop maps.
YuanMLiYZhangL, et al. Research on intelligent workshop resource scheduling method based on improved NSGA-II algorithm. Robot Comput Integr Manuf2021; 71: 1–8.
2.
ZhongRYXuXKlotzE, et al. Intelligent manufacturing in the context of industry 4.0: a review. Engineering2017; 3(5): 616–630.
3.
ZouWQPanQKTasgetirenMF. An effective iterated greedy algorithm for solving a multi-compartment AGV scheduling problem in a matrix manufacturing workshop. Appl Soft Comput2021; 99: 1–17.
4.
AlmadhounRTahaTSeneviratneL, et al. A survey on multi-robot coverage path planning for model reconstruction and mapping. SN Appl Sci2019; 1: 1–24.
5.
ParappagoudarDMandavaRKVundavilliPR, et al. An efficient path planning algorithm for the biped robot in a static environment using fast sweeping method. Proc IMechE, Part C: J Mechanical Engineering Science2022; 236: 7417–7425.
6.
ZhangJWangXXuL, et al. An occupancy information grid model for path planning of intelligent robots. ISPRS Int J Geo-Inf2022; 11: 231.
7.
ZhangHZhuangQLiG. Robot path planning method based on indoor spacetime grid model. Remote Sens2022; 14: 2357.
8.
HeYLiuYTJinYH, et al. Context-consistent generation of indoor virtual environments based on geometry constraints. IEEE Trans Vis Comput Graph2022; 28: 3986–3999.
9.
ZhouXXieQGuoM, et al. Accurate and efficient indoor pathfinding based on building information modeling data. IEEE Trans Ind Inform2020; 16: 7459–7468.
10.
WangHChenW. Multi-robot path planning with due times. IEEE Robot Autom Lett2022; 7: 4829–4836.
11.
JinYYueMLiW, et al. An improved target-oriented path planning algorithm for wheeled mobile robots. Proc IMechE, Part C: J Mechanical Engineering Science2022; 236: 11081–11093.
12.
QingGZhengZYueX, et al. Path-planning of automated guided vehicle based on improved Dijkstra algorithm. In: 29th Chinese Control and Decision Conference (CCDC), Chongqing, China, 28–30 May 2017, pp.7138–7143.
13.
TangGTangCClaramuntC, et al. Geometric A-star algorithm: an improved A-star algorithm for AGV path planning in a port environment. IEEE Access2021; 9: 59196–59210.
14.
LiKHuQLiuJ. Path planning of mobile robot based on improved multiobjective genetic algorithm. Wirel Commun Mob Comput2021; 2021: 1–12.
15.
WangMZhuCWangF, et al. Multi-factor of path planning based on an ant colony optimization algorithm. Ann GIS2020; 26: 101–112.
16.
SharonGSternRFelnerA, et al. Conflict-based search for optimal multi-agent pathfinding. Artif Intell2015; 219: 40–66.
17.
XueWYYingRDGongZ, et al. SLAM based topological mapping and navigation. In: Proceedings of the 2020 IEEE/ION position, location and navigation symposium (PLANS), Portland, OR, 20–23 April 2020, pp.1336–1341.
18.
ChengHChenHLiuY. Topological indoor localization and navigation for autonomous mobile robot. IEEE Trans Autom Sci Eng2015; 12: 729–738.
19.
YuanMHLiYDPeiFQ, et al. Dual-resource integrated scheduling method of AGV and machine in intelligent manufacturing job shop. J Cent South Univ2021; 28: 2423–2435.
20.
LiuXMaoZ. MPMVPSO algorithm for robot path planning considering LIM grid model. Control Eng China2021; 28(6): 1255–1262.
21.
MiaoCChenGYanC, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Comput Ind Eng2021; 156: 1–10. DOI: 10.1016/j.cie.2021.107230
22.
LiKLiuTRuanY. Research on intelligent AGV routing scheduling with applications in semi-conductor production. Comput Integr Manuf Syst2022, 28(09): 2970–2980.
SureshKSVenkatesanRVenugopalS. Mobile robot path planning using multi-objective genetic algorithm in industrial automation. Soft Comput2022; 26: 7387–7400.
25.
ZhangLZhangYLiY. Mobile robot path planning based on improved localized particle swarm optimization. IEEE Sens J2021; 21: 6962–6972.
26.
TaoQSangHGuoH, et al. Improved particle swarm optimization algorithm for AGV path planning. IEEE Access2021; 9: 33522–33531.
27.
HouWXiongZWangC, et al. Enhanced ant colony algorithm with communication mechanism for mobile robot path planning. Robot Auton Syst2022; 148: 1–10. DOI: 10.1016/j.robot.2021.103949
28.
YuJLiRFengZ, et al. A novel parallel ant colony optimization algorithm for warehouse path planning. Journal Control Science Eng2020; 2020: 1–12.
AlshammreiSBoubakerSKolsiL. Improved Dijkstra algorithm for mobile robot path planning and obstacle avoidance. CMC Comput Mater Contin2022; 72: 5939–5954.
31.
WangCWangLQinJ, et al. Path planning of automated guided vehicles based on improved A-star algorithm. In: IEEE International conference on information and automation, 2015, Lijiang, China, 8–10 August 2015, pp.2071–2076. New York: IEEE.
32.
LiuYChenMHuangH, et al. Multi-agent pathfinding based on improved cooperative A* in Kiva system. In: 5th International conference on control, automation and robotics (ICCAR), Beijing, China, 19–22 April 2019, pp.633–638.
33.
XuBZhangJWangC. A real-time obstacle avoidance method for multi-AUV cluster based on artificial potential field. Chin J Ship Res2018; 13: 66–71.
34.
YuJLaValleSM. Optimal multirobot path planning on graphs: complete algorithms and effective heuristics. IEEE Trans Robot2016; 32: 1163–1177.
35.
GaoJZhengXGaoF, et al. Heterogeneous multitype fleet green vehicle path planning of automated guided vehicle with time windows in flexible manufacturing system. Machines2022; 10: 197.
36.
HuHYangXXiaoS, et al. Anti-conflict AGV path planning in automated container terminals based on multi-agent reinforcement learning. Int J Prod Res2023; 61: 65–80.
37.
SharonGSternRGoldenbergM, et al. The increasing cost tree search for optimal multi-agent pathfinding. Artif Intell2013; 195: 470–495.
38.
FelnerALiJBoyarskiE, et al. Adding heuristics to conflict-based search for multi-agent path finding. In: 28th International conference on automated planning and scheduling (ICAPS 2018), Delft Univ Technol, Delft, The Netherlands, 24–29 June 2018, pp.83–87.
39.
BarerMSharonGSternR, et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In: 21st European conference on artificial intelligence (ECAI 2014), Czech Tech Univ, Prague, Czech Republic, 18–22 August 2014, pp.961–962.
40.
LiJFeinerABoyarskiE, et al. Improved heuristics for multi-agent path finding with conflict-based search. In: 28th International joint conference on artificial intelligence, Macao, China, 10–16 August 2019, pp.442–449.
