Solution of Mixed Integer Linear Programming for Multi-target Pursuit Problem

Abstract

Abstract: The path planning for multi-target pursuit (MTP) is studied. Two MTP models, the nearest target pursuit and one-vehicle-one-target enable pursuit, based on the mixed integer linear programming (MILP) are presented. In the two MTP models, the dynamic equation of mass point with linear damping is taken as the state equation of vehicle motion. Integer variables are used to describe the relative position of vehicle and obstacle. Target expansion size is proposed to describe the pursuit process for target. Pursuit direction of vehicle is defined. The isometric plane method selecting integer variables is used to solve MILP pursuit problem. How to select the integer variables in initial inner point is also given. Finally, simulation experiment 1 is given to make comparisons between two MTP models and simulation experiment 2 to show the efficiency of the method.

Key words: Isometric plane method, Mixed integer linear programming (MILP), Multi-target pursuit (MTP), Path planning, Target expansion size

CLC Number:

TP24

YANG Liying;WU Chengdong;HAN Jianda;NIE Yiyong. Solution of Mixed Integer Linear Programming for Multi-target Pursuit Problem[J]. , 2008, 44(10): 51-59.

[1]	DENG Jianxin, YUAN Bangyi, HUANG Qiulin, DING Dukun, XIN Manyu, LIU Guangming. Review on the Key Technologies of Complex Surfaces Polishing Based on Robots [J]. Journal of Mechanical Engineering, 2024, 60(7): 1-21.
[2]	ZHANG Weimin, XU Sensheng, ZHANG Yue. Research on Path Planning of Indoor Inspection Robot Based on Improved A^* Algorithm [J]. Journal of Mechanical Engineering, 2024, 60(20): 315-326.
[3]	WANG Xiaofei, XU Jiazhong, DING Liang, HUANG Cheng, YANG Huaiguang, LIU Meijun. Tendentious Chained Path Planning Algorithm [J]. Journal of Mechanical Engineering, 2024, 60(19): 53-61.
[4]	XU Wenlin, PENG Yu, HE Zhicheng, JIANG Chao. Kinematic Topological Configuration Design of Mechanism Partitions for Complex Path Planning [J]. Journal of Mechanical Engineering, 2024, 60(11): 62-73.
[5]	HU Lin, YANG Dongzhao, ZHANG Xin, ZHANG Jie, LIAO Jiacai. Dynamic Path Planning of Intelligent Vehicle Overtaking Lane Change Based on DQP-LMPC [J]. Journal of Mechanical Engineering, 2024, 60(10): 171-181.
[6]	NIE Shida, LIU Hui, LIAO Zhihao, XIE Yujia, XIANG Changle, HAN Lijin, LIN Sihao. Study on Path Planning for Off-road Autonomous Vehicles in Complex Terrains [J]. Journal of Mechanical Engineering, 2024, 60(10): 261-272.
[7]	LIN Chen, WEI Hongqian, JING Wei, ZHANG Youtong. Automotive Functional Safety: Risk Mitigation Control of Path Planning for Autonomous Vehicles towards Sensitive Command Attack Scenarios [J]. Journal of Mechanical Engineering, 2024, 60(10): 302-316.
[8]	PU Xuejie, ZHANG Jianhui, LI Jianyong, ZHANG Jiannan. Path Planning Method for Solving Implicit Contradiction for Complex Technical System [J]. Journal of Mechanical Engineering, 2024, 60(1): 309-328.
[9]	XIANG Hongbiao, YANG Dahu, YANG Lu, WANG Shoujun, ZHANG Mian, HUANG Xian, HUO Wenxing. Path Planning and Recognition Tracking of a Magnetoelastic Miniature Swimmer in Complex Environment [J]. Journal of Mechanical Engineering, 2023, 59(5): 89-99.
[10]	WU Hongyu, NIU Wendong, ZHANG Yuling, WANG Shuxin, YAN Shaoze. Path Planning Method for Multi-point Exploration of Underwater Glider to Minimize Energy Consumption [J]. Journal of Mechanical Engineering, 2023, 59(5): 156-166.
[11]	CUI Yuping, ZHENG Guolei. Research Progress of Cable Layout Design Technology: A Review [J]. Journal of Mechanical Engineering, 2023, 59(2): 268-280.
[12]	DAI Jiajia, GONG Xiaoxi, WANG Jun. Coverage Path Planning Method of Unmanned Aerial Vehicle for Aircraft Surface Detection Task [J]. Journal of Mechanical Engineering, 2023, 59(16): 243-253.
[13]	HUANG Lin, ZHAO Shikui, HUANG Sen. Hybrid Algorithm Based on Obstacle Graph Model and Tabu Search for Job Shop Scheduling Problem [J]. Journal of Mechanical Engineering, 2023, 59(16): 435-444,426.
[14]	YAN Lutao, WANG Qi, LI Haiyuan, ZHANG Qinjian. Path Planning of Continuum Robot Actuated by Shape Memory Alloy [J]. Journal of Mechanical Engineering, 2023, 59(15): 50-61.
[15]	WEI Lingtao, WANG Xiangyu, QIU Bin, LI Liang, ZHOU Daolin, LIN Jingui. Tracking and Collision Avoidance of Autonomous Vehicle Based on Adaptive Preview Path [J]. Journal of Mechanical Engineering, 2022, 58(6): 184-193.

Solution of Mixed Integer Linear Programming for Multi-target Pursuit Problem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments