Simulation of Multi-layer Ship Evacuation System Based on Improved A* Algorithm

doi:10.16182/j.issn1004731x.joss.21-0075

Abstract

Abstract:

Aiming at the low efficiency of emergency evacuation at sea, an emergency evacuation system based on improved A* algorithm is proposed. Based on the network flow model, the traversal mode of the adjacency node is used to complete the path search, and the influence of the path personnel density and path obstacles is added to the calculation of the cost, which makes the algorithm more practical. In order to improve the efficiency of the algorithm, the node optimization of the network is carried out, and a multi-path optimal scheme is proposed in the case of single layer with multiple exits, and the quadratic planning is considered in case of congestion in the path. The results show that the system can provide an effective evacuation path for the multi-storey large cruise ships. It can not only effectively avoid road congestion, but also shorten the evacuation time. The evacuation effect is better than the traditional A* algorithm.

Key words: emergency evacuation, A* algorithm, path planning, network flow models

CLC Number:

TP391.9

Dun Meng, Zhuo Hu, Huajun Zhang. Simulation of Multi-layer Ship Evacuation System Based on Improved A* Algorithm[J]. Journal of System Simulation, 2022, 34(6): 1375-1382.

Figures/Tables 11

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

References 20

1	高飞. 客轮人员应急疏散模型构建及仿真研究[D]. 大连: 大连海事大学, 2017.
	Gao Fei. Construction and Simulation Study of Emergency Evacuation Model for Passenger Ship Personnel [D]. Dalian: Dalian Maritime University, 2017.
2	郝会龙, 任鸿翔, 肖方兵. 基于A*算法的虚拟船员路径规划仿真[J]. 计算机工程与设计, 2015, 36(3): 733-737.
	Hao Huilong, Ren Hongxiang, Xiao Fangbing. Simulation of Virtual Crew Path Planning Based on A* Algorithm [J]. Computer Engineering and Design, 2015, 36(3): 733-737.
3	阳小涛, 杨克俭, 闫春香. 虚拟人几何建模及运动控制方法的研究[J]. 计算机与数字工程, 2008, 36(8): 132-135.
	Yang Xiaotao, Yang Kejian, Yan Chunxiang. Research on Geometric Modeling and Motion Control of Virtual Human [J]. Computer and Digital Engineering, 2008, 36(8): 132-135.
4	王军华, 吕克志. 面向艺术与设计虚拟人技术比较研究[J]. 计算机系统应用, 2009, 18(5): 123-127.
	Wang Junhua, Kezhi Lü. Comparative Study on Virtual Human Technology for Art and Design [J]. Computer System Application, 2009, 18(5): 123-127.
5	Dou Z, Mebarki A, Cheng Y, et al. Review on the Emergency Evacuation in Chemicals-Concentrated Areas (Review)[J]. Journal of Loss Prevention in the Process Industries(S0950-4230), 2019, 60: 35-45.
6	孙迪, 周进, 高学英, 等. 地铁站内行人疏散路径选择仿真研究[J]. 系统仿真学报, 2019, 31(9): 1819-1826.
	Sun Di, Zhou Jin, Gao Xueying, et al. Simulation Research on Pedestrian Evacuation Path Selection in the Metro Station[J]. Journal of System Simulation, 2019, 31(9): 1819-1826.
7	宋英华, 张宇, 霍非舟, 等. 考虑避让行为的人员疏散元胞自动机模型研究[J]. 系统仿真学报, 2020, 32(6): 975-981.
	Song Yinghua, Zhang Yu, Huo Feizhou, et al. Study on Evacuation Cellular Automaton Model Considering Avoidance Behavior[J]. Journal of System Simulation, 2020, 32(6): 975-981.
8	Kebel A, WahleJetal Klupfel H. Microscopic Simulation of Pedestrian Crowd Motion Pedestrian and Evacuation[C]//Pedestrian and Evacuation Dynamics 2001. Berlin Springer: Verlag Heidelberg, 2002: 193-200.
9	Andreas Schadscheider. Cellular Automaton Approach to Pedestrian Dynamics Theory Pedestrian and Evacuation[C]//Pedestrian and Evacuation Dynamics 2001. Berlin Springer: Verlag Heideberg, 2002: 75-85.
10	邓媛媛, 郑利平, 蔡瑞文. 社会行为驱动的疏散仿真方法研究[J]. 系统仿真学报, 2020, 32(1): 130-141.
	Deng Yuanyuan, Zheng Liping, Cai Ruiwen. Research on Evacuation Simulation Method Considering Social Behavior[J]. Journal of System Simulation, 2020, 32(1): 130-141.
11	Helbing D, Farkas I, Vicsek T. Simulating Dynamical Features of Escape Panic[J]. Nature(S1476-4687), 2000, 407(6803): 487-490.
12	杨琪, 王维莉, 胡志华. 突发事件下邮轮应急疏散模拟及其验证[J]. 大连海事大学学报, 2018, 44(2): 27-32.
	Yang Qi, Wang Weili, Hu Zhihua. Simulation and Verification of Cruise Ship Emergency Evacuation Under Emergencies [J]. Journal of Dalian Maritime University, 2018, 44(2): 27-32.
13	谌海云, 陈华胄, 刘强. 基于改进人工势场法的多无人机三维编队路径规划[J]. 系统仿真学报, 2020, 32(3): 414-420.
	Chen Haiyun, Chen Huazhou, Liu Qiang. Multi-UAV 3D Formation Path Planning Based on Improved Artificial Potential Field[J]. Journal of System Simulation, 2020, 32(3): 414-420.
14	杨卫, 曾亮, 康新晨. 基于蚁群算法的群机器人自组织聚集行为建模[J]. 系统仿真学报, 2020, 32(2): 191-200.
	Yang Wei, Zeng Liang, Kang Xinchen. Self-Organizing Aggregation Behavior Modeling of Swarm Robots Based on Ant Colony Algorithm[J]. Journal of System Simulation, 2020, 32(2): 191-200.
15	何明, 陈国华, 杜有翔, 等. 基于Dijkstra算法的火灾环境下人员疏散仿真方法[J]. 中国安全科学学报, 2010, 20(12): 46-51.
	He Ming, Chen Guohua, Du Youxiang, et al. A Simulation Method of Personnel Evacuation Under Fire Environment Based on Dijkstra algorithm [J].Chinese Journal of Safety Science, 2010, 20(12): 46-51.
16	Fu B, Chen L, Zhou Y, et al. An Improved A* Algorithm for the Industrial Robot Path Planning with High Success Rate and Short Length [J]. Robotics ＆ Autonomous Systems(S0921-8890), 2018, 106: 26-37.
17	Zhang H M, Li M L, Yang L. Safe Path Planning of Mobile Robot Based on Improved A* Algorithm in Complex Terrains[J]. Algorithms(S1999-4893), 2018, 11(4): 44-50.
18	靳海亮, 王赢乐, 袁鸣, 等. 改进A*的高层建筑逃生路径规划算法研究[J]. 测绘通报, 2019(11): 17-21.
	Jin Hailiang, Wang Yingle, Yuan Ming, et al. Research on Improved A* High-Rise Building Escape Path Planning Algorithm [J]. Bulletin of Surveying and Mapping, 2019(11): 17-21.
19	Fruin J J. Design for Pedestrians a Level of Service[D]. New York: Polytechnic Institute of Brooklyn, 1970.
20	张学锋, 白晨曦. 双层教学楼人员疏散仿真研究[J]. 系统仿真学报, 2017, 29(5): 1070-1076.
	Zhang Xuefeng, Bai Chenxi. Study of Crowd Evacuation in Two-storey Teaching Building[J]. Journal of System Simulation, 2017, 29(5): 1070-1076.

路径号	走向
1	P_start→stair_{1_1}→stair_{2_1}→stair_{3_1}→P_des
2	P_start→stair_{1_1}→stair_{2_1}→stair_{2_2}→stair_{3_2}→P_des
3	P_start→stair_{1_2}→stair_{2_2}→stair_{3_2}→P_des
4	P_start→stair_{1_2}→stair_{2_2}→stair_{2_1}→stair_{3_1}→P_des

[1]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[2]	Ni Peilong, Mao Pengjun, Wang Ning, Yang Mengjie. Robot Path Planning Based on Improved A-DDQN Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2420-2430.
[3]	Zhang Kaixiang, Mao Jianlin, Wang Niya, Xu Zhihao. Multi-robot Hierarchical Collaborative k-robust Path Planning for Path Interference [J]. Journal of System Simulation, 2025, 37(8): 2074-2088.
[4]	Wan Yuhang, Zhu Zilu, Zhong Chunfu, Liu Yongkui, Lin Tingyu, Zhang Lin. Dynamic Path Planning for Robotic Arms Based on an Improved PPO Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1462-1473.
[5]	Ye Chen, Shao Peng, Zhang Shaoping, Li Wenting, Zhou Tengming. Enhanced Artificial Gorilla Algorithm for Mobile Robot Path Planning [J]. Journal of System Simulation, 2025, 37(6): 1474-1485.
[6]	Zhang Yan, Li Binghua, Huo Tao, Liu Rong. Research on Robot Dynamic Obstacle Avoidance Method Based on Improved A* and Dynamic Window Algorithm [J]. Journal of System Simulation, 2025, 37(6): 1555-1564.
[7]	Zhou Xiaohui, Li Yanqiang, Wang Yong, Zhao Decai, Yang Xiaoyao. Robot Path Planning Based on Ant Colony Algorithm with Dual Heuristic Information [J]. Journal of System Simulation, 2025, 37(5): 1280-1289.
[8]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[9]	Zhang Sen, Dai Qiangqiang. UAV Path Planning Based on Improved Deep Deterministic Policy Gradients [J]. Journal of System Simulation, 2025, 37(4): 875-881.
[10]	He Zhigang, Li Dayan, Wang Niya, Mao Jianlin, Wang Ning. A Multi-robot Collaborative Path Planning Algorithm with Chain Working Mode [J]. Journal of System Simulation, 2025, 37(4): 953-967.
[11]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[12]	Bai Yuxin, Chen Zhenya, Shi Ruitao, Su Weitao, Ma Zhuoqiang, Yang Shangjin. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2025, 37(3): 742-752.
[13]	Jin Xu, Mo Yuanbin. Multi-strategy Hybrid Mountain Gazelle Optimizer for Robot Path Planning [J]. Journal of System Simulation, 2025, 37(3): 803-821.
[14]	Li Jiongyi, Li Qiang, Zhang Xinwen, Htet Zin Myo, Cai Yongbin. Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2025, 37(2): 498-507.
[15]	Peng Yi, Lei Yunkui, Yang Qingqing, Li Hui, Wang Jianming. Improved PID Search Algorithm for UAV Path Planning in Mountainous Environments [J]. Journal of System Simulation, 2025, 37(12): 3075-3086.